claimroutine

Parameters fixed before invoking UG theorem

Fixes degree hh and error constants from ζ,ν,d,H\zeta,\nu,d,H before invoking UG
sets non-circular constants for the proof
Claim·§A.1 A simple strong-left form of Unique Games·inside lemUnique Games with constant left degree and strong satisfaction

Statement (paper)

There exist a multiple hh of dd with h≥max⁡{H,2}h\ge\max\{H,2\} and 1/h<ν/41/h<\nu/4, an integer T≥hT\ge h with pgraph=(T)h/Th>3/4p_{\mathrm{graph}}=(T)_h/T^h>3/4, positive rationals β,γ,u\beta,\gamma,u, a positive integer L2L_2, and positive rationals γ0,ζ0<1/2\gamma_0,\zeta_0<1/2 such that β<ν/4\beta<\nu/4, h2γ<ν/4h^2\gamma<\nu/4, (h+1)u<ζ/2(h+1)u<\zeta/2, 1/L2<min⁡{βγ/2,ζ/(2h)}1/L_2<\min\{\beta\gamma/2,\zeta/(2h)\}, 2γ0<βγ/22\gamma_0<\beta\gamma/2, and 2ζ0<u\sqrt{2\zeta_0}<u. All these quantities are chosen from ζ,ν,d,H\zeta,\nu,d,H alone, before Theorem  is invoked with completeness error ζ0\zeta_0 and soundness error γ0\gamma_0.

In plain English

One can choose, using only ζ,ν,d,H\zeta,\nu,d,H, a degree hh (a multiple of dd, with h≥max⁡{H,2}h\ge\max\{H,2\} and 1/h<ν/41/h<\nu/4), an integer T≥hT\ge h with (T)h/Th>3/4(T)_h/T^h>3/4, and positive rationals β,γ,u,γ0,ζ0\beta,\gamma,u,\gamma_0,\zeta_0 and an integer L2L_2. They satisfy a list of smallness inequalities, such as β<ν/4\beta<\nu/4, h2γ<ν/4h^2\gamma<\nu/4, (h+1)u<ζ/2(h+1)u<\zeta/2, 2γ0<βγ/22\gamma_0<\beta\gamma/2 and 2ζ0<u\sqrt{2\zeta_0}<u.

Why it's here

This claim sets every constant in the proof of the lemma in a non-circular order, so that only the alphabet size RR comes from the Unique Games Theorem. The completeness error ζ0\zeta_0 and soundness error γ0\gamma_0 are fixed first, and the theorem is then invoked with them. The later steps (copy normalization, graph construction and the error analysis) can then use the inequalities freely, and the final degree hh and the two errors depend only on ζ,ν,d,H\zeta,\nu,d,H and not on RR.
Classified routine:
Straightforward choice of constants in a fixed order (pick h, then T large so that (T)_h/T^h>3/4, then small rationals). It is ordinary parameter bookkeeping made before invoking the Unique Games Theorem, with no new idea.

Uses

thmThe Unique Games Theorem

Used by

claimCopy normalization to unit incident weight

Sources

PaperOpen
Section
§A.1 A simple strong-left form of Unique Games
Page
—
Label
—
Line
appendices/finite-consequences.tex:41
Leannot aligned

Phase 2 aligns this node to a Lean declaration.