lemmaroutine

Good row advice is common and gives short answer sets

Good row advice has probability ≥

g_0

and answer sets of size ≤

2^{r_{\rm s}}

turns shortcode decoding into short candidate lists

Lemma·lem:good-row-advice·§5.4 Obtaining many useful row fibers

Statement (paper)

For all sufficiently large

k

, a table family with matrix-test acceptance at least

0.99

satisfies

\Pr_{U,T,A,M}[(U,T,A,AM)\text{ is good}] \ge g_0, \qquad g_0=10\eta^2\,2^{-\ell r_{\rm s}}>0.

The lower bound and the required largeness of

k

are independent of the parity instance and the family. For every positive integer

k

and every family satisfying Equation , one can select deterministically for each good row advice at most

r_{\rm s}

column specifications

Mq_j=t_j

, with

q_j\in L_U

and

t_j\in K

, and a target

Mz+u

, with

z\in L_U

u\in K

, and

e_0^\top z=1

, satisfying the definition of goodness. Writing

Z=\Span\{q_j\}

, the chosen witness determines the answer set

\mathcal A=(z+Z)\cap\{v\in L_U:e_0^\top v=1\}, \qquad 1\le |\mathcal A|\le 2^{r_{\rm s}}.

The witness and

\mathcal A

depend only on

(U,T,A,S_0)

and the fixed table family. The slice and its target retain the agreement guarantee in the definition of goodness.

In plain English

If the table family passes the matrix test with probability at least

0.99

and

k

is large, then

(U,T,A,AM)

is good with probability at least

g_0=10\eta^2 2^{-\ell r_{\rm s}}

, independent of the parity instance and family. Each good row advice also yields a deterministic witness of at most

r_{\rm s}

column specifications and a target

Mz+u

with

e_0^\top z=1

, giving an answer set

\mathcal A

with

1\le|\mathcal A|\le 2^{r_{\rm s}}

Why it's here

The probability bound comes from a contradiction argument: if good row fibers were rare, randomizing them would leave the function with acceptance at least

2\eta

but agreement below

3\alpha/4

on every allowed slice, contradicting the shortcode theorem. Combined with the spectral lemma's

10\eta

fraction of pairs and the

2^{-\ell r_{\rm s}}

cost of choosing

A

, this gives

g_0

. The deterministic witness and short answer set turn goodness into explicit, bounded candidate lists that later decoding and witness-transfer steps use.

Classified routine:

A counting and contradiction argument that combines the inverse shortcode theorem with the matrix-test spectral lemma, plus a deterministic choice of witness. This is standard bookkeeping in the style of the Khot–Minzer–Safra 2-to-2 games soundness analysis.

Uses

thmInverse shortcode theoremlemMatrix test implies surrogate acceptance bound

Used by

thmThe Unique Games TheorempropMatrix test passing yields decoding strategieslemGood advice transfers to projected sliceclaimChoosing the cube k and parity errorclaimDecoded vector lands in projected answer set

Inside the proof

claimRandomizing good fibers keeps acceptance 2etaclaimRandom replacements match few on slicesclaimShortcode contradiction forces large good setclaimGood advice mass lower boundclaimGood advice yields short nonempty answer set

Figures

A flow diagram with a Referee box at top that samples $U,O,\bar\pi,A,T_O,M_O$, sets $S_O=AM_O$, and sends inputs down two parallel columns. The left column is the Equation decoder receiving $(U,A,T_U,S_U)$ with $T_U=T_O\bar\pi$, $S_U=S_O\bar\pi$; it picks a slice witness and answer set $\mathcal A=(z+Z)\cap\{v:e_0^\top v=1\}$ and samples $a_U$ uniformly from it. The right column is the Projected decoder receiving $(O,A,T_O,S_O)$; it sets $H=\ker A$, chooses $M_0$ with $AM_0=S_O$, samples $\sigma\in K^*$ and $\Phi$ with probability $|\widehat f_\sigma(\Phi)|^2$, and outputs $a_O=\Phi(h)$ for a fixed $h\in H$ with $\sigma(h)=1$. Both outputs satisfy $e_0^\top a=1$ and feed into a bottom box where the referee checks $\bar\pi a_U=a_O$. — Figure 3diagramp. 31
The two decoders use independent random tapes. Neither receives the sampled $M_O$ or the projection $\bar\pi$ ; the right decoder chooses its own representative $M_0$ from the visible advice. Every displayed advice map includes its affine intercept, through the homogeneous coordinate. The transferred slice is used only to analyze these private rules: the right decoder does not use the left witness or answer set. If the left advice is not good, or if $\sigma|_H=0$ on the right, that decoder returns an arbitrary valid answer.
What it shows
A flow diagram with a Referee box at top that samples $U,O,\bar\pi,A,T_O,M_O$ , sets $S_O=AM_O$ , and sends inputs down two parallel columns. The left column is the Equation decoder receiving $(U,A,T_U,S_U)$ with $T_U=T_O\bar\pi$ , $S_U=S_O\bar\pi$ ; it picks a slice witness and answer set $\mathcal A=(z+Z)\cap\{v:e_0^\top v=1\}$ and samples $a_U$ uniformly from it. The right column is the Projected decoder receiving $(O,A,T_O,S_O)$ ; it sets $H=\ker A$ , chooses $M_0$ with $AM_0=S_O$ , samples $\sigma\in K^*$ and $\Phi$ with probability $|\widehat f_\sigma(\Phi)|^2$ , and outputs $a_O=\Phi(h)$ for a fixed $h\in H$ with $\sigma(h)=1$ . Both outputs satisfy $e_0^\top a=1$ and feed into a bottom box where the referee checks $\bar\pi a_U=a_O$ .
Read from the image by claude-opus-5.5 · confidence 80%
SupportsdefProjected advice experimentlemFourier decoding agrees with positive probabilitypropMatrix test passing yields decoding strategieslemGood row advice is common and gives short answer setslemGood advice transfers to projected slice

Sources

PaperOpen

Section: §5.4 Obtaining many useful row fibers
Page: —
Label: lem:good-row-advice
Line: sections/04-matrix.tex:325

Leannot aligned

Phase 2 aligns this node to a Lean declaration.