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.

Plurality opinions agree with local views in middle positions

Statement

Let $G$ be a binary constraint graph over $Σ$ whose underlying graph is $d$ -regular in the adjacency-slot convention of Constraint graph and labeling value, let $t \geq 4$ , let $G_{t}$ be its powered graph with walk length $L = 2 t + 1$ , central window $J$ and view alphabet $Σ_{t}$ , and let $φ : V \to Σ_{t}$ be any labeling of $G_{t}$ with plurality decoding $\hat{φ}$ (Plurality decoding of powered local views). Write $c : = \frac{1}{8 C_{0} ∣ Σ ∣}, C_{0} = \frac{1}{\sqrt{2 π}},$ so that $c < 1$ , and let $J_{c} : = {j \in J : ∣ j - 1 - t ∣ \leq c \sqrt{t}}$ be the corresponding sub-window of the central window; it is nonempty, since $t + 1 \in J_{c}$ .

Draw a uniformly random ordinary edge of $G_{t}$ and orient it by its unique copy- $0$ incidence slot; equivalently, choose a uniformly random start vertex $v_{0} \in V$ and a uniformly random lazy-walk pattern $σ = (σ_{1}, \dots, σ_{L}) \in P_{L}$ , giving the visited vertices $v_{0}, \dots, v_{L}$ . Then for every $j \in J_{c}$ and every slot $s$ of $G$ from $u$ to $u^{'}$ (every one of the $d$ slot options at $u$ , loops included, and no hold option), $\Pr [φ (v_{0}) (κ_{v_{0}, u}) = \hat{φ} (u) and φ (v_{L}) (κ_{v_{L}, u^{'}}) = \hat{φ} (u^{'}) ∣ the j -th lazy step of σ is the option s] \geq \frac{1}{4 ∣ Σ ∣^{2}},$ where the two $κ$ coordinates are the canonical patterns specified by the slot relation of Constraint graph powering with local-view labels. In words: whenever a powered walk traverses a fixed slot at a middle position of the window $J_{c}$ , the two endpoint views report the decoded plurality labels of that slot's two endpoints with probability bounded below by a positive constant depending only on $∣ Σ ∣$ . The bound is uniform in the slot, in the position, in the graph, in $t$ and in the powered labeling.

Facts & Assumptions

Given: a $d$ -regular binary constraint graph $G$ over $Σ$ , an integer $t \geq 4$ , the powered graph $G_{t}$ with parameters $R, L, J, Σ_{t}$ , a labeling $φ$ of $G_{t}$ with decoding $\hat{φ}$ , a position $j \in J_{c}$ and a slot $s$ of $G$ from $u$ to $u^{'}$ .

[F1]

Under the sampling convention of Constraint graph powering with local-view labels, a uniformly random powered edge oriented by its unique copy- $0$ incidence slot is a uniformly random start vertex and length- $L$ pattern; its step options are independent and uniform, and reversal pairs its copy- $0$ incidence with the copy- $1$ incidence of the reversed pattern (Constraint graph powering with local-view labels).

[F2]

For any $1 \leq ℓ \leq R$ and uniformly random lazy-walk pattern $π$ of length $ℓ$ from a vertex $x$ , let $X_{x, ℓ}$ be the value claimed for $x$ by the view at the endpoint of $π$ , namely $φ (y) (κ_{y, x})$ where $y$ is the endpoint and $κ_{y, x}$ is the canonical pattern from $y$ to $x$ ; the opinion distribution of the decoding is $p_{x} (a) = \Pr [X_{x, t} = a]$ , and $\hat{φ} (x)$ maximises $p_{x}$ , so $p_{x} (\hat{φ} (x)) \geq 1 / ∣ Σ ∣$ (Plurality decoding of powered local views).

[L1]

If $1 \leq ℓ \leq R$ , $m = \min (ℓ, t)$ , $∣ ℓ - t ∣ \leq \sqrt{m}$ and $∣ ℓ - t ∣ \leq \sqrt{t}$ , then $TV (X_{x, t}, X_{x, ℓ}) \leq C_{0} ∣ ℓ - t ∣ / \sqrt{m}$ ; consequently $TV (X_{x, t}, X_{x, ℓ}) \leq 1 / (4 ∣ Σ ∣)$ whenever $∣ ℓ - t ∣ \leq c \sqrt{t}$ , uniformly in the start vertex $x$ and in the labeling $φ$ (Nearby lazy-walk lengths have close endpoint and claim laws).

Proof

technique · direct

1.1

Condition on the $j$ -th lazy step of the sampled representative walk being the option $s$ at $v_{j - 1} = u$ ; this forces $v_{j} = u^{'}$ . The coordinates of $σ$ other than the $j$ -th are still independent uniform options, the constraint links only the prefix coordinates $1, \dots, j - 1$ through the requirement that the prefix ends at $u$ , and it does not involve the suffix coordinates $j + 1, \dots, L$ . Hence, conditionally, the suffix $(σ_{j + 1}, \dots, σ_{L})$ read from $u^{'}$ is a uniformly random lazy-walk pattern of length $L - j$ , the prefix is a uniformly random pattern of length $j - 1$ from $v_{0}$ ending at $u$ , the two are independent, and $v_{0}$ is the start of that prefix. Reversal is a bijection from patterns of length $j - 1$ ending at $u$ to patterns of length $j - 1$ starting at $u$ , and preserves the uniform law on each such set, so the reversed prefix is a uniformly random lazy-walk pattern of length $j - 1$ from $u$ . For $j \in J_{c}$ we have $j - 1 \geq t - c \sqrt{t} \geq 1$ , $L - j \geq t + 1 - c \sqrt{t} - 1 \geq 1$ , and both lengths differ from $t$ by at most $c \sqrt{t}$ .

F1givenalgebra

2.1

By the powering definition, the relation reads the canonical coordinates $φ (v_{0}) (κ_{v_{0}, u})$ and $φ (v_{L}) (κ_{v_{L}, u^{'}})$ . The reversed prefix from $u$ ends at $v_{0}$ , so the first coordinate has the law of $X_{u, j - 1}$ by [F2]; the suffix from $u^{'}$ ends at $v_{L}$ , so the second has the law of $X_{u^{'}, L - j}$ . The prefix and suffix patterns are independent under step 1.1, so the two claimed values are independent.

F1F2step 1.1

2.2

By [F2] the decoding satisfies $p_{u} (\hat{φ} (u)) \geq 1 / ∣ Σ ∣$ , and by [L1], applied with $ℓ = j - 1$ and $x = u$ , the law $X_{u, j - 1}$ is within total variation $1 / (4 ∣ Σ ∣)$ of $X_{u, t}$ because $1 \leq j - 1 \leq R$ and $∣ j - 1 - t ∣ \leq c \sqrt{t}$ ; hence $\Pr [X_{u, j - 1} = \hat{φ} (u)] \geq p_{u} (\hat{φ} (u)) - 1 / (4 ∣ Σ ∣) \geq 3 / (4 ∣ Σ ∣) \geq 1 / (2 ∣ Σ ∣)$ . The same computation with $ℓ = L - j$ and $x = u^{'}$ gives $\Pr [X_{u^{'}, L - j} = \hat{φ} (u^{'})] \geq 1 / (2 ∣ Σ ∣)$ , since $1 \leq L - j \leq R$ and $∣ L - j - t ∣ = ∣ j - 1 - t ∣ \leq c \sqrt{t}$ .

F2L1step 1.1algebra

3.1

Multiplying the two conditional probabilities of step 2.2 and using the conditional independence of step 2.1 gives the bound $1 / (4 ∣ Σ ∣^{2})$ for the event that both endpoint views report the decoded labels of $u$ and $u^{'}$ . This holds for every $j \in J_{c}$ and every slot $s$ of $G$ , with constants depending only on $∣ Σ ∣$ and not on the graph, on $t$ , on the position or on the powered labeling, and it covers loops through $u = u^{'}$ .

step 2.1step 2.2algebra∎

Remarks

Both endpoints are needed and the tested position is central. The slot relation of Constraint graph powering with local-view labels tests at position $j$ the canonical coordinate at the view on the first vertex $v_{0}$ for $u$ and the canonical coordinate at the view on the last vertex $v_{L}$ for $u^{'}$ ; that is why the argument conditions on the walk through the two endpoints of the traversed slot and not on a single random walk. The position $t + 1$ always belongs to $J_{c}$ .
The sub-window is a genuine restriction. Item [L1] loses only $1 / (4 ∣ Σ ∣)$ of probability over lengths $t \pm c \sqrt{t}$ , so the constant survives; over the whole central window of width $≍ \sqrt{t}$ the loss is a positive constant and the argument would fail for large alphabets. The promise of A complete uniform graph gap-amplification step is unaffected, because $J_{c}$ still has $Θ (\sqrt{t})$ positions and every slot violation detected at a position of $J_{c} \subseteq J$ is a violation of the powered slot.
Numerical form of the window. By definition of $C_{0}$ , $c = 1 / (8 C_{0} ∣ Σ ∣) = \sqrt{π / 32} / ∣ Σ ∣ < 1$ , so the window is centred at $t + 1$ and is nonempty for every $t \geq 4$ .
The claim is stated conditionally on the traversed option rather than unconditionally, because the consumer Powering amplifies a small unsatisfaction gap must multiply it by the probability that a stationary lazy walk traverses a given violated slot; that probability is computed there.

Depends on

Used by

Powering amplifies a small unsatisfaction gap Lemma

Dependency tree · two levels

7 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

Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1 Claim 18.32, printed pp. 374-375. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §6 first-moment estimate (Lemma 6.2), printed pp. 21-23. (standard reference, not scraped)