Bluestein chirp identity for the mission Fourier convention
ProvedBitDFT.bluestein_middle_identitycomplexity-theoryfourier-transforminteger-multiplication
For a nonzero complex number and a finite complex array , the chirp-weighted sum at coordinate equals the Fourier sum with kernel :
This is the algebraic step that converts a finite-precision DFT construction into a middle-convolution computation. It imposes no root-of-unity hypothesis; that is supplied when the identity is specialized to a DFT.
Preamble
import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.GroupWithZero.Units.Lemmas import Mathlib.Tactic.Ring import Definitions.Def_BitDFT_Numerics set_option autoImplicit false noncomputable section open scoped BigOperators
Formal statement
theorem BitDFT.bluestein_middle_identity {n : ℕ} (ρ : ℂ) (hρ : ρ ≠ 0)
(X : Fin n → ℂ) (k : Fin n) :
ρ ^ ((k.val : ℤ) ^ 2) *
(∑ j : Fin n, X j * ρ ^ ((j.val : ℤ) ^ 2) *
ρ ^ (-((k.val : ℤ) - (j.val : ℤ)) ^ 2)) =
∑ j : Fin n, X j * (ρ ^ 2) ^ (j.val * k.val) := by sorrySource
Bluestein chirp exponent identity, stated in the BitDFT mission Fourier convention. The Lean proof expands the finite sum and uses k²+j²−(k−j)²=2jk.