TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 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.

Degree reduction preserves unsatisfaction quantitatively

Statement

Let $G$ be a binary constraint graph over the fixed alphabet $Σ$ with $E (G) \neq \emptyset$ , and let $G_{2} = R_{\deg} (G)$ be its degree-reduced graph as constructed by Degree reduction by expander incidence clouds. Then $G_{2}$ is $387$ -regular over the same alphabet, has $2 ∣ E (G) ∣$ vertices and exactly $387 ∣ E (G) ∣$ ordinary edges, is produced from the explicit encoding of $G$ by a deterministic algorithm in polynomial time, and with $K = 20 / 7$ its unsatisfiability satisfies perfect completeness and the quantitative bound $UNSAT (G_{2}) \geq \frac{UNSAT (G)}{387 K} = \frac{7}{7740} UNSAT (G) .$ Consequently $R_{\deg}$ , with the empty output on edgeless inputs, is a complete uniform gap-preserving reduction in the sense of Complete uniform gap-preserving CSP reductions with output alphabet $Σ$ , output degree bound $387$ , blowup $387$ and gap map $g (ε) = ε / (387 K)$ .

Facts & Assumptions

Given: a binary constraint graph $G$ over the fixed alphabet $Σ$ with $m = ∣ E (G) ∣ \geq 1$ , its cloud graph $G_{1}$ and its degree-reduced graph $G_{2} = R_{\deg} (G)$ , and $K = 20 / 7$ .

[F1]

The full preprocessing graph $G_{2}$ of a graph with $m > 0$ edges has $2 m$ vertices, degree $387$ and $387 m$ ordinary edges over the same alphabet; it has loops at every vertex and $α (G_{2}) \leq ρ_{2} < 1$ . With $K = 20 / 7$ and $c = 1 / (129 K)$ , $\frac{129 c}{387} UNSAT (G) \leq UNSAT (G_{2}) \leq \frac{UNSAT (G)}{387} .$ For every port labeling $τ$ , ${UNSAT}_{τ} (G_{2}) = \frac{129}{387} {UNSAT}_{τ} (G_{1})$ and ${UNSAT}_{D τ} (G) \leq 387 K {UNSAT}_{τ} (G_{2})$ . Construction and plurality decoding take polynomial time, and the edgeless convention has unsatisfiability zero (Constraint expander overlay).

[F3]

The degree-reduction map $R_{\deg}$ is deterministic: on an edgeless input it outputs the empty graph over $Σ$ , and otherwise it outputs the graph $G_{2}$ of the cloud-and-overlay construction, listing the explicit expander adjacency lists, copying the $2 m$ relation tables and adding the $387 m$ slots of the overlay, in time polynomial in the encoding length of the input; the decoding map $D$ is the fixed plurality decoding of the construction (Degree reduction by expander incidence clouds).

[F4]

A complete uniform gap-preserving reduction with output alphabet $Σ^{'}$ , output degree bound $d^{'}$ , blowup $C$ and gap map $g$ satisfies: $∣ E (R (G)) ∣ \leq C ∣ E (G) ∣$ and $∣ V (R (G)) ∣ \leq C ∣ E (G) ∣$ when $E (G) \neq \emptyset$ ; edgeless inputs go to edgeless outputs; $UNSAT (G) = 0$ implies $UNSAT (R (G)) = 0$ ; $UNSAT (R (G)) \geq g (UNSAT (G))$ with $g$ nondecreasing, $g (0) = 0$ and $g (ε) > 0$ for $ε > 0$ ; and $R$ runs in polynomial time (Complete uniform gap-preserving CSP reductions).

Proof

technique · direct

1.1

By [F3] the map is deterministic and polynomial time, and by [F1] its output is $387$ -regular over $Σ$ with $2 m$ vertices and $387 m$ ordinary edges. For $m \geq 1$ these counts satisfy $∣ E (G_{2}) ∣ = 387 m \leq 387 ∣ E (G) ∣$ and $∣ V (G_{2}) ∣ = 2 m \leq 387 ∣ E (G) ∣$ , the vertex bound because $2 \leq 387$ .

F1F3algebra

1.2

Perfect completeness: if $UNSAT (G) = 0$ then the second inequality of [F1] gives $UNSAT (G_{2}) \leq UNSAT (G) / 387 = 0$ , and unsatisfiability is nonnegative, so $UNSAT (G_{2}) = 0$ . The edgeless case is the empty-output convention of [F3].

F1F3

1.3

For the quantitative bound, let $τ$ be any labeling of $G_{2}$ , decoded to $σ = D τ$ on $G$ . By [F1], ${UNSAT}_{D τ} (G) \leq 387 K {UNSAT}_{τ} (G_{2})$ , and by the definition of the minimum over labelings, $UNSAT (G) \leq {UNSAT}_{D τ} (G)$ . Hence $UNSAT (G) \leq 387 K {UNSAT}_{τ} (G_{2})$ for every $τ$ , and minimizing the right side over $τ$ gives $UNSAT (G) \leq 387 K UNSAT (G_{2}), that is, UNSAT (G_{2}) \geq \frac{UNSAT (G)}{387 K} .$

F1algebra

2.1

The gap map $g (ε) = ε / (387 K)$ is nondecreasing, satisfies $g (0) = 0$ and is positive for $ε > 0$ , and together with steps 1.1, 1.2 and 1.3 it makes $R_{\deg}$ , with the empty output on edgeless inputs, a complete uniform gap-preserving reduction with output alphabet $Σ$ (fixed), output degree bound $387$ , blowup $387$ and that gap map, in the sense of [F4]. For the edgeless input both the input and the output have unsatisfiability zero, so the gap inequality holds trivially there.

F3F4step 1.1step 1.2step 1.3∎

Remarks

The constant is not improvable by this proof: the factor $387 K = 7740 / 7$ is exactly the loss accumulated by the cloud rounding inequality $U_{G} \leq U_{e x t} + (2 / h_{0}) U_{i n t}$ and the uniform edge rescaling from $129 m$ to $387 m$ slots in [F1]. Later items absorb it into their own constants, which is why A complete uniform graph gap-amplification step carries a smaller $β$ .
Fact [F2] is declared because the published derivation of the decoding inequality in [F1] runs through the cloud rounding bound; the page records that bound as its own interface so that the code and tester branches can cite it.

Depends on

Used by

A cloud rounding calculation Example
A complete uniform graph gap-amplification step Theorem

Dependency tree · two levels

10 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, §1.3 Lemma 1.7 and §4 Corollary 4.3, pp. 6 and 15. (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1: preprocessing to a regular expander, author-hosted draft. (standard reference, not scraped)