The discrete Fourier transform turns convolution into multiplication
ProvedCouret.InterIA.Cubic.dft_cconvcouret-programmecouret-unification-20261108
Let , , and . With unnormalized Fourier transform and convolution ,
This diagonalizes cyclic convolution.
Preamble
import Definitions.Def_Couret_CubicFourier_396e42df2f8b import Mathlib.Analysis.Fourier.ZMod import Mathlib.Tactic.Ring import Mathlib.Analysis.Fourier.ZMod import Mathlib.Tactic.Ring set_option autoImplicit false namespace Couret.InterIA.Cubic open Finset
Formal statement
theorem dft_cconv {n : ℕ} [NeZero n] (f g : ZMod n → ℂ) (k : ZMod n) :
ZMod.dft (cconv f g) k = ZMod.dft f k * ZMod.dft g k := by sorry
end Couret.InterIA.Cubic
Source
Alexandre Couret, Cubic observations for four-point convolution reconstruction: universal two-coordinate bound and Lean proof archive, https://zenodo.org/records/23983731; archive Cubic_Observations_Lean_Archive_20261105.zip, SHA-256 7a118549d5729dbcfbfb20bd35fea7ebd91275b7bde61591d6bdda5c13b749ec; file formal/lean/CubicFourier.lean, lines 12–38; source file SHA-256 c0e1858422dfb02100eea58c200f328f13b0ef1ffe13be5a655bfe101674c789; theorem Couret.InterIA.Cubic.dft_cconv