用可微分方法精确识别数据中的群结构，无需暴力搜索。
A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures
- 通过张量分解构建可微分目标函数，以共线性约束保证结合律
- 理论证明目标值下界为3倍表大小，达标即表明存在群结构
- 首次实现梯度下降直接发现代数群，适合有代数背景的研究者
从数据中发现离散代数规则是机器学习的基础挑战。本文通过凯莱表补全形式化该问题——这是经典矩阵补全的代数对应物，其中结合律破坏程度取代线性秩作为复杂性度量。我们对算子值张量分解方法 HyperCube 在完全观测目标表 δ 上进行了严格的景观分析，证明其全局最小值 H_inf(δ) := inf_{Θ∈F_δ} H(Θ) 隐式定义了一个精确的可微分复杂性度量。我们表明 HyperCube 的原生目标函数 H(Θ) 可分解为几何对齐（共线性）和逆ℓ₂惩罚两项。理论证明这两项连续变分压力诱导出核心离散性质：共线性强制结合律成立（共线性-结合律等价），而逆ℓ₂惩罚在共线流形内退化为精确的逆秩惩罚，推动参数趋向满秩酉性。由此导出绝对下界 H(Θ) ≥ H_inf(δ) ≥ 3 |δ|，其中 |δ| 为目标表大小。我们证明该下界当且仅当目标与某群同构时可达，并将全局最小解刻画为底层群的正则表示（至酉规范变换）。本工作首次解决胡（2025）的核心猜想，证明某些离散代数结构可通过可微分度量精确刻画，支持梯度驱动发现，无需组合搜索。所有理论结果均经 Lean 4 机械验证，并通过小规模实验确认。
原文摘要 · Abstract (English)
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 $H_{\inf}(δ) := \inf_{Θ\in F_δ} H(Θ)$ implicitly defines an exact differentiable measure for this complexity. We show that HyperCube's native objective $H(Θ)$ 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(Θ) \ge H_{\inf}(δ) \ge 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。