AFTD Auto-Formalizing Theoretical Domains

fourier_threshold_nu_one

theoremverifiedformalization

The Fourier threshold nu(1) for functions from ZMod 2 to ZMod 3 with unique zero at 0 is equal to 2.

Statement

theorem fourier_threshold_nu_one : fourier_threshold_nu 1 = 2
Formalizes
arXiv:2610.38447, Section 5
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • fourier_threshold_nuThe Fourier threshold nu(d) is the minimum size of the Fourier support of a function f from (ZMod 2)^d to ZMod 3 whose zero set is…

Read back from the Lean

fourier_threshold_nu 1 = 2, where fourier_threshold_nu d is the minimum, over all functions f : (Fin d → ZMod 2) → ZMod 3 such that f x = 0 ↔ x = 0, of the number of vectors u : Fin d → ZMod 2 for which the Fourier-like sum (-1)^d * ∑ x, f x * (if u · x = 0 then 1 else -1) is non-zero in ZMod 3 (with a base value of 2^d + 1).

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 theorem states that the Fourier threshold $\nu(1)$ is equal to $2$. The quantity $\nu(d)$ is defined as the minimum number of non-zero Fourier coefficients over all functions from $(\mathbb{Z}/2\mathbb{Z})^d$ to $\mathbb{Z}/3\mathbb{Z}$ whose unique root is at the origin. For dimension $d = 1$, the function space and domain are small finite sets, and the statement is verified by exhaustive definitional computation via reflexivity.

  1. Both functions $f : \mathbb{Z}/2\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ with a unique zero at the origin have non-zero Fourier coefficients at both frequencies, making their minimum $\nu(1)$ equal to $2$.

    By definition, $\nu(1)$ minimizes the number of non-zero Fourier coefficients over all functions $f : \mathbb{Z}/2\mathbb{Z} \to \mathbb{Z}/3\mathbb{Z}$ satisfying $f(x) = 0 \iff x = 0$. For $d = 1$, the domain has size $2$, so such a function is completely determined by $f(1) \in \{1, 2\}$, leaving only two candidates. In both cases, the Fourier transform at both frequencies $u = 0$ and $u = 1$ yields a non-zero value in $\mathbb{Z}/3\mathbb{Z}$ (evaluating to $\pm f(1) \neq 0$). Because all sets are finite and the predicates are decidable, Lean evaluates the expression definitionally via reflexivity (`rfl`).

    line 2

    theorem fourier_threshold_nu_one : fourier_threshold_nu 1 = 2 := rfl

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Evaluation of the Fourier threshold nu(1) = 2. -/theorem fourier_threshold_nu_one : fourier_threshold_nu 1 = 2 := rfl
See it in the graphDiscuss this resultChallenge it