AFTD Auto-Formalizing Theoretical Domains

arithmetic_fourier_bound_three

theoremverified

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.

  1. 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`).

    lines 3–5

      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
  2. 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.

    lines 6–7

    uses le_antisymm, Nat.sInf_le

      apply le_antisymm
      · exact Nat.sInf_le h5
  3. 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.

    lines 8–9

    uses le_csInf

      · apply le_csInf
        · exact ⟨5, h5⟩
  4. 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.

    lines 10–14

        · 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

/-- 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
See it in the graphDiscuss this resultChallenge it