Radix-2 addition count:
ProvedFastFourierTransform.fftAddCount_eqComplex addition count of the radix-2 algorithm. Let be the addition counter of the butterfly cost model, and . Then for every
Each of the butterflies of a merge stage contributes two complex additions, and there are stages. The identity is exact and holds for as well.
import Mathlib import Definitions.Def_FastFourierTransform_opCount
namespace FastFourierTransform theorem fftAddCount_eq (p : ℕ) : fftAddCount p = p * 2 ^ p := by sorry end FastFourierTransform
Read-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 ,
where is the natural-number recursion , .
All quantities are natural numbers and all operations are natural-number arithmetic; is the natural-number power. There is no hypothesis on ; the case is included and reads . The statement is purely about this numerical recursion — it mentions no transform, no algorithm and no complex arithmetic — and it asserts an exact identity, not an asymptotic bound.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.