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

A cloud rounding calculation

Example

Let $G$ be a binary constraint graph, let $G_{1}$ be its cloud graph as constructed by Degree reduction by expander incidence clouds, and let $τ$ be a labeling of the ports of $G_{1}$ . Suppose that $S = 10$ ports carry a label different from the decoded label of their original vertex, that $U_{i n t} = 4$ equality edges inside clouds are violated (counted with multiplicity), and that $U_{e x t} = 2$ external edges are violated. Then the bounds of Cloud violations control distance to plurality labels give $U_{i n t} \geq (7 / 20) \cdot 10 = 7 / 2$ and $U_{G} \leq U_{e x t} + S = 2 + 10 = 12$ for the number $U_{G}$ of ordinary edges of $G$ violated by the decoded labeling: the first is consistent with the integer value $4$ , and the second is an upper bound, so no equality and no stronger local bound is asserted. Passing from these counts to the unsatisfaction fractions of the $387$ -regular registered graph $G_{2}$ costs the constant factor of Degree reduction preserves unsatisfaction quantitatively.

Facts & Assumptions

Given: a binary constraint graph $G$ over the fixed alphabet $Σ$ , its cloud graph $G_{1}$ and registered graph $G_{2}$ , a labeling $τ$ of the ports of $G_{1}$ with plurality decoding $σ = D τ$ , and the counts $S = 10$ , $U_{i n t} = 4$ , $U_{e x t} = 2$ of the statement.

[F1]

If $S$ is the number of ports whose label differs from the decoded label of their vertex, then the violated equality edges inside the clouds and the violated ordinary edges of $G$ satisfy $U_{i n t} \geq \frac{7}{20} S$ and $U_{G} \leq U_{e x t} + S$ , where $U_{e x t}$ counts the violated external edges (Cloud violations control distance to plurality labels).

[F2]

The registered graph $G_{2}$ is $387$ -regular with $2 ∣ E (G) ∣$ vertices, and its unsatisfaction fraction is at least $1 / (387 K)$ times that of $G$ with $K = 20 / 7$ ; the additive $65$ ordinary loops and the overlay edges at every port are tautological, so the count $U_{G}$ of the previous item is a count of edges of $G$ and not of edges of $G_{2}$ (Degree reduction preserves unsatisfaction quantitatively, Degree reduction by expander incidence clouds).

Verification

technique · direct

1.1

The first inequality of [F1] with $S = 10$ gives $U_{i n t} \geq (7 / 20) \cdot 10 = 7 / 2$ , and the labelling has $U_{i n t} = 4$ , so the bound holds and its slack is $4 - 7 / 2 = 1 / 2$ .

F1algebra

1.2

The second inequality of [F1] with $U_{e x t} = 2$ and $S = 10$ gives $U_{G} \leq 2 + 10 = 12$ .

F1algebra

2.1

Both bounds are one-sided and the integers $U_{i n t} = 4$ and $U_{G} \in {0, \dots, 12}$ are compatible with them, so the numerical data are consistent; the example shows in particular that $S = 10$ ports of disagreement force at least $7 / 2$ (hence at least $4$ integer) internal violations and at most $12$ ordinary edge violations in $G$ , and nothing of the stronger form $U_{G} \leq U_{e x t}$ or $U_{i n t} \geq S$ may be inferred from these bounds.

step 1.1step 1.2algebra

3.1

The comparison with the registered graph is a constant rescaling and not a count identity: by [F2] the fraction of violated edges of $G_{2}$ is at least $\frac{7}{7740}$ times the fraction of violated ordinary edges of $G$ , and the tautological overlay edges at the ports do not contribute violations in either direction, so the counts $U_{i n t}$ , $U_{e x t}$ and $U_{G}$ above are statements about the cloud graph $G_{1}$ and the original graph $G$ .

F2step 2.1algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

9 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, §4 Definition 4.1 and Lemma 4.1, printed pp. 12-14. (standard reference, not scraped)
Arora and Barak, Computational Complexity: A Modern Approach, §18.5, printed pp. 371-373. (standard reference, not scraped)