AlexKontorovich/PrimeNumberTheoremAnd
Source indexedlemma · leanprover/lean4:v4.32.0
sum_bounded_of_linear_bound
PrimeNumberTheoremAnd.Consequences · PrimeNumberTheoremAnd/Consequences.lean:1780 to 1804
Mathematical statement
Exact Lean statement
lemma sum_bounded_of_linear_bound {f : ℝ → ℝ} {ε C : ℝ} (hε : 0 ≤ ε) (hC : 0 ≤ C) (h : ∀ y, 1 ≤ y → |f y| ≤ ε * y + C) (x : ℝ) (hx : 1 ≤ x) :
∑ k ∈ Icc 1 ⌊x⌋₊, |f (x / k)| ≤ ε * x * (log x + 1) + C * xComplete declaration
Lean source
Full Lean sourceLean 4
lemma sum_bounded_of_linear_bound {f : ℝ → ℝ} {ε C : ℝ} (hε : 0 ≤ ε) (hC : 0 ≤ C) (h : ∀ y, 1 ≤ y → |f y| ≤ ε * y + C) (x : ℝ) (hx : 1 ≤ x) : ∑ k ∈ Icc 1 ⌊x⌋₊, |f (x / k)| ≤ ε * x * (log x + 1) + C * x := by have h_sum_bound : ∑ k ∈ Finset.Icc 1 ⌊x⌋₊, |f (x / k)| ≤ ε * x * ∑ k ∈ Finset.Icc 1 ⌊x⌋₊, (1 / (k : ℝ)) + C * ⌊x⌋₊ := by have h_sum_bound : ∀ k ∈ Finset.Icc 1 ⌊x⌋₊, |f (x / k)| ≤ ε * x / k + C := by exact fun k hk => by simpa only [mul_div_assoc] using! h (x / k) (by rw [le_div_iff₀ (Nat.cast_pos.mpr <| Finset.mem_Icc.mp hk |>.1)] ; nlinarith [Nat.floor_le (show 0 ≤ x by positivity), show (k : ℝ) ≤ ⌊x⌋₊ by exact_mod_cast Finset.mem_Icc.mp hk |>.2]) convert! Finset.sum_le_sum h_sum_bound using 1 ; norm_num [div_eq_mul_inv, Finset.mul_sum _ _ _, Finset.sum_add_distrib, mul_comm] have h_harmonic : ∀ n : ℕ, 1 ≤ n → ∑ k ∈ Finset.Icc 1 n, (1 / (k : ℝ)) ≤ Real.log n + 1 := by intro n _hn have h := harmonic_le_one_add_log n simpa [harmonic_eq_sum_Icc, Rat.cast_sum, Rat.cast_inv, Rat.cast_natCast, one_div, add_comm, add_left_comm, add_assoc] using h have h_harmonic_x : ∑ k ∈ Finset.Icc 1 ⌊x⌋₊, (1 / (k : ℝ)) ≤ Real.log x + 1 := by refine (h_harmonic _ <| Nat.floor_pos.mpr hx).trans ?_ have hlog : Real.log (⌊x⌋₊ : ℝ) ≤ Real.log x := by refine Real.log_le_log (Nat.cast_pos.mpr <| Nat.floor_pos.mpr hx) ?_ exact Nat.floor_le (by positivity) simpa using add_le_add_right hlog 1 have h_term1 : ε * x * (∑ k ∈ Finset.Icc 1 ⌊x⌋₊, (1 / (k : ℝ))) ≤ ε * x * (Real.log x + 1) := by refine mul_le_mul_of_nonneg_left h_harmonic_x ?_ exact mul_nonneg hε (by positivity) have h_term2 : C * (⌊x⌋₊ : ℝ) ≤ C * x := by refine mul_le_mul_of_nonneg_left ?_ hC exact Nat.floor_le (by positivity) exact h_sum_bound.trans (add_le_add h_term1 h_term2)