fourier_threshold_nu_odd_ge_arithmetic_bound
theoremverifiedformalization
For every integer m >= 1, the arithmetic bound lambda_{2m+1} is a lower bound on the Fourier threshold nu(2m+1).
Statement
theorem fourier_threshold_nu_odd_ge_arithmetic_bound (m : ℕ) (hm : 1 ≤ m) :
arithmetic_fourier_bound (2 * m + 1) ≤ fourier_threshold_nu (2 * m + 1)- Formalizes
- arXiv:2610.38447, Section 5.3, Lemma 5.1
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- arithmetic_fourier_boundFor odd dimension d, lambda_d is the least positive integer n satisfying n = 2 mod 3 and 8(2^d - 1) + 2n + 9 * 1_{n odd} <= 3n^2.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For every natural number $m$ satisfying $1 \le m$, the arithmetic Fourier bound at dimension $2m + 1$ is less than or equal to the Fourier threshold $\nu$ at dimension $2m + 1$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
Lean’s trace was cut to the first 400 of 415 tactics.
namespace ft716open Finset/-- the character value in ZMod 3 -/def chi {d : ℕ} (u x : Fin d → ZMod 2) : ZMod 3 := if ∑ i, u i * x i = 0 then 1 else -1def fh {d : ℕ} (f : (Fin d → ZMod 2) → ZMod 3) (u : Fin d → ZMod 2) : ZMod 3 := ∑ x, f x * chi u xtheorem dot_add_right {d : ℕ} (u x y : Fin d → ZMod 2) : ∑ i, u i * (x + y) i = ∑ i, u i * x i + ∑ i, u i * y i := by rw [← Finset.sum_add_distrib]; exact Finset.sum_congr rfl (fun i _ => by simp [mul_add])theorem dot_comm {d : ℕ} (u x : Fin d → ZMod 2) : ∑ i, u i * x i = ∑ i, x i * u i := Finset.sum_congr rfl (fun i _ => mul_comm _ _)theorem chi_of (a b : ZMod 2) : (if a + b = 0 then (1 : ZMod 3) else -1) = (if a = 0 then 1 else -1) * (if b = 0 then 1 else -1) := by revert a b; decidetheorem chi_mul {d : ℕ} (u x y : Fin d → ZMod 2) : chi u (x + y) = chi u x * chi u y := by unfold chi; rw [dot_add_right]; exact chi_of _ _theorem chi_comm {d : ℕ} (u x : Fin d → ZMod 2) : chi u x = chi x u := by unfold chi; rw [dot_comm]theorem chi_add_left {d : ℕ} (v u y : Fin d → ZMod 2) : chi (v + u) y = chi v y * chi u y := by rw [chi_comm, chi_mul, chi_comm y v, chi_comm y u]theorem chi_zero {d : ℕ} (u : Fin d → ZMod 2) : chi u 0 = 1 := by simp [chi]/-- character sums -/theorem chi_sum {d : ℕ} (z : Fin d → ZMod 2) : ∑ u : Fin d → ZMod 2, chi u z = if z = 0 then (2 : ZMod 3) ^ d else 0 := by classical split_ifs with hz · subst hz; simp [chi_zero, Fintype.card_fun, ZMod.card] · obtain ⟨i, hi⟩ : ∃ i, z i ≠ 0 := by by_contra h; push Not at h; exact hz (funext h) have hzi : z i = 1 := by have : ∀ a : ZMod 2, a ≠ 0 → a = 1 := by decide exact this _ hi let e : Fin d → ZMod 2 := Pi.single i 1 have he : ∑ j, e j * z j = 1 := by rw [Finset.sum_eq_single i] · simp [e, hzi] · intro j _ hj; simp [e, Pi.single_apply, hj] · intro h; exact absurd (Finset.mem_univ i) h have hflip : ∀ u, chi (u + e) z = - chi u z := by intro u rw [chi_add_left] simp only [chi, he] split_ifs <;> simp_all have hS : ∑ u : Fin d → ZMod 2, chi u z = - ∑ u : Fin d → ZMod 2, chi u z := by rw [← Finset.sum_neg_distrib] conv_lhs => rw [← Equiv.sum_comp (Equiv.addRight e)] exact Finset.sum_congr rfl (fun u _ => by simp [hflip]) have h2 : (2 : ZMod 3) * ∑ u : Fin d → ZMod 2, chi u z = 0 := by rw [two_mul]; nth_rewrite 1 [hS]; ring have h2u : IsUnit (2 : ZMod 3) := by decide exact (h2u.mul_right_eq_zero).mp h2theorem sq_of_ne (z : ZMod 3) : z ^ 2 = if z = 0 then 0 else 1 := by revert z; decide/-- convolution identity -/theorem conv {d : ℕ} (f : (Fin d → ZMod 2) → ZMod 3) (hf : ∀ x, f x = 0 ↔ x = 0) (u : Fin d → ZMod 2) : ∑ v, fh f v * fh f (v + u) = (2 : ZMod 3) ^ d * ((if u = 0 then (2 : ZMod 3) ^ d else 0) - 1) := by classical have step1 : ∑ v, fh f v * fh f (v + u) = ∑ x, ∑ y, f x * f y * chi u x * ∑ v, chi v (x + y) := by calc ∑ v, fh f v * fh f (v + u) = ∑ v, ∑ x, ∑ y, f x * f y * chi u x * chi v (x + y) := by refine Finset.sum_congr rfl (fun v _ => ?_) simp only [fh, Finset.sum_mul, Finset.mul_sum] refine Finset.sum_congr rfl (fun x _ => Finset.sum_congr rfl (fun y _ => ?_)) rw [chi_add_left, chi_mul]; ring _ = ∑ x, ∑ y, f x * f y * chi u x * ∑ v, chi v (x + y) := by simp only [Finset.mul_sum] rw [Finset.sum_comm] exact Finset.sum_congr rfl (fun x _ => Finset.sum_comm) rw [step1] simp only [chi_sum] have hxy : ∀ x y : Fin d → ZMod 2, (x + y = 0) ↔ y = x := by intro x y constructor · intro h; funext i; have := congrFun h i; simp at this have key : ∀ a b : ZMod 2, a + b = 0 → b = a := by decide exact key _ _ this · rintro rfl; funext i; simp have key : ∀ a : ZMod 2, a + a = 0 := by decide exact key _ have step2 : ∀ x, ∑ y, f x * f y * chi u x * (if x + y = 0 then (2 : ZMod 3) ^ d else 0) = (2 : ZMod 3) ^ d * (f x ^ 2 * chi u x) := by intro x rw [Finset.sum_eq_single x] · rw [if_pos ((hxy x x).mpr rfl)]; ring · intro y _ hyx; rw [if_neg (fun h => hyx ((hxy x y).mp h))]; ring · intro h; exact absurd (Finset.mem_univ x) h simp only [step2, ← Finset.mul_sum, sq_of_ne, ite_mul, zero_mul, one_mul] congr 1 have : ∑ x : Fin d → ZMod 2, (if f x = 0 then 0 else chi u x) = ∑ x : Fin d → ZMod 2, chi u x - chi u 0 := by rw [← Finset.sum_erase_add _ _ (Finset.mem_univ (0 : Fin d → ZMod 2))] rw [show (if f 0 = 0 then 0 else chi u 0) = 0 by simp [(hf 0).mpr rfl]] rw [← Finset.sum_erase_add _ _ (Finset.mem_univ (0 : Fin d → ZMod 2))] simp only [add_zero, add_sub_cancel_right] refine Finset.sum_congr rfl (fun x hx => ?_) rw [if_neg (fun h => (Finset.mem_erase.mp hx).1 ((hf x).mp h))] rw [this, chi_zero] simp only [chi_comm u, chi_sum]/-- inversion at zero -/theorem sum_fh {d : ℕ} (f : (Fin d → ZMod 2) → ZMod 3) (hf : ∀ x, f x = 0 ↔ x = 0) : ∑ v, fh f v = 0 := by classical simp only [fh] rw [Finset.sum_comm] simp only [← Finset.mul_sum, chi_comm _ _] rw [Finset.sum_eq_single (0 : Fin d → ZMod 2)] · simp [(hf 0).mpr rfl] · intro x _ hx have : ∑ v : Fin d → ZMod 2, chi x v = 0 := by rw [show (∑ v : Fin d → ZMod 2, chi x v) = ∑ v : Fin d → ZMod 2, chi v x from Finset.sum_congr rfl (fun v _ => chi_comm x v), chi_sum, if_neg hx] rw [this, mul_zero] · intro h; exact absurd (Finset.mem_univ _) h/-- integer lift -/def lift3 (z : ZMod 3) : ℤ := if z = 0 then 0 else if z = 1 then 1 else -1theorem lift3_cast (z : ZMod 3) : ((lift3 z : ℤ) : ZMod 3) = z := by revert z; unfold lift3; decidetheorem lift3_ne (z : ZMod 3) : lift3 z ≠ 0 ↔ z ≠ 0 := by revert z; unfold lift3; decidetheorem lift3_vals (z : ZMod 3) : lift3 z = 0 ∨ lift3 z = 1 ∨ lift3 z = -1 := by revert z; unfold lift3; decidetheorem lift3_sq (z : ZMod 3) : lift3 z * lift3 z = if lift3 z ≠ 0 then 1 else 0 := by revert z; unfold lift3; decidetheorem two_pow_odd (m : ℕ) : (2 : ZMod 3) ^ (2 * m + 1) = 2 := by rw [pow_succ, pow_mul]; norm_num have : (4 : ZMod 3) = 1 := by decide simp [this]theorem zmod3_one_iff (z : ℤ) : ((z : ℤ) : ZMod 3) = 1 → z % 3 = 1 := by intro h have h' : (((z - 1 : ℤ)) : ZMod 3) = 0 := by push_cast; rw [h]; ring rw [ZMod.intCast_zmod_eq_zero_iff_dvd] at h' omegatheorem zmod3_two_iff (z : ℤ) : ((z : ℤ) : ZMod 3) = 2 → z % 3 = 2 := by intro h have h' : (((z - 2 : ℤ)) : ZMod 3) = 0 := by push_cast; rw [h]; ring rw [ZMod.intCast_zmod_eq_zero_iff_dvd] at h' omegatheorem zmod3_zero_iff (z : ℤ) : ((z : ℤ) : ZMod 3) = 0 → z % 3 = 0 := by intro h rw [ZMod.intCast_zmod_eq_zero_iff_dvd] at h omegatheorem vadd_cancel {d : ℕ} (v u : Fin d → ZMod 2) : v + u + u = v := by funext i; simp only [Pi.add_apply] have key : ∀ a b : ZMod 2, a + b + b = a := by decide exact key _ _theorem vadd_ne {d : ℕ} (v u : Fin d → ZMod 2) (hu : u ≠ 0) : v + u ≠ v := by intro h; apply hu; funext i; have := congrFun h i; simp only [Pi.add_apply] at this have key : ∀ a b : ZMod 2, a + b = a → b = 0 := by decide exact key _ _ this/-- the main inequality for one admissible f, in ℤ -/theorem main_ineq (d : ℕ) (h2d : (2 : ZMod 3) ^ d = 2) (f : (Fin d → ZMod 2) → ZMod 3) (hf : ∀ x, f x = 0 ↔ x = 0) : let a : (Fin d → ZMod 2) → ℤ := fun v => lift3 (fh f v) let n : ℤ := ∑ v, (if a v ≠ 0 then 1 else 0) n % 3 = 2 ∧ 8 * ((2 : ℤ) ^ d - 1) + 2 * n + (if n % 2 = 1 then 9 else 0) ≤ 3 * n ^ 2 := by classical intro a n let KZ : (Fin d → ZMod 2) → ℤ := fun u => ∑ v, a v * a (v + u) let N : (Fin d → ZMod 2) → ℤ := fun u => ∑ v, (if a v * a (v + u) ≠ 0 then 1 else 0) let σ : ℤ := ∑ v, a v have hKZc : ∀ u, ((KZ u : ℤ) : ZMod 3) = (2 : ZMod 3) ^ d * ((if u = 0 then (2 : ZMod 3) ^ d else 0) - 1) := by intro u; simp only [KZ, a]; push_cast; simp only [lift3_cast]; exact conv f hf u have hKZ0 : KZ 0 = n := by simp only [KZ, n, add_zero]; exact Finset.sum_congr rfl (fun v _ => lift3_sq _) have hn3 : n % 3 = 2 := by apply zmod3_two_iff; rw [← hKZ0, hKZc 0, if_pos rfl, h2d]; decide have hKZu : ∀ u, u ≠ 0 → KZ u % 3 = 1 := by intro u hu; apply zmod3_one_iff; rw [hKZc u, if_neg hu, h2d]; decide have hσ3 : σ % 3 = 0 := by apply zmod3_zero_iff; simp only [σ, a]; push_cast; simp only [lift3_cast]; exact sum_fh f hf have hσ2 : (σ - n) % 2 = 0 := by have : σ - n = ∑ v, (a v - if a v ≠ 0 then 1 else 0) := by simp only [σ, n, Finset.sum_sub_distrib] rw [this] apply Int.emod_eq_zero_of_dvd apply Finset.dvd_sum intro v _ rcases lift3_vals (fh f v) with h | h | h <;> simp [a, h] have hsumKZ : ∑ u, KZ u = σ ^ 2 := by simp only [KZ] rw [Finset.sum_comm] simp only [← Finset.mul_sum] have : ∀ v, ∑ u, a (v + u) = σ := fun v => Equiv.sum_comp (Equiv.addLeft v) a simp only [this, ← Finset.sum_mul, σ]; ring have hsumN : ∑ u, N u = n ^ 2 := by simp only [N, n] have hsplit : ∀ v u, (if a v * a (v + u) ≠ 0 then (1 : ℤ) else 0) = (if a v ≠ 0 then 1 else 0) * (if a (v + u) ≠ 0 then 1 else 0) := by intro v u; by_cases h1 : a v = 0 <;> by_cases h2 : a (v + u) = 0 <;> simp [h1, h2] simp only [hsplit] rw [Finset.sum_comm] simp only [← Finset.mul_sum] have : ∀ v, ∑ u, (if a (v + u) ≠ 0 then (1 : ℤ) else 0) = ∑ w, (if a w ≠ 0 then 1 else 0) := fun v => Equiv.sum_comp (Equiv.addLeft v) (fun w => if a w ≠ 0 then (1 : ℤ) else 0) simp only [this, ← Finset.sum_mul]; ring have hN0 : N 0 = n := by simp only [N, n, add_zero]; exact Finset.sum_congr rfl (fun v _ => by by_cases h : a v = 0 <;> simp [h]) -- per nonzero shift have hper : ∀ u, u ≠ 0 → 8 ≤ 3 * N u - KZ u := by intro u hu let t : (Fin d → ZMod 2) → ℤ := fun v => a v * a (v + u) have ht : ∀ v, t (v + u) = t v := by intro v; simp only [t, vadd_cancel]; ring have htv : ∀ v, t v = 0 ∨ t v = 1 ∨ t v = -1 := by intro v; simp only [t, a] rcases lift3_vals (fh f v) with h | h | h <;> rcases lift3_vals (fh f (v + u)) with h' | h' | h' <;> simp [h, h'] let g : (Fin d → ZMod 2) → ℤ := fun v => 3 * (if t v ≠ 0 then 1 else 0) - t v have hg : 3 * N u - KZ u = ∑ v, g v := by simp only [g, N, KZ, t, Finset.sum_sub_distrib, Finset.mul_sum] have hg0 : ∀ v, 0 ≤ g v := by intro v; rcases htv v with h | h | h <;> simp [g, h] have hpair : ∀ v, g v + g (v + u) ≤ ∑ w, g w := by intro v have hsub : ({v, v + u} : Finset _) ⊆ Finset.univ := Finset.subset_univ _ have := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun w _ _ => hg0 w) rwa [Finset.sum_pair (vadd_ne v u hu).symm] at this rw [hg] by_cases hneg : ∃ v, t v = -1 · obtain ⟨v, hv⟩ := hneg have h1 : g v = 4 := by simp [g, hv] have h2 : g (v + u) = 4 := by simp [g, ht, hv] have := hpair v; omega · push Not at hneg have h01 : ∀ v, t v = 0 ∨ t v = 1 := fun v => by rcases htv v with h | h | h · exact Or.inl h · exact Or.inr h · exact absurd h (hneg v) have hKN : KZ u = N u := by simp only [KZ, N]; refine Finset.sum_congr rfl (fun v _ => ?_) rcases h01 v with h | h <;> simp only [t] at h <;> simp [h] have hmod := hKZu u hu have hne : KZ u ≠ 0 := by intro h; rw [h] at hmod; norm_num at hmod obtain ⟨v, hv⟩ : ∃ v, t v = 1 := by by_contra hc; push Not at hc apply hne; simp only [KZ]; exact Finset.sum_eq_zero (fun v _ => by rcases h01 v with h | h · exact h · exact absurd h (hc v)) have hgv : g v = 2 := by simp [g, hv] have hgv' : g (v + u) = 2 := by simp [g, ht, hv] have hge := hpair v have hgsum : ∑ w, g w = 2 * N u := by rw [← hg, hKN]; ring omega -- sum over shifts have htot : ∑ u, (3 * N u - KZ u) = 3 * n ^ 2 - σ ^ 2 := by rw [Finset.sum_sub_distrib, ← Finset.mul_sum, hsumN, hsumKZ] have hrest : ∑ u ∈ Finset.univ.erase 0, (3 * N u - KZ u) ≥ ∑ u ∈ Finset.univ.erase (0 : Fin d → ZMod 2), (8 : ℤ) := Finset.sum_le_sum (fun u hu => hper u (Finset.mem_erase.mp hu).1) rw [Finset.sum_const, Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fun, ZMod.card, Fintype.card_fin] at hrest have hsplit0 := Finset.sum_erase_add Finset.univ (fun u => 3 * N u - KZ u) (Finset.mem_univ 0) rw [htot, hN0, hKZ0] at hsplit0 have hpow : (1 : ℤ) ≤ 2 ^ d := one_le_pow₀ (by norm_num) have hcast : ((2 ^ d - 1 : ℕ) : ℤ) = (2 : ℤ) ^ d - 1 := by rw [Nat.cast_sub (Nat.one_le_two_pow)]; push_cast; ring simp only [nsmul_eq_mul, hcast] at hrest refine ⟨hn3, ?_⟩ split_ifs with hodd · -- n odd, so σ odd and divisible by 3: σ² ≥ 9 have hσodd : σ % 2 = 1 := by omega obtain ⟨k, hk⟩ : (3 : ℤ) ∣ σ := Int.dvd_of_emod_eq_zero hσ3 have hk0 : k ≠ 0 := by rintro rfl; simp at hk; omega have hk2 : 1 ≤ k ^ 2 := by have := pow_pos (abs_pos.mpr hk0) 2 rw [sq_abs] at this omega have : 9 ≤ σ ^ 2 := by rw [hk]; nlinarith nlinarith · nlinarith [sq_nonneg σ]theorem card_mem (m : ℕ) (f : (Fin (2 * m + 1) → ZMod 2) → ZMod 3) (hf : ∀ x, f x = 0 ↔ x = 0) : (Finset.filter (fun (u : Fin (2 * m + 1) → ZMod 2) => (-1 : ZMod 3) ^ (2 * m + 1) * ∑ x : Fin (2 * m + 1) → ZMod 2, f x * (if ∑ i, u i * x i = 0 then 1 else -1) ≠ 0) Finset.univ).card ∈ {n : ℕ | n % 3 = 2 ∧ 8 * (2 ^ (2 * m + 1) - 1) + 2 * n + (if n % 2 = 1 then 9 else 0) ≤ 3 * n ^ 2} := by classical have key := main_ineq (2 * m + 1) (two_pow_odd m) f hf dsimp only at key set c := (Finset.filter (fun (u : Fin (2 * m + 1) → ZMod 2) => (-1 : ZMod 3) ^ (2 * m + 1) * ∑ x : Fin (2 * m + 1) → ZMod 2, f x * (if ∑ i, u i * x i = 0 then 1 else -1) ≠ 0) Finset.univ).card with hc have hcount : (∑ v : Fin (2 * m + 1) → ZMod 2, (if lift3 (fh f v) ≠ 0 then (1 : ℤ) else 0)) = (c : ℤ) := by rw [hc, Finset.natCast_card_filter] refine Finset.sum_congr rfl (fun v _ => ?_) have hu : (-1 : ZMod 3) ^ (2 * m + 1) ≠ 0 := pow_ne_zero _ (by decide) have : (lift3 (fh f v) ≠ 0) ↔ ((-1 : ZMod 3) ^ (2 * m + 1) * ∑ x : Fin (2 * m + 1) → ZMod 2, f x * (if ∑ i, v i * x i = 0 then 1 else -1) ≠ 0) := by rw [lift3_ne, mul_ne_zero_iff, and_iff_right hu]; rfl simp only [this] rw [hcount] at key obtain ⟨h1, h2⟩ := key refine ⟨by omega, ?_⟩ have hp : 1 ≤ 2 ^ (2 * m + 1) := Nat.one_le_two_pow by_cases hodd : c % 2 = 1 · rw [if_pos hodd] rw [if_pos (by omega)] at h2 zify [hp]; push_cast; linarith · rw [if_neg hodd] rw [if_neg (by omega)] at h2 zify [hp]; push_cast; linarithend ft716/-- The arithmetic lower bound on the odd-dimensional Fourier threshold nu(2m+1). -/theorem fourier_threshold_nu_odd_ge_arithmetic_bound (m : ℕ) (hm : 1 ≤ m) : arithmetic_fourier_bound (2 * m + 1) ≤ fourier_threshold_nu (2 * m + 1) := by classical unfold fourier_threshold_nu rw [Finset.le_fold_min] constructor · -- 2^d itself lies in the defining set have hmem : 2 ^ (2 * m + 1) ∈ {n : ℕ | n % 3 = 2 ∧ 8 * (2 ^ (2 * m + 1) - 1) + 2 * n + (if n % 2 = 1 then 9 else 0) ≤ 3 * n ^ 2} := by have h3 : 2 ^ (2 * m + 1) % 3 = 2 := by rw [pow_succ, pow_mul, Nat.mul_mod, Nat.pow_mod]; norm_num have h2 : 2 ^ (2 * m + 1) % 2 = 0 := by rw [pow_succ]; simp refine ⟨h3, ?_⟩ rw [if_neg (by omega)] have hp : 1 ≤ 2 ^ (2 * m + 1) := Nat.one_le_two_pow have hq : 2 ≤ 2 ^ (2 * m + 1) := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (2 * m + 1) := Nat.pow_le_pow_right (by norm_num) (by omega) zify [hp]; nlinarith exact (Nat.sInf_le hmem).trans (Nat.le_succ _) · intro f hf rw [Finset.mem_filter] at hf exact Nat.sInf_le (ft716.card_mem m f hf.2)