Skip to main content
AlexKontorovich/PrimeNumberTheoremAnd
Source indexedtheorem · leanprover/lean4:v4.32.0

Chebyshev.psi_upper_clean

PrimeNumberTheoremAnd.IEANTN.Chebyshev · PrimeNumberTheoremAnd/IEANTN/Chebyshev.lean:617 to 658

Mathematical statement

Exact Lean statement

@[blueprint
  "psi-upper-clean"
  (title := "Clean upper bound for $\\psi$")
  (statement := /-- For $x > 0$, we have $\psi(x) \leq 1.11 x$. -/)
  (proof := /-- Strong induction on $x$.  For $x \leq 11723$ one can use Sublemma \ref{psi-num-2}.  Otherwise, we can use Proposition \ref{psi-diff-upper} and the triangle inequality. -/)
  (latexEnv := "theorem")
  (discussion := 844)]
theorem psi_upper_clean (x : ℝ) (hx : x > 0) : ψ x ≤ 1.11 * x

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
@[blueprint  "psi-upper-clean"  (title := "Clean upper bound for $\\psi$")  (statement := /-- For $x > 0$, we have $\psi(x) \leq 1.11 x$. -/)  (proof := /-- Strong induction on $x$.  For $x \leq 11723$ one can use Sublemma \ref{psi-num-2}.  Otherwise, we can use Proposition \ref{psi-diff-upper} and the triangle inequality. -/)  (latexEnv := "theorem")  (discussion := 844)]theorem psi_upper_clean (x : ) (hx : x > 0) : ψ x  1.11 * x := by  have hlog_large :  y : , 11723 < y  5 * log y - 5  (37 / 10000 : ) * y := by    intro y hy    have hlog_11723 : log (11723 : )  937 / 100 := LogTables.log_11723_lt    calc 5 * log y - 5         5 * (937 / 100 + (y / 11723 - 1)) - 5 := by linarith [hlog_y y hy]      _ = 5 / 11723 * y + 3685 / 100 := by ring      _  37 / 10000 * y := by linarith  have hNat :  n : , ψ (n : )  1.11 * n := by    intro n    refine Nat.strong_induction_on n ?_    intro n ih    by_cases hn0 : n = 0    · subst hn0; simp [psi_eq_zero_of_lt_two (by norm_num : (0 : ) < 2)]    · have hn : 0 < n := Nat.pos_of_ne_zero hn0      by_cases! hsmall : (n : )  11723      · exact psi_num_2 n (by exact_mod_cast hn) hsmall      · let m :  := ⌊(n : ) / 6⌋₊        have hm_lt_n : m < n := by          exact_mod_cast show (m : ) < n from            lt_of_le_of_lt (Nat.floor_le (by positivity)) (by nlinarith)        have hpsi_div : ψ ((n : ) / 6)  1.11 * ((n : ) / 6) := calc          ψ ((n : ) / 6) = ψ (m : ) := by simp [m, psi_eq_psi_coe_floor]          _  1.11 * (m : ) := ih m hm_lt_n          _  1.11 * ((n : ) / 6) := by nlinarith [Nat.floor_le (by positivity : 0  (n : ) / 6)]        calc ψ (n : )             ψ ((n : ) / 6) + a * n + 5 * log (n : ) - 5 := by                linarith [psi_diff_upper (n : ) (by linarith)]          _  1.11 * ((n : ) / 6) + 0.92130 * n + (37 / 10000 : ) * n := by                nlinarith [hpsi_div, hlog_large (n : ) hsmall, a_bound.2,                  show (0 : ) < n from by exact_mod_cast hn]          _ = 1.11 * n := by ring  rw [psi_eq_psi_coe_floor x]  calc ψ (⌊x⌋₊ : )  1.11 * ⌊x⌋₊ := hNat ⌊x⌋₊    _  1.11 * x := by nlinarith [Nat.floor_le hx.le]