fourier_threshold_nu_three
The Fourier threshold nu(3) for functions from (ZMod 2)^3 to ZMod 3 with unique zero at 0 is equal to 5.
Statement
theorem fourier_threshold_nu_three : fourier_threshold_nu 3 = 5- 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
The quantity fourier_threshold_nu 3 equals 5, where fourier_threshold_nu d is defined as the minimum (starting with upper bound $2^d + 1$) over all functions $f : (\text{Fin } d \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/3\mathbb{Z}$ that vanish precisely at $0$ (i.e., $f(x) = 0 \iff x = 0$), of the number of vectors $u : \text{Fin } d \to \mathbb{Z}/2\mathbb{Z}$ for which the sum
$$(-1)^d \sum_{x : \text{Fin } d \to \mathbb{Z}/2\mathbb{Z}} f(x) \cdot (\text{if } \sum_{i : \text{Fin } d} u(i) x(i) = 0 \text{ then } 1 \text{ else } -1) \neq 0 \pmod 3.$$
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 threshold nu(3) is defined as the minimum number of non-zero Fourier coefficients modulo 3 among all functions from (ZMod 2)^3 to ZMod 3 with a unique zero at the origin. Because the domain and codomain are finite, the search space consists of exactly 2^7 = 128 functions, each with 8 Fourier coefficients, making the value entirely computable. The auxiliary lemma `fourier_threshold_nu_three_aux` evaluates this finite minimization by definitional equality (reflexivity) under increased recursion and heartbeat limits, and `fourier_threshold_nu_three` directly invokes this result.
The Fourier threshold nu(3) is equal to 5 by finite computational exhaustion. automation
The threshold `fourier_threshold_nu 3` is defined by filtering the finite set of functions f : (ZMod 2)^3 → ZMod 3 that vanish only at 0 (there are 2^7 = 128 such functions), counting how many of the 8 Fourier coefficients modulo 3 are non-zero for each function, and taking the minimum. With `maxRecDepth` increased to 20,000 and `maxHeartbeats` to 1,000,000, Lean's kernel evaluates this entire finite search by reflexivity (`rfl`) to establish the auxiliary lemma `fourier_threshold_nu_three_aux`.
set_option maxRecDepth 20000 in set_option maxHeartbeats 1000000 in lemma fourier_threshold_nu_three_aux : fourier_threshold_nu 3 = 5 := rfl
The theorem fourier_threshold_nu 3 = 5 holds.
The main theorem `fourier_threshold_nu_three` follows immediately by citing the precomputed auxiliary lemma `fourier_threshold_nu_three_aux`.
uses
fourier_threshold_nu_three_auxtheorem fourier_threshold_nu_three : fourier_threshold_nu 3 = 5 := fourier_threshold_nu_three_aux
fourier_threshold_nu_three_aux- The Fourier threshold nu(3), defined as the minimum number of non-zero Fourier coefficients modulo 3 among functions from (ZMod 2)^3 to ZMod 3 with a unique zero at 0, equals 5.
- The proof of the auxiliary lemma `fourier_threshold_nu_three_aux` is carried out entirely by Lean's kernel through definitional equality (`rfl`). This exhaustively evaluates all 128 candidate functions and their Fourier transforms by brute force, which requires increasing `maxHeartbeats` and `maxRecDepth`.
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
set_option maxRecDepth 20000 inset_option maxHeartbeats 1000000 inlemma fourier_threshold_nu_three_aux : fourier_threshold_nu 3 = 5 := rfl/-- Evaluation of the Fourier threshold nu(3) = 5. -/theorem fourier_threshold_nu_three : fourier_threshold_nu 3 = 5 := fourier_threshold_nu_three_aux