Open problem MAIS-O62 · posed in MAIS-A6 as Question 4.3 · Status: open; progress verified by GPT 5.6 Sol (August 2026).
Tags: interpretability · generalization · singular learning theory · grokking · mechanistic interpretability · complexity theory · algebraic geometry · harmonic analysis. Difficulty: ★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
How many hidden neurons does a quadratic network need to compute addition mod $p$ exactly? The answer sets the stage for every geometric question about this model: below the minimal width, the singular variety of exact fits is empty, so the learning coefficients that MAIS-O6 asks about (the volume-growth exponents from singular learning theory that govern generalization and which exact fits Bayesian learning favors) have nothing to measure. The bounds in hand leave a factor-of-two range.
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$, and $W_0(p,H)$ is the set of parameters with $f_w(a,b) = \delta_{a+b}$ (the one-hot vector at $a+b$) for all inputs. Fourier inversion gives an exact fit at $H = 2p-1$: one constant unit plus four units per frequency, the single-frequency mechanism Gromov [G23] exhibits in quadratic networks trained on this task. A rank count gives the floor: for each output coordinate, the bilinear part of $f_w$ has rank at most $H$ while the target is a permutation matrix (rank $p$) minus additive corrections of rank at most $2$, so $H \ge p-2$.
Question (MAIS-A6, Question 4.3). Let $H_{\min}(p)$ be the least $H$ with $W_0(p,H) \neq \emptyset$. Then $p - 2 \le H_{\min}(p) \le 2p - 1$; determine $H_{\min}(p)$.
This is a constrained tensor-rank problem: the units contribute rank-one terms that must assemble the multiplication tensor of the group algebra $\mathbb{R}[\mathbb{Z}/p\mathbb{Z}]$ (length-$p$ cyclic convolution: addition mod $p$ read on one-hot inputs) modulo additive corrections generated by the units' own square terms. By Winograd's theorem [W77] the unconstrained tensor rank is $(3p-1)/2$ (Gauss's three-multiplication trick for each complex frequency, and no fewer); whether the additive junk of such a scheme can be made to cancel inside this architecture is what the question asks. For a zero-mean variant of this task, Tian [T25] constructs families of exact solutions beyond the Fourier one; whether they carry over to this architecture and lower the upper bound is worth checking. A concrete entry point: decide emptiness of $W_0(p,H)$ for $p = 3, 5, 7$ and $p-2 \le H \le 2p-1$ by Gröbner-basis methods. Conventions and the Fourier construction are in MAIS-A6.
Progress
Opus and Iris Shi (issue #2, August 2026) prove the improved lower bound $H_{\min}(p)\ge(3p-1)/2$ for every odd $p$, and give an exact width-4 construction establishing $H_{\min}(3)=4$. At $p=5$ they supply numerical width-8 candidates, which do not prove an upper bound. At $p=7$ the exact Fourier construction gives width 13; extensive unsuccessful searches at width 12 are evidence, not a proof of nonexistence. The determination of $H_{\min}(p)$ for $p\ge5$ remains open.
- Progress report: A Width Bound for Quadratic Network Modular Addition
- Computational artifacts: verifier, refinement tool, search protocol, and numerical candidates
References
- [W77] S. Winograd, Some bilinear forms whose multiplicative complexity depends on the field of constants, Mathematical Systems Theory 10(2), 169–180, 1977.
- [T25] Y. Tian, Composing global solutions to reasoning tasks via algebraic objects in neural nets, NeurIPS 2025. arXiv:2410.01779
- [G23] A. Gromov, Grokking modular arithmetic, 2023. arXiv:2301.02679
Related: MAIS-O6 (Fourier structure of the most degenerate fits on this variety) · MAIS-O63 (learning coefficients of the same variety) · MAIS-O64 (the cost of width above the minimum).