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 preserves perfect satisfiability

Statement

Let $G$ be a binary constraint graph over $Σ$ with $E (G) \neq \emptyset$ whose underlying graph is $d$ -regular in the adjacency-slot convention, let $t \geq 1$ , and let $G_{t}$ be its local-view powered graph (Constraint graph powering with local-view labels). If $val (G) = 1$ , then $val (G_{t}) = 1$ ; equivalently $UNSAT (G) = 0$ implies $UNSAT (G_{t}) = 0$ . This is perfect completeness; the quantitative lower bound for positive gaps is given, under its additional hypotheses, by Powering amplifies a small unsatisfaction gap. Perfect completeness does not assert $UNSAT (G_{t}) \geq UNSAT (G)$ .

Facts & Assumptions

Given: a $d$ -regular binary constraint graph $G$ over $Σ$ with at least one edge, an integer $t \geq 1$ , its powered graph $G_{t}$ , and the assertion $val (G) = 1$ .

[F1]

For a labeling $σ$ of $G$ and $E (G) \neq \emptyset$ , ${val}_{σ} (G)$ is the fraction of ordinary edges of $G$ satisfied by $σ$ ; hence ${val}_{σ} (G) = 1$ holds exactly when $σ$ satisfies every edge of $G$ (Constraint graph and labeling value).

[F2]

If $σ$ satisfies every edge of $G$ , its canonical lift $\overset{ˉ}{σ} (v) (π) : = σ (endpoint of the pattern π read from v)$ is a labeling of $G_{t}$ that satisfies every slot of $G_{t}$ ; consequently $val (G_{t}) = 1$ whenever $val (G) = 1$ (Canonical local views preserve perfect satisfiability).

[F3]

$val (G_{t}) = \max_{φ} {val}_{φ} (G_{t})$ where the maximum runs over all labelings of $G_{t}$ , and $G_{t}$ has at least one slot because $G$ has at least one slot (Constraint graph powering with local-view labels, Constraint graph and labeling value).

Proof

technique · direct

1.1

Since $val (G) = 1$ and $G$ is nonempty, there is a labeling $σ$ of $G$ with ${val}_{σ} (G) = 1$ , and by [F1] such a $σ$ satisfies every edge of $G$ .

F1F3given

2.1

By [F2] applied to the labeling of step 1.1, the canonical lift $\overset{ˉ}{σ}$ satisfies every slot of $G_{t}$ , so ${val}_{\overset{ˉ}{σ}} (G_{t}) = 1$ and hence $val (G_{t}) \geq 1$ ; since $val$ is a maximum of fractions, $val (G_{t}) = 1$ and $UNSAT (G_{t}) = 1 - val (G_{t}) = 0$ .

F2F3step 1.1∎

Remarks

The gap need not be monotone under powering: take one vertex with one ordinary loop whose relation is empty, so $d = 2$ and $UNSAT (G) = 1$ . At $t = 1$ the walk length is three and $J = {1, 2, 3}$ . Any move tests the empty relation and fails, while the all-hold patterns pass vacuously. Each step holds with probability $1 / 2$ , so every powered labeling has value $1 / 8$ and $UNSAT (G_{1}) = 7 / 8$ .
Nothing is assumed about $t$ beyond $t \geq 1$ , and no hypothesis on the powered labeling is needed: the lift is built from $σ$ with no choice, so the statement is itself choice-free.
The edgeless case is deliberately excluded here and is instead governed by the convention that an edgeless graph has value one and unsatisfiability zero (Constraint graph and labeling value); the degree-reduction map of Degree reduction by expander incidence clouds sends edgeless inputs to edgeless outputs, for which the powered graph is again empty.
The converse also holds for perfect satisfiability, even though a satisfying powered labeling need not be a canonical lift. If $φ$ satisfies $G_{t}$ , put $a (v) : = φ (v) (κ_{v, v})$ . For any oriented base edge $e = (u, w)$ , consider the length- $2 t + 1$ pattern that holds $t$ times at $u$ , traverses $e$ , then holds $t$ times at $w$ . Its central position $t + 1$ belongs to $J$ , and its test is exactly $(a (u), a (w)) \in R_{e}$ . Thus $a$ satisfies every base edge, including loops. The quantitative estimate Powering amplifies a small unsatisfaction gap concerns arbitrary, possibly imperfect powered labelings.

Depends on

Used by

A complete uniform graph gap-amplification step Theorem

Dependency tree · two levels

5 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, printed p. 373. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §1.2 (UNSAT(G)=0 implies UNSAT(Gᵗ)=0), printed p. 5. (standard reference, not scraped)