Adaptive Symmetry Discovery for Dynamical System Identification

# Adaptive Symmetry Discovery for Dynamical System Identification
Source: [https://arxiv.org/html/2608.08091](https://arxiv.org/html/2608.08091)
Behrooz Tahmasebi111Harvard John A\. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA\. Emails:\{behrooz\_tahmasebi,mweber\}@seas\.harvard\.edu

###### 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. [1Introduction](https://arxiv.org/html/2608.08091#S1)
2. [2Related Work](https://arxiv.org/html/2608.08091#S2)
3. [3Problem Statement](https://arxiv.org/html/2608.08091#S3)1. [3\.1Feature\-lifted linear dynamical systems](https://arxiv.org/html/2608.08091#S3.SS1) 2. [3\.2Equivariant dynamics](https://arxiv.org/html/2608.08091#S3.SS2) 3. [3\.3Identifiability from a single trajectory](https://arxiv.org/html/2608.08091#S3.SS3)
4. [4Main Results](https://arxiv.org/html/2608.08091#S4)1. [4\.1Sample complexity of equivariant identification](https://arxiv.org/html/2608.08091#S4.SS1) 2. [4\.2Adaptive symmetry discovery](https://arxiv.org/html/2608.08091#S4.SS2)
5. [5Conclusion and Future Work](https://arxiv.org/html/2608.08091#S5)
6. [References](https://arxiv.org/html/2608.08091#bib)
7. [APreliminaries](https://arxiv.org/html/2608.08091#A1)1. [A\.1Groups, representations, and equivariance](https://arxiv.org/html/2608.08091#A1.SS1) 2. [A\.2Cayley graphs, expanders, and random generators](https://arxiv.org/html/2608.08091#A1.SS2)
8. [BProofs of Main Results](https://arxiv.org/html/2608.08091#A2)1. [B\.1Proof ofTheorem4\.1](https://arxiv.org/html/2608.08091#A2.SS1) 2. [B\.2Proofs for adaptive symmetry discovery](https://arxiv.org/html/2608.08091#A2.SS2) 3. [B\.3Proof ofTheorem4\.11](https://arxiv.org/html/2608.08091#A2.SS3)
9. [CExperiments](https://arxiv.org/html/2608.08091#A3)
10. [DNotation](https://arxiv.org/html/2608.08091#A4)

## 1Introduction

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\(Bruntonet al\.,[2016](https://arxiv.org/html/2608.08091#bib.bib105); Yu and Wang,[2024](https://arxiv.org/html/2608.08091#bib.bib99); Wang and Yu,[2025](https://arxiv.org/html/2608.08091#bib.bib101)\)\. The problem of discovering governing equations from data, often formulated through the lens of dynamical systems\(Bruntonet al\.,[2016](https://arxiv.org/html/2608.08091#bib.bib105)\), 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](https://arxiv.org/html/2608.08091#bib.bib103); Isermann and Münchhof,[2011](https://arxiv.org/html/2608.08091#bib.bib104)\)\.

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\(Bronsteinet al\.,[2021](https://arxiv.org/html/2608.08091#bib.bib20); Weber,[2025](https://arxiv.org/html/2608.08091#bib.bib46)\)\. 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\.

## 2Related 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\(Bruntonet al\.,[2016](https://arxiv.org/html/2608.08091#bib.bib105); Yu and Wang,[2024](https://arxiv.org/html/2608.08091#bib.bib99); Wang and Yu,[2025](https://arxiv.org/html/2608.08091#bib.bib101); Sivaranjaniet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib100)\)\. 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](https://arxiv.org/html/2608.08091#bib.bib103); Isermann and Münchhof,[2011](https://arxiv.org/html/2608.08091#bib.bib104)\)\. 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,Simchowitzet al\.\([2018](https://arxiv.org/html/2608.08091#bib.bib79)\)study the identification of linear dynamical systems from a single noisy trajectory, with subsequent extensions to nonlinear systems under similar single\-trajectory assumptions\(Fosteret al\.,[2020](https://arxiv.org/html/2608.08091#bib.bib76); Ziemannet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib80)\)\.

Beyond this, prior work has also investigated finite\-sample identification of linear time\-invariant systems\(Sarkar and Rakhlin,[2019](https://arxiv.org/html/2608.08091#bib.bib77); Sarkaret al\.,[2021](https://arxiv.org/html/2608.08091#bib.bib75)\), regimes involving multiple trajectories\(Tuet al\.,[2024](https://arxiv.org/html/2608.08091#bib.bib78)\), as well as system identification and control over a single trajectory\(Feffermanet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib107); Carruthet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib108),[2024](https://arxiv.org/html/2608.08091#bib.bib109)\)\. 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](https://arxiv.org/html/2608.08091#bib.bib8),[2024](https://arxiv.org/html/2608.08091#bib.bib18)\), 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\(Desaiet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib42); Yanget al\.,[2023](https://arxiv.org/html/2608.08091#bib.bib25); Perin and Deny,[2025](https://arxiv.org/html/2608.08091#bib.bib94)\), including Lie algebra–based convolutional networks\(Dehmamyet al\.,[2021](https://arxiv.org/html/2608.08091#bib.bib43)\); see also\(Romero and Lohit,[2022](https://arxiv.org/html/2608.08091#bib.bib13); Koet al\.,[2024](https://arxiv.org/html/2608.08091#bib.bib82); Huet al\.,[2025c](https://arxiv.org/html/2608.08091#bib.bib93)\)\. Methods based on infinitesimal generators for discovering symmetries in nonlinear dynamical data have also been studied\(Huet al\.,[2025a](https://arxiv.org/html/2608.08091#bib.bib85)\); see\(Shawet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib87)\)for related approaches\.

Beyond these, methods for discovering nonlinear group actions in latent spaces have been proposed\(Yanget al\.,[2024a](https://arxiv.org/html/2608.08091#bib.bib45)\), including approaches that go beyond affine transformations and address manifold\-structured data\(Shawet al\.,[2024](https://arxiv.org/html/2608.08091#bib.bib44); Bhatet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib95)\)\. Another line of work learns symmetries from layer gradients to relax hard invariance constraints\(van der Ouderaaet al\.,[2023](https://arxiv.org/html/2608.08091#bib.bib27)\), while flow matching has recently been used to discover Lie group symmetries\(Parket al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib90)\)\. For symmetry discovery in differential equations and PDEs, see\(Kreideret al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib84); Huet al\.,[2025b](https://arxiv.org/html/2608.08091#bib.bib88); Yanget al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib91),[2024b](https://arxiv.org/html/2608.08091#bib.bib98)\)\. Other approaches include quadratic\-form\-based methods\(Karjolet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib89)\)and learnable data augmentation strategies\(Santos\-Escriche and Jegelka,[2025](https://arxiv.org/html/2608.08091#bib.bib92)\)\. For symmetry discovery in finite groups using representation\-theoretic tools, see\(Huh,[2025](https://arxiv.org/html/2608.08091#bib.bib57)\)\. Jointly discovering and enforcing symmetries has also been studied\(Ottoet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib97)\)\. Finally, we note that symmetry discovery is fundamentally different from \(binary\) hypothesis testing for the presence of symmetry in data\(Soleymaniet al\.,[2025b](https://arxiv.org/html/2608.08091#bib.bib60)\)\.

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 inGabelet al\.\([2024](https://arxiv.org/html/2608.08091#bib.bib102)\), while the discovery of finite symmetry groups in dynamical systems is considered inCalvo\-Barléset al\.\([2025a](https://arxiv.org/html/2608.08091#bib.bib81),[b](https://arxiv.org/html/2608.08091#bib.bib86)\)\. A related approach is proposed inLiet al\.\([2025](https://arxiv.org/html/2608.08091#bib.bib96)\), 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\(Kabaet al\.,[2023](https://arxiv.org/html/2608.08091#bib.bib35); Tahmasebi and Jegelka,[2025b](https://arxiv.org/html/2608.08091#bib.bib30),[a](https://arxiv.org/html/2608.08091#bib.bib31); Shumaylovet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib33)\)and frame averaging\(Punyet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib34); Atzmonet al\.,[2022](https://arxiv.org/html/2608.08091#bib.bib50); Linet al\.,[2024](https://arxiv.org/html/2608.08091#bib.bib28)\)to data augmentation\(Tahmasebiet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib72)\)\. 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](https://arxiv.org/html/2608.08091#bib.bib74)\)and learning under invariances\(Soleymaniet al\.,[2025c](https://arxiv.org/html/2608.08091#bib.bib49),[a](https://arxiv.org/html/2608.08091#bib.bib73)\)\.

## 3Problem 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](https://arxiv.org/html/2608.08091#A1)\.

#### Dynamical systems\.

A \(discrete\-time\) dynamical system is specified by a function

f:ℂd→ℂd,f:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\},which governs the state evolution according to

xt\+1=f​\(xt\),t=0,1,…,x\_\{t\+1\}=f\(x\_\{t\}\),\\qquad t=0,1,\\ldots,\(1\)wherext=\(xt1,xt2,…,xtd\)⊤∈ℂdx\_\{t\}=\(x\_\{t\}^\{1\},x\_\{t\}^\{2\},\\ldots,x\_\{t\}^\{d\}\)^\{\\top\}\\in\\mathbb\{C\}^\{d\}denotes the*state*of the system at timett\. We refer toffas the*dynamics*of the system and assume thatffbelongs to a function classℱ\\mathcal\{F\}\.

#### Trajectories and learning objective\.

Given an initial statex0∈ℂdx\_\{0\}\\in\\mathbb\{C\}^\{d\}, the dynamicsffgenerates a*trajectory*

\(x0,x1,…,xT\)∈ℂd×\(T\+1\),\(x\_\{0\},x\_\{1\},\\ldots,x\_\{T\}\)\\in\\mathbb\{C\}^\{d\\times\(T\+1\)\},whereT∈ℕT\\in\\mathbb\{N\}denotes the number of observed transitions\. In the system identification problem, a learner observes such a trajectory and aims to recover the underlying unknown dynamicsf∈ℱf\\in\\mathcal\{F\}\.

Clearly, if the function classℱ\\mathcal\{F\}is too rich, recoveringfffrom a finite\-length trajectory is impossible\. This motivates restricting attention to structured and low\-complexity families of dynamics\.

### 3\.1Feature\-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\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{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\\Phi\(x\_\{t\}\),\\qquad W\\in\\mathbb\{C\}^\{d\\times m\}\.\(2\)We refer toΦ\\Phias the*feature map*and toℂm\\mathbb\{C\}^\{m\}as the*feature space*\. For convenience, we write

ϕt≔Φ​\(xt\)∈ℂm\.\\phi\_\{t\}\\coloneqq\\Phi\(x\_\{t\}\)\\in\\mathbb\{C\}^\{m\}\.Without loss of generality, we assume thatΦ\\Phihas linearly independent coordinates as functions ofx∈ℂdx\\in\\mathbb\{C\}^\{d\}\.

###### Definition 3\.1\(Feature\-lifted linear dynamical systems\)\.

LetΦ:ℂd→ℂm\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{m\}be a fixed finite\-dimensional feature map\. We define

ℱΦ≔\{f:ℂd→ℂd\|f\(x\)=WΦ\(x\):∀W∈ℂd×m\}\.\\mathcal\{F\}\_\{\\Phi\}\\coloneqq\\left\\\{f:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}\\;\\middle\|\\;f\(x\)=W\\Phi\(x\):\\forall~W\\in\\mathbb\{C\}^\{d\\times m\}\\right\\\}\.Thus, every system inℱΦ\\mathcal\{F\}\_\{\\Phi\}is nonlinear in the statexxin general, but linear in the lifted featuresΦ​\(x\)\\Phi\(x\)\.

This modeling assumption encompasses a rich family of nonlinear dynamical systems while retaining a linear parameterization in feature space\. The choice ofΦ\\Phidetermines 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 mostk∈ℕk\\in\\mathbb\{N\}:

Φ≤k​\(x\)=\(\(x1\)α1​\(x2\)α2​⋯​\(xd\)αd\)α∈ℐk∈ℂm,\\Phi\_\{\\leq k\}\(x\)=\\Bigl\(\(x^\{1\}\)^\{\\alpha\_\{1\}\}\(x^\{2\}\)^\{\\alpha\_\{2\}\}\\cdots\(x^\{d\}\)^\{\\alpha\_\{d\}\}\\Bigr\)\_\{\\alpha\\in\\mathcal\{I\}\_\{k\}\}\\in\\mathbb\{C\}^\{m\},whereℐk=\{α∈ℤ≥0d\|∑i=1dαi≤k\}\.\\mathcal\{I\}\_\{k\}=\\left\\\{\\alpha\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{d\}\\;\\middle\|\\;\\sum\_\{i=1\}^\{d\}\\alpha\_\{i\}\\leq k\\right\\\}\.The feature dimension ism=\(d\+kd\)\.m=\\binom\{d\+k\}\{d\}\.We denote the corresponding class byℱ≤k≔ℱΦ≤k\.\\mathcal\{F\}\_\{\\leq k\}\\coloneqq\\mathcal\{F\}\_\{\\Phi\_\{\\leq k\}\}\.This recovers polynomial dynamical systems of total degree at mostk∈ℕk\\in\\mathbb\{N\}\.

###### Example 3\.3\(Fourier features\)\.

Another canonical choice is a finite band\-limited Fourier feature map\. LetΛ⊂ℤd\\Lambda\\subset\\mathbb\{Z\}^\{d\}be a finite set of frequencies, for instanceΛ=\{w∈ℤd:‖w‖2≤C\}\\Lambda=\\\{w\\in\\mathbb\{Z\}^\{d\}:\\\|w\\\|\_\{2\}\\leq C\\\}for someC\>0C\>0\. Define

Φ​\(x\)=\(e2​π​i​⟨w,x⟩\)w∈Λ∈ℂ\|Λ\|\.\\Phi\(x\)=\\left\(e^\{2\\pi i\\langle w,x\\rangle\}\\right\)\_\{w\\in\\Lambda\}\\in\\mathbb\{C\}^\{\|\\Lambda\|\}\.The corresponding classℱ=ℱΦ\\mathcal\{F\}=\\mathcal\{F\}\_\{\\Phi\}consists of dynamics whose coordinates are trigonometric polynomials supported onΛ\\Lambda\.

###### 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=W1​xt,W1∈ℂd×d,x\_\{t\+1\}=W\_\{1\}x\_\{t\},\\qquad W\_\{1\}\\in\\mathbb\{C\}^\{d\\times d\},and an affine system

xt\+1=W1​xt\+w0,W1∈ℂd×d,w0∈ℂd,x\_\{t\+1\}=W\_\{1\}x\_\{t\}\+w\_\{0\},\\qquad W\_\{1\}\\in\\mathbb\{C\}^\{d\\times d\},\\;w\_\{0\}\\in\\mathbb\{C\}^\{d\},belong toℱ≤1\\mathcal\{F\}\_\{\\leq 1\}, sinceΦ≤1\\Phi\_\{\\leq 1\}contains the constant feature and all coordinate functions\.

### 3\.2Equivariant 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 groupGGis 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 onnnelements, consisting of all bijectionsσ:\[n\]→\[n\]\\sigma:\[n\]\\to\[n\]under composition\.

A linear representation of a groupGGonℂn\\mathbb\{C\}^\{n\}is a homomorphismρ:G→GLn​\(ℂ\)\\rho:G\\to\\mathrm\{GL\}\_\{n\}\(\\mathbb\{C\}\), assigning to eachg∈Gg\\in Gan invertible matrixρ​\(g\)∈ℂn×n\\rho\(g\)\\in\\mathbb\{C\}^\{n\\times n\}such that

ρ​\(g​h\)=ρ​\(g\)​ρ​\(h\),∀g,h∈G\.\\rho\(gh\)=\\rho\(g\)\\rho\(h\),\\qquad\\forall g,h\\in G\.We refer toρ​\(g\)\\rho\(g\)as the action ofggonℂn\\mathbb\{C\}^\{n\}\.

#### Lifted group actions\.

Suppose a finite groupGGacts linearly on the state spaceℂd\\mathbb\{C\}^\{d\}via a representationρ:G→GLd​\(ℂ\)\\rho:G\\to\\mathrm\{GL\}\_\{d\}\(\\mathbb\{C\}\)\. We assume that the feature mapΦ:ℂd→ℂm\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{m\}is compatible with this action, in the sense that there exists a representationρΦ:G→GLm​\(ℂ\)\\rho\_\{\\Phi\}:G\\to\\mathrm\{GL\}\_\{m\}\(\\mathbb\{C\}\)satisfying

Φ​\(ρ​\(g\)​x\)=ρΦ​\(g\)​Φ​\(x\),∀g∈G,x∈ℂd\.\\Phi\(\\rho\(g\)x\)=\\rho\_\{\\Phi\}\(g\)\\Phi\(x\),\\qquad\\forall g\\in G,\\;x\\in\\mathbb\{C\}^\{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 ofGG\.

We are now ready to define equivariant dynamical systems\.

###### Definition 3\.5\(Equivariant dynamical systems\)\.

LetGGbe a finite group acting onℂd\\mathbb\{C\}^\{d\}via a representationρ\\rho\. A dynamical systemf:ℂd→ℂdf:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}is said to be*GG\-equivariant*if

f​\(ρ​\(g\)​x\)=ρ​\(g\)​f​\(x\),∀g∈G,x∈ℂd\.f\(\\rho\(g\)x\)=\\rho\(g\)f\(x\),\\qquad\\forall g\\in G,\\;x\\in\\mathbb\{C\}^\{d\}\.\(4\)For feature\-lifted linear dynamical systemsf​\(x\)=W​Φ​\(x\)∈ℱΦf\(x\)=W\\Phi\(x\)\\in\\mathcal\{F\}\_\{\\Phi\},GG\-equivariance is equivalently enforced by the intertwining condition

ρ​\(g\)​W=W​ρΦ​\(g\),∀g∈G\.\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\),\\qquad\\forall g\\in G\.We denote byℱΦG\\mathcal\{F\}\_\{\\Phi\}^\{G\}the class ofGG\-equivariant feature\-lifted linear dynamical systems with feature mapΦ\\Phi\.

This condition expresses the commutation of the parameter matrixWWwith the group actions on the state and feature spaces, respectively\.

### 3\.3Identifiability from a single trajectory

We now formalize the notion of identifiability\.

###### Definition 3\.7\(Generic identifiability\)\.

Fix a feature mapΦ:ℂd→ℂm\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{m\}, a finite groupGG, and consider the classℱΦG\\mathcal\{F\}\_\{\\Phi\}^\{G\}\. The dynamics within this class are said to be*generically identifiable from trajectories of lengthT∈ℕT\\in\\mathbb\{N\}*if, for almost all initial statesx0∈ℂdx\_\{0\}\\in\\mathbb\{C\}^\{d\}and almost allGG\-equivariant parameter matricesW∈ℂd×mW\\in\\mathbb\{C\}^\{d\\times m\}, the corresponding trajectory

\(x0,x1,…,xT\)∈ℂd×\(T\+1\)\(x\_\{0\},x\_\{1\},\\ldots,x\_\{T\}\)\\in\\mathbb\{C\}^\{d\\times\(T\+1\)\}uniquely determinesWW\. The minimal suchTTis denoted byTΦ​\(G\)T\_\{\\Phi\}\(G\)\.

Here, “generic” is understood in the standard sense: identifiability holds outside a set of measure zero in the space of initial states andGG\-equivariant parameters\. This notion allows us to exclude pathological configurations while retaining full generality\.

When identifiability holds for trajectories of lengthTT, we informally refer toTTas the*sample complexity*of the identification problem, since each transition provides one observation of the dynamics\.

#### Symmetry discovery\.

Consider an unknownGG\-equivariant dynamical systemf:ℂd→ℂdf:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}, where the underlying symmetry groupGGis unknown\. We assume, however, thatGGbelongs to a known class of admissible finite groups𝒢\\mathcal\{G\}\. While the specific groupG∈𝒢G\\in\\mathcal\{G\}is not known a priori, prior knowledge of the class𝒢\\mathcal\{G\}provides structural information that can be leveraged for system identification\.

We are primarily interested in settings where𝒢\\mathcal\{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 ofGGintroduces 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 dynamicsfffrom short trajectories, using only the assumption thatf∈ℱΦf\\in\\mathcal\{F\}\_\{\\Phi\}is equivariant with respect to some unknown groupG∈𝒢G\\in\\mathcal\{G\}\. In the ideal case, the best sample complexity one could hope to achieve is

TΦ​\(𝒢\)≔maxG∈𝒢⁡TΦ​\(G\),T\_\{\\Phi\}\(\\mathcal\{G\}\)\\coloneqq\\max\_\{G\\in\\mathcal\{G\}\}T\_\{\\Phi\}\(G\),corresponding to the worst\-case identifiability threshold over the class𝒢\\mathcal\{G\}\.

A further challenge arises from computational considerations\. Finite groups of interest are often prohibitively large\. For example, the permutation group onnnelements has cardinalityn\!≈exp⁡\(n​log⁡n\)n\!\\approx\\exp\(n\\log 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𝒢\\mathcal\{G\}and an unknown dynamical systemf:ℂd→ℂdf:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}withf∈ℱΦf\\in\\mathcal\{F\}\_\{\\Phi\}that isGG\-equivariant for an unknownG∈𝒢G\\in\\mathcal\{G\}, can one identify the dynamics from trajectories of lengthTΦ​\(𝒢\)T\_\{\\Phi\}\(\\mathcal\{G\}\)with efficient computational runtime?*

We answer this question affirmatively in the next section\.

## 4Main Results

We first characterize the trajectory length required for equivariant system identification when the symmetry groupGGis known, and then turn to adaptive symmetry discovery\.

### 4\.1Sample complexity of equivariant identification

We studyTΦ​\(G\)T\_\{\\Phi\}\(G\), the minimal trajectory length required to generically identify aGG\-equivariant system inℱΦG\\mathcal\{F\}\_\{\\Phi\}^\{G\}, whenGGandΦ\\Phiare known\. We briefly recall the required notation; see Appendix[A](https://arxiv.org/html/2608.08091#A1)\.

#### Irreducible representations\.

LetG^\\widehat\{G\}denote the set of equivalence classes of irreducible representations ofGG\. After a change of basis, the state and feature spaces decompose as

ℂd≅⨁π∈G^ℂnπ⊗Vπ,ℂm≅⨁π∈G^ℂmπ⊗Vπ,\\mathbb\{C\}^\{d\}\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{n\_\{\\pi\}\}\\otimes V\_\{\\pi\},\\qquad\\mathbb\{C\}^\{m\}\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\pi\}\}\\otimes V\_\{\\pi\},wheredπ=dimVπd\_\{\\pi\}=\\dim V\_\{\\pi\}, andnπ,mπ∈ℕn\_\{\\pi\},m\_\{\\pi\}\\in\\mathbb\{N\}denote the multiplicities ofπ\\piin the state and feature representations\. Thusd=∑πnπ​dπd=\\sum\_\{\\pi\}n\_\{\\pi\}d\_\{\\pi\}andm=∑πmπ​dπm=\\sum\_\{\\pi\}m\_\{\\pi\}d\_\{\\pi\}\.

Under this decomposition, everyGG\-equivariant matrixW:ℂm→ℂdW:\\mathbb\{C\}^\{m\}\\to\\mathbb\{C\}^\{d\}decomposes as

W=⨁π∈G^Cπ⊗IVπ,Cπ∈ℂnπ×mπ\.W=\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}C\_\{\\pi\}\\otimes I\_\{V\_\{\\pi\}\},\\qquad C\_\{\\pi\}\\in\\mathbb\{C\}^\{n\_\{\\pi\}\\times m\_\{\\pi\}\}\.Hence identifyingWWreduces to identifyingCπC\_\{\\pi\}for allπ\\piwithnπ\>0n\_\{\\pi\}\>0\.

#### Generic excitation rank\.

The required trajectory length also depends on howΦ\\Phiexcites the different isotypic components\. Theπ\\pi\-isotypic component ofΦ​\(x\)\\Phi\(x\)belongs toℂmπ⊗Vπ\\mathbb\{C\}^\{m\_\{\\pi\}\}\\otimes V\_\{\\pi\}\. Fixing bases\{vi\}i=1mπ\\\{v\_\{i\}\\\}\_\{i=1\}^\{m\_\{\\pi\}\}and\{uj\}j=1dπ\\\{u\_\{j\}\\\}\_\{j=1\}^\{d\_\{\\pi\}\}, we write it as

∑i=1mπ∑j=1dπ\[Φπ​\(x\)\]i​j​vi⊗uj,\\sum\_\{i=1\}^\{m\_\{\\pi\}\}\\sum\_\{j=1\}^\{d\_\{\\pi\}\}\[\\Phi\_\{\\pi\}\(x\)\]\_\{ij\}\\,v\_\{i\}\\otimes u\_\{j\},thereby identifying it withΦπ​\(x\)∈ℂmπ×dπ\\Phi\_\{\\pi\}\(x\)\\in\\mathbb\{C\}^\{m\_\{\\pi\}\\times d\_\{\\pi\}\}\. Thus, the rows index themπm\_\{\\pi\}copies ofπ\\pi, while the columns correspond to coordinates inVπV\_\{\\pi\}\.

For a trajectoryx0,…,xTx\_\{0\},\\ldots,x\_\{T\}, define

𝚽π,T≔\[Φπ​\(x0\),…,Φπ​\(xT−1\)\]∈ℂmπ×T​dπ,\\mathbf\{\\Phi\}\_\{\\pi,T\}\\coloneqq\[\\Phi\_\{\\pi\}\(x\_\{0\}\),\\ldots,\\Phi\_\{\\pi\}\(x\_\{T\-1\}\)\]\\in\\mathbb\{C\}^\{m\_\{\\pi\}\\times Td\_\{\\pi\}\},and lethπ,Φ​\(T\)≔rankgen⁡\(𝚽π,T\)h\_\{\\pi,\\Phi\}\(T\)\\coloneqq\\operatorname\{rank\}\_\{\\mathrm\{gen\}\}\(\\mathbf\{\\Phi\}\_\{\\pi,T\}\), where the generic rank is taken over the initial state and the equivariant parameter matrixWW\.

###### Theorem 4\.1\(Equivariant system identification\)\.

Fix a finite groupGGand an analytic feature mapΦ:ℂd→ℂm\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{m\}with linearly independent coordinates\. ThenW∈ℱΦGW\\in\\mathcal\{F\}\_\{\\Phi\}^\{G\}is generically identifiable fromx0,…,xTx\_\{0\},\\ldots,x\_\{T\}if and only ifhπ,Φ​\(T\)=mπh\_\{\\pi,\\Phi\}\(T\)=m\_\{\\pi\}for everyπ\\piwithnπ\>0n\_\{\\pi\}\>0\. Consequently,

TΦ​\(G\)=maxπ:nπ\>0mπ\>0​inf\{T∈ℕ:hπ,Φ​\(T\)=mπ\},T\_\{\\Phi\}\(G\)=\\max\_\{\\begin\{subarray\}\{c\}\\pi:n\_\{\\pi\}\>0\\\\ m\_\{\\pi\}\>0\\end\{subarray\}\}\\inf\\\{T\\in\\mathbb\{N\}:h\_\{\\pi,\\Phi\}\(T\)=m\_\{\\pi\}\\\},with the infimum interpreted as\+∞\+\\inftyif full rank is never attained\. Irreducible components withmπ=0m\_\{\\pi\}=0contain no unknown parameters and therefore impose no identification requirement\.

Indeed, in eachπ\\pi\-block the observed transitions have the formCπ​Φπ​\(xt\)C\_\{\\pi\}\\Phi\_\{\\pi\}\(x\_\{t\}\)\. Stacking the observations therefore gives a linear system with design matrix𝚽π,T\\mathbf\{\\Phi\}\_\{\\pi,T\}, soCπC\_\{\\pi\}is uniquely determined exactly when𝚽π,T\\mathbf\{\\Phi\}\_\{\\pi,T\}has full row rankmπm\_\{\\pi\}\.

Sincerank⁡\(𝚽π,T\)≤min⁡\{mπ,T​dπ\}\\operatorname\{rank\}\(\\mathbf\{\\Phi\}\_\{\\pi,T\}\)\\leq\\min\\\{m\_\{\\pi\},Td\_\{\\pi\}\\\}, we obtain the universal lower bound

TΦ​\(G\)≥Trep​\(G\)≔maxπ:nπ\>0⁡⌈mπdπ⌉\.T\_\{\\Phi\}\(G\)\\geq T\_\{\\mathrm\{rep\}\}\(G\)\\coloneqq\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\left\\lceil\\frac\{m\_\{\\pi\}\}\{d\_\{\\pi\}\}\\right\\rceil\.This is the smallest trajectory length allowed by dimension counting; whether it is attained depends on the excitation profilehπ,Φ​\(T\)h\_\{\\pi,\\Phi\}\(T\)\.

For the trivial group, there is a single one\-dimensional irrep with multiplicitymm\. Under our assumptions onΦ\\Phi,hπ,Φ​\(T\)=min⁡\{m,T\}h\_\{\\pi,\\Phi\}\(T\)=\\min\\\{m,T\\\}generically, and hence we haveTΦ​\(\{e\}\)=mT\_\{\\Phi\}\(\\\{e\\\}\)=m\.

#### Linear and affine systems\.

For linear systems,Φ​\(x\)=x\\Phi\(x\)=x, somπ=nπm\_\{\\pi\}=n\_\{\\pi\}\. For every finite group,

hπ,Φ​\(T\)=min⁡\{nπ,T​dπ\},Tlin​\(G\)=maxπ:nπ\>0⁡⌈nπdπ⌉\.h\_\{\\pi,\\Phi\}\(T\)=\\min\\\{n\_\{\\pi\},Td\_\{\\pi\}\\\},\\quad T\_\{\\mathrm\{lin\}\}\(G\)=\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\left\\lceil\\frac\{n\_\{\\pi\}\}\{d\_\{\\pi\}\}\\right\\rceil\.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\.

SupposeGGis finite Abelian andΦ\\Phiis analytic, has linearly independent coordinates, and contains the state coordinates, i\.e\., there isL∈ℂd×mL\\in\\mathbb\{C\}^\{d\\times m\}such thatL​Φ​\(x\)=xL\\Phi\(x\)=x\. Since every irreducible complex representation ofGGis one\-dimensional,dπ=1d\_\{\\pi\}=1for allπ∈G^\\pi\\in\\widehat\{G\}\. In this case,hπ,Φ​\(T\)=min⁡\{mπ,T\}h\_\{\\pi,\\Phi\}\(T\)=\\min\\\{m\_\{\\pi\},T\\\}and

TΦ​\(G\)=maxπ:nπ\>0⁡mπ=Trep​\(G\)\.T\_\{\\Phi\}\(G\)=\\max\_\{\\pi:n\_\{\\pi\}\>0\}m\_\{\\pi\}=T\_\{\\mathrm\{rep\}\}\(G\)\.In particular, this result holds for the full polynomial feature mapsΦ≤k\\Phi\_\{\\leq k\}\.

#### Permutation\-equivariant polynomial systems\.

LetGGbe a subgroup of the symmetric groupSdS\_\{d\}, acting by coordinate permutations, and letΦ=Φ≤k\\Phi=\\Phi\_\{\\leq k\}contain all monomials of total degree at mostkk, withk≥2k\\geq 2\. Then, we show

TΦ≤k​\(G\)≤maxπ:nπ\>0⁡mπ\.T\_\{\\Phi\_\{\\leq k\}\}\(G\)\\leq\\max\_\{\\pi:n\_\{\\pi\}\>0\}m\_\{\\pi\}\.Thus the trajectory length is controlled by the largest active representation multiplicity rather than by the ambient feature dimensionm=∑πmπ​dπm=\\sum\_\{\\pi\}m\_\{\\pi\}d\_\{\\pi\}\.

###### Example 4\.2\(Quadratic systems with permutation symmetry\)\.

ConsiderΦ=Φ≤2\\Phi=\\Phi\_\{\\leq 2\}under the standardSdS\_\{d\}\-action, whered≥4d\\geq 4\. LetViV\_\{i\}denote the space of homogeneous polynomials of degreeii\. Then𝒫≤2=V0⊕V1⊕V2\\mathcal\{P\}\_\{\\leq 2\}=V\_\{0\}\\oplus V\_\{1\}\\oplus V\_\{2\}, withV0=π0V\_\{0\}=\\pi\_\{0\},V1=π0⊕πstdV\_\{1\}=\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}, andV2=2​π0⊕2​πstd⊕π\(d−2,2\)V\_\{2\}=2\\pi\_\{0\}\\oplus 2\\pi\_\{\\mathrm\{std\}\}\\oplus\\pi\_\{\(d\-2,2\)\}\. Hereπ0\\pi\_\{0\}is the trivial representation,dπstd=d−1d\_\{\\pi\_\{\\mathrm\{std\}\}\}=d\-1, anddπ\(d−2,2\)=d​\(d−3\)/2d\_\{\\pi\_\{\(d\-2,2\)\}\}=d\(d\-3\)/2\. Hencemπ0=4m\_\{\\pi\_\{0\}\}=4,mπstd=3m\_\{\\pi\_\{\\mathrm\{std\}\}\}=3, andmπ\(d−2,2\)=1m\_\{\\pi\_\{\(d\-2,2\)\}\}=1\.

The state representation isℂd≅π0⊕πstd\\mathbb\{C\}^\{d\}\\cong\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}, so only the trivial and standard blocks are relevant\. Their excitation ranks satisfyhπ0,Φ​\(T\)=min⁡\{4,T\}h\_\{\\pi\_\{0\},\\Phi\}\(T\)=\\min\\\{4,T\\\}andhπstd,Φ​\(T\)=min⁡\{3,2​T\}h\_\{\\pi\_\{\\mathrm\{std\}\},\\Phi\}\(T\)=\\min\\\{3,2T\\\}, yielding

TΦ≤2​\(Sd\)=4\.T\_\{\\Phi\_\{\\leq 2\}\}\(S\_\{d\}\)=4\.By contrast,m=\(d\+22\)=Θ​\(d2\)m=\\binom\{d\+2\}\{2\}=\\Theta\(d^\{2\}\)\. Thus permutation equivariance reduces the generic trajectory length fromΘ​\(d2\)\\Theta\(d^\{2\}\)to a constant independent ofdd\.

#### Representation stability\.

The preceding phenomenon extends to any fixed polynomial degree\. Under the standard permutation action ofSdS\_\{d\}, the state representation decomposes as

ℂd≅π0⊕πstd,\\mathbb\{C\}^\{d\}\\cong\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{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 fixedkk, the multiplicities of these two representations inΦ≤k\\Phi\_\{\\leq k\}stabilize stabilize onced≥k\+1d\\geq k\+1\. In particular, forddsufficiently large,

mπ0=∑r=0kp​\(r\),mπstd=∑j=0k−1\(k−j\)​p​\(j\),m\_\{\\pi\_\{0\}\}=\\sum\_\{r=0\}^\{k\}p\(r\),\\qquad m\_\{\\pi\_\{\\mathrm\{std\}\}\}=\\sum\_\{j=0\}^\{k\-1\}\(k\-j\)p\(j\),wherep​\(r\)p\(r\)denotes the integer partition function\. Defining

Mk≔max⁡\{mπ0,mπstd\},M\_\{k\}\\coloneqq\\max\\\{m\_\{\\pi\_\{0\}\},m\_\{\\pi\_\{\\mathrm\{std\}\}\}\\\},the preceding polynomial identification bound givesTΦ≤k​\(Sd\)≤MkT\_\{\\Phi\_\{\\leq k\}\}\(S\_\{d\}\)\\leq M\_\{k\}\. Hence, for every fixedk≥2k\\geq 2,

TΦ≤k​\(Sd\)=Ok​\(1\),dim\(Φ≤k\)=\(d\+kk\)=Θk​\(dk\)\.T\_\{\\Phi\_\{\\leq k\}\}\(S\_\{d\}\)=O\_\{k\}\(1\),\\quad\\dim\(\\Phi\_\{\\leq k\}\)=\\binom\{d\+k\}\{k\}=\\Theta\_\{k\}\(d^\{k\}\)\.Thus, fixed\-degree permutation\-equivariant polynomial systems are generically identifiable from trajectories whose length remains bounded independently of the state dimensiondd\.

### 4\.2Adaptive symmetry discovery

We now consider system identification when the underlying symmetry is unknown\. LetΓ\\Gammabe a finite ambient group of transformations, and let𝒢\\mathcal\{G\}be a finite family of candidate subgroups ofΓ\\Gamma\. We assume thatΓ\\Gammaacts on the state and feature spaces through compatible representationsρ\\rhoandρΦ\\rho\_\{\\Phi\}, with the actions of each candidate group obtained by restriction\. We further assume that the full symmetry group of the unknown dynamics withinΓ\\Gammabelongs to𝒢\\mathcal\{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 subsetS⊆GS\\subseteq Gis called a*generating set*of a finite groupGGif every element ofGGcan be obtained through finitely many compositions of elements ofSSand their inverses\. Equivalently, everyg∈Gg\\in Gcan be written asg=s1ϵ1​⋯​srϵrg=s\_\{1\}^\{\\epsilon\_\{1\}\}\\cdots s\_\{r\}^\{\\epsilon\_\{r\}\}, wheresi∈Ss\_\{i\}\\in Sandϵi∈\{−1,1\}\\epsilon\_\{i\}\\in\\\{\-1,1\\\}\. In this case, we writeG=⟨S⟩G=\\langle S\\rangle\.

Generating sets are closely connected to Cayley graphs\. GivenS⊆GS\\subseteq G, the Cayley graphCay⁡\(G,S\)\\operatorname\{Cay\}\(G,S\)has vertex setGG, with edges corresponding to composition by elements ofSSand their inverses\. This graph is connected if and only ifSSgeneratesGG\. The classical Alon–Roichman theorem\(Alon and Roichman,[1994](https://arxiv.org/html/2608.08091#bib.bib55)\)establishes the substantially stronger fact thatO​\(log⁡\|G\|\)O\(\\log\|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 least1/21/2\. Whenever this occurs, the size of the generated subgroup at least doubles\. Let

\|G\|max≔maxH∈𝒢⁡\|H\|\|G\|\_\{\\max\}\\coloneqq\\max\_\{H\\in\\mathcal\{G\}\}\|H\|and define

N𝒢,δ≔⌈8​\(⌈log2⁡\|G\|max⌉\+log⁡\|𝒢\|δ\)⌉\.N\_\{\\mathcal\{G\},\\delta\}\\coloneqq\\left\\lceil 8\\left\(\\left\\lceil\\log\_\{2\}\|G\|\_\{\\max\}\\right\\rceil\+\\log\\frac\{\|\\mathcal\{G\}\|\}\{\\delta\}\\right\)\\right\\rceil\.ThenN𝒢,δN\_\{\\mathcal\{G\},\\delta\}i\.i\.d\. uniform samples from each candidate group generate all groups in𝒢\\mathcal\{G\}simultaneously with probability at least1−δ1\-\\delta\. 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\_\{\\Phi\}\(\\mathcal\{G\}\)\\coloneqq\\max\_\{G\\in\\mathcal\{G\}\}T\_\{\\Phi\}\(G\)\.We call𝒢\\mathcal\{G\}*generically separating*if, for everyG∈𝒢G\\in\\mathcal\{G\}, a genericGG\-equivariant system whose full symmetry group withinΓ\\GammaisGG, together with a generic initial state, has the following property: for everyT≥TΦ​\(𝒢\)T\\geq T\_\{\\Phi\}\(\\mathcal\{G\}\), if a candidateH∈𝒢H\\in\\mathcal\{G\}admits anHH\-equivariant system consistent with the observed trajectory, thenHHis a subgroup ofGG\.

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 aGG\-equivariant system is automatically equivariant with respect to every subgroup ofGG\.

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\. OnceT≥TΦ​\(G\)T\\geq T\_\{\\Phi\}\(G\), uniqueness within theGG\-equivariant class forces such a system to coincide with the true dynamics, contradicting the assumption thatGGis its full symmetry group\.

We are now ready to state the adaptive identification procedure\.

Algorithm 1Adaptive symmetry discovery1:Input:trajectory

\(x0,…,xT\)\(x\_\{0\},\\ldots,x\_\{T\}\), feature map

Φ\\Phi, candidate family

𝒢\\mathcal\{G\}, failure probability

δ\\delta
2:Output:parameter matrix

WWand generators

SSof the discovered symmetry group

3:Form

X←\[Φ​\(x0\),…,Φ​\(xT−1\)\]X\\leftarrow\[\\Phi\(x\_\{0\}\),\\ldots,\\Phi\(x\_\{T\-1\}\)\]and

Y←\[x1,…,xT\]Y\\leftarrow\[x\_\{1\},\\ldots,x\_\{T\}\]
4:Set

N←N𝒢,δN\\leftarrow N\_\{\\mathcal\{G\},\\delta\}and

𝒞←∅\\mathcal\{C\}\\leftarrow\\varnothing
5:foreach

G∈𝒢G\\in\\mathcal\{G\}do

6:Sample

SG=\{g1,…,gN\}S\_\{G\}=\\\{g\_\{1\},\\ldots,g\_\{N\}\\\}, where

gi​∼i\.i\.d\.​Unif⁡\(G\)g\_\{i\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\operatorname\{Unif\}\(G\)
7:Test feasibility of

W​X=Y,ρ​\(g\)​W=W​ρΦ​\(g\)for all​g∈SGWX=Y,\\qquad\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\)\\quad\\text\{for all \}g\\in S\_\{G\}
8:iffeasiblethen

9:Store

\(G,SG,WG\)\(G,S\_\{G\},W\_\{G\}\)in

𝒞\\mathcal\{C\}, where

WGW\_\{G\}is any feasible solution

10:endif

11:endfor

12:Choose a candidate

GGof maximum cardinality in

𝒞\\mathcal\{C\}
13:return

WG,SGW\_\{G\},S\_\{G\}

###### Theorem 4\.5\(Adaptive symmetry discovery\)\.

Let𝒢\\mathcal\{G\}be a generically separating family of finite candidate groups, and suppose that the full symmetry groupGGof an unknown systemf​\(x\)=W​Φ​\(x\)f\(x\)=W\\Phi\(x\)belongs to𝒢\\mathcal\{G\}\. Suppose the trajectory is generated from a generic initial state by a genericGG\-equivariant system\. Then, provided that

T≥TΦ​\(𝒢\)=maxH∈𝒢⁡TΦ​\(H\),T\\geq T\_\{\\Phi\}\(\\mathcal\{G\}\)=\\max\_\{H\\in\\mathcal\{G\}\}T\_\{\\Phi\}\(H\),Algorithm[1](https://arxiv.org/html/2608.08091#alg1)recovers the unknown dynamics and a generating set of its full symmetry group with probability at least1−δ1\-\\delta\. Assuming uniform sampling and representation evaluation can be performed efficiently for each candidate group, the runtime is polynomial ind,m,T,\|𝒢\|,log⁡\|G\|maxd,m,T,\|\\mathcal\{G\}\|,\\log\|G\|\_\{\\max\}, andlog⁡\(1/δ\)\\log\(1/\\delta\)\.

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 usingO​\(log⁡\|G\|\)O\(\\log\|G\|\)samples, while our identification procedure only requires connectivity, or equivalently generation\.

#### 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Γ\\Gammabe a finite group and define

ℋB:=\{H≤Γ:\[Γ:H\]≤B\}\.\\mathcal\{H\}\_\{B\}:=\\\{H\\leq\\Gamma:\[\\Gamma:H\]\\leq B\\\}\.We assume that the full symmetry groupHHof the unknown dynamics belongs toℋB\\mathcal\{H\}\_\{B\}, but we do not require an enumeration ofℋB\\mathcal\{H\}\_\{B\}\.

The key observation is that a uniformly sampled element ofΓ\\Gammabelongs toHHwith probability

ℙg∼Unif⁡\(Γ\)​\(g∈H\)=\|H\|\|Γ\|=1\[Γ:H\]≥1B\.\\mathbb\{P\}\_\{g\\sim\\operatorname\{Unif\}\(\\Gamma\)\}\(g\\in H\)=\\frac\{\|H\|\}\{\|\\Gamma\|\}=\\frac\{1\}\{\[\\Gamma:H\]\}\\geq\\frac\{1\}\{B\}\.Hence, if membership in the unknown symmetry group can be determined from the observed trajectory, sampling fromΓ\\Gammaprovides uniform samples fromHHwithout explicitly searching over the candidate subgroups\.

To formalize this, we assume*generic elementwise separation*: for a generic system with full symmetry groupHH, a generic initial state, and the trajectory length under consideration, a sampledg∈Γg\\in\\Gammasatisfiesg∈Hg\\in Hif and only if there existsW~\\widetilde\{W\}such that

W~​X=Y,ρ​\(g\)​W~=W~​ρΦ​\(g\)\.\\widetilde\{W\}X=Y,\\qquad\\rho\(g\)\\widetilde\{W\}=\\widetilde\{W\}\\rho\_\{\\Phi\}\(g\)\.The reverse implication is automatic forg∈Hg\\in H, since the true parameter matrixWWsatisfies both constraints\.

Therefore, we may sampleg∼Unif⁡\(Γ\)g\\sim\\operatorname\{Unif\}\(\\Gamma\), retain it whenever the above feasibility test succeeds, and repeat\. Conditioned on acceptance, the retained elements are i\.i\.d\. uniform samples fromHH\. Since the acceptance probability is at least1/B1/B, obtainingNNaccepted elements requires at mostB​NBNambient samples in expectation\.

This again admits a Cayley\-graph interpretation\. The accepted elements define a random Cayley graph of the unknown groupHH\. ThusO​\(log⁡\|H\|\)O\(\\log\|H\|\)accepted elements suffice to generateHHwith high probability, while the Alon–Roichman theorem gives the stronger expansion guarantee\.

Define

NΓ,δ:=⌈8​\(⌈log2⁡\|Γ\|⌉\+log⁡1δ\)⌉\.N\_\{\\Gamma,\\delta\}:=\\left\\lceil 8\\left\(\\left\\lceil\\log\_\{2\}\|\\Gamma\|\\right\\rceil\+\\log\\frac\{1\}\{\\delta\}\\right\)\\right\\rceil\.
Algorithm 2Discovery of a bounded\-index symmetry group1:Input:trajectory

\(x0,…,xT\)\(x\_\{0\},\\ldots,x\_\{T\}\), feature map

Φ\\Phi, ambient group

Γ\\Gamma, index bound

BB, failure probability

δ\\delta
2:Output:parameter matrix

WWand generators

SSof the discovered subgroup

3:Form

X←\[Φ​\(x0\),…,Φ​\(xT−1\)\]X\\leftarrow\[\\Phi\(x\_\{0\}\),\\ldots,\\Phi\(x\_\{T\-1\}\)\]and

Y←\[x1,…,xT\]Y\\leftarrow\[x\_\{1\},\\ldots,x\_\{T\}\]
4:Set

N←NΓ,δN\\leftarrow N\_\{\\Gamma,\\delta\}and

S←∅S\\leftarrow\\varnothing
5:while

\|S\|<N\|S\|<Ndo

6:Sample

g∼Unif⁡\(Γ\)g\\sim\\operatorname\{Unif\}\(\\Gamma\)
7:Test feasibility of

W~​X=Y,ρ​\(g\)​W~=W~​ρΦ​\(g\)\\widetilde\{W\}X=Y,\\qquad\\rho\(g\)\\widetilde\{W\}=\\widetilde\{W\}\\rho\_\{\\Phi\}\(g\)
8:iffeasiblethen

9:Add

ggto

SS
10:endif

11:endwhile

12:Solve

W​X=Y,ρ​\(g\)​W=W​ρΦ​\(g\)for all​g∈SWX=Y,\\qquad\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\)\\quad\\text\{for all \}g\\in S
13:return

W,SW,S

###### Theorem 4\.11\(Bounded\-index subgroup discovery\)\.

Suppose the full symmetry groupHHof the unknown dynamics satisfies\[Γ:H\]≤B\[\\Gamma:H\]\\leq B, and suppose generic elementwise separation holds for

T≥TΦ​\(ℋB\):=maxH≤Γ\[Γ:H\]≤B⁡TΦ​\(H\)\.T\\geq T\_\{\\Phi\}\(\\mathcal\{H\}\_\{B\}\):=\\max\_\{\\begin\{subarray\}\{c\}H\\leq\\Gamma\\\\ \[\\Gamma:H\]\\leq B\\end\{subarray\}\}T\_\{\\Phi\}\(H\)\.Then Algorithm[2](https://arxiv.org/html/2608.08091#alg2)recovers the unknown dynamics and a generating set ofHHwith probability at least1−δ1\-\\delta\.

The algorithm does not enumerate the subgroups inℋB\\mathcal\{H\}\_\{B\}\. The expected number of ambient samples and feasibility tests is

O​\(B​\(log⁡\|Γ\|\+log⁡1δ\)\),O\\left\(B\\left\(\\log\|\\Gamma\|\+\\log\\frac\{1\}\{\\delta\}\\right\)\\right\),and is therefore independent of\|ℋB\|\|\\mathcal\{H\}\_\{B\}\|\. Assuming efficient sampling fromΓ\\Gamma, representation evaluation, and linear feasibility testing, the expected runtime is polynomial ind,m,T,B,log⁡\|Γ\|d,m,T,B,\\log\|\\Gamma\|, andlog⁡\(1/δ\)\\log\(1/\\delta\)\. In particular, whenB=O​\(1\)B=O\(1\), the sampling overhead is logarithmic in\|Γ\|\|\\Gamma\|\.

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 factorBB, and is constant whenB=O​\(1\)B=O\(1\)\.

## 5Conclusion 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\(Hazanet al\.,[2025](https://arxiv.org/html/2608.08091#bib.bib106)\)\. 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 & Algorithms5\(2\),pp\. 271–284\.Cited by:[§A\.2](https://arxiv.org/html/2608.08091#A1.SS2.SSS0.Px1.p3.3),[§4\.2](https://arxiv.org/html/2608.08091#S4.SS2.p3.7)\.
- M\. Atzmon, K\. Nagano, S\. Fidler, S\. Khamis, and Y\. Lipman \(2022\)Frame averaging for equivariant shape space learning\.InIEEE Conference on Computer Vision and Pattern Recognition \(CVPR\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- M\. Bhat, J\. Park, J\. Yang, N\. Dehmamy, R\. Walters, and R\. Yu \(2025\)AtlasD: automatic local symmetry discovery\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- 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](https://arxiv.org/html/2608.08091#S1.p4.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 sciences113\(15\),pp\. 3932–3937\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p2.1),[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p6.1)\.
- 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 Technology6\(2\),pp\. 025058\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p6.1)\.
- J\. Carruth, M\. F\. Eggl, C\. Fefferman, C\. W\. Rowley, and M\. Weber \(2022\)Controlling unknown linear dynamics with bounded multiplicative regret\.Revista Matematica Iberoamericana38\(7\),pp\. 2185–2216\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- N\. Dehmamy, R\. Walters, Y\. Liu, D\. Wang, and R\. Yu \(2021\)Automatic symmetry discovery with lie algebra convolutional network\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- K\. Desai, B\. Nachman, and J\. Thaler \(2022\)Symmetry discovery with deep learning\.Physical Review D105\(9\),pp\. 096031\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- 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 Iberoamericana38\(1\),pp\. 175–187\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- D\. Foster, T\. Sarkar, and A\. Rakhlin \(2020\)Learning nonlinear dynamical systems from a single trajectory\.InLearning for Dynamics and Control,Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- W\. Fulton and J\. Harris \(2013\)Representation theory: a first course\.Vol\.129,Springer Science & Business Media\.Cited by:[Appendix A](https://arxiv.org/html/2608.08091#A1.p1.1)\.
- A\. Gabel, R\. Quax, and E\. Gavves \(2024\)Data\-driven lie point symmetry detection for continuous dynamical systems\.Machine Learning: Science and Technology5\(1\),pp\. 015037\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p6.1)\.
- 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](https://arxiv.org/html/2608.08091#S5.p2.1)\.
- L\. Hu, Y\. Li, and Z\. Lin \(2025a\)Explicit discovery of nonlinear symmetries from dynamic data\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- L\. Hu, Y\. Li, and Z\. Lin \(2025c\)Symmetry discovery for different data types\.Neural Networks,pp\. 107481\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- D\. Huh \(2025\)Discovering group structures via unitary representation learning\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- R\. Isermann and M\. Münchhof \(2011\)Identification of dynamic systems: an introduction with applications\.Vol\.85,Springer\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p3.1),[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- S\. Kaba, A\. K\. Mondal, Y\. Zhang, Y\. Bengio, and S\. Ravanbakhsh \(2023\)Equivariance with learned canonicalization functions\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- P\. Karjol, V\. V\. Kashyap, R\. Kashyap,et al\.\(2025\)Learning equivariant functions via quadratic forms\.arXiv preprint arXiv:2509\.22184\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- G\. Ko, H\. Kim, and J\. Lee \(2024\)Learning infinitesimal generators of continuous symmetries from data\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- H\. Li, C\. Xiao, M\. Guo, and Y\. Weng \(2025\)Latent mixture of symmetries for sample\-efficient dynamic learning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p6.1)\.
- Y\. Lin, J\. Helwig, S\. Gui, and S\. Ji \(2024\)Equivariance via minimal frame averaging for more symmetries and efficiency\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- 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 Research26\(248\),pp\. 1–83\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- 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 Research26\(145\),pp\. 1–70\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- 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\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- D\. W\. Romero and S\. Lohit \(2022\)Learning partial equivariances from data\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- E\. Santos\-Escriche and S\. Jegelka \(2025\)Learning equivariant models by discovering symmetries with learnable augmentations\.arXiv preprint arXiv:2506\.03914\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- T\. Sarkar, A\. Rakhlin, and M\. A\. Dahleh \(2021\)Finite time LTI system identification\.Journal of Machine Learning Research22\(26\),pp\. 1–61\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- T\. Sarkar and A\. Rakhlin \(2019\)Near optimal finite time identification of arbitrary linear dynamical systems\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- J\. Serreet al\.\(1977\)Linear representations of finite groups\.Vol\.42,Springer\.Cited by:[Appendix A](https://arxiv.org/html/2608.08091#A1.p1.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- B\. Shaw, A\. Magner, and K\. Moon \(2024\)Symmetry discovery beyond affine transformations\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- 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\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- M\. Simchowitz, H\. Mania, S\. Tu, M\. I\. Jordan, and B\. Recht \(2018\)Learning without mixing: towards a sharp analysis of linear system identification\.InConference on Learning Theory \(COLT\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- 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](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- A\. Soleymani, B\. Tahmasebi, P\. Jaillet, and S\. Jegelka \(2025a\)From finite to infinite groups: a polynomial\-time algorithm for learning with exact invariances\.InNeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations,Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. Jaillet \(2025b\)A robust kernel statistical test of invariance: detecting subtle asymmetries\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- A\. Soleymani, B\. Tahmasebi, S\. Jegelka, and P\. Jaillet \(2025c\)Learning with exact invariances in polynomial time\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- B\. Tahmasebi and S\. Jegelka \(2023\)The exact sample complexity gain from invariances for kernel regression\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p3.1)\.
- B\. Tahmasebi and S\. Jegelka \(2024\)Sample complexity bounds for estimating probability divergences under invariances\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p3.1)\.
- B\. Tahmasebi and S\. Jegelka \(2025a\)Generalization bounds for canonicalization: a comparative study with group averaging\.InInt\. Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- B\. Tahmasebi and S\. Jegelka \(2025b\)Regularity in canonicalized models: a theoretical perspective\.InInt\. Conference on Artificial Intelligence and Statistics \(AISTATS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- B\. Tahmasebi, M\. Weber, and S\. Jegelka \(2025\)Data augmentation: a Fourier analysis perspective\.InNeurIPS 2025 Workshop on Symmetry and Geometry in Neural Representations,Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- B\. Tahmasebi and M\. Weber \(2025\)Achieving approximate symmetry is exponentially easier than exact symmetry\.arXiv preprint arXiv:2512\.11855\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p7.1)\.
- S\. Tu, R\. Frostig, and M\. Soltanolkotabi \(2024\)Learning from many trajectories\.Journal of Machine Learning Research25\(216\),pp\. 1–109\.Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p2.1)\.
- T\. van der Ouderaa, A\. Immer, and M\. van der Wilk \(2023\)Learning layer\-wise equivariances automatically using gradients\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- P\. Van Overschee and B\. De Moor \(2012\)Subspace identification for linear systems: theory—implementation—applications\.Springer Science & Business Media\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p3.1),[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- R\. Wang and R\. Yu \(2025\)Physics\-guided deep learning for dynamical systems: a survey\.ACM Computing Surveys58\(5\),pp\. 1–31\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p2.1),[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- M\. Weber \(2025\)Geometric machine learning\.Wiley Online Library\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p4.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](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- J\. Yang, N\. Dehmamy, R\. Walters, and R\. Yu \(2024a\)Latent space symmetry discovery\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- J\. Yang, W\. Rao, N\. Dehmamy, R\. Walters, and R\. Yu \(2024b\)Symmetry\-informed governing equation discovery\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p5.1)\.
- J\. Yang, R\. Walters, N\. Dehmamy, and R\. Yu \(2023\)Generative adversarial symmetry discovery\.InInt\. Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p4.1)\.
- R\. Yu and R\. Wang \(2024\)Learning dynamical systems from data: an introduction to physics\-guided deep learning\.Proceedings of the National Academy of Sciences121\(27\),pp\. e2311808121\.Cited by:[§1](https://arxiv.org/html/2608.08091#S1.p2.1),[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.
- I\. M\. Ziemann, H\. Sandberg, and N\. Matni \(2022\)Single trajectory nonparametric learning of nonlinear dynamics\.InConference on Learning Theory \(COLT\),Cited by:[§2](https://arxiv.org/html/2608.08091#S2.p1.1)\.

## Appendix APreliminaries

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](https://arxiv.org/html/2608.08091#bib.bib64); Fulton and Harris,[2013](https://arxiv.org/html/2608.08091#bib.bib61)\)\.

### A\.1Groups, representations, and equivariance

#### Groups\.

A \(finite\) groupGGis a finite set equipped with a binary operation⋅:G×G→G\\cdot:G\\times G\\to Gsatisfying the following properties:

- •Associativity:\(g⋅h\)⋅s=g⋅\(h⋅s\)\(g\\cdot h\)\\cdot s=g\\cdot\(h\\cdot s\)for allg,h,s∈Gg,h,s\\in G\.
- •Identity:There exists an elemente∈Ge\\in Gsuch thate⋅g=g⋅e=ge\\cdot g=g\\cdot e=gfor allg∈Gg\\in G\.
- •Inverses:For everyg∈Gg\\in G, there existsg−1∈Gg^\{\-1\}\\in Gsuch thatg⋅g−1=g−1⋅g=eg\\cdot g^\{\-1\}=g^\{\-1\}\\cdot g=e\.

The cardinality of a finite groupGGis denoted by\|G\|\|G\|\. For convenience, we drop the dot notation and writeg​hghinstead ofg⋅hg\\cdot hfor allg,h∈Gg,h\\in G\.

#### Examples of finite groups\.

Here is a few examples of finite groups:

- •The cyclic group of integers modulonnunder addition, denoted byℤ/n​ℤ\\mathbb\{Z\}/n\\mathbb\{Z\}\.
- •The permutation group \(also known as symmetric group\) of group of all permutations ofnnelements\.
- •Direct products of commutative groups, such as group of sign inversions\{±1\}d\\\{\\pm 1\\\}^\{d\}
- •Dihedral group, consisting of symmetries of a regular polygon withnnsides in dimension two \(reflections, rotations\)\.

#### Group actions and linear representations\.

LetVVbe a vector space overℂ\\mathbb\{C\}\. A \(left\)*action*of a finite groupGGonVVis a map

θ:G×V→V\\theta:G\\times V\\to Vsatisfying

θ​\(e,v\)=v,θ​\(g​h,v\)=θ​\(g,θ​\(h,v\)\)for all​g,h∈G,v∈V\.\\theta\(e,v\)=v,\\qquad\\theta\(gh,v\)=\\theta\(g,\\theta\(h,v\)\)\\quad\\text\{for all \}g,h\\in G,\\ v\\in V\.Whenθ​\(g,⋅\)\\theta\(g,\\cdot\)is linear and invertible for everyg∈Gg\\in G, the action is equivalently described by a group homomorphism

ρ:G→GL​\(V\),\\rho:G\\to\\mathrm\{GL\}\(V\),whereρ​\(g\)​v:=θ​\(g,v\)\\rho\(g\)v:=\\theta\(g,v\)\. In this case,\(V,ρ\)\(V,\\rho\)is called a*linear representation*ofGG\. Note that here eachρ​\(g\)∈ℂn×n\\rho\(g\)\\in\\mathbb\{C\}^\{n\\times n\}is an invertible matrix, withn=dim\(V\)n=\\dim\(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,\\rho\)ofGGis said to be*irreducible*if it has no nontrivialGG\-invariant subspaces, i\.e\., the only subspacesW⊆VW\\subseteq Vsatisfyingρ​\(g\)​W⊆W\\rho\(g\)W\\subseteq Wfor allg∈Gg\\in Gare\{0\}\\\{0\\\}andVVitself\.

A fundamental result in finite group representation theory is*Maschke’s theorem*, which states that every finite\-dimensional representation of a finite group overℂ\\mathbb\{C\}is completely reducible\. That is, any representationVVadmits a decomposition of the form

V≅⨁π∈G^ℂnπ⊗Vπ,V\\;\\cong\\;\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{n\_\{\\pi\}\}\\otimes V\_\{\\pi\},where:

- •G^\\widehat\{G\}denotes the set of inequivalent irreducible representations ofGG,
- •VπV\_\{\\pi\}is a representative irreducible representation of dimensiondπ∈ℕd\_\{\\pi\}\\in\\mathbb\{N\},
- •nπ∈ℤ≥0n\_\{\\pi\}\\in\\mathbb\{Z\}\_\{\\geq 0\}is the multiplicity ofπ\\piinVV\.

The dimensions satisfy

∑π∈G^nπ​dπ=n\.\\sum\_\{\\pi\\in\\widehat\{G\}\}n\_\{\\pi\}d\_\{\\pi\}=n\.
Moreover, for finite groups, the number of irreducible representations is finite, thus\|G^\|<∞\|\\widehat\{G\}\|<\\infty, and their dimensions obey the following identity

∑π∈G^dπ2=\|G\|,\\sum\_\{\\pi\\in\\widehat\{G\}\}d\_\{\\pi\}^\{2\}=\|G\|,with eachdπd\_\{\\pi\}dividing\|G\|\|G\|\.

#### Unitary representations and change of basis\.

For finite groups, every finite\-dimensional representation overℂ\\mathbb\{C\}is equivalent to a unitary representation\. In particular, after an appropriate change of basis, we may assume without loss of generality thatρ​\(g\)\\rho\(g\)andρΦ​\(g\)\\rho\_\{\\Phi\}\(g\)are unitary for allg∈Gg\\in 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 ofVVunder which the representationρ\\rhotakes a block\-diagonal form

ρ​\(g\)=⨁π∈G^\(Inπ⊗π​\(g\)\),∀g∈G,\\rho\(g\)\\;=\\;\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\left\(I\_\{n\_\{\\pi\}\}\\otimes\\pi\(g\)\\right\),\\qquad\\forall g\\in G,where eachπ​\(g\)∈ℂdπ×dπ\\pi\(g\)\\in\\mathbb\{C\}^\{d\_\{\\pi\}\\times d\_\{\\pi\}\}is an irreducible representation andInπI\_\{n\_\{\\pi\}\}denotes the identity matrix of sizenπn\_\{\\pi\}\. We use the notation

ρ≅⨁π∈G^nπ​π\\rho\\;\\cong\\;\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}n\_\{\\pi\}\\,\\pito denote the decomposition ofρ\\rhointo irreducible representations, wherenπn\_\{\\pi\}denotes the multiplicity ofπ\\pi\.

#### Equivariant linear maps\.

Let\(V,ρV\)\(V,\\rho\_\{V\}\)and\(U,ρU\)\(U,\\rho\_\{U\}\)be two representations ofGG\. A linear mapψ:V→U\\psi:V\\to Uis called*GG\-equivariant*if

ψ∘ρV​\(g\)=ρU​\(g\)∘ψfor all​g∈G\.\\psi\\circ\\rho\_\{V\}\(g\)=\\rho\_\{U\}\(g\)\\circ\\psi\\quad\\text\{for all \}g\\in G\.The space of equivariant linear maps betweenVVandUUis denoted byHomG​\(V,U\)\\mathrm\{Hom\}\_\{G\}\(V,U\)\.

Using the decomposition into irreducible representations, the structure ofHomG​\(V,U\)\\mathrm\{Hom\}\_\{G\}\(V,U\)can be characterized explicitly in terms of multiplicities\. In particular, if

V≅⨁π∈G^ℂnπ⊗Vπ,U≅⨁π∈G^ℂmπ⊗Vπ,V\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{n\_\{\\pi\}\}\\otimes V\_\{\\pi\},\\qquad U\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\pi\}\}\\otimes V\_\{\\pi\},then

HomG​\(V,U\)≅⨁π∈G^ℂmπ×nπ,\\mathrm\{Hom\}\_\{G\}\(V,U\)\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\pi\}\\times n\_\{\\pi\}\},and in particular,

dim\(HomG​\(V,U\)\)=∑π∈G^mπ​nπ\.\\dim\(\\mathrm\{Hom\}\_\{G\}\(V,U\)\)=\\sum\_\{\\pi\\in\\widehat\{G\}\}m\_\{\\pi\}n\_\{\\pi\}\.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 matricesW∈ℝd×mW\\in\\mathbb\{R\}^\{d\\times m\}that satisfy the equivariance condition in our proofs\.

#### Polynomial feature lifting\.

Fix a degree parameterk∈ℕk\\in\\mathbb\{N\}\. Let

Φ:ℂd→ℂm\\Phi:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{m\}denote the polynomial feature map consisting of all monomials inddvariables of total degree at mostkk\. Explicitly, forx=\(x1,…,xd\)⊤∈ℂdx=\(x^\{1\},\\dots,x^\{d\}\)^\{\\top\}\\in\\mathbb\{C\}^\{d\},

Φ​\(x\)=\(\(x1\)α1​\(x2\)α2​⋯​\(xd\)αd\)α∈ℐk,ℐk=\{α∈ℤ≥0d\|∑i=1dαi≤k\}\.\\Phi\(x\)\\;=\\;\\Bigl\(\(x^\{1\}\)^\{\\alpha\_\{1\}\}\(x^\{2\}\)^\{\\alpha\_\{2\}\}\\cdots\(x^\{d\}\)^\{\\alpha\_\{d\}\}\\Bigr\)\_\{\\alpha\\in\\mathcal\{I\}\_\{k\}\},\\qquad\\mathcal\{I\}\_\{k\}=\\Bigl\\\{\\alpha\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{d\}\\;\\big\|\\;\\sum\_\{i=1\}^\{d\}\\alpha\_\{i\}\\leq k\\Bigr\\\}\.The resulting feature dimension is

m=\(d\+kd\)\.m=\\binom\{d\+k\}\{d\}\.We refer toΦ​\(x\)\\Phi\(x\)as the*feature representation*of the statexx\.

#### Polynomially lifted linear dynamical systems\.

A*polynomially lifted linear dynamical system*of degree at mostkkis a function

f:ℂd→ℂdf:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}of the form

f​\(x\)=W​Φ​\(x\),W∈ℂd×m\.f\(x\)=W\\Phi\(x\),\\qquad W\\in\\mathbb\{C\}^\{d\\times m\}\.We denote byℱ≤k\\mathcal\{F\}\_\{\\leq k\}the class of all such systems\. Althoughffis generally nonlinear in the statexx, it is linear in the lifted feature space\. Thus, each system inℱ≤k\\mathcal\{F\}\_\{\\leq k\}is fully parameterized by the matrixWW\.

For convenience, along a trajectory\{xt\}t≥0\\\{x\_\{t\}\\\}\_\{t\\geq 0\}, we writeϕt:=Φ​\(xt\)∈ℂm\\phi\_\{t\}:=\\Phi\(x\_\{t\}\)\\in\\mathbb\{C\}^\{m\}\.

#### Lifted group actions on polynomial features\.

Suppose a finite groupGGacts linearly on the state spaceℂd\\mathbb\{C\}^\{d\}via a representation

ρ:G→GLd​\(ℂ\)\.\\rho:G\\to\\mathrm\{GL\}\_\{d\}\(\\mathbb\{C\}\)\.This action induces a natural linear action on the polynomial feature space associated withΦ\\Phi\. In particular, there exists a unique representation

ρΦ:G→GLm​\(ℂ\)\\rho\_\{\\Phi\}:G\\to\\mathrm\{GL\}\_\{m\}\(\\mathbb\{C\}\)such that

Φ​\(ρ​\(g\)​x\)=ρΦ​\(g\)​Φ​\(x\),∀g∈G,x∈ℂd\.\\Phi\(\\rho\(g\)x\)=\\rho\_\{\\Phi\}\(g\)\\,\\Phi\(x\),\\qquad\\forall g\\in G,\\;x\\in\\mathbb\{C\}^\{d\}\.\(5\)The representationρΦ\\rho\_\{\\Phi\}corresponds to the action ofGGon multivariate polynomials of degree at mostkkinduced by the change of variablesx↦ρ​\(g\)​xx\\mapsto\\rho\(g\)x\.

#### Equivariant polynomially lifted systems\.

LetGGact onℂd\\mathbb\{C\}^\{d\}viaρ\\rho\. A dynamical systemf:ℂd→ℂdf:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}^\{d\}is said to be*GG\-equivariant*if

f​\(ρ​\(g\)​x\)=ρ​\(g\)​f​\(x\),∀g∈G,x∈ℂd\.f\(\\rho\(g\)x\)=\\rho\(g\)f\(x\),\\qquad\\forall g\\in G,\\;x\\in\\mathbb\{C\}^\{d\}\.For polynomially lifted linear systemsf​\(x\)=W​Φ​\(x\)∈ℱ≤kf\(x\)=W\\Phi\(x\)\\in\\mathcal\{F\}\_\{\\leq k\}, this condition is equivalent to the matrix constraint

ρ​\(g\)​W=W​ρΦ​\(g\),∀g∈G,\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\),\\qquad\\forall g\\in G,\(6\)which states thatWWis an intertwining operator between the representationsρΦ\\rho\_\{\\Phi\}andρ\\rho\.

We denote byℱ≤kG⊆ℱ≤k\\mathcal\{F\}\_\{\\leq k\}^\{G\}\\subseteq\\mathcal\{F\}\_\{\\leq k\}the class of allGG\-equivariant polynomially lifted linear dynamical systems of degree at mostkk\.

#### Equivariance as linear constraints\.

For fixed representationsρ\\rhoandρΦ\\rho\_\{\\Phi\}of a finite groupGG, the equivariance condition

ρ​\(g\)​W=W​ρΦ​\(g\),∀g∈G,\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\),\\qquad\\forall g\\in G,is a system of linear constraints in the entries ofWW\. Consequently, the space ofGG\-equivariant matrices forms a linear subspace ofℂd×m\\mathbb\{C\}^\{d\\times 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 statex0x\_\{0\}and the parameter matrixWW, rather than with respect to the ambient feature space\. In particular, whenm\>dm\>d, the feature vectorΦ​\(x\)\\Phi\(x\)need not be generic as an arbitrary element ofℂm\\mathbb\{C\}^\{m\}, since the image ofΦ\\Phimay itself lie in a lower\-dimensional subset\.

The main genericity principle used throughout our proofs concerns ranks of analytic matrix\-valued functions\. LetM​\(θ\)M\(\\theta\)be a matrix whose entries depend analytically on a finite\-dimensional parameterθ\\theta, and let

r=maxθ⁡rank⁡M​\(θ\)\.r=\\max\_\{\\theta\}\\operatorname\{rank\}M\(\\theta\)\.Thenrank⁡M​\(θ\)=r\\operatorname\{rank\}M\(\\theta\)=rgenerically\. Indeed, somer×rr\\times rminor is not identically zero, and its zero set has Lebesgue measure zero\. We refer torras the*generic rank*ofMM\.

For the dynamical systems considered in this paper, each trajectory pointxtx\_\{t\}is an analytic function of the initial state and the parameter matrix: starting fromxt\+1=W​Φ​\(xt\)x\_\{t\+1\}=W\\Phi\(x\_\{t\}\), this follows recursively from the analyticity ofΦ\\Phi\. 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\.2Cayley graphs, expanders, and random generators

LetGGbe a finite group and letS=\{s1,…,sN\}S=\\\{s\_\{1\},\\ldots,s\_\{N\}\\\}be a multiset of elements ofGG\. We writeS±S^\{\\pm\}for the symmetric multiset obtained by adjoining the inverses of the elements ofSS\. The Cayley graphCay⁡\(G,S±\)\\operatorname\{Cay\}\(G,S^\{\\pm\}\)has vertex setGG, with edges corresponding to composition by elements ofSSand their inverses\. Its connected components are precisely the cosets of the subgroup⟨S⟩\\langle S\\rangle\. In particular,

Cay⁡\(G,S±\)​is connected⟺⟨S⟩=G\.\\operatorname\{Cay\}\(G,S^\{\\pm\}\)\\text\{ is connected\}\\quad\\Longleftrightarrow\\quad\\langle S\\rangle=G\.
The normalized adjacency operator of this graph is

𝒜S​f​\(g\)=12​N​∑i=1N\(f​\(si​g\)\+f​\(si−1​g\)\),f:G→ℂ\.\\mathcal\{A\}\_\{S\}f\(g\)=\\frac\{1\}\{2N\}\\sum\_\{i=1\}^\{N\}\\bigl\(f\(s\_\{i\}g\)\+f\(s\_\{i\}^\{\-1\}g\)\\bigr\),\\qquad f:G\\to\\mathbb\{C\}\.Since the generating multiset is symmetric,𝒜S\\mathcal\{A\}\_\{S\}is self\-adjoint onℓ2​\(G\)\\ell\_\{2\}\(G\)\.

#### Representation\-theoretic decomposition\.

The regular representation decomposes as

ℓ2​\(G\)≅⨁π∈G^ℂdπ⊗Vπ,\\ell\_\{2\}\(G\)\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{d\_\{\\pi\}\}\\otimes V\_\{\\pi\},wheredπ=dimVπd\_\{\\pi\}=\\dim V\_\{\\pi\}\. Choosing the irreducible representations to be unitary, the operator𝒜S\\mathcal\{A\}\_\{S\}decomposes, up to multiplicity, into the matrices

Aπ​\(S\)≔12​N​∑i=1N\(π​\(si\)\+π​\(si\)∗\)\.A\_\{\\pi\}\(S\)\\coloneqq\\frac\{1\}\{2N\}\\sum\_\{i=1\}^\{N\}\\bigl\(\\pi\(s\_\{i\}\)\+\\pi\(s\_\{i\}\)^\{\\ast\}\\bigr\)\.Thus the nontrivial spectrum of the Cayley graph is controlled by the matricesAπ​\(S\)A\_\{\\pi\}\(S\)forπ≠𝟏\\pi\\neq\\mathbf\{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,\\max\_\{\\pi\\neq\\mathbf\{1\}\}\\\|A\_\{\\pi\}\(S\)\\\|\_\{\\mathrm\{op\}\}<1,then⟨S⟩=G\\langle S\\rangle=G\.

###### Proof\.

If⟨S⟩≠G\\langle S\\rangle\\neq G, the Cayley graph has more than one connected component\. Hence the eigenvalue11of 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π\\pifor whichAπ​\(S\)A\_\{\\pi\}\(S\)has eigenvalue11, contradicting the assumed operator\-norm bound\. ∎

The classical Alon–Roichman theorem\(Alon and Roichman,[1994](https://arxiv.org/html/2608.08091#bib.bib55)\)gives a much stronger probabilistic statement: for any fixed desired spectral gap,O​\(log⁡\|G\|\)O\(\\log\|G\|\)independent uniform samples fromGGsuffice to produce an expanding random Cayley graph, with constants depending only on the desired gap\. In particular, logarithmically many random elements generateGGwith high probability\.

For our purposes, however, expansion is not needed\. The following elementary subgroup\-growth argument gives directly the generation guarantee used in[Section4\.2](https://arxiv.org/html/2608.08091#S4.SS2)\.

###### Proposition A\.2\(Random generation\)\.

Letg1,…,gN​∼i\.i\.d\.​Unif⁡\(G\)g\_\{1\},\\ldots,g\_\{N\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\operatorname\{Unif\}\(G\)andS=\{g1,…,gN\}S=\\\{g\_\{1\},\\ldots,g\_\{N\}\\\}\. Letr=⌈log2⁡\|G\|⌉r=\\lceil\\log\_\{2\}\|G\|\\rceil\. If

N≥8​\(r\+log⁡1δ\),N\\geq 8\\left\(r\+\\log\\frac\{1\}\{\\delta\}\\right\),then

ℙ​\(⟨S⟩≠G\)≤δ\.\\mathbb\{P\}\\bigl\(\\langle S\\rangle\\neq G\\bigr\)\\leq\\delta\.

###### Proof\.

LetHi=⟨g1,…,gi⟩H\_\{i\}=\\langle g\_\{1\},\\ldots,g\_\{i\}\\rangle, withH0=\{e\}H\_\{0\}=\\\{e\\\}\. WheneverHi−1H\_\{i\-1\}is a proper subgroup ofGG, Lagrange’s theorem gives\|Hi−1\|≤\|G\|/2\|H\_\{i\-1\}\|\\leq\|G\|/2, and therefore

ℙ​\(gi∉Hi−1\|g1,…,gi−1\)≥12\.\\mathbb\{P\}\\bigl\(g\_\{i\}\\notin H\_\{i\-1\}\\,\\big\|\\,g\_\{1\},\\ldots,g\_\{i\-1\}\\bigr\)\\geq\\frac\{1\}\{2\}\.Whenevergi∉Hi−1g\_\{i\}\\notin H\_\{i\-1\}, the subgroup strictly grows, and hence\|Hi\|≥2​\|Hi−1\|\|H\_\{i\}\|\\geq 2\|H\_\{i\-1\}\|\. Consequently, afterrrsuch successful enlargements, the generated subgroup must equalGG\.

The number of successful enlargements therefore stochastically dominates a binomial random variableX∼Bin⁡\(N,1/2\)X\\sim\\operatorname\{Bin\}\(N,1/2\)until generation is complete\. Hence

ℙ​\(⟨S⟩≠G\)≤ℙ​\(X<r\)\.\\mathbb\{P\}\(\\langle S\\rangle\\neq G\)\\leq\\mathbb\{P\}\(X<r\)\.Writingμ=N/2\\mu=N/2, the assumption onNNimpliesr≤μ/4r\\leq\\mu/4\. A multiplicative Chernoff bound therefore gives

ℙ​\(X<r\)≤ℙ​\(X≤μ4\)≤exp⁡\(−9​μ32\)=exp⁡\(−9​N64\)≤δ\.\\mathbb\{P\}\(X<r\)\\leq\\mathbb\{P\}\\left\(X\\leq\\frac\{\\mu\}\{4\}\\right\)\\leq\\exp\\left\(\-\\frac\{9\\mu\}\{32\}\\right\)=\\exp\\left\(\-\\frac\{9N\}\{64\}\\right\)\\leq\\delta\.∎

The preceding proposition immediately yields the simultaneous guarantee used by Algorithm[1](https://arxiv.org/html/2608.08091#alg1)\.

###### Corollary A\.3\(Simultaneous random generation\)\.

Let𝒢\\mathcal\{G\}be a finite family of finite groups and define

\|G\|max≔maxG∈𝒢⁡\|G\|\.\|G\|\_\{\\max\}\\coloneqq\\max\_\{G\\in\\mathcal\{G\}\}\|G\|\.If, independently for everyG∈𝒢G\\in\\mathcal\{G\}, we drawN𝒢,δN\_\{\\mathcal\{G\},\\delta\}i\.i\.d\. uniform samples, where

N𝒢,δ=⌈8​\(⌈log2⁡\|G\|max⌉\+log⁡\|𝒢\|δ\)⌉,N\_\{\\mathcal\{G\},\\delta\}=\\left\\lceil 8\\left\(\\left\\lceil\\log\_\{2\}\|G\|\_\{\\max\}\\right\\rceil\+\\log\\frac\{\|\\mathcal\{G\}\|\}\{\\delta\}\\right\)\\right\\rceil,then all sampled sets generate their corresponding groups simultaneously with probability at least1−δ1\-\\delta\.

###### Proof\.

Apply Proposition[A\.2](https://arxiv.org/html/2608.08091#A1.Thmtheorem2)to each candidate group with failure probabilityδ/\|𝒢\|\\delta/\|\\mathcal\{G\}\|, and take a union bound\. ∎

#### 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\)\.

LetHHbe a subgroup of a finite groupΓ\\Gammasatisfying\[Γ:H\]≤B\[\\Gamma:H\]\\leq B\. Suppose that we can sample uniformly fromΓ\\Gammaand test membership inHH\. Ifg∼Unif⁡\(Γ\)g\\sim\\operatorname\{Unif\}\(\\Gamma\)is accepted wheneverg∈Hg\\in H, then the accepted sample is exactly uniform onHH\. Moreover, the acceptance probability satisfies

ℙ​\(g∈H\)=\|H\|\|Γ\|=1\[Γ:H\]≥1B\.\\mathbb\{P\}\(g\\in H\)=\\frac\{\|H\|\}\{\|\\Gamma\|\}=\\frac\{1\}\{\[\\Gamma:H\]\}\\geq\\frac\{1\}\{B\}\.Consequently, obtainingNNi\.i\.d\. uniform samples fromHHrequires at mostB​NBNsamples fromΓ\\Gammain expectation\.

###### Proof\.

For everyh∈Hh\\in H,

ℙ​\(g=h∣g∈H\)=1/\|Γ\|\|H\|/\|Γ\|=1\|H\|,\\mathbb\{P\}\(g=h\\mid g\\in H\)=\\frac\{1/\|\\Gamma\|\}\{\|H\|/\|\\Gamma\|\}=\\frac\{1\}\{\|H\|\},so the conditional distribution is uniform onHH\. Independent repetitions of the rejection procedure therefore produce i\.i\.d\. uniform samples\. The acceptance probability is1/\[Γ:H\]1/\[\\Gamma:H\], so the expected number of ambient samples per accepted element is\[Γ:H\]≤B\[\\Gamma:H\]\\leq B\. ∎

## Appendix BProofs of Main Results

We provide the proof of the main theorems in the paper here in this section\.

### B\.1Proof of[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1)

We first prove the general rank characterization and then establish the special cases used in the main text\.

###### Proof of[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1)\.

Recall the isotypic decompositions

ℂd≅⨁π∈G^ℂnπ⊗Vπ,ℂm≅⨁π∈G^ℂmπ⊗Vπ\.\\mathbb\{C\}^\{d\}\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{n\_\{\\pi\}\}\\otimes V\_\{\\pi\},\\qquad\\mathbb\{C\}^\{m\}\\cong\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}\\mathbb\{C\}^\{m\_\{\\pi\}\}\\otimes V\_\{\\pi\}\.By Schur’s lemma, everyGG\-equivariant matrixW:ℂm→ℂdW:\\mathbb\{C\}^\{m\}\\to\\mathbb\{C\}^\{d\}has the form

W=⨁π∈G^Cπ⊗IVπ,Cπ∈ℂnπ×mπ\.W=\\bigoplus\_\{\\pi\\in\\widehat\{G\}\}C\_\{\\pi\}\\otimes I\_\{V\_\{\\pi\}\},\\qquad C\_\{\\pi\}\\in\\mathbb\{C\}^\{n\_\{\\pi\}\\times m\_\{\\pi\}\}\.
For notational convenience, reshape theπ\\pi\-isotypic component of a statexxas a matrixXπ​\(x\)∈ℂnπ×dπX\_\{\\pi\}\(x\)\\in\\mathbb\{C\}^\{n\_\{\\pi\}\\times d\_\{\\pi\}\}\. With the analogous reshapingΦπ​\(x\)∈ℂmπ×dπ\\Phi\_\{\\pi\}\(x\)\\in\\mathbb\{C\}^\{m\_\{\\pi\}\\times d\_\{\\pi\}\}of the feature vector, the transitionxt\+1=W​Φ​\(xt\)x\_\{t\+1\}=W\\Phi\(x\_\{t\}\)gives, for everyπ\\pi,

Xπ​\(xt\+1\)=Cπ​Φπ​\(xt\)\.X\_\{\\pi\}\(x\_\{t\+1\}\)=C\_\{\\pi\}\\Phi\_\{\\pi\}\(x\_\{t\}\)\.StackingTTtransitions yields

\[Xπ​\(x1\),…,Xπ​\(xT\)\]=Cπ​𝚽π,T,\[X\_\{\\pi\}\(x\_\{1\}\),\\ldots,X\_\{\\pi\}\(x\_\{T\}\)\]=C\_\{\\pi\}\\mathbf\{\\Phi\}\_\{\\pi,T\},where𝚽π,T=\[Φπ​\(x0\),…,Φπ​\(xT−1\)\]\\mathbf\{\\Phi\}\_\{\\pi,T\}=\[\\Phi\_\{\\pi\}\(x\_\{0\}\),\\ldots,\\Phi\_\{\\pi\}\(x\_\{T\-1\}\)\]\.

Thus, for a fixed observed trajectory,CπC\_\{\\pi\}is uniquely determined if and only if𝚽π,T\\mathbf\{\\Phi\}\_\{\\pi,T\}has full row rankmπm\_\{\\pi\}\. Indeed, if it has full row rank, it admits a right inverse, which uniquely determinesCπC\_\{\\pi\}\. Conversely, if its rank is smaller thanmπm\_\{\\pi\}, there exists a nonzero matrixDπ∈ℂnπ×mπD\_\{\\pi\}\\in\\mathbb\{C\}^\{n\_\{\\pi\}\\times m\_\{\\pi\}\}such thatDπ​𝚽π,T=0D\_\{\\pi\}\\mathbf\{\\Phi\}\_\{\\pi,T\}=0\. ReplacingCπC\_\{\\pi\}byCπ\+DπC\_\{\\pi\}\+D\_\{\\pi\}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\\mathbf\{\\Phi\}\_\{\\pi,T\}are analytic functions ofx0x\_\{0\}and the equivariant parametersCπC\_\{\\pi\}\. 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 preciselyhπ,Φ​\(T\)h\_\{\\pi,\\Phi\}\(T\)\. Since the blocks are independent,WWis generically identifiable exactly when

hπ,Φ​\(T\)=mπfor every​π​with​nπ\>0\.h\_\{\\pi,\\Phi\}\(T\)=m\_\{\\pi\}\\qquad\\text\{for every \}\\pi\\text\{ with \}n\_\{\\pi\}\>0\.Taking the smallest suchTTfor every active block and then the largest over the active irreducible representations gives

TΦ​\(G\)=maxπ:nπ\>0​inf\{T∈ℕ:hπ,Φ​\(T\)=mπ\}\.T\_\{\\Phi\}\(G\)=\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\inf\\\{T\\in\\mathbb\{N\}:h\_\{\\pi,\\Phi\}\(T\)=m\_\{\\pi\}\\\}\.Finally,rank⁡\(𝚽π,T\)≤min⁡\{mπ,T​dπ\}\\operatorname\{rank\}\(\\mathbf\{\\Phi\}\_\{\\pi,T\}\)\\leq\\min\\\{m\_\{\\pi\},Td\_\{\\pi\}\\\}, and therefore

TΦ​\(G\)≥maxπ:nπ\>0⁡⌈mπdπ⌉\.T\_\{\\Phi\}\(G\)\\geq\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\left\\lceil\\frac\{m\_\{\\pi\}\}\{d\_\{\\pi\}\}\\right\\rceil\.∎

#### The trivial group\.

We next justify the non\-equivariant baselineTΦ​\(\{e\}\)=mT\_\{\\Phi\}\(\\\{e\\\}\)=m\. WriteΦ=\(ϕ1,…,ϕm\)\\Phi=\(\\phi\_\{1\},\\ldots,\\phi\_\{m\}\)\. Since the coordinate functions are linearly independent,

span⁡\{Φ​\(x\):x∈ℂd\}=ℂm;\\operatorname\{span\}\\\{\\Phi\(x\):x\\in\\mathbb\{C\}^\{d\}\\\}=\\mathbb\{C\}^\{m\};otherwise a nonzero linear functional annihilating this span would give a nontrivial linear relation among theϕi\\phi\_\{i\}\. We may therefore choosez0,…,zm−1z\_\{0\},\\ldots,z\_\{m\-1\}such thatΦ​\(z0\),…,Φ​\(zm−1\)\\Phi\(z\_\{0\}\),\\ldots,\\Phi\(z\_\{m\-1\}\)are linearly independent\.

Choose anyzm∈ℂdz\_\{m\}\\in\\mathbb\{C\}^\{d\}\. Since thesemmfeature vectors form a basis ofℂm\\mathbb\{C\}^\{m\}, there existsWWsatisfyingW​Φ​\(zt\)=zt\+1W\\Phi\(z\_\{t\}\)=z\_\{t\+1\}for0≤t<m0\\leq t<m\. Hencez0,…,zmz\_\{0\},\\ldots,z\_\{m\}is a valid trajectory whose feature design matrix has rankmm\. The corresponding determinant is therefore a nonzero analytic function of\(W,x0\)\(W,x\_\{0\}\), so it is nonzero generically\. Since a trajectory of lengthT<mT<mprovides onlyTTfeature vectors, we conclude that

TΦ​\(\{e\}\)=m\.T\_\{\\Phi\}\(\\\{e\\\}\)=m\.

#### Linear systems\.

Suppose now thatΦ​\(x\)=x\\Phi\(x\)=x\. Thenmπ=nπm\_\{\\pi\}=n\_\{\\pi\}, and in theπ\\pi\-isotypic component the dynamics become

Xπ,t\+1=Cπ​Xπ,t,Xπ,t∈ℂnπ×dπ\.X\_\{\\pi,t\+1\}=C\_\{\\pi\}X\_\{\\pi,t\},\\qquad X\_\{\\pi,t\}\\in\\mathbb\{C\}^\{n\_\{\\pi\}\\times d\_\{\\pi\}\}\.Consequently,

𝚽π,T=\[Xπ,0,Cπ​Xπ,0,…,CπT−1​Xπ,0\],\\mathbf\{\\Phi\}\_\{\\pi,T\}=\[X\_\{\\pi,0\},C\_\{\\pi\}X\_\{\\pi,0\},\\ldots,C\_\{\\pi\}^\{T\-1\}X\_\{\\pi,0\}\],which is a block Krylov matrix\.

We claim that generically

rank⁡\(𝚽π,T\)=min⁡\{nπ,T​dπ\}\.\\operatorname\{rank\}\(\\mathbf\{\\Phi\}\_\{\\pi,T\}\)=\\min\\\{n\_\{\\pi\},Td\_\{\\pi\}\\\}\.It suffices to exhibit one choice attaining this rank\. Setn=nπn=n\_\{\\pi\}andr=dπr=d\_\{\\pi\}, and chooseCπ=diag⁡\(λ1,…,λn\)C\_\{\\pi\}=\\operatorname\{diag\}\(\\lambda\_\{1\},\\ldots,\\lambda\_\{n\}\), with distinct nonzeroλi\\lambda\_\{i\}\. Partitionmin⁡\{n,T​r\}\\min\\\{n,Tr\\\}rows into at mostrrgroups, each of size at mostTT, and for every row in thejj\-th group choose the corresponding row ofXπ,0X\_\{\\pi,0\}to be thejj\-th standard basis vector ofℂr\\mathbb\{C\}^\{r\}\. After permuting rows and columns, the resulting full\-rank minor consists of Vandermonde blocks

\[1λi⋯λiT−1\]\.\\begin\{bmatrix\}1&\\lambda\_\{i\}&\\cdots&\\lambda\_\{i\}^\{T\-1\}\\end\{bmatrix\}\.Each block has maximal rank because the correspondingλi\\lambda\_\{i\}’s are distinct\. Hence the total rank ismin⁡\{n,T​r\}\\min\\\{n,Tr\\\}\. Since the relevant minors are polynomial inCπC\_\{\\pi\}andXπ,0X\_\{\\pi,0\}, the same rank holds generically\. Therefore

hπ,Φ​\(T\)=min⁡\{nπ,T​dπ\},h\_\{\\pi,\\Phi\}\(T\)=\\min\\\{n\_\{\\pi\},Td\_\{\\pi\}\\\},and

Tlin​\(G\)=maxπ:nπ\>0⁡⌈nπdπ⌉\.T\_\{\\mathrm\{lin\}\}\(G\)=\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\left\\lceil\\frac\{n\_\{\\pi\}\}\{d\_\{\\pi\}\}\\right\\rceil\.

#### 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, writezt\+1=A​zt\+bz\_\{t\+1\}=Az\_\{t\}\+b, wherezt∈ℂn0z\_\{t\}\\in\\mathbb\{C\}^\{n\_\{0\}\}\. The associated feature vector is\(1,zt\)\(1,z\_\{t\}\)\. ChoosingAAdiagonal with distinct eigenvalues different from11, and writingz⋆=\(I−A\)−1​bz\_\{\\star\}=\(I\-A\)^\{\-1\}b, giveszt=z⋆\+At​\(z0−z⋆\)z\_\{t\}=z\_\{\\star\}\+A^\{t\}\(z\_\{0\}\-z\_\{\\star\}\)\. After an invertible row operation, the feature design matrix has rows

1,yi,λi​yi,…,λiT−1​yi,1,\\qquad y\_\{i\},\\lambda\_\{i\}y\_\{i\},\\ldots,\\lambda\_\{i\}^\{T\-1\}y\_\{i\},withy=z0−z⋆y=z\_\{0\}\-z\_\{\\star\}\. This is again a Vandermonde system, now with nodes1,λ1,…,λn01,\\lambda\_\{1\},\\ldots,\\lambda\_\{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\)\.

Letf1,…,fr:ℂd→ℂf\_\{1\},\\ldots,f\_\{r\}:\\mathbb\{C\}^\{d\}\\to\\mathbb\{C\}be linearly independent analytic functions\. Then there existx∈ℂdx\\in\\mathbb\{C\}^\{d\}and a diagonal matrixA=diag⁡\(λ1,…,λd\)A=\\operatorname\{diag\}\(\\lambda\_\{1\},\\ldots,\\lambda\_\{d\}\)such that

det\[fi​\(At​x\)\]i=1,…,r;t=0,…,r−1≠0\.\\det\\bigl\[f\_\{i\}\(A^\{t\}x\)\\bigr\]\_\{i=1,\\ldots,r;\\,t=0,\\ldots,r\-1\}\\neq 0\.

###### Proof\.

Expand thefif\_\{i\}’s into their Taylor series at the origin\. By invertible row operations, we may choose a basis of their span with distinct initial monomialsxα1,…,xαrx^\{\\alpha\_\{1\}\},\\ldots,x^\{\\alpha\_\{r\}\}\. Choose a positive weight vectorwwfor which these initial monomials remain distinct, and writeei=⟨w,αi⟩e\_\{i\}=\\langle w,\\alpha\_\{i\}\\rangle\. Letx​\(s\)=\(sw1,…,swd\)x\(s\)=\(s^\{w\_\{1\}\},\\ldots,s^\{w\_\{d\}\}\)\. Then, for suitable nonzero coefficientscic\_\{i\},

fi​\(At​x​\(s\)\)=ci​\(λαi\)t​sei\+higher\-order terms in​s\.f\_\{i\}\(A^\{t\}x\(s\)\)=c\_\{i\}\(\\lambda^\{\\alpha\_\{i\}\}\)^\{t\}s^\{e\_\{i\}\}\+\\text\{higher\-order terms in \}s\.Choose the diagonal entries ofAAgenerically so that the numbersλα1,…,λαr\\lambda^\{\\alpha\_\{1\}\},\\ldots,\\lambda^\{\\alpha\_\{r\}\}are distinct\. The lowest order term of the determinant is then

\(∏i=1rci\)​s∑iei​∏1≤i<j≤r\(λαj−λαi\),\\left\(\\prod\_\{i=1\}^\{r\}c\_\{i\}\\right\)s^\{\\sum\_\{i\}e\_\{i\}\}\\prod\_\{1\\leq i<j\\leq r\}\(\\lambda^\{\\alpha\_\{j\}\}\-\\lambda^\{\\alpha\_\{i\}\}\),which is nonzero\. Hence the determinant is not identically zero, and is nonzero for some sufficiently small nonzeross\. ∎

We now prove the Abelian claim from the main text\. SinceGGis finite Abelian, there is a basis ofℂd\\mathbb\{C\}^\{d\}in which everyρ​\(g\)\\rho\(g\)is diagonal\. Hence every diagonal matrixAAcommutes with the group action\. By assumption, the state coordinates are contained in the span of the feature coordinates, so there isLLsatisfyingL​Φ​\(x\)=xL\\Phi\(x\)=x\. Consequently, every equivariant linear mapx↦A​xx\\mapsto Axof the above diagonal form belongs toℱΦG\\mathcal\{F\}\_\{\\Phi\}^\{G\}\.

Fix an active irrepπ\\pi\. Since all irreducible complex representations of a finite Abelian group are one\-dimensional,dπ=1d\_\{\\pi\}=1, andΦπ​\(x\)\\Phi\_\{\\pi\}\(x\)consists ofmπm\_\{\\pi\}scalar analytic functions\. These functions are linearly independent because the coordinates ofΦ\\Phiare linearly independent\. Applying Lemma[B\.2](https://arxiv.org/html/2608.08091#A2.Thmtheorem2)withr=mπr=m\_\{\\pi\}gives a valid equivariant linear trajectory for which𝚽π,mπ\\mathbf\{\\Phi\}\_\{\\pi,m\_\{\\pi\}\}has full rank\. Hence this rank is attained generically\. Moreover, the firstTTcolumns of a nonsingularmπ×mπm\_\{\\pi\}\\times m\_\{\\pi\}design matrix are independent, giving

hπ,Φ​\(T\)=min⁡\{mπ,T\}\.h\_\{\\pi,\\Phi\}\(T\)=\\min\\\{m\_\{\\pi\},T\\\}\.Therefore

TΦ​\(G\)=maxπ:nπ\>0⁡mπ=maxπ:nπ\>0⁡mπdπ=Trep​\(G\)\.T\_\{\\Phi\}\(G\)=\\max\_\{\\pi:n\_\{\\pi\}\>0\}m\_\{\\pi\}=\\max\_\{\\pi:n\_\{\\pi\}\>0\}\\frac\{m\_\{\\pi\}\}\{d\_\{\\pi\}\}=T\_\{\\mathrm\{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\)\.

Letg1,…,gr∈ℂ​\[x1,…,xd\]g\_\{1\},\\ldots,g\_\{r\}\\in\\mathbb\{C\}\[x\_\{1\},\\ldots,x\_\{d\}\]be linearly independent polynomials and letq≥2q\\geq 2\. Then there existsx∈ℂdx\\in\\mathbb\{C\}^\{d\}such that

det\[gi​\(x⊙qt\)\]i=1,…,r;t=0,…,r−1≠0,\\det\\bigl\[g\_\{i\}\(x^\{\\odot q^\{t\}\}\)\\bigr\]\_\{i=1,\\ldots,r;\\,t=0,\\ldots,r\-1\}\\neq 0,where the power is applied coordinatewise\.

###### Proof\.

Because thegig\_\{i\}’s contain only finitely many monomials, choose a positive integer weight vectorwwassigning distinct weights to all monomials appearing in them\. After invertible row operations, we may assume that their lowest\-weight monomials are distinct, sayci​xαic\_\{i\}x^\{\\alpha\_\{i\}\}, with weightse1<⋯<ere\_\{1\}<\\cdots<e\_\{r\}\.

Setx​\(s\)=\(sw1,…,swd\)x\(s\)=\(s^\{w\_\{1\}\},\\ldots,s^\{w\_\{d\}\}\)\. Then

gi​\(x​\(s\)⊙qt\)=ci​sei​qt\+higher\-order terms\.g\_\{i\}\(x\(s\)^\{\\odot q^\{t\}\}\)=c\_\{i\}s^\{e\_\{i\}q^\{t\}\}\+\\text\{higher\-order terms\}\.In the determinant expansion, the lowest power ofssis obtained by pairing the ordered numberseie\_\{i\}with the oppositely ordered numbersqtq^\{t\}\. By the strict rearrangement inequality, this minimizing permutation is unique\. Its coefficient is±∏ici≠0\\pm\\prod\_\{i\}c\_\{i\}\\neq 0\. Hence the determinant is a nonzero polynomial inss, and is nonzero for somess\. ∎

Now letGGbe any subgroup ofSdS\_\{d\}, acting by coordinate permutations, and letΦ=Φ≤k\\Phi=\\Phi\_\{\\leq k\}withk≥2k\\geq 2\. Fix an active irrepπ\\pi, and write theπ\\pi\-isotypic feature component in terms of itsmπm\_\{\\pi\}multiplicity copies as

F1​\(x\),…,Fmπ​\(x\)∈Vπ\.F\_\{1\}\(x\),\\ldots,F\_\{m\_\{\\pi\}\}\(x\)\\in V\_\{\\pi\}\.These are linearly independent polynomial equivariant maps\.

Choose any nonzero linear functionalℓ∈Vπ∗\\ell\\in V\_\{\\pi\}^\{\*\}, and definegi=ℓ∘Fig\_\{i\}=\\ell\\circ F\_\{i\}\. The polynomialsg1,…,gmπg\_\{1\},\\ldots,g\_\{m\_\{\\pi\}\}are linearly independent\. Indeed, if∑iai​gi=0\\sum\_\{i\}a\_\{i\}g\_\{i\}=0, then the equivariant mapF=∑iai​FiF=\\sum\_\{i\}a\_\{i\}F\_\{i\}has image contained in the proper subspaceker⁡ℓ\\ker\\ell\. IfF≠0F\\neq 0, the linear span of its image is a nonzeroGG\-invariant subspace of the irreducible spaceVπV\_\{\\pi\}, and hence must equalVπV\_\{\\pi\}, a contradiction\. ThusF=0F=0, and linear independence of theFiF\_\{i\}’s givesai=0a\_\{i\}=0\.

Consider now the coordinatewise squaring dynamics

xt\+1=xt⊙2\.x\_\{t\+1\}=x\_\{t\}^\{\\odot 2\}\.This map is equivariant under every coordinate\-permutation action and belongs toℱΦ≤k\\mathcal\{F\}\_\{\\Phi\_\{\\leq k\}\}wheneverk≥2k\\geq 2\. By Lemma[B\.3](https://arxiv.org/html/2608.08091#A2.Thmtheorem3), there isx0x\_\{0\}for which

\[gi​\(x0\),gi​\(x1\),…,gi​\(xmπ−1\)\]i=1mπ\[g\_\{i\}\(x\_\{0\}\),g\_\{i\}\(x\_\{1\}\),\\ldots,g\_\{i\}\(x\_\{m\_\{\\pi\}\-1\}\)\]\_\{i=1\}^\{m\_\{\\pi\}\}has rankmπm\_\{\\pi\}\. This matrix is obtained from𝚽π,mπ\\mathbf\{\\Phi\}\_\{\\pi,m\_\{\\pi\}\}by applying the same functionalℓ\\ellto theVπV\_\{\\pi\}\-coordinate at every time step\. Hence𝚽π,mπ\\mathbf\{\\Phi\}\_\{\\pi,m\_\{\\pi\}\}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π\>0⁡mπ\.T\_\{\\Phi\_\{\\leq k\}\}\(G\)\\leq\\max\_\{\\pi:n\_\{\\pi\}\>0\}m\_\{\\pi\}\.

#### Quadratic systems with permutation symmetry\.

We finally verify the claims in Example[4\.2](https://arxiv.org/html/2608.08091#S4.Thmtheorem2)\. LetVrV\_\{r\}denote the homogeneous degree\-rrpolynomial space\. ClearlyV0=π0V\_\{0\}=\\pi\_\{0\}, whileV1V\_\{1\}is the permutation representation, soV1=π0⊕πstdV\_\{1\}=\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}\.

ForV2V\_\{2\}, the diagonal monomials\{xi2\}i=1d\\\{x\_\{i\}^\{2\}\\\}\_\{i=1\}^\{d\}form another copy of the permutation representation, while the off\-diagonal monomials\{xi​xj:i<j\}\\\{x\_\{i\}x\_\{j\}:i<j\\\}form the permutation representation on two\-element subsets\. Ford≥4d\\geq 4, the latter decomposes asπ0⊕πstd⊕π\(d−2,2\)\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}\\oplus\\pi\_\{\(d\-2,2\)\}\. Hence

V2=2​π0⊕2​πstd⊕π\(d−2,2\),V\_\{2\}=2\\pi\_\{0\}\\oplus 2\\pi\_\{\\mathrm\{std\}\}\\oplus\\pi\_\{\(d\-2,2\)\},givingmπ0=4m\_\{\\pi\_\{0\}\}=4,mπstd=3m\_\{\\pi\_\{\\mathrm\{std\}\}\}=3, andmπ\(d−2,2\)=1m\_\{\\pi\_\{\(d\-2,2\)\}\}=1\.

Onlyπ0\\pi\_\{0\}andπstd\\pi\_\{\\mathrm\{std\}\}appear in the state representation\. For the trivial block,dπ0=1d\_\{\\pi\_\{0\}\}=1, sohπ0,Φ​\(T\)≤min⁡\{4,T\}h\_\{\\pi\_\{0\},\\Phi\}\(T\)\\leq\\min\\\{4,T\\\}\. The polynomial\-orbit argument above provides a trajectory attaining rank four atT=4T=4; its firstTTcolumns are then independent for everyT≤4T\\leq 4\. Thus

hπ0,Φ​\(T\)=min⁡\{4,T\}\.h\_\{\\pi\_\{0\},\\Phi\}\(T\)=\\min\\\{4,T\\\}\.
For the standard block, letP=I−1d​𝟏𝟏⊤P=I\-\\frac\{1\}\{d\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}denote projection onto the standard representation\. A convenient basis for its three multiplicity copies is

F1​\(x\)=P​x,F2​\(x\)=P​\(x⊙2\),F3​\(x\)=\(𝟏⊤​x\)​P​x\.F\_\{1\}\(x\)=Px,\\qquad F\_\{2\}\(x\)=P\(x^\{\\odot 2\}\),\\qquad F\_\{3\}\(x\)=\(\\mathbf\{1\}^\{\\top\}x\)Px\.For every fixedxx,F3​\(x\)F\_\{3\}\(x\)is proportional toF1​\(x\)F\_\{1\}\(x\), so the one\-step rank is at most two\. SinceF1​\(x\)F\_\{1\}\(x\)andF2​\(x\)F\_\{2\}\(x\)are generically independent,hπstd,Φ​\(1\)=2h\_\{\\pi\_\{\\mathrm\{std\}\},\\Phi\}\(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,\\ldots,0\)\.RepresentVstdV\_\{\\mathrm\{std\}\}using coordinate differences relative to the last coordinate\. Selecting the first two such coordinates at time0and the first at time11gives the minor

\(12114161214\),\\begin\{pmatrix\}1&2&1\\\\ 1&4&1\\\\ 6&12&14\\end\{pmatrix\},whose determinant equals1616\. Thus the rank is three atT=2T=2, and hence generically\. Therefore

hπstd,Φ​\(T\)=min⁡\{3,2​T\}\.h\_\{\\pi\_\{\\mathrm\{std\}\},\\Phi\}\(T\)=\\min\\\{3,2T\\\}\.The trivial block is consequently the bottleneck andTΦ≤2​\(Sd\)=4T\_\{\\Phi\_\{\\leq 2\}\}\(S\_\{d\}\)=4\.

#### Representation stability for fixed\-degree polynomial features\.

We conclude by proving the multiplicity formulas used in the main text\. Letpd​\(r\)p\_\{d\}\(r\)denote the number of partitions ofrrinto at mostddparts, and letp​\(r\)p\(r\)be the unrestricted partition function\.

For the homogeneous spaceVrV\_\{r\}, the multiplicity of the trivial representation is

multVr⁡\(π0\)=dimVrSd=pd​\(r\),\\operatorname\{mult\}\_\{V\_\{r\}\}\(\\pi\_\{0\}\)=\\dim V\_\{r\}^\{S\_\{d\}\}=p\_\{d\}\(r\),since an orbit of monomials under coordinate permutations is specified by a partition ofrrwith at mostddparts\. Hence, ford≥rd\\geq r,

multVr⁡\(π0\)=p​\(r\)\.\\operatorname\{mult\}\_\{V\_\{r\}\}\(\\pi\_\{0\}\)=p\(r\)\.
To compute the standard multiplicity, use the decomposition of the permutation representationℂd=π0⊕πstd\\mathbb\{C\}^\{d\}=\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}and the identity

ℂd≅IndSd−1Sd⁡𝟏\.\\mathbb\{C\}^\{d\}\\cong\\operatorname\{Ind\}\_\{S\_\{d\-1\}\}^\{S\_\{d\}\}\\mathbf\{1\}\.Frobenius reciprocity gives

multVr⁡\(ℂd\)=dimVrSd−1\.\\operatorname\{mult\}\_\{V\_\{r\}\}\(\\mathbb\{C\}^\{d\}\)=\\dim V\_\{r\}^\{S\_\{d\-1\}\}\.AnSd−1S\_\{d\-1\}\-invariant polynomial may have an arbitrary power on one distinguished variable and must be symmetric in the remainingd−1d\-1variables\. Therefore

dimVrSd−1=∑j=0rpd−1​\(j\)\.\\dim V\_\{r\}^\{S\_\{d\-1\}\}=\\sum\_\{j=0\}^\{r\}p\_\{d\-1\}\(j\)\.Subtracting the trivial multiplicity yields

multVr⁡\(πstd\)=∑j=0rpd−1​\(j\)−pd​\(r\)\.\\operatorname\{mult\}\_\{V\_\{r\}\}\(\\pi\_\{\\mathrm\{std\}\}\)=\\sum\_\{j=0\}^\{r\}p\_\{d\-1\}\(j\)\-p\_\{d\}\(r\)\.Whend≥r\+1d\\geq r\+1, this simplifies to

multVr⁡\(πstd\)=∑j=0r−1p​\(j\)\.\\operatorname\{mult\}\_\{V\_\{r\}\}\(\\pi\_\{\\mathrm\{std\}\}\)=\\sum\_\{j=0\}^\{r\-1\}p\(j\)\.
Summing over0≤r≤k0\\leq r\\leq k, and takingd≥k\+1d\\geq k\+1, gives the stable multiplicities

mπ0=∑r=0kp​\(r\),mπstd=∑j=0k−1\(k−j\)​p​\(j\)\.m\_\{\\pi\_\{0\}\}=\\sum\_\{r=0\}^\{k\}p\(r\),\\qquad m\_\{\\pi\_\{\\mathrm\{std\}\}\}=\\sum\_\{j=0\}^\{k\-1\}\(k\-j\)p\(j\)\.Since the state permutation representation contains only these two irreducible representations, defining

Mk≔max⁡\{mπ0,mπstd\}M\_\{k\}\\coloneqq\\max\\\{m\_\{\\pi\_\{0\}\},m\_\{\\pi\_\{\\mathrm\{std\}\}\}\\\}and applying the preceding polynomial identification bound gives

TΦ≤k​\(Sd\)≤Mk,d≥k\+1\.T\_\{\\Phi\_\{\\leq k\}\}\(S\_\{d\}\)\\leq M\_\{k\},\\qquad d\\geq k\+1\.For fixedkk,MkM\_\{k\}is independent ofdd, provingTΦ≤k​\(Sd\)=Ok​\(1\)T\_\{\\Phi\_\{\\leq k\}\}\(S\_\{d\}\)=O\_\{k\}\(1\)\.

Finally, the classical Hardy–Ramanujan estimate

p​\(k\)∼14​k​3​exp⁡\(π​2​k3\)p\(k\)\\sim\\frac\{1\}\{4k\\sqrt\{3\}\}\\exp\\left\(\\pi\\sqrt\{\\frac\{2k\}\{3\}\}\\right\)also gives the stated dependence onkk\. Indeed,Mk≥mπ0≥p​\(k\)M\_\{k\}\\geq m\_\{\\pi\_\{0\}\}\\geq p\(k\), while monotonicity ofp​\(⋅\)p\(\\cdot\)givesmπ0≤\(k\+1\)​p​\(k\)m\_\{\\pi\_\{0\}\}\\leq\(k\+1\)p\(k\)andmπstd≤k2​p​\(k\)m\_\{\\pi\_\{\\mathrm\{std\}\}\}\\leq k^\{2\}p\(k\)\. Hence

Mk=exp⁡\(π​2​k3\+O​\(log⁡k\)\)\.M\_\{k\}=\\exp\\left\(\\pi\\sqrt\{\\frac\{2k\}\{3\}\}\+O\(\\log k\)\\right\)\.

### B\.2Proofs 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\)\.

LetS⊆GS\\subseteq GgenerateGG\. A matrixWWsatisfies

ρ​\(s\)​W=W​ρΦ​\(s\)for every​s∈S\\rho\(s\)W=W\\rho\_\{\\Phi\}\(s\)\\qquad\\text\{for every \}s\\in Sif and only if it isGG\-equivariant\.

###### Proof\.

Only the forward direction requires proof\. If the intertwining identity holds forg,h∈Gg,h\\in G, then

ρ​\(g​h\)​W=ρ​\(g\)​ρ​\(h\)​W=ρ​\(g\)​W​ρΦ​\(h\)=W​ρΦ​\(g​h\)\.\\rho\(gh\)W=\\rho\(g\)\\rho\(h\)W=\\rho\(g\)W\\rho\_\{\\Phi\}\(h\)=W\\rho\_\{\\Phi\}\(gh\)\.Moreover,ρ​\(g\)​W=W​ρΦ​\(g\)\\rho\(g\)W=W\\rho\_\{\\Phi\}\(g\)also impliesρ​\(g−1\)​W=W​ρΦ​\(g−1\)\\rho\(g^\{\-1\}\)W=W\\rho\_\{\\Phi\}\(g^\{\-1\}\)\. Hence the identity is preserved under composition and inversion, and therefore holds for every element of⟨S⟩=G\\langle S\\rangle=G\. ∎

###### Proof of[Theorem4\.5](https://arxiv.org/html/2608.08091#S4.Thmtheorem5)\.

We prove correctness, the trajectory\-length guarantee, and computational efficiency of Algorithm[1](https://arxiv.org/html/2608.08091#alg1)\.

#### Linear feasibility problem\.

Fix a candidate groupH∈𝒢H\\in\\mathcal\{G\}and sampled elementsSH=\{g1,…,gN\}S\_\{H\}=\\\{g\_\{1\},\\ldots,g\_\{N\}\\\}\. From the observed trajectory, define

X=\[Φ​\(x0\),…,Φ​\(xT−1\)\],Y=\[x1,…,xT\]\.X=\[\\Phi\(x\_\{0\}\),\\ldots,\\Phi\(x\_\{T\-1\}\)\],\\qquad Y=\[x\_\{1\},\\ldots,x\_\{T\}\]\.The algorithm asks whether there exists a candidate parameter matrixW~∈ℂd×m\\widetilde\{W\}\\in\\mathbb\{C\}^\{d\\times m\}satisfying

W~​X=Y,ρ​\(gi\)​W~=W~​ρΦ​\(gi\),i=1,…,N\.\\widetilde\{W\}X=Y,\\qquad\\rho\(g\_\{i\}\)\\widetilde\{W\}=\\widetilde\{W\}\\rho\_\{\\Phi\}\(g\_\{i\}\),\\quad i=1,\\ldots,N\.These are linear equations in the entries ofW~\\widetilde\{W\}\.

For completeness, lettingw~=vec⁡\(W~\)\\widetilde\{w\}=\\operatorname\{vec\}\(\\widetilde\{W\}\), the data constraint becomes

\(X⊤⊗Id\)​w~=vec⁡\(Y\),\(X^\{\\top\}\\otimes I\_\{d\}\)\\widetilde\{w\}=\\operatorname\{vec\}\(Y\),while each equivariance constraint becomes

\(Im⊗ρ​\(gi\)−ρΦ​\(gi\)⊤⊗Id\)​w~=0\.\\left\(I\_\{m\}\\otimes\\rho\(g\_\{i\}\)\-\\rho\_\{\\Phi\}\(g\_\{i\}\)^\{\\top\}\\otimes I\_\{d\}\\right\)\\widetilde\{w\}=0\.Thus each candidate group is tested by solving a single finite\-dimensional linear feasibility problem\.

#### Random generators\.

Letℰ\\mathcal\{E\}denote the event that, for every candidateH∈𝒢H\\in\\mathcal\{G\}, the sampled multisetSHS\_\{H\}generatesHH\. By Corollary[A\.3](https://arxiv.org/html/2608.08091#A1.Thmtheorem3)and the choiceN=N𝒢,δN=N\_\{\\mathcal\{G\},\\delta\},

ℙ​\(ℰ\)≥1−δ\.\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta\.We condition on this event for the remainder of the correctness argument\.

Onℰ\\mathcal\{E\}, Lemma[B\.4](https://arxiv.org/html/2608.08091#A2.Thmtheorem4)implies that the equivariance constraints imposed for a candidateHHare equivalent to fullHH\-equivariance\. Hence the feasibility test succeeds forHHexactly when there exists anHH\-equivariant system consistent with the observed trajectory\.

#### Feasibility of the true group\.

LetG∈𝒢G\\in\\mathcal\{G\}be the full symmetry group of the unknown dynamics within the ambient groupΓ\\Gamma, and letWWdenote its parameter matrix\. Since the true dynamics areGG\-equivariant,WWsatisfies all constraints corresponding toGG, and henceGGis feasible\.

Moreover,T≥TΦ​\(𝒢\)≥TΦ​\(G\)T\\geq T\_\{\\Phi\}\(\\mathcal\{G\}\)\\geq T\_\{\\Phi\}\(G\)\. By[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1), a genericGG\-equivariant system is uniquely identifiable from the observed trajectory\. ThereforeWWis the uniqueGG\-equivariant parameter matrix consistent with the data\. In particular, any feasible solution stored by the algorithm for the candidateGGis exactly the true parameter matrixWW\.

#### Characterization of all feasible candidates\.

Every candidate subgroupHHofGGis feasible, since aGG\-equivariant system is automaticallyHH\-equivariant\.

Conversely, suppose a candidateH∈𝒢H\\in\\mathcal\{G\}is feasible\. On the eventℰ\\mathcal\{E\}, feasibility means that there exists anHH\-equivariant system consistent with the trajectory\. Since𝒢\\mathcal\{G\}is generically separating, Definition[4\.4](https://arxiv.org/html/2608.08091#S4.Thmtheorem4)then implies thatHHis a subgroup ofGG\.

Thus, onℰ\\mathcal\{E\}, every feasible candidate is a subgroup of the true group, whileGGitself is feasible\. Since every proper subgroup of a finite group has strictly smaller cardinality,GGis the unique feasible candidate of maximum cardinality\. Algorithm[1](https://arxiv.org/html/2608.08091#alg1)therefore selectsGGand returns the corresponding parameter matrixWW\.

The same event also guaranteesG=⟨SG⟩G=\\langle S\_\{G\}\\rangle, so the returned setSGS\_\{G\}is a generating set of the full symmetry group\. Sinceℙ​\(ℰ\)≥1−δ\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\delta, the algorithm succeeds with probability at least1−δ1\-\\delta\.

#### Trajectory length\.

The preceding argument requires only

T≥TΦ​\(𝒢\)=maxH∈𝒢⁡TΦ​\(H\)\.T\\geq T\_\{\\Phi\}\(\\mathcal\{G\}\)=\\max\_\{H\\in\\mathcal\{G\}\}T\_\{\\Phi\}\(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\.

Letp=d​mp=dm\. For each candidate group, the unknown vectorw~\\widetilde\{w\}hasppentries\. The trajectory contributesd​TdTscalar linear equations, while theNNsampled group elements contribute at mostN​pNpscalar equivariance equations\. Thus the complete feasibility system has at most

equations inppunknowns\.

Using dense linear algebra, feasibility and a solution can therefore be computed in time polynomial ind,m,Td,m,T, andNN\. More explicitly, forming the equivariance constraints explicitly and applying Gaussian elimination gives the coarse per\-candidate bound

O​\(d3​m2​T\+N​d3​m3\),O\\bigl\(d^\{3\}m^\{2\}T\+Nd^\{3\}m^\{3\}\\bigr\),with polynomial memory complexity\. Since

N=O​\(log⁡\|G\|max\+log⁡\|𝒢\|\+log⁡1δ\),N=O\\left\(\\log\|G\|\_\{\\max\}\+\\log\|\\mathcal\{G\}\|\+\\log\\frac\{1\}\{\\delta\}\\right\),and the procedure is repeated for\|𝒢\|\|\\mathcal\{G\}\|candidates, the overall runtime is polynomial in

d,m,T,\|𝒢\|,log⁡\|G\|max,log⁡\(1/δ\),d,\\;m,\\;T,\\;\|\\mathcal\{G\}\|,\\;\\log\|G\|\_\{\\max\},\\;\\log\(1/\\delta\),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𝒢\\mathcal\{G\}are totally ordered by inclusion\. Then𝒢\\mathcal\{G\}is generically separating\.

###### Proof\.

LetG∈𝒢G\\in\\mathcal\{G\}be the full symmetry group of a generic system and supposeT≥TΦ​\(𝒢\)T\\geq T\_\{\\Phi\}\(\\mathcal\{G\}\)\. Consider a candidateH∈𝒢H\\in\\mathcal\{G\}admitting anHH\-equivariant systemW~\\widetilde\{W\}consistent with the trajectory\.

Since the family is totally ordered by inclusion, eitherHHis a subgroup ofGG, in which case there is nothing to prove, orGGis a proper subgroup ofHH\. In the latter case, everyHH\-equivariant system is alsoGG\-equivariant\. HenceW~\\widetilde\{W\}is aGG\-equivariant system consistent with the trajectory\. SinceT≥TΦ​\(G\)T\\geq T\_\{\\Phi\}\(G\),[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1)impliesW~=W\\widetilde\{W\}=W, whereWWis the true parameter matrix\. But then the true system isHH\-equivariant, contradicting the assumption that its full symmetry group isGG\. ThereforeHHmust be a subgroup ofGG\. ∎

### B\.3Proof of[Theorem4\.11](https://arxiv.org/html/2608.08091#S4.Thmtheorem11)

###### Proof\.

LetH≤ΓH\\leq\\Gammabe the full symmetry group of the unknown dynamics, with\[Γ:H\]≤B\[\\Gamma:H\]\\leq B, and suppose generic elementwise separation holds at the trajectory lengthTT\.

Algorithm[2](https://arxiv.org/html/2608.08091#alg2)repeatedly samplesg∼Unif⁡\(Γ\)g\\sim\\operatorname\{Unif\}\(\\Gamma\)and acceptsggwhenever there existsW~\\widetilde\{W\}satisfying

W~​X=Y,ρ​\(g\)​W~=W~​ρΦ​\(g\)\.\\widetilde\{W\}X=Y,\\qquad\\rho\(g\)\\widetilde\{W\}=\\widetilde\{W\}\\rho\_\{\\Phi\}\(g\)\.Ifg∈Hg\\in H, the true parameter matrixWWsatisfies these constraints\. Conversely, generic elementwise separation implies that feasibility can hold only ifg∈Hg\\in H\. Hence the algorithm accepts exactly the samples lying inHH\.

It follows that the accepted elements are i\.i\.d\. uniform samples fromHH\. Moreover,

ℙg∼Unif⁡\(Γ\)​\(g∈H\)=\|H\|\|Γ\|=1\[Γ:H\]≥1B\.\\mathbb\{P\}\_\{g\\sim\\operatorname\{Unif\}\(\\Gamma\)\}\(g\\in H\)=\\frac\{\|H\|\}\{\|\\Gamma\|\}=\\frac\{1\}\{\[\\Gamma:H\]\}\\geq\\frac\{1\}\{B\}\.Thus each accepted sample requires at mostBBambient samples in expectation\.

By the random\-generation result, the choice

NΓ,δ=⌈8​\(⌈log2⁡\|Γ\|⌉\+log⁡1δ\)⌉N\_\{\\Gamma,\\delta\}=\\left\\lceil 8\\left\(\\left\\lceil\\log\_\{2\}\|\\Gamma\|\\right\\rceil\+\\log\\frac\{1\}\{\\delta\}\\right\)\\right\\rceilensures that the accepted setSSgeneratesHHwith probability at least1−δ1\-\\delta, since\|H\|≤\|Γ\|\|H\|\\leq\|\\Gamma\|\.

Condition on this event\. By Lemma[B\.4](https://arxiv.org/html/2608.08091#A2.Thmtheorem4), imposing the intertwining constraints for allg∈Sg\\in Sis equivalent to imposingHH\-equivariance\. Since

T≥TΦ​\(ℋB\)≥TΦ​\(H\),T\\geq T\_\{\\Phi\}\(\\mathcal\{H\}\_\{B\}\)\\geq T\_\{\\Phi\}\(H\),[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1)implies that the uniqueHH\-equivariant parameter matrix consistent with the trajectory is the true matrixWW\. Therefore Algorithm[2](https://arxiv.org/html/2608.08091#alg2)returns the true dynamics together with a generating set of its full symmetry group\.

Finally, obtainingNΓ,δN\_\{\\Gamma,\\delta\}accepted elements requires at mostB​NΓ,δBN\_\{\\Gamma,\\delta\}ambient samples and feasibility tests in expectation\. Hence the expected number of tests is

O​\(B​\(log⁡\|Γ\|\+log⁡1δ\)\),O\\left\(B\\left\(\\log\|\\Gamma\|\+\\log\\frac\{1\}\{\\delta\}\\right\)\\right\),with no dependence on the number of bounded\-index subgroups ofΓ\\Gamma\. 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,\\;\\log\|\\Gamma\|,\\;\\log\(1/\\delta\)\.IfB=O​\(1\)B=O\(1\), the rejection\-sampling overhead is constant relative to direct sampling fromHH\.

The same argument gives a high\-probability runtime bound: by a standard Chernoff bound,O​\(B​\(NΓ,δ\+log⁡\(1/η\)\)\)O\(B\(N\_\{\\Gamma,\\delta\}\+\\log\(1/\\eta\)\)\)ambient samples suffice to obtainNΓ,δN\_\{\\Gamma,\\delta\}accepted elements with probability at least1−η1\-\\eta\. ∎

## Appendix CExperiments

Table 1:Dimension of the space of equivariant linear maps\{A∈ℝd×d:ρ​\(g\)​A=A​ρ​\(g\),∀g∈G\}\\\{A\\in\\mathbb\{R\}^\{d\\times d\}:\\rho\(g\)A=A\\rho\(g\),\\ \\forall g\\in G\\\}for several permutation group actions onℝd\\mathbb\{R\}^\{d\}, withd=10d=10\.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ℝd\\mathbb\{R\}^\{d\}of the form

xt\+1=A​xt,t=0,…,T−1,x\_\{t\+1\}=Ax\_\{t\},\\qquad t=0,\\ldots,T\-1,\(7\)whereA∈ℝd×dA\\in\\mathbb\{R\}^\{d\\times d\}is unknown\. LetGGbe a finite group acting onℝd\\mathbb\{R\}^\{d\}by coordinate permutations, represented by permutation matricesρ​\(g\)\\rho\(g\)\. The dynamics isGG\-equivariant if

ρ​\(g\)​A=A​ρ​\(g\),∀g∈G\.\\rho\(g\)A=A\\rho\(g\),\\qquad\\forall g\\in G\.\(8\)The matrices satisfying \([8](https://arxiv.org/html/2608.08091#A3.E8)\) form the commutant

𝒞​\(G\)≔\{A∈ℝd×d:ρ​\(g\)​A=A​ρ​\(g\),∀g∈G\}\.\\mathcal\{C\}\(G\)\\coloneqq\\\{A\\in\\mathbb\{R\}^\{d\\times d\}:\\rho\(g\)A=A\\rho\(g\),\\ \\forall g\\in G\\\}\.
For permutation actions,dim\(𝒞​\(G\)\)\\dim\(\\mathcal\{C\}\(G\)\)has a simple combinatorial interpretation\. Equation \([8](https://arxiv.org/html/2608.08091#A3.E8)\) is equivalent toAi​j=Ag​\(i\)​g​\(j\)A\_\{ij\}=A\_\{g\(i\)g\(j\)\}for everyg∈Gg\\in G\. Thus, the entries ofAAmust be constant on the orbits of the diagonal action ofGGon ordered pairs\(i,j\)\(i,j\)\. Consequently,

dim\(𝒞​\(G\)\)=\#​\{orbits ofGon​\{1,…,d\}2\}\.\\dim\(\\mathcal\{C\}\(G\)\)=\\\#\\\{\\text\{orbits of $G$ on \}\\\{1,\\ldots,d\\\}^\{2\}\\\}\.\(9\)
Table[1](https://arxiv.org/html/2608.08091#A3.T1)gives this dimension for several standard permutation actions withd=10d=10\. For example, under the full symmetric groupSdS\_\{d\}, ordered pairs form only two orbits: diagonal pairs\(i,i\)\(i,i\)and off\-diagonal pairs\(i,j\)\(i,j\),i≠ji\\neq j\. Hencedim\(𝒞​\(Sd\)\)=2\\dim\(\\mathcal\{C\}\(S\_\{d\}\)\)=2, and everySdS\_\{d\}\-equivariant matrix has the formα​I\+β​𝟏𝟏⊤\\alpha I\+\\beta\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}, forα,β∈ℝ\\alpha,\\beta\\in\\mathbb\{R\}\.

#### Dimension of the feasible set vs\. trajectory length\.

Given a trajectory\(x0,…,xT\)\(x\_\{0\},\\ldots,x\_\{T\}\)generated by \([7](https://arxiv.org/html/2608.08091#A3.E7)\), define

X=\[x0,…,xT−1\],Y=\[x1,…,xT\]\.X=\[x\_\{0\},\\ldots,x\_\{T\-1\}\],\\qquad Y=\[x\_\{1\},\\ldots,x\_\{T\}\]\.The trajectory constraint isY=A​XY=AX\. Fix an assumed permutation symmetry groupHHand restrictAAto𝒞​\(H\)\\mathcal\{C\}\(H\)\. We study the feasible set

𝒮T​\(H\)≔\{A∈𝒞​\(H\):Y=A​X\}\.\\mathcal\{S\}\_\{T\}\(H\)\\coloneqq\\\{A\\in\\mathcal\{C\}\(H\):Y=AX\\\}\.\(10\)Whenever nonempty,𝒮T​\(H\)\\mathcal\{S\}\_\{T\}\(H\)is an affine subspace\. We measure its affine dimensiondim\(𝒮T​\(H\)\)\\dim\(\\mathcal\{S\}\_\{T\}\(H\)\); in particular,

dim\(𝒮T​\(H\)\)=0⟺the trajectory uniquely identifiesAwithin𝒞​\(H\)\.\\dim\(\\mathcal\{S\}\_\{T\}\(H\)\)=0\\quad\\Longleftrightarrow\\quad\\text\{the trajectory uniquely identifies $A$ within $\\mathcal\{C\}\(H\)$\}\.

#### Computing the feasible\-set dimension\.

Letr=dim\(𝒞​\(H\)\)r=\\dim\(\\mathcal\{C\}\(H\)\), and fix a basisA1,…,ArA\_\{1\},\\ldots,A\_\{r\}of𝒞​\(H\)\\mathcal\{C\}\(H\)\. WritingA=∑i=1rθi​AiA=\\sum\_\{i=1\}^\{r\}\\theta\_\{i\}A\_\{i\}, the constraintY=A​XY=AXbecomes

vec⁡\(Y\)=\[vec⁡\(A1​X\)⋯vec⁡\(Ar​X\)\]​θ\.\\operatorname\{vec\}\(Y\)=\\begin\{bmatrix\}\\operatorname\{vec\}\(A\_\{1\}X\)&\\cdots&\\operatorname\{vec\}\(A\_\{r\}X\)\\end\{bmatrix\}\\theta\.When feasible,dim\(𝒮T​\(H\)\)\\dim\(\\mathcal\{S\}\_\{T\}\(H\)\)is thereforerrminus the rank of this design matrix\.

#### Experimental setup\.

We setd=10d=10and drawx0∼𝒩​\(0,Id\)x\_\{0\}\\sim\\mathcal\{N\}\(0,I\_\{d\}\)\. We consider three matched settings in which the true dynamics matrixAAis drawn from a continuous distribution on: \(i\)𝒞​\(C2\)\\mathcal\{C\}\(C\_\{2\}\), whereC2=⟨\(1 2\)⟩C\_\{2\}=\\langle\(1\\,2\)\\rangle; \(ii\) the unconstrained spaceℝd×d\\mathbb\{R\}^\{d\\times d\}; and \(iii\)𝒞​\(Sd\)\\mathcal\{C\}\(S\_\{d\}\)\. For each setting, we evaluatedim\(𝒮T​\(H\)\)\\dim\(\\mathcal\{S\}\_\{T\}\(H\)\)using the corresponding correct symmetry assumptionHH, and report the median over independent trials\.

These three settings have exact theoretical identification thresholds predicted by the linear\-system result of[Section4\.1](https://arxiv.org/html/2608.08091#S4.SS1)\. For the trivial group, the state representation containsddcopies of its one\-dimensional irrep, givingTlin=d=10T\_\{\\mathrm\{lin\}\}=d=10\. For the single transposition, the state representation consists ofd−1d\-1copies of the trivial representation and one copy of the sign representation, givingTlin=d−1=9T\_\{\\mathrm\{lin\}\}=d\-1=9\. Finally, forSdS\_\{d\},ℝd≅π0⊕πstd\\mathbb\{R\}^\{d\}\\cong\\pi\_\{0\}\\oplus\\pi\_\{\\mathrm\{std\}\}, with both irreducible components appearing once, and henceTlin=1T\_\{\\mathrm\{lin\}\}=1\.

#### Observed behavior\.

Figure[1](https://arxiv.org/html/2608.08091#A3.F1)plotsdim\(𝒮T​\(H\)\)\\dim\(\\mathcal\{S\}\_\{T\}\(H\)\)as a function of the trajectory lengthTT\. The feasible\-set dimension decreases withTTand 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 atT=1T=1, the single\-transposition system atT=9T=9, and the unconstrained system atT=10T=10\.

The dimensions in Table[1](https://arxiv.org/html/2608.08091#A3.T1)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[Theorem4\.1](https://arxiv.org/html/2608.08091#S4.Thmtheorem1)\.

![Refer to caption](https://arxiv.org/html/2608.08091v1/x1.png)Figure 1:Dimension of the feasible solution set𝒮T​\(H\)\\mathcal\{S\}\_\{T\}\(H\)as a function of trajectory lengthTTfor the correctly matched symmetry classes\. The dimension reaches zero at the predicted generic identification thresholdsT=1,9,T=1,9,and1010forSdS\_\{d\},C2C\_\{2\}, and the trivial group, respectively\.

## Appendix DNotation

We collect the main notation used throughout the paper\.