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

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.

Powering amplifies a small unsatisfaction gap

Statement

Let $d \geq 1$ , let $Σ$ be a finite alphabet with $∣ Σ ∣ \geq 2$ , and let $α_{0} < 1$ be a constant. Then there are a constant $β > 0$ depending only on $d, ∣ Σ ∣, α_{0}$ , and an integer $t_{0}$ with the same dependence, such that for every $t \geq t_{0}$ , every binary constraint graph $G$ over $Σ$ whose underlying graph is $d$ -regular in the adjacency-slot convention with $E (G) \neq \emptyset$ and normalized second eigenvalue bound $α \leq α_{0}$ , and every labeling $φ$ of the powered graph $G_{t}$ of Constraint graph powering with local-view labels, ${UNSAT}_{φ} (G_{t}) \geq β \sqrt{t} \min (UNSAT (G), 1 / t) .$ In particular, if $0 < ε \leq c / t$ for a constant $c$ then ${UNSAT}_{φ} (G_{t}) \geq β^{'} \sqrt{t} ε$ , and for larger gaps the lower bound saturates at $β / \sqrt{t}$ . No parity hypothesis on $t$ is needed in this parameterization: the powered slots have length $2 t + 1$ and the analysed window is symmetric about the midpoint $t + 1$ . The bound is uniform in the labeling $φ$ .

Facts & Assumptions

Given: integers $d \geq 1$ and $t \geq \max {4, ⌈ (8 C_{0} ∣ Σ ∣)^{2} ⌉}$ ; a finite alphabet $Σ$ with $∣ Σ ∣ \geq 2$ ; a $d$ -regular binary constraint graph $G$ over $Σ$ with $E (G) \neq \emptyset$ and $α \leq α_{0} < 1$ ; a labeling $φ$ of the powered graph $G_{t}$ .

[F1]

For a labeling of $G$ , ${UNSAT}_{σ} (G) = 1 - {val}_{σ} (G)$ is one minus the fraction of ordinary edges satisfied, and $UNSAT (G) = \min_{σ} {UNSAT}_{σ} (G)$ ; for a labeling of $G_{t}$ , ${UNSAT}_{φ} (G_{t})$ is the fraction of ordinary edges violated, equivalently the violation probability for a uniformly random edge oriented by its unique copy- $0$ incidence slot (Constraint graph and labeling value, Constraint graph powering with local-view labels).

[F2]

The plurality decoding $\hat{φ}$ of $φ$ satisfies $p_{v} (\hat{φ} (v)) \geq 1 / ∣ Σ ∣$ for every $v$ , where $p_{v}$ is the law of the value claimed for $v$ by the view at the endpoint of a uniformly random lazy-walk pattern of length $t$ from $v$ (Plurality decoding of powered local views).

[F3]

Draw a uniformly random powered edge oriented by its unique copy- $0$ incidence slot, equivalently a uniform start $v_{0} \in V$ and a uniform lazy-walk pattern $σ \in P_{2 t + 1}$ . With $C_{0} = 1 / \sqrt{2 π}$ and $c_{w i n} : = 1 / (8 C_{0} ∣ Σ ∣)$ , for every $j$ with $∣ j - 1 - t ∣ \leq c_{w i n} \sqrt{t}$ and every slot $s$ of $G$ from $u$ to $u^{'}$ , the probability that both $φ (v_{0}) (κ_{v_{0}, u}) = \hat{φ} (u)$ and $φ (v_{L}) (κ_{v_{L}, u^{'}}) = \hat{φ} (u^{'})$ , conditioned on the $j$ -th lazy step of $σ$ being the option $s$ , is at least $1 / (4 ∣ Σ ∣^{2})$ (Plurality opinions agree with local views in middle positions).

[F4]

For any set $F$ of ordinary edges of $G$ with $ε_{F} = ∣ F ∣ / ∣ E (G) ∣$ , with $A_{i}$ the event that the $i$ -th step of a uniformly random lazy-walk pattern of length $k$ from a uniform start vertex traverses an edge of $F$ , one has $\sum_{1 \leq i < j \leq k} \Pr [A_{i} \cap A_{j}] \leq \sqrt{d / 2} (k^{2} ε_{F}^{2} + k ε_{F} / (1 - α))$ (Violated-edge positions have controlled collisions).

[F5]

If finitely many events satisfy $\sum_{i < j} \Pr [B_{i} \cap B_{j}] \leq C \sum_{i} \Pr [B_{i}]$ for some $C \geq 0$ , then $\Pr [⋃_{i} B_{i}] \geq \sum_{i} \Pr [B_{i}] / (1 + 2 C)$ (Overlap control gives a union lower bound).

Proof

technique · direct

1.1

If $UNSAT (G) = 0$ then the right-hand side is zero and there is nothing to prove, so assume $ε : = UNSAT (G) > 0$ . Let $\hat{φ}$ be the plurality decoding of $φ$ and put $ε^{'} : = {UNSAT}_{\hat{φ}} (G)$ , so $ε^{'} \geq ε$ by [F1]; let $V \subseteq E (G)$ be the set of edges violated by $\hat{φ}$ , of size $ε^{'} ∣ E (G) ∣ \geq 1$ . Choose a set $F \subseteq V$ as follows: if $\min (ε^{'}, 1 / t) ∣ E (G) ∣ \geq 1$ let $F$ be any subset of $V$ with $∣ F ∣ = ⌈ \min (ε^{'}, 1 / t) ∣ E (G) ∣ ⌉$ , and otherwise let $F = {f_{0}}$ for some single violated edge $f_{0}$ . Writing $ε_{F} : = ∣ F ∣ / ∣ E (G) ∣$ and $m : = ∣ E (G) ∣$ , in both cases $ε_{F} \geq \min (ε^{'}, 1 / t) \geq \min (ε, 1 / t) > 0$ , and $ε_{F} \leq \min (ε^{'}, 1 / t) + 1 / m$ . Put $a : = c_{w i n} \sqrt{t}$ and $k : = # {j : ∣ j - 1 - t ∣ \leq a}$ . Since $c_{w i n} < 1$ , this interval lies inside $J$ ; since $t \geq ⌈ c_{w i n}^{- 2} ⌉$ , $a \geq 1$ , and the integer positions give $k = 2 ⌊ a ⌋ + 1$ , so $a \leq k \leq 2 a + 1$ .

F1F2F3constructalgebra

2.1

For $j$ in the window of step 1.1 and $f \in F$ let $B_{j, f}$ be the event that the $j$ -th lazy step of the sampled representative walk traverses a slot of the edge $f$ carrying the relation $R_{f}$ in its specified endpoint order (for a loop, either of its two slots), and that both endpoint views report the decoded labels of the endpoints of $f$ . In the uniform powered-edge model of [F3] the position before the $j$ -th step is uniform, so each of the $2 m$ slots of $G$ is traversed by that step with probability $1 / (2 \cdot 2 m) = 1 / (4 m)$ , and combining this with the conditional bound of [F3] gives $\Pr [B_{j, f}] \geq 1 / (16 m ∣ Σ ∣^{2})$ . Moreover $B_{j, f}$ implies that the sampled powered edge is violated: the tested pair at position $j$ is exactly the pair $(\hat{φ} (u), \hat{φ} (u^{'}))$ of decoded labels at the endpoints of $f$ , and this pair fails $R_{f}$ because $\hat{φ}$ violates $f$ .

F1F3step 1.1algebra

3.1

Let $A_{j}$ be the event that the $j$ -th lazy step of the sampled representative walk traverses an edge of $F$ . If $j = j^{'}$ and $f \neq f^{'}$ then $B_{j, f} \cap B_{j^{'}, f^{'}} = \emptyset$ , a single step traversing one edge only; otherwise $B_{j, f} \cap B_{j^{'}, f^{'}} \subseteq A_{j} \cap A_{j^{'}}$ . The $k$ consecutive lazy steps in the central sub-window have the law of a length- $k$ lazy walk from a uniform start: the walk starts uniformly and the uniform distribution remains stationary at the beginning of this sub-window, while its step choices are independent. Thus [F4] applies to this block and this $F$ , and $\sum_{(j, f) \neq (j^{'}, f^{'})} \Pr [B_{j, f} \cap B_{j^{'}, f^{'}}] \leq 2 \sum_{j < j^{'}} \Pr [A_{j} \cap A_{j^{'}}] \leq 2 \sqrt{d / 2} (k^{2} ε_{F}^{2} + k ε_{F} / (1 - α))$ .

F1F4step 1.1step 2.1

4.1

Summing the bound of step 2.1 over the $k$ positions and the $∣ F ∣$ edges gives $S : = \sum_{j, f} \Pr [B_{j, f}] \geq k ∣ F ∣ / (16 m ∣ Σ ∣^{2}) = k ε_{F} / (16 ∣ Σ ∣^{2}) \geq c_{w i n} \sqrt{t} ε_{F} / (16 ∣ Σ ∣^{2}) > 0$ , and the events and the collision sum are finite, so [F5] is applicable. Applying it with the ratio $C : = \frac{\sum_{(j, f) \neq (j^{'}, f^{'})} \Pr [B_{j, f} \cap B_{j^{'}, f^{'}}]}{S} \leq \frac{2 \sqrt{d / 2} (k^{2} ε_{F}^{2} + k ε_{F} / (1 - α)) \cdot 16 ∣ Σ ∣^{2}}{k ε_{F}} = 32 \sqrt{\frac{d}{2}} ∣ Σ ∣^{2} (k ε_{F} + \frac{1}{1 - α})$ gives $\Pr [⋃_{j, f} B_{j, f}] \geq S / (1 + 2 C)$ .

F5step 2.1step 3.1algebra

5.1

Two regimes. If $k ε_{F} \leq 1$ then $1 + 2 C \leq 1 + 64 \sqrt{d / 2} ∣ Σ ∣^{2} (1 + 1 / (1 - α_{0})) = : 1 + 2 C^{*}$ and hence $\Pr [⋃ B] \geq c_{w i n} \sqrt{t} ε_{F} / (16 ∣ Σ ∣^{2} (1 + 2 C^{*})) = β_{1} \sqrt{t} ε_{F}$ , where $β_{1} : = c_{w i n} / (16 ∣ Σ ∣^{2} (1 + 2 C^{*}))$ . If $k ε_{F} > 1$ then $k ε_{F} + 1 / (1 - α) \leq k ε_{F} (1 + 1 / (1 - α))$ , so $1 + 2 C \leq (1 + 64 \sqrt{d / 2} ∣ Σ ∣^{2} (1 + 1 / (1 - α_{0}))) k ε_{F}$ and $\Pr [⋃ B] \geq 1 / (16 ∣ Σ ∣^{2} (1 + 2 C^{*})) = β_{2}$ with $β_{2} : = 1 / (16 ∣ Σ ∣^{2} (1 + 2 C^{*}))$ . Every $B_{j, f}$ implies that the sampled powered edge is violated, so ${UNSAT}_{φ} (G_{t}) \geq \Pr [⋃_{j, f} B_{j, f}]$ , and because $\sqrt{t} \min (ε, 1 / t) \leq t^{- 1 / 2} \leq 1$ for $t \geq 1$ while $ε_{F} \geq \min (ε, 1 / t)$ , both regimes give ${UNSAT}_{φ} (G_{t}) \geq \min (β_{1}, β_{2}) \sqrt{t} \min (UNSAT (G), 1 / t)$ with $β : = \min (β_{1}, β_{2})$ and $t_{0} : = \max {4, ⌈ c_{w i n}^{- 2} ⌉}$ .

step 1.1step 4.1algebra∎

Remarks

The two regimes are the two halves of the promise. For $k ε_{F} \leq 1$ the union bound loses only the constant $1 + 2 C^{*}$ and delivers $Θ (\sqrt{t} ε_{F})$ ; for $k ε_{F} > 1$ the same computation yields a constant lower bound, which dominates $β \sqrt{t} \min (ε, 1 / t)$ because that quantity is at most $β / \sqrt{t}$ . This is exactly Dinur's Lemma 6.1 with $\min (UNSAT (G), 1 / t)$ , and it is what makes the iteration of A complete uniform graph gap-amplification step terminate in $O (\log M)$ rounds.
The window is a sub-window of the central window. The positions used lie in $J_{c} \subseteq J$ and number $k = 2 ⌊ c_{w i n} \sqrt{t} ⌋ + 1 \geq c_{w i n} \sqrt{t}$ , so every event $B_{j, f}$ is a violation of the powered slot relation and the sub-window still gives the $\sqrt{t}$ gain. Over the full central window the middle-position lemma would lose a constant and the collision term $k ε_{F} / (1 - α)$ would grow.
Where each constant comes from. $β$ depends only on $d, ∣ Σ ∣, α_{0}$ : through $c_{w i n} = 1 / (8 C_{0} ∣ Σ ∣)$ and the factor $1 / (1 - α)$ of the collision bound, and through $\sqrt{d / 2}$ in the same bound. No dependence on $n$ , on $∣ E (G) ∣$ , on $t$ or on the labeling remains, and the proof chooses nothing beyond the subset $F$ and the slot of each edge, both of which are fixed deterministically.
The statement above is uniform over labelings of $G_{t}$ , including non-liftable ones; that is the content of the decoding step 1.1, which replaces an arbitrary powered labeling by one base labeling $\hat{φ}$ at the cost of the factor $1$ in $ε^{'} \geq ε$ .

Depends on

Used by

A complete uniform graph gap-amplification step Theorem

Dependency tree · two levels

11 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, §6 Lemma 6.1 and its proof (Lemmas 6.2-6.4), printed pp. 19-24. (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Lemma 18.29 part 3 with Claims 18.32-18.34, printed pp. 372-377. (standard reference, not scraped)