AFTD Auto-Formalizing Theoretical Domains

fourier_ratio_nonneg

theoremverified

For every complex-valued function $f : H \to \mathbb{C}$ on a finite abelian group $H$, its Fourier ratio is nonnegative: $0 \le \operatorname{FR}(f)$.

Statement

theorem fourier_ratio_nonneg {H : Type*} [AddCommGroup H] [Fintype H]
    (f : H → ℂ) : 0 ≤ fourier_ratio f
Source
arXiv:2610.31807 Definition 2.1
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_transformThe normalized Fourier transform of a complex-valued function $f : H \to \mathbb{C}$ on a finite additive abelian group $H$ (…

Read back from the Lean

For every finite additive abelian group H and every function f : H → ℂ, the Fourier ratio of f is non-negative (0 ≤ fourier_ratio f).

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

The proof, explained

The Fourier ratio is defined as the quotient of the sum of character norms ∑_γ ‖f̂(γ)‖ and the square root of the sum of squares √(∑_γ ‖f̂(γ)‖²). The proof unfolds this definition and splits the goal into showing that both the numerator and the denominator are nonnegative. The numerator is a finite sum of norms, each nonnegative, and the denominator is a real square root, which is always nonnegative.

  1. It suffices to show that the numerator ∑ γ, ‖fourier_transform f γ‖ and the denominator √(∑ γ, ‖fourier_transform f γ‖ ^ 2) are both nonnegative.

    Unfolding the definition of `fourier_ratio` expresses it as the quotient (∑ γ, ‖fourier_transform f γ‖) / √(∑ γ, ‖fourier_transform f γ‖ ^ 2). Applying `div_nonneg` reduces the goal of showing the ratio is nonnegative to establishing that the numerator and denominator are separately nonnegative.

    lines 4–5

    uses div_nonneg

      unfold fourier_ratio
      apply div_nonneg
  2. The numerator ∑ γ, ‖fourier_transform f γ‖ is nonnegative.

    Each term ‖fourier_transform f γ‖ is the norm of a complex number, hence nonnegative by `norm_nonneg`. By `Finset.sum_nonneg`, the sum of these nonnegative terms over all characters γ is nonnegative.

    line 6

    uses Finset.sum_nonneg, norm_nonneg

      · exact Finset.sum_nonneg (fun γ _ => norm_nonneg _)
  3. The denominator √(∑ γ, ‖fourier_transform f γ‖ ^ 2) is nonnegative.

    The denominator is the real square root of an expression, which is nonnegative by `Real.sqrt_nonneg`.

    line 7

    uses Real.sqrt_nonneg

      · exact Real.sqrt_nonneg _
div_nonneg
A quotient a / b is nonnegative if both a ≥ 0 and b ≥ 0.
Finset.sum_nonneg
A finite sum is nonnegative if every term in the sum is nonnegative.
norm_nonneg
The norm of any element in a seminormed group is nonnegative: ‖a‖ ≥ 0.
Real.sqrt_nonneg
The real square root function always returns a nonnegative value: 0 ≤ √x for all x ∈ ℝ.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The Fourier ratio is nonnegative. -/theorem fourier_ratio_nonneg {H : Type*} [AddCommGroup H] [Fintype H]    (f : H → ℂ) : 0 ≤ fourier_ratio f := by  unfold fourier_ratio  apply div_nonneg  · exact Finset.sum_nonneg (fun γ _ => norm_nonneg _)  · exact Real.sqrt_nonneg _
See it in the graphDiscuss this resultChallenge it