arithmetic_fourier_bound_three
The arithmetic Fourier bound lambda_3 in dimension 3 equals 5.
Statement
theorem arithmetic_fourier_bound_three : arithmetic_fourier_bound 3 = 5- Source
- step towards op716_fourier_threshold_odd_eq_arithmetic_bound
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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.
The proof, explained
The bound `arithmetic_fourier_bound 3` is defined as the infimum of the set of natural numbers n with n ≡ 2 (mod 3) satisfying 56 + 2n + (9 if n is odd else 0) ≤ 3n². The proof establishes equality with 5 by showing both inequalities (antisymmetry). The upper bound holds because n = 5 satisfies both conditions by direct computation, and the lower bound holds because testing all integers in {0, 1, 2, 3, 4} shows that none satisfies both constraints.
The number 5 belongs to the set defining the arithmetic Fourier bound in dimension 3.
Unfolding the definition of `arithmetic_fourier_bound 3`, the quantity is the infimum of the set of natural numbers n such that n % 3 = 2 and 8 * (2^3 - 1) + 2 * n + (if n is odd then 9 else 0) ≤ 3 * n^2. Evaluating this predicate at n = 5 gives 5 % 3 = 2 and 56 + 10 + 9 = 75 ≤ 3 * 25 = 75, both of which are true by direct computation (`decide`).
unfold arithmetic_fourier_bound have h5 : 5 ∈ {n : ℕ | n % 3 = 2 ∧ 8 * (2 ^ 3 - 1) + 2 * n + (if n % 2 = 1 then 9 else 0) ≤ 3 * n ^ 2} := by decide
The infimum is at most 5.
By antisymmetry of partial orders (`le_antisymm`), proving equality reduces to showing the infimum is at most 5 and at least 5. Because 5 belongs to the set, the basic property of the infimum on the natural numbers (`Nat.sInf_le`) immediately implies that the infimum is at most 5.
uses
le_antisymm,Nat.sInf_leapply le_antisymm · exact Nat.sInf_le h5
To show the infimum is at least 5, it suffices to prove that every element in the set is at least 5.
By the universal property of the infimum in a conditionally complete lattice (`le_csInf`), a number is less than or equal to the infimum of a set provided that the set is nonempty (witnessed by the element 5) and that the number is a lower bound for all elements of the set.
uses
le_csInf· apply le_csInf · exact ⟨5, h5⟩
Every natural number in the set is at least 5.
Let b be an arbitrary element of the set, so b % 3 = 2 and 56 + 2 * b + (if b is odd then 9 else 0) ≤ 3 * b^2. Assuming for contradiction that b < 5 (`by_contra!`), the only possible values for b are 0, 1, 2, 3, and 4. A case analysis on these five values (`interval_cases b`) refutes each one (`decide`): for b ∈ {0, 1, 3, 4}, the modular condition b % 3 = 2 is violated; for b = 2, the inequality simplifies to 60 ≤ 12, which is false.
· intro b hb dsimp at hb rcases hb with ⟨hb1, hb2⟩ by_contra! h interval_cases b <;> revert hb1 hb2 <;> decide
le_antisymm- in a partial order, if a ≤ b and b ≤ a, then a = b
Nat.sInf_le- for any subset of the natural numbers, its infimum is less than or equal to any element in the set
le_csInf- in a conditionally complete lattice, a lower bound for every element of a nonempty set is at most the infimum of the set
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
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.
/-- The arithmetic Fourier bound lambda_3 in dimension 3 equals 5. -/theorem arithmetic_fourier_bound_three : arithmetic_fourier_bound 3 = 5 := by unfold arithmetic_fourier_bound have h5 : 5 ∈ {n : ℕ | n % 3 = 2 ∧ 8 * (2 ^ 3 - 1) + 2 * n + (if n % 2 = 1 then 9 else 0) ≤ 3 * n ^ 2} := by decide apply le_antisymm · exact Nat.sInf_le h5 · apply le_csInf · exact ⟨5, h5⟩ · intro b hb dsimp at hb rcases hb with ⟨hb1, hb2⟩ by_contra! h interval_cases b <;> revert hb1 hb2 <;> decide