Fourier inversion for the DFT
ProvedFastFourierTransform.idft_dftFourier inversion. For , every signal and every sample index ,
Applying the inverse transform of length to the transform of length recovers the original samples exactly on the window . Nothing is claimed for , where never entered the transform. The proof rests on the orthogonality relation when and otherwise.
import Mathlib import Definitions.Def_FastFourierTransform_dft import Definitions.Def_FastFourierTransform_idft
namespace FastFourierTransform
theorem idft_dft (n : ℕ) (hn : 0 < n) (x : ℕ → ℂ) (m : ℕ) (hm : m < n) :
idft n (dft n x) m = x m := 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 with , every function from the natural numbers to the complex numbers, and every natural number with ,
Unfolded, the left-hand side is
i.e. the spectrum is formed first and then the inverse transform of length is applied to it at the index . The inner transform uses the negative sign in the exponent and no normalizing factor; the outer one uses the positive sign and the factor .
Both hypotheses are load-bearing in the sense of restricting the claim: nothing is asserted for , and nothing is asserted for output indices (where the right-hand side is a sample outside the transformed window). The recovery is exact: the claim is equality of complex numbers, not equality up to a constant factor or up to rounding. Note that the same normalization convention is fixed by the two definitions being composed — the factor sits entirely in the inverse transform.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.