Open problem MAIS-O6 · headline problem 6 of the survey MAIS-P1 · canonically formalized in MAIS-A6 as Conjecture 4.9 · Status: open.
Tags: interpretability · generalization · singular learning theory · mechanistic interpretability · developmental interpretability · grokking · simplicity bias · algebraic geometry · harmonic analysis. Difficulty: ★★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
A small network trained to add residues mod $p$, when reverse-engineered by Nanda, Chan, Lieberum, Smith, and Steinhardt [NCLSS23], turns out to be running a discrete Fourier algorithm: each hidden neuron carries a single frequency. Is that mechanism an accident of training, or is it forced by the geometry of the loss? Watanabe's singular learning theory [W09] says Bayesian learning settles on the exact fits of smallest local learning coefficient, so the question becomes a theorem-or-counterexample: whether the most singular exact fits are the Fourier ones.
Fix an odd $p \ge 3$ and a width $H$. On input $(a,b) \in (\mathbb{Z}/p\mathbb{Z})^2$ the network computes $f_w(a,b) = \sum_{j=1}^H V_j\ (u_j'(a) + u_j''(b))^2 \in \mathbb{R}^p$, with lookup tables $u_j', u_j''\colon \mathbb{Z}/p\mathbb{Z} \to \mathbb{R}$ and output columns $V_j \in \mathbb{R}^p$; the target is the one-hot vector $\delta_{a+b}$. The population loss $K$ is half the mean squared error over the $p^2$ inputs, an explicit degree-six polynomial in the $3pH$ parameters, and $W_0(p,H)$ is its zero set, the variety of exact fits. The local learning coefficient $\lambda(w)$ at an exact fit $w$ is the volume-growth exponent: the volume of $\lbrace K \le \varepsilon\rbrace $ inside a small ball around $w$ scales as $\varepsilon^{\lambda(w)}$ up to a power of $\log(1/\varepsilon)$. Smaller $\lambda$ means a more degenerate fit, better generalization, and more posterior mass.
Fourier inversion on $\mathbb{Z}/p\mathbb{Z}$ produces an exact fit $w^F$ at width $2p-1$ whose every unit uses one frequency: squaring converts sums of cosines into cosines of sums, and the resulting output columns assemble the discrete Fourier expansion of $\delta_{a+b}$ (explicit construction in MAIS-A6). Set $R_p = 1 + \Vert w^F\Vert $ and $\lambda_{\min}(p,H;R_p) = \min\lbrace \lambda(w) : w \in W_0(p,H),\ \Vert w\Vert \le R_p\rbrace $, where $\Vert \cdot\Vert $ is the Euclidean norm of the full parameter vector. For $0 \le k \le (p-1)/2$ let $\mathcal F_k \subset \mathbb{R}^p$ be the span of $(\cos 2\pi k a/p)_a$ and $(\sin 2\pi k a/p)_a$. A unit $j$ is active if $(a,b) \mapsto V_j(u_j'(a)+u_j''(b))^2$ is not identically zero, and single-frequency if there is one $k$ with $u_j', u_j'' \in \mathcal F_0 + \mathcal F_k$.
Conjecture (MAIS-A6, Conjecture 4.9). For every odd $p \ge 3$ and $H \ge 2p-1$: every $w \in W_0(p,H)$ with $\Vert w\Vert \le R_p$ and $\lambda(w) = \lambda_{\min}(p,H;R_p)$ has all of its active units single-frequency.
In words: within the fixed ball, every maximally degenerate exact fit is built from single-frequency neurons, apart from neurons contributing nothing. A proof would show that geometric simplicity selects an algorithm readable from the weights; a counterexample would split the two notions of simplicity. The structure has been forced once already, under a different selection principle: every maximum-margin solution of this task has single-frequency units, a theorem of Morwani, Edelman, Oncescu, Zhao, and Kakade [MEOZK24]. The first non-vacuous case is $p = 5$, $H = 9$ (for $p=3$ the condition is vacuous since $\mathcal F_0 + \mathcal F_1 = \mathbb{R}^3$): classify its most singular fits by symmetry, or find a non-Fourier one by computer algebra. Construction of $w^F$, its symmetries, and known bounds are in MAIS-A6.
References
- [NCLSS23] N. Nanda, L. Chan, T. Lieberum, J. Smith, and J. Steinhardt, Progress measures for grokking via mechanistic interpretability, ICLR 2023. arXiv:2301.05217
- [MEOZK24] D. Morwani, B. L. Edelman, C.-A. Oncescu, R. Zhao, and S. Kakade, Feature emergence via margin maximization: case studies in algebraic tasks, ICLR 2024. arXiv:2311.07568
- [W09] S. Watanabe, Algebraic Geometry and Statistical Learning Theory, Cambridge University Press, 2009.
Related: MAIS-O63 (compute $\lambda$ at the Fourier fits — the quantitative companion) · MAIS-O62 (the minimal width at which exact fits exist) · MAIS-O64 (how $\lambda_{\min}$ grows with width) · MAIS-O65 (the same question under cross-entropy loss).