A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures
Authors: Dongsung Huh, Lior Horesh, Halyun Jeong
Summary
arXiv:2511. 23152v4 Announce Type: cross Abstract: Discovering discrete algebraic rules from data is a fundamental challenge in machine learning.
Relevance
Read next because A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures overlaps with clean result "Leakage rate is a usable signal for recovering trigger-shaped phrases on Gaperon-1125-1B without knowing the hidden trigger itself (MODERATE confidence)", clean result "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)", clean result "Coupling evil personas with wrong answers fails to protect Qwen2.5-7B from EM-induced alignment collapse — and the apparent capability ordering across coupling conditions is mostly eval contamination (LOW confidence)". Matching terms: class, under, alignment, line, without, full, factor, completion. Source: arxiv stat.ML (Machine Learning).
Abstract
arXiv:2511.23152v4 Announce Type: cross 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 a rigorous landscape analysis of HyperCube, an operator-valued tensor factorization, on the fully observed target table $\delta$, proving that its global infimum $H_{\inf}(\delta) := \inf_{\Theta \in F_\delta} 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}(\delta) \ge 3 , |\delta|$, where $|\delta|$ 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.