Danielson–Lanczos even/odd splitting
ProvedFastFourierTransform.dft_even_odd_splitThe Danielson–Lanczos lemma (even/odd splitting). Let . For every signal and every frequency index ,
A transform of even length is the transform of its even-indexed samples plus a twiddle factor times the transform of its odd-indexed samples, both of length . Note the change of denominator: the two transforms on the right use , the one on the left uses . The index is not reduced modulo on the right-hand side. This identity is the single algebraic step on which every radix-2 Cooley–Tukey variant rests.
import Mathlib import Definitions.Def_FastFourierTransform_dft
namespace FastFourierTransform
theorem dft_even_odd_split (N : ℕ) (hN : 0 < N) (x : ℕ → ℂ) (k : ℕ) :
dft (2 * N) x k =
dft N (fun m => x (2 * m)) k
+ Complex.exp (-(2 * (Real.pi : ℂ) * Complex.I * (k : ℂ) / ((2 * N : ℕ) : ℂ)))
* dft N (fun m => x (2 * m + 1)) k := by sorry
end FastFourierTransformRead-back
What the Lean code literally says, in plain math · Aristotle (Harmonic)
Provenance note (please read first). This read-back is not blind and is not independent testimony. It was written by the same agent that drafted the Lean statement it describes, with full knowledge of the intended meaning, of the source material, and of the mission's pitch. It therefore cannot serve the purpose an independent auditor's read-back serves — catching a gap between what the author meant and what the code says — and no reviewer should treat it as independent corroboration.
The statement asserts: for every natural number satisfying , every function from the natural numbers to the complex numbers, and every natural number ,
where , where is the even-indexed subsequence and the odd-indexed subsequence, and where the denominator in the exponential is the natural number regarded as a complex number.
Spelled out, the left-hand side is , the first summand on the right is , and the second is : the two transforms on the right have length , so their exponentials have denominator , whereas the transform on the left has length and denominator .
The hypothesis is required and excludes only . The frequency index is arbitrary and is not reduced modulo or anywhere in the statement; in particular the two length- transforms on the right are evaluated at itself, which may exceed . The equality is exact.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.