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.

Violated-edge positions have controlled collisions

Statement

Let $G$ be a binary constraint graph over $Σ$ in the convention of Constraint graph and labeling value whose underlying graph is a finite $d$ -regular adjacency-slot multigraph on $n \geq 1$ vertices with normalized adjacency $M$ and normalized second eigenvalue bound $α = ∥ M ∣_{1^{⊥}} ∥ < 1$ (for $n = 1$ put $α : = 0$ ), as in Regular multigraph and normalized adjacency. Let $F$ be a set of ordinary edges of $G$ (loops allowed), put $ε : = ∣ F ∣ / ∣ E ∣$ , let $k \geq 1$ , and consider a uniformly random lazy-walk pattern of length $k$ read from a uniformly random start vertex, in the lazy-walk convention of Constraint graph powering with local-view labels. Let $A_{i}$ be the event that the $i$ -th lazy step of this pattern traverses an edge of $F$ . Then $\sum_{1 \leq i < j \leq k} \Pr [A_{i} \cap A_{j}] \leq \sqrt{\frac{d}{2}} (k^{2} ε^{2} + \frac{k ε}{1 - α}) .$ Consequently, on the small-gap range $k ε \leq c$ for an absolute constant $c$ , $\sum_{1 \leq i < j \leq k} \Pr [A_{i} \cap A_{j}] \leq \sqrt{\frac{d}{2}} (c + \frac{1}{1 - α}) k ε = O (k ε),$ the constant depending only on $d$ , $α$ and $c$ . Both bounds are uniform in $F$ ; for $ε = 0$ both sides vanish.

Facts & Assumptions

Given: a $d$ -regular binary constraint graph $G$ with $M, α$ as above, a set $F$ of ordinary edges, including possible loops, with $ε = ∣ F ∣ / ∣ E ∣$ , an integer $k \geq 1$ , and the events $A_{1}, \dots, A_{k}$ of the random lazy-walk pattern.

[F1]

A lazy step at a vertex chooses uniformly among the $2 d$ options consisting of the $d$ hold options and the $d$ slots at that vertex, the steps are independent, and the transition matrix of one lazy step is $P = (I + M) / 2$ , for which the uniform distribution on $V$ is stationary; a lazy-walk pattern of length $k$ read from a start vertex is a uniformly random element of $P_{k}$ (Constraint graph powering with local-view labels).

[F2]

The underlying graph has $n d$ slots and $∣ E ∣ = n d / 2$ ordinary edges, uniform directed-slot sampling induces the uniform distribution on the ordinary edges, and each vertex has exactly $d$ outgoing slots; a nonloop ordinary edge contributes one slot at each of its two endpoints, and loops have two slots at the same vertex (Regular multigraph and normalized adjacency).

[F3]

Any ordinary edge of $G$ is a relation $R_{e} \subseteq Σ^{2}$ in a specified endpoint order; fractions of satisfied or violated edges are computed with respect to the ordinary edges (Constraint graph and labeling value).

[L1]

For any initial probability vector $p$ and integer $t \geq 0$ , $∥ M^{t} p - u ∥_{2} \leq α^{t} ∥ p - u ∥_{2}$ with $u = 1 / n$ , in the ordinary Euclidean norm (Expander walk contraction).

[L2]

For vectors $u, v$ in a real or complex inner product space, $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ (Cauchy–Schwarz: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥ ∥ v ∥$ , with equality exactly for linearly dependent vectors).

Proof

technique · direct

1.1

By [F1] the start vertex is uniform and every lazy step preserves the uniform law, so the position before the $i$ -th step is uniform for every $i$ , and $\Pr [A_{i}] = \frac{1}{2} \cdot \frac{2 ∣ F ∣}{n d} = ε / 2$ : with probability $\frac{1}{2}$ the step is a hold, and otherwise it uses one of the $n d$ directed slots with uniform marginal law, of which $2 ∣ F ∣$ belong to $F$ , by [F2].

F1F2F3algebra

2.1

If $F = \emptyset$ , every event $A_{i}$ is empty and both bounds in the statement are zero, so assume $∣ F ∣ > 0$ . Fix $i < j$ and let $x \in R^{n}$ be the law of the position after step $i$ conditioned on $A_{i}$ , and let $f \in R^{n}$ have $f (w) = \Pr [a lazy step at w traverses an edge of F]$ , so that $\Pr [A_{j} ∣ A_{i}] = ⟨ P^{j - i - 1} x, f ⟩$ in the ordinary Euclidean inner product. In the stationary walk each of the $2 ∣ F ∣$ slots of $F$ is traversed with the same probability, so the traversed slot under $A_{i}$ is equally likely to be any of them. Thus $x_{v} \leq d_{F} (v) / (2 ∣ F ∣) \leq d / (2 ∣ F ∣)$ , with $d_{F}$ the number of slots of $F$ at $v$ . Since $\sum_{v} x_{v} = 1$ , $∥ x - u ∥_{2}^{2} = \sum_{v} x_{v}^{2} - 1 / n \leq d / (2 ∣ F ∣)$ . Also $f (w) = d_{F} (w) / (2 d) \leq \frac{1}{2}$ and $\sum_{w} f (w) = ∣ F ∣ / d$ , so in the same Euclidean norm $∥ f ∥_{2}^{2} = \sum_{w} f (w)^{2} \leq \frac{1}{2} \sum_{w} f (w) = ∣ F ∣ / (2 d)$ . Consequently $∥ x - u ∥_{2} ∥ f ∥_{2} \leq 1 / 2$ .

F1F2step 1.1algebra

3.1

Since $P = (I + M) / 2$ and $M$ leaves the mean-zero subspace invariant with operator norm $α$ by [L1], expanding $P^{h} = 2^{- h} \sum_{t = 0}^{h} (\binom{h}{t}) M^{t}$ gives $∥ P^{h} (x - u) ∥_{2} \leq (\frac{1 + α}{2})^{h} ∥ x - u ∥_{2}$ for every $h \geq 0$ ; here $\frac{1 + α}{2} < 1$ and $(1 - \frac{1 + α}{2})^{- 1} = 2 / (1 - α)$ . Splitting $⟨ P^{h} x, f ⟩ = ⟨ u, f ⟩ + ⟨ P^{h} (x - u), f ⟩$ and applying [L2] in the ordinary Euclidean norm with step 2.1 yields $\Pr [A_{j} ∣ A_{i}] \leq ε / 2 + \frac{1}{2} (\frac{1 + α}{2})^{j - i - 1} \leq ε / 2 + \sqrt{d / 2} (\frac{1 + α}{2})^{j - i - 1}$ , since $d \geq 1$ .

L1L2step 2.1algebra

4.1

Multiplying by $\Pr [A_{i}] = ε / 2$ and summing over $i < j$ gives $\sum_{i < j} \Pr [A_{i} \cap A_{j}] \leq \frac{k^{2}}{2} \cdot \frac{ε^{2}}{4} + \frac{ε}{2} \sqrt{\frac{d}{2}} \sum_{i < j} (\frac{1 + α}{2})^{j - i - 1} \leq \frac{k^{2} ε^{2}}{8} + \frac{k ε}{2} \sqrt{\frac{d}{2}} \cdot \frac{2}{1 - α}$ , which is at most $\sqrt{d / 2} (k^{2} ε^{2} + k ε / (1 - α))$ because $\sqrt{d / 2} \geq 1 / 8$ for $d \geq 1$ . For $k ε \leq c$ the term $k^{2} ε^{2}$ is at most $c k ε$ , so the sum is at most $\sqrt{d / 2} (c + 1 / (1 - α)) k ε$ , and for $ε = 0$ all the events are empty and both displays vanish.

step 3.1algebra∎

Remarks

What is counted. $A_{i}$ is the event that the $i$ -th lazy step traverses an edge of $F$ (a move, never a hold option); the collision estimate therefore also bounds the overlaps of the smaller events $B_{j, f}$ of Powering amplifies a small unsatisfaction gap, which require in addition that the two endpoint views report the decoded labels of the edge. Loop edges are allowed in $F$ : a loop has two slots at its vertex, so $\sum_{v} d_{F} (v) = 2 ∣ F ∣$ and the incidence bounds of step 2.1 remain correct, and a loop step keeps the walk at its vertex while still testing the relation on the two claims of the two endpoint views.
Where the small-gap hypothesis enters. The term $k^{2} ε^{2}$ is dominated by $k ε$ exactly when $k ε$ is bounded, which is the range $ε = O (1 / \sqrt{t})$ of the powering analysis; the other term $\sqrt{d / 2} k ε / (1 - α)$ is the spectral contribution and is already $O (k ε)$ for fixed spectral gap. The dependence on the spectral gap is through $1 / (1 - α)$ only, and not through any power of $n$ .
The lazy convention halves the first moment but leaves the collision structure intact: the ratio $\Pr [A_{j} ∣ A_{i}] ≲ ε / 2 + α_{L}^{j - i - 1}$ has the same shape as the walk-return bound of the published expander items for the non-lazy walk, with $α_{L} = (1 + α) / 2$ ; the argument above re-derives it for $P$ because the published contraction lemma is stated for $M$ .
The bound is uniform in $F$ : no lower bound on $∣ F ∣$ is used beyond $∣ F ∣ \geq 1$ in the case $ε > 0$ , and the case $F = \emptyset$ is the vanishing case $ε = 0$ .

Depends on

Used by

Powering amplifies a small unsatisfaction gap Lemma

Dependency tree · two levels

12 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.33, printed p. 376. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §6.2 Proposition 6.5 and Lemma 6.3, printed pp. 23-24. (standard reference, not scraped)