ExampleConstruction: 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 four-point radix-two FFT executed in full

Example

For $N = 4 = 2^{2}$ and $f = (f_{0}, f_{1}, f_{2}, f_{3}) \in C^{Z / 4}$ , the recursion of The recursive radix-two fast Fourier transform takes the even part $e = (f_{0}, f_{2})$ and the odd part $o = (f_{1}, f_{3})$ . The two length-two unnormalised transforms are $E = (f_{0} + f_{2}, f_{0} - f_{2})$ and $O = (f_{1} + f_{3}, f_{1} - f_{3})$ , extended $2$ -periodically, and the combine with twiddle factors $e^{- 2 π i k / 4} = (- i)^{k}$ gives

$X_{0} = f_{0} + f_{1} + f_{2} + f_{3}, X_{2} = f_{0} - f_{1} + f_{2} - f_{3},$

$X_{1} = f_{0} - i f_{1} - f_{2} + i f_{3}, X_{3} = f_{0} + i f_{1} - f_{2} - i f_{3} .$

These agree with direct evaluation of $X_{k} = \sum_{x = 0}^{3} f_{x} e^{- 2 π i k x / 4}$ , as Correctness of the recursive radix-two FFT requires, and the operation count for this length is $16 = 2 \cdot 2 \cdot 4$ complex additions and multiplications in the model of The radix-two FFT uses $O (N \log_{2} N)$ complex arithmetic operations, which is the bound $2 N \log_{2} N$ of that theorem at $N = 4$ (here $\log_{2} 4 = 2$ because $4 = 2^{2}$ ).

Facts & Assumptions

Given: The function $f \in C^{Z / 4}$ with values $f_{0} = f ([0]), f_{1} = f ([1]), f_{2} = f ([2]), f_{3} = f ([3])$ , its even part $e = (f_{0}, f_{2}) \in C^{Z / 2}$ and odd part $o = (f_{1}, f_{3}) \in C^{Z / 2}$ , and the length-two transforms $E = {FFT}_{1} (e)$ , $O = {FFT}_{1} (o)$ extended $2$ -periodically.

[F1]

The recursion of The recursive radix-two fast Fourier transform: ${FFT}_{0} = i d$ and, for $m \geq 1$ , ${FFT}_{m} (f) (k) = E (k) + e^{- 2 π i k / 2^{m}} O (k)$ with $E, O$ the recursively computed length- $2^{m - 1}$ transforms of the even and odd parts; the even and odd parts of a length- $4$ function are $e = (f_{0}, f_{2})$ and $o = (f_{1}, f_{3})$ (The radix-two even/odd factorisation of the DFT).

[F2]

The unnormalised length- $L$ transform is $X_{k} (u) = \sum_{x = 0}^{L - 1} u ([x]_{L}) e^{- 2 π i k x / L}$ , and at length $2$ it is $X_{k} (u) = u ([0]) + u ([1]) e^{- π i k} = u ([0]) + (- 1)^{k} u ([1])$ ; correctness of the recursion is Correctness of the recursive radix-two FFT and the operation bound is The radix-two FFT uses $O (N \log_{2} N)$ complex arithmetic operations (The unnormalised engineering DFT and its conversion to the unitary transform).

[L1]

Exponential values: $e^{0} = 1$ , $e^{- π i / 2} = - i$ , $e^{- π i} = - 1$ , $e^{- 3 π i / 2} = 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$ , The complex exponential by its power series); hence the twiddles $e^{- 2 π i k / 4}$ for $k = 0, 1, 2, 3$ are $1, - i, - 1, i$ .

[L2]

Field arithmetic in $C$ ( $C = R [x] / (x^{2} + 1)$ is a field, every element is uniquely $a + b i$ , and every nonzero element has inverse $(a - b i) / (a^{2} + b^{2})$ ); $\log_{2} 4 = 2$ because $4 = 2^{2}$ and $\log_{2} x = \log x / \log 2$ with $\log (\exp y) = y$ (The logarithm to a positive base other than one, The natural logarithm as the inverse of the exponential function).

Verification

technique · direct

1.1F1F2L1

The length-two transforms: by [F2] with $L = 2$ and [L1], $E (0) = f_{0} + f_{2}$ , $E (1) = f_{0} - f_{2}$ , $O (0) = f_{1} + f_{3}$ , $O (1) = f_{1} - f_{3}$ , extended $2$ -periodically (so $E (2) = E (0)$ , $E (3) = E (1)$ , and likewise for $O$ ).

2.1F1L1L2step 1.1

The combine at even $k$ : ${FFT}_{2} (f) (0) = E (0) + 1 \cdot O (0) = f_{0} + f_{1} + f_{2} + f_{3}$ and ${FFT}_{2} (f) (2) = E (2) - O (2) = f_{0} + f_{2} - f_{1} - f_{3}$ , using $e^{0} = 1$ and $e^{- π i} = - 1$ from [L1]. At odd $k$ : ${FFT}_{2} (f) (1) = E (1) + (- i) O (1) = f_{0} - i f_{1} - f_{2} + i f_{3}$ and ${FFT}_{2} (f) (3) = E (3) + i O (3) = f_{0} + i f_{1} - f_{2} - i f_{3}$ , using $e^{- π i / 2} = - i$ and $e^{- 3 π i / 2} = i$ from [L1]. These are the four displayed values.

3.1F2L1L2step 2.1

Direct evaluation: $X_{k} = \sum_{x = 0}^{3} f_{x} e^{- 2 π i k x / 4}$ gives, by [L1] and [L2], $X_{0} = f_{0} + f_{1} + f_{2} + f_{3}$ , $X_{1} = f_{0} - i f_{1} - f_{2} + i f_{3}$ , $X_{2} = f_{0} - f_{1} + f_{2} - f_{3}$ , $X_{3} = f_{0} + i f_{1} - f_{2} - i f_{3}$ ; these agree with step 2.1, as Correctness of the recursive radix-two FFT requires.

4.1L2F2step 1.1step 2.1step 3.1∎

Operation count: in the model of The radix-two FFT uses $O (N \log_{2} N)$ complex arithmetic operations, $T_{0} = 0$ , $T_{1} = 2 \cdot 2 = 4$ and $T_{2} = 2 T_{1} + 2 \cdot 2^{2} = 8 + 8 = 16$ ; the bound of that theorem is $T_{2} \leq 2 m 2^{m} = 2 \cdot 2 \cdot 4 = 16$ , and it is attained here, so the four-point recursion performs 16 complex multiplications and additions, which is $2 N \log_{2} N$ at $N = 4$ by [L2]. All four values of the transform and the count are therefore verified; the merge exercises the base case $m = 0$ implicitly through the two length-two transforms.

Remarks

Which level does what. The two length-two transforms are the calls at level $m = 1$ ; each of them in turn calls the length-one identity at level $0$ , so the example exercises both the base case and both branches of the combine. The mirror decimation-in-frequency form of Taylor's (12.2)-(12.7) computes the same four values by splitting the input into halves rather than into even and odd coefficients.
No numerical claim. The computation is exact over $C$ and says nothing about floating-point accuracy, the cost of evaluating the twiddle factors, or the cost of the index bookkeeping; those are outside the operation model of the complexity theorem.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

62 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

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