no. 17 · Wednesday 18 November 2026
Functional Compression as Occam's Razor: Algebraic Complexity from Sensitivity Minimization
Abstract
Discovering discrete algebraic structures from data is a fundamental challenge in machine learning. We ask how continuous learning objectives can favor functional compression—representing data through shared algebraic composition rather than low-rank representations. We analyze the global optima of a canonical factorization model for algebraic completion (recovering finite binary operations) that demonstrated a preference for group operations. We measure algebraic complexity by the infimum of parameter sensitivity under exact reconstruction. We establish a universal complexity floor, whose attainment forces geometric alignment and unitarity of the latent representations. At the floor, input representations compose into the corresponding output representations; their reuse across the operation table propagates these local identities to enforce a globally shared algebraic structure. If the floor is not attained, a positive gap separates it from the feasible infimum. For cancellative operations, floor attainment forces the model's latent representation to be an injective homomorphism, equivalent to the target being isotopic to a group. In this case, every global minimizer is equivalent to the underlying group's unitary left-regular representation, up to isotopy and unitary gauge, resolving the central conjecture of Huh (2025). For non-cancellative operations, floor attainment forces exact structural redundancies (identical rows or columns) and is equivalent to a unitary factorization of the target's row- and column-reduced table with orthonormal output matrices, yielding the fewest distinct input matrices compatible with exact reconstruction. The resulting cancellative table then embeds in a group-isotope table. This analysis reveals a structural bias toward functional compression: at the sensitivity floor, algebraic composition of latent representations implements the target operation.
- comments
- 28 pages, 3 figures. Version 5: major revision, adding results for arbitrary binary operations, positive-gap theorems, and Lean 4 formalizations of the main theoretical results
- fields
- Optimization and Control, Representation Theory