CounterexampleConstruction: AI-adaptedVerification: 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.

Duplicating constraints does not change UNSAT

Statement refuted

Duplicating every constraint of a CSP instance the same number of times strictly increases its unsatisfaction fraction (Repeating constraints amplifies the gap).

Facts & Assumptions

Given: the alphabet $Σ : = {0, 1}$ and the constraint graph $G$ on the single variable $x_{1}$ whose two edges are loops, the first carrying the relation $R_{1} : = {(0, 0), (1, 1)}$ and the second the empty relation $R_{2} : = \emptyset$ .

[F1]

A loop is a constraint on a repeated variable, it is satisfied by a labeling $σ$ exactly when $(σ (x_{1}), σ (x_{1})) \in R$ , and the value of a system is the fraction of listed constraints that are satisfied, duplicated constraints counting with multiplicity (Constraint graph and labeling value).

[F2]

The unsatisfaction fraction of a system is the minimum over labelings of the fraction of the listed constraints that the labeling violates; a system all of whose constraints are unsatisfiable by every labeling has $UNSAT = 1$ , and a system all of whose constraints are universally satisfied has $UNSAT = 0$ (Repeating constraints amplifies the gap, Constraint graph and labeling value).

Counterexample

technique · direct

1.1

The first loop carries $R_{1}$ , and $(0, 0), (1, 1) \in R_{1}$ , so every labeling of $x_{1}$ satisfies it; the second loop carries $R_{2} = \emptyset$ , so no labeling satisfies it. Hence the two-constraint list $G$ has ${UNSAT}_{σ} (G) = 1 / 2$ for every labeling $σ$ , and therefore $UNSAT (G) = 1 / 2$ .

F1F2algebra

1.2

For $r \geq 1$ let $G^{(r)}$ list each of the two loops $r$ times. Every labeling satisfies exactly the $r$ copies of the first loop and violates exactly the $r$ copies of the second, so ${UNSAT}_{σ} (G^{(r)}) = r / (2 r) = 1 / 2$ for every $σ$ , and the list has $2 r$ constraints.

F1algebra

2.1

Thus $UNSAT (G^{(r)}) = 1 / 2 = UNSAT (G)$ for every $r \geq 1$ : the repetition changes neither the value nor the unsatisfaction fraction, and in particular it never strictly increases it, so the statement refuted above fails at this witness.

step 1.1step 1.2F2∎

Depends on

Used by

Nothing in the library uses this result yet.

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

Irit Dinur, The PCP theorem by gap amplification, §1.5 and Definition 1.1, printed pp. 3-4. (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §18.5, printed p. 371. (standard reference, not scraped)