A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures

arXiv:2511.23152v3 Announce Type: replace Abstract: Discovering discrete algebraic rules from data is a fundamental challenge in machine learning. We formalize this problem through Cayley-table completion -- an algebraic counterpart to classical matrix completion -- where the degree of associativity violation replaces linear rank as the intrinsic measure of complexity. We provide the first optimization landscape analysis of HyperCube, an operator-valued tensor factorization, on the fully observed target table elta, proving that its global infimum H_{inf}(elta) := inf_{Theta in F_elta} H(Theta) implicitly defines an exact differentiable measure for this complexity. We show that HyperCube's native objective H(Theta) decomposes into two components: geometric alignment (collinearity) and an inverse ell_2 penalty. We establish that these continuous variational pressures induce core discrete properties: collinearity enforces associativity (Collinearity--Associativity Equivalence), and the inverse ell_2 penalty reduces to an exact inverse rank penalty within the collinear manifold, driving the parameters toward full-rank unitarity. Consequently, we derive an absolute lower bound H(Theta) ge H_{inf}(elta) ge 3 , |elta|, where |elta| is the target table size. We prove this absolute floor is attained if and only if the target is isotopic to a group, and characterize the global minimizer as the regular representation of the underlying group (up to unitary gauge). This result resolves the central open conjecture of Huh (2025). This work serves as an existence proof that certain discrete algebraic structures can be exactly characterized by differentiable measures, enabling gradient-based discovery without the need for combinatorial search. All theoretical results are mechanically verified in Lean 4 and confirmed via small-scale experiments.

Source: arXiv cs.LG | 2026-05-18