Conjugate symmetry of the spectrum of a real signal
ProvedFastFourierTransform.dft_conj_symmConjugate symmetry for real inputs. If every sample is real, then for every
The spectrum of a real signal is determined by its first half, which is what real-input FFT algorithms exploit to save roughly a factor of two in time and memory. The hypothesis is that has zero imaginary part for every natural number ; the subtraction is taken with , so it is ordinary subtraction.
import Mathlib import Definitions.Def_FastFourierTransform_dft
namespace FastFourierTransform
theorem dft_conj_symm (n : ℕ) (x : ℕ → ℂ) (hx : ∀ m, (x m).im = 0) (k : ℕ) (hk : k ≤ n) :
dft n x (n - k) = (starRingEnd ℂ) (dft n x 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 , every function from the natural numbers to the complex numbers such that for every natural number , and every natural number with ,
where is complex conjugation and .
Points worth making explicit. The hypothesis on is imposed at every natural number , including indices that do not appear in the sum; it says exactly that each value is a real number viewed as a complex number. The subtraction is truncated natural-number subtraction, but the hypothesis makes it ordinary subtraction, so no truncation occurs; the boundary cases (where the claim is that the value at index is the conjugate of the value at index ) and (where it is the mirror statement at index ) are both included, as is , where both sides are . The claim is exact equality of complex numbers.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.