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.

Nearby lazy-walk lengths have close endpoint and claim laws

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, and use the lazy-walk convention of Constraint graph powering with local-view labels: a lazy step at a vertex chooses uniformly among $2 d$ options, the $d$ hold options and the $d$ slots at that vertex, and a lazy-walk pattern of length $ℓ$ is drawn uniformly from $P_{ℓ}$ . Put $C_{0} : = \frac{1}{\sqrt{2 π}} < \frac{1}{2} .$ For $ℓ \geq 1$ let $B_{ℓ}$ be the number of non-hold options of a uniformly random lazy-walk pattern of length $ℓ$ read from a vertex $v$ ; $B_{ℓ} \sim Bin (ℓ, \frac{1}{2})$ for every $v$ . Then:

Binomial closeness. For all integers $m, m^{'} \geq 1$ with $∣ m - m^{'} ∣ \leq \sqrt{\min (m, m^{'})}$ , $TV (Bin (m, \frac{1}{2}), Bin (m^{'}, \frac{1}{2})) \leq C_{0} \frac{∣ m - m^{'} ∣}{\sqrt{\min (m, m^{'})}} .$
Transfer to walk statistics. A lazy-walk pattern determines its endpoint from its sequence of non-hold options. For any fixed labeling $φ$ of the powered graph $G_{t}$ with its fixed view radius $R = t + ⌈ \sqrt{t} ⌉$ and lengths $1 \leq ℓ, ℓ^{'} \leq R$ , the view at that endpoint claims for its start the value at the canonical coordinate specified in Plurality decoding of powered local views. Thus the claimed value, like the endpoint, is a function of the non-hold option sequence alone. Let $X_{v, ℓ}$ denote the value claimed for $v$ by the view at the endpoint of a uniformly random lazy-walk pattern of length $ℓ$ from $v$ . Then for $m = \min (ℓ, ℓ^{'})$ and $∣ ℓ - ℓ^{'} ∣ \leq \sqrt{m}$ , $TV (X_{v, ℓ}, X_{v, ℓ^{'}}) \leq C_{0} \frac{∣ ℓ - ℓ^{'} ∣}{\sqrt{m}},$ The same endpoint-law bound holds for arbitrary positive lengths satisfying the displayed window condition, without a radius restriction.
The window used by the powering analysis. If $t \geq 4$ and $∣ ℓ - t ∣ \leq \sqrt{t} / (8 C_{0} ∣ Σ ∣)$ , then $TV (X_{v, t}, X_{v, ℓ}) \leq 1 / (4 ∣ Σ ∣)$ , uniformly in the start vertex $v$ and in the labeling of $G_{t}$ .

Facts & Assumptions

Given: a $d$ -regular binary constraint graph $G$ in the stated convention, its lazy-walk patterns, a vertex $v$ , lengths $ℓ, ℓ^{'} \geq 1$ , and the statistic $X_{v, ℓ}$ of the claimed value defined above.

[F1]

A lazy step at $v$ chooses uniformly among the $2 d$ options consisting of $d$ hold options and the $d$ slots at $v$ ; the steps of a lazy-walk pattern are independent, the pattern set $P_{ℓ} = {1, \dots, 2 d}^{ℓ}$ has $(2 d)^{ℓ}$ elements, the transition matrix is $(I + M) / 2$ , the uniform distribution is stationary, and reversal of a pattern interchanges its start and endpoint (Constraint graph powering with local-view labels).

[F2]

For any $1 \leq ℓ \leq R$ and pattern $π \in P_{ℓ}$ from $v$ ending at $w$ , the view at $w$ claims the value $φ (w) (κ_{w, v})$ for $v$ , where $κ_{w, v}$ is the fixed canonical pattern from $w$ to $v$ ; $X_{v, ℓ}$ is this claimed value for a uniformly random $π$ (Plurality decoding of powered local views).

[L1]

For $a_{n} = (\binom{2 n}{n}) / 4^{n}$ one has $\sqrt{π n} a_{n} \to 1$ as $n \to \infty$ (The central binomial coefficient is asymptotic to 4^n divided by the square root of pi n).

Proof

technique · direct

1.1

A pattern records at each coordinate whether it is a hold or a move, together with the chosen option within that type. For each $k$ , there are $(\binom{ℓ}{k}) d^{k} d^{ℓ - k} = (\binom{ℓ}{k}) d^{ℓ}$ patterns with exactly $k$ moves, so $B_{ℓ} \sim Bin (ℓ, \frac{1}{2})$ . Conditional on $B_{ℓ} = k$ , the sequence of the $k$ move slots is uniform among the $d^{k}$ slot sequences; hold-option identities and the set of hold positions do not affect it. In particular $B_{ℓ}$ does not depend on $v$ .

F1given

1.2

Write $P_{m} (k) = (\binom{m}{k}) 2^{- m}$ and $b_{m} = \max_{k} P_{m} (k)$ , and let $a_{r} = (\binom{2 r}{r}) / 4^{r}$ . Then $b_{2 r} = a_{r}$ and $b_{2 r + 1} = a_{r} (2 r + 1) / (2 r + 2)$ , while $a_{r + 1} / a_{r} = (2 r + 1) / (2 r + 2) < 1$ ; hence $b_{m}$ is nonincreasing in $m$ . Moreover $a_{r} \sqrt{r}$ is increasing because $(a_{r + 1} \sqrt{r + 1}) / (a_{r} \sqrt{r}) = \sqrt{(2 r + 1)^{2} / (4 r (r + 1))} > 1$ , so [L1] gives $a_{r} \leq 1 / \sqrt{π r}$ . For even $m = 2 r$ this yields $b_{m} \leq \sqrt{2 / (π m)}$ . For odd $m = 2 r + 1$ with $r \geq 1$ , it gives $b_{m} \leq (2 r + 1) / ((2 r + 2) \sqrt{π r}) \leq \sqrt{2 / (π (2 r + 1))}$ , since squaring the last inequality reduces to $4 r^{2} + 2 r - 1 \geq 0$ ; and $b_{1} = 1 / 2 \leq \sqrt{2 / π}$ . Thus in every case $b_{m} \leq \sqrt{2 / (π m)} = 2 C_{0} / \sqrt{m}$ .

L1algebra

2.1

The endpoint of a pattern is determined by its sequence of non-hold options, and the claimed value of [F2] is the value of the fixed canonical coordinate from that endpoint back to $v$ . Hence both the endpoint and the claimed value are functions of the non-hold option sequence alone.

F1F2step 1.1

2.2

Pascal's rule gives $P_{m + 1} (k) = \frac{1}{2} (P_{m} (k) + P_{m} (k - 1))$ , so $\sum_{k} ∣ P_{m + 1} (k) - P_{m} (k) ∣ = \frac{1}{2} \sum_{k} ∣ P_{m} (k) - P_{m} (k - 1) ∣$ . The sequence $k \mapsto P_{m} (k)$ rises to its maximum and then falls, so its total variation is at most $2 b_{m}$ and hence $TV (Bin (m, \frac{1}{2}), Bin (m + 1, \frac{1}{2})) \leq \frac{1}{2} b_{m}$ .

step 1.2algebra

3.1

For $m^{'} \geq m$ the triangle inequality for total variation and step 2.2 give $TV (Bin (m, \frac{1}{2}), Bin (m^{'}, \frac{1}{2})) \leq \frac{1}{2} \sum_{i = 0}^{m^{'} - m - 1} b_{m + i} \leq \frac{m^{'} - m}{2} b_{m} \leq C_{0} \frac{m^{'} - m}{\sqrt{m}}$ by the monotonicity and the bound of step 1.2; the case $m^{'} < m$ is the same with the roles exchanged, which proves claim 1 with $\min (m, m^{'})$ in the denominator.

step 1.2step 2.2algebra

4.1

Let $1 \leq ℓ, ℓ^{'} \leq R$ with $m = \min (ℓ, ℓ^{'})$ and $∣ ℓ - ℓ^{'} ∣ \leq \sqrt{m}$ be given, and couple $B_{ℓ}$ and $B_{ℓ^{'}}$ maximally, so that they differ with probability $TV (Bin (ℓ, \frac{1}{2}), Bin (ℓ^{'}, \frac{1}{2}))$ . Conditionally on $B_{ℓ} = B_{ℓ^{'}} = k$ , use the same uniform slot sequence of length $k$ from $v$ in both experiments, which is legitimate by the conditional uniformity of step 1.1 and the fact that the endpoints and claimed values are functions of that sequence by step 2.1. This couples $X_{v, ℓ}$ and $X_{v, ℓ^{'}}$ to agree except on an event of probability at most the binomial total variation, and endpoints are coupled in the same way; claim 2 follows from step 3.1.

step 1.1step 2.1step 3.1

5.1

If $t \geq 4$ and $∣ ℓ - t ∣ \leq \sqrt{t} / (8 C_{0} ∣ Σ ∣)$ , then the window constant $1 / (8 C_{0} ∣ Σ ∣) < 1$ gives $∣ ℓ - t ∣ \leq \sqrt{t}$ and hence $m = \min (ℓ, t) \geq t - \sqrt{t} \geq t / 2$ . Also $1 / (8 C_{0} ∣ Σ ∣) < 1 / \sqrt{2}$ for $∣ Σ ∣ \geq 1$ , so $∣ ℓ - t ∣ \leq \sqrt{t / 2} \leq \sqrt{m}$ and $1 \leq ℓ \leq t + \sqrt{t} \leq R$ , so claim 2 applies. It gives $TV (X_{v, ℓ}, X_{v, t}) \leq C_{0} ∣ ℓ - t ∣ / \sqrt{m} \leq \sqrt{2} / (8 ∣ Σ ∣) \leq 1 / (4 ∣ Σ ∣)$ . This proves claim 3 uniformly in $v$ and in the powered labeling.

step 4.1algebra∎

Remarks

The lemma is stated for the binomial law of the number of moves rather than for the non-lazy walk of a fixed length, because the lazy convention of Constraint graph powering with local-view labels makes the hold positions independent of the moves; this couples endpoints and the canonical-coordinate claims using the same move sequence. Dinur's Lemma 6.4 proves the analogous binomial weight-ratio estimate for the non-lazy distribution with $p = 1 - 1 / d$ , and Arora-Barak's printed p. 374 uses the statistical-distance form with the constant $10 δ$ for a window of size $δ \sqrt{t}$ ; the constant $C_{0} = 1 / \sqrt{2 π}$ above is the exact constant supplied by the central binomial asymptotic.
No hypothesis on the graph beyond $d$ -regularity is used: the lemma compares laws of walks of different lengths on the same graph and involves neither the spectral gap nor the alphabet. The alphabet enters only through the final constant $1 / (4 ∣ Σ ∣)$ of claim 3, which fixes the admissible window width.
The transfer claim is stated for the claimed-value statistic because that is the consumer's need in Plurality opinions agree with local views in middle positions; the endpoint version is the special case in which the statistic forgets the endpoint's view coordinate.

Depends on

Used by

Plurality opinions agree with local views in middle positions Lemma

Dependency tree · two levels

15 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.1 Lemma 6.4 and Appendix A (binomial weight ratios), printed pp. 22-23 and 41. (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1, printed p. 374 (endpoint distributions of t-step and (t+δ√t)-step walks are within statistical distance 10δ). (standard reference, not scraped)