Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Rosser–Schoenfeld Mertens product lower bound: chained kernel certificate infrastructure

Definition
ros_lower

by andreaskapfer · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

Certificate infrastructure for the Rosser–Schoenfeld Mertens-product lower bound e^γ log x < ∏_{p≤x} p/(p−1) on 2 ≤ x ≤ 10^8: sieve masks, moment bounds, decimal logarithm certificates, and chained block soundness. Companion of axler_theta_chain_base.

Definition code
import Definitions.Def_axler_theta_prep

set_option autoImplicit false
set_option Elab.async false
set_option maxHeartbeats 0
set_option maxRecDepth 10000000

open Finset Real
namespace RosserLower

open RosserBitSieve RosserBitMoments RosserSieveData RosserProductCertificate RosserScan

def S : ℕ := 10 ^ 15

def logTerm15 (a d i : ℕ) : ℕ :=
  S * 2 * a ^ (2 * i + 1) / ((2 * i + 1) * d ^ (2 * i + 1))

def logSeries15 (a d : ℕ) : ℕ := ((List.range 8).map (logTerm15 a d)).sum

theorem logSeries15_eq (a d : ℕ) :
    logSeries15 a d = ∑ i ∈ Finset.range 8, logTerm15 a d i := by
  rw [logSeries15, ← List.sum_toFinset (logTerm15 a d) (List.nodup_range (n := 8))]
  rfl

def logTermUp15 (a d i : ℕ) : ℕ :=
  (S * 2 * a ^ (2 * i + 1)) ⌈/⌉ ((2 * i + 1) * d ^ (2 * i + 1))

def logSeriesUp15 (a d : ℕ) : ℕ := ((List.range 8).map (logTermUp15 a d)).sum

theorem logSeriesUp15_eq (a d : ℕ) :
    logSeriesUp15 a d = ∑ i ∈ Finset.range 8, logTermUp15 a d i := by
  rw [logSeriesUp15, ← List.sum_toFinset (logTermUp15 a d) (List.nodup_range (n := 8))]
  rfl

def logLo15 (n : ℕ) : ℕ :=
  let k := AxlerTheta.log2k n
  let q := 2 ^ k
  let a := n - q
  let d := n + q
  k * 693147180300000 + logSeries15 a d

def logUp15 (n : ℕ) : ℕ :=
  let k := AxlerTheta.log2k n
  let q := 2 ^ k
  let a := n - q
  let d := n + q
  k * 693147180800001 + logSeriesUp15 a d +
    (S * 2 * a ^ 17) ⌈/⌉ (d ^ 15 * (d ^ 2 - a ^ 2))

theorem logLo15_sound (n : ℕ) (hn : 2 ≤ n) (hbig : n < 2 ^ 64) :
    (logLo15 n : ℝ) ≤ (S : ℝ) * Real.log n := by
  set k := AxlerTheta.log2k n with hk
  set q := 2 ^ k with hq
  have hqle : q ≤ n := by
    rw [hq, hk, AxlerTheta.log2k]
    exact AxlerTheta.pow_log2f_le 64 n hn hbig
  have hqpos : 0 < q := by rw [hq]; positivity
  set a := n - q with ha
  set d := n + q with hd
  have haR : (a : ℝ) = (n : ℝ) - (q : ℝ) := by
    rw [ha]
    exact Nat.cast_sub hqle
  have hdR : (d : ℝ) = (n : ℝ) + (q : ℝ) := by
    rw [hd]
    push_cast
    rfl
  have hdposN : 0 < d := by rw [hd]; omega
  have hdpos : (0 : ℝ) < d := by exact_mod_cast hdposN
  let z : ℝ := ((n : ℝ) - (q : ℝ)) / ((n : ℝ) + (q : ℝ))
  have hz_eq : z = (a : ℝ) / (d : ℝ) := by
    dsimp only [z]
    rw [← haR, ← hdR]
  have hz0 : 0 ≤ z := by
    rw [hz_eq]
    exact div_nonneg (Nat.cast_nonneg a) hdpos.le
  have hz1 : z < 1 := by
    rw [hz_eq, div_lt_one hdpos]
    rw [haR, hdR]
    have hqR : (0 : ℝ) < q := by exact_mod_cast hqpos
    linarith
  have hqR : (0 : ℝ) < q := by exact_mod_cast hqpos
  have hratio : (1 + z) / (1 - z) = (n : ℝ) / (q : ℝ) := by
    rw [hz_eq, haR, hdR]
    field_simp [hqR.ne']
    ring
  have h := Real.sum_range_le_log_div hz0 hz1 8
  have hlogq : Real.log (q : ℝ) = (k : ℝ) * Real.log 2 := by
    rw [show (q : ℝ) = (2 : ℝ) ^ k from by rw [hq]; push_cast; rfl, Real.log_pow]
  rw [hratio, Real.log_div (by positivity : (n : ℝ) ≠ 0)
    hqR.ne', hlogq] at h
  have hgoal : (logLo15 n : ℝ) =
      ((k * 693147180300000 : ℕ) : ℝ) +
        ∑ i ∈ Finset.range 8,
          ((S * 2 * a ^ (2 * i + 1) / ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ) := by
    simp only [logLo15, ← hk, ← hq, ← ha, ← hd]
    rw [logSeries15_eq]
    simp only [logTerm15]
    push_cast
    rfl
  have hK : ((k * 693147180300000 : ℕ) : ℝ) ≤
      (S : ℝ) * ((k : ℝ) * Real.log 2) := by
    have h2 := Real.log_two_gt_d9.le
    calc ((k * 693147180300000 : ℕ) : ℝ)
        = (k : ℝ) * 693147180300000 := by push_cast; ring
      _ = (S : ℝ) * ((k : ℝ) * (0.6931471803 : ℝ)) := by
          rw [show (0.6931471803 : ℝ) = 693147180300000 / 1000000000000000 by norm_num]
          norm_num [S]
          ring
      _ = (S : ℝ) * (k : ℝ) * (0.6931471803 : ℝ) := by ring
      _ ≤ (S : ℝ) * (k : ℝ) * Real.log 2 :=
          mul_le_mul_of_nonneg_left h2 (mul_nonneg (by norm_num [S])
            (Nat.cast_nonneg k))
      _ = (S : ℝ) * ((k : ℝ) * Real.log 2) := by ring
  have hterm : ∀ i, ((S * 2 * a ^ (2 * i + 1) /
        ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ) ≤
      (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) := by
    intro i
    calc ((S * 2 * a ^ (2 * i + 1) /
          ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ)
        ≤ ((S * 2 * a ^ (2 * i + 1) : ℕ) : ℝ) /
            (((2 * i + 1) * d ^ (2 * i + 1) : ℕ) : ℝ) := AxlerTheta.cast_div_le_real
      _ = ((S : ℝ) * 2 * (a : ℝ) ^ (2 * i + 1)) /
            (((2 * i + 1) : ℝ) * (d : ℝ) ^ (2 * i + 1)) := by push_cast; ring
      _ = (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) := by
          have h2i1 : ((2 * i + 1 : ℕ) : ℝ) ≠ 0 := by positivity
          rw [hz_eq, div_pow]
          field_simp [hdpos.ne', h2i1]
  have hsum : (∑ i ∈ Finset.range 8,
        ((S * 2 * a ^ (2 * i + 1) /
          ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ)) ≤
      (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) := by
    calc (∑ i ∈ Finset.range 8, ((S * 2 * a ^ (2 * i + 1) /
            ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ))
        ≤ ∑ i ∈ Finset.range 8,
            (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) :=
          Finset.sum_le_sum (fun i _ => hterm i)
      _ = (S : ℝ) * 2 * (∑ i ∈ Finset.range 8,
            z ^ (2 * i + 1) / (2 * i + 1)) := by
          rw [Finset.mul_sum]
      _ ≤ (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) := by
          have h2 : (2 : ℝ) * (∑ i ∈ Finset.range 8,
              z ^ (2 * i + 1) / (2 * i + 1)) ≤
              Real.log n - (k : ℝ) * Real.log 2 := by linarith only [h]
          calc (S : ℝ) * 2 * (∑ i ∈ Finset.range 8,
                z ^ (2 * i + 1) / (2 * i + 1))
              = (S : ℝ) * (2 * (∑ i ∈ Finset.range 8,
                z ^ (2 * i + 1) / (2 * i + 1))) := by ring
            _ ≤ (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) :=
                mul_le_mul_of_nonneg_left h2 (by norm_num [S])
  rw [hgoal]
  have hfinal : (S : ℝ) * ((k : ℝ) * Real.log 2) +
      (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) =
      (S : ℝ) * Real.log n := by ring
  linarith only [hK, hsum, hfinal]

theorem logUp15_sound (n : ℕ) (hn : 2 ≤ n) (hbig : n < 2 ^ 64) :
    (S : ℝ) * Real.log n ≤ (logUp15 n : ℝ) := by
  set k := AxlerTheta.log2k n with hk
  set q := 2 ^ k with hq
  have hqle : q ≤ n := by
    rw [hq, hk, AxlerTheta.log2k]
    exact AxlerTheta.pow_log2f_le 64 n hn hbig
  have hqpos : 0 < q := by rw [hq]; positivity
  set a := n - q with ha
  set d := n + q with hd
  have haR : (a : ℝ) = (n : ℝ) - (q : ℝ) := by
    rw [ha]
    exact Nat.cast_sub hqle
  have hdR : (d : ℝ) = (n : ℝ) + (q : ℝ) := by
    rw [hd]
    push_cast
    rfl
  have hda : a < d := by rw [ha, hd]; omega
  have hd2a2 : 0 < d ^ 2 - a ^ 2 := by
    have h : a ^ 2 < d ^ 2 := Nat.pow_lt_pow_left hda (by norm_num)
    omega
  have hdposN : 0 < d := by rw [hd]; omega
  have hdpos : (0 : ℝ) < d := by exact_mod_cast hdposN
  let z : ℝ := ((n : ℝ) - (q : ℝ)) / ((n : ℝ) + (q : ℝ))
  have hz_eq : z = (a : ℝ) / (d : ℝ) := by
    dsimp only [z]
    rw [← haR, ← hdR]
  have hz0 : 0 ≤ z := by
    rw [hz_eq]
    exact div_nonneg (Nat.cast_nonneg a) hdpos.le
  have hz1 : z < 1 := by
    rw [hz_eq, div_lt_one hdpos]
    rw [haR, hdR]
    have hqR : (0 : ℝ) < q := by exact_mod_cast hqpos
    linarith
  have hqR : (0 : ℝ) < q := by exact_mod_cast hqpos
  have hratio : (1 + z) / (1 - z) = (n : ℝ) / (q : ℝ) := by
    rw [hz_eq, haR, hdR]
    field_simp [hqR.ne']
    ring
  have h := Real.log_div_le_sum_range_add hz0 hz1 8
  have hlogq : Real.log (q : ℝ) = (k : ℝ) * Real.log 2 := by
    rw [show (q : ℝ) = (2 : ℝ) ^ k from by rw [hq]; push_cast; rfl, Real.log_pow]
  rw [hratio, Real.log_div (by positivity : (n : ℝ) ≠ 0)
    hqR.ne', hlogq] at h
  have hgoal : (logUp15 n : ℝ) =
      ((k * 693147180800001 : ℕ) : ℝ) +
        (∑ i ∈ Finset.range 8,
          (((S * 2 * a ^ (2 * i + 1)) ⌈/⌉
            ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ)) +
        (((S * 2 * a ^ 17) ⌈/⌉ (d ^ 15 * (d ^ 2 - a ^ 2)) : ℕ) : ℝ) := by
    simp only [logUp15, ← hk, ← hq, ← ha, ← hd]
    rw [logSeriesUp15_eq]
    simp only [logTermUp15]
    push_cast
    rfl
  have hK : (S : ℝ) * ((k : ℝ) * Real.log 2) ≤
      ((k * 693147180800001 : ℕ) : ℝ) := by
    have h2 := Real.log_two_lt_d9.le
    calc (S : ℝ) * ((k : ℝ) * Real.log 2)
        ≤ (S : ℝ) * ((k : ℝ) * (0.6931471808 : ℝ)) := by
          apply mul_le_mul_of_nonneg_left _ (by norm_num [S])
          exact mul_le_mul_of_nonneg_left h2 (Nat.cast_nonneg k)
      _ = (k : ℝ) * 693147180800000 := by
          rw [show (0.6931471808 : ℝ) = 6931471808 / 10000000000 by norm_num]
          norm_num [S]
          ring
      _ ≤ (k : ℝ) * 693147180800001 := by
          have : (0 : ℝ) ≤ (k : ℝ) := Nat.cast_nonneg k
          nlinarith
      _ = ((k * 693147180800001 : ℕ) : ℝ) := by push_cast; ring
  have hterm : ∀ i, (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) ≤
      (((S * 2 * a ^ (2 * i + 1)) ⌈/⌉
        ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ) := by
    intro i
    calc (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1))
        = ((S : ℝ) * 2 * (a : ℝ) ^ (2 * i + 1)) /
            (((2 * i + 1) : ℝ) * (d : ℝ) ^ (2 * i + 1)) := by
          have h2i1 : ((2 * i + 1 : ℕ) : ℝ) ≠ 0 := by positivity
          rw [hz_eq, div_pow]
          field_simp [hdpos.ne', h2i1]
      _ = ((S * 2 * a ^ (2 * i + 1) : ℕ) : ℝ) /
            (((2 * i + 1) * d ^ (2 * i + 1) : ℕ) : ℝ) := by push_cast; ring
      _ ≤ (((S * 2 * a ^ (2 * i + 1)) ⌈/⌉
            ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ) :=
          AxlerTheta.real_div_le_cast_ceilDiv (by positivity)
  have htail : (S : ℝ) * (2 * (z ^ 17 / (1 - z ^ 2))) ≤
      (((S * 2 * a ^ 17) ⌈/⌉ (d ^ 15 * (d ^ 2 - a ^ 2)) : ℕ) : ℝ) := by
    have hd2a2R : (0 : ℝ) < (d : ℝ) ^ 2 - (a : ℝ) ^ 2 := by
      have hle : a ^ 2 ≤ d ^ 2 := le_of_lt (by omega : a ^ 2 < d ^ 2)
      rw [← Nat.cast_pow, ← Nat.cast_pow, ← Nat.cast_sub hle]
      exact_mod_cast hd2a2
    calc (S : ℝ) * (2 * (z ^ 17 / (1 - z ^ 2)))
        = (S : ℝ) * 2 * (a : ℝ) ^ 17 /
            ((d : ℝ) ^ 15 * ((d : ℝ) ^ 2 - (a : ℝ) ^ 2)) := by
          rw [hz_eq, div_pow]
          field_simp [hdpos.ne', hd2a2R.ne']
      _ ≤ (((S * 2 * a ^ 17) ⌈/⌉
            (d ^ 15 * (d ^ 2 - a ^ 2)) : ℕ) : ℝ) := by
          have hle : a ^ 2 ≤ d ^ 2 := by omega
          have h := AxlerTheta.real_div_le_cast_ceilDiv (x := S * 2 * a ^ 17)
            (m := d ^ 15 * (d ^ 2 - a ^ 2)) (by positivity)
          push_cast [Nat.cast_sub hle] at h
          exact h
  have hsplit : (S : ℝ) * (2 * ((∑ i ∈ Finset.range 8,
        z ^ (2 * i + 1) / (2 * i + 1)) + z ^ 17 / (1 - z ^ 2))) =
      (∑ i ∈ Finset.range 8,
        (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1))) +
      (S : ℝ) * (2 * (z ^ 17 / (1 - z ^ 2))) := by
    rw [show (S : ℝ) * (2 * ((∑ i ∈ Finset.range 8,
          z ^ (2 * i + 1) / (2 * i + 1)) + z ^ 17 / (1 - z ^ 2))) =
        (S : ℝ) * 2 * (∑ i ∈ Finset.range 8,
          z ^ (2 * i + 1) / (2 * i + 1)) +
        (S : ℝ) * 2 * (z ^ 17 / (1 - z ^ 2)) from by ring]
    rw [Finset.mul_sum]
    ring
  have h2 : (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) ≤
      (S : ℝ) * (2 * ((∑ i ∈ Finset.range 8,
        z ^ (2 * i + 1) / (2 * i + 1)) + z ^ 17 / (1 - z ^ 2))) := by
    have h' : (1 : ℝ) / 2 * (Real.log n - (k : ℝ) * Real.log 2) ≤
        (∑ i ∈ Finset.range 8, z ^ (2 * i + 1) / (2 * i + 1)) +
          z ^ 17 / (1 - z ^ 2) := h
    have h2' : Real.log n - (k : ℝ) * Real.log 2 ≤
        2 * ((∑ i ∈ Finset.range 8, z ^ (2 * i + 1) / (2 * i + 1)) +
          z ^ 17 / (1 - z ^ 2)) := by linarith only [h']
    have hs0 : (0 : ℝ) ≤ (S : ℝ) := by norm_num [S]
    exact mul_le_mul_of_nonneg_left h2' hs0
  rw [hgoal]
  have hbound :
      (S : ℝ) * ((k : ℝ) * Real.log 2) +
          (∑ i ∈ Finset.range 8, (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1))) +
          ((S : ℝ) * (2 * (z ^ 17 / (1 - z ^ 2)))) ≤
      (((k * 693147180800001 : ℕ) : ℝ) +
          (∑ i ∈ Finset.range 8,
            (((S * 2 * a ^ (2 * i + 1)) ⌈/⌉
              ((2 * i + 1) * d ^ (2 * i + 1)) : ℕ) : ℝ)) +
          (((S * 2 * a ^ 17) ⌈/⌉ (d ^ 15 * (d ^ 2 - a ^ 2)) : ℕ) : ℝ)) := by
    exact add_le_add
      (add_le_add hK (Finset.sum_le_sum (fun i _ => hterm i)))
      htail
  rw [hsplit] at h2
  have hfinal : (S : ℝ) * ((k : ℝ) * Real.log 2) +
      (S : ℝ) * (Real.log n - (k : ℝ) * Real.log 2) =
      (S : ℝ) * Real.log n := by ring
  linarith only [h2, hbound, hfinal]

/-- Upper bound: `S * log (log b) ≤ llUp b` (when the sub is exact). -/
theorem llUp_sound (b : ℕ) (h2 : 2 ≤ b) (hb8 : b ≤ 10 ^ 8)
    (hlo2 : 2 ≤ logUp15 b) (hlo64 : logUp15 b < 2 ^ 64)
    (hsub : logLo15 S ≤ logUp15 (logUp15 b)) :
    (S : ℝ) * Real.log (Real.log b) ≤
      ((logUp15 (logUp15 b) - logLo15 S : ℕ) : ℝ) := by
  have hb64 : b < 2 ^ 64 := by omega
  have hS2 : 2 ≤ S := by norm_num [S]
  have hS64 : S < 2 ^ 64 := by norm_num [S]
  have hSpos : (0 : ℝ) < (S : ℝ) := by norm_num [S]
  have hlo : (logLo15 S : ℝ) ≤ (S : ℝ) * Real.log S := logLo15_sound S hS2 hS64
  have hhi : (S : ℝ) * Real.log b ≤ (logUp15 b : ℝ) := logUp15_sound b h2 hb64
  have hhi_hi : (S : ℝ) * Real.log (logUp15 b : ℝ) ≤
      (logUp15 (logUp15 b) : ℝ) := logUp15_sound (logUp15 b) hlo2 hlo64
  have hcast : ((logUp15 (logUp15 b) - logLo15 S : ℕ) : ℝ) =
      (logUp15 (logUp15 b) : ℝ) - (logLo15 S : ℝ) := Nat.cast_sub hsub
  have hlogb : (0 : ℝ) < Real.log b := Real.log_pos (by exact_mod_cast (show 1 < b by omega))
  have hdiv : Real.log b ≤ (logUp15 b : ℝ) / (S : ℝ) := by
    rw [le_div_iff₀ hSpos]
    linarith [hhi]
  have hlogdiv : Real.log (Real.log b) ≤ Real.log ((logUp15 b : ℝ) / (S : ℝ)) :=
    Real.log_le_log hlogb hdiv
  have hsplit : Real.log ((logUp15 b : ℝ) / (S : ℝ)) =
      Real.log (logUp15 b : ℝ) - Real.log S := by
    apply Real.log_div
    · have : (2 : ℝ) ≤ (logUp15 b : ℝ) := by exact_mod_cast hlo2
      linarith
    · exact hSpos.ne'
  rw [hsplit] at hlogdiv
  rw [hcast]
  have hmain : (S : ℝ) * Real.log (Real.log b) ≤
      (logUp15 (logUp15 b) : ℝ) - (logLo15 S : ℝ) := by
    have hmul : (S : ℝ) * Real.log (Real.log b) ≤
        (S : ℝ) * (Real.log (logUp15 b : ℝ) - Real.log S) :=
      mul_le_mul_of_nonneg_left hlogdiv hSpos.le
    have hdist : (S : ℝ) * (Real.log (logUp15 b : ℝ) - Real.log S) =
        (S : ℝ) * Real.log (logUp15 b : ℝ) - (S : ℝ) * Real.log S := by ring
    rw [hdist] at hmul
    linarith [hhi_hi, hlo]
  exact hmain

-- ============================================================
-- Part B: prime product bridge, moments exactness, increment bound
-- ============================================================

noncomputable def logProd (n : ℕ) : ℝ := Real.log (eulerProduct n)

theorem eulerProduct_pos (n : ℕ) : 0 < eulerProduct n := by
  unfold eulerProduct
  apply Finset.prod_pos
  intro p hp
  have hp2 : (2 : ℝ) ≤ (p : ℝ) := by
    exact_mod_cast (Nat.mem_primesLE.mp hp).2.two_le
  exact div_pos (by linarith) (by linarith)

theorem eulerProduct_sdiff (a b : ℕ) (hab : a ≤ b) :
    eulerProduct b / eulerProduct a =
      ∏ p ∈ Nat.primesLE b \ Nat.primesLE a, (p : ℝ) / ((p : ℝ) - 1) := by
  have hne := (eulerProduct_pos a).ne'
  unfold eulerProduct
  rw [← Finset.prod_sdiff (s₁ := Nat.primesLE a) (s₂ := Nat.primesLE b)
    (Nat.primesLE_mono hab) (f := fun p : ℕ => (p : ℝ) / ((p : ℝ) - 1))]
  exact mul_div_cancel_right₀ _ hne

theorem logProd_mono (a b : ℕ) (hab : a ≤ b) : logProd a ≤ logProd b := by
  apply Real.log_le_log (eulerProduct_pos a)
  exact eulerProduct_mono hab

theorem sum_log_sdiff (a b : ℕ) (hab : a ≤ b) :
    logProd b - logProd a =
      ∑ p ∈ Nat.primesLE b \ Nat.primesLE a,
        Real.log (1 + 1 / ((p : ℝ) - 1)) := by
  have hb := eulerProduct_pos b
  have ha := eulerProduct_pos a
  have h1 : logProd b - logProd a =
      Real.log (∏ p ∈ Nat.primesLE b \ Nat.primesLE a, (p : ℝ) / ((p : ℝ) - 1)) := by
    rw [logProd, logProd, ← Real.log_div hb.ne' ha.ne', eulerProduct_sdiff a b hab]
  rw [h1, Real.log_prod]
  · apply Finset.sum_congr rfl
    intro p hp
    have hp2 : (2 : ℝ) ≤ (p : ℝ) := by
      exact_mod_cast (Nat.mem_primesLE.mp (Finset.mem_sdiff.mp hp).1).2.two_le
    have hp1 : (p : ℝ) - 1 ≠ 0 := by linarith
    rw [show (p : ℝ) / ((p : ℝ) - 1) = 1 + 1 / ((p : ℝ) - 1) from by
      field_simp; ring]
  · intro p hp
    have hp2 : (2 : ℝ) ≤ (p : ℝ) := by
      exact_mod_cast (Nat.mem_primesLE.mp (Finset.mem_sdiff.mp hp).1).2.two_le
    exact ne_of_gt (div_pos (by linarith) (by linarith))

theorem filter_range_pad_aux (w len k : ℕ)
    (h : ∀ i, w.testBit i = true → i < len) :
    (List.range (len + k)).filter (fun i => w.testBit i) =
      (List.range len).filter (fun i => w.testBit i) := by
  induction k with
  | zero => simp
  | succ k ih =>
    rw [show len + (k + 1) = (len + k) + 1 by omega, List.range_succ, List.filter_append, ih]
    have hf : w.testBit (len + k) = false := by
      cases hb : w.testBit (len + k) with
      | false => rfl
      | true => exact absurd (h _ hb) (by omega)
    simp [hf]

theorem filter_range_pad (w len N : ℕ) (hw : w < 2 ^ len) (hle : len ≤ N) :
    (List.range N).filter (fun i => w.testBit i) =
      (List.range len).filter (fun i => w.testBit i) := by
  have hlt : ∀ i, w.testBit i = true → i < len := by
    intro i hi
    by_contra hcon
    push_neg at hcon
    have hw' : w < 2 ^ i := lt_of_lt_of_le hw (Nat.pow_le_pow_right (by norm_num) hcon)
    rw [Nat.testBit_eq_false_of_lt hw'] at hi
    exact Bool.noConfusion hi
  have := filter_range_pad_aux w len (N - len) hlt
  rwa [show len + (N - len) = N by omega] at this

theorem windowMoments_prime_offsets (base top a b : ℕ)
    (hbase : base ≤ a) (hb1 : 1 ≤ base) (hsq : top ≤ base * base)
    (hab : a < b) (hbtop : b ≤ top) (h8 : b ≤ 10 ^ 8) (hlen : b - a ≤ 2 ^ 13) :
    windowMoments (RosserSieveData.mask base top) (a - base) (b - a) =
      moments (((List.range (b - a)).filter
        (fun i => decide (Nat.Prime (a + 1 + i)))).map (fun i => i + 1)) := by
  set m := RosserSieveData.mask base top with hm
  set w := m / 2 ^ (a - base) % 2 ^ (b - a) with hw
  have hwlt : w < 2 ^ (b - a) := by
    rw [hw]
    exact Nat.mod_lt _ (Nat.pow_pos (by norm_num))
  have hbit : ∀ i, i < b - a → w.testBit i = decide (Nat.Prime (a + 1 + i)) := by
    intro i hi
    have hs : w.testBit i = m.testBit (a - base + i) := by
      rw [hw]
      exact AxlerSieve.slice_bit (base := base) (a := a) (b := b) (m := m) hi
    rw [hs]
    by_cases hp : Nat.Prime (a + 1 + i)
    · rw [decide_eq_true hp]
      exact (AxlerSieve.mask_bit_iff (base := base) (top := top) (a := a) (i := i)
        hbase hb1 hsq (by omega) (by omega)).mpr hp
    · rw [decide_eq_false hp]
      apply Bool.eq_false_iff.mpr
      intro hb2
      exact hp ((AxlerSieve.mask_bit_iff (base := base) (top := top) (a := a) (i := i)
        hbase hb1 hsq (by omega) (by omega)).mp hb2)
  rw [windowMoments_sound]
  rw [show windowOffsets 13 m (a - base) (b - a) =
      (enumBits 13 0 w).map (fun d => d + 1) from by
    simp only [RosserBitSieve.windowOffsets]
    rw [← hw]]
  apply moments_perm
  apply List.Perm.map
  refine (RosserPackedMoments.enumBits_perm_filter 13 w).trans ?_
  rw [filter_range_pad w (b - a) (2 ^ 13) hwlt hlen]
  exact List.Perm.of_eq (List.filter_congr (fun i hi => hbit i (List.mem_range.mp hi)))

theorem log_one_add_ge (a b p : ℕ) (ha : 2 ≤ a) (hap : a < p) (hpb : p ≤ b) :
    1 / ((a : ℝ) - 1 / 2) - ((p : ℝ) - (a : ℝ)) / ((a : ℝ) - 1 / 2) ^ 2
      + ((p : ℝ) - (a : ℝ)) ^ 2 / (((a : ℝ) - 1 / 2) ^ 2 * ((b : ℝ) - 1 / 2))
    ≤ Real.log (1 + 1 / ((p : ℝ) - 1)) := by
  have hp2 : 2 ≤ p := by omega
  have hp1 : (0 : ℝ) < (p : ℝ) - 1 := by
    have : (2 : ℝ) ≤ (p : ℝ) := by exact_mod_cast hp2
    linarith
  set x0 : ℝ := (a : ℝ) - 1 / 2 with hx0
  set y : ℝ := (p : ℝ) - 1 / 2 with hy
  set Y : ℝ := (b : ℝ) - 1 / 2 with hY
  have hx0pos : 0 < x0 := by
    rw [hx0]
    have : (2 : ℝ) ≤ (a : ℝ) := by exact_mod_cast ha
    linarith
  have hypos : 0 < y := by
    rw [hy]
    have : (1 : ℝ) < (p : ℝ) := by exact_mod_cast (show 1 < p by omega)
    linarith
  have hYpos : 0 < Y := by
    rw [hY]
    have : (1 : ℝ) ≤ (b : ℝ) := by exact_mod_cast (show 1 ≤ b by omega)
    linarith
  have hyY : y ≤ Y := by
    rw [hy, hY]
    exact sub_le_sub_right (by exact_mod_cast hpb) (1 / 2)
  have hxy : (p : ℝ) - (a : ℝ) = y - x0 := by
    rw [hy, hx0]
    ring
  rw [hxy]
  have hx : 0 ≤ 1 / ((p : ℝ) - 1) := by positivity
  have hpade := Real.le_log_one_add_of_nonneg hx
  have hp_eq : 2 * (1 / ((p : ℝ) - 1)) / ((1 / ((p : ℝ) - 1)) + 2) = 1 / y := by
    rw [hy]
    have h1 : (p : ℝ) - 1 ≠ 0 := by linarith
    have h2 : (p : ℝ) - 1 / 2 ≠ 0 := by
      have : (1 : ℝ) < (p : ℝ) := by exact_mod_cast (show 1 < p by omega)
      linarith
    have h3 : 2 * (p : ℝ) - 1 ≠ 0 := by
      have : (1 : ℝ) < (p : ℝ) := by exact_mod_cast (show 1 < p by omega)
      linarith
    field_simp [h1, h2, h3]
    ring
  have hid : 1 / y = 1 / x0 - (y - x0) / x0 ^ 2 + (y - x0) ^ 2 / (x0 ^ 2 * y) := by
    field_simp [hx0pos.ne', hypos.ne']
    ring
  have hlast : (y - x0) ^ 2 / (x0 ^ 2 * Y) ≤ (y - x0) ^ 2 / (x0 ^ 2 * y) := by
    have hd2 : x0 ^ 2 * y ≤ x0 ^ 2 * Y := by nlinarith
    have hone : 1 / (x0 ^ 2 * Y) ≤ 1 / (x0 ^ 2 * y) :=
      one_div_le_one_div_of_le (by positivity) hd2
    have hone' : (x0 ^ 2 * Y)⁻¹ ≤ (x0 ^ 2 * y)⁻¹ := by
      simpa only [one_div] using hone
    rw [div_eq_mul_inv, div_eq_mul_inv]
    exact mul_le_mul_of_nonneg_left hone' (sq_nonneg _)
  calc 1 / x0 - (y - x0) / x0 ^ 2 + (y - x0) ^ 2 / (x0 ^ 2 * Y)
      ≤ 1 / x0 - (y - x0) / x0 ^ 2 + (y - x0) ^ 2 / (x0 ^ 2 * y) := by
        linarith only [hlast]
    _ = 1 / y := hid.symm
    _ = 2 * (1 / ((p : ℝ) - 1)) / ((1 / ((p : ℝ) - 1)) + 2) := hp_eq.symm
    _ ≤ Real.log (1 + 1 / ((p : ℝ) - 1)) := hpade

def blockNum (s : Moments) (a b : ℕ) : ℕ :=
  S * ((2 * s.count * (2 * a - 1) * (2 * b - 1) + 8 * s.second) -
        4 * s.first * (2 * b - 1)) /
    ((2 * a - 1) * (2 * a - 1) * (2 * b - 1))

def incrOf (s : Moments) (a b : ℕ) : ℕ :=
  if s.count = 1 then logSeries15 1 (2 * (a + s.first) - 1)
  else blockNum s a b

def gammaUpS : ℕ := 577216170667183

structure Blk where
  a : ℕ
  b : ℕ
  L : ℕ
  L' : ℕ
  deriving DecidableEq, Repr

structure Grp where
  lo : ℕ
  base : ℕ
  top : ℕ
  lin : ℕ
  lfin : ℕ
  blks : List Blk
  deriving Repr

theorem slice_eq (m shift len : ℕ) :
    (m >>> shift) &&& (2 ^ len - 1) = m / 2 ^ shift % 2 ^ len := by
  rw [Nat.shiftRight_eq_div_pow, Nat.and_two_pow_sub_one_eq_mod]

def blkOK (gbase m : ℕ) (B : Blk) (L : ℕ) : Bool × ℕ :=
  if B.b = 0 then (false, L)
  else
    forceNat ((m >>> (B.a - gbase)) &&& (2 ^ (B.b - B.a) - 1)) fun w =>
    forceNat (logUp15 B.b) fun lhi =>
    forceNat (logUp15 lhi) fun hhi =>
    let ok := decide (2 ≤ lhi ∧ lhi < 2 ^ 64 ∧ logLo15 S ≤ hhi ∧
      gammaUpS + (hhi - logLo15 S) < L)
    forceNat (L + incrOf (fastMoments 10 1 w) B.a B.b) fun L' => (ok, L')

def grpGo (G : Grp) (gbase m : ℕ) : ℕ → ℕ → List Blk → Bool
  | prev, L, [] => (prev = G.top) && (L = G.lfin)
  | prev, L, B :: rest =>
    match blkOK gbase m B L with
    | (ok, L') => (prev = B.a) && ok && grpGo G gbase m B.b L' rest

def grpOK (G : Grp) : Bool :=
  forceNat (mask G.base G.top) fun m => grpGo G G.base m G.base G.lin G.blks

def grpWF (G : Grp) : Bool :=
  decide (3 ≤ G.lo ∧ (G.base = G.lo ∨ (Nat.Prime G.lo ∧ G.base = G.lo + 1)) ∧
    G.base < G.top ∧ G.top ≤ G.base * G.base ∧ G.top ≤ 10 ^ 8) &&
  G.blks.all (fun B => decide (G.base ≤ B.a ∧ B.a < B.b ∧ B.b ≤ G.top ∧
    B.b - B.a ≤ 2 ^ 13 ∧ B.b ≤ 10 ^ 8))

def blkSpec (gbase m : ℕ) (B : Blk) (L L' : ℕ) : Prop :=
  L' = L + incrOf (windowMoments m (B.a - gbase) (B.b - B.a)) B.a B.b ∧
  ∃ lhi hhi : ℕ, lhi = logUp15 B.b ∧ hhi = logUp15 lhi ∧
    2 ≤ lhi ∧ lhi < 2 ^ 64 ∧ logLo15 S ≤ hhi ∧
    gammaUpS + (hhi - logLo15 S) < L

theorem blkOK_spec {gbase m : ℕ} {B : Blk} {L L' : ℕ}
    (h : blkOK gbase m B L = (true, L')) :
    blkSpec gbase m B L L' := by
  unfold blkOK blkSpec at *
  by_cases hz : B.b = 0
  · rw [if_pos hz] at h
    simp at h
  rw [if_neg hz] at h
  simp only [forceNat_eq] at h ⊢
  have hfst : decide (2 ≤ logUp15 B.b ∧ logUp15 B.b < 2 ^ 64 ∧
      logLo15 S ≤ logUp15 (logUp15 B.b) ∧
      gammaUpS + (logUp15 (logUp15 B.b) - logLo15 S) < L) = true :=
    congrArg Prod.fst h
  have hsnd : L + incrOf (windowMoments m (B.a - gbase) (B.b - B.a)) B.a B.b = L' := by
    simpa only [slice_eq, windowMoments] using congrArg Prod.snd h
  obtain ⟨h1, h2, h3, h4⟩ := of_decide_eq_true hfst
  exact ⟨hsnd.symm, _, _, rfl, rfl, h1, h2, h3, h4⟩

def grpSpec (G : Grp) (gbase m : ℕ) : ℕ → ℕ → List Blk → Prop
  | prev, L, [] => prev = G.top ∧ L = G.lfin
  | prev, L, B :: rest =>
    prev = B.a ∧ ∃ L', blkSpec gbase m B L L' ∧ grpSpec G gbase m B.b L' rest

theorem blkOK_spec' {gbase m : ℕ} {B : Blk} {L L' : ℕ} {ok : Bool}
    (h : blkOK gbase m B L = (ok, L')) (hok : ok = true) :
    blkSpec gbase m B L L' :=
  blkOK_spec (by rw [hok] at h; exact h)

theorem grpGo_spec (G : Grp) (gbase m : ℕ) :
    ∀ (prev L : ℕ) (blks : List Blk),
      grpGo G gbase m prev L blks = true → grpSpec G gbase m prev L blks := by
  intro prev L blks
  induction blks generalizing prev L with
  | nil =>
    intro h
    simp only [grpGo, grpSpec] at h ⊢
    simpa [and_assoc] using h
  | cons B rest ih =>
    intro h
    simp only [grpGo] at h
    cases hb : blkOK gbase m B L with
    | mk ok L' =>
      rw [hb] at h
      simp only [Bool.and_eq_true, decide_eq_true_eq] at h
      obtain ⟨⟨hprev, hok⟩, hrest⟩ := h
      exact ⟨hprev, L', blkOK_spec' hb hok, ih B.b L' hrest⟩

theorem grpOK_spec {G : Grp} (h : grpOK G = true) :
    grpSpec G G.base (mask G.base G.top) G.base G.lin G.blks := by
  unfold grpOK at h
  simp only [forceNat_eq] at h
  exact grpGo_spec G G.base (mask G.base G.top) G.base G.lin G.blks h

theorem grpWF_spec {G : Grp} (h : grpWF G = true) :
    3 ≤ G.lo ∧ (G.base = G.lo ∨ (Nat.Prime G.lo ∧ G.base = G.lo + 1)) ∧
      G.base < G.top ∧ G.top ≤ G.base * G.base ∧ G.top ≤ 10 ^ 8 ∧
      ∀ B ∈ G.blks, G.base ≤ B.a ∧ B.a < B.b ∧ B.b ≤ G.top ∧
        B.b - B.a ≤ 2 ^ 13 ∧ B.b ≤ 10 ^ 8 := by
  rw [grpWF, Bool.and_eq_true] at h
  obtain ⟨h1, h2⟩ := h
  have h1' := of_decide_eq_true h1
  refine ⟨h1'.1, h1'.2.1, h1'.2.2.1, h1'.2.2.2.1, h1'.2.2.2.2, ?_⟩
  exact fun B hB => of_decide_eq_true (List.all_eq_true.mp h2 B hB)

theorem cast_sum_eq (ds : List ℕ) :
    ((ds.sum : ℕ) : ℝ) = (ds.map (fun d : ℕ => (d : ℝ))).sum := by
  induction ds with
  | nil => simp
  | cons d ds ih => simp only [List.sum_cons, List.map_cons, List.sum_cons, Nat.cast_add, ih]

theorem cast_sum_sq_eq (ds : List ℕ) :
    (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) =
      (ds.map (fun d : ℕ => (d : ℝ) ^ 2)).sum := by
  induction ds with
  | nil => simp
  | cons d ds ih =>
    simp only [List.map_cons, List.sum_cons, Nat.cast_add, Nat.cast_pow, ih]

theorem blockNum_le_log (a b : ℕ) (ds : List ℕ)
    (ha : 2 ≤ a) (hab : a < b)
    (hds : ds.Nodup) (hpos : ∀ d ∈ ds, 1 ≤ d) (hle : ∀ d ∈ ds, d ≤ b - a)
    (hprime : ∀ d ∈ ds, Nat.Prime (a + d))
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b → p - a ∈ ds) :
    (blockNum (moments ds) a b : ℝ) ≤ (S : ℝ) * (logProd b - logProd a) := by
  have hb : a ≤ b := le_of_lt hab
  set ps := ds.map (fun d => a + d) with hpsdef
  have hinj : Function.Injective (fun d : ℕ => a + d) := by
    intro x y h
    change a + x = a + y at h
    omega
  have hps : ps.Nodup := by
    rw [hpsdef]
    exact List.Nodup.map hinj hds
  have hpsset : ps.toFinset = Nat.primesLE b \ Nat.primesLE a := by
    apply Finset.Subset.antisymm
    · intro p hp
      obtain ⟨d, hd, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hp)
      rw [Finset.mem_sdiff]
      constructor
      · exact Nat.mem_primesLE.mpr ⟨by have := hle d hd; omega, hprime d hd⟩
      · intro hpa
        have hple : a + d ≤ a := (Nat.mem_primesLE.mp hpa).1
        have := hpos d hd
        omega
    · intro p hp
      obtain ⟨hpb, hpa⟩ := Finset.mem_sdiff.mp hp
      obtain ⟨hpb', hpp⟩ := Nat.mem_primesLE.mp hpb
      have hap : a < p := by
        by_contra h
        exact hpa (Nat.mem_primesLE.mpr ⟨by omega, hpp⟩)
      apply List.mem_toFinset.mpr
      exact List.mem_map.mpr ⟨p - a, hcover p hpp hap hpb', by omega⟩
  have hlogsum : logProd b - logProd a =
      ds.toFinset.sum (fun d : ℕ => Real.log (1 + 1 / ((a : ℝ) + d - 1))) := by
    rw [sum_log_sdiff a b hb, ← hpsset, List.sum_toFinset _ hps, hpsdef, List.map_map]
    rw [List.sum_toFinset (l := ds)
      (fun d : ℕ => Real.log (1 + 1 / ((a : ℝ) + d - 1))) hds]
    congr 1
    apply List.map_congr_left
    intro d hd
    simp only [Function.comp_def]
    have e : ((a + d : ℕ) : ℝ) - 1 = (a : ℝ) + d - 1 := by push_cast; ring
    rw [e]
  set x0 : ℝ := (a : ℝ) - 1 / 2 with hx0
  set Y : ℝ := (b : ℝ) - 1 / 2 with hY
  have hx0pos : 0 < x0 := by
    rw [hx0]
    have : (2 : ℝ) ≤ (a : ℝ) := by exact_mod_cast ha
    linarith
  have hYpos : 0 < Y := by
    rw [hY]
    have : (1 : ℝ) ≤ (b : ℝ) := by exact_mod_cast (show 1 ≤ b by omega)
    linarith
  set Lsum := ds.toFinset.sum
    (fun d => 1 / x0 - (d : ℝ) / x0 ^ 2 + (d : ℝ) ^ 2 / (x0 ^ 2 * Y)) with hLsum
  have hlow : Lsum = (ds.toFinset.card : ℝ) / x0 -
      (ds.toFinset.sum (fun d : ℕ => (d : ℝ))) / x0 ^ 2 +
      (ds.toFinset.sum (fun d : ℕ => (d : ℝ) ^ 2)) / (x0 ^ 2 * Y) := by
    rw [hLsum]
    rw [Finset.sum_add_distrib, Finset.sum_sub_distrib]
    rw [Finset.sum_const, nsmul_eq_mul]
    rw [← Finset.sum_div (s := ds.toFinset) (f := fun d : ℕ => (d : ℝ)) (a := x0 ^ 2)]
    rw [← Finset.sum_div (s := ds.toFinset) (f := fun d : ℕ => (d : ℝ) ^ 2)
      (a := x0 ^ 2 * Y)]
    ring
  have hu : (ds.sum : ℝ) = ds.toFinset.sum (fun d : ℕ => (d : ℝ)) := by
    rw [cast_sum_eq ds, ← List.sum_toFinset (fun d : ℕ => (d : ℝ)) hds]
  have hv : (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) =
      ds.toFinset.sum (fun d : ℕ => (d : ℝ) ^ 2) := by
    rw [cast_sum_sq_eq ds, ← List.sum_toFinset (fun d : ℕ => (d : ℝ) ^ 2) hds]
  have hn : (ds.length : ℝ) = (ds.toFinset.card : ℝ) := by
    rw [List.toFinset_card_of_nodup hds]
  have hterm : ∀ d ∈ ds.toFinset,
      1 / x0 - (d : ℝ) / x0 ^ 2 + (d : ℝ) ^ 2 / (x0 ^ 2 * Y) ≤
        Real.log (1 + 1 / ((a : ℝ) + d - 1)) := by
    intro d hd
    have hd' := List.mem_toFinset.mp hd
    have h1 := hpos d hd'
    have h2 := hle d hd'
    have hinst := log_one_add_ge a b (a + d) ha (by omega) (by omega)
    have e1 : ((a + d : ℕ) : ℝ) - (a : ℝ) = (d : ℝ) := by push_cast; ring
    have e2 : ((a + d : ℕ) : ℝ) - 1 = (a : ℝ) + d - 1 := by push_cast; ring
    rw [e1, e2] at hinst
    exact hinst
  by_cases hcase : 4 * ds.sum * (2 * b - 1) ≤
    2 * ds.length * (2 * a - 1) * (2 * b - 1) + 8 * (ds.map (fun d => d ^ 2)).sum
  · have hA : ((2 * a - 1 : ℕ) : ℝ) = 2 * (a : ℝ) - 1 := by
      rw [Nat.cast_sub (by omega : 1 ≤ 2 * a)]; push_cast; ring
    have hB : ((2 * b - 1 : ℕ) : ℝ) = 2 * (b : ℝ) - 1 := by
      rw [Nat.cast_sub (by omega : 1 ≤ 2 * b)]; push_cast; ring
    have hA0 : 2 * (a : ℝ) - 1 ≠ 0 := by
      have : (2 : ℝ) ≤ (a : ℝ) := by exact_mod_cast ha
      linarith
    have hB0 : 2 * (b : ℝ) - 1 ≠ 0 := by
      have : (2 : ℝ) ≤ (b : ℝ) := by
        exact_mod_cast (show 2 ≤ b by omega)
      linarith
    have hsum : (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) =
        ds.toFinset.sum (fun d : ℕ => (d : ℝ) ^ 2) := hv
    have hnum : (blockNum (moments ds) a b : ℝ) ≤ (S : ℝ) * Lsum := by
      calc (blockNum (moments ds) a b : ℝ)
          ≤ ((S * ((2 * ds.length * (2 * a - 1) * (2 * b - 1) +
                8 * (ds.map (fun d => d ^ 2)).sum) -
              4 * ds.sum * (2 * b - 1)) : ℕ) : ℝ) /
              (((2 * a - 1) * (2 * a - 1) * (2 * b - 1) : ℕ) : ℝ) :=
            Nat.cast_div_le
        _ = (S : ℝ) * ((2 * (ds.length : ℝ) * (2 * (a : ℝ) - 1) * (2 * (b : ℝ) - 1) +
                8 * (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) -
                4 * (ds.sum : ℝ) * (2 * (b : ℝ) - 1)) /
              ((2 * (a : ℝ) - 1) * (2 * (a : ℝ) - 1) * (2 * (b : ℝ) - 1))) := by
            simp only [Nat.cast_mul]
            rw [Nat.cast_sub hcase]
            simp only [Nat.cast_add, Nat.cast_mul, Nat.cast_ofNat, hA, hB]
            ring
        _ = (S : ℝ) * Lsum := by
            have halg : (2 * (ds.length : ℝ) * (2 * (a : ℝ) - 1) * (2 * (b : ℝ) - 1) +
                    8 * (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) -
                    4 * (ds.sum : ℝ) * (2 * (b : ℝ) - 1)) /
                  ((2 * (a : ℝ) - 1) * (2 * (a : ℝ) - 1) * (2 * (b : ℝ) - 1)) =
                  (ds.length : ℝ) / ((a : ℝ) - 1 / 2) -
                    (ds.sum : ℝ) / ((a : ℝ) - 1 / 2) ^ 2 +
                    (((ds.map (fun d => d ^ 2)).sum : ℕ) : ℝ) /
                      (((a : ℝ) - 1 / 2) ^ 2 * ((b : ℝ) - 1 / 2)) := by
              have hx : (a : ℝ) - 1 / 2 ≠ 0 := by
                have : (2 : ℝ) ≤ (a : ℝ) := by exact_mod_cast ha
                linarith
              have hy : (b : ℝ) - 1 / 2 ≠ 0 := by
                have : (2 : ℝ) ≤ (b : ℝ) := by
                  exact_mod_cast (show 2 ≤ b by omega)
                linarith
              field_simp
              ring
            rw [halg, hlow, hu, hsum, hn, hx0, hY]
    calc (blockNum (moments ds) a b : ℝ)
        ≤ (S : ℝ) * Lsum := hnum
      _ ≤ (S : ℝ) * (logProd b - logProd a) := by
          apply mul_le_mul_of_nonneg_left _ (by norm_num [S])
          rw [hlogsum, hLsum]
          exact Finset.sum_le_sum hterm
  · have hz : blockNum (moments ds) a b = 0 := by
      simp only [blockNum, moments]
      rw [Nat.sub_eq_zero_of_le (le_of_lt (not_le.mp hcase))]
      simp
    rw [hz, Nat.cast_zero]
    exact mul_nonneg (by norm_num [S]) (sub_nonneg.mpr (logProd_mono a b hb))

theorem logSeries15_one_le_step (r : ℕ) (hr : 2 ≤ r) :
    (logSeries15 1 (2 * r - 1) : ℝ) ≤
      (S : ℝ) * (Real.log r - Real.log (r - 1)) := by
  set dd : ℕ := 2 * r - 1 with hdd
  have hdd3 : 3 ≤ dd := by omega
  have hdposN : 0 < dd := by omega
  have hdpos : (0 : ℝ) < (dd : ℝ) := by exact_mod_cast hdposN
  let z : ℝ := 1 / (dd : ℝ)
  have hz_eq : z = (1 : ℝ) / (dd : ℝ) := rfl
  have hz0 : 0 ≤ z := by rw [hz_eq]; positivity
  have hz1 : z < 1 := by
    rw [hz_eq, div_lt_one hdpos]
    exact_mod_cast (show 1 < dd by omega)
  have hdR : (dd : ℝ) = 2 * (r : ℝ) - 1 := by
    rw [hdd, Nat.cast_sub (by omega : 1 ≤ 2 * r)]
    push_cast
    ring
  have hr2R : (2 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr
  have hr1pos : (0 : ℝ) < (r : ℝ) - 1 := by linarith
  have hratio : (1 + z) / (1 - z) = (r : ℝ) / ((r : ℝ) - 1) := by
    have hd1 : (2 * (r : ℝ) - 1) ≠ 0 := by linarith
    have hr1 : (r : ℝ) - 1 ≠ 0 := by linarith
    have hden : (1 : ℝ) - 1 / (2 * (r : ℝ) - 1) ≠ 0 := by
      have h2 : (0 : ℝ) < 2 * (r : ℝ) - 1 := by linarith [hr2R]
      have heq : (1 : ℝ) - 1 / (2 * (r : ℝ) - 1) =
          (2 * (r : ℝ) - 2) / (2 * (r : ℝ) - 1) := by
        field_simp
        ring
      rw [heq]
      exact div_ne_zero (by linarith [hr2R]) (ne_of_gt h2)
    rw [hz_eq, hdR, div_eq_div_iff hden hr1]
    field_simp [hd1]
    ring
  have h := Real.sum_range_le_log_div hz0 hz1 8
  have hgoal : (logSeries15 1 dd : ℝ) =
      ∑ i ∈ Finset.range 8,
        ((S * 2 * 1 ^ (2 * i + 1) / ((2 * i + 1) * dd ^ (2 * i + 1)) : ℕ) : ℝ) := by
    rw [logSeries15_eq]
    simp only [logTerm15]
    push_cast
    rfl
  have hterm : ∀ i, ((S * 2 * 1 ^ (2 * i + 1) /
        ((2 * i + 1) * dd ^ (2 * i + 1)) : ℕ) : ℝ) ≤
      (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) := by
    intro i
    calc ((S * 2 * (1 : ℕ) ^ (2 * i + 1) /
          ((2 * i + 1) * dd ^ (2 * i + 1)) : ℕ) : ℝ)
        ≤ ((S * 2 * (1 : ℕ) ^ (2 * i + 1) : ℕ) : ℝ) /
            (((2 * i + 1) * dd ^ (2 * i + 1) : ℕ) : ℝ) := AxlerTheta.cast_div_le_real
      _ = ((S : ℝ) * 2 * (1 : ℝ) ^ (2 * i + 1)) /
            (((2 * i + 1) : ℝ) * (dd : ℝ) ^ (2 * i + 1)) := by push_cast; ring
      _ = (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) := by
          have h2i1 : ((2 * i + 1 : ℕ) : ℝ) ≠ 0 := by positivity
          rw [hz_eq, one_div, inv_pow, one_pow]
          field_simp [hdpos.ne', h2i1]
  calc (logSeries15 1 dd : ℝ)
      = ∑ i ∈ Finset.range 8,
          ((S * 2 * 1 ^ (2 * i + 1) / ((2 * i + 1) * dd ^ (2 * i + 1)) : ℕ) : ℝ) := hgoal
    _ ≤ ∑ i ∈ Finset.range 8, (S : ℝ) * 2 * (z ^ (2 * i + 1) / (2 * i + 1)) :=
        Finset.sum_le_sum (fun i _ => hterm i)
    _ = (S : ℝ) * 2 * (∑ i ∈ Finset.range 8, z ^ (2 * i + 1) / (2 * i + 1)) := by
        rw [Finset.mul_sum]
    _ ≤ (S : ℝ) * (Real.log r - Real.log (r - 1)) := by
        have h2 : (2 : ℝ) * (∑ i ∈ Finset.range 8,
            z ^ (2 * i + 1) / (2 * i + 1)) ≤
            Real.log r - Real.log ((r : ℝ) - 1) := by
          have h' := h
          rw [hratio, Real.log_div (by positivity : (r : ℝ) ≠ 0) hr1pos.ne'] at h'
          linarith only [h']
        calc (S : ℝ) * 2 * (∑ i ∈ Finset.range 8, z ^ (2 * i + 1) / (2 * i + 1))
            = (S : ℝ) * (2 * (∑ i ∈ Finset.range 8,
                z ^ (2 * i + 1) / (2 * i + 1))) := by ring
          _ ≤ (S : ℝ) * (Real.log r - Real.log (r - 1)) :=
              mul_le_mul_of_nonneg_left h2 (by norm_num [S])

theorem incrOf_le_log (a b : ℕ) (ds : List ℕ)
    (ha : 2 ≤ a) (hab : a < b) (h64 : b < 2 ^ 64)
    (hds : ds.Nodup) (hpos : ∀ d ∈ ds, 1 ≤ d) (hle : ∀ d ∈ ds, d ≤ b - a)
    (hprime : ∀ d ∈ ds, Nat.Prime (a + d))
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b → p - a ∈ ds) :
    (incrOf (moments ds) a b : ℝ) ≤ (S : ℝ) * (logProd b - logProd a) := by
  have hb : a ≤ b := le_of_lt hab
  by_cases hcnt : (moments ds).count = 1
  · have hlen : ds.length = 1 := hcnt
    obtain ⟨d, rfl⟩ := List.length_eq_one_iff.mp hlen
    have hmem : d ∈ [d] := List.mem_singleton.mpr rfl
    have hd1 : 1 ≤ d := hpos d hmem
    have hdle : d ≤ b - a := hle d hmem
    have hpr : Nat.Prime (a + d) := hprime d hmem
    set r := a + d with hr
    have hr2 : 2 ≤ r := by omega
    have hrb : r ≤ b := by omega
    have hincr : incrOf (moments [d]) a b = logSeries15 1 (2 * (a + d) - 1) := by
      simp [incrOf, moments]
    rw [hincr, ← hr]
    have hseries := logSeries15_one_le_step r hr2
    have hlogsum : logProd b - logProd a = Real.log (1 + 1 / ((r : ℝ) - 1)) := by
      rw [sum_log_sdiff a b hb]
      have hset : Nat.primesLE b \ Nat.primesLE a = {r} := by
        ext p
        constructor
        · intro hp
          obtain ⟨hpb, hpa⟩ := Finset.mem_sdiff.mp hp
          obtain ⟨hpb', hpp⟩ := Nat.mem_primesLE.mp hpb
          have hap : a < p := by
            by_contra hc
            exact hpa (Nat.mem_primesLE.mpr ⟨by omega, hpp⟩)
          have hm : p - a ∈ [d] := hcover p hpp hap hpb'
          have hpd : p - a = d := List.mem_singleton.mp hm
          have : p = r := by omega
          simp [this]
        · intro hp
          rw [Finset.mem_singleton] at hp
          subst hp
          rw [Finset.mem_sdiff]
          constructor
          · exact Nat.mem_primesLE.mpr ⟨hrb, hpr⟩
          · intro hcontra
            have := (Nat.mem_primesLE.mp hcontra).1
            omega
      rw [hset, Finset.sum_singleton]
    have hratio : 1 + 1 / ((r : ℝ) - 1) = (r : ℝ) / ((r : ℝ) - 1) := by
      have h1 : ((r : ℝ) - 1) ≠ 0 := by
        have : (2 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr2
        linarith
      field_simp
      ring
    have hrne : (r : ℝ) ≠ 0 := by
      have : (0 : ℝ) < (r : ℝ) := by exact_mod_cast (show 0 < r by omega)
      linarith
    have hr1ne : ((r : ℝ) - 1) ≠ 0 := by
      have : (2 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr2
      linarith
    calc ((logSeries15 1 (2 * r - 1) : ℕ) : ℝ)
        ≤ (S : ℝ) * (Real.log r - Real.log (r - 1)) := hseries
      _ = (S : ℝ) * (logProd b - logProd a) := by
          rw [hlogsum, hratio, Real.log_div hrne hr1ne]
  · have hiff : incrOf (moments ds) a b = blockNum (moments ds) a b := by
      simp only [incrOf, hcnt, if_false]
    rw [hiff]
    exact blockNum_le_log a b ds ha hab hds hpos hle hprime hcover

-- ============================================================
-- Part C2: block state advance and block range soundness
-- ============================================================

theorem primesLE_succ_of_not_prime {n : ℕ} (hn : ¬ Nat.Prime (n + 1)) :
    Nat.primesLE (n + 1) = Nat.primesLE n := by
  apply Finset.Subset.antisymm
  · intro p hp
    obtain ⟨hpn, hpp⟩ := Nat.mem_primesLE.mp hp
    rcases eq_or_lt_of_le hpn with h | h
    · rw [h] at hpp
      exact absurd hpp hn
    · exact Nat.mem_primesLE.mpr ⟨by omega, hpp⟩
  · exact Nat.primesLE_mono (by omega)

theorem logProd_succ_prime {p : ℕ} (hp : Nat.Prime p) (h3 : 3 ≤ p) :
    logProd (p + 1) = logProd p := by
  have hps : Nat.primesLE (p + 1) = Nat.primesLE p := by
    apply primesLE_succ_of_not_prime
    intro hcon
    have hev : Even (p + 1) := by
      obtain ⟨k, hk⟩ := Nat.Prime.odd_of_ne_two hp (by omega)
      exact ⟨k + 1, by omega⟩
    have h2 : p + 1 = 2 := (Nat.Prime.even_iff hcon).mp hev
    exact hp.ne_one (by omega)
  simp only [logProd, eulerProduct, hps]

theorem logProd_succ_of_not_prime {n : ℕ} (hn : ¬ Nat.Prime (n + 1)) :
    logProd (n + 1) = logProd n := by
  simp only [logProd, eulerProduct, primesLE_succ_of_not_prime hn]

theorem logProd_two : logProd 2 = Real.log 2 := by
  have hset : Nat.primesLE 2 = {2} := by
    apply Finset.Subset.antisymm
    · intro p hp
      obtain ⟨hp2, hpp⟩ := Nat.mem_primesLE.mp hp
      rw [Finset.mem_singleton]
      exact le_antisymm hp2 hpp.two_le
    · intro p hp
      rw [Finset.mem_singleton] at hp
      subst hp
      exact Nat.mem_primesLE.mpr ⟨le_refl 2, Nat.prime_two⟩
  rw [logProd, eulerProduct, hset, Finset.prod_singleton]
  norm_num

theorem blk_state {gbase top m : ℕ} {B : Blk} {L L' : ℕ}
    (hm : m = mask gbase top) (h : blkSpec gbase m B L L')
    (hbase : gbase ≤ B.a) (hb1 : 1 ≤ gbase) (hsq : top ≤ gbase * gbase)
    (hbtop : B.b ≤ top) (h8 : B.b ≤ 10 ^ 8) (hlen : B.b - B.a ≤ 2 ^ 13)
    (ha2 : 2 ≤ B.a) (hab : B.a < B.b)
    (hL : (L : ℝ) ≤ (S : ℝ) * logProd B.a) :
    (L' : ℝ) ≤ (S : ℝ) * logProd B.b := by
  unfold blkSpec at h
  obtain ⟨hL'e, lhi, hhi, hlhi, hhhi, hlhi2, hlhi64, hsub, hentry⟩ := h
  set ds := ((List.range (B.b - B.a)).filter
    (fun i => decide (Nat.Prime (B.a + 1 + i)))).map (fun i => i + 1) with hdsdef
  have hwm := windowMoments_prime_offsets gbase top B.a B.b hbase hb1 hsq hab hbtop h8 hlen
  rw [← hdsdef, ← hm] at hwm
  have hds : ds.Nodup := by
    rw [hdsdef]
    exact List.Nodup.map (fun x y hxy => by omega) (List.Nodup.filter _ List.nodup_range)
  have hpos : ∀ d ∈ ds, 1 ≤ d := by
    intro d hd
    rw [hdsdef] at hd
    obtain ⟨i, hi, rfl⟩ := List.mem_map.mp hd
    have := List.mem_range.mp (List.mem_of_mem_filter hi)
    omega
  have hle : ∀ d ∈ ds, d ≤ B.b - B.a := by
    intro d hd
    rw [hdsdef] at hd
    obtain ⟨i, hi, rfl⟩ := List.mem_map.mp hd
    have := List.mem_range.mp (List.mem_of_mem_filter hi)
    omega
  have hprime : ∀ d ∈ ds, Nat.Prime (B.a + d) := by
    intro d hd
    rw [hdsdef] at hd
    obtain ⟨i, hi, rfl⟩ := List.mem_map.mp hd
    have hdec := (List.mem_filter.mp hi).2
    have hp := of_decide_eq_true hdec
    have e : B.a + (i + 1) = B.a + 1 + i := by omega
    rwa [e]
  have hcover : ∀ p, Nat.Prime p → B.a < p → p ≤ B.b → p - B.a ∈ ds := by
    intro p hpp hap hpb
    rw [hdsdef]
    apply List.mem_map.mpr
    refine ⟨p - B.a - 1, ?_, by omega⟩
    apply List.mem_filter.mpr
    refine ⟨List.mem_range.mpr (by omega), ?_⟩
    rw [decide_eq_true_iff]
    have e : B.a + 1 + (p - B.a - 1) = p := by omega
    rwa [e]
  have hb64 : B.b < 2 ^ 64 := by omega
  have hbl := incrOf_le_log B.a B.b ds ha2 hab hb64 hds hpos hle hprime hcover
  have hmono : (S : ℝ) * logProd B.a ≤ (S : ℝ) * logProd B.b :=
    mul_le_mul_of_nonneg_left (logProd_mono B.a B.b (le_of_lt hab))
      (by norm_num [S] : (0 : ℝ) ≤ S)
  rw [hL'e, Nat.cast_add, hwm]
  linarith [hL, hbl, hmono]

theorem blk_range {gbase m : ℕ} {B : Blk} {L L' : ℕ} {l0 : ℕ}
    (h : blkSpec gbase m B L L') (h2b : 2 ≤ B.b) (hb8 : B.b ≤ 10 ^ 8)
    (hl02 : 2 ≤ l0) (hL : (L : ℝ) ≤ (S : ℝ) * logProd l0)
    (hγ : Real.eulerMascheroniConstant < (gammaUpS : ℝ) / (S : ℝ)) :
    ∀ x : ℝ, (l0 : ℝ) ≤ x → x ≤ (B.b : ℝ) →
      Real.exp Real.eulerMascheroniConstant * Real.log x < eulerProduct ⌊x⌋₊ := by
  unfold blkSpec at h
  obtain ⟨hL'e, lhi, hhi, hlhi, hhhi, hlhi2, hlhi64, hsub, hentry⟩ := h
  have hlo2 : 2 ≤ logUp15 B.b := hlhi ▸ hlhi2
  have hlo64 : logUp15 B.b < 2 ^ 64 := hlhi ▸ hlhi64
  have hsub' : logLo15 S ≤ logUp15 (logUp15 B.b) := by
    rw [← hlhi, ← hhhi]
    exact hsub
  have hll := llUp_sound B.b h2b hb8 hlo2 hlo64 hsub'
  rw [← hlhi, ← hhhi] at hll
  have hcast : ((hhi - logLo15 S : ℕ) : ℝ) = (hhi : ℝ) - (logLo15 S : ℝ) :=
    Nat.cast_sub hsub
  rw [hcast] at hll
  have hentryR : (gammaUpS : ℝ) + ((hhi : ℝ) - (logLo15 S : ℝ)) < (L : ℝ) := by
    have h1 : ((gammaUpS + (hhi - logLo15 S) : ℕ) : ℝ) < (L : ℝ) := by exact_mod_cast hentry
    push_cast at h1
    rwa [hcast] at h1
  have hSpos : (0 : ℝ) < (S : ℝ) := by norm_num [S]
  have hSγ : (S : ℝ) * Real.eulerMascheroniConstant < (gammaUpS : ℝ) := by
    calc (S : ℝ) * Real.eulerMascheroniConstant
        < (S : ℝ) * ((gammaUpS : ℝ) / (S : ℝ)) := mul_lt_mul_of_pos_left hγ hSpos
      _ = (gammaUpS : ℝ) := by field_simp
  intro x hx hxb
  have hx1 : 1 < x := by
    have : (2 : ℝ) ≤ (l0 : ℝ) := by exact_mod_cast hl02
    linarith
  have hx0 : 0 < x := by linarith
  have hlogx : 0 < Real.log x := Real.log_pos hx1
  have hb1R : 1 < (B.b : ℝ) := by exact_mod_cast (show 1 < B.b by omega)
  have hlogb : 0 < Real.log (B.b : ℝ) := Real.log_pos hb1R
  have hlogxb : Real.log x ≤ Real.log (B.b : ℝ) := Real.log_le_log hx0 hxb
  have hloglog : Real.log (Real.log x) ≤ Real.log (Real.log (B.b : ℝ)) :=
    Real.log_le_log hlogx hlogxb
  have hsum2 : (S : ℝ) * (Real.eulerMascheroniConstant +
      Real.log (Real.log (B.b : ℝ))) < (L : ℝ) := by
    have hdist : (S : ℝ) * (Real.eulerMascheroniConstant +
        Real.log (Real.log (B.b : ℝ))) =
        (S : ℝ) * Real.eulerMascheroniConstant +
          (S : ℝ) * Real.log (Real.log (B.b : ℝ)) := by ring
    rw [hdist]
    linarith only [hSγ, hll, hentryR]
  have hSx : (S : ℝ) * (Real.eulerMascheroniConstant + Real.log (Real.log x)) < (L : ℝ) := by
    have hle : Real.eulerMascheroniConstant + Real.log (Real.log x) ≤
        Real.eulerMascheroniConstant + Real.log (Real.log (B.b : ℝ)) := by linarith
    have hm := mul_le_mul_of_nonneg_left hle hSpos.le
    exact lt_of_le_of_lt hm hsum2
  have hlfloor : logProd l0 ≤ logProd ⌊x⌋₊ := logProd_mono l0 ⌊x⌋₊ (Nat.le_floor hx)
  have hSL : (S : ℝ) * (Real.eulerMascheroniConstant + Real.log (Real.log x)) <
      (S : ℝ) * logProd ⌊x⌋₊ := by
    have hm := mul_le_mul_of_nonneg_left hlfloor hSpos.le
    linarith only [hSx, hL, hm]
  have hfin : Real.eulerMascheroniConstant + Real.log (Real.log x) < logProd ⌊x⌋₊ :=
    lt_of_mul_lt_mul_left hSL hSpos.le
  calc Real.exp Real.eulerMascheroniConstant * Real.log x
      = Real.exp (Real.eulerMascheroniConstant + Real.log (Real.log x)) := by
        rw [Real.exp_add, Real.exp_log hlogx]
    _ < Real.exp (logProd ⌊x⌋₊) := Real.exp_lt_exp.mpr hfin
    _ = eulerProduct ⌊x⌋₊ := by rw [logProd]; exact Real.exp_log (eulerProduct_pos _)

theorem state_range {p q L lhi hhi : ℕ}
    (hp2 : 2 ≤ p) (hq2 : 2 ≤ q) (hq8 : q ≤ 10 ^ 8)
    (hlhi : lhi = logUp15 q) (hhhi : hhi = logUp15 lhi)
    (hlhi2 : 2 ≤ lhi) (hlhi64 : lhi < 2 ^ 64) (hsub : logLo15 S ≤ hhi)
    (hentry : gammaUpS + (hhi - logLo15 S) < L)
    (hL : (L : ℝ) ≤ (S : ℝ) * logProd p)
    (hγ : Real.eulerMascheroniConstant < (gammaUpS : ℝ) / (S : ℝ)) :
    ∀ x : ℝ, (p : ℝ) ≤ x → x ≤ (q : ℝ) →
      Real.exp Real.eulerMascheroniConstant * Real.log x < eulerProduct ⌊x⌋₊ := by
  have hlo2 : 2 ≤ logUp15 q := hlhi ▸ hlhi2
  have hlo64 : logUp15 q < 2 ^ 64 := hlhi ▸ hlhi64
  have hsub' : logLo15 S ≤ logUp15 (logUp15 q) := by
    rw [← hlhi, ← hhhi]
    exact hsub
  have hll := llUp_sound q hq2 hq8 hlo2 hlo64 hsub'
  rw [← hlhi, ← hhhi] at hll
  have hcast : ((hhi - logLo15 S : ℕ) : ℝ) = (hhi : ℝ) - (logLo15 S : ℝ) :=
    Nat.cast_sub hsub
  rw [hcast] at hll
  have hentryR : (gammaUpS : ℝ) + ((hhi : ℝ) - (logLo15 S : ℝ)) < (L : ℝ) := by
    have h1 : ((gammaUpS + (hhi - logLo15 S) : ℕ) : ℝ) < (L : ℝ) := by exact_mod_cast hentry
    push_cast at h1
    rwa [hcast] at h1
  have hSpos : (0 : ℝ) < (S : ℝ) := by norm_num [S]
  have hSγ : (S : ℝ) * Real.eulerMascheroniConstant < (gammaUpS : ℝ) := by
    calc (S : ℝ) * Real.eulerMascheroniConstant
        < (S : ℝ) * ((gammaUpS : ℝ) / (S : ℝ)) := mul_lt_mul_of_pos_left hγ hSpos
      _ = (gammaUpS : ℝ) := by field_simp
  intro x hx hxb
  have hx1 : 1 < x := by
    have : (2 : ℝ) ≤ (p : ℝ) := by exact_mod_cast hp2
    linarith
  have hx0 : 0 < x := by linarith
  have hlogx : 0 < Real.log x := Real.log_pos hx1
  have hb1R : 1 < (q : ℝ) := by
    have : (2 : ℝ) ≤ (q : ℝ) := by exact_mod_cast hq2
    linarith
  have hlogb : 0 < Real.log (q : ℝ) := Real.log_pos hb1R
  have hlogxb : Real.log x ≤ Real.log (q : ℝ) := Real.log_le_log hx0 hxb
  have hloglog : Real.log (Real.log x) ≤ Real.log (Real.log (q : ℝ)) :=
    Real.log_le_log hlogx hlogxb
  have hsum2 : (S : ℝ) * (Real.eulerMascheroniConstant +
      Real.log (Real.log (q : ℝ))) < (L : ℝ) := by
    have hdist : (S : ℝ) * (Real.eulerMascheroniConstant +
        Real.log (Real.log (q : ℝ))) =
        (S : ℝ) * Real.eulerMascheroniConstant +
          (S : ℝ) * Real.log (Real.log (q : ℝ)) := by ring
    rw [hdist]
    linarith only [hSγ, hll, hentryR]
  have hSx : (S : ℝ) * (Real.eulerMascheroniConstant + Real.log (Real.log x)) < (L : ℝ) := by
    have hle : Real.eulerMascheroniConstant + Real.log (Real.log x) ≤
        Real.eulerMascheroniConstant + Real.log (Real.log (q : ℝ)) := by linarith
    have hm := mul_le_mul_of_nonneg_left hle hSpos.le
    exact lt_of_le_of_lt hm hsum2
  have hlfloor : logProd p ≤ logProd ⌊x⌋₊ := logProd_mono p ⌊x⌋₊ (Nat.le_floor hx)
  have hSL : (S : ℝ) * (Real.eulerMascheroniConstant + Real.log (Real.log x)) <
      (S : ℝ) * logProd ⌊x⌋₊ := by
    have hm := mul_le_mul_of_nonneg_left hlfloor hSpos.le
    linarith only [hSx, hL, hm]
  have hfin : Real.eulerMascheroniConstant + Real.log (Real.log x) < logProd ⌊x⌋₊ :=
    lt_of_mul_lt_mul_left hSL hSpos.le
  calc Real.exp Real.eulerMascheroniConstant * Real.log x
      = Real.exp (Real.eulerMascheroniConstant + Real.log (Real.log x)) := by
        rw [Real.exp_add, Real.exp_log hlogx]
    _ < Real.exp (logProd ⌊x⌋₊) := Real.exp_lt_exp.mpr hfin
    _ = eulerProduct ⌊x⌋₊ := by rw [logProd]; exact Real.exp_log (eulerProduct_pos _)

-- ============================================================
-- Part C3: group chain state and range soundness
-- ============================================================

theorem grpSpec_state {G : Grp} {gbase m : ℕ} (hm : m = mask gbase G.top)
    (hbase1 : 1 ≤ gbase) (hbase2 : 2 ≤ gbase) (hsq : G.top ≤ gbase * gbase)
    (h8top : G.top ≤ 10 ^ 8) :
    ∀ prev L blks, grpSpec G gbase m prev L blks →
      (∀ B ∈ blks, gbase ≤ B.a ∧ B.a < B.b ∧ B.b ≤ G.top ∧
        B.b - B.a ≤ 2 ^ 13 ∧ B.b ≤ 10 ^ 8) →
      (L : ℝ) ≤ (S : ℝ) * logProd prev →
      (G.lfin : ℝ) ≤ (S : ℝ) * logProd G.top := by
  intro prev L blks
  induction blks generalizing prev L with
  | nil =>
    intro hspec _ hL
    simp only [grpSpec] at hspec
    obtain ⟨hprev, hLf⟩ := hspec
    subst hprev
    rw [← hLf]
    exact hL
  | cons B rest ih =>
    intro hspec hbd hL
    simp only [grpSpec] at hspec
    obtain ⟨hprev, L', hbs, hrest⟩ := hspec
    subst hprev
    have hB := hbd B (by simp)
    have hst := blk_state hm hbs hB.1 hbase1 hsq hB.2.2.1 hB.2.2.2.2
      hB.2.2.2.1 (le_trans hbase2 hB.1) hB.2.1 hL
    have hbd' : ∀ B' ∈ rest, gbase ≤ B'.a ∧ B'.a < B'.b ∧ B'.b ≤ G.top ∧
        B'.b - B'.a ≤ 2 ^ 13 ∧ B'.b ≤ 10 ^ 8 := by
      intro B' hB'
      exact hbd B' (List.mem_cons_of_mem B hB')
    exact ih B.b L' hrest hbd' hst

theorem grpSpec_range {G : Grp} {gbase m : ℕ} (hm : m = mask gbase G.top)
    (hbase1 : 1 ≤ gbase) (hbase2 : 2 ≤ gbase) (hsq : G.top ≤ gbase * gbase)
    (h8top : G.top ≤ 10 ^ 8)
    (hγ : Real.eulerMascheroniConstant < (gammaUpS : ℝ) / (S : ℝ)) :
    ∀ prev L blks, grpSpec G gbase m prev L blks →
      (∀ B ∈ blks, gbase ≤ B.a ∧ B.a < B.b ∧ B.b ≤ G.top ∧
        B.b - B.a ≤ 2 ^ 13 ∧ B.b ≤ 10 ^ 8) →
      (L : ℝ) ≤ (S : ℝ) * logProd prev →
      (G.lfin : ℝ) ≤ (S : ℝ) * logProd G.top ∧
        (∀ x : ℝ, (prev : ℝ) < x → x ≤ (G.top : ℝ) →
          Real.exp Real.eulerMascheroniConstant * Real.log x < eulerProduct ⌊x⌋₊) := by
  intro prev L blks
  induction blks generalizing prev L with
  | nil =>
    intro hspec _ hL
    simp only [grpSpec] at hspec
    obtain ⟨hprev, hLf⟩ := hspec
    subst hprev
    refine ⟨?_, ?_⟩
    · rw [← hLf]
      exact hL
    · intro x hx1 hx2
      exact absurd hx2 (not_le_of_gt hx1)
  | cons B rest ih =>
    intro hspec hbd hL
    simp only [grpSpec] at hspec
    obtain ⟨hprev, L', hbs, hrest⟩ := hspec
    subst hprev
    have hB := hbd B (by simp)
    have hst := blk_state hm hbs hB.1 hbase1 hsq hB.2.2.1 hB.2.2.2.2
      hB.2.2.2.1 (le_trans hbase2 hB.1) hB.2.1 hL
    have hbd' : ∀ B' ∈ rest, gbase ≤ B'.a ∧ B'.a < B'.b ∧ B'.b ≤ G.top ∧
        B'.b - B'.a ≤ 2 ^ 13 ∧ B'.b ≤ 10 ^ 8 := by
      intro B' hB'
      exact hbd B' (List.mem_cons_of_mem B hB')
    have hrec := ih B.b L' hrest hbd' hst
    refine ⟨hrec.1, ?_⟩
    intro x hx1 hx2
    by_cases hxb : x ≤ (B.b : ℝ)
    · exact blk_range hbs (by omega) hB.2.2.2.2 (le_trans hbase2 hB.1) hL hγ x
        (le_of_lt hx1) hxb
    · exact hrec.2 x (not_le.mp hxb) hx2

theorem grp_solution (G : Grp) (hOK : grpOK G = true) (hwf : grpWF G = true)
    (hγ : Real.eulerMascheroniConstant < (gammaUpS : ℝ) / (S : ℝ))
    (hstate : (G.lin : ℝ) ≤ (S : ℝ) * logProd G.lo) :
    (G.lfin : ℝ) ≤ (S : ℝ) * logProd G.top ∧
      (∀ x : ℝ, (G.lo : ℝ) < x → x ≤ (G.top : ℝ) →
        Real.exp Real.eulerMascheroniConstant * Real.log x < eulerProduct ⌊x⌋₊) := by
  have hP := grpWF_spec hwf
  have hbase2 : 2 ≤ G.base := by
    rcases hP.2.1 with hb | ⟨hbp, hb⟩ <;> omega
  have hbase1 : 1 ≤ G.base := by omega
  have hLbase : (G.lin : ℝ) ≤ (S : ℝ) * logProd G.base := by
    rcases hP.2.1 with hb | ⟨hbp, hb⟩
    · rw [hb]
      exact hstate
    · rw [hb, logProd_succ_prime hbp (by omega)]
      exact hstate
  have hspec := grpOK_spec hOK
  have hstatefin := grpSpec_state rfl hbase1 hbase2 hP.2.2.2.1 hP.2.2.2.2.1
    G.base G.lin G.blks hspec hP.2.2.2.2.2 hLbase
  refine ⟨hstatefin, ?_⟩
  cases hblks : G.blks with
  | nil =>
    exfalso
    rw [hblks] at hspec
    simp only [grpSpec] at hspec
    exact (ne_of_lt hP.2.2.1) hspec.1
  | cons B1 rest =>
    rw [hblks] at hspec
    simp only [grpSpec] at hspec
    obtain ⟨hprev, L1, hbs, hrest⟩ := hspec
    have hB1 := hP.2.2.2.2.2 B1 (by rw [hblks]; exact List.mem_cons_self)
    have hst1 := blk_state rfl hbs hB1.1 hbase1 hP.2.2.2.1 hB1.2.2.1 hB1.2.2.2.2
      hB1.2.2.2.1 (le_trans hbase2 hB1.1) hB1.2.1 (by rw [← hprev]; exact hLbase)
    have hbd' : ∀ B' ∈ rest, G.base ≤ B'.a ∧ B'.a < B'.b ∧ B'.b ≤ G.top ∧
        B'.b - B'.a ≤ 2 ^ 13 ∧ B'.b ≤ 10 ^ 8 := by
      intro B' hB'
      exact hP.2.2.2.2.2 B' (by rw [hblks]; exact List.mem_cons_of_mem B1 hB')
    have hrec := grpSpec_range rfl hbase1 hbase2 hP.2.2.2.1 hP.2.2.2.2.1 hγ
      B1.b L1 rest hrest hbd' hst1
    intro x hx1 hx2
    by_cases hxb : x ≤ (B1.b : ℝ)
    · exact blk_range hbs (by omega) hB1.2.2.2.2 (by omega : 2 ≤ G.lo) hstate hγ x
        (le_of_lt hx1) hxb
    · exact hrec.2 x (not_le.mp hxb) hx2

end RosserLower
Source
Rosser & Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94; companion to the platform theorem TaoFivePrimes.rosser_schoenfeld_product_bound_lower; kernel-verified block certificate.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me