CounterexampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)

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.

The radix-two split fails for odd $N$

Statement refuted

False claim: for every integer $N \geq 2$ , the even/odd split of the classes of $Z / N Z$ into the images of $r \mapsto 2 r$ and $r \mapsto 2 r + 1$ partitions the group into two disjoint sets of size $N / 2$ , so that the radix-two factorisation of The radix-two even/odd factorisation of the DFT reduces the $N$ -point transform to two transforms of length $N / 2$ ; equivalently, that reduction applies to every length $N \geq 2$ .

The claim fails for $N = 3$ : doubling permutes the three classes of $Z / 3 Z$ , so the "even" classes are all of $Z / 3 Z$ and the "odd" classes are all of $Z / 3 Z$ as well; the two attempted index sets are not disjoint and have no length $M = N / 2 = 3 / 2$ behind them. This says nothing against direct evaluation of the three-point transform, which is a finite sum like any other.

Facts & Assumptions

Given: The classes of $Z / 3 Z$ and the maps $δ, ε : Z / 3 Z \to Z / 3 Z$ defined by $δ (r) : = [2 r]_{3}$ and $ε (r) : = [2 r + 1]_{3}$ ; the false claim of the Statement refuted section; and the reduction hypothesis $N = 2 M$ of the radix-two step.

[F1]

In $Z / 3 Z$ addition and multiplication are the operations of Addition and multiplication on $Z / n$ by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} [b]_{n} = [a b]_{n}$ : $[u] + [v] = [u + v]$ and $[u] \cdot [v] = [u v]$ , and classes are equal exactly when the representatives are congruent modulo $3$ (The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[F2]

The radix-two step of The radix-two even/odd factorisation of the DFT is stated for $M \geq 1$ and $N = 2 M$ : its even and odd parts have domain $Z / M Z$ , and the second identity uses the twiddle factor $e^{- 2 π i (k + M) / N} = - e^{- 2 π i k / N}$ because $2 π i M / N = π i$ ( $\exp (x + i y) = e^{x} (\cos y + i \sin y)$ , $∣ \exp (x + i y) ∣ = e^{x}$ , and $e^{i π} + 1 = 0$ , $\ker (\exp) = 2 π i Z$ , and $\exp z = \exp w$ exactly when $z - w \in 2 π i Z$ ).

[F3]

The recursion of The recursive radix-two fast Fourier transform is defined only for $N = 2^{m}$ , $m \in N$ , and each level halves the length.

[L1]

In $Z / 3 Z$ the class $[2]$ satisfies $[2] \cdot [2] = [4] = [1]$ , so multiplication by $[2]$ is its own inverse and hence a bijection of the three-element group. [F1]

[L2]

The claim being refuted is the universal statement of the Statement refuted section, applied at $N = 3$ .

Counterexample

technique · direct

1.1F1L1

The doubling map on $Z / 3 Z$ : $δ ([0]) = [2 \cdot 0] = [0]$ , $δ ([1]) = [2]$ , $δ ([2]) = [4] = [1]$ , so $δ$ is the transposition of the classes $[1]$ and $[2]$ fixing $[0]$ ; in particular $δ$ is a bijection of $Z / 3 Z$ onto itself, with inverse $δ$ itself, as multiplication by $[2]$ is involutive by [L1]. The image of $δ$ is therefore all of $Z / 3 Z$ , not a subset of size $3 / 2$ .

1.2F2F3

The second branch of the radix-two combine uses $e^{- 2 π i (k + M) / N} = - e^{- 2 π i k / N}$ , where $M / N = 1 / 2$ ; at $N = 3$ the quantity $M = 3 / 2$ is not an integer, so the factor $e^{- π i} = - 1$ has no interpretation as a twiddle factor of an integer-length subproblem, and the recursion of [F3] has no level corresponding to length $3 / 2$ .

2.1F1step 1.1

The translate $ε$ : since $ε (r) = [2 r + 1] = δ (r) + [1]$ and translation by $[1]$ is a bijection of $Z / 3 Z$ , $ε$ is a bijection as well; explicitly $ε ([0]) = [1]$ , $ε ([1]) = [0]$ , $ε ([2]) = [2]$ , so its image is again all of $Z / 3 Z$ .

3.1F1step 1.1step 2.1

Thus the two attempted index sets are each the whole group: they intersect in every class and their union is $Z / 3 Z$ , not the disjoint union of two $3 / 2$ -element sets. No two-coset decomposition with parts of size $M = 3 / 2$ exists, and no integer $M$ satisfies $2 M = 3$ .

4.1step 1.1step 1.2step 2.1step 3.1L2∎

The false claim [L2] asserted a partition into two disjoint sets of size $N / 2$ and a reduction to two length- $N / 2$ transforms for every $N \geq 2$ . At $N = 3$ both attempted index sets are all of $Z / 3 Z$ by steps 1.1, 2.1 and 3.1, and $N / 2$ is not an integer by step 1.2; the claim therefore fails. This is a statement only about the algorithm's length hypothesis: direct evaluation of the three-point transform remains well defined and unaffected.

Remarks

Scope of the witness. It shows that the radix-two reduction needs $N$ even: for odd $N$ , the attempted even and odd images do not form a partition. Other algorithms for odd lengths are outside this counterexample.
Domains of doubling. For $N = 2 M$ , doubling from $Z / M Z$ into $Z / N Z$ is injective, as the factorisation lemma proves. For odd $N = 2 q + 1$ , $2 (q + 1) = N + 1$ , so $[q + 1]_{N}$ is the multiplicative inverse of $[2]_{N}$ . Thus doubling on $Z / N Z$ is a permutation of the whole group; it cannot give one half of a partition.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

42 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

MIT 18.310 lecture 23, The Finite Fourier Transform and the Fast Fourier Transform Algorithm (course page) (standard reference, not scraped)
Michael E. Taylor, Fourier Analysis, Distributions, and Constant-Coefficient Linear PDE (author PDF) (standard reference, not scraped)

The radix-two split fails for odd NN