AFTD Auto-Formalizing Theoretical Domains

fourier_collision_dim_nonneg

theoremverified

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

Statement

theorem fourier_collision_dim_nonneg {H : Type*} [AddCommGroup H] [Fintype H]
    (f : H → ℂ) : 0 ≤ fourier_collision_dim f
Source
arXiv:2610.31807 Definition 2.1
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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 \to \mathbb{C}$, the Fourier collision dimension of $f$ is non-negative ($0 \le \mathrm{fourier\_collision\_dim}(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 definition of the Fourier collision dimension expresses it as the ratio of the squared $L^2$-energy of the Fourier transform to its $L^4$-energy, namely $\left(\sum_{\gamma} \|\widehat{f}(\gamma)\|^2\right)^2 / \sum_{\gamma} \|\widehat{f}(\gamma)\|^4$. The numerator is a square of a real number and the denominator is a sum of fourth powers of norms, so both are nonnegative real numbers. The claim follows immediately because the quotient of two nonnegative quantities is nonnegative.

  1. The inequality reduces to showing that $\left(\sum_{\gamma} \|\widehat{f}(\gamma)\|^2\right)^2 / \sum_{\gamma} \|\widehat{f}(\gamma)\|^4 \ge 0$.

    Unfolding the definition of `fourier_collision_dim` expresses the collision dimension directly as the square of the sum of squared norms of the Fourier transform divided by the sum of fourth powers of those norms.

    line 4

      unfold fourier_collision_dim
  2. The quotient of the two sums is nonnegative. automation

    The numerator is the square of a real number and therefore nonnegative. The denominator is a finite sum of fourth powers of norms, each of which is nonnegative. Since the ratio of two nonnegative real numbers is nonnegative, the `positivity` tactic verifies the inequality directly from the syntactic structure of the expression.

    line 5

      positivity

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 collision dimension is nonnegative. -/theorem fourier_collision_dim_nonneg {H : Type*} [AddCommGroup H] [Fintype H]    (f : H → ℂ) : 0 ≤ fourier_collision_dim f := by  unfold fourier_collision_dim  positivity
See it in the graphDiscuss this resultChallenge it