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

Technical Summary: A Differentiable Measure of Algebraic Complexity

Problem Formulation
The paper addresses the fundamental challenge of discovering discrete algebraic rules, specifically group structures, from data using machine learning. While matrix completion has successfully formalized the discovery of continuous low-dimensional manifolds, the discrete nature of algebraic axioms (such as associativity) renders them non-differentiable and resistant to standard gradient-based optimization. The authors formalize this challenge as Cayley-table completion: recovering a discrete binary operation from partial or full observations. Unlike linear rank, which is inadequate for algebraic structures due to the inherent permutation properties of Latin squares, the paper posits that associativity is the true measure of algebraic parsimony. The core problem is to find a continuous, differentiable measure that penalizes associativity violations without relying on intractable combinatorial search.

Methodology: The HyperCube Architecture
The study analyzes the HyperCube architecture, an operator-valued tensor factorization model designed to learn discrete binary operations.

• Model Structure: The model represents the structure tensor $\delta \in \{0, 1\}^{n \times n \times n}$ via a trilinear product $T_{abc}(\Theta) = \frac{1}{n} \text{Tr}(A_a B_b C_c)$, where $\Theta = (A, B, C)$ are factor matrices.
• Objective Function: The optimization minimizes a Jacobian-based objective $H(\Theta)$, defined as the sum of squared Frobenius norms of the Jacobian terms with respect to the factors. For a quasigroup target, this is reformulated as a sum over supported triples:
  $$H(\Theta) = \sum_{a,b,c} \delta_{abc} \left( \|B_b C_c\|^2 + \|C_c A_a\|^2 + \|A_a B_b\|^2 \right)$$
• Theoretical Framework: The authors perform a rigorous landscape analysis of $H(\Theta)$ over the feasible set $\mathcal{F}_\delta$ (where $T(\Theta) = \delta$). They decompose the objective into two orthogonal components:
  1. Geometric Misalignment ($R_\delta$): A penalty term measuring the deviation from collinearity between factor slices.
  2. Inverse-Scale Penalty ($B_\delta$): A term promoting balanced, full-rank factorizations.

Key Contributions and Theoretical Results
The paper provides a rigorous mathematical characterization of the global optimization landscape of HyperCube, resolving the open conjecture of Huh [1] regarding the model's inductive bias.

1. Collinearity–Associativity Equivalence:
   The authors prove that the "collinear manifold" (where geometric misalignment $R_\delta = 0$) is non-empty if and only if the target Cayley table is isotopic to a group. This establishes a strict equivalence: geometric alignment in the continuous parameter space forces the discrete algebraic structure to satisfy the associativity axiom.

2. Rank-Maximizing Pressure and Unitarity:
   Within the collinear manifold, the objective reduces to an exact inverse rank penalty. This variational pressure drives the factor slices toward full-rank unitarity. Consequently, the unique global minimizer (up to unitary gauge) is identified as the left-regular representation of the underlying group.

3. Absolute Lower Bound and the Associativity Gap:
   The paper establishes an absolute lower bound for the objective: $H(\Theta) \geq 3|\delta|$, where $|\delta| = n^2$ is the table size.

   • Group Isotopes: If the target is isotopic to a group, this floor is attainable ($H_{inf}(\delta) = 3|\delta|$), and the solution is the regular representation.
   • Non-Group Isotopes: If the target is not a group, the global infimum is strictly separated from the floor by a residual penalty, termed the Associativity Gap ($H_{inf}(\delta) > 3|\delta|$). This gap serves as a differentiable measure of algebraic complexity, scaling with the degree of associativity violations.

4. Mechanized Verification:
   All foundational theoretical results, including the decomposition of the objective and the equivalence theorems, are mechanically verified using Lean 4, ensuring mathematical rigor.

Empirical Results
Small-scale experiments on quasigroup targets (orders $n=5$ to $8$) validate the theoretical landscape:

• Convergence Dynamics: Optimization trajectories exhibit smooth convergence without getting trapped in spurious local minima.
• Pareto Frontier: The trade-off between misalignment ($R_\delta$) and the base penalty ($B_\delta$) follows a strict Pareto frontier. Reducing misalignment forces an increase in the base penalty, but the net effect is a reduction in total loss.
• Dichotomy: Group targets converge exactly to the $3|\delta|$ floor with zero misalignment. Non-group targets are geometrically obstructed, converging to a higher loss value with positive residual misalignment, directly visualizing the Associativity Gap.
• Emergent Disentanglement: For commutative groups, the model naturally discovers the irreducible representations (irreps), reducing the latent space to an exact orthogonal frequency decomposition.

Significance and Claims
The paper claims to provide an existence proof that certain discrete algebraic structures can be exactly characterized by differentiable measures.

• Gradient-Based Discovery: It demonstrates that gradient-based optimization can discover exact discrete rules (associativity) without combinatorial search, driven by the geometry of the continuous loss surface.
• Inductive Bias: The work formally explains the empirical success of HyperCube, attributing it to a "structural prior" where the optimization landscape inherently privileges associative structures over non-associative ones.
• Geometric Deep Learning: By automating the discovery of underlying symmetry groups, the approach frees architectures from manually prescribed inductive biases, potentially enabling systematic generalization in domains with unknown symmetry groups.

The authors remain modest regarding scalability, noting that current theoretical guarantees and empirical validations are limited to small-scale, fully observed discrete targets. Scaling to high-dimensional, noisy, or partially observed real-world data remains an open challenge.