AFTD Auto-Formalizing Theoretical Domains

fourier_transform

def

The normalized Fourier transform of a complex-valued function $f : H \to \mathbb{C}$ on a finite additive abelian group $H$ (AddCommGroup H with Fintype H), defined for an additive character $\gamma : \operatorname{AddChar} H\ \mathbb{C}$ as $(\sqrt{|H|})^{-1} \sum_{x \in H} f(x) \overline{\gamma(x)}$, where $|H| = \operatorname{card}(H)$ and the square root is inverted in $\mathbb{C}$.

Statement

noncomputable def fourier_transform {H : Type*} [AddCommGroup H] [Fintype H]
    (f : H → ℂ) (γ : AddChar H ℂ) : ℂ
Defined in
arXiv:2610.31807, equation (2.1)
Verified
26 Oct 2026
Axioms
none listed
Used by 4
  • fourier_ratio_nonnegFor every complex-valued function $f : H \to \mathbb{C}$ on a finite abelian group $H$, its Fourier ratio is nonnegative:…
  • fourier_ratioFor a complex-valued function $f : H \to \mathbb{C}$ on a finite abelian group $H$, its Fourier ratio $\operatorname{FR}(f)$ is…
  • fourier_collision_dim_nonnegFor every complex-valued function $f : H \to \mathbb{C}$ on a finite abelian group $H$, its Fourier collision dimension is nonnegative:…
  • fourier_collision_dimFor a complex-valued function $f : H \to \mathbb{C}$ on a finite abelian group $H$, its Fourier collision dimension $D_4(f)$ is…

Read back from the Lean

Given a finite additive abelian group $H$, a function $f : H \to \mathbb{C}$, and an additive character $\gamma : \mathrm{AddChar}(H, \mathbb{C})$, fourier_transform f γ is defined as the complex number $$\frac{1}{\sqrt{|H|}} \sum_{x \in H} f(x) \overline{\gamma(x)}$$ where $|H|$ is the cardinality of $H$, the square root is cast to $\mathbb{C}$, and star denotes complex conjugation.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Normalized Fourier transform of a complex-valued function on a finite additive abelian group. -/
noncomputable def fourier_transform {H : Type*} [AddCommGroup H] [Fintype H]
    (f : H → ℂ) (γ : AddChar H ℂ) : ℂ := (Real.sqrt (Fintype.card H) : ℂ)⁻¹ * ∑ x : H, f x * star (γ x)
See it in the graphDiscuss this resultChallenge it