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.

Canonical local views preserve perfect satisfiability

Statement

Let $G$ be a $d$ -regular binary constraint graph over $Σ$ , let $t \geq 1$ and let $G_{t}$ be its powered graph as in Constraint graph powering with local-view labels. If $σ : V \to Σ$ satisfies every edge of $G$ , then the canonical lift $\overset{ˉ}{σ}$ defined by $\overset{ˉ}{σ} (v) (π) : = σ (endpoint of the pattern π read from v), π \in P_{R},$ is a labeling of $G_{t}$ that satisfies every slot of $G_{t}$ ; in particular $val (G_{t}) = 1$ whenever $val (G) = 1$ . The same holds with repeated vertices, hold steps and loops, and no hypothesis on $t$ beyond $t \geq 1$ is used.

Facts & Assumptions

Given: a $d$ -regular binary constraint graph $G$ over $Σ$ , an integer $t \geq 1$ , its powered graph $G_{t}$ with view alphabet $Σ_{t} = Σ^{P_{R}}$ , central window $J$ and slot relations as in the powering definition, and a labeling $σ$ of $G$ that satisfies every edge.

[F1]

A view is a function $φ : P_{R} \to Σ$ ; a directed incidence slot of $G_{t}$ is indexed by a length- $L$ pattern read from a vertex $v_{0}$ and a copy bit, visits $v_{0}, \dots, v_{L}$ , joins $v_{0}$ to $v_{L}$ , and its relation table is determined by the starting vertex and the pattern (with the base graph fixed), independently of the copy bit. That table accepts the pair of views $(φ, ψ)$ exactly when for every $j \in J$ whose step is a move along a slot $e = (v_{j - 1}, v_{j})$ , the pair $(φ (κ_{v_{0}, v_{j - 1}}), ψ (κ_{v_{L}, v_{j}}))$ lies in the relation of $e$ ; the two canonical patterns exist because their endpoints lie within radius $R$ of their view centres, and hold steps impose no condition (Constraint graph powering with local-view labels).

[F2]

For an edge $e$ with endpoints $u, w$ in the specified order, a labeling satisfies $e$ exactly when $(σ (u), σ (w)) \in R_{e}$ ; loops are tested on the repeated label and a labeling satisfies $G$ when it satisfies every ordinary edge (Constraint graph and labeling value).

Proof

technique · direct

1.1

For each $v \in V$ and each pattern $π \in P_{R}$ the endpoint of $π$ read from $v$ is a well-defined vertex, so $\overset{ˉ}{σ} (v)$ is a function $P_{R} \to Σ$ , i.e. an element of $Σ_{t}$ ; hence $\overset{ˉ}{σ}$ is a labeling of $G_{t}$ .

F1given

2.1

Let a directed incidence slot of $G_{t}$ be given by a pattern $(σ_{1}, \dots, σ_{L})$ from $v_{0}$ , a copy bit, and visited vertices $v_{0}, \dots, v_{L}$ , and let $j \in J$ be such that $σ_{j}$ is a move along a slot $e = (v_{j - 1}, v_{j})$ . The coordinate $κ_{v_{0}, v_{j - 1}}$ ends at $v_{j - 1}$ and $κ_{v_{L}, v_{j}}$ ends at $v_{j}$ by definition. Since the canonical lift labels every pattern by its endpoint, $\overset{ˉ}{σ} (v_{0}) (κ_{v_{0}, v_{j - 1}}) = σ (v_{j - 1})$ and $\overset{ˉ}{σ} (v_{L}) (κ_{v_{L}, v_{j}}) = σ (v_{j})$ ; the copy bit does not alter the relation or these coordinates.

F1step 1.1algebra

3.1

Since $σ$ satisfies every edge of $G$ , the pair $(σ (v_{j - 1}), σ (v_{j}))$ lies in the relation of the slot $e$ in its orientation $(v_{j - 1}, v_{j})$ , whether or not $e$ is a loop; by step 2.1 the pair of views reads exactly this pair at position $j$ , so the slot of $G_{t}$ accepts $(\overset{ˉ}{σ} (v_{0}), \overset{ˉ}{σ} (v_{L}))$ . Position $j$ was an arbitrary member of the central window and the slot was arbitrary, so $\overset{ˉ}{σ}$ satisfies every slot of $G_{t}$ , and therefore $val (G_{t}) = 1$ when $val (G) = 1$ .

F1F2step 2.1∎

Remarks

The lift is a function of the base labeling and the explicit pattern list; it makes no choice. Repeated occurrences of one vertex in a pattern all receive the same symbol $σ$ of that vertex, which is why consistency across the central overlap is automatic here.
The converse direction is not claimed: satisfying labelings of $G_{t}$ need not be lifts. That gap is what the plurality decoding and collision analysis of the following items address.

Depends on

Used by

Powering preserves perfect satisfiability Lemma

Dependency tree · two levels

4 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 Lemma 18.31 part 2 (canonical assignment satisfies the powered instance). (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §1.2: UNSAT(G)=0 implies UNSAT(Gᵗ)=0, p. 5. (standard reference, not scraped)