Paper deep dive
Adaptive Symmetry Discovery for Dynamical System Identification
Behrooz Tahmasebi, Melanie Weber
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/11/2026, 5:11:17 AM
Summary
This paper addresses the problem of adaptive symmetry discovery for dynamical system identification. It demonstrates that systems with known symmetries can be identified from significantly shorter single trajectories than generic systems. The authors propose a method to automatically discover the unknown symmetry group from a single trajectory and incorporate it into the identification procedure, achieving optimal trajectory length. The analysis utilizes group representation theory and the expander properties of Cayley graphs.
Entities (7)
Relation Signals (6)
Symmetry → formalizedas → Equivariance
confidence 96% · symmetries imposed by physical laws, formalized through equivariance with respect to group actions
Dynamical Systems → exhibits → Symmetry
confidence 95% · dynamical systems are not generic but often exhibit symmetries imposed by physical laws
Analysis → relieson → Group Representation Theory
confidence 95% · Our analysis relies on tools from group representation theory
Adaptive Symmetry Discovery → enables → System Identification
confidence 94% · proposing a method to learn the symmetry group directly from a single trajectory and incorporate it into the identification procedure
Analysis → relieson → Cayley Graphs
confidence 94% · Our analysis relies on tools from ... the expander properties of Cayley graphs
Feature-lifted Linear Dynamical Systems → isa → Nonlinear Dynamics
confidence 90% · study a class of nonlinear dynamics that become linear after a finite-dimensional lifting of the state
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Dynamical systems model trajectory data generated by fixed underlying dynamics, with applications ranging from biology to physics. Especially in scientific settings, dynamical systems are not generic but often exhibit symmetries imposed by physical laws, formalized through equivariance with respect to group actions. The identification problem concerns recovering the parameters of a system from observed trajectories. In this work, we study adaptive symmetry discovery for dynamical system identification and address how a system can be identified from a single trajectory when it is equivariant with respect to an unknown symmetry group. To this end, we first show that for known symmetries, the system can be identified from a significantly shorter single trajectory than in the generic setting, and we precisely characterize this improvement. We then consider the automatic symmetry discovery setting, proposing a method to learn the symmetry group directly from a single trajectory and incorporate it into the identification procedure, achieving the same optimal trajectory length as in the known-symmetry case. Our analysis relies on tools from group representation theory and the expander properties of Cayley graphs, and may be of independent interest for the study of symmetries in dynamical systems.
Tags
Links
- Source: https://arxiv.org/abs/2608.08091v1
- Canonical: https://arxiv.org/abs/2608.08091v1
Trouble viewing inline? Open PDF directly →
Full Text
115,047 characters extracted from source content.
Expand or collapse full text
Adaptive Symmetry Discovery for Dynamical System Identification Behrooz Tahmasebi111Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA. Emails: behrooz_tahmasebi,mweber@seas.harvard.edu Melanie Weber11footnotemark: 1 Abstract Dynamical systems model trajectory data generated by fixed underlying dynamics, with applications ranging from biology to physics. Especially in scientific settings, dynamical systems are not generic but often exhibit symmetries imposed by physical laws, formalized through equivariance with respect to group actions. The identification problem concerns recovering the parameters of a system from observed trajectories. In this work, we study adaptive symmetry discovery for dynamical system identification and address how a system can be identified from a single trajectory when it is equivariant with respect to an unknown symmetry group. To this end, we first show that for known symmetries, the system can be identified from a significantly shorter single trajectory than in the generic setting, and we precisely characterize this improvement. We then consider the automatic symmetry discovery setting, proposing a method to learn the symmetry group directly from a single trajectory and incorporate it into the identification procedure, achieving the same optimal trajectory length as in the known-symmetry case. Our analysis relies on tools from group representation theory and the expander properties of Cayley graphs, and may be of independent interest for the study of symmetries in dynamical systems. Contents 1 Introduction 2 Related Work 3 Problem Statement 3.1 Feature-lifted linear dynamical systems 3.2 Equivariant dynamics 3.3 Identifiability from a single trajectory 4 Main Results 4.1 Sample complexity of equivariant identification 4.2 Adaptive symmetry discovery 5 Conclusion and Future Work References A Preliminaries A.1 Groups, representations, and equivariance A.2 Cayley graphs, expanders, and random generators B Proofs of Main Results B.1 Proof of Theorem 4.1 B.2 Proofs for adaptive symmetry discovery B.3 Proof of Theorem 4.11 C Experiments D Notation 1 Introduction The classical scientific approach has long relied on discovering fundamental laws of nature expressed through simple and interpretable equations. The recent abundance of data, together with rapid advances in machine learning and deep learning, has given rise to a complementary scientific paradigm: inferring governing laws and equations directly from data using principled methodologies rather than ad hoc modeling assumptions. Among many modeling frameworks, dynamical systems constitute one of the most fundamental mathematical formalisms for describing flows, trajectory data, and non-independent evolutionary processes in the sciences, with applications ranging from biological systems to physical flows (Brunton et al., 2016; Yu and Wang, 2024; Wang and Yu, 2025). The problem of discovering governing equations from data, often formulated through the lens of dynamical systems (Brunton et al., 2016), has the potential to uncover previously unknown scientific principles and to significantly accelerate scientific discovery. To this end, a central task is to learn the parameters of a dynamical system from data (observed trajectories), a problem commonly referred to as dynamical system identification. As a well-studied topic in system identification, a wide range of approaches and algorithms have been developed to address this problem across various settings (Van Overschee and De Moor, 2012; Isermann and Münchhof, 2011). In the context of scientific discovery from data, however, dynamical systems are often not generic. Instead, they are structured and frequently exhibit (potentially unknown) symmetries imposed by physical laws, formalized as equivariance with respect to a (possibly unknown) group action. The field of geometric machine learning studies how and when such symmetries can be exploited to improve learning and generalization (Bronstein et al., 2021; Weber, 2025). In this work, we focus on the intersection of geometric machine learning and dynamical system identification. Motivated by these considerations, we study the problem of adaptive symmetry discovery for dynamical system identification. Focusing on single-trajectory data and finite groups, the central question we address is how to identify a system when it is equivariant with respect to an unknown symmetry group, and how to automatically discover and exploit this symmetry to improve sample efficiency, namely by enabling identification from shorter trajectories. First, we show that when the symmetry group is known, the system can be identified from significantly shorter trajectories than in the generic setting, and we precisely characterize this improvement. Second, we turn to the automatic symmetry discovery setting and propose a method to learn the symmetry group directly from a single trajectory and to incorporate it into the identification procedure. Our approach achieves the same optimal trajectory length as in the known-symmetry case. Consequently, under mild conditions, symmetry discovery incurs negligible overhead, allowing one to fully leverage the benefits of equivariance. It is worth noting that, while a number of recent studies are closely related to our work (as outlined in the related work section), most existing methods are heuristic or model-specific, and provable quantitative guarantees for symmetry discovery in dynamical systems are lacking. In contrast, our focus is on understanding the theoretical and foundational limits of this problem, which, to the best of our knowledge, have been largely unexplored in the literature. Finally, we emphasize that the tools used in this paper, drawing from group representation theory and the expansion properties of Cayley graphs for finite groups, introduce techniques that are new to this context and may be of independent interest for the study of symmetries in dynamical systems and beyond. In short, in this paper we make the following contributions: • We study the problem of automatic symmetry discovery for dynamical system identification, with a focus on adapting to unknown finite group invariances. • We show that symmetries can drastically reduce the trajectory length required to identify a system, and that this benefit can be achieved even when the symmetry is unknown by exploiting a new formulation that enables adaptation to the underlying symmetry. • Our analysis leverages tools from group representation theory and the expander properties of Cayley graphs, which may be of independent interest for the broader study of symmetric and equivariant dynamical systems. 2 Related Work Recently, the problem of learning dynamical systems from data has received particular attention, driven by applications across the sciences and physics-guided machine learning (Brunton et al., 2016; Yu and Wang, 2024; Wang and Yu, 2025; Sivaranjani et al., 2025). From a theoretical perspective, characterizing when and how a dynamical system can be identified from data is a classical and well-studied problem in system identification (Van Overschee and De Moor, 2012; Isermann and Münchhof, 2011). More recently, significant effort has focused on learning dynamical systems from noisy observations, a setting that goes beyond, and is substantially more challenging than, the noiseless identification regime. For example, Simchowitz et al. (2018) study the identification of linear dynamical systems from a single noisy trajectory, with subsequent extensions to nonlinear systems under similar single-trajectory assumptions (Foster et al., 2020; Ziemann et al., 2022). Beyond this, prior work has also investigated finite-sample identification of linear time-invariant systems (Sarkar and Rakhlin, 2019; Sarkar et al., 2021), regimes involving multiple trajectories (Tu et al., 2024), as well as system identification and control over a single trajectory (Fefferman et al., 2022; Carruth et al., 2022, 2024). In contrast, the focus of this paper is on the identification of dynamical systems simultaneously with symmetry discovery. As a first step toward this goal, we focus on the noiseless single-trajectory setting, which allows us to study the fundamental role of symmetry without additional statistical complications. Although known symmetries are known to provide both empirical and theoretical benefits in learning and estimation, including improved generalization guarantees (Tahmasebi and Jegelka, 2023, 2024), in many applications the relevant symmetries exist but are not known a priori. In such settings, symmetries must be detected or discovered directly from data, as commonly encountered in the discovery of physical laws governed by differential equations. The research direction of automatic symmetry discovery seeks to identify underlying symmetries in a principled manner, moving beyond ad hoc or manually engineered approaches. A wide range of methods for symmetry discovery have been proposed in the literature. Deep learning approaches for symmetry discovery have been explored in several works (Desai et al., 2022; Yang et al., 2023; Perin and Deny, 2025), including Lie algebra–based convolutional networks (Dehmamy et al., 2021); see also (Romero and Lohit, 2022; Ko et al., 2024; Hu et al., 2025c). Methods based on infinitesimal generators for discovering symmetries in nonlinear dynamical data have also been studied (Hu et al., 2025a); see (Shaw et al., 2025) for related approaches. Beyond these, methods for discovering nonlinear group actions in latent spaces have been proposed (Yang et al., 2024a), including approaches that go beyond affine transformations and address manifold-structured data (Shaw et al., 2024; Bhat et al., 2025). Another line of work learns symmetries from layer gradients to relax hard invariance constraints (van der Ouderaa et al., 2023), while flow matching has recently been used to discover Lie group symmetries (Park et al., 2025). For symmetry discovery in differential equations and PDEs, see (Kreider et al., 2025; Hu et al., 2025b; Yang et al., 2025, 2024b). Other approaches include quadratic-form-based methods (Karjol et al., 2025) and learnable data augmentation strategies (Santos-Escriche and Jegelka, 2025). For symmetry discovery in finite groups using representation-theoretic tools, see (Huh, 2025). Jointly discovering and enforcing symmetries has also been studied (Otto et al., 2025). Finally, we note that symmetry discovery is fundamentally different from (binary) hypothesis testing for the presence of symmetry in data (Soleymani et al., 2025b). There has also been recent work on symmetry discovery, specifically in dynamical systems. Data-driven detection of Lie point symmetries for continuous dynamical systems is studied in Gabel et al. (2024), while the discovery of finite symmetry groups in dynamical systems is considered in Calvo-Barlés et al. (2025a, b). A related approach is proposed in Li et al. (2025), where the authors introduce latent mixtures of symmetries to model dynamical systems with multiple symmetric latent components. Finally, we note that a variety of approaches have been proposed to introduce and exploit symmetries in learning, ranging from canonicalization (Kaba et al., 2023; Tahmasebi and Jegelka, 2025b, a; Shumaylov et al., 2025) and frame averaging (Puny et al., 2022; Atzmon et al., 2022; Lin et al., 2024) to data augmentation (Tahmasebi et al., 2025). In contrast, this paper introduces an approach based on generating sets of groups and their expansion properties, with close connections to recent work on approximate symmetry (Tahmasebi and Weber, 2025) and learning under invariances (Soleymani et al., 2025c, a). 3 Problem Statement We first introduce the basic notation and formalize the class of dynamical systems studied in this paper. A detailed review of the required background is deferred to Appendix A. Dynamical systems. A (discrete-time) dynamical system is specified by a function f:ℂd→ℂd,f:C^d ^d, which governs the state evolution according to xt+1=f(xt),t=0,1,…,x_t+1=f(x_t), t=0,1,…, (1) where xt=(xt1,xt2,…,xtd)⊤∈ℂdx_t=(x_t^1,x_t^2,…,x_t^d) ^d denotes the state of the system at time t. We refer to f as the dynamics of the system and assume that f belongs to a function class ℱF. Trajectories and learning objective. Given an initial state x0∈ℂdx_0 ^d, the dynamics f generates a trajectory (x0,x1,…,xT)∈ℂd×(T+1),(x_0,x_1,…,x_T) ^d×(T+1), where T∈ℕT denotes the number of observed transitions. In the system identification problem, a learner observes such a trajectory and aims to recover the underlying unknown dynamics f∈ℱf . Clearly, if the function class ℱF is too rich, recovering f from a finite-length trajectory is impossible. This motivates restricting attention to structured and low-complexity families of dynamics. 3.1 Feature-lifted linear dynamical systems In this work, we study a class of nonlinear dynamics that become linear after a finite-dimensional lifting of the state. Let Φ:ℂd→ℂm :C^d ^m be an analytic feature map, and consider dynamics of the form xt+1=f(xt)=WΦ(xt),W∈ℂd×m.x_t+1=f(x_t)=W (x_t), W ^d× m. (2) We refer to Φ as the feature map and to ℂmC^m as the feature space. For convenience, we write ϕt≔Φ(xt)∈ℂm. _t (x_t) ^m. Without loss of generality, we assume that Φ has linearly independent coordinates as functions of x∈ℂdx ^d. Definition 3.1 (Feature-lifted linear dynamical systems). Let Φ:ℂd→ℂm :C^d ^m be a fixed finite-dimensional feature map. We define ℱΦ≔f:ℂd→ℂd|f(x)=WΦ(x):∀W∈ℂd×m.F_ \f:C^d ^d\; |\;f(x)=W (x):∀~W ^d× m \. Thus, every system in ℱΦF_ is nonlinear in the state x in general, but linear in the lifted features Φ(x) (x). This modeling assumption encompasses a rich family of nonlinear dynamical systems while retaining a linear parameterization in feature space. The choice of Φ determines the expressive power of the class, and later sections characterize how the representation-theoretic structure of the feature space controls the trajectory length needed for identifying the system. Example 3.2 (Polynomial features). A canonical choice is the polynomial feature map consisting of all monomials of total degree at most k∈ℕk : Φ≤k(x)=((x1)α1(x2)α2⋯(xd)αd)α∈ℐk∈ℂm, _≤ k(x)= ((x^1) _1(x^2) _2·s(x^d) _d )_α _k ^m, where ℐk=α∈ℤ≥0d|∑i=1dαi≤k.I_k= \α _≥ 0^d\; |\; _i=1^d _i≤ k \. The feature dimension is m=(d+kd).m= d+kd. We denote the corresponding class by ℱ≤k≔ℱΦ≤k.F_≤ k _ _≤ k. This recovers polynomial dynamical systems of total degree at most k∈ℕk . Example 3.3 (Fourier features). Another canonical choice is a finite band-limited Fourier feature map. Let Λ⊂ℤd ^d be a finite set of frequencies, for instance Λ=w∈ℤd:‖w‖2≤C =\w ^d:\|w\|_2≤ C\ for some C>0C>0. Define Φ(x)=(e2πi⟨w,x⟩)w∈Λ∈ℂ|Λ|. (x)= (e^2π i w,x )_w∈ ^| |. The corresponding class ℱ=ℱΦF=F_ consists of dynamics whose coordinates are trigonometric polynomials supported on Λ . Example 3.4 (Linear and affine systems). Linear and affine dynamical systems are included as special cases of polynomial lifting. Indeed, a linear system xt+1=W1xt,W1∈ℂd×d,x_t+1=W_1x_t, W_1 ^d× d, and an affine system xt+1=W1xt+w0,W1∈ℂd×d,w0∈ℂd,x_t+1=W_1x_t+w_0, W_1 ^d× d,\;w_0 ^d, belong to ℱ≤1F_≤ 1, since Φ≤1 _≤ 1 contains the constant feature and all coordinate functions. 3.2 Equivariant dynamics We now introduce the notion of symmetry in dynamical systems. Intuitively, a dynamical system is symmetric if transformations applied to its input state induce predictable and consistent transformations of its output state. For example, rotating the input state results in a correspondingly rotated output. Such structure reflects underlying invariances often imposed by physical laws and is pervasive in scientific and engineering applications. In this work, we formalize symmetry through the notion of equivariance. We begin by briefly reviewing the necessary group-theoretic background. Groups and representations. A finite group G is a finite set equipped with an associative binary operation, an identity element, and inverses for all elements. Common examples include finite rotation groups, reflection groups, and the permutation group on n elements, consisting of all bijections σ:[n]→[n]σ:[n]→[n] under composition. A linear representation of a group G on ℂnC^n is a homomorphism ρ:G→GLn(ℂ)ρ:G _n(C), assigning to each g∈Gg∈ G an invertible matrix ρ(g)∈ℂn×nρ(g) ^n× n such that ρ(gh)=ρ(g)ρ(h),∀g,h∈G.ρ(gh)=ρ(g)ρ(h), ∀ g,h∈ G. We refer to ρ(g)ρ(g) as the action of g on ℂnC^n. Lifted group actions. Suppose a finite group G acts linearly on the state space ℂdC^d via a representation ρ:G→GLd(ℂ)ρ:G _d(C). We assume that the feature map Φ:ℂd→ℂm :C^d ^m is compatible with this action, in the sense that there exists a representation ρΦ:G→GLm(ℂ) _ :G _m(C) satisfying Φ(ρ(g)x)=ρΦ(g)Φ(x),∀g∈G,x∈ℂd. (ρ(g)x)= _ (g) (x), ∀ g∈ G,\;x ^d. (3) Thus, the group action on the state space induces a corresponding linear action on the feature space. This compatibility holds for the canonical feature maps considered in this paper, including polynomial features and finite Fourier features whenever the feature dictionary is closed under the action of G. We are now ready to define equivariant dynamical systems. Definition 3.5 (Equivariant dynamical systems). Let G be a finite group acting on ℂdC^d via a representation ρ. A dynamical system f:ℂd→ℂdf:C^d ^d is said to be G-equivariant if f(ρ(g)x)=ρ(g)f(x),∀g∈G,x∈ℂd.f(ρ(g)x)=ρ(g)f(x), ∀ g∈ G,\;x ^d. (4) For feature-lifted linear dynamical systems f(x)=WΦ(x)∈ℱΦf(x)=W (x) _ , G-equivariance is equivalently enforced by the intertwining condition ρ(g)W=WρΦ(g),∀g∈G.ρ(g)W=W _ (g), ∀ g∈ G. We denote by ℱΦGF_ ^G the class of G-equivariant feature-lifted linear dynamical systems with feature map Φ . This condition expresses the commutation of the parameter matrix W with the group actions on the state and feature spaces, respectively. Remark 3.6. Throughout the paper, we use the terms symmetric and equivariant interchangeably when referring to dynamical systems. The term equivariant is used when emphasizing the underlying group action. 3.3 Identifiability from a single trajectory We now formalize the notion of identifiability. Definition 3.7 (Generic identifiability). Fix a feature map Φ:ℂd→ℂm :C^d ^m, a finite group G, and consider the class ℱΦGF_ ^G. The dynamics within this class are said to be generically identifiable from trajectories of length T∈ℕT if, for almost all initial states x0∈ℂdx_0 ^d and almost all G-equivariant parameter matrices W∈ℂd×mW ^d× m, the corresponding trajectory (x0,x1,…,xT)∈ℂd×(T+1)(x_0,x_1,…,x_T) ^d×(T+1) uniquely determines W. The minimal such T is denoted by TΦ(G)T_ (G). Here, “generic” is understood in the standard sense: identifiability holds outside a set of measure zero in the space of initial states and G-equivariant parameters. This notion allows us to exclude pathological configurations while retaining full generality. When identifiability holds for trajectories of length T, we informally refer to T as the sample complexity of the identification problem, since each transition provides one observation of the dynamics. Remark 3.8. The notation TΦ(G)T_ (G) emphasizes that the trajectory length depends not only on the symmetry group G, but also on the feature map Φ . Later, we characterize this dependence through the representation-theoretic decomposition of the feature space and the generic excitation rank induced by Φ . Symmetry discovery. Consider an unknown G-equivariant dynamical system f:ℂd→ℂdf:C^d ^d, where the underlying symmetry group G is unknown. We assume, however, that G belongs to a known class of admissible finite groups G. While the specific group G∈G is not known a priori, prior knowledge of the class G provides structural information that can be leveraged for system identification. We are primarily interested in settings where G consists of relatively large finite groups, as such symmetries can lead to substantial reductions in the trajectory length required for identifiability. At the same time, the unknown identity of G introduces a nontrivial challenge, as the learner must simultaneously identify the dynamics and discover the underlying symmetry. The goal of adaptive symmetry discovery for dynamical system identification is to recover the dynamics f from short trajectories, using only the assumption that f∈ℱΦf _ is equivariant with respect to some unknown group G∈G . In the ideal case, the best sample complexity one could hope to achieve is TΦ()≔maxG∈TΦ(G),T_ (G) _G T_ (G), corresponding to the worst-case identifiability threshold over the class G. A further challenge arises from computational considerations. Finite groups of interest are often prohibitively large. For example, the permutation group on n elements has cardinality n!≈exp(nlogn)n!≈ (n n), as do many of its subgroups. Consequently, algorithms whose runtime scales linearly with the group size are infeasible, and one must instead aim for procedures with runtime at most polylogarithmic in the group size. Accordingly, our aim is to address the following question: Given a class of groups G and an unknown dynamical system f:ℂd→ℂdf:C^d ^d with f∈ℱΦf _ that is G-equivariant for an unknown G∈G , can one identify the dynamics from trajectories of length TΦ()T_ (G) with efficient computational runtime? We answer this question affirmatively in the next section. 4 Main Results We first characterize the trajectory length required for equivariant system identification when the symmetry group G is known, and then turn to adaptive symmetry discovery. 4.1 Sample complexity of equivariant identification We study TΦ(G)T_ (G), the minimal trajectory length required to generically identify a G-equivariant system in ℱΦGF_ ^G, when G and Φ are known. We briefly recall the required notation; see Appendix A. Irreducible representations. Let G G denote the set of equivalence classes of irreducible representations of G. After a change of basis, the state and feature spaces decompose as ℂd≅⨁π∈G^ℂnπ⊗Vπ,ℂm≅⨁π∈G^ℂmπ⊗Vπ,C^d _π∈ GC^n_π V_π, ^m _π∈ GC^m_π V_π, where dπ=dimVπd_π= V_π, and nπ,mπ∈ℕn_π,m_π denote the multiplicities of π in the state and feature representations. Thus d=∑πnπdπd= _πn_πd_π and m=∑πmπdπm= _πm_πd_π. Under this decomposition, every G-equivariant matrix W:ℂm→ℂdW:C^m ^d decomposes as W=⨁π∈G^Cπ⊗IVπ,Cπ∈ℂnπ×mπ.W= _π∈ GC_π I_V_π, C_π ^n_π× m_π. Hence identifying W reduces to identifying CπC_π for all π with nπ>0n_π>0. Generic excitation rank. The required trajectory length also depends on how Φ excites the different isotypic components. The π-isotypic component of Φ(x) (x) belongs to ℂmπ⊗VπC^m_π V_π. Fixing bases vii=1mπ\v_i\_i=1^m_π and ujj=1dπ\u_j\_j=1^d_π, we write it as ∑i=1mπ∑j=1dπ[Φπ(x)]ijvi⊗uj, _i=1^m_π _j=1^d_π[ _π(x)]_ij\,v_i u_j, thereby identifying it with Φπ(x)∈ℂmπ×dπ _π(x) ^m_π× d_π. Thus, the rows index the mπm_π copies of π, while the columns correspond to coordinates in VπV_π. For a trajectory x0,…,xTx_0,…,x_T, define π,T≔[Φπ(x0),…,Φπ(xT−1)]∈ℂmπ×Tdπ, _π,T [ _π(x_0),…, _π(x_T-1)] ^m_π× Td_π, and let hπ,Φ(T)≔rankgen(π,T)h_π, (T) _gen( _π,T), where the generic rank is taken over the initial state and the equivariant parameter matrix W. Theorem 4.1 (Equivariant system identification). Fix a finite group G and an analytic feature map Φ:ℂd→ℂm :C^d ^m with linearly independent coordinates. Then W∈ℱΦGW _ ^G is generically identifiable from x0,…,xTx_0,…,x_T if and only if hπ,Φ(T)=mπh_π, (T)=m_π for every π with nπ>0n_π>0. Consequently, TΦ(G)=maxπ:nπ>0mπ>0infT∈ℕ:hπ,Φ(T)=mπ,T_ (G)= _ subarraycπ:n_π>0\\ m_π>0 subarray \T :h_π, (T)=m_π\, with the infimum interpreted as +∞+∞ if full rank is never attained. Irreducible components with mπ=0m_π=0 contain no unknown parameters and therefore impose no identification requirement. Indeed, in each π-block the observed transitions have the form CπΦπ(xt)C_π _π(x_t). Stacking the observations therefore gives a linear system with design matrix π,T _π,T, so CπC_π is uniquely determined exactly when π,T _π,T has full row rank mπm_π. Since rank(π,T)≤minmπ,Tdπrank( _π,T)≤ \m_π,Td_π\, we obtain the universal lower bound TΦ(G)≥Trep(G)≔maxπ:nπ>0⌈mπdπ⌉.T_ (G)≥ T_rep(G) _π:n_π>0 m_πd_π . This is the smallest trajectory length allowed by dimension counting; whether it is attained depends on the excitation profile hπ,Φ(T)h_π, (T). For the trivial group, there is a single one-dimensional irrep with multiplicity m. Under our assumptions on Φ , hπ,Φ(T)=minm,Th_π, (T)= \m,T\ generically, and hence we have TΦ(e)=mT_ (\e\)=m. Linear and affine systems. For linear systems, Φ(x)=x (x)=x, so mπ=nπm_π=n_π. For every finite group, hπ,Φ(T)=minnπ,Tdπ,Tlin(G)=maxπ:nπ>0⌈nπdπ⌉.h_π, (T)= \n_π,Td_π\, T_lin(G)= _π:n_π>0 n_πd_π . Thus the representation-theoretic lower bound is always tight. The affine case follows similarly after adjoining the constant feature, which adds one copy of the trivial representation to the feature space. Finite Abelian groups. Suppose G is finite Abelian and Φ is analytic, has linearly independent coordinates, and contains the state coordinates, i.e., there is L∈ℂd×mL ^d× m such that LΦ(x)=xL (x)=x. Since every irreducible complex representation of G is one-dimensional, dπ=1d_π=1 for all π∈G^π∈ G. In this case, hπ,Φ(T)=minmπ,Th_π, (T)= \m_π,T\ and TΦ(G)=maxπ:nπ>0mπ=Trep(G).T_ (G)= _π:n_π>0m_π=T_rep(G). In particular, this result holds for the full polynomial feature maps Φ≤k _≤ k. Permutation-equivariant polynomial systems. Let G be a subgroup of the symmetric group SdS_d, acting by coordinate permutations, and let Φ=Φ≤k = _≤ k contain all monomials of total degree at most k, with k≥2k≥ 2. Then, we show TΦ≤k(G)≤maxπ:nπ>0mπ.T_ _≤ k(G)≤ _π:n_π>0m_π. Thus the trajectory length is controlled by the largest active representation multiplicity rather than by the ambient feature dimension m=∑πmπdπm= _πm_πd_π. Example 4.2 (Quadratic systems with permutation symmetry). Consider Φ=Φ≤2 = _≤ 2 under the standard SdS_d-action, where d≥4d≥ 4. Let ViV_i denote the space of homogeneous polynomials of degree i. Then ≤2=V0⊕V1⊕V2P_≤ 2=V_0 V_1 V_2, with V0=π0V_0= _0, V1=π0⊕πstdV_1= _0 _std, and V2=2π0⊕2πstd⊕π(d−2,2)V_2=2 _0 2 _std _(d-2,2). Here π0 _0 is the trivial representation, dπstd=d−1d_ _std=d-1, and dπ(d−2,2)=d(d−3)/2d_ _(d-2,2)=d(d-3)/2. Hence mπ0=4m_ _0=4, mπstd=3m_ _std=3, and mπ(d−2,2)=1m_ _(d-2,2)=1. The state representation is ℂd≅π0⊕πstdC^d _0 _std, so only the trivial and standard blocks are relevant. Their excitation ranks satisfy hπ0,Φ(T)=min4,Th_ _0, (T)= \4,T\ and hπstd,Φ(T)=min3,2Th_ _std, (T)= \3,2T\, yielding TΦ≤2(Sd)=4.T_ _≤ 2(S_d)=4. By contrast, m=(d+22)=Θ(d2)m= d+22= (d^2). Thus permutation equivariance reduces the generic trajectory length from Θ(d2) (d^2) to a constant independent of d. Representation stability. The preceding phenomenon extends to any fixed polynomial degree. Under the standard permutation action of SdS_d, the state representation decomposes as ℂd≅π0⊕πstd,C^d _0 _std, so only the trivial and standard irreducible representations are relevant for identification, even though other irreducible representations may appear in the feature space. For fixed k, the multiplicities of these two representations in Φ≤k _≤ k stabilize stabilize once d≥k+1d≥ k+1. In particular, for d sufficiently large, mπ0=∑r=0kp(r),mπstd=∑j=0k−1(k−j)p(j),m_ _0= _r=0^kp(r), m_ _std= _j=0^k-1(k-j)p(j), where p(r)p(r) denotes the integer partition function. Defining Mk≔maxmπ0,mπstd,M_k \m_ _0,m_ _std\, the preceding polynomial identification bound gives TΦ≤k(Sd)≤MkT_ _≤ k(S_d)≤ M_k. Hence, for every fixed k≥2k≥ 2, TΦ≤k(Sd)=Ok(1),dim(Φ≤k)=(d+k)=Θk(dk).T_ _≤ k(S_d)=O_k(1), ( _≤ k)= d+kk= _k(d^k). Thus, fixed-degree permutation-equivariant polynomial systems are generically identifiable from trajectories whose length remains bounded independently of the state dimension d. 4.2 Adaptive symmetry discovery We now consider system identification when the underlying symmetry is unknown. Let Γ be a finite ambient group of transformations, and let G be a finite family of candidate subgroups of Γ . We assume that Γ acts on the state and feature spaces through compatible representations ρ and ρΦ _ , with the actions of each candidate group obtained by restriction. We further assume that the full symmetry group of the unknown dynamics within Γ belongs to G. We first recall the notion of a generating set, which provides a compact description of a potentially large finite group. Definition 4.3 (Generating set). A subset S⊆GS G is called a generating set of a finite group G if every element of G can be obtained through finitely many compositions of elements of S and their inverses. Equivalently, every g∈Gg∈ G can be written as g=s1ϵ1⋯srϵrg=s_1 _1·s s_r _r, where si∈Ss_i∈ S and ϵi∈−1,1 _i∈\-1,1\. In this case, we write G=⟨S⟩G= S . Generating sets are closely connected to Cayley graphs. Given S⊆GS G, the Cayley graph Cay(G,S)Cay(G,S) has vertex set G, with edges corresponding to composition by elements of S and their inverses. This graph is connected if and only if S generates G. The classical Alon–Roichman theorem (Alon and Roichman, 1994) establishes the substantially stronger fact that O(log|G|)O( |G|) uniformly sampled group elements produce an expanding random Cayley graph with high probability. In particular, they form a generating set with high probability. For our purposes, expansion itself is not required, and a simpler argument already yields the logarithmic generation bound. As long as the sampled elements generate a proper subgroup, a new uniform sample lies outside this subgroup with probability at least 1/21/2. Whenever this occurs, the size of the generated subgroup at least doubles. Let |G|max≔maxH∈|H||G|_ _H |H| and define N,δ≔⌈8(⌈log2|G|max⌉+log||δ)⌉.N_G,δ 8 ( _2|G|_ + |G|δ ) . Then N,δN_G,δ i.i.d. uniform samples from each candidate group generate all groups in G simultaneously with probability at least 1−δ1-δ. We provide the elementary argument in the appendix. Separating candidate symmetries. Known-symmetry identifiability alone does not necessarily imply that different candidate symmetry classes can be distinguished from the same short trajectory. We therefore isolate the condition required for adaptive discovery. Definition 4.4 (Generic candidate separation). Let TΦ()≔maxG∈TΦ(G).T_ (G) _G T_ (G). We call G generically separating if, for every G∈G , a generic G-equivariant system whose full symmetry group within Γ is G, together with a generic initial state, has the following property: for every T≥TΦ()T≥ T_ (G), if a candidate H∈H admits an H-equivariant system consistent with the observed trajectory, then H is a subgroup of G. Thus, generic separation rules out spurious candidate groups that are incomparable with, or strictly larger than, the true group. It does not rule out subgroups of the true group, since a G-equivariant system is automatically equivariant with respect to every subgroup of G. The condition is automatic when the candidate groups are totally ordered by inclusion. Indeed, every candidate subgroup of the true group is feasible. Conversely, if a candidate group strictly contains the true group, then every system equivariant to that candidate is also equivariant to the true group. Once T≥TΦ(G)T≥ T_ (G), uniqueness within the G-equivariant class forces such a system to coincide with the true dynamics, contradicting the assumption that G is its full symmetry group. We are now ready to state the adaptive identification procedure. Algorithm 1 Adaptive symmetry discovery 1: Input: trajectory (x0,…,xT)(x_0,…,x_T), feature map Φ , candidate family G, failure probability δ 2: Output: parameter matrix W and generators S of the discovered symmetry group 3: Form X←[Φ(x0),…,Φ(xT−1)]X←[ (x_0),…, (x_T-1)] and Y←[x1,…,xT]Y←[x_1,…,x_T] 4: Set N←N,δN← N_G,δ and ←∅C← 5: for each G∈G do 6: Sample SG=g1,…,gNS_G=\g_1,…,g_N\, where gi∼i.i.d.Unif(G)g_i i.i.d. Unif(G) 7: Test feasibility of WX=Y,ρ(g)W=WρΦ(g)for all g∈SGWX=Y, ρ(g)W=W _ (g) all g∈ S_G 8: if feasible then 9: Store (G,SG,WG)(G,S_G,W_G) in C, where WGW_G is any feasible solution 10: end if 11: end for 12: Choose a candidate G of maximum cardinality in C 13: return WG,SGW_G,S_G Theorem 4.5 (Adaptive symmetry discovery). Let G be a generically separating family of finite candidate groups, and suppose that the full symmetry group G of an unknown system f(x)=WΦ(x)f(x)=W (x) belongs to G. Suppose the trajectory is generated from a generic initial state by a generic G-equivariant system. Then, provided that T≥TΦ()=maxH∈TΦ(H),T≥ T_ (G)= _H T_ (H), Algorithm 1 recovers the unknown dynamics and a generating set of its full symmetry group with probability at least 1−δ1-δ. Assuming uniform sampling and representation evaluation can be performed efficiently for each candidate group, the runtime is polynomial in d,m,T,||,log|G|maxd,m,T,|G|, |G|_ , and log(1/δ) (1/δ). The theorem shows that, under generic candidate separation, discovering the symmetry requires no additional trajectory observations beyond those needed when the group is known. The additional cost is computational: the algorithm solves linearly constrained feasibility problems using only logarithmically many sampled elements per candidate group. From the Cayley-graph viewpoint, these samples define a sparse random Cayley graph of each candidate. The Alon–Roichman theorem guarantees the stronger property of expansion using O(log|G|)O( |G|) samples, while our identification procedure only requires connectivity, or equivalently generation. Remark 4.6 (Why the largest feasible group is selected). Suppose G is the full symmetry group of the unknown dynamics. With probability at least 1−δ1-δ, the sampled set SGS_G generates G, so imposing equivariance with respect to SGS_G is equivalent to imposing equivariance with respect to all of G. Since T≥TΦ(G)T≥ T_ (G), the corresponding feasible system is uniquely the true one. Every candidate subgroup of G is also feasible. Generic separation rules out all other candidates. Hence G is the unique feasible candidate of maximum cardinality. Remark 4.7 (Randomization and random Cayley graphs). The randomness in Algorithm 1 is used only to obtain compact generating sets for the candidate groups. The sampled elements may equivalently be viewed as defining random Cayley graphs. By the Alon–Roichman theorem, O(log|G|)O( |G|) random elements suffice with high probability to obtain an expanding Cayley graph, and hence a generating set. Our analysis requires only the weaker connectivity property and therefore uses the elementary subgroup-growth argument above. If a generating set is supplied for every candidate group in advance, this randomization is unnecessary. Remark 4.8 (Nested candidate families). If the candidate groups are totally ordered by inclusion, generic candidate separation is automatic. Thus adaptive discovery over a nested family achieves the same trajectory length TΦ()T_ (G) as identification with the group known in advance. Remark 4.9 (Optimal trajectory length). Under generic candidate separation, Algorithm 1 achieves the known-symmetry trajectory length. In particular, no additional trajectory observations are required for discovering the unknown group. The additional randomness and computation are used only to determine which symmetry constraints are compatible with the observed dynamics. Remark 4.10 (General candidate families). For arbitrary incomparable candidate groups, TΦ()T_ (G) need not be sufficient for symmetry discovery, even though it suffices once the correct group is known. In this case, one may instead consider the smallest trajectory horizon at which generic candidate separation holds. The same algorithm and argument then apply at this larger horizon. Discovery among bounded-index subgroups. We next consider a complementary setting in which the possible symmetries are large subgroups of a single known ambient group. Let Γ be a finite group and define ℋB:=H≤Γ:[Γ:H]≤B.H_B:=\H≤ :[ :H]≤ B\. We assume that the full symmetry group H of the unknown dynamics belongs to ℋBH_B, but we do not require an enumeration of ℋBH_B. The key observation is that a uniformly sampled element of Γ belongs to H with probability ℙg∼Unif(Γ)(g∈H)=|H||Γ|=1[Γ:H]≥1B.P_g ( )(g∈ H)= |H|| |= 1[ :H]≥ 1B. Hence, if membership in the unknown symmetry group can be determined from the observed trajectory, sampling from Γ provides uniform samples from H without explicitly searching over the candidate subgroups. To formalize this, we assume generic elementwise separation: for a generic system with full symmetry group H, a generic initial state, and the trajectory length under consideration, a sampled g∈Γg∈ satisfies g∈Hg∈ H if and only if there exists W~ W such that W~X=Y,ρ(g)W~=W~ρΦ(g). WX=Y, ρ(g) W= W _ (g). The reverse implication is automatic for g∈Hg∈ H, since the true parameter matrix W satisfies both constraints. Therefore, we may sample g∼Unif(Γ)g ( ), retain it whenever the above feasibility test succeeds, and repeat. Conditioned on acceptance, the retained elements are i.i.d. uniform samples from H. Since the acceptance probability is at least 1/B1/B, obtaining N accepted elements requires at most BNBN ambient samples in expectation. This again admits a Cayley-graph interpretation. The accepted elements define a random Cayley graph of the unknown group H. Thus O(log|H|)O( |H|) accepted elements suffice to generate H with high probability, while the Alon–Roichman theorem gives the stronger expansion guarantee. Define NΓ,δ:=⌈8(⌈log2|Γ|⌉+log1δ)⌉.N_ ,δ:= 8 ( _2| | + 1δ ) . Algorithm 2 Discovery of a bounded-index symmetry group 1: Input: trajectory (x0,…,xT)(x_0,…,x_T), feature map Φ , ambient group Γ , index bound B, failure probability δ 2: Output: parameter matrix W and generators S of the discovered subgroup 3: Form X←[Φ(x0),…,Φ(xT−1)]X←[ (x_0),…, (x_T-1)] and Y←[x1,…,xT]Y←[x_1,…,x_T] 4: Set N←NΓ,δN← N_ ,δ and S←∅S← 5: while |S|<N|S|<N do 6: Sample g∼Unif(Γ)g ( ) 7: Test feasibility of W~X=Y,ρ(g)W~=W~ρΦ(g) WX=Y, ρ(g) W= W _ (g) 8: if feasible then 9: Add g to S 10: end if 11: end while 12: Solve WX=Y,ρ(g)W=WρΦ(g)for all g∈SWX=Y, ρ(g)W=W _ (g) all g∈ S 13: return W,SW,S Theorem 4.11 (Bounded-index subgroup discovery). Suppose the full symmetry group H of the unknown dynamics satisfies [Γ:H]≤B[ :H]≤ B, and suppose generic elementwise separation holds for T≥TΦ(ℋB):=maxH≤Γ[Γ:H]≤BTΦ(H).T≥ T_ (H_B):= _ subarraycH≤ \\ [ :H]≤ B subarrayT_ (H). Then Algorithm 2 recovers the unknown dynamics and a generating set of H with probability at least 1−δ1-δ. The algorithm does not enumerate the subgroups in ℋBH_B. The expected number of ambient samples and feasibility tests is O(B(log|Γ|+log1δ)),O (B ( | |+ 1δ ) ), and is therefore independent of |ℋB||H_B|. Assuming efficient sampling from Γ , representation evaluation, and linear feasibility testing, the expected runtime is polynomial in d,m,T,B,log|Γ|d,m,T,B, | |, and log(1/δ) (1/δ). In particular, when B=O(1)B=O(1), the sampling overhead is logarithmic in |Γ|| |. Remark 4.12 (Role of the index bound). The index bound controls the rejection-sampling overhead. Since [Γ:H]≤B[ :H]≤ B, each uniform ambient sample belongs to the unknown group with probability at least 1/B1/B. Thus bounded index allows the group to be discovered directly from ambient samples without constructing a separate sampler or enumerating candidate subgroups. Remark 4.13 (Computational efficiency). Each sampled element requires only a linear feasibility test in the entries of W~ W, consisting of the trajectory constraint W~X=Y WX=Y and one intertwining constraint ρ(g)W~=W~ρΦ(g)ρ(g) W= W _ (g). Hence the number of such tests depends on B and log|Γ| | |, but not on the potentially very large number of bounded-index subgroups. Therefore, the main message of this section can be summarized as follows: When the candidate symmetries are generically distinguishable, equivariant dynamics can be identified without knowing the symmetry in advance and with the same trajectory length as in the known-symmetry setting. Moreover, when the unknown symmetry is a bounded-index subgroup of a known ambient group, there is no need to enumerate the candidate subgroups: one can instead sample directly from the ambient group, test individual elements for symmetry, and recover the unknown subgroup from the accepted samples. The resulting sampling overhead is at most a factor B, and is constant when B=O(1)B=O(1). 5 Conclusion and Future Work In this paper, we study how to integrate adaptive symmetry discovery with the problem of dynamical system identification. Focusing on single-trajectory data, we address the question of how to identify a system that is symmetric with respect to an unknown finite group. Our main contribution is a method based on the theory of Cayley graph expanders and generating sets of finite groups, which enables adaptation to unknown symmetries with near-zero overhead. Moreover, the proposed approach achieves the same trajectory length (i.e., sample complexity) as in the setting where the symmetries are known, thereby yielding optimal adaptation. An important direction for future work is to extend our results to infinite (Lie) groups, which would likely require theoretical tools beyond the expander-based framework developed for finite groups. Another promising direction is to study noisy dynamical systems and to identify system parameters while simultaneously adapting to symmetries in such settings. Establishing provable sample complexity guarantees in the presence of noise remains open, to the best of our knowledge. More broadly, it would be interesting to investigate whether similar adaptive symmetry techniques can be developed for learning linear time-invariant systems and for control systems with hidden states and noisy observations in modern settings (Hazan et al., 2025). We leave these directions for future work. Acknowledgements BT and MW were partially supported by NSF Award CBET-2112085 and DMS-2406905. MW acknowledges partial funding from an Alfred P. Sloan Fellowship in Mathematics and the AI2050 program at Schmidt Sciences (Grant G-25-69786). This material is based on research sponsored by the Air Force Office of Scientific Research under agreement number FA9550261B044. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The opinions, findings, views, conclusions or recommendations contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the DAF, AFRL or the U.S. Government. References N. Alon and Y. Roichman (1994) Random cayley graphs and expanders. Random Structures & Algorithms 5 (2), p. 271–284. Cited by: §A.2, §4.2. M. Atzmon, K. Nagano, S. Fidler, S. Khamis, and Y. Lipman (2022) Frame averaging for equivariant shape space learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Cited by: §2. M. Bhat, J. Park, J. Yang, N. Dehmamy, R. Walters, and R. Yu (2025) AtlasD: automatic local symmetry discovery. In Int. Conference on Machine Learning (ICML), Cited by: §2. M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković (2021) Geometric deep learning: grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478. Cited by: §1. S. L. Brunton, J. L. Proctor, and J. N. Kutz (2016) Discovering governing equations from data by sparse identification of nonlinear dynamical systems. Proceedings of the national academy of sciences 113 (15), p. 3932–3937. Cited by: §1, §2. P. Calvo-Barlés, S. G. Rodrigo, and L. Martín-Moreno (2025a) Learning finite symmetry groups of dynamical systems via equivariance detection. arXiv preprint arXiv:2503.03014. Cited by: §2. P. Calvo-Barlés, S. G. Rodrigo, and L. Martín-Moreno (2025b) Machine learning for detection of equivariant finite symmetry groups in dynamical systems. Machine Learning: Science and Technology 6 (2), p. 025058. Cited by: §2. J. Carruth, M. F. Eggl, C. Fefferman, C. W. Rowley, and M. Weber (2022) Controlling unknown linear dynamics with bounded multiplicative regret. Revista Matematica Iberoamericana 38 (7), p. 2185–2216. Cited by: §2. J. Carruth, M. F. Eggl, C. Fefferman, and C. W. Rowley (2024) Almost optimal agnostic control of unknown linear dynamics. arXiv preprint arXiv:2403.06320. Cited by: §2. N. Dehmamy, R. Walters, Y. Liu, D. Wang, and R. Yu (2021) Automatic symmetry discovery with lie algebra convolutional network. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. K. Desai, B. Nachman, and J. Thaler (2022) Symmetry discovery with deep learning. Physical Review D 105 (9), p. 096031. Cited by: §2. C. L. Fefferman, B. Guillen Pegueroles, C. W. Rowley, and M. Weber (2022) Optimal control with learning on the fly: a toy problem. Revista Matematica Iberoamericana 38 (1), p. 175–187. Cited by: §2. D. Foster, T. Sarkar, and A. Rakhlin (2020) Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, Cited by: §2. W. Fulton and J. Harris (2013) Representation theory: a first course. Vol. 129, Springer Science & Business Media. Cited by: Appendix A. A. Gabel, R. Quax, and E. Gavves (2024) Data-driven lie point symmetry detection for continuous dynamical systems. Machine Learning: Science and Technology 5 (1), p. 015037. Cited by: §2. E. Hazan, S. S. Shwartz, and N. Srebro (2025) Research program: theory of learning in dynamical systems. arXiv preprint arXiv:2512.19410. Cited by: §5. L. Hu, Y. Li, and Z. Lin (2025a) Explicit discovery of nonlinear symmetries from dynamic data. In Int. Conference on Machine Learning (ICML), Cited by: §2. L. Hu, Y. Li, and Z. Lin (2025b) Governing equation discovery from data based on differential invariants. arXiv preprint arXiv:2505.18798. Cited by: §2. L. Hu, Y. Li, and Z. Lin (2025c) Symmetry discovery for different data types. Neural Networks, p. 107481. Cited by: §2. D. Huh (2025) Discovering group structures via unitary representation learning. In Int. Conference on Learning Representations (ICLR), Cited by: §2. R. Isermann and M. Münchhof (2011) Identification of dynamic systems: an introduction with applications. Vol. 85, Springer. Cited by: §1, §2. S. Kaba, A. K. Mondal, Y. Zhang, Y. Bengio, and S. Ravanbakhsh (2023) Equivariance with learned canonicalization functions. In Int. Conference on Machine Learning (ICML), Cited by: §2. P. Karjol, V. V. Kashyap, R. Kashyap, et al. (2025) Learning equivariant functions via quadratic forms. arXiv preprint arXiv:2509.22184. Cited by: §2. G. Ko, H. Kim, and J. Lee (2024) Learning infinitesimal generators of continuous symmetries from data. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. M. Kreider, J. Harlim, and D. Huang (2025) A model-free method for discovering symmetry in differential equations. arXiv preprint arXiv:2511.09779. Cited by: §2. H. Li, C. Xiao, M. Guo, and Y. Weng (2025) Latent mixture of symmetries for sample-efficient dynamic learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. Y. Lin, J. Helwig, S. Gui, and S. Ji (2024) Equivariance via minimal frame averaging for more symmetries and efficiency. In Int. Conference on Machine Learning (ICML), Cited by: §2. S. E. Otto, N. Zolman, J. N. Kutz, and S. L. Brunton (2025) A unified framework to enforce, discover, and promote symmetry in machine learning. Journal of Machine Learning Research 26 (248), p. 1–83. Cited by: §2. J. Y. Park, Y. Chen, F. Eijkelboom, J. van de Meent, L. L. Wong, and R. Walters (2025) Discovering lie groups with flow matching. arXiv preprint arXiv:2512.20043. Cited by: §2. A. Perin and S. Deny (2025) On the ability of deep networks to learn symmetries from data: a neural kernel theory. Journal of Machine Learning Research 26 (145), p. 1–70. Cited by: §2. O. Puny, M. Atzmon, E. J. Smith, I. Misra, A. Grover, H. Ben-Hamu, and Y. Lipman (2022) Frame averaging for invariant and equivariant network design. In Int. Conference on Learning Representations (ICLR), Cited by: §2. D. W. Romero and S. Lohit (2022) Learning partial equivariances from data. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. E. Santos-Escriche and S. Jegelka (2025) Learning equivariant models by discovering symmetries with learnable augmentations. arXiv preprint arXiv:2506.03914. Cited by: §2. T. Sarkar, A. Rakhlin, and M. A. Dahleh (2021) Finite time LTI system identification. Journal of Machine Learning Research 22 (26), p. 1–61. Cited by: §2. T. Sarkar and A. Rakhlin (2019) Near optimal finite time identification of arbitrary linear dynamical systems. In Int. Conference on Machine Learning (ICML), Cited by: §2. J. Serre et al. (1977) Linear representations of finite groups. Vol. 42, Springer. Cited by: Appendix A. B. Shaw, S. Kunapuli, A. Magner, and K. R. Moon (2025) Continuous symmetry discovery and enforcement using infinitesimal generators of multi-parameter group actions. arXiv preprint arXiv:2505.08219. Cited by: §2. B. Shaw, A. Magner, and K. Moon (2024) Symmetry discovery beyond affine transformations. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. Z. Shumaylov, P. Zaika, J. Rowbottom, F. Sherry, M. Weber, and C. Schönlieb (2025) Lie algebra canonicalization: equivariant neural operators under arbitrary lie groups. In Int. Conference on Learning Representations (ICLR), Cited by: §2. M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht (2018) Learning without mixing: towards a sharp analysis of linear system identification. In Conference on Learning Theory (COLT), Cited by: §2. S. Sivaranjani, Y. Shi, N. Atanasov, T. Duong, J. Feng, T. Martin, Y. Xu, V. Gupta, and F. Allgöwer (2025) Control-oriented system identification: classical, learning, and physics-informed approaches. arXiv preprint arXiv:2512.06315. Cited by: §2. A. Soleymani, B. Tahmasebi, P. Jaillet, and S. Jegelka (2025a) From finite to infinite groups: a polynomial-time algorithm for learning with exact invariances. In NeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations, Cited by: §2. A. Soleymani, B. Tahmasebi, S. Jegelka, and P. Jaillet (2025b) A robust kernel statistical test of invariance: detecting subtle asymmetries. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: §2. A. Soleymani, B. Tahmasebi, S. Jegelka, and P. Jaillet (2025c) Learning with exact invariances in polynomial time. In Int. Conference on Machine Learning (ICML), Cited by: §2. B. Tahmasebi and S. Jegelka (2023) The exact sample complexity gain from invariances for kernel regression. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. B. Tahmasebi and S. Jegelka (2024) Sample complexity bounds for estimating probability divergences under invariances. In Int. Conference on Machine Learning (ICML), Cited by: §2. B. Tahmasebi and S. Jegelka (2025a) Generalization bounds for canonicalization: a comparative study with group averaging. In Int. Conference on Learning Representations (ICLR), Cited by: §2. B. Tahmasebi and S. Jegelka (2025b) Regularity in canonicalized models: a theoretical perspective. In Int. Conference on Artificial Intelligence and Statistics (AISTATS), Cited by: §2. B. Tahmasebi, M. Weber, and S. Jegelka (2025) Data augmentation: a Fourier analysis perspective. In NeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations, Cited by: §2. B. Tahmasebi and M. Weber (2025) Achieving approximate symmetry is exponentially easier than exact symmetry. arXiv preprint arXiv:2512.11855. Cited by: §2. S. Tu, R. Frostig, and M. Soltanolkotabi (2024) Learning from many trajectories. Journal of Machine Learning Research 25 (216), p. 1–109. Cited by: §2. T. van der Ouderaa, A. Immer, and M. van der Wilk (2023) Learning layer-wise equivariances automatically using gradients. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. P. Van Overschee and B. De Moor (2012) Subspace identification for linear systems: theory—implementation—applications. Springer Science & Business Media. Cited by: §1, §2. R. Wang and R. Yu (2025) Physics-guided deep learning for dynamical systems: a survey. ACM Computing Surveys 58 (5), p. 1–31. Cited by: §1, §2. M. Weber (2025) Geometric machine learning. Wiley Online Library. Cited by: §1. J. Yang, M. Bhat, B. Hu, Y. Cao, N. Dehmamy, R. Walters, and R. Yu (2025) Discovering symbolic differential equations with symmetry invariants. arXiv preprint arXiv:2505.12083. Cited by: §2. J. Yang, N. Dehmamy, R. Walters, and R. Yu (2024a) Latent space symmetry discovery. In Int. Conference on Machine Learning (ICML), Cited by: §2. J. Yang, W. Rao, N. Dehmamy, R. Walters, and R. Yu (2024b) Symmetry-informed governing equation discovery. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. J. Yang, R. Walters, N. Dehmamy, and R. Yu (2023) Generative adversarial symmetry discovery. In Int. Conference on Machine Learning (ICML), Cited by: §2. R. Yu and R. Wang (2024) Learning dynamical systems from data: an introduction to physics-guided deep learning. Proceedings of the National Academy of Sciences 121 (27), p. e2311808121. Cited by: §1, §2. I. M. Ziemann, H. Sandberg, and N. Matni (2022) Single trajectory nonparametric learning of nonlinear dynamics. In Conference on Learning Theory (COLT), Cited by: §2. Appendix A Preliminaries In this section, we summarize the basic definitions and background material required to understand the results of the paper. Standard references for finite group theory and representation theory include (Serre and others, 1977; Fulton and Harris, 2013). A.1 Groups, representations, and equivariance Groups. A (finite) group G is a finite set equipped with a binary operation ⋅:G×G→G·:G× G→ G satisfying the following properties: • Associativity: (g⋅h)⋅s=g⋅(h⋅s)(g· h)· s=g·(h· s) for all g,h,s∈Gg,h,s∈ G. • Identity: There exists an element e∈Ge∈ G such that e⋅g=g⋅e=ge· g=g· e=g for all g∈Gg∈ G. • Inverses: For every g∈Gg∈ G, there exists g−1∈Gg^-1∈ G such that g⋅g−1=g−1⋅g=eg· g^-1=g^-1· g=e. The cardinality of a finite group G is denoted by |G||G|. For convenience, we drop the dot notation and write ghgh instead of g⋅hg· h for all g,h∈Gg,h∈ G. Examples of finite groups. Here is a few examples of finite groups: • The cyclic group of integers modulo n under addition, denoted by ℤ/nℤZ/nZ. • The permutation group (also known as symmetric group) of group of all permutations of n elements. • Direct products of commutative groups, such as group of sign inversions ±1d\± 1\^d • Dihedral group, consisting of symmetries of a regular polygon with n sides in dimension two (reflections, rotations). Group actions and linear representations. Let V be a vector space over ℂC. A (left) action of a finite group G on V is a map θ:G×V→Vθ:G× V→ V satisfying θ(e,v)=v,θ(gh,v)=θ(g,θ(h,v))for all g,h∈G,v∈V.θ(e,v)=v, θ(gh,v)=θ(g,θ(h,v)) all g,h∈ G,\ v∈ V. When θ(g,⋅)θ(g,·) is linear and invertible for every g∈Gg∈ G, the action is equivalently described by a group homomorphism ρ:G→GL(V),ρ:G (V), where ρ(g)v:=θ(g,v)ρ(g)v:=θ(g,v). In this case, (V,ρ)(V,ρ) is called a linear representation of G. Note that here each ρ(g)∈ℂn×nρ(g) ^n× n is an invertible matrix, with n=dim(V)n= (V). Note: While group actions can be defined on general sets or manifolds, throughout this paper we only consider linear actions on finite-dimensional complex vector spaces. Irreducible representations. A representation (V,ρ)(V,ρ) of G is said to be irreducible if it has no nontrivial G-invariant subspaces, i.e., the only subspaces W⊆VW V satisfying ρ(g)W⊆Wρ(g)W W for all g∈Gg∈ G are 0\0\ and V itself. A fundamental result in finite group representation theory is Maschke’s theorem, which states that every finite-dimensional representation of a finite group over ℂC is completely reducible. That is, any representation V admits a decomposition of the form V≅⨁π∈G^ℂnπ⊗Vπ,V\; \; _π∈ GC^n_π V_π, where: • G G denotes the set of inequivalent irreducible representations of G, • VπV_π is a representative irreducible representation of dimension dπ∈ℕd_π , • nπ∈ℤ≥0n_π _≥ 0 is the multiplicity of π in V. The dimensions satisfy ∑π∈G^nπdπ=n. _π∈ Gn_πd_π=n. Moreover, for finite groups, the number of irreducible representations is finite, thus |G^|<∞| G|<∞, and their dimensions obey the following identity ∑π∈G^dπ2=|G|, _π∈ Gd_π^2=|G|, with each dπd_π dividing |G||G|. Unitary representations and change of basis. For finite groups, every finite-dimensional representation over ℂC is equivalent to a unitary representation. In particular, after an appropriate change of basis, we may assume without loss of generality that ρ(g)ρ(g) and ρΦ(g) _ (g) are unitary for all g∈Gg∈ G. This change of basis does not affect equivariance properties or the structure of the state/feature space. Isotypic decomposition and block structure. The decomposition above can be made explicit at the level of matrices. In particular, there exists a change of basis of V under which the representation ρ takes a block-diagonal form ρ(g)=⨁π∈G^(Inπ⊗π(g)),∀g∈G,ρ(g)\;=\; _π∈ G (I_n_π π(g) ), ∀ g∈ G, where each π(g)∈ℂdπ×dπ(g) ^d_π× d_π is an irreducible representation and InπI_n_π denotes the identity matrix of size nπn_π. We use the notation ρ≅⨁π∈G^nππρ\; \; _π∈ Gn_π\,π to denote the decomposition of ρ into irreducible representations, where nπn_π denotes the multiplicity of π. Equivariant linear maps. Let (V,ρV)(V, _V) and (U,ρU)(U, _U) be two representations of G. A linear map ψ:V→Uψ:V→ U is called G-equivariant if ψ∘ρV(g)=ρU(g)∘ψfor all g∈G.ψ _V(g)= _U(g) ψ all g∈ G. The space of equivariant linear maps between V and U is denoted by HomG(V,U)Hom_G(V,U). Using the decomposition into irreducible representations, the structure of HomG(V,U)Hom_G(V,U) can be characterized explicitly in terms of multiplicities. In particular, if V≅⨁π∈G^ℂnπ⊗Vπ,U≅⨁π∈G^ℂmπ⊗Vπ,V _π∈ GC^n_π V_π, U _π∈ GC^m_π V_π, then HomG(V,U)≅⨁π∈G^ℂmπ×nπ,Hom_G(V,U) _π∈ GC^m_π× n_π, and in particular, dim(HomG(V,U))=∑π∈G^mπnπ. (Hom_G(V,U))= _π∈ Gm_πn_π. This characterization will play a central role in our analysis of equivariant linear dynamical systems. In particular, it allows us to count the dimension of the matrices W∈ℝd×mW ^d× m that satisfy the equivariance condition in our proofs. Polynomial feature lifting. Fix a degree parameter k∈ℕk . Let Φ:ℂd→ℂm :C^d ^m denote the polynomial feature map consisting of all monomials in d variables of total degree at most k. Explicitly, for x=(x1,…,xd)⊤∈ℂdx=(x^1,…,x^d) ^d, Φ(x)=((x1)α1(x2)α2⋯(xd)αd)α∈ℐk,ℐk=α∈ℤ≥0d|∑i=1dαi≤k. (x)\;=\; ((x^1) _1(x^2) _2·s(x^d) _d )_α _k, _k= \α _≥ 0^d\; |\; _i=1^d _i≤ k \. The resulting feature dimension is m=(d+kd).m= d+kd. We refer to Φ(x) (x) as the feature representation of the state x. Polynomially lifted linear dynamical systems. A polynomially lifted linear dynamical system of degree at most k is a function f:ℂd→ℂdf:C^d ^d of the form f(x)=WΦ(x),W∈ℂd×m.f(x)=W (x), W ^d× m. We denote by ℱ≤kF_≤ k the class of all such systems. Although f is generally nonlinear in the state x, it is linear in the lifted feature space. Thus, each system in ℱ≤kF_≤ k is fully parameterized by the matrix W. For convenience, along a trajectory xtt≥0\x_t\_t≥ 0, we write ϕt:=Φ(xt)∈ℂm _t:= (x_t) ^m. Lifted group actions on polynomial features. Suppose a finite group G acts linearly on the state space ℂdC^d via a representation ρ:G→GLd(ℂ).ρ:G _d(C). This action induces a natural linear action on the polynomial feature space associated with Φ . In particular, there exists a unique representation ρΦ:G→GLm(ℂ) _ :G _m(C) such that Φ(ρ(g)x)=ρΦ(g)Φ(x),∀g∈G,x∈ℂd. (ρ(g)x)= _ (g)\, (x), ∀ g∈ G,\;x ^d. (5) The representation ρΦ _ corresponds to the action of G on multivariate polynomials of degree at most k induced by the change of variables x↦ρ(g)x ρ(g)x. Equivariant polynomially lifted systems. Let G act on ℂdC^d via ρ. A dynamical system f:ℂd→ℂdf:C^d ^d is said to be G-equivariant if f(ρ(g)x)=ρ(g)f(x),∀g∈G,x∈ℂd.f(ρ(g)x)=ρ(g)f(x), ∀ g∈ G,\;x ^d. For polynomially lifted linear systems f(x)=WΦ(x)∈ℱ≤kf(x)=W (x) _≤ k, this condition is equivalent to the matrix constraint ρ(g)W=WρΦ(g),∀g∈G,ρ(g)W=W _ (g), ∀ g∈ G, (6) which states that W is an intertwining operator between the representations ρΦ _ and ρ. We denote by ℱ≤kG⊆ℱ≤kF_≤ k^G _≤ k the class of all G-equivariant polynomially lifted linear dynamical systems of degree at most k. Equivariance as linear constraints. For fixed representations ρ and ρΦ _ of a finite group G, the equivariance condition ρ(g)W=WρΦ(g),∀g∈G,ρ(g)W=W _ (g), ∀ g∈ G, is a system of linear constraints in the entries of W. Consequently, the space of G-equivariant matrices forms a linear subspace of ℂd×mC^d× m whose dimension can be characterized using representation-theoretic multiplicities given above. This observation is essential for the study of the time complexity of optimization problems considered later in the paper. Genericity and analytic maps. Throughout the paper, a property is said to hold generically if it holds outside a set of Lebesgue measure zero in the natural finite-dimensional parameter space. In the polynomial setting, the exceptional set can typically be taken to be a proper algebraic variety; for analytic models, it is contained in the zero set of a nonzero analytic function. Importantly, genericity is always understood with respect to the underlying parameters, such as the initial state x0x_0 and the parameter matrix W, rather than with respect to the ambient feature space. In particular, when m>dm>d, the feature vector Φ(x) (x) need not be generic as an arbitrary element of ℂmC^m, since the image of Φ may itself lie in a lower-dimensional subset. The main genericity principle used throughout our proofs concerns ranks of analytic matrix-valued functions. Let M(θ)M(θ) be a matrix whose entries depend analytically on a finite-dimensional parameter θ, and let r=maxθrankM(θ).r= _θrankM(θ). Then rankM(θ)=rrankM(θ)=r generically. Indeed, some r×r× r minor is not identically zero, and its zero set has Lebesgue measure zero. We refer to r as the generic rank of M. For the dynamical systems considered in this paper, each trajectory point xtx_t is an analytic function of the initial state and the parameter matrix: starting from xt+1=WΦ(xt)x_t+1=W (x_t), this follows recursively from the analyticity of Φ . Consequently, all feature design matrices constructed from a finite trajectory have entries that depend analytically on (x0,W)(x_0,W). Generic rank statements can therefore be proved by exhibiting a single choice of (x0,W)(x_0,W) for which an appropriate minor is nonzero. This is the genericity argument used repeatedly in the proofs below. A.2 Cayley graphs, expanders, and random generators Let G be a finite group and let S=s1,…,sNS=\s_1,…,s_N\ be a multiset of elements of G. We write S±S^± for the symmetric multiset obtained by adjoining the inverses of the elements of S. The Cayley graph Cay(G,S±)Cay(G,S^±) has vertex set G, with edges corresponding to composition by elements of S and their inverses. Its connected components are precisely the cosets of the subgroup ⟨S⟩ S . In particular, Cay(G,S±) is connected⟺⟨S⟩=G.Cay(G,S^±) is connected S =G. The normalized adjacency operator of this graph is Sf(g)=12N∑i=1N(f(sig)+f(si−1g)),f:G→ℂ.A_Sf(g)= 12N _i=1^N (f(s_ig)+f(s_i^-1g) ), f:G . Since the generating multiset is symmetric, SA_S is self-adjoint on ℓ2(G) _2(G). Representation-theoretic decomposition. The regular representation decomposes as ℓ2(G)≅⨁π∈G^ℂdπ⊗Vπ, _2(G) _π∈ GC^d_π V_π, where dπ=dimVπd_π= V_π. Choosing the irreducible representations to be unitary, the operator SA_S decomposes, up to multiplicity, into the matrices Aπ(S)≔12N∑i=1N(π(si)+π(si)∗).A_π(S) 12N _i=1^N (π(s_i)+π(s_i) ). Thus the nontrivial spectrum of the Cayley graph is controlled by the matrices Aπ(S)A_π(S) for π≠π 1. A spectral gap is a stronger property than what is needed in our algorithms. Indeed, the following immediate observation connects expansion to generation. Lemma A.1 (Spectral certificate for generation). If maxπ≠‖Aπ(S)‖op<1, _π 1\|A_π(S)\|_op<1, then ⟨S⟩=G S =G. Proof. If ⟨S⟩≠G S ≠ G, the Cayley graph has more than one connected component. Hence the eigenvalue 11 of its normalized adjacency operator has multiplicity greater than one. One copy corresponds to the constant functions, while another lies in the orthogonal complement of the constants. Under the irreducible decomposition of the regular representation, this yields a nontrivial π for which Aπ(S)A_π(S) has eigenvalue 11, contradicting the assumed operator-norm bound. ∎ The classical Alon–Roichman theorem (Alon and Roichman, 1994) gives a much stronger probabilistic statement: for any fixed desired spectral gap, O(log|G|)O( |G|) independent uniform samples from G suffice to produce an expanding random Cayley graph, with constants depending only on the desired gap. In particular, logarithmically many random elements generate G with high probability. For our purposes, however, expansion is not needed. The following elementary subgroup-growth argument gives directly the generation guarantee used in Section 4.2. Proposition A.2 (Random generation). Let g1,…,gN∼i.i.d.Unif(G)g_1,…,g_N i.i.d. Unif(G) and S=g1,…,gNS=\g_1,…,g_N\. Let r=⌈log2|G|⌉r= _2|G| . If N≥8(r+log1δ),N≥ 8 (r+ 1δ ), then ℙ(⟨S⟩≠G)≤δ.P ( S ≠ G )≤δ. Proof. Let Hi=⟨g1,…,gi⟩H_i= g_1,…,g_i , with H0=eH_0=\e\. Whenever Hi−1H_i-1 is a proper subgroup of G, Lagrange’s theorem gives |Hi−1|≤|G|/2|H_i-1|≤|G|/2, and therefore ℙ(gi∉Hi−1|g1,…,gi−1)≥12.P (g_i∉ H_i-1\, |\,g_1,…,g_i-1 )≥ 12. Whenever gi∉Hi−1g_i∉ H_i-1, the subgroup strictly grows, and hence |Hi|≥2|Hi−1||H_i|≥ 2|H_i-1|. Consequently, after r such successful enlargements, the generated subgroup must equal G. The number of successful enlargements therefore stochastically dominates a binomial random variable X∼Bin(N,1/2)X (N,1/2) until generation is complete. Hence ℙ(⟨S⟩≠G)≤ℙ(X<r).P( S ≠ G) (X<r). Writing μ=N/2μ=N/2, the assumption on N implies r≤μ/4r≤μ/4. A multiplicative Chernoff bound therefore gives ℙ(X<r)≤ℙ(X≤μ4)≤exp(−9μ32)=exp(−9N64)≤δ.P(X<r) (X≤ μ4 )≤ (- 9μ32 )= (- 9N64 )≤δ. ∎ The preceding proposition immediately yields the simultaneous guarantee used by Algorithm 1. Corollary A.3 (Simultaneous random generation). Let G be a finite family of finite groups and define |G|max≔maxG∈|G|.|G|_ _G |G|. If, independently for every G∈G , we draw N,δN_G,δ i.i.d. uniform samples, where N,δ=⌈8(⌈log2|G|max⌉+log||δ)⌉,N_G,δ= 8 ( _2|G|_ + |G|δ ) , then all sampled sets generate their corresponding groups simultaneously with probability at least 1−δ1-δ. Proof. Apply Proposition A.2 to each candidate group with failure probability δ/||δ/|G|, and take a union bound. ∎ Remark A.4 (Relation to Alon–Roichman). The proof of Proposition A.2 uses only connectivity of the random Cayley graph. The Alon–Roichman theorem gives the considerably stronger conclusion that a logarithmic-size random generating set typically produces a Cayley graph with a nontrivial spectral gap. Thus, the random generators used in our adaptive procedure can be viewed as a weaker consequence of the random-Cayley-graph expansion phenomenon. Rejection sampling for bounded-index subgroups. We finally record the elementary sampling fact used in the bounded-index variant of our algorithm. Lemma A.5 (Sampling a bounded-index subgroup). Let H be a subgroup of a finite group Γ satisfying [Γ:H]≤B[ :H]≤ B. Suppose that we can sample uniformly from Γ and test membership in H. If g∼Unif(Γ)g ( ) is accepted whenever g∈Hg∈ H, then the accepted sample is exactly uniform on H. Moreover, the acceptance probability satisfies ℙ(g∈H)=|H||Γ|=1[Γ:H]≥1B.P(g∈ H)= |H|| |= 1[ :H]≥ 1B. Consequently, obtaining N i.i.d. uniform samples from H requires at most BNBN samples from Γ in expectation. Proof. For every h∈Hh∈ H, ℙ(g=h∣g∈H)=1/|Γ||H|/|Γ|=1|H|,P(g=h g∈ H)= 1/| ||H|/| |= 1|H|, so the conditional distribution is uniform on H. Independent repetitions of the rejection procedure therefore produce i.i.d. uniform samples. The acceptance probability is 1/[Γ:H]1/[ :H], so the expected number of ambient samples per accepted element is [Γ:H]≤B[ :H]≤ B. ∎ Remark A.6 (High-probability sampling complexity). The expected bound in Lemma A.5 can also be upgraded to a high-probability bound using a standard Chernoff argument. In particular, O(B(N+log(1/δ)))O(B(N+ (1/δ))) ambient samples suffice to obtain N accepted samples with probability at least 1−δ1-δ. Thus, when B=O(1)B=O(1), both the expected and high-probability sampling overheads are constant up to the logarithmic failure-probability term. Appendix B Proofs of Main Results We provide the proof of the main theorems in the paper here in this section. B.1 Proof of Theorem 4.1 We first prove the general rank characterization and then establish the special cases used in the main text. Proof of Theorem 4.1. Recall the isotypic decompositions ℂd≅⨁π∈G^ℂnπ⊗Vπ,ℂm≅⨁π∈G^ℂmπ⊗Vπ.C^d _π∈ GC^n_π V_π, ^m _π∈ GC^m_π V_π. By Schur’s lemma, every G-equivariant matrix W:ℂm→ℂdW:C^m ^d has the form W=⨁π∈G^Cπ⊗IVπ,Cπ∈ℂnπ×mπ.W= _π∈ GC_π I_V_π, C_π ^n_π× m_π. For notational convenience, reshape the π-isotypic component of a state x as a matrix Xπ(x)∈ℂnπ×dπX_π(x) ^n_π× d_π. With the analogous reshaping Φπ(x)∈ℂmπ×dπ _π(x) ^m_π× d_π of the feature vector, the transition xt+1=WΦ(xt)x_t+1=W (x_t) gives, for every π, Xπ(xt+1)=CπΦπ(xt).X_π(x_t+1)=C_π _π(x_t). Stacking T transitions yields [Xπ(x1),…,Xπ(xT)]=Cππ,T,[X_π(x_1),…,X_π(x_T)]=C_π _π,T, where π,T=[Φπ(x0),…,Φπ(xT−1)] _π,T=[ _π(x_0),…, _π(x_T-1)]. Thus, for a fixed observed trajectory, CπC_π is uniquely determined if and only if π,T _π,T has full row rank mπm_π. Indeed, if it has full row rank, it admits a right inverse, which uniquely determines CπC_π. Conversely, if its rank is smaller than mπm_π, there exists a nonzero matrix Dπ∈ℂnπ×mπD_π ^n_π× m_π such that Dππ,T=0D_π _π,T=0. Replacing CπC_π by Cπ+DπC_π+D_π then gives a distinct equivariant parameter producing exactly the same observed transitions. It remains only to pass from a fixed trajectory to the generic statement. The entries of π,T _π,T are analytic functions of x0x_0 and the equivariant parameters CπC_π. Hence its maximal attainable rank is achieved outside the common zero set of its maximal nonzero minors, a measure-zero set. Therefore this maximal rank is precisely hπ,Φ(T)h_π, (T). Since the blocks are independent, W is generically identifiable exactly when hπ,Φ(T)=mπfor every π with nπ>0.h_π, (T)=m_π every π with n_π>0. Taking the smallest such T for every active block and then the largest over the active irreducible representations gives TΦ(G)=maxπ:nπ>0infT∈ℕ:hπ,Φ(T)=mπ.T_ (G)= _π:n_π>0 \T :h_π, (T)=m_π\. Finally, rank(π,T)≤minmπ,Tdπrank( _π,T)≤ \m_π,Td_π\, and therefore TΦ(G)≥maxπ:nπ>0⌈mπdπ⌉.T_ (G)≥ _π:n_π>0 m_πd_π . ∎ Remark B.1 (Identification may fail for every finite T). The possibility TΦ(G)=+∞T_ (G)=+∞ in Theorem 4.1 can genuinely occur without further assumptions on Φ . For example, let G=ℤ/2ℤG=Z/2Z act on (u,v)∈ℂ2(u,v) ^2 by (u,v)↦(u,−v)(u,v) (u,-v), and consider Φ(u,v)=(1,v,uv,u2v). (u,v)=(1,v,uv,u^2v). The coordinates of Φ are analytic and linearly independent. Every equivariant system in this class has the form ut+1=a,vt+1=vt(b0+b1ut+b2ut2).u_t+1=a, v_t+1=v_t(b_0+b_1u_t+b_2u_t^2). After the first transition, ut=au_t=a, and hence all subsequent feature vectors in the nontrivial isotypic component are proportional to (1,a,a2)(1,a,a^2). Together with the initial feature vector, their rank is at most two, whereas this component has multiplicity three. Thus its parameter block can never be identified from a single trajectory. The trivial group. We next justify the non-equivariant baseline TΦ(e)=mT_ (\e\)=m. Write Φ=(ϕ1,…,ϕm) =( _1,…, _m). Since the coordinate functions are linearly independent, spanΦ(x):x∈ℂd=ℂm;span\ (x):x ^d\=C^m; otherwise a nonzero linear functional annihilating this span would give a nontrivial linear relation among the ϕi _i. We may therefore choose z0,…,zm−1z_0,…,z_m-1 such that Φ(z0),…,Φ(zm−1) (z_0),…, (z_m-1) are linearly independent. Choose any zm∈ℂdz_m ^d. Since these m feature vectors form a basis of ℂmC^m, there exists W satisfying WΦ(zt)=zt+1W (z_t)=z_t+1 for 0≤t<m0≤ t<m. Hence z0,…,zmz_0,…,z_m is a valid trajectory whose feature design matrix has rank m. The corresponding determinant is therefore a nonzero analytic function of (W,x0)(W,x_0), so it is nonzero generically. Since a trajectory of length T<mT<m provides only T feature vectors, we conclude that TΦ(e)=m.T_ (\e\)=m. Linear systems. Suppose now that Φ(x)=x (x)=x. Then mπ=nπm_π=n_π, and in the π-isotypic component the dynamics become Xπ,t+1=CπXπ,t,Xπ,t∈ℂnπ×dπ.X_π,t+1=C_πX_π,t, X_π,t ^n_π× d_π. Consequently, π,T=[Xπ,0,CπXπ,0,…,CπT−1Xπ,0], _π,T=[X_π,0,C_πX_π,0,…,C_π^T-1X_π,0], which is a block Krylov matrix. We claim that generically rank(π,T)=minnπ,Tdπ.rank( _π,T)= \n_π,Td_π\. It suffices to exhibit one choice attaining this rank. Set n=nπn=n_π and r=dπr=d_π, and choose Cπ=diag(λ1,…,λn)C_π=diag( _1,…, _n), with distinct nonzero λi _i. Partition minn,Tr \n,Tr\ rows into at most r groups, each of size at most T, and for every row in the j-th group choose the corresponding row of Xπ,0X_π,0 to be the j-th standard basis vector of ℂrC^r. After permuting rows and columns, the resulting full-rank minor consists of Vandermonde blocks [1λi⋯λiT−1]. bmatrix1& _i&·s& _i^T-1 bmatrix. Each block has maximal rank because the corresponding λi _i’s are distinct. Hence the total rank is minn,Tr \n,Tr\. Since the relevant minors are polynomial in CπC_π and Xπ,0X_π,0, the same rank holds generically. Therefore hπ,Φ(T)=minnπ,Tdπ,h_π, (T)= \n_π,Td_π\, and Tlin(G)=maxπ:nπ>0⌈nπdπ⌉.T_lin(G)= _π:n_π>0 n_πd_π . Affine systems. The same argument extends to affine dynamics after adjoining the constant feature. For every nontrivial irrep, the dynamics and the proof above are unchanged. In the trivial component, write zt+1=Azt+bz_t+1=Az_t+b, where zt∈ℂn0z_t ^n_0. The associated feature vector is (1,zt)(1,z_t). Choosing A diagonal with distinct eigenvalues different from 11, and writing z⋆=(I−A)−1bz_ =(I-A)^-1b, gives zt=z⋆+At(z0−z⋆)z_t=z_ +A^t(z_0-z_ ). After an invertible row operation, the feature design matrix has rows 1,yi,λiyi,…,λiT−1yi,1, y_i, _iy_i,…, _i^T-1y_i, with y=z0−z⋆y=z_0-z_ . This is again a Vandermonde system, now with nodes 1,λ1,…,λn01, _1,…, _n_0. Thus the same representation-theoretic formula holds using the multiplicities of the affine feature representation; the constant feature simply adds one copy of the trivial representation. Finite Abelian groups. We first record a simple analytic lemma. Lemma B.2 (Analytic Vandermonde lemma). Let f1,…,fr:ℂd→ℂf_1,…,f_r:C^d be linearly independent analytic functions. Then there exist x∈ℂdx ^d and a diagonal matrix A=diag(λ1,…,λd)A=diag( _1,…, _d) such that det[fi(Atx)]i=1,…,r;t=0,…,r−1≠0. [f_i(A^tx) ]_i=1,…,r;\,t=0,…,r-1≠ 0. Proof. Expand the fif_i’s into their Taylor series at the origin. By invertible row operations, we may choose a basis of their span with distinct initial monomials xα1,…,xαrx _1,…,x _r. Choose a positive weight vector w for which these initial monomials remain distinct, and write ei=⟨w,αi⟩e_i= w, _i . Let x(s)=(sw1,…,swd)x(s)=(s^w_1,…,s^w_d). Then, for suitable nonzero coefficients cic_i, fi(Atx(s))=ci(λαi)tsei+higher-order terms in s.f_i(A^tx(s))=c_i(λ _i)^ts^e_i+higher-order terms in s. Choose the diagonal entries of A generically so that the numbers λα1,…,λαrλ _1,…,λ _r are distinct. The lowest order term of the determinant is then (∏i=1rci)s∑iei∏1≤i<j≤r(λαj−λαi), ( _i=1^rc_i )s _ie_i _1≤ i<j≤ r(λ _j-λ _i), which is nonzero. Hence the determinant is not identically zero, and is nonzero for some sufficiently small nonzero s. ∎ We now prove the Abelian claim from the main text. Since G is finite Abelian, there is a basis of ℂdC^d in which every ρ(g)ρ(g) is diagonal. Hence every diagonal matrix A commutes with the group action. By assumption, the state coordinates are contained in the span of the feature coordinates, so there is L satisfying LΦ(x)=xL (x)=x. Consequently, every equivariant linear map x↦Ax Ax of the above diagonal form belongs to ℱΦGF_ ^G. Fix an active irrep π. Since all irreducible complex representations of a finite Abelian group are one-dimensional, dπ=1d_π=1, and Φπ(x) _π(x) consists of mπm_π scalar analytic functions. These functions are linearly independent because the coordinates of Φ are linearly independent. Applying Lemma B.2 with r=mπr=m_π gives a valid equivariant linear trajectory for which π,mπ _π,m_π has full rank. Hence this rank is attained generically. Moreover, the first T columns of a nonsingular mπ×mπm_π× m_π design matrix are independent, giving hπ,Φ(T)=minmπ,T.h_π, (T)= \m_π,T\. Therefore TΦ(G)=maxπ:nπ>0mπ=maxπ:nπ>0mπdπ=Trep(G).T_ (G)= _π:n_π>0m_π= _π:n_π>0 m_πd_π=T_rep(G). Permutation-equivariant polynomial systems. We next prove the upper bound for full polynomial features. The key ingredient is the following elementary polynomial-orbit lemma. Lemma B.3 (Polynomial orbit lemma). Let g1,…,gr∈ℂ[x1,…,xd]g_1,…,g_r [x_1,…,x_d] be linearly independent polynomials and let q≥2q≥ 2. Then there exists x∈ℂdx ^d such that det[gi(x⊙qt)]i=1,…,r;t=0,…,r−1≠0, [g_i(x q^t) ]_i=1,…,r;\,t=0,…,r-1≠ 0, where the power is applied coordinatewise. Proof. Because the gig_i’s contain only finitely many monomials, choose a positive integer weight vector w assigning distinct weights to all monomials appearing in them. After invertible row operations, we may assume that their lowest-weight monomials are distinct, say cixαic_ix _i, with weights e1<⋯<ere_1<·s<e_r. Set x(s)=(sw1,…,swd)x(s)=(s^w_1,…,s^w_d). Then gi(x(s)⊙qt)=ciseiqt+higher-order terms.g_i(x(s) q^t)=c_is^e_iq^t+higher-order terms. In the determinant expansion, the lowest power of s is obtained by pairing the ordered numbers eie_i with the oppositely ordered numbers qtq^t. By the strict rearrangement inequality, this minimizing permutation is unique. Its coefficient is ±∏ici≠0± _ic_i≠ 0. Hence the determinant is a nonzero polynomial in s, and is nonzero for some s. ∎ Now let G be any subgroup of SdS_d, acting by coordinate permutations, and let Φ=Φ≤k = _≤ k with k≥2k≥ 2. Fix an active irrep π, and write the π-isotypic feature component in terms of its mπm_π multiplicity copies as F1(x),…,Fmπ(x)∈Vπ.F_1(x),…,F_m_π(x)∈ V_π. These are linearly independent polynomial equivariant maps. Choose any nonzero linear functional ℓ∈Vπ∗ ∈ V_π^*, and define gi=ℓ∘Fig_i= F_i. The polynomials g1,…,gmπg_1,…,g_m_π are linearly independent. Indeed, if ∑iaigi=0 _ia_ig_i=0, then the equivariant map F=∑iaiFiF= _ia_iF_i has image contained in the proper subspace kerℓ . If F≠0F≠ 0, the linear span of its image is a nonzero G-invariant subspace of the irreducible space VπV_π, and hence must equal VπV_π, a contradiction. Thus F=0F=0, and linear independence of the FiF_i’s gives ai=0a_i=0. Consider now the coordinatewise squaring dynamics xt+1=xt⊙2.x_t+1=x_t 2. This map is equivariant under every coordinate-permutation action and belongs to ℱΦ≤kF_ _≤ k whenever k≥2k≥ 2. By Lemma B.3, there is x0x_0 for which [gi(x0),gi(x1),…,gi(xmπ−1)]i=1mπ[g_i(x_0),g_i(x_1),…,g_i(x_m_π-1)]_i=1^m_π has rank mπm_π. This matrix is obtained from π,mπ _π,m_π by applying the same functional ℓ to the VπV_π-coordinate at every time step. Hence π,mπ _π,m_π itself has full row rank. The corresponding minor is therefore not identically zero in the system parameters and initial state, so full rank holds generically. We conclude that TΦ≤k(G)≤maxπ:nπ>0mπ.T_ _≤ k(G)≤ _π:n_π>0m_π. Quadratic systems with permutation symmetry. We finally verify the claims in Example 4.2. Let VrV_r denote the homogeneous degree-r polynomial space. Clearly V0=π0V_0= _0, while V1V_1 is the permutation representation, so V1=π0⊕πstdV_1= _0 _std. For V2V_2, the diagonal monomials xi2i=1d\x_i^2\_i=1^d form another copy of the permutation representation, while the off-diagonal monomials xixj:i<j\x_ix_j:i<j\ form the permutation representation on two-element subsets. For d≥4d≥ 4, the latter decomposes as π0⊕πstd⊕π(d−2,2) _0 _std _(d-2,2). Hence V2=2π0⊕2πstd⊕π(d−2,2),V_2=2 _0 2 _std _(d-2,2), giving mπ0=4m_ _0=4, mπstd=3m_ _std=3, and mπ(d−2,2)=1m_ _(d-2,2)=1. Only π0 _0 and πstd _std appear in the state representation. For the trivial block, dπ0=1d_ _0=1, so hπ0,Φ(T)≤min4,Th_ _0, (T)≤ \4,T\. The polynomial-orbit argument above provides a trajectory attaining rank four at T=4T=4; its first T columns are then independent for every T≤4T≤ 4. Thus hπ0,Φ(T)=min4,T.h_ _0, (T)= \4,T\. For the standard block, let P=I−1d⊤P=I- 1d11 denote projection onto the standard representation. A convenient basis for its three multiplicity copies is F1(x)=Px,F2(x)=P(x⊙2),F3(x)=(⊤x)Px.F_1(x)=Px, F_2(x)=P(x 2), F_3(x)=(1 x)Px. For every fixed x, F3(x)F_3(x) is proportional to F1(x)F_1(x), so the one-step rank is at most two. Since F1(x)F_1(x) and F2(x)F_2(x) are generically independent, hπstd,Φ(1)=2h_ _std, (1)=2. It remains to show that two transitions generically give rank three. Use the squaring dynamics and take x0=(1,2,3,0,…,0).x_0=(1,2,3,0,…,0). Represent VstdV_std using coordinate differences relative to the last coordinate. Selecting the first two such coordinates at time 0 and the first at time 11 gives the minor (12114161214), pmatrix1&2&1\\ 1&4&1\\ 6&12&14 pmatrix, whose determinant equals 1616. Thus the rank is three at T=2T=2, and hence generically. Therefore hπstd,Φ(T)=min3,2T.h_ _std, (T)= \3,2T\. The trivial block is consequently the bottleneck and TΦ≤2(Sd)=4T_ _≤ 2(S_d)=4. Representation stability for fixed-degree polynomial features. We conclude by proving the multiplicity formulas used in the main text. Let pd(r)p_d(r) denote the number of partitions of r into at most d parts, and let p(r)p(r) be the unrestricted partition function. For the homogeneous space VrV_r, the multiplicity of the trivial representation is multVr(π0)=dimVrSd=pd(r),mult_V_r( _0)= V_r^S_d=p_d(r), since an orbit of monomials under coordinate permutations is specified by a partition of r with at most d parts. Hence, for d≥rd≥ r, multVr(π0)=p(r).mult_V_r( _0)=p(r). To compute the standard multiplicity, use the decomposition of the permutation representation ℂd=π0⊕πstdC^d= _0 _std and the identity ℂd≅IndSd−1Sd.C^d _S_d-1^S_d1. Frobenius reciprocity gives multVr(ℂd)=dimVrSd−1.mult_V_r(C^d)= V_r^S_d-1. An Sd−1S_d-1-invariant polynomial may have an arbitrary power on one distinguished variable and must be symmetric in the remaining d−1d-1 variables. Therefore dimVrSd−1=∑j=0rpd−1(j). V_r^S_d-1= _j=0^rp_d-1(j). Subtracting the trivial multiplicity yields multVr(πstd)=∑j=0rpd−1(j)−pd(r).mult_V_r( _std)= _j=0^rp_d-1(j)-p_d(r). When d≥r+1d≥ r+1, this simplifies to multVr(πstd)=∑j=0r−1p(j).mult_V_r( _std)= _j=0^r-1p(j). Summing over 0≤r≤k0≤ r≤ k, and taking d≥k+1d≥ k+1, gives the stable multiplicities mπ0=∑r=0kp(r),mπstd=∑j=0k−1(k−j)p(j).m_ _0= _r=0^kp(r), m_ _std= _j=0^k-1(k-j)p(j). Since the state permutation representation contains only these two irreducible representations, defining Mk≔maxmπ0,mπstdM_k \m_ _0,m_ _std\ and applying the preceding polynomial identification bound gives TΦ≤k(Sd)≤Mk,d≥k+1.T_ _≤ k(S_d)≤ M_k, d≥ k+1. For fixed k, MkM_k is independent of d, proving TΦ≤k(Sd)=Ok(1)T_ _≤ k(S_d)=O_k(1). Finally, the classical Hardy–Ramanujan estimate p(k)∼14k3exp(π2k3)p(k) 14k 3 (π 2k3 ) also gives the stated dependence on k. Indeed, Mk≥mπ0≥p(k)M_k≥ m_ _0≥ p(k), while monotonicity of p(⋅)p(·) gives mπ0≤(k+1)p(k)m_ _0≤(k+1)p(k) and mπstd≤k2p(k)m_ _std≤ k^2p(k). Hence Mk=exp(π2k3+O(logk)).M_k= (π 2k3+O( k) ). B.2 Proofs for adaptive symmetry discovery We first record a simple observation showing that it is sufficient to impose equivariance on a generating set. Lemma B.4 (Equivariance from generators). Let S⊆GS G generate G. A matrix W satisfies ρ(s)W=WρΦ(s)for every s∈Sρ(s)W=W _ (s) every s∈ S if and only if it is G-equivariant. Proof. Only the forward direction requires proof. If the intertwining identity holds for g,h∈Gg,h∈ G, then ρ(gh)W=ρ(g)ρ(h)W=ρ(g)WρΦ(h)=WρΦ(gh).ρ(gh)W=ρ(g)ρ(h)W=ρ(g)W _ (h)=W _ (gh). Moreover, ρ(g)W=WρΦ(g)ρ(g)W=W _ (g) also implies ρ(g−1)W=WρΦ(g−1)ρ(g^-1)W=W _ (g^-1). Hence the identity is preserved under composition and inversion, and therefore holds for every element of ⟨S⟩=G S =G. ∎ Proof of Theorem 4.5. We prove correctness, the trajectory-length guarantee, and computational efficiency of Algorithm 1. Linear feasibility problem. Fix a candidate group H∈H and sampled elements SH=g1,…,gNS_H=\g_1,…,g_N\. From the observed trajectory, define X=[Φ(x0),…,Φ(xT−1)],Y=[x1,…,xT].X=[ (x_0),…, (x_T-1)], Y=[x_1,…,x_T]. The algorithm asks whether there exists a candidate parameter matrix W~∈ℂd×m W ^d× m satisfying W~X=Y,ρ(gi)W~=W~ρΦ(gi),i=1,…,N. WX=Y, ρ(g_i) W= W _ (g_i), i=1,…,N. These are linear equations in the entries of W~ W. For completeness, letting w~=vec(W~) w=vec( W), the data constraint becomes (X⊤⊗Id)w~=vec(Y),(X I_d) w=vec(Y), while each equivariance constraint becomes (Im⊗ρ(gi)−ρΦ(gi)⊤⊗Id)w~=0. (I_m ρ(g_i)- _ (g_i) I_d ) w=0. Thus each candidate group is tested by solving a single finite-dimensional linear feasibility problem. Random generators. Let ℰE denote the event that, for every candidate H∈H , the sampled multiset SHS_H generates H. By Corollary A.3 and the choice N=N,δN=N_G,δ, ℙ(ℰ)≥1−δ.P(E)≥ 1-δ. We condition on this event for the remainder of the correctness argument. On ℰE, Lemma B.4 implies that the equivariance constraints imposed for a candidate H are equivalent to full H-equivariance. Hence the feasibility test succeeds for H exactly when there exists an H-equivariant system consistent with the observed trajectory. Feasibility of the true group. Let G∈G be the full symmetry group of the unknown dynamics within the ambient group Γ , and let W denote its parameter matrix. Since the true dynamics are G-equivariant, W satisfies all constraints corresponding to G, and hence G is feasible. Moreover, T≥TΦ()≥TΦ(G)T≥ T_ (G)≥ T_ (G). By Theorem 4.1, a generic G-equivariant system is uniquely identifiable from the observed trajectory. Therefore W is the unique G-equivariant parameter matrix consistent with the data. In particular, any feasible solution stored by the algorithm for the candidate G is exactly the true parameter matrix W. Characterization of all feasible candidates. Every candidate subgroup H of G is feasible, since a G-equivariant system is automatically H-equivariant. Conversely, suppose a candidate H∈H is feasible. On the event ℰE, feasibility means that there exists an H-equivariant system consistent with the trajectory. Since G is generically separating, Definition 4.4 then implies that H is a subgroup of G. Thus, on ℰE, every feasible candidate is a subgroup of the true group, while G itself is feasible. Since every proper subgroup of a finite group has strictly smaller cardinality, G is the unique feasible candidate of maximum cardinality. Algorithm 1 therefore selects G and returns the corresponding parameter matrix W. The same event also guarantees G=⟨SG⟩G= S_G , so the returned set SGS_G is a generating set of the full symmetry group. Since ℙ(ℰ)≥1−δP(E)≥ 1-δ, the algorithm succeeds with probability at least 1−δ1-δ. Trajectory length. The preceding argument requires only T≥TΦ()=maxH∈TΦ(H).T≥ T_ (G)= _H T_ (H). Thus, under generic candidate separation, adaptive symmetry discovery requires no additional trajectory observations beyond the worst-case trajectory length needed when the candidate group is known. Computational complexity. Let p=dmp=dm. For each candidate group, the unknown vector w~ w has p entries. The trajectory contributes dTdT scalar linear equations, while the N sampled group elements contribute at most NpNp scalar equivariance equations. Thus the complete feasibility system has at most dT+NpdT+Np equations in p unknowns. Using dense linear algebra, feasibility and a solution can therefore be computed in time polynomial in d,m,Td,m,T, and N. More explicitly, forming the equivariance constraints explicitly and applying Gaussian elimination gives the coarse per-candidate bound O(d3m2T+Nd3m3),O (d^3m^2T+Nd^3m^3 ), with polynomial memory complexity. Since N=O(log|G|max+log||+log1δ),N=O ( |G|_ + |G|+ 1δ ), and the procedure is repeated for |||G| candidates, the overall runtime is polynomial in d,m,T,||,log|G|max,log(1/δ),d,\;m,\;T,\;|G|,\; |G|_ ,\; (1/δ), assuming uniform sampling and representation evaluation for each candidate group can be performed efficiently. This proves the theorem. ∎ Nested candidate families. We next justify the claim that generic candidate separation is automatic for nested candidate families. Proposition B.5 (Separation for nested families). Suppose the groups in G are totally ordered by inclusion. Then G is generically separating. Proof. Let G∈G be the full symmetry group of a generic system and suppose T≥TΦ()T≥ T_ (G). Consider a candidate H∈H admitting an H-equivariant system W~ W consistent with the trajectory. Since the family is totally ordered by inclusion, either H is a subgroup of G, in which case there is nothing to prove, or G is a proper subgroup of H. In the latter case, every H-equivariant system is also G-equivariant. Hence W~ W is a G-equivariant system consistent with the trajectory. Since T≥TΦ(G)T≥ T_ (G), Theorem 4.1 implies W~=W W=W, where W is the true parameter matrix. But then the true system is H-equivariant, contradicting the assumption that its full symmetry group is G. Therefore H must be a subgroup of G. ∎ B.3 Proof of Theorem 4.11 Proof. Let H≤ΓH≤ be the full symmetry group of the unknown dynamics, with [Γ:H]≤B[ :H]≤ B, and suppose generic elementwise separation holds at the trajectory length T. Algorithm 2 repeatedly samples g∼Unif(Γ)g ( ) and accepts g whenever there exists W~ W satisfying W~X=Y,ρ(g)W~=W~ρΦ(g). WX=Y, ρ(g) W= W _ (g). If g∈Hg∈ H, the true parameter matrix W satisfies these constraints. Conversely, generic elementwise separation implies that feasibility can hold only if g∈Hg∈ H. Hence the algorithm accepts exactly the samples lying in H. It follows that the accepted elements are i.i.d. uniform samples from H. Moreover, ℙg∼Unif(Γ)(g∈H)=|H||Γ|=1[Γ:H]≥1B.P_g ( )(g∈ H)= |H|| |= 1[ :H]≥ 1B. Thus each accepted sample requires at most B ambient samples in expectation. By the random-generation result, the choice NΓ,δ=⌈8(⌈log2|Γ|⌉+log1δ)⌉N_ ,δ= 8 ( _2| | + 1δ ) ensures that the accepted set S generates H with probability at least 1−δ1-δ, since |H|≤|Γ||H|≤| |. Condition on this event. By Lemma B.4, imposing the intertwining constraints for all g∈Sg∈ S is equivalent to imposing H-equivariance. Since T≥TΦ(ℋB)≥TΦ(H),T≥ T_ (H_B)≥ T_ (H), Theorem 4.1 implies that the unique H-equivariant parameter matrix consistent with the trajectory is the true matrix W. Therefore Algorithm 2 returns the true dynamics together with a generating set of its full symmetry group. Finally, obtaining NΓ,δN_ ,δ accepted elements requires at most BNΓ,δBN_ ,δ ambient samples and feasibility tests in expectation. Hence the expected number of tests is O(B(log|Γ|+log1δ)),O (B ( | |+ 1δ ) ), with no dependence on the number of bounded-index subgroups of Γ . Assuming efficient ambient-group sampling, representation evaluation, and linear feasibility testing, the expected runtime is polynomial in d,m,T,B,log|Γ|,log(1/δ).d,\;m,\;T,\;B,\; | |,\; (1/δ). If B=O(1)B=O(1), the rejection-sampling overhead is constant relative to direct sampling from H. The same argument gives a high-probability runtime bound: by a standard Chernoff bound, O(B(NΓ,δ+log(1/η)))O(B(N_ ,δ+ (1/η))) ambient samples suffice to obtain NΓ,δN_ ,δ accepted elements with probability at least 1−η1-η. ∎ Remark B.6 (Cayley-graph interpretation). The proof only requires that the accepted samples generate the unknown group H, equivalently that their symmetric Cayley graph is connected. The Alon–Roichman theorem gives the stronger conclusion that O(log|H|)O( |H|) uniform samples produce an expanding Cayley graph with high probability. In the bounded-index setting, the feasibility test acts as rejection sampling from Γ , producing exactly uniform elements of the unknown subgroup H, so the same random-Cayley-graph interpretation applies. Appendix C Experiments Table 1: Dimension of the space of equivariant linear maps A∈ℝd×d:ρ(g)A=Aρ(g),∀g∈G\A ^d× d:ρ(g)A=Aρ(g),\ ∀ g∈ G\ for several permutation group actions on ℝdR^d, with d=10d=10. Group G Generators dim(equivariant maps) (equivariant maps) Description Trivial (no symmetry) e\e\ d2=100d^2=100 All linear maps Single transposition C2=⟨(1 2)⟩C_2= (1\,2) one swap d2−2d+2=82d^2-2d+2=82 Single swap constraint Cyclic shifts CdC_d one d-cycle d=10d=10 Circulant matrices Dihedral group DdD_d shift + reversal d/2+1=6d/2+1=6 Symmetric circulant Block permutations S5×S5S_5× S_5 within-block swaps 66 Two exchangeable blocks Full symmetric group SdS_d adjacent swaps 22 αI+β⊤α I+ 11 In this section, we present a simple proof-of-concept experiment illustrating the sample-complexity results developed in this paper. Our focus is primarily theoretical, and the experiment serves as a complementary empirical illustration of the predicted identification thresholds. Dimension of equivariant maps for permutation symmetries. We consider linear dynamics on ℝdR^d of the form xt+1=Axt,t=0,…,T−1,x_t+1=Ax_t, t=0,…,T-1, (7) where A∈ℝd×dA ^d× d is unknown. Let G be a finite group acting on ℝdR^d by coordinate permutations, represented by permutation matrices ρ(g)ρ(g). The dynamics is G-equivariant if ρ(g)A=Aρ(g),∀g∈G.ρ(g)A=Aρ(g), ∀ g∈ G. (8) The matrices satisfying (8) form the commutant (G)≔A∈ℝd×d:ρ(g)A=Aρ(g),∀g∈G.C(G) \A ^d× d:ρ(g)A=Aρ(g),\ ∀ g∈ G\. For permutation actions, dim((G)) (C(G)) has a simple combinatorial interpretation. Equation (8) is equivalent to Aij=Ag(i)g(j)A_ij=A_g(i)g(j) for every g∈Gg∈ G. Thus, the entries of A must be constant on the orbits of the diagonal action of G on ordered pairs (i,j)(i,j). Consequently, dim((G))=#orbits of G on 1,…,d2. (C(G))=\#\orbits of $G$ on \1,…,d\^2\. (9) Table 1 gives this dimension for several standard permutation actions with d=10d=10. For example, under the full symmetric group SdS_d, ordered pairs form only two orbits: diagonal pairs (i,i)(i,i) and off-diagonal pairs (i,j)(i,j), i≠ji≠ j. Hence dim((Sd))=2 (C(S_d))=2, and every SdS_d-equivariant matrix has the form αI+β⊤α I+ 11 , for α,β∈ℝα,β . Dimension of the feasible set vs. trajectory length. Given a trajectory (x0,…,xT)(x_0,…,x_T) generated by (7), define X=[x0,…,xT−1],Y=[x1,…,xT].X=[x_0,…,x_T-1], Y=[x_1,…,x_T]. The trajectory constraint is Y=AXY=AX. Fix an assumed permutation symmetry group H and restrict A to (H)C(H). We study the feasible set T(H)≔A∈(H):Y=AX.S_T(H) \A (H):Y=AX\. (10) Whenever nonempty, T(H)S_T(H) is an affine subspace. We measure its affine dimension dim(T(H)) (S_T(H)); in particular, dim(T(H))=0⟺the trajectory uniquely identifies A within (H). (S_T(H))=0 trajectory uniquely identifies $A$ within $ C(H)$. Computing the feasible-set dimension. Let r=dim((H))r= (C(H)), and fix a basis A1,…,ArA_1,…,A_r of (H)C(H). Writing A=∑i=1rθiAiA= _i=1^r _iA_i, the constraint Y=AXY=AX becomes vec(Y)=[vec(A1X)⋯vec(ArX)]θ.vec(Y)= bmatrixvec(A_1X)&·s&vec(A_rX) bmatrixθ. When feasible, dim(T(H)) (S_T(H)) is therefore r minus the rank of this design matrix. Experimental setup. We set d=10d=10 and draw x0∼(0,Id)x_0 (0,I_d). We consider three matched settings in which the true dynamics matrix A is drawn from a continuous distribution on: (i) (C2)C(C_2), where C2=⟨(1 2)⟩C_2= (1\,2) ; (i) the unconstrained space ℝd×dR^d× d; and (i) (Sd)C(S_d). For each setting, we evaluate dim(T(H)) (S_T(H)) using the corresponding correct symmetry assumption H, and report the median over independent trials. These three settings have exact theoretical identification thresholds predicted by the linear-system result of Section 4.1. For the trivial group, the state representation contains d copies of its one-dimensional irrep, giving Tlin=d=10T_lin=d=10. For the single transposition, the state representation consists of d−1d-1 copies of the trivial representation and one copy of the sign representation, giving Tlin=d−1=9T_lin=d-1=9. Finally, for SdS_d, ℝd≅π0⊕πstdR^d _0 _std, with both irreducible components appearing once, and hence Tlin=1T_lin=1. Observed behavior. Figure 1 plots dim(T(H)) (S_T(H)) as a function of the trajectory length T. The feasible-set dimension decreases with T and reaches zero exactly when the dynamics becomes uniquely identifiable within the assumed equivariant class. The empirical transitions agree with the theoretical predictions: the fully permutation-equivariant system reaches dimension zero at T=1T=1, the single-transposition system at T=9T=9, and the unconstrained system at T=10T=10. The dimensions in Table 1 provide useful intuition for the reduction in parameter complexity under symmetry, although the identification threshold is determined more precisely by the representation multiplicities characterized in Theorem 4.1. Figure 1: Dimension of the feasible solution set T(H)S_T(H) as a function of trajectory length T for the correctly matched symmetry classes. The dimension reaches zero at the predicted generic identification thresholds T=1,9,T=1,9, and 1010 for SdS_d, C2C_2, and the trivial group, respectively. Appendix D Notation We collect the main notation used throughout the paper. Symbol Meaning G Finite group acting on the state and feature spaces G G Equivalence classes of irreducible representations of G π∈G^π∈ G An irreducible representation of G VπV_π Representation space of π dπd_π Dimension of VπV_π ρ Representation of G on the state space ℂdC^d ρΦ _ Representation of G on the feature space ℂmC^m nπn_π Multiplicity of π in the state representation mπm_π Multiplicity of π in the feature representation Φ Feature map Φ:ℂd→ℂm :C^d ^m Φ≤k _≤ k Full polynomial feature map of degree at most k ℱΦF_ Systems f(x)=WΦ(x)f(x)=W (x) associated with Φ ℱΦGF_ ^G G-equivariant systems in ℱΦF_ W Parameter matrix W:ℂm→ℂdW:C^m ^d CπC_π Multiplicity-space matrix of the π-block of W IVπI_V_π Identity map on VπV_π xtx_t State at time t T Trajectory length Xπ(xt)X_π(x_t) Matrix form of the π-isotypic component of xtx_t Φπ(xt) _π(x_t) Matrix form of the π-isotypic component of Φ(xt) (x_t) π,T _π,T Block feature matrix [Φπ(x0),…,Φπ(xT−1)][ _π(x_0),…, _π(x_T-1)] hπ,Φ(T)h_π, (T) Generic rank of π,T _π,T TΦ(G)T_ (G) Generic identification trajectory length for known G Trep(G)T_rep(G) Representation-theoretic lower bound on TΦ(G)T_ (G) Γ Ambient finite group of candidate transformations G Finite family of candidate groups TΦ()T_ (G) Worst-case threshold maxG∈TΦ(G) _G T_ (G) |G|max|G|_ Maximum cardinality of a group in G S Set or multiset of sampled group elements ⟨S⟩ S Subgroup generated by S Cay(G,S)Cay(G,S) Cayley graph of G generated by S N,δN_G,δ Number of random samples used per candidate group δ Failure probability ℋBH_B Family of candidate subgroups of index at most B [Γ:H][ :H] Index of a subgroup H in Γ B Upper bound on candidate subgroup index MkM_k Stable maximal active multiplicity for degree-k features p(r)p(r) Number of integer partitions of r (G)C(G) Commutant of a permutation action in the experiments T(H)S_T(H) Feasible parameter set under assumed symmetry H