Canonical Minimal Polynomial Invariants from Noisy Data via Adaptive Sparse Nullspace Recovery and Gröbner Basis

Abstract

Discovering conservation laws and algebraic invariants from data is a fundamental challenge in scientific machine learning. Existing methods, such as SINDy-null (KRONIC), successfully recover a single invariant but fail when multiple invariants coexist, returning arbitrary linear mixtures instead of the individual physical quantities—a problem explicitly left open by Kaiser, Kutz & Brunton (2018). Another challenge is lack of canonicalization: expressions like x² + y² - 1 = 0, (x² + y² - 1)² = 0, and x² - 1 + y² = 0 are treated as distinct by SMT solvers and SOS verifiers despite representing the same constraint. This paper introduces SR-GB+CSNP (Sparse Recovery, Gröbner Basis, and Combinatorial Sparse Nullspace Pursuit), a pipeline that resolves these ambiguities through a novel combination of techniques: Resolves Nullspace Ambiguity using CSNP, a lexicographic Branch-and-Bound search that enforces an information-theoretic rationality cost as its primary criterion—favoring sparse, geometrically stable invariants with simple rational coefficients. This moves beyond sparsity, which alone would prefer a 3-term artifact over the true 4-term energy invariant. Eliminates Algebraic Redundancy by computing the reduced Gröbner basis of the recovered ideal, ensuring a unique, canonical output. This solves the "canonicalization gap" where expressions like x² + y² - 1 = 0, (x² + y² - 1)² = 0, and x² - 1 + y² = 0 are treated as distinct by SMT solvers and SOS verifiers despite representing the same mathematical constraint. Discovers the Polynomial Degree Automatically via adaptive monomial expansion and a Minimum Description Length (MDL)-based stopping criterion, removing the need to specify the polynomial degree upfront. Key Contributions: Algorithmic: A certified Branch-and-Bound search that provides a global optimality certificate, moving beyond greedy selection. An information-theoretic rationality cost that prioritizes simple rational coefficients, resolving ambiguities that sparsity alone cannot. Automatic degree discovery through adaptive monomial expansion and MDL-based stopping. Noise-tolerant snap-rounding that significantly extends robustness compared to naïve rounding. Theoretical: Exact recovery conditions and global optimality proofs for the core CSNP algorithm. A Normal-Form Pruning Lemma that justifies algebra-guided monomial elimination. A closed-form, partial resolution of the "integrator trap," showing that the method's selection criterion prefers the true Hamiltonian over a symplectic integrator's modified invariant. Empirical: 100% exact recovery on 26 Feynman polynomial equations at zero noise. 96.7% recovery at σ=0.05 for degree-2 equations, outperforming all benchmarks. On the 2D oscillator multi-invariant benchmark, recovers all 4 entangled generators in every seed, where SINDy-null recovers 0%. Validation across eight benchmark classes, including synthetic varieties, robotic holonomic constraints, program loop invariants, and physical systems (Kepler, point vortices). Where This Applies: Reinforcement Learning & Formal Verification: Canonical invariants enable SMT solvers and SOS verifiers to reason about RL policies without degenerate results. Robotics: Holonomic kinematic constraints. Chemical Reaction Networks: Conservation laws. Program Verification: Loop invariant generation. Scientific Discovery: Extracting physical laws from data. Limitations & Future Work: Unit Dependence: The rationality prior assumes data is in units where the true invariant has simple rational coefficients—not scale-invariant. Polynomial-Only: Currently restricted to polynomial invariants with rational coefficients (trigonometric, exponential, and irrational coefficients are future work). Combinatorial Scalability: The search becomes infeasible for large dictionaries (M > 100), where an L1-fallback heuristic is used without optimality guarantees. Resources: Paper & Source Code (Full Manuscript): https://github.com/TesfayZ/srgb-csnp — Contains the complete paper, benchmark scripts, and reproduction instructions. PyPI Package (polyinv): https://github.com/TesfayZ/polyinv — Initial Python package release: pip install polyinv.