AFTD Auto-Formalizing Theoretical Domains

fourier_threshold_nu

def

The 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 precisely {0}.

Statement

def fourier_threshold_nu (d : ℕ) : ℕ
Defined in
arXiv:2610.38447, Section 4, eq. (28)
Verified
01 Nov 2026
Axioms
none listed
Used by 5
  • fourier_threshold_nu_twoThe Fourier threshold nu(2) for functions from (ZMod 2)^2 to ZMod 3 with unique zero at 0 is equal to 3.
  • fourier_witness_fiveThe explicit test function f : (ZMod 2)^5 → ZMod 3 obtained by Fourier inversion from the dual combination with support the Hamming-weight…
  • fourier_threshold_nu_threeThe Fourier threshold nu(3) for functions from (ZMod 2)^3 to ZMod 3 with unique zero at 0 is equal to 5.
  • fourier_threshold_nu_oneThe Fourier threshold nu(1) for functions from ZMod 2 to ZMod 3 with unique zero at 0 is equal to 2.
  • fourier_threshold_nu_odd_ge_arithmetic_boundFor every integer m >= 1, the arithmetic bound lambda_{2m+1} is a lower bound on the Fourier threshold nu(2m+1).

Read back from the Lean

For a natural number d, fourier_threshold_nu d is defined as the minimum over all functions f : (Fin d → ZMod 2) → ZMod 3 satisfying ∀ x, f x = 0 ↔ x = 0 (with a base accumulator of 2^d + 1) of the number of vectors u : Fin d → ZMod 2 such that (-1 : ZMod 3)^d * ∑ x : Fin d → ZMod 2, f x * (if (∑ i : Fin d, u i * x i) = 0 then 1 else -1) ≠ 0 in ZMod 3.

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

/-- The extremal Fourier threshold nu(d) is the minimum Fourier support size of an F_3-valued function on F_2^d with unique zero at the origin. -/
def fourier_threshold_nu (d : ℕ) : ℕ :=
  (Finset.filter (fun f : (Fin d → ZMod 2) → ZMod 3 => ∀ x, (f x = 0 ↔ x = 0)) Finset.univ).fold
    min (2^d + 1) (fun f => (Finset.filter (fun (u : Fin d → ZMod 2) =>
      (-1 : ZMod 3)^d * ∑ x : Fin d → ZMod 2, f x * (if ∑ i, u i * x i = 0 then 1 else -1) ≠ 0) Finset.univ).card)
See it in the graphDiscuss this resultChallenge it