TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

Correctness of the recursive radix-two FFT

Statement

Let $m \in N$ , $N = 2^{m}$ and $f \in C^{Z / N}$ . Then

${FFT}_{m} (f) (k) = X_{k} (f) for every k \in Z,$

where $X$ is the unnormalised $N$ -point discrete Fourier transform of The unnormalised engineering DFT and its conversion to the unitary transform. Equivalently ${FFT}_{m} (f) = 2^{m / 2} F_{N} f$ for the unitary transform of The unitary discrete Fourier transform on $Z / N Z$ ; consequently the algorithm returns the unitary transform after the single rescaling $2^{- m / 2}$ , and it does so for every input of length $2^{m}$ . Correctness is separate from speed: the operation count is the subject of a different theorem, and no floating-point or stability claim is made here.

Facts & Assumptions

Given: The family ${FFT}_{m}$ of The recursive radix-two fast Fourier transform, the unnormalised transform $X$ and the unitary transform $F_{N}$ , and the statement $P (m)$ : for every $f \in C^{Z / 2^{m}}$ and every $k \in Z$ , ${FFT}_{m} (f) (k) = X_{k} (f)$ .

[F1]

Definition of the recursion: ${FFT}_{0} = i d$ on $C^{Z / 1}$ , and for $m \geq 1$ , with $M = 2^{m - 1}$ , $f \in C^{Z / 2^{m}}$ and even/odd parts $e, o \in C^{Z / M}$ , one has ${FFT}_{m} (f) (k) = {FFT}_{m - 1} (e) (k) + e^{- 2 π i k / 2^{m}} {FFT}_{m - 1} (o) (k)$ for every $k \in Z$ , the subproblem outputs being extended $M$ -periodically (The recursive radix-two fast Fourier transform).

[F2]

Radix-two factorisation: with $M \geq 1$ , $2 M$ in place of $N$ , and even/odd parts $e, o$ of $f$ , $X_{k} (f) = X_{k} (e) + e^{- 2 π i k / (2 M)} X_{k} (o)$ and $X_{k + M} (f) = X_{k} (e) - e^{- 2 π i k / (2 M)} X_{k} (o)$ for every $k \in Z$ (The radix-two even/odd factorisation of the DFT).

[F3]

The unnormalised transform at length $L$ is $X_{k} (u) = \sum_{x = 0}^{L - 1} u ([x]_{L}) e^{- 2 π i k x / L}$ and satisfies $X_{k} (u) = L^{1 / 2} (F_{L} u) (k)$ ; at $L = 1$ , $X_{0} (u) = u ([0]_{1})$ because $e^{0} = 1$ (The unnormalised engineering DFT and its conversion to the unitary transform, The unitary discrete Fourier transform on $Z / N Z$ ).

[L1]

Induction: a property holding at $0$ and inherited by successors holds at every natural (The principle of mathematical induction); $2^{0} = 1$ and $2^{m} = 2 \cdot 2^{m - 1}$ for $m \geq 1$ (Laws of integer exponents, The natural numbers $N$ (von Neumann)).

[L2]

Rational powers: $2^{m} > 0$ , $(2^{m})^{1 / 2} = 2^{m / 2}$ and $2^{m / 2} \cdot 2^{- m / 2} = 1$ (Rational powers $a^{r}$ of a positive base, Laws of rational exponents, claims 1, 2 and 5).

Proof

technique · induction on $m$

1.1baseF1F3L1

Base case $m = 0$ : the group $Z / 1 Z$ has the single class $[0]_{1}$ , ${FFT}_{0} = i d$ , and $X_{0} (f) = f ([0]_{1}) e^{0} = f ([0]_{1})$ while $X_{k} (f) = X_{k m o d 1} (f) = X_{0} (f)$ for every integer $k$ because the length-one transform is $1$ -periodic; hence ${FFT}_{0} (f) (k) = f ([0]_{1}) = X_{k} (f)$ for every $k$ .

1.2ih

Inductive hypothesis: fix $m \geq 0$ and assume $P (m)$ , that is ${FFT}_{m} (g) (k) = X_{k} (g)$ for every $g \in C^{Z / 2^{m}}$ and every integer $k$ .

1.3givenF1L1

Successor data: for the induction step from $m$ to $m + 1$ , put $N : = 2^{m + 1}$ and $M : = 2^{m}$ , and let $f \in C^{Z / N}$ have even and odd parts $e, o \in C^{Z / M}$ , so $N = 2 M$ and $M \geq 1$ .

2.1step 1.2step 1.3F1F2L1

Successor case: by [F1], ${FFT}_{m + 1} (f) (k) = {FFT}_{m} (e) (k) + e^{- 2 π i k / 2^{m + 1}} {FFT}_{m} (o) (k)$ ; the induction hypothesis of step 1.2 applies to $e, o \in C^{Z / 2^{m}}$ and every integer $k$ , giving ${FFT}_{m} (e) (k) = X_{k} (e)$ and ${FFT}_{m} (o) (k) = X_{k} (o)$ . Substituting these equalities and applying the first radix-two factorisation [F2] with $N = 2^{m + 1} = 2 M$ yields ${FFT}_{m + 1} (f) (k) = X_{k} (f)$ for every $k \in Z$ , which is $P (m + 1)$ .

3.1discharge-induction: step 2.1F1F3L1L2step 1.1step 2.1∎

By induction [L1], $P (m)$ holds for every $m \in N$ , which is the first display. For the equivalent form, [F3] gives $X_{k} (f) = 2^{m / 2} (F_{2^{m}} f) (k)$ since $\sqrt{2^{m}} = 2^{m / 2}$ by [L2]; hence ${FFT}_{m} (f) = 2^{m / 2} F_{N} f$ , and multiplying both sides by $2^{- m / 2}$ recovers the unitary transform from the output, so the rescaling $2^{- m / 2}$ is the only normalisation step needed.

Remarks

Use of the induction hypothesis. In the step from $m$ to $m + 1$ , the hypothesis is applied at level $m$ to the even and odd parts. The combine is the radix-two factorisation, and the base case is the identity transform at length $1$ .
Correctness and the operation model are independent. Nothing in this proof counts operations or inspects the resources used by the recursion; conversely the complexity theorem does not reprove the identity. The two statements share only the definition of the algorithm and the factorisation lemma.

Depends on

Used by

The four-point radix-two FFT executed in full Example

Dependency tree · two levels

56 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)