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

arXiv: https://arxiv.org/abs/2511.23152 · HTML: https://mlsanity.com/paper/2511.23152/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 28 Nov 2025.

## Builds on (most cited first, 12 of 12)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning](https://mlsanity.com/paper/2012.13255/) (2020)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups](https://mlsanity.com/paper/2104.09459/) (2021)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [The Low-Rank Simplicity Bias in Deep Networks](https://mlsanity.com/paper/2103.10427/) (2021)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Automatic Symmetry Discovery with Lie Algebra Convolutional Network](https://mlsanity.com/paper/2109.07103/) (2021)
- [Bispectral Neural Networks](https://mlsanity.com/paper/2209.03416/) (2022)
- [Disentangling images with Lie group transformations and sparse coding](https://mlsanity.com/paper/2012.12071/) (2020)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)

## Built on by (most cited first, 1 of 1)

- [Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion](https://mlsanity.com/paper/2605.29885/) (2026)

## Abstract (arXiv)

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 a rigorous landscape analysis of HyperCube, an operator-valued tensor factorization, on the fully observed target table δ, proving that its global infimum Hinf(δ) := infTheta ∈ Fδ 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 ℓ2 penalty. We establish that these continuous variational pressures induce core discrete properties: collinearity enforces associativity (Collinearity--Associativity Equivalence), and the inverse ℓ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) ≥ Hinf(δ) ≥ 3 , |δ|, where |δ| 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), resolving 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.