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

Nonconstructive expanders suffice for uniform reductions

Statement

False statement: every choice of one bounded-degree expander on each positive vertex count automatically supplies a polynomial-time uniform adjacency generator for the chosen family.

Facts & Assumptions

Given: the objects and hypotheses in the statement above.

[F1]

For the regular multigraph and spectral conventions in the stated convention, put $α = ∥ M ∣_{1^{⊥}} ∥$ . For $n \geq 2$ order the eigenvalues $1 = μ_{1} \geq μ_{2} \geq \dots \geq μ_{n}$ , counting multiplicity, and put $γ = 1 - μ_{2}$ . Thus $α = \max_{j \geq 2} ∣ μ_{j} ∣$ , which also controls negative eigenvalues. Write $cut (S) = \sum_{u \in S, v \notin S} A_{u v}$ and $\partial_{V} S = {v \notin S : A_{u v} > 0 for some u \in S}$ . Normalized edge expansion and external vertex expansion are $h = \min_{0 < ∣ S ∣ \leq n / 2} \frac{cut (S)}{d ∣ S ∣}, h_{V} = \min_{0 < ∣ S ∣ \leq n / 2} \frac{∣ \partial_{V} S ∣}{∣ S ∣} .$ For $n = 1$ , put $α = 0$ and leave $μ_{2}, γ, h, h_{V}$ undefined; cut-expansion assertions are vacuous. A bounded-degree family is an expander family when its normalized edge expansion has a positive uniform lower bound for $n \geq 2$ . Polynomial-time constructibility means a uniform algorithm outputs the adjacency list in time polynomial in $n$ ; neighbor computation in time polynomial in $\log n$ is a stronger requirement. (Spectral edge and vertex expansion).

[F2]

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$ . (Explicit polynomial time constant degree expanders exist).

Refutation

1.1F2algebra

Let $H_{N}$ be the explicit degree- $128$ family with nontrivial norm at most $ρ_{0} < 1$ . For $N \geq 2$ , let $P_{N}$ be the permutation matrix interchanging vertices one and two and fixing the others. The two matrices $C_{N}^{0} = A (H_{N}) + 128 I$ and $C_{N}^{1} = A (H_{N}) + 128 P_{N}$ are symmetric degree- $256$ adjacency matrices. They differ in entry $(1, 2)$ . On mean-zero vectors their normalized operator norms are at most $η = (ρ_{0} + 1) / 2 < 1$ , since both $I$ and $P_{N}$ have norm one and preserve constants.

2.1F1step 1.1

Both families are expanders in the cut sense too: for any $S$ of size at most half, the centered indicator has energy at least $(1 - η) ∥ 1_{S} - (∣ S ∣ / N) 1 ∥^{2}$ , so its normalized cut ratio is at least $(1 - η) (1 - ∣ S ∣ / N) \geq (1 - η) / 2$ . This calculation applies to either choice at each size.

3.1step 1.1step 2.1algebra∎

Enumerate all graph-output programs with explicit polynomial-in- $N$ clocks. At stage $i \geq 0$ use size $N = i + 2$ and run the corresponding clocked program there. If its output, parsed as an adjacency matrix, equals $C_{N}^{0}$ , choose $C_{N}^{1}$ ; otherwise choose $C_{N}^{0}$ . Fix the singleton output arbitrarily to degree $256$ loops. Every selected graph expands with the same constants, yet every polynomial-time generator differs from the chosen graph at its assigned size, even if it uses a different ordering of adjacency slots. Thus the chosen family has no polynomial-time uniform generator.

Depends on

Used by

Nonconstructive expanders suffice for uniform reductions Counterexample

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

Hoory–Linial–Wigderson, Expander Graphs and Their Applications, May 2006 draft; §2.1 Definition2.3, p19; Dinur §2.1 Lemma2.1 explicitly requires constructibility. (standard reference, not scraped)