lemmanovelinferred_dep

Latent alphabet gadget with detecting noise

Builds a noisy KK-equivariant coloring whose noise is detected by high-rank tests
supplies latent alphabet and threshold r∗r_* to the game
Lemma·lem:latent·§3 A latent alphabet gadget

Statement (paper)

For every p∗>0p_*>0 there is an integer r∗r_* such that, for every sufficiently large integer ℓ\ell, the following objects exist: a finite-dimensional binary space V\mathcal V containing an identified subspace K=F2ℓK=\F_2^\ell, a map C:V→KC:\mathcal V\to K, and a rational probability distribution μ\mu on V\mathcal V. They satisfy C(x+k)=C(x)+k(x∈V, k∈K), C(x+k)=C(x)+k \qquad(x\in\mathcal V,\ k\in K), and, for independent uniform x∈Vx\in\mathcal V and a∼μa\sim\mu, Pr⁡[C(x+a)≠C(x)]≤p∗. \Pr[C(x+a)\ne C(x)]\le p_*. Moreover, every linear subspace G≤V∗G\le\mathcal V^* with dim⁡(G∣K)≥r∗\dim(G|_K)\ge r_* satisfies Pr⁡a∼μ[there exists g∈G with g(a)≠0]≥18. \Pr_{a\sim\mu}[\text{there exists }g\in G\text{ with }g(a)\ne0] \ge\frac18. In particular, r∗r_* is fixed before ℓ\ell is chosen. For rational p∗p_*, the threshold and all the finite data can be found by a terminating deterministic algorithm.

In plain English

For every p∗>0p_*>0 there is a threshold r∗r_* such that for all large ℓ\ell there are a binary space V⊇K=F2ℓ\mathcal V\supseteq K=\F_2^\ell, a KK-equivariant map C:V→KC:\mathcal V\to K with C(x+k)=C(x)+kC(x+k)=C(x)+k, and a rational noise distribution μ\mu on V\mathcal V under which CC changes with probability at most p∗p_*. Any subspace G≤V∗G\le\mathcal V^* with dim⁡(G∣K)≥r∗\dim(G|_K)\ge r_* is detected by the noise, meaning some g∈Gg\in G has g(a)≠0g(a)\ne0, with probability at least 1/81/8; r∗r_* does not depend on ℓ\ell and everything is computable for rational p∗p_*.

Why it's here

This is the main gadget of the section. It gives a large alphabet KK that can be recovered robustly from a noisy encoding, while any low-complexity family of linear tests that sees a high-rank part of KK must notice the noise. It combines a small base gadget, with small change probability and detection from the generic-subspace and noise lemmas and the full-lift detection proposition, with a symmetrization over all injections B→KB\to K, so the threshold r∗=b+2r_*=b+2 is independent of ℓ\ell.
Classified novel:
This is the section's main new gadget. It gives a large alphabet K that is recoverable under noise, with K-equivariance and a detection threshold r_* independent of ℓ. It is built from the paper's own generic-subspace, noise and full-lift lemmas plus symmetrization over all injections B→K, and no prior known gadget provides this combination.

Uses

lemRandom binary subspaces are genericlemLatent coloring change probability formulapropFull lifts detect the leaf symbol

Used by

thmThe Unique Games TheoremlemMatrix test implies surrogate acceptance boundclaimEffective choice of latent and shortcode parameters

Inside the proof

claimBase gadget change probability at most p_*claimEnlargement by injections gives equivariant mapclaimEnlarged noise preserves small change probabilityclaimHigh-rank families detect with probability 3/16claimConstruction is effective for rational p_*

Figures

A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least $\gamma>0$ (Proposition 5.3), while a NO parity instance gives agreement at most $\exp(-ck^{1/3})$ for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large $k$: $\exp(-ck^{1/3})<\gamma$.
Figure 1diagramp. 6
The solid arrows describe the reduction; the dashed arrows describe its soundness argument. The decoding lower bound follows from high test acceptance, while the clean-coordinate upper bound follows from the NO parity gap and applies to every advice strategy. The constants c,γ>0c,\gamma>0 are fixed before the tuple length kk grows.
What it shows
A two-column flow diagram. The left column, "The reduction", has three boxes linked by solid arrows: 3SAT to a weighted parity gap instance, then the latent matrix test (stable nonlinear map, Lemma 3.1), then via "Rounding and subdivision; parallel repetition" to unweighted simple bipartite Unique Games (Theorem 1.1). The right column, "Soundness on a NO input", has two branches with dashed arrows: assuming test acceptance at least 0.99 gives decoded advice strategies with agreement at least γ>0\gamma>0 (Proposition 5.3), while a NO parity instance gives agreement at most exp⁡(−ck1/3)\exp(-ck^{1/3}) for every pair of strategies (Lemma 6.2). Both branches point to a bottom box stating a contradiction for sufficiently large kk: exp⁡(−ck1/3)<γ\exp(-ck^{1/3})<\gamma.
Read from the image by claude-opus-5.5 · confidence 88%
SupportsthmThe Unique Games TheoremlemLatent alphabet gadget with detecting noisepropMatrix test passing yields decoding strategieslemAdvice agreement decays with clean coordinatesthmGap hardness for weighted parity equationsthmParallel repetition for projection gameslemSubdivision yields unweighted simple gamepropMatrix game completeness and soundness gap
A flow diagram of one level of the latent recursion. Three boxes sit in a top row, separated by ellipses: a left child box ($u_{AJ}\in P_{t-1}$ mapped to $JC_{t-1}(u_{AJ})$), a red-highlighted selected child box ($u_{A_*J_*}+\xi_{t-1}$ mapped to $J_*C_{t-1}(u_{A_*J_*}+\xi_{t-1})$) and a right box of other child inputs. Arrows from all three, the middle one red, point to a summation box reading "Sum over every child $(A,J)\in\mathcal I$" with noisy aggregate $(x',y')=(x,y)+J_*\Delta$. That box points down to a final box, "Noisy parent output $y'+Q(x')\in B$". The figure shows how noise in only one uniformly chosen child propagates through the embedding, summation and quadratic map to the parent output.
Figure 2diagramp. 13
One level of the latent recursion, shown under its additive noise. The input space is a product over all child indices (A,J)(A,J); only one uniformly chosen child is perturbed. Each child output is embedded in UA≤X⊕BU_A\le X\oplus B, all embedded outputs are added, and the quadratic map is applied once at the parent. Here (x,y)(x,y) is the initial aggregate, and Δ\Delta is the selected child's output difference, so the noisy aggregate is (x′,y′)=(x,y)+J∗Δ(x',y')=(x,y)+J_*\Delta. The omitted children obey the same rule. The highlighted perturbation may disappear at the parent.
What it shows
A flow diagram of one level of the latent recursion. Three boxes sit in a top row, separated by ellipses: a left child box (uAJ∈Pt−1u_{AJ}\in P_{t-1} mapped to JCt−1(uAJ)JC_{t-1}(u_{AJ})), a red-highlighted selected child box (uA∗J∗+ξt−1u_{A_*J_*}+\xi_{t-1} mapped to J∗Ct−1(uA∗J∗+ξt−1)J_*C_{t-1}(u_{A_*J_*}+\xi_{t-1})) and a right box of other child inputs. Arrows from all three, the middle one red, point to a summation box reading "Sum over every child (A,J)∈I(A,J)\in\mathcal I" with noisy aggregate (x′,y′)=(x,y)+J∗Δ(x',y')=(x,y)+J_*\Delta. That box points down to a final box, "Noisy parent output y′+Q(x′)∈By'+Q(x')\in B". The figure shows how noise in only one uniformly chosen child propagates through the embedding, summation and quadratic map to the parent output.
Read from the image by claude-opus-5.5 · confidence 80%
SupportslemLatent coloring change probability formulalemLatent alphabet gadget with detecting noiselemBlock coloring changes with probability 1−θ

Sources

PaperOpen
Section
§3 A latent alphabet gadget
Page
—
Label
lem:latent
Line
sections/02-latent.tex:8
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    critique: The proof of Lemma 3.1 uses Eq. (latent-base-detection) at sections/02-latent.tex:739-740. That equation is derived in running text from "Proposition  gives the bound" (line 653). The lemma node has no edge to the proposition.