Introduction
Grokking is delayed generalisation: a network fits its training examples, remains near chance on held-out inputs for a long period, and then generalises abruptly (Power et al., [42 ] ). The classical instance is modular addition, where the network observes some pairs ( x , y ) (x, y) ( x , y ) x + y m o d q x + y \bmod q x + y mod q [38 ] ; Mohamadi et al., [36 ] ; Gu et al., [17 ] ). However, a run that generalises shows that there exists one solution does; it does not show that every solution a training could have selected would. We isolate the generalisation behaviour and ask it at the level of the task. Defining the minimum-norm endpoint as the solution to the weight decay-induced optimization problem, our central question is therefore: which task structures make the entire minimum-norm endpoint set generalise?
Answering it needs modelling of the task and endpoint set. A pairwise input task assigns an output to every pair of inputs, and we encode it as an edge colouring of the complete bipartite graph K q , q K_{q,q} K q , q ( u , v ) (u,v) ( u , v ) q × q q \times q q × q F q \mathbb{F}_q F q Latin when it is proper, so that no vertex sees a colour twice; in table coordinates every symbol appears exactly once in each row and column, so the Latin colourings are the Latin squares of combinatorics. Every group multiplication table is one, and the family therefore contains modular addition together with its natural competitors. Permuting the vertices within either class, permuting the colours, or swapping the two classes only changes how the table is written; we call such a move a relabelling , and the orbit of a colouring under relabellings is our task object. Training observes a uniformly random subset of the cells of fixed size.
The network reads an edge through its two endpoints, with one embedding table per vertex class, a hidden ReLU layer, and a head over the colours. For the endpoint of training we follow implicit-bias theory, which motivates the minimum-norm interpolator as the idealised late-training object ([46 , 30 , 39 ] ). A partially observed colouring, however, has many minimum-norm interpolators: all meet the margins on the observed cells and are free to disagree on the rest, and a handful of training runs yields a few selected predictors without certifying that they belong to this set or how the set behaves as a whole. We therefore take the whole set, the endpoint set , as the object of study, and describe it by what holds across it at a fixed held-out threshold τ \tau τ phase profile , a point of a triangle (Figure 1 , middle and right).
Figure 1. Coordinates, endpoint sets, and the two poles. Left: x + y x+y x + y S q ( D ) \mathcal{S}_q(\mathcal{D}) S q ( D ) A q − ≤ A q + A_q^{-} \leq A_q^{+} A q − ≤ A q + τ \tau τ
Relabelling induces a norm-preserving bijection between endpoint sets and preserves the law of the observations, so the phase profile is well defined on orbits: it is a map from colouring orbits to the triangle. The network realises the bijection by permuting the rows of its embedding tables and of its head. This separates task structure from its polynomial description. Take x + y x+y x + y F 97 \mathbb{F}_{97} F 97 x + y x+y x + y Figure 1 , left). Relabelling preserves the phase while changing polynomial sparsity and degree, and in this comparison those coordinate statistics also fail to distinguish the trained predictors’ outcomes. This is why we work with orbits.
Our results place two structures at opposite poles of the triangle. The all-good pole contains every finite abelian group family : at any fixed positive observation fraction, the worst endpoint accuracy converges to one in probability as the order grows. Cyclic addition is one instance, and non-isomorphic abelian groups supply distinct all-good orbits. At the opposite pole, a uniformly random Latin colouring defeats every learner that reads only the observations, at any fixed positive accuracy; consequently the colourings with a non-negligible all-good component have vanishing uniform mass. Generalisation is thus guaranteed throughout a structured family yet rare in the ambient space.
The core of our theory is a lemma of carrier criterion : a network that scores the full grid with controlled margins at a known norm cost. It bounds the cost of every minimum-norm endpoint on every mask, and a finite atlas fixed before the observations counts the harmful low-norm alternatives, whose number is too small for any of them to evade a random mask. The criterion does not depend on the colouring, and abelian characters provide carriers uniformly across group structures. Therefore, we have proven that satisfying this lemma is a sufficient condition for all good. We conjecture that the carrier criterion is also necessary: every asymptotically all-good Latin family admits a full-grid carrier in the same norm-and-margin regime.
Experiments at composite order 64 compare the guaranteed families with non-abelian and non-group candidates and show that coarse output factors are recovered before exact labels. These trained predictors probe structure; they do not measure the phase of the whole endpoint set. Whether a typical random colouring has some good endpoint, and whether any family carries non-vanishing mixed mass, remain open.
Contributions.
A task-level formulation: Latin colourings of K q , q K_{q,q} K q , q
Two poles: every finite abelian group family is asymptotically all-good, while the uniform Latin ensemble defeats every learner at any fixed positive held-out accuracy.
A colouring-independent carrier criterion for all-goodness, together with the conjecture that this criterion is necessary.
Experiments in the same model class: relabelled addition groks like addition while looking like noise, and at composite order structured tasks recover coarse output factors before exact labels.
Paper Organization. Section 2 reviews prior work, Section 3 defines the model, Section 4 states and proves the two poles and the abelian extension, Section 5 reports the composite-order experiments and states the conjecture, and Section 6 concludes. Experiments that speak directly to the theory follow the theory itself.
Related Work
Grokking is reported in non-neural models [32 ] , deep networks [14 , 33 ] , in-context and multi-hop reasoning [19 , 56 , 1 ] , and LLM pretraining [27 ] ; its onset needs a critical data fraction [64 , 21 ] and its delay can be shortened [49 , 26 , 40 , 24 , 59 ] . Related approaches include representation learning, norm and optimisation bias, and circuit competition. Representation-level work studies Fourier circuits and progress measures [38 , 16 , 15 , 3 ] , spectral dynamics [63 , 61 ] , embedding bottlenecks [2 ] , architectural bias [44 ] (Yıldırım 2026), task symmetry [23 ] , embedding uniformity coupled to the training distribution [17 ] , feature-emergence scaling laws [50 ] , and topological signatures [48 ] .
Norm- and optimisation-based accounts appeal to implicit bias toward max-margin, minimum-norm endpoints [46 , 30 , 39 , 31 , 36 , 22 ] , to norm minimisation on the zero-loss manifold [37 , 51 ] , to the edge of linear separability [4 ] , to numerical stability [43 ] , sharpness [35 ] , Jacobian alignment [55 ] , and quantitative delay laws [52 , 47 , 11 ] .
Competition accounts pit a slow generalising circuit against a fast memorising one [54 , 34 ] , linking grokking to double descent and emergent abilities [9 , 21 , 28 ] , with phase-transition, statistical, basin-selection, and capacity variants [7 , 6 , 8 , 45 , 29 ] . Provable results include generalisation guarantees for bounded-norm quadratic networks on modular addition [36 ] and delay bounds in ridge regression [58 ] . Gu et al. [17 ] separately analyse the accuracy ceiling and embedding dynamics; Appendix E.2 discusses their ceiling and transition-time measurements. Our setting fixes a ReLU architecture and a uniform mask law, compares Latin colourings up to relabelling, and quantifies over every minimum-norm response. These choices specify the scope of our endpoint guarantees.
Latin-Square Tasks and the Endpoint Set
This section builds the objects the introduction used informally: the task and its observed part, the endpoint set, its three phases, and the relabelling invariance that makes the phase a property of the task rather than of its presentation.
Tasks, masks, and three coordinates
Let q ≥ 2 q \ge2 q ≥ 2 [ q ] = { 0 , … , q − 1 } [q] = \{0,\ldots,q-1\} [ q ] = { 0 , … , q − 1 } X q = [ q ] 2 X_q = [q]^2 X q = [ q ] 2 N = q 2 N = q^2 N = q 2 C : X q → [ q ] C : X_q \to[q] C : X q → [ q ] C q \mathcal{C}_q C q Latin when every symbol occurs exactly once in each row and each column; L q ⊂ C q \mathcal{L}_q \subset\mathcal{C}_q L q ⊂ C q q q q q q q C q a d d ( u , v ) = u + v ( m o d q ) C_q^{\mathrm{add}}(u,v) = u+v \pmod q C q add ( u , v ) = u + v ( mod q )
Fix α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 )
Ω ∼ ν q : = Unif { Ω ′ ⊆ X q : ∣ Ω ′ ∣ = ⌊ α N ⌋ } , T = X q ∖ Ω ; (1) \Omega\sim\nu_q := \operatorname{Unif}\{\Omega' \subseteq X_q : |\Omega'| = \lfloor\alpha N \rfloor\}, \qquad T = X_q \setminus\Omega; \tag*{(1)} Ω ∼ ν q := Unif { Ω ′ ⊆ X q : ∣ Ω ′ ∣ = ⌊ α N ⌋} , T = X q ∖ Ω ; (1) T T T D ( C , Ω ) = { ( u , v , C ( u , v ) ) : ( u , v ) ∈ Ω } \mathcal{D}(C,\Omega) = \{(u,v,C(u,v)) : (u,v) \in\Omega\} D ( C , Ω ) = {( u , v , C ( u , v )) : ( u , v ) ∈ Ω } α \alpha α
Proposition 3.1 (Two coordinates, and a third at prime-power order). For every q ≥ 2 q \ge2 q ≥ 2 C ∈ C q C \in\mathcal{C}_q C ∈ C q q q q K q , q K_{q,q} K q , q C ( u , v ) C(u,v) C ( u , v ) U u V v U_uV_v U u V v q q q [ q ] [q] [ q ] F q \mathbb{F}_q F q P C ∈ F q [ X , Y ] P_C \in\mathbb{F}_q[X,Y] P C ∈ F q [ X , Y ] deg X P C , deg Y P C ≤ q − 1 \deg_X P_C,\deg_Y P_C \le q-1 deg X P C , deg Y P C ≤ q − 1 P C ( u , v ) = C ( u , v ) P_C(u,v)=C(u,v) P C ( u , v ) = C ( u , v ) C C C
The minimum-norm endpoint set
The model is a bias-free one-hidden-layer ReLU network with a separate embedding table for each input, E U , E V : [ q ] → R d q E_U,E_V : [q] \to\mathbb{R}^{d_q} E U , E V : [ q ] → R d q W ∈ R h q × d q W \in\mathbb{R}^{h_q \times d_q} W ∈ R h q × d q A ∈ R q × h q A \in\mathbb{R}^{q \times h_q} A ∈ R q × h q d q = 2 q + 1 d_q = 2q+1 d q = 2 q + 1 h q = q 2 h_q = q^2 h q = q 2 θ = ( E U , E V , W , A ) \theta=(E_U,E_V,W,A) θ = ( E U , E V , W , A )
F θ ( u , v ) = A ReLU ( W ( E U ( u ) + E V ( v ) ) ) ∈ R q , ∥ θ ∥ 2 = ∥ E U ∥ F 2 + ∥ E V ∥ F 2 + ∥ W ∥ F 2 + ∥ A ∥ F 2 . (2) F_\theta(u,v)=A\operatorname{ReLU}(W(E_U(u)+E_V(v))) \in\mathbb{R}^q,\qquad\|\theta\|^2=\|E_U\|_F^2+\|E_V\|_F^2+\|W\|_F^2+\|A\|_F^2. \tag*{(2)} F θ ( u , v ) = A ReLU ( W ( E U ( u ) + E V ( v ))) ∈ R q , ∥ θ ∥ 2 = ∥ E U ∥ F 2 + ∥ E V ∥ F 2 + ∥ W ∥ F 2 + ∥ A ∥ F 2 . (2) As a function class the pair embedding contains the common design that shares one table E E E [ E ( u ) ; E ( v ) ] [E(u);E(v)] [ E ( u ) ; E ( v )] W [ E ( u ) ; E ( v ) ] = W 1 E ( u ) + W 2 E ( v ) W[E(u);E(v)]=W_1E(u)+W_2E(v) W [ E ( u ) ; E ( v )] = W 1 E ( u ) + W 2 E ( v ) endpoint set of an observed dataset is the set of global minimisers of the parameter norm under unit margins on the observed cells,
S q ( D ) = arg min θ 1 2 ∥ θ ∥ 2 s.t. F θ , y ( u , v ) ≥ 1 + max a ≠ y F θ , a ( u , v ) ( ( u , v , y ) ∈ D ) . (3) \mathcal{S}_q(\mathcal{D})=\underset{\theta}{\arg\min}\ \frac{1}{2}\|\theta\|^2\quad\text{s.t.}\quad F_{\theta,y}(u,v)\ge1+\max_{a\ne y}F_{\theta,a}(u,v)\qquad((u,v,y)\in\mathcal{D}). \tag*{(3)} S q ( D ) = θ arg min 2 1 ∥ θ ∥ 2 s.t. F θ , y ( u , v ) ≥ 1 + a = y max F θ , a ( u , v ) (( u , v , y ) ∈ D ) . (3) Max-margin and implicit-bias results for homogeneous networks motivate this as the idealised late-training object ([46 , 30 , 39 ] ). S q ( D ) \mathcal{S}_q(\mathcal{D}) S q ( D ) Ω \Omega Ω T T T § 8 .§ 2 treats the extension to L 2 L_2 L 2
Three of the four parameter blocks can be folded into one matrix, which is the form the proofs work with. Assemble Φ = [ E U ( 0 ) , … , E U ( q − 1 ) , E V ( 0 ) , … , E V ( q − 1 ) ] ∈ R d q × 2 q \Phi=[E_U(0),\ldots,E_U(q-1),E_V(0),\ldots,E_V(q-1)]\in\mathbb{R}^{d_q\times2q} Φ = [ E U ( 0 ) , … , E U ( q − 1 ) , E V ( 0 ) , … , E V ( q − 1 )] ∈ R d q × 2 q Z = W Φ Z=W\Phi Z = W Φ ξ ( u , v ) = e u + e q + v ∈ R 2 q \xi_{(u,v)}=e_u+e_{q+v}\in\mathbb{R}^{2q} ξ ( u , v ) = e u + e q + v ∈ R 2 q F θ ( x ) = A ReLU ( Z ξ x ) F_\theta(x)=A\operatorname{ReLU}(Z\xi_x) F θ ( x ) = A ReLU ( Z ξ x ) ( A , Z ) (A,Z) ( A , Z ) reduced representation and define
J ( F ) = inf { ∥ A ∥ F ∥ Z ∥ ∗ : F = A ReLU ( Z ξ ) , any finite width } , J(F)=\inf\{\|A\|_F\|Z\|_*:F=A\operatorname{ReLU}(Z\xi),\ \text{any finite width}\}, J ( F ) = inf { ∥ A ∥ F ∥ Z ∥ ∗ : F = A ReLU ( Z ξ ) , any finite width } , J ∗ = min { ∥ A ∥ F ∥ Z ∥ ∗ : Z ∈ R h q × 2 q , A ReLU ( Z ξ ) meets the margins of (3) } . (4) J_*=\min\{\|A\|_F\|Z\|_*:Z\in\mathbb{R}^{h_q\times2q},\ A\operatorname{ReLU}(Z\xi)\text{ meets the margins of (3)}\}. \tag*{(4)} J ∗ = min { ∥ A ∥ F ∥ Z ∥ ∗ : Z ∈ R h q × 2 q , A ReLU ( Z ξ ) meets the margins of (3) } . (4) Lemma 3.2 (Reduced normalisation). The optimal value of (3) is V ∗ = 3 2 J ∗ 2 / 3 V_*=\frac{3}{2}J_*^{2/3} V ∗ = 2 3 J ∗ 2/3 ∥ A ∥ F 2 = ∥ W ∥ F 2 = ∥ Φ ∥ F 2 = J ∗ 2 / 3 \|A\|_F^2=\|W\|_F^2=\|\Phi\|_F^2=J_*^{2/3} ∥ A ∥ F 2 = ∥ W ∥ F 2 = ∥Φ ∥ F 2 = J ∗ 2/3 ∥ A ∥ F ∥ W Φ ∥ ∗ = J ∗ \|A\|_F\|W\Phi\|_*=J_* ∥ A ∥ F ∥ W Φ ∥ ∗ = J ∗
In words: the nuclear norm of Z Z Z ∥ A ∥ F ∥ Z ∥ ∗ \|A\|_F\|Z\|_* ∥ A ∥ F ∥ Z ∥ ∗
Phases of the endpoint set and the phase profile
Fix C C C Ω \Omega Ω S q = S q ( D ( C , Ω ) ) S_q = S_q(\mathcal{D}(C,\Omega)) S q = S q ( D ( C , Ω ))
Acc T ( θ ; C ) = 1 ∣ T ∣ ∑ x ∈ T 1 { F θ , C ( x ) ( x ) > max a ≠ C ( x ) F θ , a ( x ) } , A q + = max S q Acc T , A q − = min S q Acc T . (5) \operatorname{Acc}_{T}(\theta;C)=\frac{1}{|T|}\sum_{x\in T}\mathbf{1}\left\{F_{\theta,C(x)}(x)>\max_{a\ne C(x)}F_{\theta,a}(x)\right\},\qquad A_q^+=\max_{S_q}\operatorname{Acc}_{T},\quad A_q^-=\min_{S_q}\operatorname{Acc}_{T}. \tag*{(5)} Acc T ( θ ; C ) = ∣ T ∣ 1 x ∈ T ∑ 1 { F θ , C ( x ) ( x ) > a = C ( x ) max F θ , a ( x ) } , A q + = S q max Acc T , A q − = S q min Acc T . (5) For a threshold τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) S q S_q S q
all-good : A q − ≥ τ , mixed : A q + ≥ τ > A q − , no-good : A q + < τ . (6) \text{all-good}:~A_q^-\ge\tau,\qquad\text{mixed}:~A_q^+\ge\tau>A_q^-,\qquad\text{no-good}:~A_q^+<\tau. \tag*{(6)} all-good : A q − ≥ τ , mixed : A q + ≥ τ > A q − , no-good : A q + < τ . (6) Write G q , τ ∀ G_{q,\tau}^{\forall} G q , τ ∀ G q , τ m i x G_{q,\tau}^{\mathrm{mix}} G q , τ mix G q , τ ∅ G_{q,\tau}^{\varnothing} G q , τ ∅ G q , τ ∃ = G q , τ ∀ + G q , τ m i x G_{q,\tau}^{\exists}=G_{q,\tau}^{\forall}+G_{q,\tau}^{\mathrm{mix}} G q , τ ∃ = G q , τ ∀ + G q , τ mix ⋆ ∈ { ∀ , m i x , ∅ , ∃ } \star\in\{\forall,\mathrm{mix},\varnothing,\exists\} ⋆ ∈ { ∀ , mix , ∅ , ∃ }
p q , τ ⋆ ( C ) = E Ω ∼ ν q [ G q , τ ⋆ ( C , Ω ) ] , Π q , τ ( C ) = ( p q , τ ∀ ( C ) , p q , τ m i x ( C ) , p q , τ ∅ ( C ) ) . (7) p_{q,\tau}^{\star}(C)=\mathbb{E}_{\Omega\sim\nu_q}\left[G_{q,\tau}^{\star}(C,\Omega)\right],\qquad\Pi_{q,\tau}(C)=\left(p_{q,\tau}^{\forall}(C),p_{q,\tau}^{\mathrm{mix}}(C),p_{q,\tau}^{\varnothing}(C)\right). \tag*{(7)} p q , τ ⋆ ( C ) = E Ω ∼ ν q [ G q , τ ⋆ ( C , Ω ) ] , Π q , τ ( C ) = ( p q , τ ∀ ( C ) , p q , τ mix ( C ) , p q , τ ∅ ( C ) ) . (7) Proposition 3.3 (Phase decomposition). S q ( D ) S_q(\mathcal{D}) S q ( D ) non-empty for every C ∈ C q C\in\mathcal{C}_q C ∈ C q Ω ⊆ X q \Omega\subseteq X_q Ω ⊆ X q τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) Π q , τ ( C ) \Pi_{q,\tau}(C) Π q , τ ( C ) Δ 2 = { ( a , b , c ) ∈ [ 0 , 1 ] 3 : a + b + c = 1 } \Delta_2=\{(a,b,c)\in[0,1]^3:a+b+c=1\} Δ 2 = {( a , b , c ) ∈ [ 0 , 1 ] 3 : a + b + c = 1 }
The threshold only decides where an instance falls; the extremes A q − ≤ A q + A_q^-\le A_q^+ A q − ≤ A q + A q − A_q^- A q − A q − A_q^- A q − A q + A_q^+ A q + § 8 .§ 1 ).
Invariance: the profile lives on colouring orbits
Permuting rows, columns, or symbols, or exchanging the two inputs, changes how a table is written and nothing about the learning problem. The formal name for this equivalence is colouring isomorphism (for Latin squares, isotopy together with transposition); the paper calls it relabelling.
Definition 3.4 (Colouring isomorphism). C ∼ q C ′ C\sim_q C' C ∼ q C ′ ρ , κ , γ ∈ S q \rho,\kappa,\gamma\in S_q ρ , κ , γ ∈ S q C ′ ( u , v ) = γ ( C ( ρ ( u ) , κ ( v ) ) ) C'(u,v)=\gamma(C(\rho(u),\kappa(v))) C ′ ( u , v ) = γ ( C ( ρ ( u ) , κ ( v ))) u , v u,v u , v C ′ ( u , v ) = γ ( C ( κ ( v ) , ρ ( u ) ) ) C'(u,v)=\gamma(C(\kappa(v),\rho(u))) C ′ ( u , v ) = γ ( C ( κ ( v ) , ρ ( u ))) u , v u,v u , v Q ‾ q = C q / ∼ q \overline{\mathcal{Q}}_q=\mathcal{C}_q/\sim_q Q q = C q / ∼ q Q q = L q / ∼ q \mathcal{Q}_q=\mathcal{L}_q/\sim_q Q q = L q / ∼ q
Theorem 3.5 (Quotient invariance). Let C ∼ q C ′ C\sim_q C' C ∼ q C ′ p q , τ ∀ p_{q,\tau}^{\forall} p q , τ ∀ p q , τ m i x p_{q,\tau}^{\mathrm{mix}} p q , τ mix p q , τ ∅ p_{q,\tau}^{\varnothing} p q , τ ∅ p q , τ ∃ p_{q,\tau}^{\exists} p q , τ ∃ Π q , τ \Pi_{q,\tau} Π q , τ Q ‾ q \overline{\mathcal{Q}}_q Q q Q q \mathcal{Q}_q Q q τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 )
The proof is short: relabelling the task amounts to permuting the entries of the two embedding tables and the rows of the head, and swapping the two tables under transposition, and each of these moves preserves the norm, the margin constraints, and cellwise correctness. The consequence is that the profile becomes a function on orbits, the classification map
Q q ⟶ Δ 2 , [ C ] ⟼ Π q , τ ( [ C ] ) , (8) \mathcal{Q}_q\longrightarrow\Delta_2,\qquad[C]\longmapsto\Pi_{q,\tau}([C]), \tag*{(8)} Q q ⟶ Δ 2 , [ C ] ⟼ Π q , τ ([ C ]) , (8) which is the object classified in the rest of the paper. One consequence deserves to be seen before the full proof (Appendix § 9 .§ 2 ): the support size and degree of the polynomial coordinate are not orbit invariants, so every relabelled representative γ ( ρ ( u ) + κ ( v ) ) \gamma(\rho(u)+\kappa(v)) γ ( ρ ( u ) + κ ( v )) C q a d d C_q^{\mathrm{add}} C q add
Dense representatives of addition grok. Figure 2 is the invariance theorem seen from the data side. Ten random relabellings ( ρ , κ , γ ) (\rho,\kappa,\gamma) ( ρ , κ , γ ) C q a d d C_q^{\mathrm{add}} C q add q = 97 q=97 q = 97
both statistics, while their orbit is still that of C q a d d C_q^{\mathrm{add}} C q add § 10 .§ 3 ). At this order, these runs support a stable final outcome with variable delay; they do not certify membership in S q S_q S q
Two Poles of the Latin Quotient
Informal Results. The objects of the previous section turn the question of the introduction into a map: each relabelling orbit of Latin colourings is sent to its phase profile, a point of the triangle whose corners are all-good, mixed, and no-good. Which orbits sit at the all-good corner? Which carry mixed mass? And where does the orbit of a uniformly random Latin colouring sit? Our results answer the first for every abelian group family and the third in its all-good coordinate, with the observation fraction and the success threshold held fixed while the order grows.
Part (i) concerns every endpoint of each task in a structured family; part (ii) concerns every learner under a random task law. The latter controls the all-good coordinate, leaving open whether a typical colouring has some good endpoint.
The main results
We prove cyclic addition first and obtain every abelian group from it as a corollary, rather than proving the general statement directly: both proofs share one method, a carrier and a notch; the notch is insensitive to the colouring, and only the characters that build the carrier change from Z q \mathbb{Z}_q Z q task ensemble is a sequence M = ( μ q ) q \mathsf{M}=(\mu_q)_q M = ( μ q ) q L q \mathcal{L}_q L q M a d d = ( δ C q a d d ) q \mathsf{M}_{\mathrm{add}}=(\delta_{C_q^{\mathrm{add}}})_q M add = ( δ C q add ) q M u n i f = ( Unif ( L q ) ) q \mathsf{M}_{\mathrm{unif}}=(\operatorname{Unif}(\mathcal{L}_q))_q M unif = ( Unif ( L q ) ) q learner A q A_q A q X q X_q X q X q → R q X_q\to\mathbb{R}^q X q → R q Acc T \operatorname{Acc}_{\mathsf{T}} Acc T C ∼ μ q C\sim\mu_q C ∼ μ q Ω ∼ ν q \Omega\sim\nu_q Ω ∼ ν q
P q , τ ∗ ( M ) = E C ∼ μ q [ p q , τ ∗ ( C ) ] , P q , τ A ( M ) = P [ Acc T ( A q ( D ( C , Ω ) ) ; C ) ≥ τ ] . (9) P^*_{q,\tau}(\mathsf{M})=\mathbb{E}_{C\sim\mu_q}\left[p^*_{q,\tau}(C)\right],\qquad
P^A_{q,\tau}(\mathsf{M})=\mathbb{P}\left[\operatorname{Acc}_{\mathsf{T}}(A_q(D(C,\Omega));C)\ge\tau\right]. \tag*{(9)} P q , τ ∗ ( M ) = E C ∼ μ q [ p q , τ ∗ ( C ) ] , P q , τ A ( M ) = P [ Acc T ( A q ( D ( C , Ω )) ; C ) ≥ τ ] . (9) A selector is a learner with A q ( D ) = F θ A_q(\mathcal{D})=F_\theta A q ( D ) = F θ θ ∈ S q ( D ) \theta\in S_q(\mathcal{D}) θ ∈ S q ( D ) S q ( D ) S_q(\mathcal{D}) S q ( D )
Theorem 4.1 (Cyclic prototype and uniform obstruction). Fix α , τ ∈ ( 0 , 1 ) \alpha,\tau\in(0,1) α , τ ∈ ( 0 , 1 ) q → ∞ q\to\infty q → ∞
(Addition is all-good.) The worst endpoint accuracy converges to one in probability over the mask,
A q ( C q a d d , Ω ) → P 1 , hence P q , τ ∀ ( M a d d ) → 1 and Π q , τ ( [ C q a d d ] ) → ( 1 , 0 , 0 ) . (10) A_q(C_q^{\mathrm{add}},\Omega)\xrightarrow{\mathbb{P}}1,\qquad\text{hence}\quad P^{\forall}_{q,\tau}(\mathsf{M}_{\mathrm{add}})\to1\quad\text{and}\quad\Pi_{q,\tau}([C_q^{\mathrm{add}}])\to(1,0,0). \tag*{(10)} A q ( C q add , Ω ) P 1 , hence P q , τ ∀ ( M add ) → 1 and Π q , τ ([ C q add ]) → ( 1 , 0 , 0 ) . (10) (Uniform Latin squares defeat every learner.) *Uniformly over all learners A q A_q A q
P q , τ A ( M u n i f ) ≤ ( 2 e 2 ) N q − τ ( 1 − α ) N → 0 , (11) P^A_{q,\tau}(\mathsf{M}_{\mathrm{unif}})\le(2e^2)^N q^{-\tau(1-\alpha)N}\to0, \tag*{(11)} P q , τ A ( M unif ) ≤ ( 2 e 2 ) N q − τ ( 1 − α ) N → 0 , (11) hence P q , τ ∇ ( M u n i f ) → 0 P^{\nabla}_{q,\tau}(\mathrm{Munif}) \to0 P q , τ ∇ ( Munif ) → 0 P C ∼ Unif ( L q ) [ p q , τ ∇ ( C ) ≥ ε ] → 0 \mathbb{P}_{C\sim\operatorname{Unif}(L_q)}[p^{\nabla}_{q,\tau}(C) \ge\varepsilon] \to0 P C ∼ Unif ( L q ) [ p q , τ ∇ ( C ) ≥ ε ] → 0 ε > 0 \varepsilon> 0 ε > 0
The two parts are proved in the next two subsections. The second part is pure counting and never looks at the model; the phase enters only through the observation that on an all-good instance every selector succeeds, so P q , τ ∇ ( M u n i f ) ≤ P q , τ △ ( M u n i f ) P^{\nabla}_{q,\tau}(\mathrm{Munif}) \le P^{\triangle}_{q,\tau}(\mathrm{Munif}) P q , τ ∇ ( Munif ) ≤ P q , τ △ ( Munif ) q q q C q C_q C q q q q exp ( − N [ τ ( 1 − α ) log q − log 2 e 2 ] ) \exp\left(-N[\tau(1-\alpha)\log q-\log2e^2]\right) exp ( − N [ τ ( 1 − α ) log q − log 2 e 2 ] ) q τ ( 1 − α ) > 2 e 2 q^{\tau(1-\alpha)} > 2e^2 q τ ( 1 − α ) > 2 e 2
Addition: a carrier and a notch
The all-good pole rests on two lemmas. The first exhibits a cheap network that computes the whole addition table with a comfortable margin; the second says that, with high probability over the observed cells, no cheap network can agree with the observations and still be confidently wrong on a constant fraction of the table.
Lemma 4.2 (Addition carrier). There is an absolute constant C 0 C_0 C 0 q q q F q ⋆ = A c a r ReLU ( Z c a r ξ ⋅ ) F_q^\star=A_{\mathrm{car}}\operatorname{ReLU}(Z_{\mathrm{car}}\xi_\cdot) F q ⋆ = A car ReLU ( Z car ξ ⋅ ) w q = O ( log q ) w_q=O(\log q) w q = O ( log q ) x ∈ X q x\in X_q x ∈ X q a ≠ C q a d d ( x ) a\ne C_q^{\mathrm{add}}(x) a = C q add ( x )
1 ≤ F q , C q a d d ⋆ ( x ) − F q , a ⋆ ( x ) ≤ 9 , J c a r : = ∥ A c a r ∥ F ∥ Z c a r ∥ ∗ ≤ C 0 q log q . (12) 1 \le F_{q,C_q^{\mathrm{add}}}^\star(x)-F_{q,a}^\star(x)\le9,\qquad J_{\mathrm{car}}:=\lVert A_{\mathrm{car}}\rVert_F\lVert Z_{\mathrm{car}}\rVert_\ast\le C_0q\sqrt{\log q}. \tag*{(12)} 1 ≤ F q , C q add ⋆ ( x ) − F q , a ⋆ ( x ) ≤ 9 , J car := ∥ A car ∥ F ∥ Z car ∥ ∗ ≤ C 0 q log q . (12) The carrier is the Fourier-multiplication circuit of the interpretability literature, made explicit and costed. Roughly log q \log q log q O ( q log q ) O(q\sqrt{\log q}) O ( q log q )
Lemma 4.3 (One-sided notch). Fix α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) B q B_q B q B q 2 log q / q 5 / 2 → 0 B_q^2\log q/q^{5/2}\to0 B q 2 log q / q 5/2 → 0 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) Ω ∼ ν q \Omega\sim\nu_q Ω ∼ ν q D ( x ) = A ReLU ( Z ξ x ) D(x)=A\operatorname{ReLU}(Z\xi_x) D ( x ) = A ReLU ( Z ξ x ) ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q \lVert A\rVert_F\lVert Z\rVert_\ast\le B_q ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q
D y ( x ) ( x ) − D a ( x ) ≥ 0 D_{y(x)}(x)-D_a(x)\ge0 D y ( x ) ( x ) − D a ( x ) ≥ 0 x ∈ Ω x\in\Omega x ∈ Ω a ≠ y ( x ) a\ne y(x) a = y ( x ) y ( x ) = C q a d d ( x ) y(x)=C_q^{\mathrm{add}}(x) y ( x ) = C q add ( x )
at least β N \beta N β N x x x a ( x ) ≠ y ( x ) a(x)\ne y(x) a ( x ) = y ( x ) D a ( x ) ( x ) − D y ( x ) ( x ) ≥ 1 D_{a(x)}(x)-D_{y(x)}(x)\ge1 D a ( x ) ( x ) − D y ( x ) ( x ) ≥ 1
Both names are descriptive: the carrier carries the whole table at a known cost, and the notch is the region of the norm–error plane the lemma cuts out, cheap tables that fit the observations yet err confidently on a constant fraction of cells. The difficulty is that D D D after the mask is seen, and the proof meets it in three steps. Before the mask is drawn it fixes a finite atlas H q \mathcal{H}_q H q N N N Z Z Z q \sqrt q q [62 , 25 ] , and counting the sign patterns of the resulting polynomial gates [5 ] give ∣ H q ∣ = exp ( o ( N ) ) |\mathcal{H}_q|=\exp(o(N)) ∣ H q ∣ = exp ( o ( N )) B q B_q B q β N / 2 \beta N/2 β N /2 e − c N e^{-cN} e − c N
P ( ∃ harmful low-norm table ) ≤ ∣ H q ∣ e − c N = exp ( log ∣ H q ∣ − c N ) ⟶ 0 , (13) \mathbb{P}(\exists\ \text{harmful low-norm table})\le|\mathcal{H}_q|e^{-cN}=\exp(\log|\mathcal{H}_q|-cN)\longrightarrow0, \tag*{(13)} P ( ∃ harmful low-norm table ) ≤ ∣ H q ∣ e − c N = exp ( log ∣ H q ∣ − c N ) ⟶ 0 , (13) the carrier serving only to put every endpoint inside the budget B q B_q B q
Proof of Theorem 4.1(i). Padded with zero hidden rows to width N N N ( A c a r , Z c a r ) (A_{\mathrm{car}},Z_{\mathrm{car}}) ( A car , Z car ) J ∗ J_\ast J ∗ J ∗ ≤ J c a r ≤ C 0 q log q J_\ast\le J_{\mathrm{car}}\le C_0q\sqrt{\log q} J ∗ ≤ J car ≤ C 0 q log q F F F N N N ( A F , Z F ) (A_F,Z_F) ( A F , Z F ) ∥ A F ∥ F ∥ Z F ∥ ∗ = J ∗ \lVert A_F\rVert_F\lVert Z_F\rVert_\ast=J_\ast ∥ A F ∥ F ∥ Z F ∥ ∗ = J ∗ D = 9 F − F q ⋆ D=9F-F_q^\star D = 9 F − F q ⋆ y ( x ) = C q a d d ( x ) y(x)=C_q^{\mathrm{add}}(x) y ( x ) = C q add ( x ) F y − F a ≥ 1 F_y-F_a\ge1 F y − F a ≥ 1 D y − D a ≥ 0 D_y-D_a\ge0 D y − D a ≥ 0 F a ≥ F y F_a\ge F_y F a ≥ F y D a − D y ≥ 1 D_a-D_y\ge1 D a − D y ≥ 1 A ~ = [ 3 A F − A c a r ] \widetilde{A}=[3A_F-A_{\mathrm{car}}] A = [ 3 A F − A car ] Z ~ = [ 3 Z F ; Z c a r ] \widetilde{Z}=[3Z_F;Z_{\mathrm{car}}] Z = [ 3 Z F ; Z car ] D D D ∥ A ~ ∥ F 2 = 9 J ∗ + J c a r \lVert\widetilde{A}\rVert_F^2=9J_*+J_{\mathrm{car}} ∥ A ∥ F 2 = 9 J ∗ + J car ∥ Z ~ ∥ ∗ ≤ 3 J ∗ + J c a r ≤ 2 9 J ∗ + J c a r \lVert\widetilde{Z}\rVert_*\le3\sqrt{J_*}+\sqrt{J_{\mathrm{car}}}\le\sqrt{2}\sqrt{9J_*+J_{\mathrm{car}}} ∥ Z ∥ ∗ ≤ 3 J ∗ + J car ≤ 2 9 J ∗ + J car
J ( D ) ≤ ∥ A ~ ∥ F ∥ Z ~ ∥ ∗ ≤ 2 ( 9 J ∗ + J c a r ) ≤ 10 2 C 0 q log q = : B q . (14) J(D)\le\lVert\widetilde{A}\rVert_F\lVert\widetilde{Z}\rVert_*\le\sqrt{2}(9J_*+J_{\mathrm{car}})\le10\sqrt{2}\,C_0q\sqrt{\log q}=:B_q. \tag*{(14)} J ( D ) ≤ ∥ A ∥ F ∥ Z ∥ ∗ ≤ 2 ( 9 J ∗ + J car ) ≤ 10 2 C 0 q log q =: B q . (14) Then B q 2 log q / q 5 / 2 = O ( ( log q ) 2 / q ) → 0 B_q^2\log q/q^{5/2}=O((\log q)^2/\sqrt{q})\to0 B q 2 log q / q 5/2 = O (( log q ) 2 / q ) → 0 N + w q N+w_q N + w q Acc T < τ \operatorname{Acc}_T<\tau Acc T < τ ( 1 − τ ) ∣ T ∣ ≥ ( 1 − τ ) ( 1 − α ) N (1-\tau)|T|\ge(1-\tau)(1-\alpha)N ( 1 − τ ) ∣ T ∣ ≥ ( 1 − τ ) ( 1 − α ) N β = 1 2 ( 1 − τ ) ( 1 − α ) \beta=\frac{1}{2}(1-\tau)(1-\alpha) β = 2 1 ( 1 − τ ) ( 1 − α ) D D D 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) A q − ( C q a d d , Ω ) ≥ τ A_q^-(C_q^{\mathrm{add}},\Omega)\ge\tau A q − ( C q add , Ω ) ≥ τ τ < 1 \tau<1 τ < 1 A q − → P 1 A_q^-\mathrel{\xrightarrow{\mathrm{P}}}1 A q − P 1
Corollary 4.4 (Abelian group families are all-good). Let ( G q ) q (G_q)_q ( G q ) q ∣ G q ∣ = q → ∞ |G_q|=q\to\infty ∣ G q ∣ = q → ∞ [ q ] [q] [ q ] C G q ( u , v ) = u + v C_{G_q}(u,v)=u+v C G q ( u , v ) = u + v α , τ ∈ ( 0 , 1 ) \alpha,\tau\in(0,1) α , τ ∈ ( 0 , 1 )
A q − ( C G q , Ω ) → P 1 , Π q , τ ( [ C G q ] ) → ( 1 , 0 , 0 ) . (15) A_q^-(C_{G_q},\Omega)\xrightarrow{\mathrm{P}}1,\qquad\Pi_{q,\tau}([C_{G_q}])\to(1,0,0). \tag*{(15)} A q − ( C G q , Ω ) P 1 , Π q , τ ([ C G q ]) → ( 1 , 0 , 0 ) . (15) The conclusion holds for every relabelled representative.
:::
Cyclic frequencies are the characters of Z q \mathbb{Z}_q Z q G q G_q G q O ( log q ) O(\log q) O ( log q ) [ 1 , 9 ] [1,9] [ 1 , 9 ] O ( q log q ) O(q\sqrt{\log q}) O ( q log q ) § 11 .§ 3.1 and § 11 .§ 3.2 .
Uniform Latin squares: a counting bound
Lemma 4.5 (Counting). Let n q = ⌊ α N ⌋ n_q=\lfloor\alpha N\rfloor n q = ⌊ α N ⌋ r = ⌊ ( 1 − τ ) ( N − n q ) ⌋ r=\lfloor(1-\tau)(N-n_q)\rfloor r = ⌊( 1 − τ ) ( N − n q )⌋ A q A_q A q
(a) P q , τ A ( M u n i f ) ≤ q n q ∑ i = 0 r ( N − n q i ) ( q − 1 ) i ∣ L q ∣ , (b) ∣ L q ∣ ≥ ( q ! ) 2 q q q 2 ≥ ( q e 2 ) q 2 . (16) \begin{aligned}
\text{(a)}\quad P^A_{q,\tau}(M_{\mathrm{unif}})&\le\frac{q^{n_q}\sum_{i=0}^{r}\binom{N-n_q}{i}(q-1)^i}{|\mathcal{L}_q|},\\
\text{(b)}\quad|\mathcal{L}_q|&\ge\frac{(q!)^{2q}}{q^{q^2}}\ge\left(\frac{q}{e^2}\right)^{q^2}. \tag*{(16)}
\end{aligned} (a) P q , τ A ( M unif ) (b) ∣ L q ∣ ≤ ∣ L q ∣ q n q ∑ i = 0 r ( i N − n q ) ( q − 1 ) i , ≥ q q 2 ( q ! ) 2 q ≥ ( e 2 q ) q 2 . (16) The uniform pole needs no geometry. Part (a) fixes the mask, notes that the observed labels can take at most q n q q^{n_q} q n q r r r [10 , 18 ] (Falikman 1981)); the bound is essentially sharp, since ∣ L q ∣ = ( ( 1 + o ( 1 ) ) q / e 2 ) q 2 |\mathcal{L}_q|=((1+o(1))q/e^2)^{q^2} ∣ L q ∣ = (( 1 + o ( 1 )) q / e 2 ) q 2 [53 ] ). The ratio of the two counts is the theorem.
Proof of Theorem 4.1(ii). Since ∑ i ≤ r ( N − n q i ) ( q − 1 ) i ≤ 2 N q r \sum_{i\le r}\binom{N-n_q}{i}(q-1)^i\le2^Nq^r ∑ i ≤ r ( i N − n q ) ( q − 1 ) i ≤ 2 N q r N − n q − r ≥ τ ( N − n q ) ≥ τ ( 1 − α ) N N-n_q-r\ge\tau(N-n_q)\ge\tau(1-\alpha)N N − n q − r ≥ τ ( N − n q ) ≥ τ ( 1 − α ) N P q , τ A ( M u n i f ) ≤ 2 N e 2 N q − τ ( 1 − α ) N P^A_{q,\tau}(M_{\mathrm{unif}})\le2^Ne^{2N}q^{-\tau(1-\alpha)N} P q , τ A ( M unif ) ≤ 2 N e 2 N q − τ ( 1 − α ) N A q A_q A q P q , τ ∃ ( M u n i f ) ≤ P q , τ A ( M u n i f ) P^\exists_{q,\tau}(M_{\mathrm{unif}})\le P^A_{q,\tau}(M_{\mathrm{unif}}) P q , τ ∃ ( M unif ) ≤ P q , τ A ( M unif )
Remark 4.6 (Biases). With hidden bias b b b c c c O ( q 7 / 6 ( log q ) 1 / 3 ) O(q^{7/6}(\log q)^{1/3}) O ( q 7/6 ( log q ) 1/3 ) B q 2 log q / q 5 / 2 → 0 B_q^2\log q/q^{5/2}\to0 B q 2 log q / q 5/2 → 0
Remark 4.7 (Vanishing observation fractions). Applying part (i) at α = 1 / k \alpha=1/k α = 1/ k 1 − 1 / k 1-1/k 1 − 1/ k 1 / k 1/k 1/ k α q ↓ 0 \alpha_q\downarrow0 α q ↓ 0 A q − ( C q a d d , Ω ) → P 1 A_q^-(C_q^{\mathrm{add}},\Omega)\xrightarrow{\mathrm{P}}1 A q − ( C q add , Ω ) P 1 α q ≫ ( log q ) 3 / q \alpha_q\gg(\log q)^3/\sqrt{q} α q ≫ ( log q ) 3 / q 0.33 0.33 0.33 q = 47 q=47 q = 47 0.20 0.20 0.20 q = 211 q=211 q = 211
Remark 4.8 (What part (ii) cannot open). The existential probability P q , τ ∃ ( M u n i f ) = P [ ∃ θ ∈ S q ( D ( C , Ω ) ) : Acc T ( θ ; C ′ ) ≥ τ ] P^\exists_{q,\tau}(M_{\mathrm{unif}})=\mathbb{P}[\exists\theta\in S_q(\mathcal{D}(C,\Omega)):\operatorname{Acc}_T(\theta;C')\ge\tau] P q , τ ∃ ( M unif ) = P [ ∃ θ ∈ S q ( D ( C , Ω )) : Acc T ( θ ; C ′ ) ≥ τ ] C ∼ Unif ( L q ) C\sim\operatorname{Unif}(\mathcal{L}_q) C ∼ Unif ( L q )
Beyond the Poles: Structured Families at Composite Order
At q = 64 = 2 6 q = 64 = 2^{6} q = 64 = 2 6 § 10 .§ 1 with label-stratified masks (distinct from ν q \nu_q ν q S q S_q S q C r C_r C r C 2 k C_2^k C 2 k R r R_r R r § 10 .§ 3 ), and products are direct products.
Group laws beyond cyclic addition. Every group-table run in Table 1 transitions; C 2 6 C_2^6 C 2 6 Table 3 ). C 8 × R 8 C_8 \times R_8 C 8 × R 8 § 11 .§ 3 ).
Table 1. Final trained predictors at q = 64 q=64 q = 64 § 10 .§ 1 ; 0.99 is a reporting cutoff unrelated to τ \tau τ
Table 3. Empirical observation threshold for modular addition. α ^ q \hat{\alpha}_q α ^ q ⌊ α ^ q q 2 ⌋ \lfloor\hat{\alpha}_q q^2\rfloor ⌊ α ^ q q 2 ⌋ (1) ; the implementation rounds, so realised sizes can differ by one cell.
Factor recovery with weak exact completion. The table C 2 × R 32 C_2 \times R_{32} C 2 × R 32 factor quotients : projections of predicted and true labels to product factors, distinct from the orbit quotient Q q Q_q Q q Figure 3 , left, replacing the cyclic residual C 32 C_{32} C 32 R 32 R_{32} R 32
Figure 3. Coarse factors are recovered before exact labels. Colour encodes label resolution: exact label and the prespecified 2-, 4-, 8-way factor quotients. Left: held-out accuracy at nominal 30% coverage (runs small, medians outlined). Right: nested masks at 20%, 30%, 40%; coarse factors saturate one coverage level before the exact label.
Coverage moves the recovered resolution. The nested-mask panels re-train the same task and optimisation seeds at increasing coverage. Coarse factors are recovered before exact labels, with the residual structure setting the required coverage: for C 2 3 × R 8 C_2^3 \times R_8 C 2 3 × R 8 § 10 .§ 4 ). Checkpoint trajectories, alternate factor directions, and probe interventions (Appendix § 10 .§ 5 ) confirm that the factor accuracies reflect structured label resolution, not exact hits alone.
These observations motivate carriers beyond abelian groups and for coarse factors. For the all-good limit, we propose the following robust necessity conjecture.
Conjecture 5.1 (Robust margin necessity). Let C q ∈ L q C_q \in\mathcal{L}_q C q ∈ L q q → ∞ q \to\infty q → ∞ A ˉ q ( C q , Ω ) → 1 \bar{A}_q(C_q,\Omega) \to1 A ˉ q ( C q , Ω ) → 1 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) C q C_q C q N = q 2 N = q^2 N = q 2 o ( N ) o(N) o ( N ) ∥ A c a r , q ∥ F ∥ Z c a r , q ∥ ∗ = o ( q 3 / 2 ) \lVert A_{\mathrm{car},q}\rVert_{\mathrm{F}}\lVert Z_{\mathrm{car},q}\rVert_* = o(q^{3/2}) ∥ A car , q ∥ F ∥ Z car , q ∥ ∗ = o ( q 3/2 )
Appendix § 11 .3.5 gives the precise formulation, motivation, and remaining proof gaps.
Conclusion
We study which task structures make the entire minimum-norm endpoint set generalise. Our carrier criterion guarantees this asymptotically for every finite abelian group family, whereas the uniform Latin ensemble defeats observation-based learners at fixed positive accuracy. Moreover, relabelling preserves endpoint generalisation despite changing polynomial complexity, making task structure central to this classification. Composite-order experiments further suggest recovery through coarse factors, without characterising the whole endpoint set. Together, these results connect grokking to the generalisation properties of its idealised endpoints, leaving carrier necessity and the mixed/no-good boundary as open questions.
AI Use Statement
Generative AI tools were used to improve the language and clarity of the manuscript, and to surface existing results in the literature that shortened the proofs. The authors located the original sources and verified each result in the form used; the external proof ingredients are stated explicitly in Appendix C.4.
Notation
Table 2 lists the symbols used throughout the main text. Appendix-local symbols are defined where they enter.
Table 2. Notation used in the main text. Appendix-local symbols are defined where they enter.
Supplementary Theory
This appendix contains the exact finite-instance criterion behind the phases, the bias extension of Theorem 4.1, an unstructured comparison bound, and a formal statement of the classification programme that the two poles leave open. Proofs are in Appendix C.
An exact criterion for a finite instance
Fix ( q , C , Ω ) (q,C,\Omega) ( q , C , Ω ) τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) N N N B ∈ R N × 2 q B \in\mathbb{R}^{N\times2q} B ∈ R N × 2 q H ( B ) H(B) H ( B ) x x x ReLU ( B ξ x ) \operatorname{ReLU}(B\xi_x) ReLU ( B ξ x ) S ∗ = { B : ∥ B ∥ ∗ = 1 } S_\ast= \{B : \lVert B\rVert_\ast= 1\} S ∗ = { B : ∥ B ∥ ∗ = 1 }
ρ ( B ) = min A ∥ A ∥ F s.t. ( e C ( x ) − e a ) ⊤ A H ( B ) x ≥ 1 ( x ∈ Ω , a ≠ C ( x ) ) , (17) \rho(B)=\min_A \lVert A\rVert_F \quad\text{s.t.}\quad(e_{C(x)}-e_a)^\top A H(B)_x \ge1 \quad(x\in\Omega,\ a\ne C(x)), \tag*{(17)} ρ ( B ) = A min ∥ A ∥ F s.t. ( e C ( x ) − e a ) ⊤ A H ( B ) x ≥ 1 ( x ∈ Ω , a = C ( x )) , (17) with ρ ( B ) = + ∞ \rho(B)=+\infty ρ ( B ) = + ∞ A A A g = min S ∗ ρ g=\min_{S_\ast}\rho g = min S ∗ ρ E g = { B ∈ S ∗ : ρ ( B ) = g } E_g=\{B\in S_\ast:\rho(B)=g\} E g = { B ∈ S ∗ : ρ ( B ) = g } B ∈ E g B\in E_g B ∈ E g A B A_B A B F B = A B H ( B ) F_B=A_BH(B) F B = A B H ( B ) m x ( B ) = F B , C ( x ) ( x ) − max a ≠ C ( x ) F B , a ( x ) m_x(B)=F_{B,C(x)}(x)-\max_{a\ne C(x)}F_{B,a}(x) m x ( B ) = F B , C ( x ) ( x ) − max a = C ( x ) F B , a ( x ) x ∈ T x\in T x ∈ T s ( B ) s(B) s ( B ) k k k k = ⌈ τ ∣ T ∣ ⌉ k=\lceil\tau|T|\rceil k = ⌈ τ ∣ T ∣ ⌉
s − , τ = min B ∈ E g s ( B ) , s + , τ = max B ∈ E g s ( B ) . (18) s_{-,\tau}=\min_{B\in E_g}s(B),\qquad s_{+,\tau}=\max_{B\in E_g}s(B). \tag*{(18)} s − , τ = B ∈ E g min s ( B ) , s + , τ = B ∈ E g max s ( B ) . (18) Theorem B.1 (Exact finite-instance criterion). E g E_g E g B ↦ F B B\mapsto F_B B ↦ F B E g E_g E g { F B : B ∈ E g } \{F_B:B\in E_g\} { F B : B ∈ E g }
all-good ⟺ s − , τ > 0 , mixed ⟺ s − , τ ≤ 0 < s + , τ , no-good ⟺ s + , τ ≤ 0. (19) \textit{all-good}\Longleftrightarrow s_{-,\tau}>0,\qquad
\textit{mixed}\Longleftrightarrow s_{-,\tau}\le0<s_{+,\tau},\qquad
\textit{no-good}\Longleftrightarrow s_{+,\tau}\le0. \tag*{(19)} all-good ⟺ s − , τ > 0 , mixed ⟺ s − , τ ≤ 0 < s + , τ , no-good ⟺ s + , τ ≤ 0. (19) A tie s = 0 s=0 s = 0
Proposition B.2 (The mixed phase is a degeneracy question). For fixed ( C , Ω ) (C,\Omega) ( C , Ω ) ( 0 , A q − ] (0,A_q^-] ( 0 , A q − ] ( A q − , A q + ) (A_q^-,A_q^+) ( A q − , A q + ) ( A q + , 1 ) (A_q^+,1) ( A q + , 1 )
∃ τ ∈ ( 0 , 1 ) with ( C , Ω ) mixed ⟺ Acc T ( ⋅ ; C ) is non-constant on { F B : B ∈ E g } . (20) \exists\tau\in(0,1)\ \text{with}\ (C,\Omega)\ \textit{mixed}\Longleftrightarrow\operatorname{Acc}_T(\,\cdot\,;C)\ \text{is non-constant on }\{F_B:B\in E_g\}. \tag*{(20)} ∃ τ ∈ ( 0 , 1 ) with ( C , Ω ) mixed ⟺ Acc T ( ⋅ ; C ) is non-constant on { F B : B ∈ E g } . (20) If the held-out accuracy of the minimum-norm response is almost surely constant along a family, then p q , τ m i x = 0 p_{q,\tau}^{\mathrm{mix}}=0 p q , τ mix = 0 Δ 2 \Delta_2 Δ 2 ( 1 , 0 , 0 ) (1,0,0) ( 1 , 0 , 0 ) ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 ) τ \tau τ
Two distinct responses of equal accuracy do not make an instance mixed, so (20) is strictly stronger than non-uniqueness of the minimum-norm response. A spread of accuracies across finite-training runs is not evidence of it either: such runs need not be global minimisers, and their spread is typically removable by changing the optimiser or regulariser. The natural source of the required degeneracy would be a nontrivial stabiliser of the observed data inside the isomorphism group of Definition 3.4 , which by Theorem 3.5 carries one global response to another; we expect that stabiliser to be trivial with high probability under the uniform mask law, and responses that respect a symmetry produce score ties, which (5) counts as errors.
L2-regularised biases
Add a hidden bias b ∈ R h q b \in\mathbb{R}^{h_q} b ∈ R h q c ∈ R q c \in\mathbb{R}^{q} c ∈ R q θ b = ( E U , E V , W , A , b , c ) \theta^{b} = (E_U,E_V,W,A,b,c) θ b = ( E U , E V , W , A , b , c )
F θ b ( u , v ) = A ReLU ( W ( E U ( u ) + E V ( v ) ) + b ) + c , ∥ θ b ∥ 2 = ∥ θ ∥ 2 + ∥ b ∥ 2 + ∥ c ∥ 2 , (21) F_{\theta^b}(u,v) = A\operatorname{ReLU}(W(E_U(u)+E_V(v))+b)+c,\qquad\lVert\theta^b\rVert^2 = \lVert\theta\rVert^2+\lVert b\rVert^2+\lVert c\rVert^2, \tag*{(21)} F θ b ( u , v ) = A ReLU ( W ( E U ( u ) + E V ( v )) + b ) + c , ∥ θ b ∥ 2 = ∥ θ ∥ 2 + ∥ b ∥ 2 + ∥ c ∥ 2 , (21) and let S q b ( D ) S_q^b(D) S q b ( D ) Z = W Φ Z=W\Phi Z = W Φ F b \mathcal{F}_b F b ( A , Z , b , c ) (A,Z,b,c) ( A , Z , b , c ) F ( x ) = A ReLU ( Z ξ x + b ) + c F(x)=A\operatorname{ReLU}(Z\xi_x+b)+c F ( x ) = A ReLU ( Z ξ x + b ) + c
Φ b ( A , Z , b , c ) = ∥ Z ∥ ∗ + 1 2 ( ∥ A ∥ F 2 + ∥ b ∥ 2 + ∥ c ∥ 2 ) . (22) \Phi_b(A,Z,b,c)=\lVert Z\rVert_*+\frac{1}{2}\left(\lVert A\rVert_F^2+\lVert b\rVert^2+\lVert c\rVert^2\right). \tag*{(22)} Φ b ( A , Z , b , c ) = ∥ Z ∥ ∗ + 2 1 ( ∥ A ∥ F 2 + ∥ b ∥ 2 + ∥ c ∥ 2 ) . (22) Lemma B.3 (Bias complexity bridge). The biased problem is equivalent, in optimal value and in score responses, to min F b Φ b \min_{\mathcal{F}_b}\Phi_b min F b Φ b There is an absolute constant C b C_b C b such that on every addition mask every biased minimum-norm response F F F has a finite-width bias-free representation F ( x ) = A ^ ReLU ( Z ^ ξ x ) F(x)=\widehat{A}\operatorname{ReLU}(\widehat{Z}\xi_x) F ( x ) = A ReLU ( Z ξ x ) with ∥ A ^ ∥ F ∥ Z ^ ∥ ∗ ≤ C b q 7 / 6 ( log q ) 1 / 3 \lVert\widehat{A}\rVert_F\lVert\widehat{Z}\rVert_*\le C_bq^{7/6}(\log q)^{1/3} ∥ A ∥ F ∥ Z ∥ ∗ ≤ C b q 7/6 ( log q ) 1/3
The representation is an analysis device whose width may exceed h q h_q h q
Corollary B.4 (Transfer to L 2 L_2 L 2 For the model (21):
(i) feasibility, phase decomposition, and quotient invariance hold, so Π q , τ b ( [ C ] ) \Pi^b_{q,\tau}([C]) Π q , τ b ([ C ]) Q ^ q b \widehat{Q}_q^b Q q b
(ii) for fixed α , τ ∈ ( 0 , 1 ) \alpha,\tau\in(0,1) α , τ ∈ ( 0 , 1 ) min θ b ∈ S q b ( D ( C q a d d , Ω ) ) Acc T ( θ b ; C q a d d ) → P 1 \min_{\theta^b\in S_q^b(D(C_q^{\mathrm{add}},\Omega))}\operatorname{Acc}_T(\theta^b;C_q^{\mathrm{add}})\xrightarrow{\mathrm{P}}1 min θ b ∈ S q b ( D ( C q add , Ω )) Acc T ( θ b ; C q add ) P 1 P q , τ V , b ( M a d d ) → 1 P^{{\mathrm{V},b}}_{q,\tau}(M_{\mathrm{add}})\to1 P q , τ V , b ( M add ) → 1 Π q , τ b ( [ C q a d d ] ) → ( 1 , 0 , 0 ) \Pi^b_{q,\tau}([C_q^{\mathrm{add}}])\to(1,0,0) Π q , τ b ([ C q add ]) → ( 1 , 0 , 0 )
(iii) uniformly over deterministic biased selectors, P q , τ A , b ( M u n i f ) ≤ ( 2 e 2 ) N q − τ ( 1 − α ) N → 0 P^{A,b}_{q,\tau}(M_{\mathrm{unif}})\le(2e^2)^Nq^{-\tau(1-\alpha)N}\to0 P q , τ A , b ( M unif ) ≤ ( 2 e 2 ) N q − τ ( 1 − α ) N → 0 P q , τ V , b ( M u n i f ) → 0 P^{{\mathrm{V},b}}_{q,\tau}(M_{\mathrm{unif}})\to0 P q , τ V , b ( M unif ) → 0
(iv) on a finite instance, with s − , b , s + , b s_{-,b},s_{+,b} s − , b , s + , b ⌈ τ ∣ T ∣ ⌉ \lceil\tau|T|\rceil ⌈ τ ∣ T ∣ ⌉ (19) ; Theorem B.6 holds for the biased profiles.
Unstructured colourings
Removing the Latin constraint gives an elementary independent-label bound for comparison with Lemma 4.5.
Proposition B.5 (Unstructured colourings). Let C ∼ Unif ( C q ) \mathcal{C}\sim\operatorname{Unif}(\mathcal{C}_q) C ∼ Unif ( C q ) For any learner, any α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and any τ > 1 / q \tau>1/q τ > 1/ q
P C ∼ Unif ( C q ) , Ω ∼ ν q [ Acc T ( A q ( D ( C , Ω ) ) ; C ) ≥ τ ] ≤ exp ( − 2 ( τ − 1 / q ) 2 ∣ T ∣ ) . (23) \mathbb{P}_{\mathcal{C}\sim\operatorname{Unif}(\mathcal{C}_q),\,\Omega\sim\nu_q}\left[\operatorname{Acc}_T(A_q(D(\mathcal{C},\Omega));\mathcal{C})\ge\tau\right]\le\exp\left(-2(\tau-1/q)^2|T|\right). \tag*{(23)} P C ∼ Unif ( C q ) , Ω ∼ ν q [ Acc T ( A q ( D ( C , Ω )) ; C ) ≥ τ ] ≤ exp ( − 2 ( τ − 1/ q ) 2 ∣ T ∣ ) . (23) Proof. Conditionally on D \mathcal{D} D T T T 1 / q 1/q 1/ q
A proof-guided observation-scale question
Tracking the discarded-cell parameter η \eta η § 9 .§ 3.2 suggests that the notch argument tolerates
α q ≫ ( log q ) 3 q , equivalently n q ≫ q 3 / 2 ( log q ) 3 . (24) \alpha_q \gg\frac{(\log q)^3}{\sqrt{q}}, \qquad\text{equivalently} \qquad n_q \gg q^{3/2}(\log q)^3. \tag*{(24)} α q ≫ q ( log q ) 3 , equivalently n q ≫ q 3/2 ( log q ) 3 . (24) Turning this into a theorem requires a uniform accounting of the η \eta η O ( q polylog q ) O(q\operatorname{polylog}q) O ( q polylog q )
Fix τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) K ∞ , τ K_{\infty,\tau} K ∞ , τ Π q , τ ( [ C q j ] ) \Pi_{q,\tau}([C_{q_j}]) Π q , τ ([ C q j ]) q j → ∞ q_j \to\infty q j → ∞ [ C q j ] ∈ Q q j [C_{q_j}] \in\mathcal{Q}_{q_j} [ C q j ] ∈ Q q j v = ( 1 , 0 , 0 ) \mathbf{v}=(1,0,0) v = ( 1 , 0 , 0 ) e = { ( 0 , λ , 1 − λ ) : 0 ≤ λ ≤ 1 } \mathbf{e}=\{(0,\lambda,1-\lambda):0\leq\lambda\leq1\} e = {( 0 , λ , 1 − λ ) : 0 ≤ λ ≤ 1 }
U q , τ = sup [ C ] ∈ Q q p q , τ ∨ ( [ C ] ) ( 1 − p q , τ ∨ ( [ C ] ) ) . (25) U_{q,\tau}=\sup_{[C]\in\mathcal{Q}_q}p^{\vee}_{q,\tau}([C])(1-p^{\vee}_{q,\tau}([C])). \tag*{(25)} U q , τ = [ C ] ∈ Q q sup p q , τ ∨ ([ C ]) ( 1 − p q , τ ∨ ([ C ])) . (25) Full edge realisation holds when for every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] q j → ∞ q_j\to\infty q j → ∞ p q j , τ ∨ ( [ C q j ] ) → 0 p^{\vee}_{q_j,\tau}([C_{q_j}])\to0 p q j , τ ∨ ([ C q j ]) → 0 p q j , τ m i x ( [ C q j ] ) → λ p^{\mathop{\mathrm{mix}}}_{q_j,\tau}([C_{q_j}])\to\lambda p q j , τ mix ([ C q j ]) → λ
Theorem B.6 (Classification readiness). Theorem 4.1 (i) gives v ∈ K ∞ , τ \mathbf{v}\in K_{\infty,\tau} v ∈ K ∞ , τ K ∞ , τ = { v } ∪ e K_{\infty,\tau}=\{\mathbf{v}\}\cup\mathbf{e} K ∞ , τ = { v } ∪ e U q , τ → 0 U_{q,\tau}\to0 U q , τ → 0 v \mathbf{v} v p q , τ ∨ → 1 p^{\vee}_{q,\tau}\to1 p q , τ ∨ → 1 ( 0 , λ , 1 − λ ) (0,\lambda,1-\lambda) ( 0 , λ , 1 − λ ) p q , τ ∨ → 0 p^{\vee}_{q,\tau}\to0 p q , τ ∨ → 0 p q , τ m i x → λ p^{\mathop{\mathrm{mix}}}_{q,\tau}\to\lambda p q , τ mix → λ
The theorem packages the remaining programme as a polarisation estimate and a realisation construction. Realisation is the harder half: Proposition B.2 says it needs instances on which Acc T \operatorname{Acc}_T Acc T
Proofs
This appendix gives the detailed proofs for § 3 , Theorem 4.1 , and Appendix § 8 ; the abelian extension Corollary 4.4 is proved in Appendix § 11 .§ 3.2 . Appendix § 9 .§ 1 covers the modelling section, Appendix § 9 .§ 2 the invariance theorem and the finite-instance criterion, Appendix § 9 .§ 3 the two poles of Theorem 4.1 , Appendix § 9 .3.5 the bias transfer, and Appendix § 9 .§ 4 states the external results in the forms used.
Proofs for the modelling section
Proof of Proposition 3.1. Assigning the value C ( u , v ) C(u,v) C ( u , v ) U u V v U_uV_v U u V v [ q ] [q] [ q ] q ≥ 2 q\geq2 q ≥ 2
Now suppose q q q [ q ] [q] [ q ] F q \mathbb{F}_q F q a ∈ F q a\in\mathbb{F}_q a ∈ F q
ℓ a ( t ) = 1 − ( t − a ) q − 1 . (26) \ell_a(t)=1-(t-a)^{q-1}. \tag*{(26)} ℓ a ( t ) = 1 − ( t − a ) q − 1 . (26) The finite-field identity z q − 1 = 1 z^{q-1}=1 z q − 1 = 1 z ≠ 0 z\ne0 z = 0 ℓ a ( t ) = 1 { t = a } \ell_a(t)=\mathbf{1}\{t=a\} ℓ a ( t ) = 1 { t = a } t ∈ F q t\in\mathbb{F}_q t ∈ F q
P C ( X , Y ) = ∑ u , v ∈ F q C ( u , v ) ℓ u ( X ) ℓ v ( Y ) (27) P_C(X,Y)=\sum_{u,v\in\mathbb{F}_q}C(u,v)\ell_u(X)\ell_v(Y) \tag*{(27)} P C ( X , Y ) = u , v ∈ F q ∑ C ( u , v ) ℓ u ( X ) ℓ v ( Y ) (27) has degree at most q − 1 q-1 q − 1 C C C F q 2 \mathbb{F}_q^2 F q 2 F q 2 → F q \mathbb{F}_q^2\to\mathbb{F}_q F q 2 → F q q 2 q^2 q 2
Suppose C C C U u U_u U u C ( u , 0 ) , … , C ( u , q − 1 ) C(u,0),\ldots,C(u,q-1) C ( u , 0 ) , … , C ( u , q − 1 ) u u u
Conversely, properness says the q q q q q q
Fix a colour a a a a a a M a M_a M a E ( K q , q ) E(K_{q,q}) E ( K q , q ) q q q
Under each bijection, the mask selects the same evaluations, cells, or edges.
Proof of Proposition 3.3: non-emptiness. We exhibit a feasible point of finite norm; attainment then follows from closedness and coercivity. Let e 0 , … , e 2 q e_0,\ldots,e_{2q} e 0 , … , e 2 q R d q \mathbb{R}^{d_q} R d q d q = 2 q + 1 d_q=2q+1 d q = 2 q + 1
E U ( u ) = e u + 1 2 e 2 q , E V ( v ) = e q + v + 1 2 e 2 q . (28) E_U(u)=e_u+\frac{1}{2}e_{2q},\qquad E_V(v)=e_{q+v}+\frac{1}{2}e_{2q}. \tag*{(28)} E U ( u ) = e u + 2 1 e 2 q , E V ( v ) = e q + v + 2 1 e 2 q . (28) so that E U ( u ) + E V ( v ) = e u + e q + v + e 2 q E_U(u)+E_V(v)=e_u+e_{q+v}+e_{2q} E U ( u ) + E V ( v ) = e u + e q + v + e 2 q ( i , j ) (i,j) ( i , j )
w i j = e i + e q + j − 3 2 e 2 q . (29) w_{ij}=e_i+e_{q+j}-\frac{3}{2}e_{2q}. \tag*{(29)} w ij = e i + e q + j − 2 3 e 2 q . (29) Its preactivation at cell ( u , v ) (u,v) ( u , v ) 1 { u = i } + 1 { v = j } − 3 2 \mathbf{1}\{u=i\}+\mathbf{1}\{v=j\}-\frac{3}{2} 1 { u = i } + 1 { v = j } − 2 3 1 2 \frac{1}{2} 2 1 ( i , j ) (i,j) ( i , j ) − 1 2 -\frac{1}{2} − 2 1 ( i , j ) (i,j) ( i , j ) 1 2 \frac{1}{2} 2 1 2 2 2 C ( i , j ) C(i,j) C ( i , j ) 0 0 0 1 1 1 0 0 0 Ω \Omega Ω q 2 = h q q^2=h_q q 2 = h q
The feasible set of (3) is closed, being an intersection of preimages of closed sets under the continuous map θ ↦ F θ \theta\mapsto F_\theta θ ↦ F θ θ ↦ 1 2 ∥ θ ∥ 2 \theta\mapsto\frac{1}{2}\|\theta\|^2 θ ↦ 2 1 ∥ θ ∥ 2 S q ( D ) ≠ ∅ S_q(\mathcal{D})\ne\varnothing S q ( D ) = ∅
Proofs of invariance and of the finite-instance criterion
Proof of Theorem 3.5. Consider first the direct case of Definition 3.4. Given Ω ′ \Omega' Ω ′
Ω = { ( ρ ( u ) , κ ( v ) ) : ( u , v ) ∈ Ω ′ } , (30) \Omega=\{(\rho(u),\kappa(v)):(u,v)\in\Omega'\}, \tag*{(30)} Ω = {( ρ ( u ) , κ ( v )) : ( u , v ) ∈ Ω ′ } , (30) a bijection of the space of subsets of a fixed size, hence measure-preserving for ν q \nu_q ν q θ = ( E U , E V , W , A ) \theta=(E_U,E_V,W,A) θ = ( E U , E V , W , A )
E U ′ ( u ) = E U ( ρ ( u ) ) , E V ′ ( v ) = E V ( κ ( v ) ) , W ′ = W , (31) E'_U(u)=E_U(\rho(u)),\qquad E'_V(v)=E_V(\kappa(v)),\qquad W'=W, \tag*{(31)} E U ′ ( u ) = E U ( ρ ( u )) , E V ′ ( v ) = E V ( κ ( v )) , W ′ = W , (31) and let A ′ A' A ′ A γ ( a ) , : ′ = A a , : A'_{\gamma(a),:}=A_{a,:} A γ ( a ) , : ′ = A a , : a ∈ [ q ] a\in[q] a ∈ [ q ]
F θ ′ , γ ( a ) ( u , v ) = F θ , a ( ρ ( u ) , κ ( v ) ) . (32) F_{\theta',\gamma(a)}(u,v)=F_{\theta,a}(\rho(u),\kappa(v)). \tag*{(32)} F θ ′ , γ ( a ) ( u , v ) = F θ , a ( ρ ( u ) , κ ( v )) . (32) Each transformation permutes the entries of a finite table or the rows of a matrix, so ∥ θ ′ ∥ = ∥ θ ∥ \|\theta'\|=\|\theta\| ∥ θ ′ ∥ = ∥ θ ∥ γ \gamma γ A c c T \mathrm{Acc}_T Acc T
For the transposed case set Ω = { ( κ ( v ) , ρ ( u ) ) : ( u , v ) ∈ Ω ′ } \Omega=\{(\kappa(v),\rho(u)):(u,v)\in\Omega'\} Ω = {( κ ( v ) , ρ ( u )) : ( u , v ) ∈ Ω ′ }
E U ′ ( u ) = E V ( ρ ( u ) ) , E V ′ ( v ) = E U ( κ ( v ) ) , (33) E'_U(u)=E_V(\rho(u)),\qquad E'_V(v)=E_U(\kappa(v)), \tag*{(33)} E U ′ ( u ) = E V ( ρ ( u )) , E V ′ ( v ) = E U ( κ ( v )) , (33) with A ′ A' A ′ γ \gamma γ ( u , v ) (u,v) ( u , v ) ( κ ( v ) , ρ ( u ) ) (\kappa(v),\rho(u)) ( κ ( v ) , ρ ( u ))
Proof of Proposition 3.3: decomposition. By the first part the set S q ( D ) S_q(\mathcal{D}) S q ( D ) A q † < τ A_q^\dagger<\tau A q † < τ A q † ≥ τ A_q^\dagger\ge\tau A q † ≥ τ ν q \nu_q ν q p q n g + p q m i x + p q g = 1 p_q^{\mathrm{ng}}+p_q^{\mathrm{mix}}+p_q^{\mathrm{g}}=1 p q ng + p q mix + p q g = 1 ( C , Ω ) (C,\Omega) ( C , Ω ) τ \tau τ { F B : B ∈ E g } \{F_B:B\in E_g\} { F B : B ∈ E g }
Proof of Lemma 3.2. If Ω = ∅ \Omega= \varnothing Ω = ∅ Ω ≠ ∅ \Omega\ne\varnothing Ω = ∅ Z = W Φ Z = W\Phi Z = W Φ
∥ W ∥ F 2 + ∥ Φ ∥ F 2 2 ≥ ∥ W Φ ∥ ∗ = ∥ Z ∥ ∗ , (34) \frac{\lVert W\rVert_F^2+\lVert\Phi\rVert_F^2}{2} \ge\lVert W\Phi\rVert_* = \lVert Z\rVert_*, \tag*{(34)} 2 ∥ W ∥ F 2 + ∥ Φ ∥ F 2 ≥ ∥ W Φ ∥ ∗ = ∥ Z ∥ ∗ , (34) with equality attained as follows: if Z = U Σ V T Z = U\Sigma V^{\mathsf{T}} Z = U Σ V T W = U Σ 1 / 2 W = U\Sigma^{1/2} W = U Σ 1/2 Φ = Σ 1 / 2 V T \Phi= \Sigma^{1/2}V^{\mathsf{T}} Φ = Σ 1/2 V T ∥ W ∥ F 2 = ∥ Φ ∥ F 2 = tr Σ = ∥ Z ∥ ∗ \lVert W\rVert_F^2 = \lVert\Phi\rVert_F^2 = \operatorname{tr}\Sigma= \lVert Z\rVert_* ∥ W ∥ F 2 = ∥ Φ ∥ F 2 = tr Σ = ∥ Z ∥ ∗ rank Z ≤ 2 q < d q = 2 q + 1 \operatorname{rank} Z \le2q < d_q = 2q + 1 rank Z ≤ 2 q < d q = 2 q + 1
Now fix a reduced representation ( A , Z ) (A,Z) ( A , Z ) t > 0 t > 0 t > 0
A ReLU ( Z ξ x ) = ( t − 1 A ) ReLU ( ( t Z ) ξ x ) , (35) A\operatorname{ReLU}(Z\xi_x) = (t^{-1}A)\operatorname{ReLU}((tZ)\xi_x), \tag*{(35)} A ReLU ( Z ξ x ) = ( t − 1 A ) ReLU (( tZ ) ξ x ) , (35) so the score table, and hence feasibility, is unchanged under ( A , Z ) ↦ ( t − 1 A , t Z ) (A,Z) \mapsto(t^{-1}A,tZ) ( A , Z ) ↦ ( t − 1 A , tZ ) W W W Φ \Phi Φ (34) , the objective of (3) at the balanced point becomes
ϕ ( t ) = t ∥ Z ∥ ∗ + ∥ A ∥ F 2 2 t 2 . (36) \phi(t) = t\lVert Z\rVert_* + \frac{\lVert A\rVert_F^2}{2t^2}. \tag*{(36)} ϕ ( t ) = t ∥ Z ∥ ∗ + 2 t 2 ∥ A ∥ F 2 . (36) Then ϕ ′ ( t ) = ∥ Z ∥ ∗ − ∥ A ∥ F 2 / t 3 \phi'(t) = \lVert Z\rVert_* - \lVert A\rVert_F^2/t^3 ϕ ′ ( t ) = ∥ Z ∥ ∗ − ∥ A ∥ F 2 / t 3 t 3 = ∥ A ∥ F 2 / ∥ Z ∥ ∗ t^3 = \lVert A\rVert_F^2/\lVert Z\rVert_* t 3 = ∥ A ∥ F 2 / ∥ Z ∥ ∗ ϕ ′ ′ > 0 \phi'' > 0 ϕ ′′ > 0
min t > 0 ϕ ( t ) = 3 2 ( ∥ A ∥ F ∥ Z ∥ ∗ ) 2 / 3 . (37) \min_{t>0}\phi(t) = \frac{3}{2}\left(\lVert A\rVert_F\lVert Z\rVert_*\right)^{2/3}. \tag*{(37)} t > 0 min ϕ ( t ) = 2 3 ( ∥ A ∥ F ∥ Z ∥ ∗ ) 2/3 . (37) Minimising over all feasible reduced representations gives V ∗ = 3 2 J ∗ 2 / 3 V_* = \frac{3}{2}J_*^{2/3} V ∗ = 2 3 J ∗ 2/3 t t t ∥ A ∥ F 2 \lVert A\rVert_F^2 ∥ A ∥ F 2 ∥ W ∥ F 2 \lVert W\rVert_F^2 ∥ W ∥ F 2 ∥ Φ ∥ F 2 \lVert\Phi\rVert_F^2 ∥ Φ ∥ F 2 J ∗ 2 / 3 J_*^{2/3} J ∗ 2/3
Proof of Theorem B.1. If Ω = ∅ \Omega= \varnothing Ω = ∅ g = 0 g = 0 g = 0 E g = S ∗ E_g = S_* E g = S ∗ A B = 0 A_B = 0 A B = 0 Ω ≠ ∅ \Omega\ne\varnothing Ω = ∅ ( A , B ) (A,B) ( A , B ) ( ∥ B ∥ ∗ A , B / ∥ B ∥ ∗ ) (\lVert B\rVert_*A,B/\lVert B\rVert_*) (∥ B ∥ ∗ A , B / ∥ B ∥ ∗ ) ∥ A ∥ F ∥ B ∥ ∗ \lVert A\rVert_F\lVert B\rVert_* ∥ A ∥ F ∥ B ∥ ∗ inf B ∈ S ∗ ρ ( B ) \inf_{B\in S_*}\rho(B) inf B ∈ S ∗ ρ ( B )
The set S ∗ S_* S ∗ ρ \rho ρ B i → B B_i \to B B i → B lim inf ρ ( B i ) < ∞ \liminf\rho(B_i) < \infty lim inf ρ ( B i ) < ∞ A i A_i A i (17) shows the limit is feasible for B B B ρ ( B ) ≤ lim inf ρ ( B i ) \rho(B) \le\liminf\rho(B_i) ρ ( B ) ≤ lim inf ρ ( B i ) g < ∞ g < \infty g < ∞ ρ ≥ g \rho\ge g ρ ≥ g S ∗ S_* S ∗ E g = { B : ρ ( B ) ≤ g } E_g = \{B : \rho(B) \le g\} E g = { B : ρ ( B ) ≤ g }
For fixed B B B A A A ∥ A ∥ F 2 \lVert A\rVert_F^2 ∥ A ∥ F 2 A B A_B A B B i → B B_i \to B B i → B B i ∈ E g B_i \in E_g B i ∈ E g ∥ A B i ∥ F = g \lVert A_{B_i}\rVert_F = g ∥ A B i ∥ F = g i i i B B B g g g A B A_B A B B ↦ A B B \mapsto A_B B ↦ A B B ↦ F B B \mapsto F_B B ↦ F B s − , τ , s + , τ s_{-,\tau},s_{+,\tau} s − , τ , s + , τ (18) are attained.
Any reduced global minimiser, once normalised, must have B ∈ E g B \in E_g B ∈ E g A B A_B A B B ∈ E g B \in E_g B ∈ E g A B A_B A B { F B : B ∈ E g } \{F_B : B \in E_g\} { F B : B ∈ E g }
Finally, a response has strict test accuracy at least τ \tau τ k = ⌈ τ ∣ T ∣ ⌉ k = \lceil\tau|\mathcal{T}|\rceil k = ⌈ τ ∣ T ∣ ⌉ s ( B ) > 0 s_{(B)} > 0 s ( B ) > 0 min E g s > 0 \min_{E_g}s > 0 min E g s > 0 s = 0 s = 0 s = 0 (5) . This is (19) .
Proofs for the main theorem
The addition carrier
Proof of Lemma 4.2. We give the construction explicitly. Put
h = 2 3 , ϵ = 2 h 2 4 = 2 9 , ρ = 1 − ϵ 2 , c = 2 1 − ϵ . (38) h=\frac{2}{3},\qquad\epsilon=\frac{\sqrt{2}h^2}{4}=\frac{\sqrt{2}}{9},\qquad\rho=\frac{1-\epsilon}{2},\qquad c=\frac{2}{1-\epsilon}. \tag*{(38)} h = 3 2 , ϵ = 4 2 h 2 = 9 2 , ρ = 2 1 − ϵ , c = 1 − ϵ 2 . (38) and
L = ⌈ 2 ( log ( q − 1 ) + 1 ) ( ρ + 1 / ( q − 1 ) ) 2 ⌉ = O ( log q ) . (39) L=\left\lceil\frac{2(\log(q-1)+1)}{(\rho+1/(q-1))^2}\right\rceil=O(\log q). \tag*{(39)} L = ⌈ ( ρ + 1/ ( q − 1 ) ) 2 2 ( log ( q − 1 ) + 1 ) ⌉ = O ( log q ) . (39) Frequency selection. We claim there are non-zero frequencies k 1 , … , k L ∈ Z q k_1,\ldots,k_L\in\mathbb{Z}_q k 1 , … , k L ∈ Z q e ≠ 0 e\ne0 e = 0
1 L ∑ ℓ = 1 L cos ( 2 π k ℓ e / q ) ≤ ρ . (40) \frac{1}{L}\sum_{\ell=1}^{L}\cos(2\pi k_\ell e/q)\le\rho. \tag*{(40)} L 1 ℓ = 1 ∑ L cos ( 2 π k ℓ e / q ) ≤ ρ . (40) Argue probabilistically: for uniform non-zero k k k cos ( 2 π k e / q ) \cos(2\pi ke/q) cos ( 2 π k e / q ) − 1 / ( q − 1 ) -1/(q-1) − 1/ ( q − 1 ) k ∈ Z q k\in\mathbb{Z}_q k ∈ Z q [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] [20 ] bounds the probability that (40) fails at a fixed e e e exp { − L ( ρ + 1 / ( q − 1 ) ) 2 / 2 } \exp\{-L(\rho+1/(q-1))^2/2\} exp { − L ( ρ + 1/ ( q − 1 ) ) 2 /2 } q − 1 q-1 q − 1 e e e L L L
An exact ReLU surrogate for multiplication. Let Q h Q_h Q h t 2 t^2 t 2 { − 2 , − 4 3 , − 2 3 , 0 , 2 3 , 4 3 , 2 } \{-2,-\frac{4}{3},-\frac{2}{3},0,\frac{2}{3},\frac{4}{3},2\} { − 2 , − 3 4 , − 3 2 , 0 , 3 2 , 3 4 , 2 }
Q h ( t ) = h ∣ t ∣ + 2 h ∑ j = 1 2 ( ∣ t ∣ − j h ) + , ∣ t ∣ = ( t ) + + ( − t ) + , (41) Q_h(t)=h|t|+2h\sum_{j=1}^{2}(|t|-jh)_+,\qquad|t|=(t)_++(-t)_+, \tag*{(41)} Q h ( t ) = h ∣ t ∣ + 2 h j = 1 ∑ 2 ( ∣ t ∣ − j h ) + , ∣ t ∣ = ( t ) + + ( − t ) + , (41) and satisfies 0 ≤ Q h ( t ) − t 2 ≤ h 2 / 4 0\le Q_h(t)-t^2\le h^2/4 0 ≤ Q h ( t ) − t 2 ≤ h 2 /4 ∣ t ∣ ≤ 2 |t|\le2 ∣ t ∣ ≤ 2
P ( x , y ) = Q h ( x + y ) − Q h ( x − y ) 4 (42) P(x,y)=\frac{Q_h(x+y)-Q_h(x-y)}{4} \tag*{(42)} P ( x , y ) = 4 Q h ( x + y ) − Q h ( x − y ) (42) satisfies, for ∣ x ∣ , ∣ y ∣ ≤ 1 |x|,|y|\le1 ∣ x ∣ , ∣ y ∣ ≤ 1
∣ P ( x , y ) − x y ∣ ≤ h 2 / 16. (43) |P(x,y)-xy|\le h^2/16. \tag*{(43)} ∣ P ( x , y ) − x y ∣ ≤ h 2 /16. (43) Scores. For each frequency k ℓ k_\ell k ℓ ϕ ℓ ( t ) = 2 π k ℓ t / q \phi_\ell(t)=2\pi k_\ell t/q ϕ ℓ ( t ) = 2 π k ℓ t / q
c ℓ ( u , v ) = P ( cos ϕ ℓ ( u ) , cos ϕ ℓ ( v ) ) − P ( sin ϕ ℓ ( u ) , sin ϕ ℓ ( v ) ) , (44) c_\ell(u,v)=P(\cos\phi_\ell(u),\cos\phi_\ell(v))-P(\sin\phi_\ell(u),\sin\phi_\ell(v)), \tag*{(44)} c ℓ ( u , v ) = P ( cos ϕ ℓ ( u ) , cos ϕ ℓ ( v )) − P ( sin ϕ ℓ ( u ) , sin ϕ ℓ ( v )) , (44) s ℓ ( u , v ) = P ( sin ϕ ℓ ( u ) , cos ϕ ℓ ( v ) ) + P ( cos ϕ ℓ ( u ) , sin ϕ ℓ ( v ) ) , (45) s_\ell(u,v)=P(\sin\phi_\ell(u),\cos\phi_\ell(v))+P(\cos\phi_\ell(u),\sin\phi_\ell(v)), \tag*{(45)} s ℓ ( u , v ) = P ( sin ϕ ℓ ( u ) , cos ϕ ℓ ( v )) + P ( cos ϕ ℓ ( u ) , sin ϕ ℓ ( v )) , (45) so that ∣ c ℓ − cos ϕ ℓ ( u + v ) ∣ ≤ h 2 / 8 |c_\ell-\cos\phi_\ell(u+v)|\le h^2/8 ∣ c ℓ − cos ϕ ℓ ( u + v ) ∣ ≤ h 2 /8 ∣ s ℓ − sin ϕ ℓ ( u + v ) ∣ ≤ h 2 / 8 |s_\ell-\sin\phi_\ell(u+v)|\le h^2/8 ∣ s ℓ − sin ϕ ℓ ( u + v ) ∣ ≤ h 2 /8
F q , a ∗ ( u , v ) = c L ∑ ℓ = 1 L ( cos ϕ ℓ ( a ) c ℓ ( u , v ) + sin ϕ ℓ ( a ) s ℓ ( u , v ) ) . (46) F^*_{q,a}(u,v)=\frac{c}{L}\sum_{\ell=1}^{L}\left(\cos\phi_\ell(a)c_\ell(u,v)+\sin\phi_\ell(a)s_\ell(u,v)\right). \tag*{(46)} F q , a ∗ ( u , v ) = L c ℓ = 1 ∑ L ( cos ϕ ℓ ( a ) c ℓ ( u , v ) + sin ϕ ℓ ( a ) s ℓ ( u , v ) ) . (46) Margins. The idealised version of (46), with c ℓ , s ℓ c_\ell,s_\ell c ℓ , s ℓ c c c a = u + v a=u+v a = u + v c ρ c\rho c ρ c 2 h 2 / 8 c\sqrt{2}h^2/8 c 2 h 2 /8 c ( 1 − ρ − 2 h 2 / 4 ) = 1 c(1-\rho-\sqrt{2}h^2/4)=1 c ( 1 − ρ − 2 h 2 /4 ) = 1 c c c c ϵ / 2 c\epsilon/2 cϵ /2 ϵ = 2 / 9 < 1 / 6 \epsilon=\sqrt{2}/9<1/6 ϵ = 2 /9 < 1/6 c = 2 / ( 1 − ϵ ) < 12 / 5 c=2/(1-\epsilon)<12/5 c = 2/ ( 1 − ϵ ) < 12/5
2 c ( 1 + ϵ 2 ) < 24 5 ⋅ 13 12 = 26 5 < 9. (47) 2c\left(1+\frac{\epsilon}{2}\right)<\frac{24}{5}\cdot\frac{13}{12}=\frac{26}{5}<9. \tag*{(47)} 2 c ( 1 + 2 ϵ ) < 5 24 ⋅ 12 13 = 5 26 < 9. (47) Additivity and width. Every hinge in (41) is the positive part of r u + s v − t r_u+s_v-t r u + s v − t t t t ξ ( u , v ) = e u + e q + v \xi_{(u,v)}=e_u+e_{q+v} ξ ( u , v ) = e u + e q + v O ( L ) = O ( log q ) O(L)=O(\log q) O ( L ) = O ( log q ) q 2 q^2 q 2
Norms. Each preactivation row has Euclidean norm O ( q ) O(\sqrt{q}) O ( q ) 2 q 2q 2 q O ( q / L ) O(\sqrt{q}/L) O ( q / L )
∥ Z ∥ ∗ ≤ O ( L ) ∥ Z ∥ F = O ( L q ) , ∥ A ∥ F = O ( q / L ) , (48) \|Z\|_* \le\sqrt{O(L)}\|Z\|_F = O(L\sqrt{q}), \qquad\|A\|_F = O(\sqrt{q/L}), \tag*{(48)} ∥ Z ∥ ∗ ≤ O ( L ) ∥ Z ∥ F = O ( L q ) , ∥ A ∥ F = O ( q / L ) , (48) so, taking these constructed factors as ( A c a r , Z c a r ) (A_{\mathrm{car}}, Z_{\mathrm{car}}) ( A car , Z car ) J c a r : = ∥ A c a r ∥ F ∥ Z c a r ∥ ∗ ≤ C 0 q log q J_{\mathrm{car}} := \|A_{\mathrm{car}}\|_F\|Z_{\mathrm{car}}\|_* \le C_0q\sqrt{\log q} J car := ∥ A car ∥ F ∥ Z car ∥ ∗ ≤ C 0 q log q C 0 C_0 C 0 Z c a r Z_{\mathrm{car}} Z car W W W Φ \Phi Φ
The one-sided notch lemma
Proof of Lemma 4.3. Throughout, y ( x ) = C q a d d ( x ) y(x) = C_q^{\mathrm{add}}(x) y ( x ) = C q add ( x )
Step 0: the design Gram matrix. The full addition design satisfies
∥ ∑ x ∈ X q ξ x ξ x T ∥ o p = 2 q , (49) \left\|\sum_{x\in X_q}\xi_x\xi_x^{\mathsf T}\right\|_{\mathrm{op}} = 2q, \tag*{(49)} x ∈ X q ∑ ξ x ξ x T op = 2 q , (49) because that Gram matrix is ( q I 11 T 11 T q I ) \begin{pmatrix}qI & \mathbf{1}\mathbf{1}^{\mathsf T}\\ \mathbf{1}\mathbf{1}^{\mathsf T} & qI\end{pmatrix} ( q I 1 1 T 1 1 T q I )
Step 1: low-rank split. Let m = ⌈ q ⌉ m=\lceil\sqrt{q}\rceil m = ⌈ q ⌉ Z Z Z m m m Z m Z_m Z m i i i A A A a i a_i a i i i i Z m Z_m Z m z i ( m ) z_i^{(m)} z i ( m )
A ReLU ( Z m ξ x ) = ∑ i s i u i ReLU ( w i T ξ x ) , (50) A\operatorname{ReLU}(Z_m\xi_x)=\sum_i s_i u_i\operatorname{ReLU}(w_i^{\mathsf T}\xi_x), \tag*{(50)} A ReLU ( Z m ξ x ) = i ∑ s i u i ReLU ( w i T ξ x ) , (50) with ∥ u i ∥ 2 = ∥ w i ∥ 2 = 1 \|u_i\|_2=\|w_i\|_2=1 ∥ u i ∥ 2 = ∥ w i ∥ 2 = 1 s i = ∥ a i ∥ 2 ∥ z i ( m ) ∥ 2 s_i=\|a_i\|_2\|z_i^{(m)}\|_2 s i = ∥ a i ∥ 2 ∥ z i ( m ) ∥ 2
∑ i s i ≤ ∥ A ∥ F ∥ Z m ∥ F ≤ ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q . (51) \sum_i s_i\le\|A\|_F\|Z_m\|_F\le\|A\|_F\|Z\|_*\le B_q. \tag*{(51)} i ∑ s i ≤ ∥ A ∥ F ∥ Z m ∥ F ≤ ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q . (51) By (49) each normalised scalar gate has full-grid squared norm at most 2 q 2q 2 q [41 ] yields a proxy built from K 0 K_0 K 0 2 q B q 2 / K 0 2qB_q^2/K_0 2 q B q 2 / K 0
The i i i a i ( ReLU ( z i T ξ x ) − ReLU ( ( z i ( m ) ) T ξ x ) ) a_i\bigl(\operatorname{ReLU}(z_i^{\mathsf T}\xi_x)-\operatorname{ReLU}((z_i^{(m)})^{\mathsf T}\xi_x)\bigr) a i ( ReLU ( z i T ξ x ) − ReLU (( z i ( m ) ) T ξ x ) ) ∥ Z − Z m ∥ F 2 ≤ ∥ Z ∥ ∗ 2 / ( m + 1 ) \|Z-Z_m\|_F^2\le\|Z\|_*^2/(m+1) ∥ Z − Z m ∥ F 2 ≤ ∥ Z ∥ ∗ 2 / ( m + 1 ) ( m + 1 ) σ m + 1 ≤ ∑ j ≤ m + 1 σ j ≤ ∥ Z ∥ ∗ (m+1)\sigma_{m+1}\le\sum_{j\le m+1}\sigma_j\le\|Z\|_* ( m + 1 ) σ m + 1 ≤ ∑ j ≤ m + 1 σ j ≤ ∥ Z ∥ ∗
( ∑ i ∥ tail atom i ∥ ℓ 2 ( X q ; R q ) 2 ) 2 ≤ 2 q ∥ A ∥ F 2 ∥ Z − Z m ∥ F 2 ≤ 2 q B q 2 m + 1 . (52) \left(\sum_i\|\text{tail atom}_i\|_{\ell_2(X_q;\mathbb{R}^q)}^2\right)^2 \le2q\|A\|_F^2\|Z-Z_m\|_F^2\le\frac{2qB_q^2}{m+1}. \tag*{(52)} ( i ∑ ∥ tail atom i ∥ ℓ 2 ( X q ; R q ) 2 ) 2 ≤ 2 q ∥ A ∥ F 2 ∥ Z − Z m ∥ F 2 ≤ m + 1 2 q B q 2 . (52) and sampling K 1 K_1 K 1 K 1 K_1 K 1
Step 2: sampling budgets. Set
ϵ q = B q 2 log q q 5 / 2 , r q = { min { log q , ϵ q − 1 / 2 } , ϵ q > 0 , log q , ϵ q = 0 , (53) \epsilon_q=\frac{B_q^2\log q}{q^{5/2}},\qquad
r_q=
\begin{cases}
\min\{\log q,\epsilon_q^{-1/2}\}, & \epsilon_q>0,\\
\log q, & \epsilon_q=0,
\end{cases} \tag*{(53)} ϵ q = q 5/2 B q 2 log q , r q = { min { log q , ϵ q − 1/2 } , log q , ϵ q > 0 , ϵ q = 0 , (53) and
K 0 = max { 1 , ⌈ r q B q 2 / q ⌉ } , K 1 = max { 1 , ⌈ r q B q 2 / ( q m ) ⌉ } . (54) K_0=\max\{1,\lceil r_qB_q^2/q\rceil\},\qquad K_1=\max\{1,\lceil r_qB_q^2/(qm)\rceil\}. \tag*{(54)} K 0 = max { 1 , ⌈ r q B q 2 / q ⌉} , K 1 = max { 1 , ⌈ r q B q 2 / ( q m )⌉} . (54) Then r q → ∞ r_q\to\infty r q → ∞ r q ϵ q → 0 r_q\epsilon_q\to0 r q ϵ q → 0 ϵ q → 0 \epsilon_q\to0 ϵ q → 0 O ( N / r q ) = o ( N ) O(N/r_q)=o(N) O ( N / r q ) = o ( N )
Write the core proxy as D ~ 0 = B 0 H 0 \widetilde{D}_0=B_0H_0 D 0 = B 0 H 0 2 q \sqrt{2q} 2 q
∥ B 0 ∥ F 2 ≤ a q 2 : = C 1 N / r q . (55) \|B_0\|_F^2\le a_q^2:=C_1N/r_q. \tag*{(55)} ∥ B 0 ∥ F 2 ≤ a q 2 := C 1 N / r q . (55) and the normalised feature table satisfies ∑ x ∈ X q ∥ H 0 ( x ) ∥ 2 2 ≤ K 0 \sum_{x\in X_q}\lVert H_0(x)\rVert_2^2 \le K_0 ∑ x ∈ X q ∥ H 0 ( x ) ∥ 2 2 ≤ K 0 η N \eta N η N
∥ H 0 ( x ) ∥ 2 2 ≤ b q 2 : = K 0 / ( η N ) . (56) \lVert H_0(x)\rVert_2^2 \le b_q^2 := K_0/(\eta N). \tag*{(56)} ∥ H 0 ( x ) ∥ 2 2 ≤ b q 2 := K 0 / ( η N ) . (56) The tail proxy remains explicit outside the covering theorem:
T ~ ( x ) = ∑ j = 1 K 1 v j ( ReLU ( r j T ξ x ) − ReLU ( ( r j ′ ) T ξ x ) ) , (57) \widetilde{T}(x)=\sum_{j=1}^{K_1}v_j\bigl(\operatorname{ReLU}(r_j^{\mathsf{T}}\xi_x)-\operatorname{ReLU}((r'_j)^{\mathsf{T}}\xi_x)\bigr), \tag*{(57)} T ( x ) = j = 1 ∑ K 1 v j ( ReLU ( r j T ξ x ) − ReLU (( r j ′ ) T ξ x ) ) , (57) which avoids hiding a mask-adaptive component inside a fixed-feature cover.
Step 3: a mask-independent cover code for the core. Apply Theorem C.1 with p = r = 2 p=r=2 p = r = 2 q q q ( x , c ) (x,c) ( x , c )
ζ x , c = e c ⊗ H 0 ( x ) ∈ R q K 0 . (58) \zeta_{x,c}=e_c\otimes H_0(x)\in\mathbb{R}^{qK_0}. \tag*{(58)} ζ x , c = e c ⊗ H 0 ( x ) ∈ R q K 0 . (58) On the retained cells ∥ ζ x , c ∥ 2 ≤ b q \lVert\zeta_{x,c}\rVert_2\le b_q ∥ ζ x , c ∥ 2 ≤ b q ∥ B 0 ∥ F ≤ a q \lVert B_0\rVert_F\le a_q ∥ B 0 ∥ F ≤ a q
Fix precision δ = 1 / 16 \delta=1/16 δ = 1/16 { θ s } s = 0 L q g r i d ⊂ [ − a q b q − δ / 2 , a q b q + δ / 2 ] \{\theta_s\}_{s=0}^{L_q^{\mathrm{grid}}}\subset[-a_qb_q-\delta/2,a_qb_q+\delta/2] { θ s } s = 0 L q grid ⊂ [ − a q b q − δ /2 , a q b q + δ /2 ] L q g r i d ≤ ⌈ 4 a q b q / δ + 2 ⌉ L_q^{\mathrm{grid}}\le\lceil4a_qb_q/\delta+2\rceil L q grid ≤ ⌈ 4 a q b q / δ + 2 ⌉ q , η , B q , r q q,\eta,B_q,r_q q , η , B q , r q
Dispose first of the degenerate branch: if δ > a q b q \delta>a_qb_q δ > a q b q a q b q < δ a_qb_q<\delta a q b q < δ δ ≤ a q b q \delta\le a_qb_q δ ≤ a q b q
At p = 2 p=2 p = 2 κ = ( α x , c , s , β x , c , s ) \kappa=(\alpha_{x,c,s},\beta_{x,c,s}) κ = ( α x , c , s , β x , c , s )
M q : = ⌈ 36 a q 2 b q 2 δ − 2 ⌉ , (59) M_q:=\left\lceil36a_q^2b_q^2\delta^{-2}\right\rceil, \tag*{(59)} M q := ⌈ 36 a q 2 b q 2 δ − 2 ⌉ , (59) defined on the ambient address set X q × [ q ] × { 0 , … , L q g r i d } × { + , − } X_q\times[q]\times\{0,\ldots,L_q^{\mathrm{grid}}\}\times\{+,-\} X q × [ q ] × { 0 , … , L q grid } × { + , − }
y κ ( H 0 ) = 2 ∑ x , c , s ( α x , c , s − β x , c , s ) ζ x , c , a q z κ = 2 a q ∑ x , c , s ( − α x , c , s + β x , c , s ) θ s , (60) \begin{aligned}
y_\kappa(H_0)&=2\sum_{x,c,s}(\alpha_{x,c,s}-\beta_{x,c,s})\zeta_{x,c},\\
a_qz_\kappa&=\frac{2}{a_q}\sum_{x,c,s}(-\alpha_{x,c,s}+\beta_{x,c,s})\theta_s, \tag*{(60)}
\end{aligned} y κ ( H 0 ) a q z κ = 2 x , c , s ∑ ( α x , c , s − β x , c , s ) ζ x , c , = a q 2 x , c , s ∑ ( − α x , c , s + β x , c , s ) θ s , (60) where z κ z_\kappa z κ z κ > 0 z_\kappa>0 z κ > 0 z κ ≤ 0 z_\kappa\le0 z κ ≤ 0 w ^ κ ( H 0 ) = y κ ( H 0 ) / z κ \widehat{w}_\kappa(H_0)=y_\kappa(H_0)/z_\kappa w κ ( H 0 ) = y κ ( H 0 ) / z κ a q = 0 a_q=0 a q = 0 a q > 0 a_q>0 a q > 0 B 0 H 0 B_0H_0 B 0 H 0 δ \delta δ
The number of codes is likewise fixed before the mask is drawn. The address count is at most L q a d d r = 2 N q ( L q g r i d + 1 ) L_q^{\mathrm{addr}}=2Nq(L_q^{\mathrm{grid}}+1) L q addr = 2 N q ( L q grid + 1 ) M q M_q M q ( L q a d d r + 1 ) M q (L_q^{\mathrm{addr}}+1)^{M_q} ( L q addr + 1 ) M q (54) –(56) ,
a q 2 b q 2 = O n ( B q 2 q + 1 r q ) , (61) a_q^2b_q^2=O_n\left(\frac{B_q^2}{q}+\frac{1}{r_q}\right), \tag*{(61)} a q 2 b q 2 = O n ( q B q 2 + r q 1 ) , (61) and a q b q a_qb_q a q b q q q q
log # { κ } = O n ( ( 1 + B q 2 q + 1 r q ) log q ) = o ( N ) . (62) \log\#\{\kappa\}=O_n\left(\left(1+\frac{B_q^2}{q}+\frac{1}{r_q}\right)\log q\right)=o(N). \tag*{(62)} log # { κ } = O n ( ( 1 + q B q 2 + r q 1 ) log q ) = o ( N ) . (62) The additive constant 1 1 1 O ( log q ) = o ( N ) O(\log q)=o(N) O ( log q ) = o ( N ) a q 2 b q 2 ≥ δ 2 a_q^2b_q^2\ge\delta^2 a q 2 b q 2 ≥ δ 2
Step 4: sign-pattern counting. Write the common rank-m m m R ∈ R m × 2 q R \in\mathbb{R}^{m \times2q} R ∈ R m × 2 q j j j R T t j R^{\mathsf{T}}t_j R T t j 2 q m + m K 0 2qm+mK_0 2 q m + m K 0 5 q K 1 5qK_1 5 q K 1 v j ∈ R q v_j \in\mathbb{R}^q v j ∈ R q r j , r j ′ ∈ R 2 q r_j,r'_j \in\mathbb{R}^{2q} r j , r j ′ ∈ R 2 q
D q p a r ≤ 2 q m + m K 0 + 5 q K 1 = O ( q 3 / 2 + r q B q 2 q + q ) , (63) D_q^{\mathrm{par}} \le2qm+mK_0+5qK_1=O\left(q^{3/2}+\frac{r_qB_q^2}{\sqrt{q}}+q\right), \tag*{(63)} D q par ≤ 2 q m + m K 0 + 5 q K 1 = O ( q 3/2 + q r q B q 2 + q ) , (63) and therefore
D q p a r log q N = O ( log q q + r q ϵ q ) = o ( 1 ) . (64) \frac{D_q^{\mathrm{par}}\log q}{N}=O\left(\frac{\log q}{\sqrt{q}}+r_q\epsilon_q\right)=o(1). \tag*{(64)} N D q par log q = O ( q log q + r q ϵ q ) = o ( 1 ) . (64) For each x x x j j j t j T R ξ x t_j^{\mathsf{T}}R\xi_x t j T R ξ x r j T ξ x , ( r j ′ ) T ξ x r_j^{\mathsf{T}}\xi_x,(r'_j)^{\mathsf{T}}\xi_x r j T ξ x , ( r j ′ ) T ξ x Theorem C.3 , the ternary sign patterns of these ( K 0 + 2 K 1 ) N (K_0+2K_1)N ( K 0 + 2 K 1 ) N exp ( O ( D q p a r log q ) ) \exp(O(D_q^{\mathrm{par}}\log q)) exp ( O ( D q par log q ))
On a fixed gate stratum each H 0 , j ( x ) H_{0,j}(x) H 0 , j ( x ) (60) the c c c x x x
F ^ κ , c ( x ) = 2 z κ ∑ s , c ′ , ℓ σ κ , s , c ′ , ℓ H 0 , ℓ ( s ) H 0 , ℓ ( x ) , (65) \widehat{F}_{\kappa,c}(x)=\frac{2}{z_\kappa}\sum_{s,c',\ell}\sigma_{\kappa,s,c',\ell}H_{0,\ell}(s)H_{0,\ell}(x), \tag*{(65)} F κ , c ( x ) = z κ 2 s , c ′ , ℓ ∑ σ κ , s , c ′ , ℓ H 0 , ℓ ( s ) H 0 , ℓ ( x ) , (65) with integer coefficients σ κ , s , c ′ , ℓ \sigma_{\kappa,s,c',\ell} σ κ , s , c ′ , ℓ z κ z_\kappa z κ
F ^ κ , a ( x ) + T ~ a ( x ) − F ^ κ , y ( x ) ( x ) − T ~ y ( x ) ( x ) − 1 2 (66) \widehat{F}_{\kappa,a}(x)+\widetilde{T}_a(x)-\widehat{F}_{\kappa,y(x)}(x)-\widetilde{T}_{y(x)}(x)-\frac{1}{2} \tag*{(66)} F κ , a ( x ) + T a ( x ) − F κ , y ( x ) ( x ) − T y ( x ) ( x ) − 2 1 (66) agrees in sign with a polynomial of degree at most 4, and there are only N ( q − 1 ) N(q-1) N ( q − 1 ) Theorem C.3 again—or the direct 3 M 3^M 3 M exp ( O ( D q p a r log q ) ) \exp(O(D_q^{\mathrm{par}}\log q)) exp ( O ( D q par log q ))
Combining (62) and (64) , the deterministic atlas H q \mathcal{H}_q H q
log ∣ H q ∣ ≤ log # { κ } + O ( D q p a r log q ) = o ( N ) . (67) \log|\mathcal{H}_q|\le\log\#\{\kappa\}+O(D_q^{\mathrm{par}}\log q)=o(N). \tag*{(67)} log ∣ H q ∣ ≤ log # { κ } + O ( D q par log q ) = o ( N ) . (67) Its address set, threshold grid, codes and polynomial list are all fixed before Ω \Omega Ω Ω \Omega Ω
Step 5: concentration. Let X e x c \mathcal{X}_{\mathrm{exc}} X exc 1 / 16 1/16 1/16 η > 0 \eta>0 η > 0 q → ∞ q\to\infty q → ∞
∣ X e x c ∣ ≤ ( η + o ( 1 ) ) N . (68) |\mathcal{X}_{\mathrm{exc}}|\le(\eta+o(1))N. \tag*{(68)} ∣ X exc ∣ ≤ ( η + o ( 1 )) N . (68) Off X e x c \mathcal{X}_{\mathrm{exc}} X exc 1 / 16 1/16 1/16 1 / 16 1/16 1/16 D ~ \widetilde{D} D D D D 3 / 16 3/16 3/16 3 / 8 3/8 3/8
H D ~ = { x : max a ≠ y ( x ) ( D ~ a ( x ) − D ~ y ( x ) ( x ) ) ≥ 1 2 } . (69) H_{\widetilde{D}}=\left\{x:\max_{a\ne y(x)}\left(\widetilde{D}_a(x)-\widetilde{D}_{y(x)}(x)\right)\ge\frac{1}{2}\right\}. \tag*{(69)} H D = { x : a = y ( x ) max ( D a ( x ) − D y ( x ) ( x ) ) ≥ 2 1 } . (69) Hypothesis (1) gives ∣ H D ~ ∩ Ω ∣ ≤ ∣ X e x c ∣ |H_{\widetilde{D}}\cap\Omega|\le|\mathcal{X}_{\mathrm{exc}}| ∣ H D ∩ Ω∣ ≤ ∣ X exc ∣ β N \beta N β N ∣ H D ~ ∣ ≥ β N − ∣ X e x c ∣ ≥ β N / 2 |H_{\widetilde{D}}|\ge\beta N-|\mathcal{X}_{\mathrm{exc}}|\ge\beta N/2 ∣ H D ∣ ≥ β N − ∣ X exc ∣ ≥ β N /2 q q q
Fix any H ⊆ X q H\subseteq X_q H ⊆ X q ∣ H ∣ ≥ β N / 2 |H|\ge\beta N/2 ∣ H ∣ ≥ β N /2 ∣ H ∩ Ω ∣ |H\cap\Omega| ∣ H ∩ Ω∣ α β N / 2 + O ( 1 ) \alpha\beta N/2+O(1) α β N /2 + O ( 1 ) 0 < η < α β / 16 0<\eta<\alpha\beta/16 0 < η < α β /16
P ( ∣ H ∩ Ω ∣ ≤ 2 η N ) = ∑ j ≤ 2 η N ( ∣ H ∣ j ) ( N − ∣ H ∣ n q − j ) ( N n q ) ≤ e − c α , β , η N . (70) \mathbb{P}\left(|H\cap\Omega|\le2\eta N\right)=\sum_{j\le2\eta N}\frac{\binom{|H|}{j}\binom{N-|H|}{n_q-j}}{\binom{N}{n_q}}\le e^{-c_{\alpha,\beta,\eta}N}. \tag*{(70)} P ( ∣ H ∩ Ω∣ ≤ 2 η N ) = j ≤ 2 η N ∑ ( n q N ) ( j ∣ H ∣ ) ( n q − j N − ∣ H ∣ ) ≤ e − c α , β , η N . (70) for some $c_{\alpha,\beta,\eta}>0; the same bound follows from sampling-without-replacement Chernoff estimates [20 ] . Taking a union bound over the exp ( o ( N ) ) \exp(o(N)) exp ( o ( N )) H H H o ( 1 ) o(1) o ( 1 ) D D D 1 2 \frac{1}{2} 2 1
Assembly of part (i)
The proof of Theorem 4.1 (i) is given in full in § 4.1.1 . For the bias transfer of Appendix § 9 .3.5 we record the two gap inequalities in the form used there. With D = 9 F − F q ∗ D=9F-F_q^* D = 9 F − F q ∗ y = C q a d d ( x ) y=C_q^{\mathrm{add}}(x) y = C q add ( x ) γ x , a = F q , y ∗ ( x ) − F q , a ∗ ( x ) ∈ [ 1 , 9 ] \gamma_{x,a}=F_{q,y}^*(x)-F_{q,a}^*(x)\in[1,9] γ x , a = F q , y ∗ ( x ) − F q , a ∗ ( x ) ∈ [ 1 , 9 ]
D y − D a = 9 ( F y − F a ) − γ x , a ≥ 0 on observed cells, since F y − F a ≥ 1 , (71) D_y-D_a=9(F_y-F_a)-\gamma_{x,a}\ge0 \qquad\text{on observed cells, since }F_y-F_a\ge1, \tag*{(71)} D y − D a = 9 ( F y − F a ) − γ x , a ≥ 0 on observed cells, since F y − F a ≥ 1 , (71) and at every held-out non-strict error, including a tie, some a ≠ y a\ne y a = y F a ≥ F y F_a\ge F_y F a ≥ F y
D a − D y = 9 ( F a − F y ) + γ x , a ≥ 1. (72) D_a-D_y=9(F_a-F_y)+\gamma_{x,a}\ge1. \tag*{(72)} D a − D y = 9 ( F a − F y ) + γ x , a ≥ 1. (72) The norm budget is B q B_q B q (14) .
Proof of Lemma 4.5(a). Since C C C L q \mathcal{L}_q L q Ω \Omega Ω P q , τ A ( M u n i f ) = E Ω [ ∣ { C ∈ L q : Acc T ( A q ( D ( C , Ω ) ) ; C ) ≥ τ } ∣ / ∣ L q ∣ ] P_{q,\tau}^{A}(\mathsf{M}_{\mathrm{unif}})=\mathbb{E}_{\Omega}\left[\left|\left\{C\in\mathcal{L}_q:\operatorname{Acc}_{T}(A_q(\mathcal{D}(C,\Omega));C)\ge\tau\right\}\right|/|\mathcal{L}_q|\right] P q , τ A ( M unif ) = E Ω [ ∣ { C ∈ L q : Acc T ( A q ( D ( C , Ω )) ; C ) ≥ τ } ∣ /∣ L q ∣ ] Ω \Omega Ω q n q q^{nq} q n q D \mathcal{D} D
Success means the true Latin table differs from the winner table on at most r r r
∑ i = 0 r ( N − n q i ) ( q − 1 ) i , (73) \sum_{i=0}^{r}\binom{N-n_q}{i}(q-1)^i, \tag*{(73)} i = 0 ∑ r ( i N − n q ) ( q − 1 ) i , (73) and restricting to Latin arrays can only decrease the count. Summing over all D \mathcal{D} D (16) .
Proof of Lemma 4.5(b). By the permanent bound in Theorem C.4 , if B B B q × q q\times q q × q per ( B ) ≥ q ! / q q \operatorname{per}(B)\ge q!/q^q per ( B ) ≥ q ! / q q
Build the Latin square row by row. When k k k ( q − k ) (q-k) ( q − k ) q − k q-k q − k
( q − k ) q q ! q q . (74) (q-k)^q\frac{q!}{q^q}. \tag*{(74)} ( q − k ) q q q q ! . (74) The first row admits q ! q! q !
∣ L q ∣ ≥ q ! ∏ k = 1 q − 1 ( q − k ) q q ! q q = ( q ! ) 2 q q q 2 . (75) |\mathcal{L}_q|\ge q!\prod_{k=1}^{q-1}\frac{(q-k)^q q!}{q^q}=\frac{(q!)^{2q}}{q^{q^2}}. \tag*{(75)} ∣ L q ∣ ≥ q ! k = 1 ∏ q − 1 q q ( q − k ) q q ! = q q 2 ( q ! ) 2 q . (75) Finally log ( q ! ) = ∑ j = 1 q log j ≥ ∫ 1 q log x d x = q log q − q + 1 \log(q!)=\sum_{j=1}^{q}\log j\ge\int_1^q\log x\,\mathrm{d}x=q\log q-q+1 log ( q !) = ∑ j = 1 q log j ≥ ∫ 1 q log x d x = q log q − q + 1 q ! ≥ ( q / e ) q q!\ge(q/e)^q q ! ≥ ( q / e ) q ( q / e 2 ) q 2 (q/e^2)^{q^2} ( q / e 2 ) q 2
L2-regularised biases
Proof of Lemma B.3. For fixed Z = W Φ Z=W\Phi Z = W Φ (34) gives
inf W Φ = Z 1 2 ( ∥ W ∥ F 2 + ∥ Φ ∥ F 2 ) = ∥ Z ∥ ∗ . (76) \inf_{W\Phi=Z}\frac{1}{2}\left(\lVert W\rVert_F^2+\lVert\Phi\rVert_F^2\right)=\lVert Z\rVert_*. \tag*{(76)} W Φ = Z inf 2 1 ( ∥ W ∥ F 2 + ∥ Φ ∥ F 2 ) = ∥ Z ∥ ∗ . (76) Every admissible Z Z Z 2 q 2q 2 q d q = 2 q + 1 d_q=2q+1 d q = 2 q + 1 (76) respects the embedding dimension; zero padding respects the hidden width. Keeping A A A b b b c c c min F b Φ b \min_{\mathcal{F}_b}\Phi_b min F b Φ b Proposition 3.3 is feasible with b = c = 0 b=c=0 b = c = 0
Let F q ∗ F_q^* F q ∗ J c a r J_{\mathrm{car}} J car b = c = 0 b=c=0 b = c = 0 M q M_q M q
M q : = min F b Φ b ≤ 3 2 J c a r 2 / 3 ≤ C 1 q 2 / 3 ( log q ) 1 / 3 . (77) M_q := \min_{\mathcal{F}_b} \Phi_b \le\frac{3}{2}J_{\mathrm{car}}^{2/3} \le C_1q^{2/3}(\log q)^{1/3}. \tag*{(77)} M q := F b min Φ b ≤ 2 3 J car 2/3 ≤ C 1 q 2/3 ( log q ) 1/3 . (77) for an absolute constant C 1 C_1 C 1
∥ Z ∥ ∗ ≤ M q , ∥ A ∥ F , ∥ b ∥ 2 , ∥ c ∥ 2 ≤ 2 M q . (78) \lVert Z\rVert_* \le M_q,\qquad\lVert A\rVert_F,\lVert b\rVert_2,\lVert c\rVert_2 \le\sqrt{2M_q}. \tag*{(78)} ∥ Z ∥ ∗ ≤ M q , ∥ A ∥ F , ∥ b ∥ 2 , ∥ c ∥ 2 ≤ 2 M q . (78) The hidden bias can be absorbed into the two endpoint blocks. Put
Z ‾ = Z + 1 2 b 1 2 q T . (79) \overline{Z}=Z+\frac{1}{2}b\mathbf{1}_{2q}^{\mathsf T}. \tag*{(79)} Z = Z + 2 1 b 1 2 q T . (79) Since ξ x \xi_x ξ x Z ‾ ξ x = Z ξ x + b \overline{Z}\xi_x=Z\xi_x+b Z ξ x = Z ξ x + b q / 2 ∥ b ∥ 2 \sqrt{q/2}\lVert b\rVert_2 q /2 ∥ b ∥ 2
∥ Z ‾ ∥ ∗ ≤ M q + q M q . (80) \lVert\overline{Z}\rVert_* \le M_q+\sqrt{qM_q}. \tag*{(80)} ∥ Z ∥ ∗ ≤ M q + q M q . (80) It follows that F 0 ( x ) = A ReLU ( Z ‾ ξ x ) F_0(x)=A\operatorname{ReLU}(\overline{Z}\xi_x) F 0 ( x ) = A ReLU ( Z ξ x )
J ( F 0 ) ≤ 2 M q ( M q + q M q ) . (81) J(F_0)\le\sqrt{2M_q}\left(M_q+\sqrt{qM_q}\right). \tag*{(81)} J ( F 0 ) ≤ 2 M q ( M q + q M q ) . (81) The constant table F c ( x ) = c F_c(x)=c F c ( x ) = c z c = 1 2 1 2 q T z_c=\frac{1}{2}\mathbf{1}_{2q}^{\mathsf T} z c = 2 1 1 2 q T ReLU ( z c ξ x ) = 1 \operatorname{ReLU}(z_c\xi_x)=1 ReLU ( z c ξ x ) = 1 c c c
J ( F c ) ≤ q M q . (82) J(F_c)\le\sqrt{qM_q}. \tag*{(82)} J ( F c ) ≤ q M q . (82) If F 1 , F 2 F_1,F_2 F 1 , F 2 J 1 , J 2 J_1,J_2 J 1 , J 2
J ( F 1 + F 2 ) ≤ ( J 1 + J 2 ) 2 ≤ 2 ( J 1 + J 2 ) . (83) J(F_1+F_2)\le\left(\sqrt{J_1}+\sqrt{J_2}\right)^2\le2(J_1+J_2). \tag*{(83)} J ( F 1 + F 2 ) ≤ ( J 1 + J 2 ) 2 ≤ 2 ( J 1 + J 2 ) . (83) Applying (83) to F = F 0 + F c F=F_0+F_c F = F 0 + F c
J ( F ) ≤ 2 [ 2 M q ( M q + q M q ) + q M q ] (84) J(F)\le2\left[\sqrt{2M_q}\left(M_q+\sqrt{qM_q}\right)+\sqrt{qM_q}\right] \tag*{(84)} J ( F ) ≤ 2 [ 2 M q ( M q + q M q ) + q M q ] (84) = O ( M q 3 / 2 + q M q + q M q ) (85) =O\left(M_q^{3/2}+\sqrt{q}M_q+\sqrt{qM_q}\right) \tag*{(85)} = O ( M q 3/2 + q M q + q M q ) (85) = O ( q 7 / 6 ( log q ) 1 / 3 ) , (86) =O\left(q^{7/6}(\log q)^{1/3}\right), \tag*{(86)} = O ( q 7/6 ( log q ) 1/3 ) , (86) which proves the bound of Lemma B.3.
Proof of Corollary B.4. The bias-free feasible set embeds into the biased one by taking b = c = 0 b=c=0 b = c = 0 b b b c c c A A A
For addition, let F F F
J ( F ) = O ( q 7 / 6 ( log q ) 1 / 3 ) . (87) J(F)=O\left(q^{7/6}(\log q)^{1/3}\right). \tag*{(87)} J ( F ) = O ( q 7/6 ( log q ) 1/3 ) . (87) Set D = 9 F − F q ∗ D=9F-F_q^* D = 9 F − F q ∗
J ( D ) ≤ 2 ( 9 J ( F ) + J ( F q ∗ ) ) = O ( q 7 / 6 ( log q ) 1 / 3 ) , (88) J(D)\le2\left(9J(F)+J(F_q^*)\right)=O\left(q^{7/6}(\log q)^{1/3}\right), \tag*{(88)} J ( D ) ≤ 2 ( 9 J ( F ) + J ( F q ∗ ) ) = O ( q 7/6 ( log q ) 1/3 ) , (88) and therefore
J ( D ) 2 log q q 5 / 2 = O ( q − 1 / 6 ( log q ) 5 / 3 ) → 0. (89) \frac{J(D)^2\log q}{q^{5/2}}=O\left(q^{-1/6}(\log q)^{5/3}\right)\to0. \tag*{(89)} q 5/2 J ( D ) 2 log q = O ( q − 1/6 ( log q ) 5/3 ) → 0. (89) For any fixed τ < 1 \tau< 1 τ < 1 τ \tau τ ( 1 − τ ) ( 1 − α ) N (1-\tau)(1-\alpha)N ( 1 − τ ) ( 1 − α ) N β = 1 2 ( 1 − τ ) ( 1 − α ) \beta= \frac{1}{2}(1-\tau)(1-\alpha) β = 2 1 ( 1 − τ ) ( 1 − α ) 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) τ < 1 \tau< 1 τ < 1
The proof of Lemma 4.5 uses only observation measurability of the predicted table. It therefore applies verbatim to every biased minimum-norm selector and gives Corollary B.4(iii). On a biased all-good instance every such selector succeeds, which proves P q , τ v , b ( M u n i f ) → 0 P^{\mathrm{v},b}_{q,\tau}(M_{\mathrm{unif}}) \to0 P q , τ v , b ( M unif ) → 0
For the finite-instance claim, let
g b = min F b Φ b , E g , b = { ( A , Z , b , c ) ∈ F b : Φ b ( A , Z , b , c ) = g b } . (90) g_b = \min_{\mathcal{F}_b} \Phi_b,\qquad E_{g,b} = \{(A,Z,b,c) \in\mathcal{F}_b : \Phi_b(A,Z,b,c)=g_b\}. \tag*{(90)} g b = F b min Φ b , E g , b = {( A , Z , b , c ) ∈ F b : Φ b ( A , Z , b , c ) = g b } . (90) This set is non-empty and compact. By (76), its score responses are exactly the original biased global responses. The held-out margins and their finite order statistics are continuous on E g , b E_{g,b} E g , b k k k k = ⌈ τ ∣ T ∣ ⌉ k = \lceil\tau|T| \rceil k = ⌈ τ ∣ T ∣ ⌉
Classification readiness
Proof of Theorem B.6. Assume first that U q , τ → 0 U_{q,\tau} \to0 U q , τ → 0 t t t t ( 1 − t ) = 0 t(1-t)=0 t ( 1 − t ) = 0 t ∈ { 0 , 1 } t \in\{0,1\} t ∈ { 0 , 1 } t = 1 t=1 t = 1 v \mathbf{v} v t = 0 t=0 t = 0 e \mathbf{e} e K ∞ , τ ⊆ { v } ∪ e K_{\infty,\tau} \subseteq\{\mathbf{v}\} \cup\mathbf{e} K ∞ , τ ⊆ { v } ∪ e v ∈ K ∞ , τ \mathbf{v} \in K_{\infty,\tau} v ∈ K ∞ , τ e ⊆ K ∞ , τ \mathbf{e} \subseteq K_{\infty,\tau} e ⊆ K ∞ , τ K ∞ , τ = { v } ∪ e K_{\infty,\tau} = \{\mathbf{v}\} \cup\mathbf{e} K ∞ , τ = { v } ∪ e
Conversely suppose K ∞ , τ = { v } ∪ e K_{\infty,\tau} = \{\mathbf{v}\} \cup\mathbf{e} K ∞ , τ = { v } ∪ e lim sup q → ∞ U q , τ > 0 \limsup_{q\to\infty} U_{q,\tau} > 0 lim sup q → ∞ U q , τ > 0 δ > 0 \delta> 0 δ > 0 q j → ∞ q_j \to\infty q j → ∞ [ C q j ] [C_{q_j}] [ C q j ]
p q j , τ ∇ ( [ C q j ] ) ( 1 − p q j , τ ∇ ( [ C q j ] ) ) ≥ δ . (91) p^{\nabla}_{q_j,\tau}([C_{q_j}])\left(1-p^{\nabla}_{q_j,\tau}([C_{q_j}])\right) \ge\delta. \tag*{(91)} p q j , τ ∇ ([ C q j ]) ( 1 − p q j , τ ∇ ([ C q j ]) ) ≥ δ . (91) The probability simplex is compact, so we may extract a further subsequence along which the profile converges. Its first coordinate lies strictly inside ( 0 , 1 ) (0,1) ( 0 , 1 ) v \mathbf{v} v e \mathbf{e} e K ∞ , τ = { v } ∪ e K_{\infty,\tau} = \{\mathbf{v}\} \cup\mathbf{e} K ∞ , τ = { v } ∪ e U q , τ → 0 U_{q,\tau} \to0 U q , τ → 0 K ∞ , τ = { v } ∪ e K_{\infty,\tau} = \{\mathbf{v}\} \cup\mathbf{e} K ∞ , τ = { v } ∪ e e \mathbf{e} e K ∞ , τ K_{\infty,\tau} K ∞ , τ
The final coordinate characterisation is immediate from p q , τ ∇ + p q , τ m i x + p q , τ ∅ = 1 p^{\nabla}_{q,\tau} + p^{\mathrm{mix}}_{q,\tau} + p^{\varnothing}_{q,\tau} = 1 p q , τ ∇ + p q , τ mix + p q , τ ∅ = 1
External results used
We state the covering/counting results, permanent bound, sampling estimates, and character identities in the forms used in the proofs.
Theorem C.1 [62 Theorem 4] . Let sample vectors satisfy ∥ x i ∥ p ≤ b \|x_i\|_p \le b ∥ x i ∥ p ≤ b and linear weights satisfy ∥ w ∥ r ≤ a \|w\|_r \le a ∥ w ∥ r ≤ a where 2 ≤ p ≤ ∞ 2 \le p \le\infty 2 ≤ p ≤ ∞ and 1 / p + 1 / r = 1 1/p+1/r=1 1/ p + 1/ r = 1 Then for every ε > 0 \varepsilon> 0 ε > 0 the empirical ℓ ∞ \ell_\infty ℓ ∞ covering number of the linear function class on these n n n samples satisfies
log 2 N ∞ ≤ 36 ( p − 1 ) a 2 b 2 ε − 2 log 2 ( 2 ⌈ 4 a b / ε + 2 ⌉ n + 1 ) . (92) \log_2 N_\infty\le36(p-1)a^2b^2\varepsilon^{-2}\log_2(2\lceil4ab/\varepsilon+2\rceil n+1). \tag*{(92)} log 2 N ∞ ≤ 36 ( p − 1 ) a 2 b 2 ε − 2 log 2 ( 2 ⌈ 4 ab / ε + 2 ⌉ n + 1 ) . (92) Theorem C.2 [25 Proposition 5] . Let X ∈ R n × U d X \in\mathbb{R}^{n\times U^d} X ∈ R n × U d with ∥ X i , u , : ∥ 2 ≤ b \|X_{i,u,:}\|_2 \le b ∥ X i , u , : ∥ 2 ≤ b for every patch. For any reference M M M the matrix class { X A : ∥ A − M ∥ F ≤ a } \{XA:\|A-M\|_F \le a\} { X A : ∥ A − M ∥ F ≤ a } admits an entrywise ℓ ∞ \ell_\infty ℓ ∞ cover over all sample, patch and output-channel coordinates with
log N ≤ 36 a 2 b 2 ε − 2 log 2 ( ( ( 8 a b / ε ) + 7 ) m n U ) , (93) \log N \le36a^2b^2\varepsilon^{-2}\log_2(((8ab/\varepsilon)+7)mnU), \tag*{(93)} log N ≤ 36 a 2 b 2 ε − 2 log 2 ((( 8 ab / ε ) + 7 ) mn U ) , (93) where m m m is the number of output channels.
Theorem C.2 is the block-diagonal lift of Theorem C.1 to the index triple (sample, patch, output channel), which is exactly the form we need in Step 3 of the proof of Lemma 4.3.
Theorem C.3 [5 Corollary 3.2] . For M ≥ n M \ge n M ≥ n d ≥ 1 d \ge1 d ≥ 1 n n n { − 1 , 0 , 1 } M \{-1,0,1\}^{M} { − 1 , 0 , 1 } M
( 8 e d M / n ) n . (94) (8edM/n)^n. \tag*{(94)} ( 8 e d M / n ) n . (94) Zeros are counted in (94) , which is why exact zero ReLU gates and exact score ties survive our enumeration. This is the multi-valued refinement of the classical bound of Warren [57 ] .
Theorem C.4 (van der Waerden permanent bound; Gurvits [18 ] , diagonal specialisation). If B B B q × q q \times q q × q
per ( B ) ≥ q ! / q q . (95) \operatorname{per}(B) \ge q!/q^q. \tag*{(95)} per ( B ) ≥ q ! / q q . (95) The bound (95) was conjectured by van der Waerden and first proved by Falikman (1981), with the uniqueness statement due to Egorychev [10 ] ; we quote the hyperbolic-polynomial proof of Gurvits [18 ] because its diagonal specialisation yields exactly the inequality we use.
Lemma C.5 (Hilbert-space sampling; Pisier [41 ] ). Let f = ∑ i v i f = \sum_i v_i f = ∑ i v i S = ∑ i ∥ v i ∥ S = \sum_i \lVert v_i\rVert S = ∑ i ∥ v i ∥ K ≥ 1 K \ge1 K ≥ 1 K K K S 2 / K S^2/K S 2 / K S > 0 S > 0 S > 0 i i i ∥ v i ∥ / S \lVert v_i\rVert/S ∥ v i ∥ / S S v i / ∥ v i ∥ Sv_i/\lVert v_i\rVert S v i / ∥ v i ∥
Proof. Each sampled atom has mean f f f S 2 S^2 S 2 K K K ( S 2 − ∥ f ∥ 2 ) / K ≤ S 2 / K (S^2-\lVert f\rVert^2)/K \le S^2/K ( S 2 − ∥ f ∥ 2 ) / K ≤ S 2 / K S = 0 S=0 S = 0
Theorem C.6 (Bounded sampling; Hoeffding [20 ] ). If Y 1 , … , Y L Y_1,\ldots,Y_L Y 1 , … , Y L [ a , b ] [a,b] [ a , b ] a < b a<b a < b t > 0 t>0 t > 0
P [ 1 L ∑ i = 1 L ( Y i − E Y i ) ≥ t ] ≤ exp ( − 2 L t 2 ( b − a ) 2 ) . (96) \mathbb{P}\left[\frac{1}{L}\sum_{i=1}^{L}(Y_i-\mathbb{E}Y_i)\ge t\right]\le\exp\left(-\frac{2Lt^2}{(b-a)^2}\right). \tag*{(96)} P [ L 1 i = 1 ∑ L ( Y i − E Y i ) ≥ t ] ≤ exp ( − ( b − a ) 2 2 L t 2 ) . (96) The same bound, including the lower-tail version, holds for a uniform sample without replacement from a finite population in [ a , b ] [a,b] [ a , b ] (70) .
Proposition C.7 (Finite-group character identities; Etingof et al. [12 ] ). For a finite abelian group G G G G ^ \widehat{G} G ∣ G ∣ \lvert G\rvert ∣ G ∣ χ ( u + v ) = χ ( u ) χ ( v ) \chi(u+v)=\chi(u)\chi(v) χ ( u + v ) = χ ( u ) χ ( v ) ∑ χ ∈ G ^ χ ( g ) = ∣ G ∣ 1 { g = 0 } \sum_{\chi\in\widehat{G}}\chi(g)=\lvert G\rvert\mathbf{1}\{g=0\} ∑ χ ∈ G χ ( g ) = ∣ G ∣ 1 { g = 0 } π \pi π d π d_\pi d π χ π \chi_\pi χ π
∑ π ∈ G ^ d π 2 = ∣ G ∣ , ∑ π ∈ G ^ d π χ π ( g ) = ∣ G ∣ 1 { g = e } . (97) \sum_{\pi\in\widehat{G}}d_\pi^2=\lvert G\rvert,\qquad\sum_{\pi\in\widehat{G}}d_\pi\chi_\pi(g)=\lvert G\rvert\mathbf{1}\{g=e\}. \tag*{(97)} π ∈ G ∑ d π 2 = ∣ G ∣ , π ∈ G ∑ d π χ π ( g ) = ∣ G ∣ 1 { g = e } . (97) Experimental Protocols and Supplementary Results
This appendix specifies the finite-training protocol, gives the complete run-level results behind Figure 2 and Figure 3 , and records the supplementary analyses and controls; the group-family runs of Table 1 are part of the order-64 structure sweep audited in Appendix D.7. The experiments train the model class of the theory, the pair-embedding one-hidden-layer ReLU network of Section 3.2 with the L 2 L_2 L 2
Figure 2. Relabelled addition groks like addition.
Protocol
Model and optimisation. The network (“PairMLP”, named for its pair embedding) has separate trainable row and column embedding tables E U E_U E U E V E_V E V R 128 \mathbb{R}^{128} R 128 q q q d q = 2 q + 1 d_q=2q+1 d q = 2 q + 1 h q = q 2 h_q=q^2 h q = q 2 § 11 .§ 1 ). The common design that shares one embedding table and concatenates the two embedded inputs is the special case E U = W 1 E E_U = W_1 E E U = W 1 E E V = W 2 E E_V = W_2 E E V = W 2 E
Masks. The q = 97 q = 97 q = 97 0.30 q 2 0.30q^2 0.30 q 2 (1) uses a floor. The q = 64 q = 64 q = 64
832 / 4096 = 20.3125 % (nominal 20%), 1216 / 4096 = 29.6875 % (nominal 30%), 1664 / 4096 = 40.625 % (nominal 40%). (98) \begin{aligned}
832/4096 &= 20.3125\% \quad\text{(nominal 20\%),}\\
1216/4096 &= 29.6875\% \quad\text{(nominal 30\%),}\\
1664/4096 &= 40.625\% \quad\text{(nominal 40\%).} \tag*{(98)}
\end{aligned} 832/4096 1216/4096 1664/4096 = 20.3125% (nominal 20%), = 29.6875% (nominal 30%), = 40.625% (nominal 40%). (98) For the coverage experiment, each colour has one random ordering and the masks are prefixes of that ordering, so the three levels are nested.
Seeds and reporting units. A task seed selects a table, product residual, or coordinate relabelling; a training seed selects the initialisation and optimisation repeat. Every point in the main figures is one training run; saturated markers and lines report medians.
Relative transition. The transition statistic locates sustained training memorisation, estimates a pre-generalisation test plateau and a stable terminal plateau, and counts a run when its test accuracy crosses the midpoint of that run’s plateau-relative gain. It permits terminal accuracy below one; absolute endpoint accuracy is reported separately, and 0.99 is a reporting cutoff unrelated to the threshold τ \tau τ
Addition coverage across orders
The archived addition experiments vary the order q q q α \alpha α α \alpha α α ^ q \hat{\alpha}_q α ^ q § 10 .§ 1 . Each grid point costs one training run per seed, so the sweep covers four orders, q ∈ { 47 , 79 , 113 , 211 } q \in\{47, 79, 113, 211\} q ∈ { 47 , 79 , 113 , 211 }
The measured fraction falls from 0.33 at q = 47 q = 47 q = 47 q = 211 q = 211 q = 211 α q \alpha_q α q
The order-97 orbit comparison
The hidden-addition experiment samples ten independent triples of row, column, and symbol permutations of one cyclic-addition table. Each representation is trained under three optimisation seeds, giving 30 runs. The Latin control uses eight task seeds from the sequential random-perfect-matching generator and three optimisation seeds, giving 24 runs. Two further planned control seeds were never completed and are excluded. A one-way random-effects decomposition of the transition midpoint over the ten task seeds with three optimisation seeds each attributes about 7% of the variance to task seed and about 93% to the optimisation seed (variance-components estimate; the fixed-effects η 2 \eta^2 η 2 F ( 9 , 20 ) = 1.22 F(9, 20) = 1.22 F ( 9 , 20 ) = 1.22 p ≈ 0.33 p \approx0.33 p ≈ 0.33
Table 5. Index of the machine-readable sparse coefficient archives. Each CSV stores the nonzero triples ( i , j , a i j ) (i, j, a_{ij}) ( i , j , a ij ) F 97 \mathbb{F}_{97} F 97
For the polynomial statistics illustrated in Figure 1 , we reconstruct the unique reduced polynomial over F 97 \mathbb{F}_{97} F 97 Table 4 reports the result. The hidden representatives occupy the same colouring orbit as X + Y X + Y X + Y
Table 4. Reduced-polynomial reconstruction at q = 97 q = 97 q = 97 97 2 = 9409 97^2 = 9409 9 7 2 = 9409
Machine-readable coefficient archive
For every unique task instance in the order-97 comparison, we archive the unique reduced coefficient matrix over F 97 \mathbb{F}_{97} F 97 ( i , j , a i j ) (i,j,a_{ij}) ( i , j , a ij ) a i j X i Y j a_{ij}X^iY^j a ij X i Y j i i i j j j materials/polynomial-coefficients/ in the submission bundle. It also contains manifest.csv, which records the source experiment, support statistics, degree statistics, relative file path, and full SHA-256 digest. The 19 archived task instances comprise visible addition, ten hidden-addition relabellings, and eight sequential-Latin controls.
The median hidden-addition support is 9124/9409 = 96.971%. Its 30 endpoint accuracies have median 1.000 and range 0.969025–1.000; all 30 runs pass the relative-transition criterion. The 24 sequential-Latin endpoints have median 4.56 × 10 − 4 4.56 \times10^{-4} 4.56 × 1 0 − 4 1.37 × 10 − 3 1.37 \times10^{-3} 1.37 × 1 0 − 3 Unif ( L q ) \operatorname{Unif}(L_q) Unif ( L q )
Complete endpoint summaries for the open-region experiments
The designated-factor experiment (left panel of Figure 3 ) uses five q = 64 q = 64 q = 64 Table 6 lists the final exact accuracy and the prespecified binary factor quotient. The R 64 R_{64} R 64
Table 6. Final medians at nominal 30% label-stratified coverage; six runs per family.
The run-level binary factor-quotient ranges for the two hardest structured families are 0.456–0.989 for C 2 2 × R 16 C_2^2 \times R_{16} C 2 2 × R 16 C 2 × R 32 C_2 \times R_{32} C 2 × R 32 Figure 3 .
Table 7 gives all median resolutions used in the matched nested-mask comparison. Every entry aggregates the same two task seeds and two training seeds, giving four matched triplets per family.
Table 7. Final held-out accuracy under nested masks. A dash denotes a factor quotient absent from the factor chain.
Factor-quotient lattice and intervention analyses
Section 5 evaluates prespecified product-factor quotients at the final checkpoint. The supplementary mechanism audit expands the evaluation to every checkpoint and, for elementary 2-group factors, to all factor-quotient directions of a fixed order. Eighteen runs contribute nine saved checkpoints each. The audit contains 550 factor-quotient-lattice records, 148 probe/intervention records, and 32 matched random-partition controls.
Two observations refine the endpoint picture. First, different optimisation runs can select different isomorphic binary factor-quotient directions. In one C 2 2 × R 16 C_2^2 \times R_{16} C 2 2 × R 16
These analyses concern representation dynamics along the trajectory; their role here is to confirm that the factor-quotient accuracies in Figure 3 reflect structured label resolution rather than the contribution of exact hits to a coarse score.
Supplementary families and negative controls
Several additional sweeps delimit the empirical interpretation.
A product ladder from C 64 C_{64} C 64 C 8 × R 8 C_8 \times R_8 C 8 × R 8 C 4 × R 16 C_4 \times R_{16} C 4 × R 16 C 2 × R 32 C_2 \times R_{32} C 2 × R 32 R 64 R_{64} R 64 C 8 × R 8 C_8 \times R_8 C 8 × R 8
Sparse perturbations of the cyclic table yield a finite crossover at corruption levels around 2–5%. Forty valid runs remain after removing task-seed collisions. These endpoints quantify robustness to leaving the group orbit and carry no asymptotic phase label.
Timing-only weight-decay and angular-clock analyses remain in the experiment archive as analyses of trajectory delay.
Completeness and reproducibility audit
The order-64 structure sweep contains 72/72 completed runs and the factor-quotient sweep contains 64/64 completed runs, all reaching 80,000 updates. Stored manifests and checkpoint hashes pass the archive checks. The order-97 Latin control contributes the 24 completed runs specified in Appendix D.3; denominators use completed runs only.
Archived run identities record a base commit and a dirty-worktree flag, so exact reproduction requires the frozen source snapshot, which the submission archive preserves together with the run manifests, analysis script, endpoint CSVs, figure inputs, and the finite-field polynomial reconstruction table.
Discussion
The first two subsections discuss the stability of the all-good proof and the relation between endpoints and training timescales. The third turns to task structure: it extracts a colouring-independent carrier criterion, proves the all-good conclusion for every finite abelian group family, and examines the necessity conjecture stated in Conjecture 5.1.
What the all-good proof rests on
The competition. Stripped of its construction, the proof of Theorem 4.1(i) is the competition (13) between a counting term and a deviation term. H q \mathcal{H}_q H q (67) : the enumeration, fixed before the mask is drawn, of every cell set on which a low-norm score table can be confidently wrong while remaining consistent on the observed cells. The exponent c N cN c N (70) is the large-deviation price a positive-density set pays to meet a uniform mask of density α \alpha α log ∣ H q ∣ \log|\mathcal{H}_q| log ∣ H q ∣ (67) gives log ∣ H q ∣ = o ( N ) \log|\mathcal{H}_q|=o(N) log ∣ H q ∣ = o ( N ) log ∣ H q ∣ \log|\mathcal{H}_q| log ∣ H q ∣ Ω \Omega Ω
Stability in width. Lemma 4.3 quantifies over tables of any finite width, and the atlas dimension of (64) , D q p a r ≤ 2 q m + m K 0 + 5 q K 1 = O ( q 3 / 2 + r q 2 / q + q ) D_q^{\mathrm{par}}\leq2qm+mK_0+5qK_1=O(q^{3/2}+rq^2/\sqrt{q}+q) D q par ≤ 2 q m + m K 0 + 5 q K 1 = O ( q 3/2 + r q 2 / q + q ) m = ⌈ q ⌉ m=\lceil\sqrt{q}\rceil m = ⌈ q ⌉ K 0 , K 1 K_0,K_1 K 0 , K 1 (54) depend only on q q q B q B_q B q r q r_q r q K 0 K_0 K 0 ∥ A ∥ F ∥ Z ∥ ∗ \lVert A\rVert_F\lVert Z\rVert_* ∥ A ∥ F ∥ Z ∥ ∗ O ( q log q ) O(q\log q) O ( q log q ) n n n
Fragility in depth. There is no depth-L L L (67) are tied to a single hidden layer. The variational identity behind a two-factor L 2 L_2 L 2 ∥ A ∥ F ∥ Z ∥ ∗ \lVert A\rVert_F\lVert Z\rVert_* ∥ A ∥ F ∥ Z ∥ ∗ L L L (49) that caps each normalised gate at 2 q 2q 2 q L L L L L L
The empirical record on depth. Fan et al. [14 ] train 12-layer MLPs, find deep networks at least as susceptible to delayed generalisation as shallow ones, and find that internal feature rank, not weight norm, tracks the transition; Manir & Rupa [33 ] report a non-monotone depth effect on modular addition, with depth-4 MLPs failing to grok and depth-8 residual networks recovering generalisation. Both point to architectures in which upper layers are forced to track a representation built below, which is also the situation the atlas argument can cover: a single controlled map over a given feature table. A norm bound over a solution set and a rank statistic along a trajectory answer different questions, and a trajectory-level account of depth would likely be organised around a different quantity than the one controlled here.
Timescales, and the extent to which they decouple
Scope. The phase of (6) is a property of the solution set S q ( D ) S_q(\mathcal{D}) S q ( D ) § 4.1 would read identically if the optimiser reached its endpoint immediately. The transition statistic of Appendix § 10 .§ 1 is a reporting device, not an object the theory predicts.
What our measurements show. The order-97 orbit comparison is a clean instrument for the separation: all ten hidden-addition tasks are relabellings of one addition table, so Theorem 3.5 makes the phase constant along the orbit, and the trained predictors have concentrated final accuracies (30/30 transitions, median 1.000, range 0.969–1.000). The delay is not constant: midpoints span 13,000–21,000 updates, with about 93% of their variance attributable to the optimisation seed (Appendix § 10 .§ 3 ). Within one orbit the phase is invariant and the delay is dominated by optimisation randomness. This does not establish that endpoint and delay are independent: every family we sweep either fixes the task and varies the optimiser, or varies the task and reports endpoints; none varies task structure while measuring delay under a comparable phase.
Where the coupling is visible. Gu et al. [17 ] distinguish the accuracy ceiling from the training process leading to it, and their experiments measure both the ceiling and transition time. At p = 97 p = 97 p = 97 i , j ≤ k i,j \le k i , j ≤ k i ≤ t i \le t i ≤ t Table 8 ). Enlarging the excision lowers the ceiling monotonically and shifts the transition epoch non-monotonically; the widest strip removes the transition. Under a random split the same configuration transitions near epoch 5000 and reaches accuracy 1. One manipulation thus moves ceiling and delay together.
Table 8. Excised training distributions at p = 97 p = 97 p = 97 [17 ] . U-Acc is the accuracy ceiling after the transition, GO-Epoch the epoch at which it occurs.
A ceiling below one, with runs halting at different accuracies, is not evidence of the mixed phase: that phase concerns the exact minimum-norm set (Proposition B.2), and no training curve reports it.
How this sits against our framework. Both of their manipulations fall outside our hypotheses in instructive ways. The excisions keep the colouring at C q a d d C_q^{\mathrm{add}} C q add ν q \nu_q ν q ∣ H ∩ Ω ∣ |H \cap\Omega| ∣ H ∩ Ω∣ f ( i , j ) = i 2 + i j + j 2 f(i,j)=i^2+ij+j^2 f ( i , j ) = i 2 + ij + j 2 i i i j j j L q \mathcal{L}_q L q
What the all-good proof needs from the colouring
Appendix E.1 asked what the proof is stable to as the model varies. Here we vary the colouring while keeping the bias-free model, the product norm (4), and the mask law (1) fixed. Only the carrier construction uses addition; the counting argument that turns a carrier into an all-good statement does not.
A colouring-independent notch and a carrier criterion
Lemma E.1 (One-sided notch for any colouring). Fix α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) C q ∈ C q C_q\in\mathcal{C}_q C q ∈ C q B q B_q B q B q 2 log q / q 5 / 2 → 0 B_q^2\log q/q^{5/2}\to0 B q 2 log q / q 5/2 → 0 With probability 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) Ω ∼ ν q \Omega\sim\nu_q Ω ∼ ν q D ( x ) = A ReLU ( Z ξ x ) D(x)=A\operatorname{ReLU}(Z\xi_x) D ( x ) = A ReLU ( Z ξ x ) ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q \lVert A\rVert_F\lVert Z\rVert_*\le B_q ∥ A ∥ F ∥ Z ∥ ∗ ≤ B q
(1) D C q ( x ) ( x ) − D a ( x ) ≥ 0 D_{C_q(x)}(x)-D_a(x)\ge0 D C q ( x ) ( x ) − D a ( x ) ≥ 0 x ∈ Ω x\in\Omega x ∈ Ω a ≠ C q ( x ) a\ne C_q(x) a = C q ( x )
(2) at least β N \beta N β N a ≠ C q ( x ) a\ne C_q(x) a = C q ( x ) D a ( x ) − D C q ( x ) ( x ) ≥ 1 D_a(x)-D_{C_q(x)}(x)\ge1 D a ( x ) − D C q ( x ) ( x ) ≥ 1
The failure bound is uniform in the choice of the deterministic colouring.
Proof. In Appendix C.3.2, replace y ( x ) = C q a d d ( x ) y(x)=C_q^{\mathrm{add}}(x) y ( x ) = C q add ( x ) y ( x ) = C q ( x ) y(x)=C_q(x) y ( x ) = C q ( x ) ξ \xi ξ N ( q − 1 ) N(q-1) N ( q − 1 ) C q C_q C q
Proposition E.2 (Carrier criterion). Let C q ∈ C q C_q\in\mathcal{C}_q C q ∈ C q Suppose that, for every sufficiently large q q q it admits a full-grid carrier F q ⋆ = A c a r ReLU ( Z c a r ξ ⋅ ) F_q^\star=A_{\mathrm{car}}\operatorname{ReLU}(Z_{\mathrm{car}}\xi_\cdot) F q ⋆ = A car ReLU ( Z car ξ ⋅ ) of width at most h q = N h_q=N h q = N with J c a r , q : = ∥ A c a r ∥ F ∥ Z c a r ∥ ∗ J_{\mathrm{car},q}:=\lVert A_{\mathrm{car}}\rVert_F\lVert Z_{\mathrm{car}}\rVert_* J car , q := ∥ A car ∥ F ∥ Z car ∥ ∗ and Γ q ≥ 1 \Gamma_q\ge1 Γ q ≥ 1 satisfying
1 ≤ F q , C q ( x ) ⋆ ( x ) − F q , a ⋆ ( x ) ≤ Γ q ( x ∈ X q , a ≠ C q ( x ) ) , (99) 1\le F^\star_{q,C_q(x)}(x)-F^\star_{q,a}(x)\le\Gamma_q\qquad(x\in X_q,\ a\ne C_q(x)), \tag*{(99)} 1 ≤ F q , C q ( x ) ⋆ ( x ) − F q , a ⋆ ( x ) ≤ Γ q ( x ∈ X q , a = C q ( x )) , (99) \[
\Gamma_qJ_{\mathrm{car},q}=o\left(\frac{q^{5/4}}{\sqrt{\log q}}\right).
Then for every fixed α , τ ∈ ( 0 , 1 ) \alpha,\tau\in(0,1) α , τ ∈ ( 0 , 1 )
A q − ( C q , Ω ) → P 1 , p q , τ ⋄ ( C q ) → 1 , Π q , τ ( [ C q ] ) → ν = ( 1 , 0 , 0 ) . (100) A_q^-(C_q,\Omega)\xrightarrow{\mathrm{P}}1,\qquad
p^\diamond_{q,\tau}(C_q)\to1,\qquad
\Pi_{q,\tau}([C_q])\to\nu=(1,0,0). \tag*{(100)} A q − ( C q , Ω ) P 1 , p q , τ ⋄ ( C q ) → 1 , Π q , τ ([ C q ]) → ν = ( 1 , 0 , 0 ) . (100) Proof. Zero padding makes the carrier feasible in (4) on every mask, so J ∗ ≤ J c a r , q J_*\le J_{\mathrm{car},q} J ∗ ≤ J car , q F F F N N N F q ⋆ − F q F_q^\star-F_q F q ⋆ − F q Ω \Omega Ω D y − D a ≥ 0 D_y-D_a\ge0 D y − D a ≥ 0 y = C q ( x ) y=C_q(x) y = C q ( x ) a ≠ y a\ne y a = y F a ≥ F y F_a\ge F_y F a ≥ F y D a − D y ≥ 1 D_a-D_y\ge1 D a − D y ≥ 1
Balance the two representations by positive homogeneity so that ∥ A F ∥ F = ∥ Z F ∥ ∗ = J ∗ \lVert A_F\rVert_F=\lVert Z_F\rVert_*=\sqrt{J_*} ∥ A F ∥ F = ∥ Z F ∥ ∗ = J ∗ ∥ A c a r ∥ F = ∥ Z c a r ∥ ∗ = J c a r , q \lVert A_{\mathrm{car}}\rVert_F=\lVert Z_{\mathrm{car}}\rVert_*=\sqrt{J_{\mathrm{car},q}} ∥ A car ∥ F = ∥ Z car ∥ ∗ = J car , q
A ~ = [ Γ q A F − A c a r ] , Z ~ = [ Γ q Z F ; Z c a r ] (101) \widetilde A=\left[\sqrt{\Gamma_q}A_F-A_{\mathrm{car}}\right],\qquad
\widetilde Z=\left[\sqrt{\Gamma_q}Z_F;Z_{\mathrm{car}}\right] \tag*{(101)} A = [ Γ q A F − A car ] , Z = [ Γ q Z F ; Z car ] (101) represent D D D (14) gives
∥ A ~ ∥ F ∥ Z ~ ∥ ∗ ≤ 2 ( Γ q J ∗ + J c a r , q ) ≤ 2 ( Γ q + 1 ) J c a r , q = : B q . (102) \begin{aligned}
\lVert\widetilde{A}\rVert_F \lVert\widetilde{Z}\rVert_* \le\sqrt{2}\,(\Gamma_q J_*+J_{\mathrm{car},q}) \\
&\le\sqrt{2}\,(\Gamma_q+1)J_{\mathrm{car},q}=:B_q. \tag*{(102)}
\end{aligned} ∥ A ∥ F ∥ Z ∥ ∗ ≤ 2 ( Γ q J ∗ + J car , q ) ≤ 2 ( Γ q + 1 ) J car , q =: B q . (102) Since Γ q ≥ 1 \Gamma_q \ge1 Γ q ≥ 1 (99) is equivalent to B q 2 log q / q 5 / 2 → 0 B_q^2 \log q/q^{5/2}\to0 B q 2 log q / q 5/2 → 0 N N N N N N J ∗ J_* J ∗ Acc T < τ \operatorname{Acc}_T<\tau Acc T < τ ( 1 − τ ) ( 1 − α ) N (1-\tau)(1-\alpha)N ( 1 − τ ) ( 1 − α ) N β = 1 2 ( 1 − τ ) ( 1 − α ) \beta=\frac{1}{2}(1-\tau)(1-\alpha) β = 2 1 ( 1 − τ ) ( 1 − α ) (100) . □
The proposition is a sufficient condition. Its contrapositive constrains families that fail to be all-good; it does not say that a family without such a carrier fails to generalise. In particular, the observed optimum J ∗ J_* J ∗
Finite abelian group tables
Let G G G q q q [ q ] [q] [ q ] C G ( u , v ) = u + v C_G(u,v)=u+v C G ( u , v ) = u + v G ^ \widehat{G} G q q q χ ( t ) = c χ ( t ) + i s χ ( t ) \chi(t)=c_\chi(t)+\mathrm{i}s_\chi(t) χ ( t ) = c χ ( t ) + i s χ ( t ) c χ ( t ) 2 + s χ ( t ) 2 = 1 c_\chi(t)^2+s_\chi(t)^2=1 c χ ( t ) 2 + s χ ( t ) 2 = 1 [12 ] .
Lemma E.3 (Abelian carrier). There is an absolute constant C a b C_{\mathrm{ab}} C ab G G G q q q C G C_G C G O ( log q ) O(\log q) O ( log q ) [ 1 , 9 ] [1,9] [ 1 , 9 ] J c a r , q ≤ C a b q log q J_{\mathrm{car},q}\le C_{\mathrm{ab}}q\sqrt{\log q} J car , q ≤ C ab q log q
Proof. Keep h h h ϵ \epsilon ϵ ρ \rho ρ c c c L L L P P P § 9 .§ 3.1 . We give each change to that construction.
Character selection. For e ≠ 0 e\ne0 e = 0 ∑ χ ∈ G ^ χ ( e ) = 0 \sum_{\chi\in\widehat{G}}\chi(e)=0 ∑ χ ∈ G χ ( e ) = 0 ψ \psi ψ ψ ( e ) ≠ 1 \psi(e)\ne1 ψ ( e ) = 1 ψ ( e ) \psi(e) ψ ( e ) 1 1 1
E χ ∼ Unif ( G ^ ∖ { 1 } ) [ c χ ( e ) ] = − 1 q − 1 . (103) \mathbb{E}_{\chi\sim\operatorname{Unif}(\widehat{G}\setminus\{1\})}[c_\chi(e)]=-\frac{1}{q-1}. \tag*{(103)} E χ ∼ Unif ( G ∖ { 1 }) [ c χ ( e )] = − q − 1 1 . (103) The real parts lie in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] q − 1 q-1 q − 1 L = O ( log q ) L=O(\log q) L = O ( log q ) χ 1 , … , χ L \chi_1,\ldots,\chi_L χ 1 , … , χ L
1 L ∑ ℓ = 1 L c χ ℓ ( e ) ≤ ρ ( e ≠ 0 ) . (104) \frac{1}{L}\sum_{\ell=1}^{L}c_{\chi_\ell}(e)\le\rho\qquad(e\ne0). \tag*{(104)} L 1 ℓ = 1 ∑ L c χ ℓ ( e ) ≤ ρ ( e = 0 ) . (104) Sampling with replacement is allowed; no distinctness is needed.
Products, scores, and gaps. Multiplicativity gives the real and imaginary addition identities. Set
c ~ ℓ ( u , v ) = P ( c χ ℓ ( u ) , c χ ℓ ( v ) ) − P ( s χ ℓ ( u ) , s χ ℓ ( v ) ) , \widetilde{c}_\ell(u,v)=P(c_{\chi_\ell}(u),c_{\chi_\ell}(v))-P(s_{\chi_\ell}(u),s_{\chi_\ell}(v)), c ℓ ( u , v ) = P ( c χ ℓ ( u ) , c χ ℓ ( v )) − P ( s χ ℓ ( u ) , s χ ℓ ( v )) , s ~ ℓ ( u , v ) = P ( s χ ℓ ( u ) , c χ ℓ ( v ) ) + P ( c χ ℓ ( u ) , s χ ℓ ( v ) ) . (105) \widetilde{s}_\ell(u,v)=P(s_{\chi_\ell}(u),c_{\chi_\ell}(v))+P(c_{\chi_\ell}(u),s_{\chi_\ell}(v)). \tag*{(105)} s ℓ ( u , v ) = P ( s χ ℓ ( u ) , c χ ℓ ( v )) + P ( c χ ℓ ( u ) , s χ ℓ ( v )) . (105) By (43) , these approximate c χ ℓ ( u + v ) c_{\chi_\ell}(u+v) c χ ℓ ( u + v ) s χ ℓ ( u + v ) s_{\chi_\ell}(u+v) s χ ℓ ( u + v ) h 2 / 8 h^2/8 h 2 /8
F q , a ∗ ( u , v ) = c L ∑ ℓ = 1 L ( c χ ℓ ( a ) c ~ ℓ ( u , v ) + s χ ℓ ( a ) s ~ ℓ ( u , v ) ) . (106) F^*_{q,a}(u,v)=\frac{c}{L}\sum_{\ell=1}^{L}\left(c_{\chi_\ell}(a)\widetilde{c}_\ell(u,v)+s_{\chi_\ell}(a)\widetilde{s}_\ell(u,v)\right). \tag*{(106)} F q , a ∗ ( u , v ) = L c ℓ = 1 ∑ L ( c χ ℓ ( a ) c ℓ ( u , v ) + s χ ℓ ( a ) s ℓ ( u , v ) ) . (106) Its ideal version is c L ∑ ℓ Re χ ℓ ( u + v − a ) \frac{c}{L}\sum_\ell\operatorname{Re}\chi_\ell(u+v-a) L c ∑ ℓ Re χ ℓ ( u + v − a ) c c c c ρ c\rho c ρ ∣ c χ ( a ) ∣ + ∣ s χ ( a ) ∣ ≤ 2 |c_\chi(a)|+|s_\chi(a)|\le\sqrt{2} ∣ c χ ( a ) ∣ + ∣ s χ ( a ) ∣ ≤ 2 c 2 h 2 / 8 c\sqrt{2}h^2/8 c 2 h 2 /8 § 9 .§ 3.1 therefore gives exactly the same interval [ 1 , 9 ] [1,9] [ 1 , 9 ]
Architecture and cost. Expanding P P P (41) produces a constant number of hinges per character. Each hinge is ( r u + s v − t ) + (r_u+s_v-t)_+ ( r u + s v − t ) + t t t O ( q ) O(\sqrt{q}) O ( q ) O ( q / L ) O(\sqrt{q}/L) O ( q / L ) G G G
∥ A c a r ∥ F = O ( q / L ) , ∥ Z c a r ∥ ∗ ≤ O ( L ) ∥ Z c a r ∥ F = O ( L q ) , (107) \lVert A_{\mathrm{car}}\rVert_F=O(\sqrt{q}/L),\qquad\lVert Z_{\mathrm{car}}\rVert_* \le\sqrt{O(L)}\lVert Z_{\mathrm{car}}\rVert_F=O(L\sqrt{q}), \tag*{(107)} ∥ A car ∥ F = O ( q / L ) , ∥ Z car ∥ ∗ ≤ O ( L ) ∥ Z car ∥ F = O ( L q ) , (107) giving J c a r , q = O ( q log q ) J_{\mathrm{car},q}=O(q\sqrt{\log q}) J car , q = O ( q log q ) O ( log q ) ≤ N O(\log q)\le N O ( log q ) ≤ N
Proof of Corollary 4.4. Lemma E.3 gives Γ q J c a r , q = O ( q log q ) = o ( q 5 / 4 / log q ) \Gamma_qJ_{\mathrm{car},q}=O(q\sqrt{\log q})=o(q^{5/4}/\sqrt{\log q}) Γ q J car , q = O ( q log q ) = o ( q 5/4 / log q )
Thus the all-good pole contains every abelian group family, beyond the cyclic case of Theorem 4.1 (i). Non-isomorphic abelian groups give distinct colouring orbits: an isotopy between two such group tables can be written h ( u + v ) = f ( u ) + g ( v ) h(u+v)=f(u)+g(v) h ( u + v ) = f ( u ) + g ( v ) u ↦ h ( u ) − h ( 0 ) u\mapsto h(u)-h(0) u ↦ h ( u ) − h ( 0 ) q = 2 m q=2^m q = 2 m m m m m = 6 m=6 m = 6 v \mathbf{v} v
What the finite-order experiments can suggest
The abelian rows C 2 6 C_2^6 C 2 6 C 64 C_{64} C 64 C 8 × C 8 C_8\times C_8 C 8 × C 8 Table 1 are finite members of families covered by Corollary 4.4. The corollary concerns the whole minimum-norm endpoint set under ν q \nu_q ν q q → ∞ q\to\infty q → ∞ q = 64 q=64 q = 64
There is nevertheless a concrete simplification for elementary abelian 2-groups. Every character is real with values in { ± 1 } \{\pm1\} { ± 1 } s χ = 0 s_\chi=0 s χ = 0 (105) reduces to one product P ( c χ ( u ) , c χ ( v ) ) P(c_\chi(u),c_\chi(v)) P ( c χ ( u ) , c χ ( v )) { − 2 , 0 , 2 } \{-2,0,2\} { − 2 , 0 , 2 } Q h Q_h Q h P ( x , y ) = x y P(x,y)=xy P ( x , y ) = x y C 2 6 C_2^6 C 2 6
Non-abelian tables and the missing cost estimate
The transitions for Dih 64 \operatorname{Dih}_{64} Dih 64 (104) at a non-identity commutator. For the order-64 dihedral group, the abelianisation has only four elements.
Write G ^ \widehat{G} G π ∈ G ^ \pi\in\widehat{G} π ∈ G d π d_\pi d π χ π = tr π \chi_\pi=\operatorname{tr}\pi χ π = tr π
∑ π ∈ G ^ d π 2 q χ π ( g ) d π = 1 { g = e } . (108) \sum_{\pi\in\widehat{G}}\frac{d_\pi^2}{q}\frac{\chi_\pi(g)}{d_\pi}=\mathbf{1}\{g=e\}. \tag*{(108)} π ∈ G ∑ q d π 2 d π χ π ( g ) = 1 { g = e } . (108) The real part of the normalised character lies in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] d π 2 / q d_\pi^2/q d π 2 / q a a a Re χ π ( u v u − 1 ) / d π \operatorname{Re}\chi_\pi(uvu^{-1})/d_\pi Re χ π ( uv u − 1 ) / d π χ π ( u v ) \chi_\pi(uv) χ π ( uv )
χ π ( u v u − 1 ) d π = 1 d π ∑ i , j , k = 1 d π π ( u ) i k π ( v ) k j π ( a ) i j ‾ . (109) \frac{\chi_\pi(uvu^{-1})}{d_\pi}=\frac{1}{d_\pi}\sum_{i,j,k=1}^{d_\pi}\pi(u)_{ik}\pi(v)_{kj}\overline{\pi(a)_{ij}}. \tag*{(109)} d π χ π ( uv u − 1 ) = d π 1 i , j , k = 1 ∑ d π π ( u ) ik π ( v ) k j π ( a ) ij . (109) Each complex product of a row quantity and a column quantity can again be expanded into real products and approximated using P ^ \widehat{P} P d π 3 d_\pi^3 d π 3 d π 2 d_\pi^2 d π 2 tr ( π ( u ) π ( v ‾ ) ) \operatorname{tr}(\pi(u)\pi(\overline{v})) tr ( π ( u ) π ( v ))
Rarity, and what a necessary carrier would mean
Every colouring has a full-grid carrier of finite, indeed polynomial, cost: the cell-indicator construction in Appendix C.1 uses N N N
The uniform obstruction does give a precise rarity statement for cheap carriers. For a deterministic b q = o ( q 5 / 4 / log q ) b_q = o(q^{5/4}/\sqrt{\log q}) b q = o ( q 5/4 / log q ) K q ( b q ) ⊆ L q K_q(b_q) \subseteq\mathcal{L}_q K q ( b q ) ⊆ L q N N N [ 1 , Γ ] [1,\Gamma] [ 1 , Γ ] Γ J c a r ≤ b q \Gamma J_{\mathrm{car}} \leq b_q Γ J car ≤ b q Γ ≥ 1 \Gamma\geq1 Γ ≥ 1 B q = 2 2 b q B_q = 2\sqrt{2}b_q B q = 2 2 b q p q , τ ν ( C ) ≥ 1 − o ( 1 ) p_{q,\tau}^{\nu}(C) \geq1-o(1) p q , τ ν ( C ) ≥ 1 − o ( 1 )
∣ K q ( b q ) ∣ ∣ L q ∣ ( 1 − o ( 1 ) ) ≤ P q , τ ν ( M u n i f ) ⟶ 0. (110) \frac{\lvert K_q(b_q)\rvert}{\lvert\mathcal{L}_q\rvert}(1-o(1)) \leq P_{q,\tau}^{\nu}(\mathcal{M}_{\mathrm{unif}}) \longrightarrow0. \tag*{(110)} ∣ L q ∣ ∣ K q ( b q )∣ ( 1 − o ( 1 )) ≤ P q , τ ν ( M unif ) ⟶ 0. (110) This rules out this cheap-carrier regime for almost all Latin colourings; it rules out neither arbitrary carriers nor the existence of a good endpoint in a mixed instance.
The sufficient budget in (99) is not necessary. The accompanying Carrier necessity counterexample note constructs a deterministic Latin family along even orders for which A q − ⟶ P 1 A_q^{-} \mathop{\longrightarrow}^{\mathrm{P}} 1 A q − ⟶ P 1 Γ J c a r \Gamma J_{\mathrm{car}} Γ J car N N N [ 1 , Γ ] [1,\Gamma] [ 1 , Γ ] ( 1 + o ( 1 ) ) q 13 / 10 (1+o(1))q^{13/10} ( 1 + o ( 1 )) q 13/10 q 5 / 4 / log q q^{5/4}/\sqrt{\log q} q 5/4 / log q Γ J \Gamma J Γ J Γ \Gamma Γ
A mask-independent robust certificate. For a colouring C C C 0 ≤ ε < 1 0 \leq\varepsilon< 1 0 ≤ ε < 1
R q ( C , ε ) = inf { ∥ A ∥ F ∥ Z ∥ ∗ : w ≤ N , E ⊆ X q , ∣ E ∣ ≤ ε N , F C ( x ) ( x ) − F a ( x ) ≥ 1 ( x ∉ E , a ≠ C ( x ) ) } , F = A ReLU ( Z ξ ) . (111) R_q(C,\varepsilon)=\inf\left\{\lVert A\rVert_F\lVert Z\rVert_* :
\begin{array}{c}
w \leq N,\quad E \subseteq X_q,\quad\lvert E\rvert\leq\varepsilon N,\\
F_{C(x)}(x)-F_a(x)\geq1\quad(x\notin E,\ a\neq C(x))
\end{array}
\right\},
\qquad F=A\operatorname{ReLU}(Z\xi). \tag*{(111)} R q ( C , ε ) = inf { ∥ A ∥ F ∥ Z ∥ ∗ : w ≤ N , E ⊆ X q , ∣ E ∣ ≤ εN , F C ( x ) ( x ) − F a ( x ) ≥ 1 ( x ∈ / E , a = C ( x )) } , F = A ReLU ( Z ξ ) . (111) where F = A ReLU ( Z ξ ) F=A\operatorname{ReLU}(Z\xi) F = A ReLU ( Z ξ ) E E E
In this notation, Conjecture 5.1 asserts that if a deterministic Latin sequence satisfies A q − ( C q , Ω ) ⟶ P 1 A_q^{-}(C_q,\Omega)\mathop{\longrightarrow}^{\mathrm{P}}1 A q − ( C q , Ω ) ⟶ P 1 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ε q → 0 \varepsilon_q\to0 ε q → 0
R q ( C q , ε q ) = o ( q 3 / 2 ) . (112) R_q(C_q,\varepsilon_q)=o(q^{3/2}). \tag*{(112)} R q ( C q , ε q ) = o ( q 3/2 ) . (112) The premise includes every fixed accuracy threshold τ < 1 \tau<1 τ < 1 α \alpha α
The upper-gap factor Γ \Gamma Γ Γ F ′ − F q ∗ \Gamma F'-F_q^* Γ F ′ − F q ∗ F F F o ( N ) o(N) o ( N ) 5 / 4 5/4 5/4 3 / 2 3/2 3/2
The accompanying multiscale exploration gives a sufficient condition using a full-grid unit-margin carrier of cost o ( q 3 / 2 / log q ) o(q^{3/2}/\log q) o ( q 3/2 / log q ) J ∗ J_* J ∗
Conversely, a robust carrier need not satisfy the constraints at observed exceptional cells, so it does not by itself give J ∗ ≤ R q ( C q , ε q ) J_* \le R_q(C_q,\varepsilon_q) J ∗ ≤ R q ( C q , ε q ) o ( N ) o(N) o ( N ) 3 / 2 3/2 3/2
