claimroutineinferred_dep

Alphabet-independent gap fixes repetition exponent

A 1/100 gap becomes ≥ 1/800 after subdivision, fixing repetition number tt
chooses tt before the alphabet, breaking circularity
Claim·§7.2 The final reduction·inside thmThe Unique Games Theorem

Statement (paper)

Let ε0≤ε\eps_0\le\eps and δ0≤δ\delta_0\le\delta be positive rationals and let τ≤1/200\tau\le 1/200. For every matrix game HH with val⁡(H)≤99/100\val(H)\le 99/100, the game BB obtained by rounding and subdivision satisfies val⁡(B)≤1−1/100−τ4≤1−1800\val(B)\le 1-\frac{1/100-\tau}{4}\le 1-\frac1{800}, independently of the alphabet. Hence any integer t≥1t\ge1 with (1−110240000)t≤δ0\left(1-\frac1{10240000}\right)^t\le\delta_0 (for instance t≥⌈10240000log⁡(1/δ0)⌉t\ge\lceil 10240000\log(1/\delta_0)\rceil) can be chosen before the alphabet is fixed, and by Theorem  the tt-fold repetition reduces every projection game of value at most 1−1/8001-1/800 to value at most δ0\delta_0.

In plain English

For any matrix game HH with val⁡(H)≤99/100\val(H)\le 99/100, the rounded and subdivided game BB has val⁡(B)≤1−1/100−τ4≤1−1800\val(B)\le 1-\frac{1/100-\tau}{4}\le 1-\frac1{800} (for τ≤1/200\tau\le 1/200), regardless of the alphabet. So a repetition number tt with (1−1/10240000)t≤δ0(1-1/10240000)^t\le\delta_0 can be chosen before the alphabet is fixed, and tt-fold repetition brings BB to value at most δ0\delta_0.

Why it's here

The subdivision lemma shrinks the unsatisfied fraction by a factor of 4 up to τ/4\tau/4 error, so a 1/1001/100 gap in HH becomes a gap of at least 1/8001/800 in BB. Plugging g=1/800g=1/800 into the parallel repetition theorem gives the rate 1−g2/16=1−1/102400001-g^2/16=1-1/10240000, which depends on no alphabet size. This breaks the circularity between the alphabet and tt in the final reduction.
Classified routine:
A parameter-bookkeeping consequence of the subdivision lemma (gap shrinks by a factor of 4 up to \tau/4) combined with the alphabet-independent parallel repetition bound for projection games (Rao-style, rate 1-g^2/16), used to choose t before the alphabet is fixed.

Uses

thmParallel repetition for projection gameslemSubdivision yields unweighted simple game

Used by

claimYES and NO values of the final game

Sources

PaperOpen
Section
§7.2 The final reduction
Page
—
Label
—
Line
sections/06-finish.tex:93
Leannot aligned

Phase 2 aligns this node to a Lean declaration.

Friction

  • info
    inferred_dep
    outline: "Alphabet-independent gap fixes repetition exponent" rests on lem:unweighted-subdivision