CorollaryStatement: AI-adaptedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-07

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.

Explicit polynomial time constant degree expanders exist

Statement

There is a uniform polynomial-time algorithm producing, for each positive vertex count $N$ , a degree- $128$ expander $H_{N}$ with absolute nontrivial norm at most $1 - 49 / 1638400$ . The output has $128 N$ adjacency slots; its bit-time cost is polynomial in $N$ .

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

For every integer $N \geq 1$ there is a polynomial-time constructible reverse-paired $128$ -regular multigraph $H_{N}$ on exactly $N$ vertices with $α (H_{N}) \leq ρ_{0} : = 1 - \frac{49}{1638400} < 1.$ For $N \geq 2$ every $S$ satisfies $cut (S) \geq (7 / 10) \min (∣ S ∣, N - ∣ S ∣)$ . Every vertex has loops. (Expander size adjustment and laziness).

Proof

1.1F1

Apply the all-size construction at the given $N$ . Its bound is independent of $N$ and is strictly smaller than one. For $N \geq 2$ its unnormalized expansion is at least $7 / 10$ , so normalized expansion is at least $7 / 1280$ .

2.1F1step 1.1∎

The construction explicitly lists $128$ destinations at each of the $N$ vertices and runs in polynomial bit time. The singleton output has only loops and satisfies the zero-space spectral convention. Endpoint names require logarithmically many bits, so the adjacency-slot count alone is not a claim of linear bit time.

Depends on

Expander size adjustment and laziness

Used by

Nonconstructive expanders suffice for uniform reductions False statement

Dependency tree · two levels

3 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; §2.1 Lemma2.1, p8, instantiated by preceding construction. (standard reference, not scraped)