Skip to main content
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 * x

Complete declaration

Lean source

Canonical 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)