LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-09-30

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

One fixed-alphabet transformation doubles small gaps

Statement

Let $Σ_{⋆}$ be the fixed $66$ -symbol alphabet of Fixed-alphabet reduction with constant gap retention, let $β > 0$ , $c : = D K = 7740 / 7$ and $t_{0}$ be the constants that A complete uniform graph gap-amplification step attaches to the finite alphabet $Σ_{⋆}$ , and let $κ = 1 / 48000$ be the absolute constant of Fixed-alphabet reduction with constant gap retention. Put $t : = \max (t_{0}, ⌈ 4 (κ β)^{- 2} ⌉), α : = \min (1 / 2, κ β c / \sqrt{t}),$ and let $T : = T_{t}$ be the transformation of One fixed-alphabet Dinur transformation at this fixed $t$ . Then $t \geq t_{0}$ is an integer in the transformation domain, $α > 0$ , and both depend only on the absolute constants $κ, β, c$ and $t_{0}$ , never on an input graph. For every finite binary constraint graph $G$ over $Σ_{⋆}$ , $UNSAT (T (G)) \geq \min (2 UNSAT (G), α) .$ Moreover $T$ is a deterministic map from finite $Σ_{⋆}$ -graphs to finite $Σ_{⋆}$ -graphs, so the same transformation and the same $t$ can be used in every round of an iteration.

Facts & Assumptions

Given: Fix the alphabet $Σ_{⋆}$ and the constants $β, c, t_{0}$ of A complete uniform graph gap-amplification step and $κ$ of Fixed-alphabet reduction with constant gap retention attached to it.

[F1]

$T_{t} (G) = A_{Σ_{t}} (R_{t} (G))$ for every finite $Σ_{⋆}$ -graph $G$ and every integer $t \geq t_{0}$ , and $T_{t}$ is a deterministic map from finite $Σ_{⋆}$ -graphs to finite $Σ_{⋆}$ -graphs, defined exactly for integers $t \geq t_{0}$ . (One fixed-alphabet Dinur transformation)

[F2]

$Σ_{t}$ has $∣ Σ_{t} ∣ = ∣ Σ_{⋆} ∣^{(2 D)^{R}}$ symbols for the absolute constant $D = 387$ and the view radius $R = t + ⌈ \sqrt{t} ⌉$ , so $∣ Σ_{t} ∣ \geq 2$ for every $t$ in the domain and the alphabet reduction $A_{Σ_{t}}$ of [F4] can be instantiated at this input alphabet. (One fixed-alphabet Dinur transformation)

[F3]

The gap-amplification step at the alphabet $Σ_{⋆}$ has a gap map $g_{t} (ε) = β \sqrt{t} \min (ε, c / t)$ with $c = D K = 7740 / 7$ and $β > 0$ depending only on $∣ Σ_{⋆} ∣ = 66$ and the absolute constants of that theorem, and $UNSAT (R_{t} (G)) \geq β \sqrt{t} \min (UNSAT (G), c / t)$ for every $t \geq t_{0}$ and every finite $Σ_{⋆}$ -graph $G$ . (A complete uniform graph gap-amplification step)

[F4]

For every finite alphabet $Σ$ with $∣ Σ ∣ \geq 2$ and every finite $Σ$ -graph $H$ , $UNSAT (A_{Σ} (H)) \geq κ UNSAT (H), κ = \frac{ρ_{0} δ}{4 \cdot 6} = \frac{1}{48000},$ so the retention factor is the absolute constant $κ$ . (Fixed-alphabet reduction with constant gap retention)

[F5]

For a labeling $σ$ the number ${val}_{σ} (G)$ is the fraction of ordinary edges satisfied, or $1$ when $E (G) = \emptyset$ ; hence $0 \leq {val}_{σ} (G) \leq 1$ and $0 \leq UNSAT (G) \leq 1$ for every finite graph $G$ . (Constraint graph and labeling value)

Proof

Given: Use the fixed alphabet $Σ_{⋆}$ and the constants $β, c, t_{0}, κ$ of [F3] and [F4].

1.1F1F3F4algebra

The numbers $κ = 1 / 48000 > 0$ and $β > 0$ are fixed constants, so $t : = \max (t_{0}, ⌈ 4 (κ β)^{- 2} ⌉)$ is a well-defined integer with $t \geq t_{0}$ ; it therefore lies in the transformation domain of [F1], and $t \geq 4 (κ β)^{- 2}$ gives $\sqrt{t} \geq 2 / (κ β)$ , that is, $κ β \sqrt{t} \geq 2$ .

1.2F3F5given

Let $G$ be an arbitrary finite $Σ_{⋆}$ -graph and put $ε : = UNSAT (G)$ ; by [F5], $ε \geq 0$ . The gap-amplification step [F3] gives $UNSAT (R_{t} (G)) \geq β \sqrt{t} \min (ε, c / t)$ .

2.1F3step 1.1algebra

With $c = 7740 / 7 > 0$ from [F3], set $α : = \min (1 / 2, κ β c / \sqrt{t})$ . Then $α > 0$ and $α \leq κ β c / \sqrt{t}$ , and both $t$ and $α$ depend only on $κ, β, c, t_{0}$ .

2.2F1F2F4step 1.1

Put $T : = T_{t}$ . By [F1], $T$ is a deterministic map from finite $Σ_{⋆}$ -graphs to finite $Σ_{⋆}$ -graphs with $T (G) = A_{Σ_{t}} (R_{t} (G))$ for every finite $Σ_{⋆}$ -graph $G$ ; by [F2] the alphabet $Σ_{t}$ is finite of size at least two, so the reduction $A_{Σ_{t}}$ of [F4] applies to $Σ_{t}$ -graphs.

2.3F1F2F3F4step 1.2algebra

The graph $R_{t} (G)$ is a finite graph over the alphabet $Σ_{t}$ , which has at least two symbols by [F2]. Applying [F4] with $Σ : = Σ_{t}$ and $H : = R_{t} (G)$ gives $UNSAT (A_{Σ_{t}} (R_{t} (G))) \geq κ UNSAT (R_{t} (G))$ , and multiplying the inequality of step 1.2 by $κ > 0$ yields $UNSAT (A_{Σ_{t}} (R_{t} (G))) \geq κ β \sqrt{t} \min (ε, c / t)$ .

3.1F1step 1.1step 1.2step 2.1step 2.3algebra

Since $κ β \sqrt{t} \geq 2$ (step 1.1) and $ε \geq 0$ (step 1.2), $κ β \sqrt{t} \min (ε, c / t) = \min (κ β \sqrt{t} ε, κ β c / \sqrt{t}) \geq \min (2 ε, α)$ , because $κ β \sqrt{t} ε \geq 2 ε$ while $κ β c / \sqrt{t} \geq α$ by step 2.1. Hence $UNSAT (T (G)) = UNSAT (A_{Σ_{t}} (R_{t} (G))) \geq \min (2 ε, α) = \min (2 UNSAT (G), α)$ .

4.1step 1.1step 2.1step 2.2step 3.1∎

The graph $G$ was arbitrary and the numbers $t, α$ and the map $T$ were fixed in steps 1.1–2.2 without reference to $G$ ; hence there are a fixed integer $t \geq t_{0}$ , a fixed $α > 0$ and the fixed map $T = T_{t}$ with $UNSAT (T (G)) \geq \min (2 UNSAT (G), α)$ for every finite $Σ_{⋆}$ -graph $G$ , and $T$ is again a finite $Σ_{⋆}$ -graph transformation, so the same $t$ serves in every round.

Remarks

This is the soundness clause of Dinur's gap-amplification step in the fixed-alphabet form: the powering alone multiplies small unsatisfaction values by $β \sqrt{t}$ but enlarges the alphabet to $Σ_{t}$ , and the alphabet reduction returns to $Σ_{⋆}$ at the absolute cost $κ$ . Fixing one $t$ with $κ β \sqrt{t} \geq 2$ therefore restores the factor two, with the cap $α$ for large inputs. The threshold $t$ and the cap $α$ are computed from absolute constants alone, so no input-dependent choice or sampling is involved and the map can be iterated. The lemma asserts only the lower bound on unsatisfaction; it makes no claim about value one, which is supplied separately by One Dinur transformation preserves perfect satisfiability.

Depends on

Used by

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Irit Dinur, The PCP Theorem by Gap Amplification, §1.3 Theorem 1.5 (Main), soundness clause and fixed output alphabet, printed pp. 4–5 (standard reference, not scraped)
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §18.5.1 gap amplification (Lemma 18.29) and §18.5.2 alphabet reduction (Lemma 18.30), printed pp. 370–379 (standard reference, not scraped)