CounterexampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-30

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 powered graph whose alphabet grows

Statement refuted

Local-view powering does not preserve the input alphabet on every graph and every positive parameter. The one-vertex graph below has base unsatisfaction $1 / 2$ , while its $t = 1$ local-view alphabet has size $2^{64}$ rather than $2$ .

Facts & Assumptions

[F1]

The universal claim under examination is that the local-view powering step keeps the input alphabet unchanged for every graph and every positive powering parameter. (False: graph powering alone keeps the alphabet fixed)

Counterexample

Given: Let $G$ have one vertex $v$ , base alphabet $Σ = {0, 1}$ , and two loop edges $e_{0}, e_{1}$ with relations $R_{e_{0}} = {(0, 0)}$ and $R_{e_{1}} = {(1, 1)}$ .

1.1givenalgebra

The only vertex labels are $0$ and $1$ . Label $0$ passes $e_{0}$ and fails $e_{1}$ ; label $1$ passes $e_{1}$ and fails $e_{0}$ . Thus every labeling violates exactly one of the two edges and $UNSAT (G) = 1 / 2$ . Each loop has two incidence slots, so the one-vertex graph is $d = 4$ regular.

2.1step 1.1algebra

Set $t = 1$ , so $R = t + ⌈ \sqrt{t} ⌉ = 2$ . In the local-view convention, a powered label assigns an element of $Σ$ to each length- $R$ lazy-step pattern, hence the pattern set has size $(2 d)^{R} = 8^{2} = 64$ and the view alphabet has size $∣ Σ ∣^{64} = 2^{64}$ .

3.1F1step 1.1step 2.1algebra∎

Since $2^{64} > 2 = ∣ Σ ∣$ , this explicit power does not preserve the alphabet, contradicting the universal assertion in [F1]. The witness uses a positive parameter and has the claimed base unsatisfaction $1 / 2$ ; it makes no claim that every graph or every parameter yields alphabet growth.

Depends on

False: graph powering alone keeps the alphabet fixed

Used by

Nothing in the library uses this result yet.

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

Arora and Barak, Computational Complexity: A Modern Approach, §18.5.1, Lemma 18.31, printed pp. 371–372 (standard reference, not scraped)