Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Axler theta certificate base computations

Definition
axler_theta_base

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

Certificate infrastructure for the Rosser-Schoenfeld style theta bound chain (Axler).

Definition code
import Mathlib.Data.Nat.Sqrt
import Mathlib.NumberTheory.PrimeCounting
import Mathlib.NumberTheory.Harmonic.EulerMascheroni
import Mathlib.Analysis.SpecialFunctions.Log.Deriv
import Mathlib.Analysis.Real.Sqrt
import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
import Mathlib.Topology.Algebra.InfiniteSum.Order
import Mathlib.NumberTheory.Harmonic.ZetaAsymp
import Mathlib.Analysis.Complex.ExponentialBounds
import Mathlib.Tactic.GCongr
import Mathlib.Analysis.Complex.Exponential
import Mathlib.Data.Nat.Log
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Mathlib.Data.Nat.Prime.Basic
import Mathlib.Data.Nat.Bitwise
import Mathlib.Algebra.Ring.GeomSum
import Lean.Elab.Tactic.Omega
import Mathlib.Data.Nat.ModEq
import Mathlib.NumberTheory.Chebyshev
import Mathlib.Algebra.Order.Floor.Div

set_option autoImplicit false
set_option Elab.async false

open Finset

-- Source: Solutions/RosserCompute.lean
/-! Pure natural-number computations for the Rosser--Schoenfeld certificate.
Numerical certificate modules import only this file; real analysis and
correctness proofs remain in the separate proof modules. -/

namespace RosserBitSieve


def periodicMask (d count : ℕ) : ℕ :=
  (2 ^ (d * count) - 1) / (2 ^ d - 1)

def divisorMask (a len d : ℕ) : ℕ :=
  periodicMask d ((len + d - 1) / d) * 2 ^ ((d - a % d) % d)

def compositeMask (divisors : List ℕ) (a len : ℕ) : ℕ :=
  divisors.foldl (fun mask d => mask ||| divisorMask a len d) 0

def candidateMask (divisors : List ℕ) (a len : ℕ) : ℕ :=
  (2 ^ len - 1) ^^^ (compositeMask divisors a len % 2 ^ len)

/-- Enumerate a bit interval by halving it, skipping empty subtrees. -/
def enumBits : ℕ → ℕ → ℕ → List ℕ
  | 0, start, mask => if mask % 2 == 1 then [start] else []
  | depth + 1, start, mask =>
    if mask == 0 then [] else
    let half := 2 ^ depth
    enumBits depth start (mask % 2 ^ half) ++
      enumBits depth (start + half) (mask / 2 ^ half)

def offsets (divisors : List ℕ) (depth a len : ℕ) : List ℕ :=
  enumBits depth 0 (candidateMask divisors a len)

/-- Reuse one sieve mask for many short blocks. Offsets here start at one. -/
def windowOffsets (depth mask shift len : ℕ) : List ℕ :=
  (enumBits depth 0 (mask / 2 ^ shift % 2 ^ len)).map (· + 1)

end RosserBitSieve

namespace AlternativeProductMoments


def firstMoment (ds : List ℕ) : ℕ := ds.sum

def secondMoment (ds : List ℕ) : ℕ := (ds.map (fun (d : ℕ) => d ^ 2)).sum

def lowerNumerator (a : ℕ) (ds : List ℕ) : ℕ :=
  ds.length * a - firstMoment ds

def upperNumerator (a : ℕ) (ds : List ℕ) : ℕ :=
  ds.length * a ^ 2 - a * firstMoment ds + secondMoment ds

def pairNumerator (a : ℕ) (ds : List ℕ) : ℕ :=
  lowerNumerator a ds ^ 2 - ds.length * a ^ 2

def factorNumerator (a : ℕ) (ds : List ℕ) : ℕ :=
  (a ^ 3 - upperNumerator a ds) * (2 * a ^ 4 + pairNumerator a ds)

def factorDenominator (a : ℕ) : ℕ := 2 * a ^ 7

/-- One downward-rounded update for a whole candidate block. -/
def momentStep (v a : ℕ) (ds : List ℕ) : ℕ :=
  v * factorNumerator a ds / factorDenominator a

end AlternativeProductMoments

namespace RosserBitMoments

open RosserBitSieve AlternativeProductMoments

@[ext] structure Moments where
  count : ℕ
  first : ℕ
  second : ℕ
  deriving DecidableEq, Repr

def moments (ds : List ℕ) : Moments :=
  ⟨ds.length, ds.sum, (ds.map (fun (d : ℕ) => d ^ 2)).sum⟩

def merge (s t : Moments) : Moments :=
  ⟨s.count + t.count, s.first + t.first, s.second + t.second⟩

def translate (offset : ℕ) (s : Moments) : Moments :=
  ⟨s.count, s.first + offset * s.count,
    s.second + 2 * offset * s.first + offset ^ 2 * s.count⟩

def packedTable : ℕ := 18472300896970103792108295030754343311462210589054640814582099618958825816112921765637552819554960025580043253363337196071510397018042133440073613070599528214959555081087759177994513208873881398958301422300628985358844335629703824674989009933744813385983504668349668413339407645329016240118311102009327559169919361752210702429893649728293932236557803946372391347786424282478245140012004923246019750498074272682481869124019625063780294997972415480522849467413156748308598193741959980512364680419185912142662080168720543223372130422252685000667222028691552391144914476582653820543415241442522565567827850971540414084963023662461454138479593909733901640282571543659792227281002640358593405226625400471739963595439608037996346958976031522266509217418626068981435972643586956604265934825153588078474541062083601584565110669452202573339800164169103872550900181154149463648375952255080306757167758906906382736410940812007907700484645358916007966298027371443379797534272791198303638115965305949698405311795153919406852986359475633446763175764573556098103639551525890208319167226087125167594382204144161586295123540456912808096572570872821701693833155843103822148960692081668132802646373741121271338591023149542977379459365527447593127745781442122554270427974619422849735484296339832731170084457029930842499657049873841177855047761694425403274812125429077333590092198933962090340380251846202809362383975418479306463890842278375332614640909801129604954946001702919968537917515644728884667828251078535570507012846902588218779713741378512607411980300476879133811456575684021346503785234617675182982977540462331832399895301441454472653688500254658691068207975085644854631617042755709815233293970628383901959051862306499230180026929443703650068362443283922131960509713762221413633617444652901862094089062362383582693974422591379320268703353694406511098994725224448

def byteMoments (byte : ℕ) : Moments :=
  if byte == 0 then ⟨0, 0, 0⟩ else
  if byte &&& (byte - 1) == 0 then
    let bit := Nat.log2 byte
    ⟨1, bit, bit ^ 2⟩
  else
    let word := packedTable / 2 ^ (24 * byte) % 2 ^ 24
    ⟨word % 256, word / 256 % 256, word / 65536 % 256⟩

/-- Depth d represents 2^(d+3) bits. Empty subtrees are skipped. -/
def fastMoments : ℕ → ℕ → ℕ → Moments
  | 0, start, mask => translate start (byteMoments (mask % 256))
  | depth + 1, start, mask =>
    if mask == 0 then ⟨0, 0, 0⟩ else
    let half := 2 ^ (depth + 3)
    merge (fastMoments depth start (mask % 2 ^ half))
      (fastMoments depth (start + half) (mask / 2 ^ half))

def windowMoments (mask shift len : ℕ) : Moments :=
  fastMoments 10 1 (mask / 2 ^ shift % 2 ^ len)

def stepFromMoments (v a : ℕ) (s : Moments) : ℕ :=
  let ell := s.count * a - s.first
  let u := s.count * a ^ 2 - a * s.first + s.second
  let e := ell ^ 2 - s.count * a ^ 2
  v * ((a ^ 3 - u) * (2 * a ^ 4 + e)) / (2 * a ^ 7)

def fastMomentStep (v a mask shift len : ℕ) : ℕ :=
  stepFromMoments v a (windowMoments mask shift len)

end RosserBitMoments

namespace RosserLogCertificate


def scale : ℕ := 2 ^ 64

/-- `p` represents the current odd power, `q` the squared series argument. -/
def seriesRun (D q : ℕ) : ℕ → ℕ → ℕ → ℕ
  | _, _, 0 => 0
  | j, p, terms + 1 => p / (2 * j + 1) +
      seriesRun D q (j + 1) (p * q / D) terms

def atanhLower (num den : ℕ) : ℕ :=
  let z := num * scale / den
  let q := z * z / scale
  2 * seriesRun scale q 0 z 12

/-- One shared constant, checked from the same twelve-term integer algorithm. -/
def logTwoLower : ℕ := 12786308645200714054

def logLower (n : ℕ) : ℕ :=
  let k := Nat.log2 n
  let t := 2 ^ k
  k * logTwoLower + atanhLower (n - t) (n + t)

end RosserLogCertificate

namespace RosserBlockCheck

open RosserLogCertificate

def sqrtUpper (b : ℕ) : ℕ := Nat.sqrt b + 1

def check (a b v : ℕ) : Bool :=
  decide (0 < v ∧
    scale * scale * 10 ^ 8 * sqrtUpper b <
      v * 178107239 * (logLower a * sqrtUpper b + 2 * scale))

end RosserBlockCheck

namespace RosserScan

open RosserBitSieve AlternativeProductMoments RosserLogCertificate RosserBlockCheck RosserBitMoments

/-- Force a natural-number state before the next recursive call. This avoids
re-evaluating a growing expression during kernel reduction. -/
def forceNat {α : Type} (n : ℕ) (f : ℕ → α) : α :=
  match n with
  | 0 => f 0
  | n + 1 => f (n + 1)

def stepOffsets (base mask a b : ℕ) : List ℕ :=
  windowOffsets 13 mask (a - base) (b - a)

def stepCheck (a b v : ℕ) (ds : List ℕ) : Bool :=
  decide (2 ≤ a ∧ a < b ∧ b - a ≤ 2 ^ 13 ∧
    firstMoment ds ≤ ds.length * a ∧ upperNumerator a ds ≤ a ^ 3) &&
      check a b (momentStep v a ds)

def stepData (base mask a b v : ℕ) : Bool × ℕ :=
  let s := windowMoments mask (a - base) (b - a)
  let w := stepFromMoments v a s
  (decide (2 ≤ a ∧ a < b ∧ b - a ≤ 2 ^ 13 ∧
    s.first ≤ s.count * a ∧ s.count * a ^ 2 - a * s.first + s.second ≤ a ^ 3) &&
      check a b w, w)

/-- Try a block, halving its width if the numerical test does not pass. -/
def attempt (base top mask a v : ℕ) : ℕ → ℕ → Option (ℕ × ℕ)
  | 0, _ => none
  | fuel + 1, width =>
    let b := min top (a + width)
    let data := stepData base mask a b v
    if data.1 then some (b, data.2)
    else attempt base top mask a v fuel (width / 2)

def run (base top mask : ℕ) : ℕ → ℕ → ℕ → Option ℕ
  | 0, a, v => if a == top then some v else none
  | fuel + 1, a, v =>
    if a == top then some v else
    match attempt base top mask a v 20 (max 1 (Nat.sqrt a / 2)) with
    | none => none
    | some (b, w) => forceNat b (fun b => forceNat w (fun w => run base top mask fuel b w))

end RosserScan

namespace RosserSieveData

open RosserBitSieve RosserScan

def divisors : List ℕ := [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

def smallDivisors (base : ℕ) := divisors.filter (fun d => decide (d ≤ base))

def mask (base top : ℕ) := candidateMask (smallDivisors base) (base + 1) (top - base)

def segment (base top v : ℕ) :=
  forceNat (mask base top) (fun m => run base top m 4096 base v)

end RosserSieveData

-- Source: Solutions/RosserProductBlocks.lean
/-!
Reusable, kernel-checked parts of a block certificate for Rosser--Schoenfeld.
This module does not assert the target on [4500, 10^8]. In particular, it does
not trust the Python sieve or import any open platform theorem.
-/

namespace RosserProductCertificate

noncomputable def eulerProduct (n : ℕ) : ℝ :=
  ∏ p ∈ Nat.primesLE n, (p : ℝ) / ((p : ℝ) - 1)

theorem eulerProduct_mono : Monotone eulerProduct := by
  intro a b hab
  apply Finset.prod_le_prod_of_subset_of_one_le (Nat.primesLE_mono hab)
  · intro p hp
    have hp2 : (2 : ℝ) ≤ p := by exact_mod_cast (Nat.mem_primesLE.mp hp).2.two_le
    exact div_nonneg (by positivity) (by linarith)
  · intro p hp _
    have hp2 : (2 : ℝ) ≤ p := by exact_mod_cast (Nat.mem_primesLE.mp hp).2.two_le
    apply (le_div_iff₀ (by linarith : (0 : ℝ) < p - 1)).mpr
    linarith

/-- A single comparison closes every real x in [a, B]. The square-root
term is bounded at B, while the logarithm is bounded at a. -/
theorem block_bound (B : ℕ) (a x U g L S : ℝ)
    (ha : 1 ≤ a) (hax : a ≤ x) (hxB : x ≤ B)
    (hU : eulerProduct B ≤ U)
    (hg : g ≤ Real.exp Real.eulerMascheroniConstant)
    (hL0 : 0 ≤ L) (hL : L ≤ Real.log a)
    (hS : 0 < S) (hBS : (B : ℝ) ≤ S ^ 2)
    (hcheck : U < g * (L + 2 / S)) :
    eulerProduct ⌊x⌋₊ <
      Real.exp Real.eulerMascheroniConstant * Real.log x +
        2 * Real.exp Real.eulerMascheroniConstant / Real.sqrt x := by
  have hxpos : 0 < x := by linarith
  have hlog : L ≤ Real.log x := hL.trans (Real.log_le_log (by linarith) hax)
  have hsqrt : Real.sqrt x ≤ S :=
    Real.sqrt_le_iff.mpr ⟨hS.le, hxB.trans hBS⟩
  have hdiv : (2 : ℝ) / S ≤ 2 / Real.sqrt x :=
    div_le_div_of_nonneg_left (by norm_num) (Real.sqrt_pos.mpr hxpos) hsqrt
  have hbase : 0 ≤ L + 2 / S := by positivity
  calc
    eulerProduct ⌊x⌋₊ ≤ eulerProduct B := eulerProduct_mono (Nat.floor_le_of_le hxB)
    _ ≤ U := hU
    _ < g * (L + 2 / S) := hcheck
    _ ≤ Real.exp Real.eulerMascheroniConstant * (L + 2 / S) :=
      mul_le_mul_of_nonneg_right hg hbase
    _ ≤ Real.exp Real.eulerMascheroniConstant * (Real.log x + 2 / Real.sqrt x) :=
      mul_le_mul_of_nonneg_left (add_le_add hlog hdiv) (Real.exp_pos _).le
    _ = _ := by ring

/-- Integer update for a downward-rounded reciprocal product. -/
def downStep (v p : ℕ) : ℕ := v * (p - 1) / p

/-- Rounding down preserves a lower bound for the reciprocal product. -/
theorem downStep_sound (D v p : ℕ) (Q : ℝ)
    (hD : 0 < D) (hp : 2 ≤ p) (hv : (v : ℝ) / D ≤ Q) :
    (downStep v p : ℝ) / D ≤ Q * (((p : ℝ) - 1) / p) := by
  have hD' : (0 : ℝ) < D := by exact_mod_cast hD
  have hp' : (2 : ℝ) ≤ p := by exact_mod_cast hp
  have hcast : ((p - 1 : ℕ) : ℝ) = (p : ℝ) - 1 := by
    rw [Nat.cast_sub (by omega), Nat.cast_one]
  have hround : (downStep v p : ℝ) ≤ (v : ℝ) * (p - 1) / p := by
    simpa [downStep, Nat.cast_mul, hcast] using
      (Nat.cast_div_le (m := v * (p - 1)) (n := p) (α := ℝ))
  calc
    (downStep v p : ℝ) / D ≤ ((v : ℝ) * (p - 1) / p) / D :=
      div_le_div_of_nonneg_right hround hD'.le
    _ = ((v : ℝ) / D) * ((p - 1) / p) := by ring
    _ ≤ Q * ((p - 1) / p) :=
      mul_le_mul_of_nonneg_right hv (div_nonneg (by linarith) (by linarith))

/-- The rounding invariant for an entire list, including repeated or composite
entries. A separate coverage proof connects this list to the target primes. -/
theorem downRun_sound (ps : List ℕ) (D v : ℕ) (Q : ℝ)
    (hD : 0 < D) (hps : ∀ p ∈ ps, 2 ≤ p) (hv : (v : ℝ) / D ≤ Q) :
    ((ps.foldl downStep v : ℕ) : ℝ) / D ≤
      Q * (ps.map (fun (p : ℕ) => ((p : ℝ) - 1) / p)).prod := by
  induction ps generalizing v Q with
  | nil => simpa using hv
  | cons p ps ih =>
    have hp : 2 ≤ p := hps p (by simp)
    have htail : ∀ q ∈ ps, 2 ≤ q := by
      intro q hq
      exact hps q (by simp [hq])
    have hstep := downStep_sound D v p Q hD hp hv
    simpa [List.foldl_cons, List.map_cons, List.prod_cons, mul_assoc] using
      ih (downStep v p) (Q * (((p : ℝ) - 1) / p)) htail hstep

/-- Convert a positive lower bound on the reciprocal product into the needed
upper bound on the original Euler product. -/
theorem eulerProduct_le_of_reciprocal (n : ℕ) (r : ℝ) (hr : 0 < r)
    (hrecip : r ≤ ∏ p ∈ Nat.primesLE n, (((p : ℝ) - 1) / p)) :
    eulerProduct n ≤ 1 / r := by
  have hnonneg : 0 ≤ eulerProduct n := by
    apply Finset.prod_nonneg
    intro p hp
    have h : (2 : ℝ) ≤ p := by exact_mod_cast (Nat.mem_primesLE.mp hp).2.two_le
    exact div_nonneg (by positivity) (by linarith)
  have hcancel :
      (∏ p ∈ Nat.primesLE n, (((p : ℝ) - 1) / p)) * eulerProduct n = 1 := by
    unfold eulerProduct
    rw [← Finset.prod_mul_distrib]
    apply Finset.prod_eq_one
    intro p hp
    have h : (2 : ℝ) ≤ p := by exact_mod_cast (Nat.mem_primesLE.mp hp).2.two_le
    field_simp [show (p : ℝ) - 1 ≠ 0 by linarith]
  apply (le_div_iff₀ hr).mpr
  have := mul_le_mul_of_nonneg_right hrecip hnonneg
  nlinarith

/-- Sieving with any divisor d >= 2 cannot discard a prime p > d.
This is the mathematical invariant required of an optimized sieve. -/
theorem prime_survives_sieve (p d : ℕ) (hp : Nat.Prime p) (hd : 2 ≤ d)
    (hdp : d < p) : ¬d ∣ p := by
  intro hdiv
  rcases hp.eq_one_or_self_of_dvd d hdiv with h | h <;> omega

/-- No assertion of primality is needed for retained sieve candidates:
including extra integers >= 2 only makes a reciprocal-product bound smaller. -/
theorem reciprocal_product_of_superset (s t : Finset ℕ)
    (hst : s ⊆ t) (ht : ∀ p ∈ t, 2 ≤ p) :
    (∏ p ∈ t, (((p : ℝ) - 1) / p)) ≤ ∏ p ∈ s, (((p : ℝ) - 1) / p) := by
  apply Finset.prod_le_prod_of_subset_of_le_one hst
  · intro p hp
    have h : (2 : ℝ) ≤ p := by exact_mod_cast ht p hp
    exact div_nonneg (by linarith) (by linarith)
  · intro p hp _
    have h : (2 : ℝ) ≤ p := by exact_mod_cast ht p hp
    apply (div_le_one (by linarith : (0 : ℝ) < p)).mpr
    linarith

/-- The short positive series used by the experiment for logarithm bounds.
Range reduction n = 2^k * m keeps its argument at most 1/3. -/
theorem log_series_lower (z : ℝ) (hz0 : 0 ≤ z) (hz1 : z < 1) (terms : ℕ) :
    2 * (∑ i ∈ Finset.range terms, z ^ (2 * i + 1) / (2 * i + 1)) ≤
      Real.log ((1 + z) / (1 - z)) := by
  have h := Real.sum_range_le_log_div hz0 hz1 terms
  linarith

end RosserProductCertificate

-- Source: Solutions/ImportedGammaLower.lean
/-!
Accepted Prove2Me proof by andreaskapfer, submission
https://prove2.me/submissions/5b7f3df2-2c10-4572-822a-c64a9d656697
for theorem 9563c569-6ee9-44dd-84a3-163bdd7ea018.
Only changes: added provenance and an enclosing namespace; removed #print;
replaced the all-tactics import with the specific imports used by the proof.
The complete proof is included so local builds do not trust a platform status.
-/

namespace Prove2MeGammaLower

set_option maxRecDepth 1000000

open Real Filter

set_option maxHeartbeats 2000000

namespace TaoFivePrimes


lemma pw (k : ℕ) (hk : 201 ≤ k) :
    2/(2*(k:ℝ)+1) + (2/3)/((2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1)) - 1/((k:ℝ)+1)
      ≤ 18/((6*(k:ℝ)+1)*(6*(k:ℝ)+7)) := by
  have hk403 : (403:ℝ) ≤ 2*(k:ℝ)+1 := by exact_mod_cast (by omega : 403 ≤ 2*k+1)
  have h2 : (0:ℝ) < 2*(k:ℝ)+1 := by linarith
  have hsq : (0:ℝ) < (2*(k:ℝ)+1)^2 - 1 := by nlinarith [sq_nonneg ((2*(k:ℝ)+1) - 403), hk403]
  have hk1 : (0:ℝ) < (k:ℝ)+1 := by positivity
  have hk0 : (0:ℝ) < (k:ℝ) := by exact_mod_cast (by omega : 0 < k)
  have h6 : (0:ℝ) < 6*(k:ℝ)+1 := by linarith
  have h7 : (0:ℝ) < 6*(k:ℝ)+7 := by linarith
  have hu : (0:ℝ) ≤ (k:ℝ) - 201 := by linarith
  have hA : 2/(2*(k:ℝ)+1) + (2/3)/((2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1))
      = (6*((2*(k:ℝ)+1)^2 - 1) + 2)/(3*(2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1)) := by
    field_simp <;> ring_nf
  have hB : 18/((6*(k:ℝ)+1)*(6*(k:ℝ)+7)) + 1/((k:ℝ)+1)
      = (18*((k:ℝ)+1) + (6*(k:ℝ)+1)*(6*(k:ℝ)+7))/((6*(k:ℝ)+1)*(6*(k:ℝ)+7)*((k:ℝ)+1)) := by
    field_simp <;> ring_nf
  suffices hs : (6*((2*(k:ℝ)+1)^2 - 1) + 2)/(3*(2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1))
      ≤ (18*((k:ℝ)+1) + (6*(k:ℝ)+1)*(6*(k:ℝ)+7))/((6*(k:ℝ)+1)*(6*(k:ℝ)+7)*((k:ℝ)+1)) by
    linarith [hA, hB]
  rw [div_le_iff₀ (by positivity : (0:ℝ) < 3*(2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1))]
  rw [div_mul_eq_mul_div]
  rw [le_div_iff₀ (by positivity : (0:ℝ) < ((6*(k:ℝ)+1)*(6*(k:ℝ)+7))*((k:ℝ)+1))]
  have hdec : (0:ℝ) ≤ 36*((k:ℝ)-201)^2 + 14494*((k:ℝ)-201) + 1458844 := by positivity
  nlinarith [hdec, hu, sq_nonneg ((k:ℝ)-201)]



lemma log_series_le (k : ℕ) (hk : 1 ≤ k) :
    Real.log (1 + 1/(k:ℝ)) ≤
      2/(2*(k:ℝ)+1) + (2/3)/((2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1)) := by
  have hk0 : (0:ℝ) < (k:ℝ) := by exact_mod_cast hk
  have ha : (0:ℝ) ≤ 1/(k:ℝ) := by positivity
  have hHS : HasSum (fun j : ℕ => 2 * (1 / (2 * (j:ℝ) + 1)) * ((1/(k:ℝ)) / ((1/(k:ℝ)) + 2)) ^ (2 * j + 1))
      (Real.log (1 + 1/(k:ℝ))) := Real.hasSum_log_one_add ha
  have hq : (1/(k:ℝ)) / ((1/(k:ℝ)) + 2) = 1/(2*(k:ℝ)+1) := by
    field_simp
    ring
  simp only [hq] at hHS
  have hsumm : Summable (fun j : ℕ => 2 * (1 / (2 * (j:ℝ) + 1)) * (1/(2*(k:ℝ)+1)) ^ (2 * j + 1)) :=
    hHS.summable
  have hsplit := Summable.sum_add_tsum_nat_add 1 hsumm
  rw [Finset.sum_range_one, hHS.tsum_eq] at hsplit
  have htail_le : (∑' i : ℕ, (fun j : ℕ => 2 * (1 / (2 * (j:ℝ) + 1)) * (1/(2*(k:ℝ)+1)) ^ (2 * j + 1)) (i+1))
      ≤ (2/3) * (1/(2*(k:ℝ)+1))^3 / (1 - (1/(2*(k:ℝ)+1))^2) := by
    have hq0 : (0:ℝ) ≤ (1/(2*(k:ℝ)+1))^2 := sq_nonneg _
    have hq1 : (1/(2*(k:ℝ)+1))^2 < 1 := by
      rw [div_pow, one_pow, div_lt_one (by positivity)]
      nlinarith [hk0, sq_nonneg ((k:ℝ))]
    have hgeo : HasSum (fun j : ℕ => (2/3) * (1/(2*(k:ℝ)+1))^3 * ((1/(2*(k:ℝ)+1))^2)^j)
        ((2/3) * (1/(2*(k:ℝ)+1))^3 / (1 - (1/(2*(k:ℝ)+1))^2)) := by
      have := (hasSum_geometric_of_norm_lt_one
        (show ‖(1/(2*(k:ℝ)+1))^2‖ < 1 by rwa [Real.norm_eq_abs, abs_of_nonneg hq0])).mul_left
        ((2/3) * (1/(2*(k:ℝ)+1))^3)
      rwa [div_eq_mul_inv]
    have hmain := ((summable_nat_add_iff 1).mpr hsumm).tsum_le_tsum (fun j => by
      push_cast
      have hcoe : 2 * (1 / (2 * ((j:ℝ) + 1) + 1)) ≤ 2/3 := by
        rw [show 2 * (1 / (2 * ((j:ℝ) + 1) + 1)) = 2/(2*((j:ℝ)+1)+1) by ring]
        rw [div_le_iff₀ (by positivity : (0:ℝ) < 2*((j:ℝ)+1)+1)]
        linarith
      have hpow : (1/(2*(k:ℝ)+1)) ^ (2 * (j + 1) + 1)
          = (1/(2*(k:ℝ)+1))^3 * ((1/(2*(k:ℝ)+1))^2)^j := by
        rw [show 2 * (j + 1) + 1 = 3 + 2 * j by omega, pow_add, pow_mul]
      calc 2 * (1 / (2 * ((j:ℝ) + 1) + 1)) * (1/(2*(k:ℝ)+1)) ^ (2 * (j + 1) + 1)
          = (2 * (1 / (2 * ((j:ℝ) + 1) + 1))) * ((1/(2*(k:ℝ)+1))^3 * ((1/(2*(k:ℝ)+1))^2)^j) := by
            rw [hpow]
        _ ≤ (2/3) * ((1/(2*(k:ℝ)+1))^3 * ((1/(2*(k:ℝ)+1))^2)^j) := by
            apply mul_le_mul_of_nonneg_right hcoe
            positivity
        _ = (2/3) * (1/(2*(k:ℝ)+1))^3 * ((1/(2*(k:ℝ)+1))^2)^j := by ring) hgeo.summable
    exact hmain.trans_eq hgeo.tsum_eq
  have hconv : (2/3) * (1/(2*(k:ℝ)+1))^3 / (1 - (1/(2*(k:ℝ)+1))^2)
      = (2/3)/((2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1)) := by
    field_simp
  have hlog : Real.log (1 + 1/(k:ℝ)) = 2 * (1/(2*(k:ℝ)+1))
      + (∑' i : ℕ, (fun j : ℕ => 2 * (1 / (2 * (j:ℝ) + 1)) * (1/(2*(k:ℝ)+1)) ^ (2 * j + 1)) (i+1)) := by
    rw [← hsplit]
    congr 1
    norm_num
  have hid : 2 * (1/(2*(k:ℝ)+1)) = 2/(2*(k:ℝ)+1) := by ring
  have htail_le' : (∑' i : ℕ, (fun j : ℕ => 2 * (1 / (2 * (j:ℝ) + 1)) * (1/(2*(k:ℝ)+1)) ^ (2 * j + 1)) (i+1))
      ≤ (2/3)/((2*(k:ℝ)+1)*((2*(k:ℝ)+1)^2 - 1)) := htail_le.trans_eq hconv
  rw [hlog]
  linarith [htail_le', hid]


lemma term_le (k : ℕ) (hk : 201 ≤ k) :
    ZetaAsymptotics.term k 1 ≤ 18/((6*(k:ℝ)+1)*(6*(k:ℝ)+7)) := by
  have hk0 : (0:ℝ) < (k:ℝ) := by exact_mod_cast (by omega : 0 < k)
  rw [ZetaAsymptotics.term_one (by omega : 0 < k)]
  have h1 : Real.log ((k:ℝ)+1) - Real.log (k:ℝ) = Real.log (1 + 1/(k:ℝ)) := by
    rw [← Real.log_div (by positivity) (by positivity)]
    congr 1
    field_simp
  rw [h1]
  linarith [log_series_le k (by omega : 1 ≤ k), pw k hk]

lemma tail_bound : (∑' k : ℕ, ZetaAsymptotics.term (k + 201) 1) ≤ 3/1207 := by
  have htel : ∀ k : ℕ, (18:ℝ)/((6*(((k+201:ℕ)):ℝ)+1)*(6*(((k+201:ℕ)):ℝ)+7))
      = (1/2)/((k:ℝ)+201+1/6) - (1/2)/(((k+1:ℕ):ℝ)+201+1/6) := by
    intro k
    push_cast
    have h1 : (6*((k:ℝ)+201)+1) ≠ 0 := by positivity
    have h2 : (6*((k:ℝ)+201)+7) ≠ 0 := by positivity
    have h3 : ((k:ℝ)+201+1/6) ≠ 0 := by positivity
    have h4 : ((k:ℝ)+1+201+1/6) ≠ 0 := by positivity
    field_simp [h1, h2, h3, h4]
    ring
  have hu_tend : Tendsto (fun n : ℕ => (1/2)/((n:ℝ)+201+1/6)) atTop (nhds 0) := by
    have h1 : Tendsto (fun n : ℕ => ((n:ℝ) + (201 + 1/6))) atTop atTop :=
      tendsto_atTop_add_const_right _ _ tendsto_natCast_atTop_atTop
    have h2 : Tendsto (fun n : ℕ => (((n:ℝ) + (201 + 1/6)))⁻¹) atTop (nhds 0) := h1.inv_tendsto_atTop
    have h3 : Tendsto (fun n : ℕ => (1/2) * (((n:ℝ) + (201 + 1/6)))⁻¹) atTop (nhds (1/2 * 0)) :=
      tendsto_const_nhds.mul h2
    rw [mul_zero] at h3
    simpa [div_eq_mul_inv, add_assoc] using h3
  have hRsum : HasSum (fun k : ℕ => (18:ℝ)/((6*(((k+201:ℕ)):ℝ)+1)*(6*(((k+201:ℕ)):ℝ)+7)))
      ((1/2)/((201:ℝ)+1/6)) := by
    rw [hasSum_iff_tendsto_nat_of_nonneg (fun k => by positivity)]
    have hps : ∀ n, ∑ k ∈ Finset.range n, (18:ℝ)/((6*(((k+201:ℕ)):ℝ)+1)*(6*(((k+201:ℕ)):ℝ)+7))
        = (1/2)/((0:ℝ)+201+1/6) - (1/2)/((n:ℝ)+201+1/6) := by
      intro n
      calc ∑ k ∈ Finset.range n, (18:ℝ)/((6*(((k+201:ℕ)):ℝ)+1)*(6*(((k+201:ℕ)):ℝ)+7))
          = ∑ k ∈ Finset.range n, ((1/2)/((k:ℝ)+201+1/6) - (1/2)/(((k+1:ℕ):ℝ)+201+1/6)) := by
            apply Finset.sum_congr rfl
            intro k _
            exact htel k
        _ = -(∑ k ∈ Finset.range n, ((1/2)/(((k+1:ℕ):ℝ)+201+1/6) - (1/2)/((k:ℝ)+201+1/6))) := by
            rw [← Finset.sum_neg_distrib]
            apply Finset.sum_congr rfl
            intro k _
            ring
        _ = -((1/2)/((n:ℝ)+201+1/6) - (1/2)/(((0:ℕ):ℝ)+201+1/6)) := by
            rw [Finset.sum_range_sub (fun k : ℕ => (1/2)/((k:ℝ)+201+1/6)) n]
        _ = (1/2)/((0:ℝ)+201+1/6) - (1/2)/((n:ℝ)+201+1/6) := by
            simp only [Nat.cast_zero]
            ring
    simp_rw [hps]
    simpa using tendsto_const_nhds.sub hu_tend
  have hsumg : Summable (fun k : ℕ => ZetaAsymptotics.term (k + 201) 1) := by
    have hf : Summable (fun n : ℕ => ZetaAsymptotics.term (n+1) 1) :=
      ZetaAsymptotics.term_tsum_one.summable
    exact (summable_nat_add_iff 200).mpr hf
  have hRsummable : Summable (fun k : ℕ =>
      (18:ℝ)/((6*(((k+201:ℕ)):ℝ)+1)*(6*(((k+201:ℕ)):ℝ)+7))) := hRsum.summable
  have key := hsumg.tsum_le_tsum (fun k => term_le (k+201) (by omega)) hRsummable
  rw [hRsum.tsum_eq] at key
  norm_num at key ⊢
  exact key

/-- Lower bound for Euler--Mascheroni: `57721565/10^8 ≤ γ`. -/
theorem solution : (57721565/10^8 : ℝ) ≤ Real.eulerMascheroniConstant := by
  have hf : Summable (fun n : ℕ => ZetaAsymptotics.term (n+1) 1) :=
    ZetaAsymptotics.term_tsum_one.summable
  have hsplit := Summable.sum_add_tsum_nat_add 200 hf
  rw [ZetaAsymptotics.term_tsum_one.tsum_eq] at hsplit
  have htail_eq : (∑' i : ℕ, (fun n : ℕ => ZetaAsymptotics.term (n+1) 1) (i+200))
      = (∑' k : ℕ, ZetaAsymptotics.term (k+201) 1) := by
    apply tsum_congr
    intro i
    congr 1
  rw [htail_eq] at hsplit
  have htermSum : (∑ i ∈ Finset.range 200, ZetaAsymptotics.term (i+1) 1)
      = Real.log 201 - (harmonic 201 : ℝ) + 1 := by
    have h := ZetaAsymptotics.termSum_one 200
    unfold ZetaAsymptotics.termSum at h
    rw [show ((200:ℕ):ℝ) + 1 = 201 by norm_num, show (200 + 1 : ℕ) = 201 by norm_num] at h
    exact h
  rw [htermSum] at hsplit
  have hγ : Real.eulerMascheroniConstant = (harmonic 201 : ℝ) - Real.log 201
      - (∑' k : ℕ, ZetaAsymptotics.term (k+201) 1) := by
    linarith
  have hr : Real.log 201 ≤ (530330491/10^8 : ℝ) := by
    rw [Real.log_le_iff_le_exp (by norm_num : (0:ℝ) < 201)]
    calc (201:ℝ) ≤ (2.7182818283:ℝ)^5 * (∑ i ∈ Finset.range 10, (30330491/10^8:ℝ)^i / (i.factorial : ℝ)) := by
          norm_num
      _ ≤ (Real.exp 1)^5 * Real.exp (30330491/10^8) := by
          gcongr
          · exact le_of_lt Real.exp_one_gt_d9
          · exact Real.sum_le_exp_of_nonneg (by norm_num) 10
      _ = Real.exp 5 * Real.exp (30330491/10^8) := by
          rw [← Real.exp_nat_mul 1 5]
          norm_num
      _ = Real.exp (5 + 30330491/10^8) := by rw [← Real.exp_add]
      _ = Real.exp (530330491/10^8) := by norm_num
  have hnum : (57721565/10^8 : ℝ) ≤ (harmonic 201 : ℝ) - (530330491/10^8) - 3/1207 := by
    norm_num [harmonic]
  calc (57721565/10^8 : ℝ) ≤ (harmonic 201 : ℝ) - (530330491/10^8) - 3/1207 := hnum
    _ ≤ Real.eulerMascheroniConstant := by
        rw [hγ]
        linarith [hr, tail_bound]

end TaoFivePrimes

open TaoFivePrimes

/-- The verification harness looks for `theorem solution` in the root
namespace, so the namespaced proof above is re-exported at the root. -/
theorem solution : (57721565/10^8 : ℝ) ≤ Real.eulerMascheroniConstant :=
  TaoFivePrimes.solution


end Prove2MeGammaLower

-- Source: Solutions/RosserProductPilot.lean
/-!
A fully proved pilot interval, using the same downward-rounding scheme as
scripts/rosser_product_experiment.py. All concrete computations below are
checked by Lean; there is no native_decide or external numerical oracle.
The slow reference prime enumeration is only intended for this small pilot.
-/

namespace RosserProductCertificate

set_option maxRecDepth 100000
set_option maxHeartbeats 4000000

def referencePrimes (B : ℕ) : List ℕ :=
  (List.range (B + 1)).filter (fun p => decide (2 ≤ p ∧ Nat.minFac p = p))

theorem referencePrimes_toFinset (B : ℕ) :
    (referencePrimes B).toFinset = Nat.primesLE B := by
  ext p
  simp [referencePrimes, Nat.mem_primesLE, Nat.prime_def_minFac]

theorem referencePrimes_nodup (B : ℕ) : (referencePrimes B).Nodup :=
  List.nodup_range.filter _

theorem referencePrimes_ge_two (B p : ℕ) (hp : p ∈ referencePrimes B) : 2 ≤ p := by
  have h := (List.mem_filter.mp hp).2
  exact (of_decide_eq_true h).1

theorem exp_gamma_lower :
    (178107239 / 10 ^ 8 : ℝ) ≤ Real.exp Real.eulerMascheroniConstant := by
  have h := Real.sum_le_exp_of_nonneg
    (show (0 : ℝ) ≤ 57721565 / 10 ^ 8 by norm_num) 16
  have hnum : (178107239 / 10 ^ 8 : ℝ) ≤
      ∑ i ∈ Finset.range 16, (57721565 / 10 ^ 8 : ℝ) ^ i / i.factorial := by
    norm_num [Finset.sum_range_succ]
  exact (hnum.trans h).trans (Real.exp_le_exp.mpr Prove2MeGammaLower.solution)

theorem log_4500_lower : (8411832675757 / 10 ^ 12 : ℝ) ≤ Real.log 4500 := by
  have htwo := log_series_lower (1 / 3 : ℝ) (by norm_num) (by norm_num) 12
  have hrest := log_series_lower (101 / 2149 : ℝ) (by norm_num) (by norm_num) 12
  norm_num [Finset.sum_range_succ] at htwo hrest
  have heq : Real.log 4500 = 12 * Real.log 2 + Real.log (1125 / 1024) := by
    have hn : (4500 : ℝ) = 2 ^ 12 * (1125 / 1024) := by norm_num
    rw [hn, Real.log_mul (by positivity) (by positivity), Real.log_pow]
    norm_num
  rw [heq]
  linarith

/-- A kernel computation with a fixed 64-bit denominator; no huge exact
numerator and denominator for the Euler product are constructed. -/
theorem reciprocal_4533_lower :
    (1227903923884082104 : ℝ) / 2 ^ 64 ≤
      ∏ p ∈ Nat.primesLE 4533, (((p : ℝ) - 1) / p) := by
  have hcalc : (referencePrimes 4533).foldl downStep (2 ^ 64) =
      1227903923884082104 := by decide +kernel
  have h := downRun_sound (referencePrimes 4533) (2 ^ 64) (2 ^ 64) 1
    (by norm_num) (referencePrimes_ge_two 4533) (by norm_num)
  rw [hcalc] at h
  rw [← List.prod_toFinset _ (referencePrimes_nodup 4533), referencePrimes_toFinset] at h
  simpa only [Nat.cast_pow, Nat.cast_ofNat, one_mul] using h

/-- The original platform inequality, proved without additional hypotheses
on the closed real interval [4500, 4533]. -/
theorem product_bound_4500_to_4533 (x : ℝ) (hx : 4500 ≤ x) (hx' : x ≤ 4533) :
    ∏ p ∈ Nat.primesLE ⌊x⌋₊, (p : ℝ) / ((p : ℝ) - 1) <
      Real.exp Real.eulerMascheroniConstant * Real.log x +
        2 * Real.exp Real.eulerMascheroniConstant / Real.sqrt x := by
  have hu := eulerProduct_le_of_reciprocal 4533
    (1227903923884082104 / 2 ^ 64) (by norm_num) reciprocal_4533_lower
  apply block_bound 4533 4500 x (1 / (1227903923884082104 / 2 ^ 64))
    (178107239 / 10 ^ 8) (8411832675757 / 10 ^ 12) 68
    (by norm_num) hx hx' hu exp_gamma_lower (by norm_num) log_4500_lower
    (by norm_num) (by norm_num)
  norm_num

end RosserProductCertificate

-- Source: Solutions/RosserLogCertificate.lean
/-!
A table-free lower bound for log(n). All evaluation uses natural numbers
with fixed denominator 2^64. There are twelve positive atanh-series terms;
every division, including the power recurrence, rounds downward.
-/

namespace RosserLogCertificate

theorem scale_pos : 0 < scale := by decide

theorem rounded_mul_lower (D p q : ℕ) (x y : ℝ) (hD : 0 < D)
    (hx0 : 0 ≤ x) (hp : (p : ℝ) / D ≤ x) (hq : (q : ℝ) / D ≤ y) :
    ((p * q / D : ℕ) : ℝ) / D ≤ x * y := by
  have hD0 : (0 : ℝ) < D := by exact_mod_cast hD
  have hround := Nat.cast_div_le (m := p * q) (n := D) (α := ℝ)
  simp only [Nat.cast_mul] at hround
  calc
    ((p * q / D : ℕ) : ℝ) / D ≤ ((p : ℝ) * q / D) / D :=
      div_le_div_of_nonneg_right hround hD0.le
    _ = ((p : ℝ) / D) * ((q : ℝ) / D) := by ring
    _ ≤ x * y := mul_le_mul hp hq (by positivity) hx0

theorem seriesRun_sound (D q : ℕ) (z : ℝ) (hD : 0 < D) (hz : 0 ≤ z)
    (hq : (q : ℝ) / D ≤ z ^ 2) (j p terms : ℕ)
    (hp : (p : ℝ) / D ≤ z ^ (2 * j + 1)) :
    (seriesRun D q j p terms : ℝ) / D ≤
      ∑ i ∈ Finset.range terms,
        z ^ (2 * (j + i) + 1) / (2 * ((j + i : ℕ) : ℝ) + 1) := by
  induction terms generalizing j p with
  | zero => simp [seriesRun]
  | succ terms ih =>
    have hD0 : (0 : ℝ) < D := by exact_mod_cast hD
    have hden : (0 : ℝ) < 2 * j + 1 := by positivity
    have hterm : ((p / (2 * j + 1) : ℕ) : ℝ) / D ≤
        z ^ (2 * j + 1) / (2 * (j : ℝ) + 1) := by
      have hr := Nat.cast_div_le (m := p) (n := 2 * j + 1) (α := ℝ)
      simp only [Nat.cast_add, Nat.cast_mul, Nat.cast_ofNat, Nat.cast_one] at hr
      calc
        ((p / (2 * j + 1) : ℕ) : ℝ) / D ≤
            ((p : ℝ) / (2 * (j : ℝ) + 1)) / D :=
          div_le_div_of_nonneg_right hr hD0.le
        _ = ((p : ℝ) / D) / (2 * (j : ℝ) + 1) := by ring
        _ ≤ _ := div_le_div_of_nonneg_right hp hden.le
    have hnext : ((p * q / D : ℕ) : ℝ) / D ≤ z ^ (2 * (j + 1) + 1) := by
      have hr := rounded_mul_lower D p q (z ^ (2 * j + 1)) (z ^ 2)
        hD (by positivity) hp hq
      have he : z ^ (2 * j + 1) * z ^ 2 = z ^ (2 * (j + 1) + 1) := by
        rw [← pow_add]
        congr 1
      exact he ▸ hr
    have hi := ih (j + 1) (p * q / D) hnext
    rw [Finset.sum_range_succ']
    simp only [seriesRun, Nat.cast_add, add_div]
    have hshift :
        (∑ i ∈ Finset.range terms,
          z ^ (2 * (j + 1 + i) + 1) / (2 * ((j + 1 + i : ℕ) : ℝ) + 1)) =
        ∑ i ∈ Finset.range terms,
          z ^ (2 * (j + (i + 1)) + 1) / (2 * ((j + (i + 1) : ℕ) : ℝ) + 1) := by
      apply Finset.sum_congr rfl
      intro i _
      have he : j + 1 + i = j + (i + 1) := by omega
      rw [he]
    rw [hshift] at hi
    simpa only [Nat.add_zero, Nat.cast_add, Nat.cast_zero, Nat.cast_one,
      add_zero, add_comm] using add_le_add hi hterm

theorem atanhLower_sound (num den : ℕ) (hden : 0 < den) (hnum : num < den) :
    (atanhLower num den : ℝ) / scale ≤
      Real.log ((1 + (num : ℝ) / den) / (1 - (num : ℝ) / den)) := by
  let z : ℝ := (num : ℝ) / den
  let v := num * scale / den
  let q := v * v / scale
  have hD0 : (0 : ℝ) < scale := by exact_mod_cast scale_pos
  have hden0 : (0 : ℝ) < den := by exact_mod_cast hden
  have hz0 : 0 ≤ z := by dsimp [z]; positivity
  have hz1 : z < 1 := by
    apply (div_lt_one hden0).mpr
    exact_mod_cast hnum
  have hv : (v : ℝ) / scale ≤ z := by
    have hr := Nat.cast_div_le (m := num * scale) (n := den) (α := ℝ)
    simp only [Nat.cast_mul] at hr
    calc
      (v : ℝ) / scale ≤ ((num : ℝ) * scale / den) / scale :=
        div_le_div_of_nonneg_right hr hD0.le
      _ = z := by dsimp [z]; field_simp
  have hq : (q : ℝ) / scale ≤ z ^ 2 := by
    simpa only [pow_two] using rounded_mul_lower scale v v z z scale_pos hz0 hv hv
  have hr := seriesRun_sound scale q z scale_pos hz0 hq 0 v 12
    (by simpa using hv)
  simp only [Nat.zero_add] at hr
  have hl := Real.sum_range_le_log_div hz0 hz1 12
  change (2 * seriesRun scale q 0 v 12 : ℕ) / (scale : ℝ) ≤ _
  push_cast
  change 2 * (seriesRun scale q 0 v 12 : ℝ) / scale ≤
    Real.log ((1 + z) / (1 - z))
  calc
    2 * (seriesRun scale q 0 v 12 : ℝ) / scale =
        2 * ((seriesRun scale q 0 v 12 : ℝ) / scale) := by ring
    _ ≤ _ := by linarith only [hr, hl]

theorem logTwoLower_eval : atanhLower 1 3 = logTwoLower := by decide +kernel

theorem logTwoLower_sound : (logTwoLower : ℝ) / scale ≤ Real.log 2 := by
  have h := atanhLower_sound 1 3 (by decide) (by decide)
  rw [logTwoLower_eval] at h
  norm_num at h ⊢
  exact h

theorem logLower_sound (n : ℕ) (hn : 1 ≤ n) :
    (logLower n : ℝ) / scale ≤ Real.log n := by
  let k := Nat.log2 n
  let t : ℕ := 2 ^ k
  have hn0 : n ≠ 0 := by omega
  have ht0 : 0 < t := by dsimp [t]; positivity
  have htn : t ≤ n := (Nat.le_log2 hn0).mp (le_refl _)
  have hnum : n - t < n + t := by omega
  have hden : 0 < n + t := by omega
  have hrest := atanhLower_sound (n - t) (n + t) hden hnum
  have ht0' : (0 : ℝ) < t := by exact_mod_cast ht0
  have hn0' : (0 : ℝ) < n := by exact_mod_cast (show 0 < n by omega)
  have hid : (1 + ((n - t : ℕ) : ℝ) / (n + t : ℕ)) /
      (1 - ((n - t : ℕ) : ℝ) / (n + t : ℕ)) = (n : ℝ) / t := by
    rw [Nat.cast_sub htn, Nat.cast_add]
    field_simp [ne_of_gt ht0', ne_of_gt (add_pos hn0' ht0')]
    ring
  rw [hid, Real.log_div (ne_of_gt hn0') (ne_of_gt ht0')] at hrest
  have htlog : Real.log (t : ℝ) = (k : ℝ) * Real.log 2 := by
    simp only [t, Nat.cast_pow, Nat.cast_ofNat, Real.log_pow]
  rw [htlog] at hrest
  have htwo := mul_le_mul_of_nonneg_left logTwoLower_sound
    (show (0 : ℝ) ≤ k by positivity)
  change ((k * logTwoLower + atanhLower (n - t) (n + t) : ℕ) : ℝ) / scale ≤ _
  rw [Nat.cast_add, Nat.cast_mul, add_div, mul_div_assoc]
  linarith only [htwo, hrest]

theorem logLower_4500_eval : logLower 4500 = 155170924560559531400 := by decide +kernel

theorem logLower_4500_ge_pilot :
    (8411832675757 / 10 ^ 12 : ℝ) ≤ (logLower 4500 : ℝ) / scale := by
  rw [logLower_4500_eval]
  norm_num [scale]

end RosserLogCertificate

-- Source: Solutions/RosserBlockCheck.lean
/-! A single exact integer comparison proves the real bound on a block. -/

namespace RosserBlockCheck

open RosserProductCertificate RosserLogCertificate

def Bound (x : ℝ) : Prop :=
  eulerProduct ⌊x⌋₊ <
    Real.exp Real.eulerMascheroniConstant * Real.log x +
      2 * Real.exp Real.eulerMascheroniConstant / Real.sqrt x

theorem check_sound (a b v : ℕ) (ha : 1 ≤ a) (hcheck : check a b v = true)
    (hv : (v : ℝ) / scale ≤ ∏ p ∈ Nat.primesLE b, (((p : ℝ) - 1) / p))
    (x : ℝ) (hax : (a : ℝ) ≤ x) (hxb : x ≤ b) : Bound x := by
  obtain ⟨hv0, hnum⟩ := of_decide_eq_true hcheck
  have hv0' : (0 : ℝ) < v := by exact_mod_cast hv0
  have hD : (0 : ℝ) < scale := by exact_mod_cast scale_pos
  have hS : (0 : ℝ) < sqrtUpper b := by
    exact_mod_cast (show 0 < sqrtUpper b by unfold sqrtUpper; omega)
  have hBS : (b : ℝ) ≤ (sqrtUpper b : ℝ) ^ 2 := by
    have h : b ≤ sqrtUpper b ^ 2 := (Nat.lt_succ_sqrt' b).le
    exact_mod_cast h
  have hineq : (scale : ℝ) * scale * 10 ^ 8 * sqrtUpper b <
      (v : ℝ) * 178107239 * ((logLower a : ℝ) * sqrtUpper b + 2 * scale) := by
    exact_mod_cast hnum
  have hc : (1 : ℝ) / ((v : ℝ) / scale) <
      (178107239 / 10 ^ 8 : ℝ) *
        ((logLower a : ℝ) / scale + 2 / sqrtUpper b) := by
    apply (div_lt_iff₀ (div_pos hv0' hD)).mpr
    field_simp
    nlinarith only [hineq]
  exact block_bound b a x (1 / ((v : ℝ) / scale)) (178107239 / 10 ^ 8)
    ((logLower a : ℝ) / scale) (sqrtUpper b)
    (by exact_mod_cast ha) hax hxb
    (eulerProduct_le_of_reciprocal b _ (div_pos hv0' hD) hv)
    exp_gamma_lower (div_nonneg (Nat.cast_nonneg _) hD.le)
    (logLower_sound a ha) hS hBS hc

end RosserBlockCheck

-- Source: Solutions/AlternativeProductMoments.lean
/-!
A different arithmetic kernel for a finite Euler-product certificate.
It replaces multiplication/division for every prime by three integer moments
per block. This file proves the mathematical inequalities, not the full
Rosser--Schoenfeld bound through 10^8.
-/

namespace AlternativeProductMoments

theorem square_sum_ge_sum_squares (xs : List ℝ)
    (hxs : ∀ x ∈ xs, 0 ≤ x) :
    (xs.map (fun x => x ^ 2)).sum ≤ xs.sum ^ 2 := by
  induction xs with
  | nil => simp
  | cons x xs ih =>
    have hx := hxs x (by simp)
    have htail : ∀ y ∈ xs, 0 ≤ y := by
      intro y hy
      exact hxs y (by simp [hy])
    have hs : 0 ≤ xs.sum := List.sum_nonneg htail
    have hi := ih htail
    simp only [List.map_cons, List.sum_cons]
    nlinarith [mul_nonneg hx hs]

/-- A conservative third-order Bonferroni bound. Its induction only uses
the nonnegative first two moments; no exponential or logarithm is needed. -/
theorem product_lower (xs : List ℝ)
    (hxs : ∀ x ∈ xs, 0 ≤ x ∧ x ≤ 1) :
    (1 - xs.sum) * (1 + (xs.sum ^ 2 - (xs.map (fun x => x ^ 2)).sum) / 2) ≤
      (xs.map (fun x => 1 - x)).prod := by
  induction xs with
  | nil => simp
  | cons x xs ih =>
    have hx := hxs x (by simp)
    have htail : ∀ y ∈ xs, 0 ≤ y ∧ y ≤ 1 := by
      intro y hy
      exact hxs y (by simp [hy])
    have hs : 0 ≤ xs.sum := List.sum_nonneg (fun y hy => (htail y hy).1)
    have he : 0 ≤ xs.sum ^ 2 - (xs.map (fun y => y ^ 2)).sum :=
      sub_nonneg.mpr (square_sum_ge_sum_squares xs (fun y hy => (htail y hy).1))
    have hmul := mul_le_mul_of_nonneg_left (ih htail) (sub_nonneg.mpr hx.2)
    have herr : 0 ≤ x * xs.sum *
        ((xs.sum ^ 2 - (xs.map (fun y => y ^ 2)).sum) / 2 + xs.sum + x) := by
      exact mul_nonneg (mul_nonneg hx.1 hs)
        (add_nonneg (add_nonneg (div_nonneg he (by norm_num)) hs) hx.1)
    simp only [List.map_cons, List.sum_cons, List.prod_cons]
    nlinarith only [hmul, herr]

/-- Safe interval versions of the two moments. The max allows blocks with
zero or one candidate, for which the approximate pair correction is negative. -/
theorem product_lower_of_moment_bounds (xs : List ℝ) (L U T : ℝ)
    (hxs : ∀ x ∈ xs, 0 ≤ x ∧ x ≤ 1)
    (hL0 : 0 ≤ L) (hL : L ≤ xs.sum) (hU : xs.sum ≤ U) (hU1 : U ≤ 1)
    (hT : (xs.map (fun x => x ^ 2)).sum ≤ T) :
    (1 - U) * (1 + max 0 ((L ^ 2 - T) / 2)) ≤
      (xs.map (fun x => 1 - x)).prod := by
  have hs : 0 ≤ xs.sum := List.sum_nonneg (fun y hy => (hxs y hy).1)
  have he := square_sum_ge_sum_squares xs (fun y hy => (hxs y hy).1)
  have hpair : max 0 ((L ^ 2 - T) / 2) ≤
      (xs.sum ^ 2 - (xs.map (fun x => x ^ 2)).sum) / 2 := by
    apply max_le
    · linarith
    · nlinarith [sq_nonneg (xs.sum - L)]
  calc
    (1 - U) * (1 + max 0 ((L ^ 2 - T) / 2)) ≤
        (1 - xs.sum) * (1 + (xs.sum ^ 2 - (xs.map (fun x => x ^ 2)).sum) / 2) := by
      apply mul_le_mul
      · linarith
      · linarith
      · positivity
      · linarith
    _ ≤ _ := product_lower xs hxs

/-- The first three terms of the geometric expansion enclose 1/(a+d).
Summing this uses only the count, sum, and sum of squares of integer offsets. -/
theorem inverse_bounds (a d : ℝ) (ha : 0 < a) (hd : 0 ≤ d) :
    1 / a - d / a ^ 2 ≤ 1 / (a + d) ∧
    1 / (a + d) ≤ 1 / a - d / a ^ 2 + d ^ 2 / a ^ 3 := by
  have had : 0 < a + d := by linarith
  constructor
  · apply (le_div_iff₀ had).mpr
    field_simp
    nlinarith [sq_nonneg d]
  · apply (div_le_iff₀ had).mpr
    field_simp
    nlinarith [mul_nonneg hd (sq_nonneg d)]

/-- Moment bounds for all candidates of the form a+d in a block. -/
theorem reciprocal_moment_bounds (a : ℝ) (ds : List ℝ)
    (ha : 0 < a) (hds : ∀ d ∈ ds, 0 ≤ d) :
    ((ds.length : ℝ) / a - ds.sum / a ^ 2 ≤
        (ds.map (fun d => 1 / (a + d))).sum) ∧
    ((ds.map (fun d => 1 / (a + d))).sum ≤
        (ds.length : ℝ) / a - ds.sum / a ^ 2 +
          (ds.map (fun d => d ^ 2)).sum / a ^ 3) ∧
    ((ds.map (fun d => (1 / (a + d)) ^ 2)).sum ≤
        (ds.length : ℝ) / a ^ 2) := by
  induction ds with
  | nil => simp
  | cons d ds ih =>
    have hd := hds d (by simp)
    have htail : ∀ e ∈ ds, 0 ≤ e := by
      intro e he
      exact hds e (by simp [he])
    have hi := ih htail
    have hb := inverse_bounds a d ha hd
    have had : 0 < a + d := by linarith
    have hsq : (1 / (a + d)) ^ 2 ≤ 1 / a ^ 2 := by
      rw [div_pow, one_pow]
      apply div_le_div_of_nonneg_left (by norm_num) (sq_pos_of_pos ha)
      nlinarith [sq_nonneg d, mul_nonneg ha.le hd]
    simp only [List.length_cons, Nat.cast_add, Nat.cast_one,
      List.map_cons, List.sum_cons]
    constructor
    · convert add_le_add hb.1 hi.1 using 1 <;> first | rfl | ring
    constructor
    · convert add_le_add hb.2 hi.2.1 using 1 <;> first | rfl | ring
    · convert add_le_add hsq hi.2.2 using 1 <;> first | rfl | ring

/-- The exact factor used by the alternative experiment. Checking the three
integer moments suffices for the product bound for an entire block. -/
theorem block_factor_lower (a : ℝ) (ds : List ℝ)
    (ha : 1 ≤ a) (hds : ∀ d ∈ ds, 0 ≤ d)
    (hL : 0 ≤ (ds.length : ℝ) / a - ds.sum / a ^ 2)
    (hU : (ds.length : ℝ) / a - ds.sum / a ^ 2 +
      (ds.map (fun d => d ^ 2)).sum / a ^ 3 ≤ 1) :
    (1 - ((ds.length : ℝ) / a - ds.sum / a ^ 2 +
        (ds.map (fun d => d ^ 2)).sum / a ^ 3)) *
      (1 + max 0 ((((ds.length : ℝ) / a - ds.sum / a ^ 2) ^ 2 -
        (ds.length : ℝ) / a ^ 2) / 2)) ≤
      (ds.map (fun d => 1 - 1 / (a + d))).prod := by
  have ha0 : 0 < a := by linarith
  have hb := reciprocal_moment_bounds a ds ha0 hds
  have hxs : ∀ x ∈ ds.map (fun d => 1 / (a + d)), 0 ≤ x ∧ x ≤ 1 := by
    intro x hx
    obtain ⟨d, hd, rfl⟩ := List.mem_map.mp hx
    have hd0 := hds d hd
    have had : 0 < a + d := by linarith
    constructor
    · positivity
    · apply (div_le_one had).mpr
      linarith
  simpa only [List.map_map, Function.comp_def] using
    product_lower_of_moment_bounds (ds.map (fun d => 1 / (a + d)))
      ((ds.length : ℝ) / a - ds.sum / a ^ 2)
      ((ds.length : ℝ) / a - ds.sum / a ^ 2 +
        (ds.map (fun d => d ^ 2)).sum / a ^ 3)
      ((ds.length : ℝ) / a ^ 2) hxs hL hb.1 hb.2.1 hU
      (by simpa only [List.map_map, Function.comp_def] using hb.2.2)

private theorem cast_sub_max (n m : ℕ) :
    ((n - m : ℕ) : ℝ) = max 0 ((n : ℝ) - m) := by
  by_cases h : m ≤ n
  · rw [Nat.cast_sub h, max_eq_right]
    exact sub_nonneg.mpr (by exact_mod_cast h)
  · have hmn : n ≤ m := by omega
    rw [Nat.sub_eq_zero_of_le hmn, Nat.cast_zero, max_eq_left]
    exact sub_nonpos.mpr (by exact_mod_cast hmn)

/-- Cast the three integer moments once, outside the computational loop. -/
theorem integer_factor_lower (a : ℕ) (ds : List ℕ)
    (ha : 2 ≤ a) (hfirst : firstMoment ds ≤ ds.length * a)
    (hupper : upperNumerator a ds ≤ a ^ 3) :
    (factorNumerator a ds : ℝ) / factorDenominator a ≤
      (ds.map (fun (d : ℕ) => 1 - 1 / ((a : ℝ) + d))).prod := by
  have ha0 : (0 : ℝ) < a := by exact_mod_cast (show 0 < a by omega)
  have ha_ne : (a : ℝ) ≠ 0 := ne_of_gt ha0
  have hfirst' : a * firstMoment ds ≤ ds.length * a ^ 2 := by
    calc
      a * firstMoment ds ≤ a * (ds.length * a) := Nat.mul_le_mul_left a hfirst
      _ = ds.length * a ^ 2 := by ring
  have hcastL : (lowerNumerator a ds : ℝ) =
      (ds.length : ℝ) * a - firstMoment ds := by
    simp only [lowerNumerator, Nat.cast_sub hfirst, Nat.cast_mul]
  have hcastU : (upperNumerator a ds : ℝ) =
      (ds.length : ℝ) * (a : ℝ) ^ 2 - a * firstMoment ds + secondMoment ds := by
    simp only [upperNumerator, Nat.cast_add, Nat.cast_sub hfirst', Nat.cast_mul,
      Nat.cast_pow]
  have hcastE : (pairNumerator a ds : ℝ) =
      max 0 (((ds.length : ℝ) * a - firstMoment ds) ^ 2 -
        (ds.length : ℝ) * (a : ℝ) ^ 2) := by
    simp only [pairNumerator, cast_sub_max, Nat.cast_pow, Nat.cast_mul, hcastL]
  have hL : 0 ≤ (ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2 := by
    have heq : (ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2 =
        (lowerNumerator a ds : ℝ) / (a : ℝ) ^ 2 := by
      rw [hcastL]
      field_simp
    rw [heq]
    positivity
  have hU : (ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2 +
      (secondMoment ds : ℝ) / (a : ℝ) ^ 3 ≤ 1 := by
    have hcast := (show (upperNumerator a ds : ℝ) ≤ (a : ℝ) ^ 3 by exact_mod_cast hupper)
    have heq : (ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2 +
        (secondMoment ds : ℝ) / (a : ℝ) ^ 3 =
        (upperNumerator a ds : ℝ) / (a : ℝ) ^ 3 := by
      rw [hcastU]
      field_simp
    rw [heq]
    exact (div_le_one (pow_pos ha0 3)).mpr hcast
  have hsum : (ds.map (fun (d : ℕ) => (d : ℝ))).sum = (firstMoment ds : ℝ) := by
    simp only [firstMoment, Nat.cast_list_sum]
  have hsquares :
      ((ds.map (fun (d : ℕ) => (d : ℝ))).map (fun d => d ^ 2)).sum =
        (secondMoment ds : ℝ) := by
    simp only [secondMoment, Nat.cast_list_sum, List.map_map, Function.comp_def,
      Nat.cast_pow]
  have hsquares' : (ds.map (fun (d : ℕ) => (d : ℝ) ^ 2)).sum =
      (secondMoment ds : ℝ) := by
    simpa only [List.map_map, Function.comp_def] using hsquares
  have hb := block_factor_lower (a : ℝ) (ds.map (fun (d : ℕ) => (d : ℝ)))
    (by exact_mod_cast (show 1 ≤ a by omega))
    (by intro d hd; obtain ⟨n, _, rfl⟩ := List.mem_map.mp hd; positivity)
    (by simpa only [List.length_map, hsum] using hL)
    (by simpa only [List.length_map, hsum, hsquares] using hU)
  simp only [List.length_map, hsum, List.map_map, Function.comp_def, hsquares'] at hb
  have hpair : (pairNumerator a ds : ℝ) / (2 * (a : ℝ) ^ 4) =
      max 0 ((((ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2) ^ 2 -
        (ds.length : ℝ) / (a : ℝ) ^ 2) / 2) := by
    rw [hcastE, ← max_div_div_right (by positivity : (0 : ℝ) ≤ 2 * (a : ℝ) ^ 4),
      zero_div]
    congr 1
    field_simp
  have hfactor : (factorNumerator a ds : ℝ) / factorDenominator a =
      (1 - ((ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2 +
        (secondMoment ds : ℝ) / (a : ℝ) ^ 3)) *
        (1 + max 0 ((((ds.length : ℝ) / a - (firstMoment ds : ℝ) / (a : ℝ) ^ 2) ^ 2 -
          (ds.length : ℝ) / (a : ℝ) ^ 2) / 2)) := by
    rw [← hpair]
    simp only [factorNumerator, factorDenominator, Nat.cast_mul,
      Nat.cast_sub hupper, Nat.cast_pow, Nat.cast_add, Nat.cast_ofNat, hcastU]
    field_simp
  rw [hfactor]
  exact hb

/-- The complete integer step: all candidates may be composite and all
computations are on natural numbers. A separate sieve coverage theorem
relates their product to the actual prime product. -/
theorem momentStep_sound (D v a : ℕ) (ds : List ℕ) (Q : ℝ)
    (hD : 0 < D) (ha : 2 ≤ a) (hfirst : firstMoment ds ≤ ds.length * a)
    (hupper : upperNumerator a ds ≤ a ^ 3) (hv : (v : ℝ) / D ≤ Q) :
    (momentStep v a ds : ℝ) / D ≤
      Q * (ds.map (fun (d : ℕ) => 1 - 1 / ((a : ℝ) + d))).prod := by
  have hD0 : (0 : ℝ) < D := by exact_mod_cast hD
  have hQ : 0 ≤ Q := (by positivity : (0 : ℝ) ≤ (v : ℝ) / D).trans hv
  have hround : (momentStep v a ds : ℝ) ≤
      (v : ℝ) * (factorNumerator a ds : ℝ) / factorDenominator a := by
    simpa only [momentStep, Nat.cast_mul] using
      (Nat.cast_div_le (m := v * factorNumerator a ds)
        (n := factorDenominator a) (α := ℝ))
  calc
    (momentStep v a ds : ℝ) / D ≤
        ((v : ℝ) * (factorNumerator a ds : ℝ) / factorDenominator a) / D :=
      div_le_div_of_nonneg_right hround hD0.le
    _ = ((v : ℝ) / D) * ((factorNumerator a ds : ℝ) / factorDenominator a) := by ring
    _ ≤ Q * ((factorNumerator a ds : ℝ) / factorDenominator a) :=
      mul_le_mul_of_nonneg_right hv (by positivity)
    _ ≤ _ := mul_le_mul_of_nonneg_left (integer_factor_lower a ds ha hfirst hupper) hQ

end AlternativeProductMoments

-- Source: Solutions/RosserMomentBridge.lean
/-!
Connect a rounded moment update to the genuine reciprocal prime product.
The candidate list only needs to cover all primes in the block; it may also
contain composites. Its correctness is separate from the arithmetic update.
-/

namespace RosserMomentBridge

open AlternativeProductMoments

noncomputable def reciprocalProduct (n : ℕ) : ℝ :=
  ∏ p ∈ Nat.primesLE n, (((p : ℝ) - 1) / p)

theorem reciprocalProduct_nonneg (n : ℕ) : 0 ≤ reciprocalProduct n := by
  apply Finset.prod_nonneg
  intro p hp
  have hp2 : (2 : ℝ) ≤ p := by exact_mod_cast Nat.two_le_of_mem_primesLE hp
  exact div_nonneg (by linarith) (by linarith)

/-- The list product bounds the product over new primes in (a,b]. -/
theorem candidate_product_le_prime_block (a b : ℕ) (ds : List ℕ)
    (ha : 2 ≤ a) (hds : ds.Nodup)
    (hbounds : ∀ d ∈ ds, 0 < d ∧ d ≤ b - a)
    (hcover : ∀ p : ℕ, Nat.Prime p → a < p → p ≤ b → p - a ∈ ds) :
    (ds.map (fun (d : ℕ) => 1 - 1 / ((a : ℝ) + d))).prod ≤
      ∏ p ∈ Nat.primesLE b \ Nat.primesLE a, (((p : ℝ) - 1) / p) := by
  let ps := ds.map (fun (d : ℕ) => a + d)
  have hps : ps.Nodup := List.Nodup.map (by intro x y h; dsimp at h; omega) hds
  have hps_bounds : ∀ p ∈ ps.toFinset, a < p ∧ p ≤ b := by
    intro p hp
    obtain ⟨d, hd, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hp)
    have hb := hbounds d hd
    omega
  have hsubset : Nat.primesLE b \ Nat.primesLE a ⊆ ps.toFinset := by
    intro p hp
    obtain ⟨hpb, hpa⟩ := Finset.mem_sdiff.mp hp
    obtain ⟨hpb', hpprime⟩ := Nat.mem_primesLE.mp hpb
    have hap : a < p := by
      by_contra h
      exact hpa (Nat.mem_primesLE.mpr ⟨by omega, hpprime⟩)
    apply List.mem_toFinset.mpr
    exact List.mem_map.mpr ⟨p - a, hcover p hpprime hap hpb', by omega⟩
  have hbound := RosserProductCertificate.reciprocal_product_of_superset
    (Nat.primesLE b \ Nat.primesLE a) ps.toFinset hsubset
    (by intro p hp; have h := hps_bounds p hp; omega)
  have hprod :
      (∏ p ∈ ps.toFinset, (((p : ℝ) - 1) / p)) =
        (ds.map (fun (d : ℕ) => 1 - 1 / ((a : ℝ) + d))).prod := by
    rw [List.prod_toFinset _ hps]
    change ((ds.map (fun (d : ℕ) => a + d)).map
      (fun (p : ℕ) => ((p : ℝ) - 1) / p)).prod = _
    rw [List.map_map]
    congr 1
    apply List.map_congr_left
    intro d _
    have ha0 : (0 : ℝ) < a := by exact_mod_cast (show 0 < a by omega)
    have had : (0 : ℝ) < a + d := by positivity
    simp only [Function.comp_def, Nat.cast_add]
    field_simp
  rwa [hprod] at hbound

/-- A verified update of the reciprocal product across one whole block.
Every prime in (a,b] must survive the candidate sieve. Extra composite
candidates are harmless because their factors lie between zero and one. -/
theorem momentStep_reciprocalProduct (D v a b : ℕ) (ds : List ℕ)
    (hD : 0 < D) (hab : a ≤ b) (ha : 2 ≤ a) (hds : ds.Nodup)
    (hbounds : ∀ d ∈ ds, 0 < d ∧ d ≤ b - a)
    (hcover : ∀ p : ℕ, Nat.Prime p → a < p → p ≤ b → p - a ∈ ds)
    (hfirst : firstMoment ds ≤ ds.length * a)
    (hupper : upperNumerator a ds ≤ a ^ 3)
    (hv : (v : ℝ) / D ≤ reciprocalProduct a) :
    (momentStep v a ds : ℝ) / D ≤ reciprocalProduct b := by
  have hstep := momentStep_sound D v a ds (reciprocalProduct a)
    hD ha hfirst hupper hv
  have hblock := candidate_product_le_prime_block a b ds ha hds hbounds hcover
  have hsplit :
      reciprocalProduct a *
        (∏ p ∈ Nat.primesLE b \ Nat.primesLE a, (((p : ℝ) - 1) / p)) =
        reciprocalProduct b := by
    unfold reciprocalProduct
    rw [mul_comm]
    exact Finset.prod_sdiff (Nat.primesLE_mono hab)
  calc
    (momentStep v a ds : ℝ) / D ≤
        reciprocalProduct a * (ds.map (fun (d : ℕ) => 1 - 1 / ((a : ℝ) + d))).prod :=
      hstep
    _ ≤ reciprocalProduct a *
        (∏ p ∈ Nat.primesLE b \ Nat.primesLE a, (((p : ℝ) - 1) / p)) :=
      mul_le_mul_of_nonneg_left hblock (reciprocalProduct_nonneg a)
    _ = reciprocalProduct b := hsplit

end RosserMomentBridge

-- Source: Solutions/RosserBernoulli.lean
/-! An elementary lower bound for the product of prime factors in a block. -/

namespace RosserBernoulli

theorem one_sub_sum_le_prod {α : Type*} (s : Finset α) (u : α → ℝ)
    (h0 : ∀ i ∈ s, 0 ≤ u i) (h1 : ∀ i ∈ s, u i ≤ 1) :
    1 - ∑ i ∈ s, u i ≤ ∏ i ∈ s, (1 - u i) := by
  classical
  induction s using Finset.induction_on with
  | empty => simp
  | @insert i s hi ih =>
    have hui0 : 0 ≤ u i := h0 i (Finset.mem_insert_self _ _)
    have hui1 : u i ≤ 1 := h1 i (Finset.mem_insert_self _ _)
    have htail0 : ∀ j ∈ s, 0 ≤ u j := by
      intro j hj
      exact h0 j (Finset.mem_insert_of_mem hj)
    have htail1 : ∀ j ∈ s, u j ≤ 1 := by
      intro j hj
      exact h1 j (Finset.mem_insert_of_mem hj)
    have hs0 : 0 ≤ ∑ j ∈ s, u j := Finset.sum_nonneg htail0
    have htail := ih htail0 htail1
    have hmul := mul_le_mul_of_nonneg_left htail (by linarith : 0 ≤ 1 - u i)
    rw [Finset.sum_insert hi, Finset.prod_insert hi]
    nlinarith only [hmul, hui0, hs0]

theorem prime_block_lower (a n k : ℕ) (ha : 2 ≤ a) (han : a ≤ n)
    (hcard : (Nat.primesLE n \ Nat.primesLE a).card ≤ k) :
    1 - (k : ℝ) / (a + 1) ≤
      ∏ p ∈ Nat.primesLE n \ Nat.primesLE a, (((p : ℝ) - 1) / p) := by
  let s := Nat.primesLE n \ Nat.primesLE a
  have hpa : ∀ p ∈ s, a < p := by
    intro p hp
    have hp' := Finset.mem_sdiff.mp hp
    have hprime := (Nat.mem_primesLE.mp hp'.1).2
    by_contra h
    exact hp'.2 (Nat.mem_primesLE.mpr ⟨by omega, hprime⟩)
  have hp2 : ∀ p ∈ s, (2 : ℝ) ≤ p := by
    intro p hp
    exact_mod_cast (show 2 ≤ p by have := hpa p hp; omega)
  have h0 : ∀ p ∈ s, (0 : ℝ) ≤ 1 / p := by
    intro p hp
    positivity
  have h1 : ∀ p ∈ s, (1 : ℝ) / p ≤ 1 := by
    intro p hp
    have h := hp2 p hp
    apply (div_le_iff₀ (by linarith : (0 : ℝ) < p)).mpr
    linarith
  have hpoint : ∀ p ∈ s, (1 : ℝ) / p ≤ 1 / (a + 1) := by
    intro p hp
    have h := hpa p hp
    have h' : (a + 1 : ℝ) ≤ p := by exact_mod_cast h
    exact div_le_div_of_nonneg_left (by norm_num) (by positivity) h'
  have hsum : (∑ p ∈ s, (1 : ℝ) / p) ≤ (k : ℝ) / (a + 1) := by
    calc
      (∑ p ∈ s, (1 : ℝ) / p) ≤ ∑ _p ∈ s, (1 : ℝ) / (a + 1) :=
        Finset.sum_le_sum hpoint
      _ = (s.card : ℝ) / (a + 1) := by simp [div_eq_mul_inv]
      _ ≤ (k : ℝ) / (a + 1) :=
        div_le_div_of_nonneg_right (by exact_mod_cast hcard) (by positivity)
  have hb := one_sub_sum_le_prod s (fun p => (1 : ℝ) / p) h0 h1
  have heq : (∏ p ∈ s, (1 - (1 : ℝ) / p)) =
      ∏ p ∈ s, (((p : ℝ) - 1) / p) := by
    apply Finset.prod_congr rfl
    intro p hp
    have hp0 : (0 : ℝ) < p := by have := hp2 p hp; linarith
    field_simp
    <;> ring
  calc
    1 - (k : ℝ) / (a + 1) ≤ 1 - ∑ p ∈ s, (1 : ℝ) / p := by linarith only [hsum]
    _ ≤ ∏ p ∈ s, (1 - (1 : ℝ) / p) := hb
    _ = _ := heq

theorem reciprocal_prefix_lower (a n k : ℕ) (ha : 2 ≤ a) (han : a ≤ n)
    (hcard : (Nat.primesLE n \ Nat.primesLE a).card ≤ k) :
    RosserMomentBridge.reciprocalProduct a * (1 - (k : ℝ) / (a + 1)) ≤
      RosserMomentBridge.reciprocalProduct n := by
  have hblock := prime_block_lower a n k ha han hcard
  have hnonneg := RosserMomentBridge.reciprocalProduct_nonneg a
  have hmul := mul_le_mul_of_nonneg_left hblock hnonneg
  have hsplit : RosserMomentBridge.reciprocalProduct a *
      (∏ p ∈ Nat.primesLE n \ Nat.primesLE a, (((p : ℝ) - 1) / p)) =
      RosserMomentBridge.reciprocalProduct n := by
    unfold RosserMomentBridge.reciprocalProduct
    rw [mul_comm]
    exact Finset.prod_sdiff (Nat.primesLE_mono han)
  exact hmul.trans_eq hsplit

end RosserBernoulli

-- Source: Solutions/RosserPrefixBounds.lean
/-! Elementary interval bounds for the fast finite Rosser certificate. -/

namespace RosserPrefixBounds

theorem log_step (a b x : ℝ) (ha : 0 < a) (hax : a ≤ x) (hxb : x ≤ b) :
    (x - a) / b ≤ Real.log x - Real.log a := by
  have hx : 0 < x := lt_of_lt_of_le ha hax
  have hb : 0 < b := lt_of_lt_of_le hx hxb
  have hlog := Real.one_sub_inv_le_log_of_pos (div_pos hx ha)
  rw [Real.log_div (ne_of_gt hx) (ne_of_gt ha)] at hlog
  have heq : 1 - (x / a)⁻¹ = (x - a) / x := by
    field_simp
  rw [heq] at hlog
  exact (div_le_div_of_nonneg_left (sub_nonneg.mpr hax) hx hxb).trans hlog

theorem sqrt_reciprocal_step (a x : ℝ) (ha : 0 < a) (hax : a ≤ x) :
    -(x - a) / (a * Real.sqrt a) ≤
      2 / Real.sqrt x - 2 / Real.sqrt a := by
  let s := Real.sqrt x
  let t := Real.sqrt a
  have hx : 0 < x := lt_of_lt_of_le ha hax
  have hs : 0 < s := Real.sqrt_pos.mpr hx
  have ht : 0 < t := Real.sqrt_pos.mpr ha
  have hst : t ≤ s := Real.sqrt_le_sqrt hax
  have hsa : s ^ 2 = x := Real.sq_sqrt hx.le
  have hta : t ^ 2 = a := Real.sq_sqrt ha.le
  have hden : 2 * a * t ≤ s * t * (s + t) := by
    have hfactor : 0 ≤ t * (s - t) * (s + 2 * t) := by positivity
    calc
      2 * a * t = 2 * t ^ 3 := by rw [← hta]; ring
      _ ≤ s * t * (s + t) := by nlinarith only [hfactor]
  have hdenpos : 0 < s * t * (s + t) := by positivity
  have hatpos : 0 < a * t := by positivity
  have hfrac : 2 / (s * t * (s + t)) ≤ 1 / (a * t) := by
    apply (div_le_div_iff₀ hdenpos hatpos).mpr
    nlinarith only [hden]
  have hmul := mul_le_mul_of_nonneg_right hfrac (sub_nonneg.mpr hax)
  have hidentity : 2 / t - 2 / s =
      (x - a) * (2 / (s * t * (s + t))) := by
    rw [← hsa, ← hta]
    field_simp
    <;> ring
  have hnegative : -(x - a) * (1 / (a * t)) ≤
      -(x - a) * (2 / (s * t * (s + t))) := by
    simpa only [neg_mul, mul_comm] using neg_le_neg hmul
  calc
    -(x - a) / (a * Real.sqrt a) = -(x - a) * (1 / (a * t)) := by
      dsimp [t]; ring
    _ ≤ -(x - a) * (2 / (s * t * (s + t))) := hnegative
    _ = -((x - a) * (2 / (s * t * (s + t)))) := by ring
    _ = -(2 / t - 2 / s) := by rw [← hidentity]
    _ = 2 / s - 2 / t := by ring
    _ = 2 / Real.sqrt x - 2 / Real.sqrt a := rfl

theorem log_sqrt_linear (a b x : ℝ) (ha : 0 < a) (hax : a ≤ x) (hxb : x ≤ b) :
    Real.log a + 2 / Real.sqrt a +
        (1 / b - 1 / (a * Real.sqrt a)) * (x - a) ≤
      Real.log x + 2 / Real.sqrt x := by
  have hlog := log_step a b x ha hax hxb
  have hsqrt := sqrt_reciprocal_step a x ha hax
  simp only [neg_div] at hsqrt
  calc
    Real.log a + 2 / Real.sqrt a +
        (1 / b - 1 / (a * Real.sqrt a)) * (x - a) =
      Real.log a + 2 / Real.sqrt a +
        (x - a) / b - (x - a) / (a * Real.sqrt a) := by ring
    _ ≤ Real.log x + 2 / Real.sqrt x := by linarith only [hlog, hsqrt]

theorem reciprocal_barrier_chord (A U B C h d : ℝ)
    (hA : 0 ≤ A) (hU : 0 ≤ U) (hB : 0 < B) (hC : 0 ≤ C)
    (hd : 0 ≤ d) (hdh : d ≤ h) :
    A * (1 - U / B) + A * U * C / (B * (B + C * h)) * d ≤
      A * (1 - U / (B + C * d)) := by
  have hh : 0 ≤ h := le_trans hd hdh
  have hbh : 0 < B + C * h := by positivity
  have hbd : 0 < B + C * d := by positivity
  have hhd : 0 ≤ h - d := sub_nonneg.mpr hdh
  have hnum : 0 ≤ A * U * C ^ 2 * d * (h - d) := by positivity
  have hden : 0 < B * (B + C * d) * (B + C * h) := by positivity
  have hid :
      A * (1 - U / (B + C * d)) -
        (A * (1 - U / B) + A * U * C / (B * (B + C * h)) * d) =
      (A * U * C ^ 2 * d * (h - d)) /
        (B * (B + C * d) * (B + C * h)) := by
    field_simp
    <;> ring
  have hnonneg := div_nonneg hnum hden.le
  linarith only [hid, hnonneg]

/-- A lower affine envelope for the full real-valued target on an interval. -/
theorem target_linear_lower (a b x g B C : ℝ)
    (ha : 0 < a) (hax : a ≤ x) (hxb : x ≤ b)
    (hg : 0 ≤ g) (hgamma : g ≤ Real.exp Real.eulerMascheroniConstant)
    (hB : B ≤ g * (Real.log a + 2 / Real.sqrt a))
    (hC : C ≤ g * (1 / b - 1 / (a * Real.sqrt a)))
    (hFx : 0 ≤ Real.log x + 2 / Real.sqrt x) :
    B + C * (x - a) ≤
      Real.exp Real.eulerMascheroniConstant *
        (Real.log x + 2 / Real.sqrt x) := by
  have hd : 0 ≤ x - a := sub_nonneg.mpr hax
  have hlin := log_sqrt_linear a b x ha hax hxb
  have hC' := mul_le_mul_of_nonneg_right hC hd
  have hlin' := mul_le_mul_of_nonneg_left hlin hg
  have hgamma' := mul_le_mul_of_nonneg_right hgamma hFx
  nlinarith only [hB, hC', hlin', hgamma']

/-- Integer square-root bounds may be used with opposite rounding directions
in the intercept and the slope. -/
theorem rounded_target_linear_lower (a b x g L r S : ℝ)
    (ha : 1 ≤ a) (hax : a ≤ x) (hxb : x ≤ b)
    (hg : 0 ≤ g) (hgamma : g ≤ Real.exp Real.eulerMascheroniConstant)
    (hL : L ≤ Real.log a) (hr : 0 < r) (hrS : r ≤ Real.sqrt a)
    (hS : 0 < S) (hSa : Real.sqrt a ≤ S) :
    g * (L + 2 / S) +
      g * (1 / b - 1 / (a * r)) * (x - a) ≤
      Real.exp Real.eulerMascheroniConstant *
        (Real.log x + 2 / Real.sqrt x) := by
  have hsa : 0 < Real.sqrt a := Real.sqrt_pos.mpr (by linarith)
  have hSdiv : 2 / S ≤ 2 / Real.sqrt a :=
    div_le_div_of_nonneg_left (by norm_num) hsa hSa
  have hB : g * (L + 2 / S) ≤
      g * (Real.log a + 2 / Real.sqrt a) := by
    apply mul_le_mul_of_nonneg_left _ hg
    linarith only [hL, hSdiv]
  have har : 0 < a * r := mul_pos (by linarith) hr
  have hsar : a * r ≤ a * Real.sqrt a :=
    mul_le_mul_of_nonneg_left hrS (by linarith)
  have hRdiv : 1 / (a * Real.sqrt a) ≤ 1 / (a * r) :=
    div_le_div_of_nonneg_left (by norm_num) har hsar
  have hC : g * (1 / b - 1 / (a * r)) ≤
      g * (1 / b - 1 / (a * Real.sqrt a)) := by
    apply mul_le_mul_of_nonneg_left _ hg
    linarith only [hRdiv]
  have hx1 : (1 : ℝ) ≤ x := ha.trans hax
  have hlogx : 0 ≤ Real.log x := Real.log_nonneg hx1
  have hsx : 0 < Real.sqrt x := Real.sqrt_pos.mpr (by linarith)
  have hFx : 0 ≤ Real.log x + 2 / Real.sqrt x := by positivity
  exact target_linear_lower a b x g _ _ (by linarith) hax hxb hg
    hgamma hB hC hFx

/-- A strict count bound in a prefix converts a reciprocal-product lower
bound into a strict upper bound on the Euler product. -/
theorem prefix_count_to_product (a n k : ℕ) (q T : ℝ)
    (ha : 2 ≤ a) (han : a ≤ n) (hq : 0 < q) (hT : 0 < T)
    (hv : q ≤ RosserMomentBridge.reciprocalProduct a)
    (hcard : (Nat.primesLE n \ Nat.primesLE a).card ≤ k)
    (hcount : (k : ℝ) < (a + 1) * (1 - (1 / q) / T)) :
    RosserProductCertificate.eulerProduct n < T := by
  let A : ℝ := a + 1
  have hA : 0 < A := by dsimp [A]; positivity
  have hfrac : (k : ℝ) / A < 1 - (1 / q) / T := by
    apply (div_lt_iff₀ hA).mpr
    dsimp [A] at hcount ⊢
    nlinarith only [hcount]
  have hfactor : 0 < 1 - (k : ℝ) / A := by
    have : 0 < (1 / q) / T := by positivity
    linarith only [hfrac, this]
  have hqprod : q * (1 - (k : ℝ) / A) ≤
      RosserMomentBridge.reciprocalProduct n := by
    have hmul := mul_le_mul_of_nonneg_right hv hfactor.le
    exact hmul.trans (by simpa only [A] using
      RosserBernoulli.reciprocal_prefix_lower a n k ha han hcard)
  have hbar : 1 < T * (q * (1 - (k : ℝ) / A)) := by
    have hqt : 0 < q * T := mul_pos hq hT
    have hrewrite : (1 / q) / T = 1 / (q * T) := by ring
    rw [hrewrite] at hfrac
    have h : 1 < (1 - (k : ℝ) / A) * (q * T) :=
      (div_lt_iff₀ hqt).mp (by linarith only [hfrac])
    nlinarith only [h]
  have hr : 0 < q * (1 - (k : ℝ) / A) := mul_pos hq hfactor
  have hupper := RosserProductCertificate.eulerProduct_le_of_reciprocal n
    _ hr hqprod
  have hstrict : 1 / (q * (1 - (k : ℝ) / A)) < T :=
    (div_lt_iff₀ hr).mpr (by nlinarith only [hbar])
  exact hupper.trans_lt hstrict

/-- A certified affine count bound at any point of a block suffices for the
prime product at that point. -/
theorem affine_prefix_to_product (a n k : ℕ) (q B C h d I M : ℝ)
    (ha : 2 ≤ a) (han : a ≤ n) (hq : 0 < q) (hB : 0 < B)
    (hC : 0 ≤ C) (hd : 0 ≤ d) (hdh : d ≤ h)
    (hv : q ≤ RosserMomentBridge.reciprocalProduct a)
    (hcard : (Nat.primesLE n \ Nat.primesLE a).card ≤ k)
    (hI : I ≤ (a + 1) * (1 - (1 / q) / B))
    (hM : M ≤ (a + 1) * (1 / q) * C / (B * (B + C * h)))
    (hk : (k : ℝ) < I + M * d) :
    RosserProductCertificate.eulerProduct n < B + C * d := by
  have hT : 0 < B + C * d := by positivity
  have hchord := reciprocal_barrier_chord (a + 1 : ℝ) (1 / q) B C h d
    (by positivity) (by positivity) hB hC hd hdh
  have hMd := mul_le_mul_of_nonneg_right hM hd
  have hbound : (k : ℝ) < (a + 1) * (1 - (1 / q) / (B + C * d)) := by
    linarith only [hk, hI, hMd, hchord]
  exact prefix_count_to_product a n k q (B + C * d)
    ha han hq hT hv hcard hbound

end RosserPrefixBounds

-- Source: Solutions/RosserPrefixParams.lean
/-! Exact arithmetic for the downward-rounded affine barrier parameters. -/

namespace RosserPrefixParams

open RosserLogCertificate

private theorem forceNat_eq {α : Type} (n : ℕ) (f : ℕ → α) :
    RosserScan.forceNat n f = f n := by
  cases n <;> rfl

structure Parameters where
  intercept : ℕ
  slope : ℕ
  valid : Bool

def parameters (a b v : ℕ) : Parameters :=
  RosserScan.forceNat (Nat.sqrt a) fun r =>
  RosserScan.forceNat (178107239 * (logLower a * (r + 1) + 2 * scale)) fun bn =>
  RosserScan.forceNat (10 ^ 8 * scale * (r + 1)) fun bd =>
  RosserScan.forceNat (178107239 * (a * r - b)) fun cn =>
  RosserScan.forceNat (10 ^ 8 * b * a * r) fun cd =>
    ⟨16384 * (a + 1) * (v * bn - scale * bd) / (v * bn),
     16384 * (a + 1) * scale * cn * bd ^ 2 /
       (v * bn * (bn * cd + cn * bd * (b - a))),
     decide (4500 ≤ a ∧ a < b ∧ b ≤ 10 ^ 8 ∧ 0 < v ∧
       b < a * r ∧ scale * bd < v * bn)⟩

theorem parameters_valid (a b v : ℕ) (h : (parameters a b v).valid = true) :
    4500 ≤ a ∧ a < b ∧ b ≤ 10 ^ 8 ∧ 0 < v ∧
      b < a * Nat.sqrt a ∧
      scale * (10 ^ 8 * scale * (Nat.sqrt a + 1)) <
        v * (178107239 *
          (logLower a * (Nat.sqrt a + 1) + 2 * scale)) := by
  simpa only [parameters, forceNat_eq, decide_eq_true_eq] using h

theorem sqrt_bracket (a : ℕ) (ha : 1 ≤ a) :
    0 < (Nat.sqrt a : ℝ) ∧
      (Nat.sqrt a : ℝ) ≤ Real.sqrt a ∧
      Real.sqrt a ≤ (Nat.sqrt a + 1 : ℕ) := by
  have hr1 : 1 ≤ Nat.sqrt a := by
    apply Nat.le_sqrt.mpr
    simpa using ha
  have hr0 : (0 : ℝ) < Nat.sqrt a := by exact_mod_cast hr1
  have hlow : (Nat.sqrt a : ℝ) ^ 2 ≤ a := by
    exact_mod_cast Nat.sqrt_le' a
  have hhigh : (a : ℝ) ≤ (Nat.sqrt a + 1 : ℕ) ^ 2 := by
    exact_mod_cast (Nat.lt_succ_sqrt' a).le
  exact ⟨hr0, Real.le_sqrt_of_sq_le hlow,
    Real.sqrt_le_iff.mpr ⟨by positivity, hhigh⟩⟩

theorem intercept_lower (J A D v bn bd : ℕ)
    (hJ : 0 < J) (hv : 0 < v) (hbn : 0 < bn) (hbd : 0 < bd)
    (hsub : D * bd ≤ v * bn) :
    ((J * A * (v * bn - D * bd) / (v * bn) : ℕ) : ℝ) / J ≤
      (A : ℝ) * (1 - ((D : ℝ) / v) / ((bn : ℝ) / bd)) := by
  have hJ' : (0 : ℝ) < J := by exact_mod_cast hJ
  have hv' : (0 : ℝ) < v := by exact_mod_cast hv
  have hbn' : (0 : ℝ) < bn := by exact_mod_cast hbn
  have hbd' : (0 : ℝ) < bd := by exact_mod_cast hbd
  have hsub' : ((v * bn - D * bd : ℕ) : ℝ) =
      (v : ℝ) * bn - D * bd := by
    rw [Nat.cast_sub hsub]
    push_cast
    ring
  have hround := Nat.cast_div_le
    (m := J * A * (v * bn - D * bd)) (n := v * bn) (α := ℝ)
  have heq :
      (((J * A * (v * bn - D * bd) : ℕ) : ℝ) / (v * bn : ℕ)) / J =
        (A : ℝ) * (1 - ((D : ℝ) / v) / ((bn : ℝ) / bd)) := by
    rw [Nat.cast_mul, Nat.cast_mul, hsub', Nat.cast_mul]
    field_simp
    <;> ring
  calc
    ((J * A * (v * bn - D * bd) / (v * bn) : ℕ) : ℝ) / J ≤
        (((J * A * (v * bn - D * bd) : ℕ) : ℝ) / (v * bn : ℕ)) / J :=
      div_le_div_of_nonneg_right hround hJ'.le
    _ = _ := heq

theorem slope_lower (J A D v bn bd cn cd h : ℕ)
    (hJ : 0 < J) (hv : 0 < v) (hbn : 0 < bn) (hbd : 0 < bd)
    (hcd : 0 < cd) :
    ((J * A * D * cn * bd ^ 2 /
        (v * bn * (bn * cd + cn * bd * h)) : ℕ) : ℝ) / J ≤
      (A : ℝ) * ((D : ℝ) / v) * ((cn : ℝ) / cd) /
        (((bn : ℝ) / bd) *
          ((bn : ℝ) / bd + ((cn : ℝ) / cd) * h)) := by
  have hJ' : (0 : ℝ) < J := by exact_mod_cast hJ
  have hv' : (0 : ℝ) < v := by exact_mod_cast hv
  have hbn' : (0 : ℝ) < bn := by exact_mod_cast hbn
  have hbd' : (0 : ℝ) < bd := by exact_mod_cast hbd
  have hcd' : (0 : ℝ) < cd := by exact_mod_cast hcd
  have hden : 0 < v * bn * (bn * cd + cn * bd * h) := by
    have hterm : 0 < bn * cd := Nat.mul_pos hbn hcd
    positivity
  have hround := Nat.cast_div_le
    (m := J * A * D * cn * bd ^ 2)
    (n := v * bn * (bn * cd + cn * bd * h)) (α := ℝ)
  have heq :
      (((J * A * D * cn * bd ^ 2 : ℕ) : ℝ) /
        (v * bn * (bn * cd + cn * bd * h) : ℕ)) / J =
      (A : ℝ) * ((D : ℝ) / v) * ((cn : ℝ) / cd) /
        (((bn : ℝ) / bd) *
          ((bn : ℝ) / bd + ((cn : ℝ) / cd) * h)) := by
    push_cast
    field_simp
    <;> ring
  calc
    ((J * A * D * cn * bd ^ 2 /
        (v * bn * (bn * cd + cn * bd * h)) : ℕ) : ℝ) / J ≤
      (((J * A * D * cn * bd ^ 2 : ℕ) : ℝ) /
        (v * bn * (bn * cd + cn * bd * h) : ℕ)) / J :=
      div_le_div_of_nonneg_right hround hJ'.le
    _ = _ := heq

theorem intercept_value (D a r ell : ℕ) (hD : 0 < D) :
    ((178107239 * (ell * (r + 1) + 2 * D) : ℕ) : ℝ) /
        (10 ^ 8 * D * (r + 1) : ℕ) =
      (178107239 / 10 ^ 8 : ℝ) *
        ((ell : ℝ) / D + 2 / (r + 1)) := by
  have hD' : (0 : ℝ) < D := by exact_mod_cast hD
  have hr' : (0 : ℝ) < r + 1 := by positivity
  push_cast
  field_simp
  <;> ring

theorem slope_value (a b r : ℕ)
    (ha : 0 < a) (hb : 0 < b) (hr : 0 < r) (hbar : b ≤ a * r) :
    ((178107239 * (a * r - b) : ℕ) : ℝ) /
        (10 ^ 8 * b * a * r : ℕ) =
      (178107239 / 10 ^ 8 : ℝ) *
        (1 / b - 1 / ((a : ℝ) * r)) := by
  have ha' : (0 : ℝ) < a := by exact_mod_cast ha
  have hb' : (0 : ℝ) < b := by exact_mod_cast hb
  have hr' : (0 : ℝ) < r := by exact_mod_cast hr
  rw [Nat.cast_mul, Nat.cast_mul, Nat.cast_sub hbar]
  push_cast
  field_simp
  <;> ring

theorem parameters_intercept_lower (a b v : ℕ)
    (hvalid : (parameters a b v).valid = true) :
    ((parameters a b v).intercept : ℝ) / 16384 ≤
      (a + 1 : ℝ) *
        (1 - (1 / ((v : ℝ) / scale)) /
          ((178107239 / 10 ^ 8 : ℝ) *
            ((logLower a : ℝ) / scale +
              2 / (Nat.sqrt a + 1 : ℕ)))) := by
  rcases parameters_valid a b v hvalid with
    ⟨ha, hab, hbound, hv, hbar, hnum⟩
  let r := Nat.sqrt a
  let bn := 178107239 * (logLower a * (r + 1) + 2 * scale)
  let bd := 10 ^ 8 * scale * (r + 1)
  have hbn : 0 < bn := by
    dsimp [bn]
    have h2 : 0 < 2 * scale := Nat.mul_pos (by decide) scale_pos
    exact Nat.mul_pos (by decide) (by omega)
  have hbd : 0 < bd := by
    dsimp [bd]
    exact Nat.mul_pos (Nat.mul_pos (by norm_num) scale_pos) (by omega)
  have hnum' : scale * bd ≤ v * bn := by
    simpa only [bn, bd, r] using hnum.le
  have hi := intercept_lower 16384 (a + 1) scale v bn bd
    (by norm_num) hv hbn hbd hnum'
  have hbnval : ((bn : ℝ) / bd) =
      (178107239 / 10 ^ 8 : ℝ) *
        ((logLower a : ℝ) / scale + 2 / (r + 1 : ℕ)) :=
    by simpa only [bn, bd, Nat.cast_add, Nat.cast_one] using
      intercept_value scale a r (logLower a) scale_pos
  have hq : (1 : ℝ) / ((v : ℝ) / scale) = (scale : ℝ) / v := by
    have hv' : (0 : ℝ) < v := by exact_mod_cast hv
    have hD' : (0 : ℝ) < scale := by exact_mod_cast scale_pos
    field_simp
  change ((parameters a b v).intercept : ℝ) / 16384 ≤
    (a + 1 : ℝ) *
      (1 - (1 / ((v : ℝ) / scale)) /
        ((178107239 / 10 ^ 8 : ℝ) *
          ((logLower a : ℝ) / scale + 2 / (r + 1 : ℕ))))
  rw [hq, ← hbnval]
  simpa only [parameters, forceNat_eq, Nat.cast_add, Nat.cast_one,
    Nat.cast_ofNat, r, bn, bd] using hi

theorem parameters_slope_lower (a b v : ℕ)
    (hvalid : (parameters a b v).valid = true) :
    ((parameters a b v).slope : ℝ) / 16384 ≤
      (a + 1 : ℝ) * (1 / ((v : ℝ) / scale)) *
        ((178107239 / 10 ^ 8 : ℝ) *
          (1 / b - 1 / ((a : ℝ) * Nat.sqrt a))) /
        (((178107239 / 10 ^ 8 : ℝ) *
          ((logLower a : ℝ) / scale + 2 / (Nat.sqrt a + 1 : ℕ))) *
          ((178107239 / 10 ^ 8 : ℝ) *
            ((logLower a : ℝ) / scale + 2 / (Nat.sqrt a + 1 : ℕ)) +
            ((178107239 / 10 ^ 8 : ℝ) *
              (1 / b - 1 / ((a : ℝ) * Nat.sqrt a))) * (b - a : ℕ))) := by
  rcases parameters_valid a b v hvalid with
    ⟨ha, hab, hbound, hv, hbar, hnum⟩
  let r := Nat.sqrt a
  let bn := 178107239 * (logLower a * (r + 1) + 2 * scale)
  let bd := 10 ^ 8 * scale * (r + 1)
  let cn := 178107239 * (a * r - b)
  let cd := 10 ^ 8 * b * a * r
  have hbn : 0 < bn := by
    dsimp [bn]
    have h2 : 0 < 2 * scale := Nat.mul_pos (by decide) scale_pos
    exact Nat.mul_pos (by decide) (by omega)
  have hbd : 0 < bd := by
    dsimp [bd]
    exact Nat.mul_pos (Nat.mul_pos (by norm_num) scale_pos) (by omega)
  have hr : 0 < r := by
    have := (sqrt_bracket a (by omega : 1 ≤ a)).1
    exact_mod_cast this
  have hcd : 0 < cd := by
    dsimp [cd]
    exact Nat.mul_pos (Nat.mul_pos (Nat.mul_pos (by norm_num)
      (by omega : 0 < b)) (by omega : 0 < a)) hr
  have hvalB : ((bn : ℝ) / bd) =
      (178107239 / 10 ^ 8 : ℝ) *
        ((logLower a : ℝ) / scale + 2 / (r + 1 : ℕ)) := by
    simpa only [bn, bd, Nat.cast_add, Nat.cast_one] using
      intercept_value scale a r (logLower a) scale_pos
  have hvalC : ((cn : ℝ) / cd) =
      (178107239 / 10 ^ 8 : ℝ) *
        (1 / b - 1 / ((a : ℝ) * r)) := by
    simpa only [cn, cd] using slope_value a b r
      (by omega) (by omega) hr hbar.le
  have hq : (1 : ℝ) / ((v : ℝ) / scale) = (scale : ℝ) / v := by
    have hv' : (0 : ℝ) < v := by exact_mod_cast hv
    have hD' : (0 : ℝ) < scale := by exact_mod_cast scale_pos
    field_simp
  have hs := slope_lower 16384 (a + 1) scale v bn bd cn cd (b - a)
    (by norm_num) hv hbn hbd hcd
  change ((parameters a b v).slope : ℝ) / 16384 ≤
    (a + 1 : ℝ) * (1 / ((v : ℝ) / scale)) *
      ((178107239 / 10 ^ 8 : ℝ) *
        (1 / b - 1 / ((a : ℝ) * r))) /
      (((178107239 / 10 ^ 8 : ℝ) *
        ((logLower a : ℝ) / scale + 2 / (r + 1 : ℕ))) *
        ((178107239 / 10 ^ 8 : ℝ) *
          ((logLower a : ℝ) / scale + 2 / (r + 1 : ℕ)) +
          ((178107239 / 10 ^ 8 : ℝ) *
            (1 / b - 1 / ((a : ℝ) * r))) * (b - a : ℕ)))
  rw [hq, ← hvalB, ← hvalC]
  simpa only [parameters, forceNat_eq, Nat.cast_add, Nat.cast_one,
    Nat.cast_ofNat, r, bn, bd, cn, cd] using hs

theorem parameterized_bound (a b v k : ℕ) (x : ℝ)
    (hvalid : (parameters a b v).valid = true)
    (hax : (a : ℝ) ≤ x) (hxb : x ≤ b)
    (hv : ((v : ℝ) / scale) ≤ RosserMomentBridge.reciprocalProduct a)
    (hcard : (Nat.primesLE ⌊x⌋₊ \ Nat.primesLE a).card ≤ k)
    (hcount : (k : ℝ) <
      ((parameters a b v).intercept : ℝ) / 16384 +
        ((parameters a b v).slope : ℝ) / 16384 * (x - a)) :
    RosserBlockCheck.Bound x := by
  rcases parameters_valid a b v hvalid with
    ⟨ha, hab, hbmax, hv0, hbar, hnum⟩
  let r := Nat.sqrt a
  let g : ℝ := 178107239 / 10 ^ 8
  let L : ℝ := (logLower a : ℝ) / scale
  let S : ℝ := (r + 1 : ℕ)
  let B : ℝ := g * (L + 2 / S)
  let C : ℝ := g * (1 / b - 1 / ((a : ℝ) * r))
  let q : ℝ := (v : ℝ) / scale
  have hg : 0 ≤ g := by dsimp [g]; norm_num
  have hgamma : g ≤ Real.exp Real.eulerMascheroniConstant :=
    RosserProductCertificate.exp_gamma_lower
  have hsqrt := sqrt_bracket a (by omega : 1 ≤ a)
  have hr : 0 < (r : ℝ) := hsqrt.1
  have hrS : (r : ℝ) ≤ Real.sqrt a := hsqrt.2.1
  have hS : 0 < S := by dsimp [S]; positivity
  have hSa : Real.sqrt a ≤ S := hsqrt.2.2
  have hL : L ≤ Real.log a :=
    logLower_sound a (by omega : 1 ≤ a)
  have hB : 0 < B := by
    have hgp : 0 < g := by dsimp [g]; norm_num
    have hD : (0 : ℝ) < scale := by exact_mod_cast scale_pos
    have hL0 : 0 ≤ L :=
      div_nonneg (by exact_mod_cast Nat.zero_le (logLower a))
        (by exact_mod_cast Nat.zero_le scale)
    have h2 : 0 < 2 / S := by positivity
    exact mul_pos hgp (by linarith only [hL0, h2])
  have hC : 0 ≤ C := by
    have hval := slope_value a b r (by omega) (by omega)
      (by exact_mod_cast hr) hbar.le
    have hnonneg : (0 : ℝ) ≤
        ((178107239 * (a * r - b) : ℕ) : ℝ) /
          (10 ^ 8 * b * a * r : ℕ) := by positivity
    dsimp [C, g, r]
    rw [hval] at hnonneg
    exact hnonneg
  have hq : 0 < q := by
    dsimp [q]
    have hD : (0 : ℝ) < scale := by exact_mod_cast scale_pos
    have hv' : (0 : ℝ) < v := by exact_mod_cast hv0
    positivity
  have hI : ((parameters a b v).intercept : ℝ) / 16384 ≤
      (a + 1 : ℝ) * (1 - (1 / q) / B) :=
    parameters_intercept_lower a b v hvalid
  have hM : ((parameters a b v).slope : ℝ) / 16384 ≤
      (a + 1 : ℝ) * (1 / q) * C / (B * (B + C * (b - a : ℕ))) :=
    parameters_slope_lower a b v hvalid
  have hfloor : a ≤ ⌊x⌋₊ := Nat.le_floor hax
  have hrealha : (2 : ℝ) ≤ a := by exact_mod_cast (show 2 ≤ a by omega)
  have hd : 0 ≤ x - a := sub_nonneg.mpr hax
  have hdh : x - (a : ℝ) ≤ (b - a : ℕ) := by
    rw [Nat.cast_sub hab.le]
    linarith only [hxb]
  have hp := RosserPrefixBounds.affine_prefix_to_product a ⌊x⌋₊ k q B C
    (b - a : ℕ) (x - a)
    (((parameters a b v).intercept : ℝ) / 16384)
    (((parameters a b v).slope : ℝ) / 16384)
    (by omega) hfloor hq hB hC hd hdh hv hcard hI hM hcount
  have ht := RosserPrefixBounds.rounded_target_linear_lower
    (a : ℝ) b x g L r S (by linarith only [hrealha]) hax hxb hg hgamma
    hL hr hrS hS hSa
  change RosserProductCertificate.eulerProduct ⌊x⌋₊ <
    Real.exp Real.eulerMascheroniConstant * Real.log x +
      2 * Real.exp Real.eulerMascheroniConstant / Real.sqrt x
  calc
    RosserProductCertificate.eulerProduct ⌊x⌋₊ < B + C * (x - a) := hp
    _ ≤ Real.exp Real.eulerMascheroniConstant *
        (Real.log x + 2 / Real.sqrt x) := ht
    _ = _ := by ring

end RosserPrefixParams

-- Source: Solutions/RosserBitSieve.lean
/-!
A bit sieve using only natural-number arithmetic, suitable for kernel reduction.
The divisors are untrusted data: they need only satisfy 2 <= d < a.
No claim that the divisor list is complete or consists of primes is required.
-/

namespace RosserBitSieve

theorem periodicMask_eq_sum (d count : ℕ) (hd : 0 < d) :
    periodicMask d count = ∑ i ∈ Finset.range count, (2 ^ d) ^ i := by
  rw [Nat.geomSum_eq (Nat.one_lt_two_pow (Nat.ne_of_gt hd)), periodicMask, pow_mul]

theorem periodicMask_succ (d count : ℕ) (hd : 0 < d) :
    periodicMask d (count + 1) = 2 ^ d * periodicMask d count + 1 := by
  rw [periodicMask_eq_sum d (count + 1) hd, periodicMask_eq_sum d count hd,
    geom_sum_succ]

/-- Every set bit in a periodic mask has index divisible by d. -/
theorem periodicMask_bit_dvd (d count i : ℕ) (hd : 0 < d)
    (hbit : (periodicMask d count).testBit i = true) : d ∣ i := by
  induction count generalizing i with
  | zero => simp [periodicMask] at hbit
  | succ count ih =>
    rw [periodicMask_succ d count hd,
      Nat.testBit_two_pow_mul_add _ (Nat.one_lt_two_pow (Nat.ne_of_gt hd))] at hbit
    split at hbit
    · have hone : (1 : ℕ).testBit i = decide (i = 0) := by
        simpa only [Nat.pow_zero, eq_comm] using (Nat.testBit_two_pow (n := 0) (m := i))
      rw [hone] at hbit
      have hi : i = 0 := of_decide_eq_true hbit
      subst i
      exact dvd_zero d
    · rename_i hi
      have hdiv := ih (i - d) hbit
      have heq : i = (i - d) + d := by omega
      rw [heq]
      exact dvd_add hdiv (dvd_refl d)

theorem first_multiple (a d : ℕ) (hd : 0 < d) :
    d ∣ a + (d - a % d) % d := by
  apply Nat.dvd_of_mod_eq_zero
  by_cases hz : a % d = 0
  · simp [hz]
  · have hm := Nat.mod_lt a hd
    have hsmall : d - a % d < d := by omega
    rw [Nat.mod_eq_of_lt hsmall, Nat.add_mod]
    rw [Nat.mod_eq_of_lt hsmall, Nat.add_sub_of_le hm.le, Nat.mod_self]

theorem divisorMask_bit_dvd (a len d i : ℕ) (hd : 0 < d)
    (hbit : (divisorMask a len d).testBit i = true) : d ∣ a + i := by
  unfold divisorMask at hbit
  rw [Nat.testBit_mul_two_pow, Bool.and_eq_true] at hbit
  obtain ⟨hoffset, hperiodic⟩ := hbit
  have hoffset' : (d - a % d) % d ≤ i := of_decide_eq_true hoffset
  have hp := periodicMask_bit_dvd d _ _ hd hperiodic
  have hfirst := first_multiple a d hd
  have heq : a + i = (a + (d - a % d) % d) + (i - (d - a % d) % d) := by omega
  rw [heq]
  exact dvd_add hfirst hp

theorem divisorMask_preserves_prime (a len d i : ℕ)
    (hd : 2 ≤ d) (hda : d < a) (hp : Nat.Prime (a + i)) :
    (divisorMask a len d).testBit i = false := by
  apply Bool.eq_false_iff.mpr
  intro hbit
  have hdiv := divisorMask_bit_dvd a len d i (by omega) hbit
  rcases hp.eq_one_or_self_of_dvd d hdiv with h | h <;> omega

theorem compositeMask_preserves_prime (divisors : List ℕ) (a len i : ℕ)
    (hds : ∀ d ∈ divisors, 2 ≤ d ∧ d < a) (hp : Nat.Prime (a + i)) :
    (compositeMask divisors a len).testBit i = false := by
  suffices h : ∀ mask : ℕ, mask.testBit i = false →
      (divisors.foldl (fun mask d => mask ||| divisorMask a len d) mask).testBit i = false by
    exact h 0 (by simp)
  induction divisors with
  | nil => simp
  | cons d ds ih =>
    intro mask hmask
    apply ih (fun q hq => hds q (by simp [hq]))
    rw [Nat.testBit_or, hmask, divisorMask_preserves_prime a len d i
      (hds d (by simp)).1 (hds d (by simp)).2 hp]
    rfl

theorem candidateMask_preserves_prime (divisors : List ℕ) (a len i : ℕ)
    (hds : ∀ d ∈ divisors, 2 ≤ d ∧ d < a) (hi : i < len)
    (hp : Nat.Prime (a + i)) :
    (candidateMask divisors a len).testBit i = true := by
  simp [candidateMask, Nat.testBit_xor, Nat.testBit_two_pow_sub_one,
    Nat.testBit_mod_two_pow, hi, compositeMask_preserves_prime divisors a len i hds hp]

theorem mem_enumBits (depth start mask x : ℕ) :
    x ∈ enumBits depth start mask ↔
      start ≤ x ∧ x < start + 2 ^ depth ∧ mask.testBit (x - start) = true := by
  induction depth generalizing start mask with
  | zero =>
    simp only [enumBits, Nat.pow_zero]
    split
    · rename_i h
      have hm : mask % 2 = 1 := by simpa using h
      constructor
      · intro hx
        have hx' : x = start := by simpa using hx
        subst x
        simp [Nat.testBit_eq_decide_div_mod_eq, hm]
      · intro hx
        have hx' : x = start := by omega
        simp [hx']
    · rename_i h
      have hm : mask % 2 ≠ 1 := by simpa using h
      constructor
      · simp
      · intro hx
        have hx' : x = start := by omega
        subst x
        simp [Nat.testBit_eq_decide_div_mod_eq, hm] at hx
  | succ depth ih =>
    by_cases hm : mask = 0
    · subst mask
      simp [enumBits]
    · simp only [enumBits, beq_iff_eq, hm, if_false, List.mem_append, ih,
        Nat.testBit_mod_two_pow, Nat.testBit_div_two_pow, Bool.and_eq_true,
        decide_eq_true_eq, Nat.pow_succ]
      constructor
      · intro hx
        rcases hx with ⟨hlo, hhi, _, hb⟩ | ⟨hlo, hhi, hb⟩
        · exact ⟨hlo, by omega, hb⟩
        · refine ⟨by omega, by omega, ?_⟩
          have heq : x - (start + 2 ^ depth) + 2 ^ depth = x - start := by omega
          simpa only [heq] using hb
      · intro ⟨hlo, hhi, hb⟩
        by_cases hleft : x < start + 2 ^ depth
        · exact Or.inl ⟨hlo, hleft, by omega, hb⟩
        · right
          refine ⟨by omega, by omega, ?_⟩
          have heq : x - (start + 2 ^ depth) + 2 ^ depth = x - start := by omega
          simpa only [heq] using hb

theorem enumBits_nodup (depth start mask : ℕ) : (enumBits depth start mask).Nodup := by
  induction depth generalizing start mask with
  | zero => simp only [enumBits]; split <;> simp
  | succ depth ih =>
    simp only [enumBits]
    split
    · simp
    · apply List.Nodup.append (ih _ _) (ih _ _)
      apply List.disjoint_left.mpr
      intro x hx hx'
      have hleft := (mem_enumBits _ _ _ _).mp hx
      have hright := (mem_enumBits _ _ _ _).mp hx'
      omega

theorem candidateMask_bit (divisors : List ℕ) (a len i : ℕ) :
    (candidateMask divisors a len).testBit i =
      (decide (i < len) && !(compositeMask divisors a len).testBit i) := by
  by_cases hi : i < len <;>
    simp [candidateMask, Nat.testBit_xor, Nat.testBit_two_pow_sub_one,
      Nat.testBit_mod_two_pow, hi]

theorem offsets_lt (divisors : List ℕ) (depth a len i : ℕ)
    (hi : i ∈ offsets divisors depth a len) : i < len := by
  have hb := (mem_enumBits _ _ _ _).mp hi
  simp only [Nat.sub_zero, candidateMask_bit, Bool.and_eq_true, decide_eq_true_eq] at hb
  exact hb.2.2.1

theorem offsets_preserve_primes (divisors : List ℕ) (depth a len p : ℕ)
    (hds : ∀ d ∈ divisors, 2 ≤ d ∧ d < a) (hlen : len ≤ 2 ^ depth)
    (hpa : a ≤ p) (hpB : p < a + len) (hp : Nat.Prime p) :
    p - a ∈ offsets divisors depth a len := by
  apply (mem_enumBits _ _ _ _).mpr
  refine ⟨Nat.zero_le _, by omega, ?_⟩
  simp only [Nat.sub_zero]
  apply candidateMask_preserves_prime divisors a len (p - a) hds (by omega)
  simpa only [Nat.add_sub_of_le hpa] using hp

theorem offsets_nodup (divisors : List ℕ) (depth a len : ℕ) :
    (offsets divisors depth a len).Nodup := enumBits_nodup _ _ _

theorem mem_windowOffsets (depth mask shift len d : ℕ) :
    d ∈ windowOffsets depth mask shift len ↔
      0 < d ∧ d ≤ len ∧ d ≤ 2 ^ depth ∧ mask.testBit (d - 1 + shift) = true := by
  simp only [windowOffsets, List.mem_map, mem_enumBits, Nat.zero_add, Nat.sub_zero,
    Nat.testBit_mod_two_pow, Nat.testBit_div_two_pow, Bool.and_eq_true,
    decide_eq_true_eq]
  constructor
  · rintro ⟨i, ⟨_, hi, hlen, hb⟩, rfl⟩
    exact ⟨by omega, by omega, by omega, by simpa using hb⟩
  · rintro ⟨hd, hlen, hdepth, hb⟩
    exact ⟨d - 1, ⟨Nat.zero_le _, by omega, by omega, hb⟩, by omega⟩

theorem windowOffsets_nodup (depth mask shift len : ℕ) :
    (windowOffsets depth mask shift len).Nodup := by
  apply List.Nodup.map _ (enumBits_nodup _ _ _)
  intro a b h
  change a + 1 = b + 1 at h
  omega

end RosserBitSieve

-- Source: Solutions/RosserPackedBarrier.lean
/-! Arithmetic lemmas for the packed prefix-count certificate. -/

namespace RosserPackedBarrier

theorem forceNat_eq {α : Sort _} (n : ℕ) (f : ℕ → α) :
    RosserScan.forceNat n f = f n := by
  cases n <;> rfl

def candidateCount (mask d : ℕ) : ℕ :=
  ((List.range d).filter (fun i => mask.testBit i)).length

/-- Little-endian packing with a fixed number of digits. -/
def pack (q : ℕ) : ℕ → (ℕ → ℕ) → ℕ
  | 0, _ => 0
  | n + 1, f => f 0 + q * pack q n (fun i => f (i + 1))

theorem pack_congr (q n : ℕ) {f g : ℕ → ℕ}
    (h : ∀ i < n, f i = g i) : pack q n f = pack q n g := by
  induction n generalizing f g with
  | zero => rfl
  | succ n ih =>
    simp only [pack]
    rw [h 0 (by omega), ih (fun i hi => h (i + 1) (by omega))]

theorem pack_add (q n : ℕ) (f g : ℕ → ℕ) :
    pack q n (fun i => f i + g i) = pack q n f + pack q n g := by
  induction n generalizing f g with
  | zero => rfl
  | succ n ih => simp only [pack, ih]; ring

theorem pack_mul (q n c : ℕ) (f : ℕ → ℕ) :
    pack q n (fun i => c * f i) = c * pack q n f := by
  induction n generalizing f with
  | zero => simp [pack]
  | succ n ih => simp only [pack, ih]; ring

theorem pack_mono (q n : ℕ) {f g : ℕ → ℕ}
    (h : ∀ i < n, f i ≤ g i) : pack q n f ≤ pack q n g := by
  induction n generalizing f g with
  | zero => rfl
  | succ n ih =>
    exact Nat.add_le_add (h 0 (by omega))
      (Nat.mul_le_mul_left q (ih (fun i hi => h (i + 1) (by omega))))

theorem pack_sub (q n : ℕ) {f g : ℕ → ℕ}
    (h : ∀ i < n, g i ≤ f i) :
    pack q n (fun i => f i - g i) = pack q n f - pack q n g := by
  have heq : pack q n (fun i => f i - g i) + pack q n g = pack q n f := by
    rw [← pack_add]
    exact pack_congr q n (fun i hi => Nat.sub_add_cancel (h i hi))
  omega

theorem pack_lt (q n : ℕ) (hq : 0 < q) {f : ℕ → ℕ}
    (h : ∀ i < n, f i < q) : pack q n f < q ^ n := by
  induction n generalizing f with
  | zero => simp [pack]
  | succ n ih =>
    have htail := ih (fun i hi => h (i + 1) (by omega))
    have hhead := h 0 (by omega)
    simp only [pack, pow_succ]
    nlinarith

theorem pack_mod (q n : ℕ) (hq : 0 < q) {f : ℕ → ℕ}
    (h : f 0 < q) : pack q (n + 1) f % q = f 0 := by
  simp [pack, Nat.mod_eq_of_lt h]

theorem pack_div (q n : ℕ) (hq : 0 < q) {f : ℕ → ℕ}
    (h : f 0 < q) : pack q (n + 1) f / q = pack q n (fun i => f (i + 1)) := by
  simp [pack, Nat.add_mul_div_left _ _ hq, Nat.div_eq_of_lt h]

theorem pack_digit (q n i : ℕ) (hq : 0 < q) {f : ℕ → ℕ}
    (h : ∀ j < n, f j < q) (hi : i < n) :
    pack q n f / q ^ i % q = f i := by
  induction i generalizing n f with
  | zero =>
    obtain ⟨n, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)
    simpa using pack_mod q n hq (h 0 (by omega))
  | succ i ih =>
    obtain ⟨n, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)
    rw [pow_succ', ← Nat.div_div_eq_div_mul, pack_div q n hq (h 0 (by omega))]
    exact ih n (fun j hj => h (j + 1) (by omega)) (by omega)

theorem pack_eq_sum (q n : ℕ) (f : ℕ → ℕ) :
    pack q n f = ∑ i ∈ Finset.range n, f i * q ^ i := by
  induction n generalizing f with
  | zero => simp [pack]
  | succ n ih =>
    rw [pack, ih, Finset.sum_range_succ']
    simp only [pow_zero, Nat.mul_one, Finset.mul_sum, pow_succ]
    rw [Nat.add_comm (f 0)]
    congr 1
    apply Finset.sum_congr rfl
    intro i hi
    ring

theorem pack_const_one (q n : ℕ) (hq : 1 < q) :
    pack q n (fun _ => 1) = (q ^ n - 1) / (q - 1) := by
  rw [pack_eq_sum]
  simp only [Nat.one_mul]
  exact Nat.geomSum_eq hq n

theorem pack_const (q n c : ℕ) :
    pack q n (fun _ => c) = c * pack q n (fun _ => 1) := by
  simpa using pack_mul q n c (fun _ => 1)

theorem pack_one_identity (q n : ℕ) (hq : 1 ≤ q) :
    (q - 1) * pack q n (fun _ => 1) + 1 = q ^ n := by
  induction n with
  | zero => simp [pack]
  | succ n ih =>
    simp only [pack, pow_succ]
    have hq' := Nat.sub_add_cancel hq
    nlinarith

def prefixSum (f : ℕ → ℕ) (n : ℕ) : ℕ := ∑ i ∈ Finset.range n, f i

@[simp] theorem prefixSum_one (f : ℕ → ℕ) : prefixSum f 1 = f 0 := by
  simp [prefixSum]

theorem prefixSum_shift (f : ℕ → ℕ) (n : ℕ) :
    prefixSum f (n + 1) = f 0 + prefixSum (fun i => f (i + 1)) n := by
  simp [prefixSum, Finset.sum_range_succ', Nat.add_comm]

theorem pack_prefix_identity (q n : ℕ) (f : ℕ → ℕ) (hq : 1 ≤ q) :
    (q - 1) * pack q n (fun i => prefixSum f (i + 1)) + pack q n f =
      q ^ n * prefixSum f n := by
  induction n generalizing f with
  | zero => simp [pack, prefixSum]
  | succ n ih =>
    have hy : pack q (n + 1) (fun i => prefixSum f (i + 1)) =
        f 0 + q * (f 0 * pack q n (fun _ => 1) +
          pack q n (fun i => prefixSum (fun j => f (j + 1)) (i + 1))) := by
      rw [pack, prefixSum_one, ← pack_const, ← pack_add]
      congr 2
      apply pack_congr
      intro i hi
      exact prefixSum_shift f (i + 1)
    rw [hy, pack, prefixSum_shift, pow_succ]
    have htail := congrArg (fun x => q * x) (ih (fun i => f (i + 1)))
    have hr := congrArg (fun x => q * f 0 * x) (pack_one_identity q n hq)
    have hq' := Nat.sub_add_cancel hq
    nlinarith

theorem prefixSum_mono (f : ℕ → ℕ) {a b : ℕ} (h : a ≤ b) :
    prefixSum f a ≤ prefixSum f b := by
  exact Finset.sum_le_sum_of_subset (Finset.range_mono h)

/-- Multiplication by a repunit packs all cumulative digit sums at once. -/
theorem pack_prefix_mod (q n : ℕ) (f : ℕ → ℕ) (hq : 1 < q)
    (hsum : prefixSum f n < q) :
    (pack q n f * pack q n (fun _ => 1)) % q ^ n =
      pack q n (fun i => prefixSum f (i + 1)) := by
  have hcop : Nat.Coprime (q ^ n) (q - 1) := by
    apply Nat.Coprime.pow_left
    exact (Nat.coprime_self_sub_right (by omega : 1 ≤ q)).mpr (by simp)
  have hx : (q - 1) * (pack q n f * pack q n (fun _ => 1)) + pack q n f =
      q ^ n * pack q n f := by
    have := congrArg (fun x => pack q n f * x) (pack_one_identity q n (by omega))
    nlinarith
  have heq :
      (q - 1) * (pack q n f * pack q n (fun _ => 1)) + pack q n f ≡
      (q - 1) * pack q n (fun i => prefixSum f (i + 1)) + pack q n f [MOD q ^ n] := by
    rw [hx, pack_prefix_identity q n f (by omega)]
    simp [Nat.ModEq]
  have heq' := Nat.ModEq.add_right_cancel (Nat.ModEq.refl (pack q n f)) heq
  have hc := Nat.ModEq.cancel_left_of_coprime hcop heq'
  rw [Nat.ModEq, Nat.mod_eq_of_lt (pack_lt q n (by omega) (fun i hi =>
    (prefixSum_mono f (by omega : i + 1 ≤ n)).trans_lt hsum))] at hc
  exact hc

theorem pack_testBit (w n i j : ℕ) {f : ℕ → ℕ}
    (h : ∀ k < n, f k < 2 ^ w) (hi : i < n) (hj : j < w) :
    (pack (2 ^ w) n f).testBit (w * i + j) = (f i).testBit j := by
  have hd := pack_digit (2 ^ w) n i (by positivity) h hi
  have hb := congrArg (fun x : ℕ => x.testBit j) hd
  rw [Nat.testBit_mod_two_pow, show decide (j < w) = true by simp [hj],
    Bool.true_and] at hb
  simpa only [← pow_mul, Nat.testBit_div_two_pow, Nat.add_comm] using hb

theorem pack_testBit_all (w n k : ℕ) (hw : 0 < w) {f : ℕ → ℕ}
    (h : ∀ i < n, f i < 2 ^ w) :
    (pack (2 ^ w) n f).testBit k =
      if k / w < n then (f (k / w)).testBit (k % w) else false := by
  have hdecomp := Nat.mod_add_div k w
  by_cases hi : k / w < n
  · rw [if_pos hi]
    have hk : k = w * (k / w) + k % w := by omega
    simpa only [← hk] using pack_testBit w n (k / w) (k % w) h hi (Nat.mod_lt k hw)
  · rw [if_neg hi]
    have hkn : w * n ≤ k := by
      have := Nat.mul_le_mul_left w (by omega : n ≤ k / w)
      omega
    apply Nat.testBit_eq_false_of_lt
    apply (pack_lt (2 ^ w) n (by positivity) h).trans_le
    rw [← pow_mul]
    exact Nat.pow_le_pow_right (by omega) hkn

theorem pack_and (w n : ℕ) (hw : 0 < w) (f g : ℕ → ℕ)
    (hf : ∀ i < n, f i < 2 ^ w) (hg : ∀ i < n, g i < 2 ^ w) :
    pack (2 ^ w) n f &&& pack (2 ^ w) n g =
      pack (2 ^ w) n (fun i => f i &&& g i) := by
  apply Nat.eq_of_testBit_eq
  intro k
  rw [Nat.testBit_and, pack_testBit_all w n k hw hf, pack_testBit_all w n k hw hg,
    pack_testBit_all w n k hw (fun i hi => Nat.and_le_left.trans_lt (hf i hi))]
  split_ifs <;> simp [Nat.testBit_and]

/-- A low mask discards exactly the bits shifted in from the next digit. -/
theorem pack_shift_and (w n s : ℕ) (hw : 0 < w) (hs : s ≤ w) (f g : ℕ → ℕ)
    (hf : ∀ i < n, f i < 2 ^ w) (hg : ∀ i < n, g i < 2 ^ (w - s)) :
    (pack (2 ^ w) n f >>> s) &&& pack (2 ^ w) n g =
      pack (2 ^ w) n (fun i => (f i >>> s) &&& g i) := by
  have hg' : ∀ i < n, g i < 2 ^ w := fun i hi =>
    (hg i hi).trans_le (Nat.pow_le_pow_right (by omega) (by omega))
  have hout : ∀ i < n, ((f i >>> s) &&& g i) < 2 ^ w := fun i hi =>
    Nat.and_le_right.trans_lt (hg' i hi)
  apply Nat.eq_of_testBit_eq
  intro k
  rw [Nat.testBit_and, pack_testBit_all w n k hw hg', pack_testBit_all w n k hw hout]
  by_cases hi : k / w < n
  · rw [if_pos hi, if_pos hi, Nat.testBit_and]
    by_cases hb : (g (k / w)).testBit (k % w) = true
    · have hsmall : k % w < w - s := by
        by_contra hh
        have hfals := Nat.testBit_eq_false_of_lt ((hg (k / w) hi).trans_le
          (Nat.pow_le_pow_right (by omega) (by omega : w - s ≤ k % w)))
        simp [hb] at hfals
      have hd := Nat.mod_add_div k w
      have heq : s + k = w * (k / w) + (k % w + s) := by omega
      rw [Nat.testBit_shiftRight, heq, pack_testBit w n (k / w) (k % w + s) hf hi
        (by omega), Nat.testBit_shiftRight]
      simp [Nat.add_comm]
    · simp [Bool.eq_false_iff.mpr hb]
  · simp [hi]

theorem pack_pair (q n : ℕ) (f : ℕ → ℕ) :
    pack q (2 * n) f = pack (q * q) n (fun i => f (2 * i) + q * f (2 * i + 1)) := by
  induction n generalizing f with
  | zero => simp [pack]
  | succ n ih =>
    rw [show 2 * (n + 1) = 2 * n + 1 + 1 by omega]
    simp only [pack]
    rw [ih]
    have heq :
        pack (q * q) n (fun i => f (2 * i + 1 + 1) + q * f (2 * i + 1 + 1 + 1)) =
        pack (q * q) n (fun i => f (2 * (i + 1)) + q * f (2 * (i + 1) + 1)) := by
      apply pack_congr
      intro i hi
      congr 2 <;> omega
    rw [heq]
    ring

theorem pack_digits (w n mask : ℕ) (hw : 0 < w) (hm : mask < 2 ^ (w * n)) :
    pack (2 ^ w) n (fun i => mask / 2 ^ (w * i) % 2 ^ w) = mask := by
  apply Nat.eq_of_testBit_eq
  intro k
  rw [pack_testBit_all w n k hw (fun i hi => Nat.mod_lt _ (by positivity))]
  by_cases hi : k / w < n
  · rw [if_pos hi, Nat.testBit_mod_two_pow, Nat.testBit_div_two_pow]
    have hj := Nat.mod_lt k hw
    simp only [show decide (k % w < w) = true by simp [hj], Bool.true_and]
    rw [Nat.mod_add_div]
  · rw [if_neg hi]
    symm
    apply Nat.testBit_eq_false_of_lt
    apply hm.trans_le (Nat.pow_le_pow_right (by omega) ?_)
    have hdecomp := Nat.mod_add_div k w
    have := Nat.mul_le_mul_left w (by omega : n ≤ k / w)
    omega

theorem stripe_eq (w n : ℕ) (hw : 0 < w) :
    (2 ^ (2 * w * n) - 1) / (2 ^ w + 1) =
      pack (2 ^ (2 * w)) n (fun _ => 2 ^ w - 1) := by
  have hq : 1 ≤ 2 ^ w := Nat.succ_le_of_lt (Nat.two_pow_pos w)
  have hr := pack_one_identity (2 ^ (2 * w)) n
    (Nat.succ_le_of_lt (Nat.two_pow_pos (2 * w)))
  have hpow : 2 ^ (2 * w) = 2 ^ w * 2 ^ w := by
    rw [two_mul, pow_add]
  have hsub : 2 ^ (2 * w) - 1 = (2 ^ w + 1) * (2 ^ w - 1) := by
    have := Nat.sub_add_cancel hq
    rw [hpow]
    have hs := Nat.sub_add_cancel (show 1 ≤ 2 ^ w * 2 ^ w by nlinarith)
    nlinarith
  have hall : 2 ^ (2 * w * n) - 1 =
      (2 ^ w + 1) * ((2 ^ w - 1) * pack (2 ^ (2 * w)) n (fun _ => 1)) := by
    rw [pow_mul, ← hr, Nat.add_sub_cancel, hsub]
    ring
  rw [hall, Nat.mul_div_cancel_left _ (by positivity)]
  exact (pack_const _ _ _).symm

/-- One parallel pairwise population-count step. -/
def mergeCounts (w n x : ℕ) : ℕ :=
  RosserScan.forceNat ((2 ^ (2 * w * n) - 1) / (2 ^ w + 1)) fun stripe =>
    (x &&& stripe) + ((x >>> w) &&& stripe)

theorem mergeCounts_sound (w n : ℕ) (hw : 0 < w) (f : ℕ → ℕ)
    (hf : ∀ i < 2 * n, f i < 2 ^ w) :
    mergeCounts w n (pack (2 ^ w) (2 * n) f) =
      pack (2 ^ (2 * w)) n (fun i => f (2 * i) + f (2 * i + 1)) := by
  have hq : 0 < 2 ^ w := by positivity
  have hpow : 2 ^ w * 2 ^ w = 2 ^ (2 * w) := by rw [two_mul, pow_add]
  let g := fun i => f (2 * i) + 2 ^ w * f (2 * i + 1)
  have hg : ∀ i < n, g i < 2 ^ (2 * w) := by
    intro i hi
    have h0 := hf (2 * i) (by omega)
    have h1 := hf (2 * i + 1) (by omega)
    dsimp [g]
    rw [← hpow]
    nlinarith
  have hm : ∀ i < n, 2 ^ w - 1 < 2 ^ (2 * w - w) := by
    intro i hi
    rw [show 2 * w - w = w by omega]
    omega
  have hlo : ∀ i < n, (g i &&& (2 ^ w - 1)) = f (2 * i) := by
    intro i hi
    simp only [g, Nat.and_two_pow_sub_one_eq_mod, Nat.add_mul_mod_self_left,
      Nat.mod_eq_of_lt (hf (2 * i) (by omega))]
  have hhi : ∀ i < n, ((g i >>> w) &&& (2 ^ w - 1)) = f (2 * i + 1) := by
    intro i hi
    simp only [g, Nat.shiftRight_eq_div_pow, Nat.add_mul_div_left _ _ hq,
      Nat.div_eq_of_lt (hf (2 * i) (by omega)), Nat.zero_add,
      Nat.and_two_pow_sub_one_eq_mod, Nat.mod_eq_of_lt (hf (2 * i + 1) (by omega))]
  simp only [mergeCounts, forceNat_eq, stripe_eq w n hw, pack_pair, hpow]
  change (pack (2 ^ (2 * w)) n g &&& pack (2 ^ (2 * w)) n (fun _ => 2 ^ w - 1)) +
    ((pack (2 ^ (2 * w)) n g >>> w) &&& pack (2 ^ (2 * w)) n (fun _ => 2 ^ w - 1)) = _
  rw [pack_and (2 * w) n (by omega) g _ hg (fun i hi => (hm i hi).trans_le
    (Nat.pow_le_pow_right (by omega) (by omega))),
    pack_shift_and (2 * w) n w (by omega) (by omega) g _ hg hm, ← pack_add]
  apply pack_congr
  intro i hi
  rw [hlo i hi, hhi i hi]

def bitValue (mask i : ℕ) : ℕ := (mask.testBit i).toNat

theorem bitValue_le_one (mask i : ℕ) : bitValue mask i ≤ 1 := by
  unfold bitValue
  cases mask.testBit i <;> decide

theorem bitValue_eq_digit (mask i : ℕ) : bitValue mask i = mask / 2 ^ i % 2 := by
  simp only [bitValue, Nat.testBit_eq_decide_div_mod_eq]
  have h := Nat.mod_lt (mask / 2 ^ i) (by omega : 0 < 2)
  by_cases heq : mask / 2 ^ i % 2 = 1
  · simp [heq]
  · have hz : mask / 2 ^ i % 2 = 0 := by omega
    simp [hz]

theorem candidateCount_eq_sum (mask d : ℕ) :
    candidateCount mask d = prefixSum (bitValue mask) d := by
  induction d with
  | zero => simp [candidateCount, prefixSum]
  | succ d ih =>
    simp only [candidateCount, List.range_succ, List.filter_append, List.length_append,
      prefixSum, Finset.sum_range_succ] at *
    rw [ih]
    cases h : mask.testBit d <;> simp [List.filter, bitValue, h]

def blockSum (f : ℕ → ℕ) (w j : ℕ) : ℕ :=
  ∑ i ∈ Finset.range w, f (w * j + i)

@[simp] theorem blockSum_one (f : ℕ → ℕ) (j : ℕ) : blockSum f 1 j = f j := by
  simp [blockSum]

theorem blockSum_le (f : ℕ → ℕ) (hf : ∀ i, f i ≤ 1) (w j : ℕ) :
    blockSum f w j ≤ w := by
  calc
    _ ≤ ∑ _i ∈ Finset.range w, 1 := Finset.sum_le_sum (fun i hi => hf _)
    _ = _ := by simp

theorem blockSum_pair (f : ℕ → ℕ) (w j : ℕ) :
    blockSum f (2 * w) j = blockSum f w (2 * j) + blockSum f w (2 * j + 1) := by
  unfold blockSum
  rw [show 2 * w = w + w by omega, Finset.sum_range_add]
  congr 1 <;> apply Finset.sum_congr rfl <;> intro i hi <;> congr 1 <;> ring

theorem prefixSum_blocks (f : ℕ → ℕ) (w n : ℕ) :
    prefixSum (blockSum f w) n = prefixSum f (w * n) := by
  induction n with
  | zero => simp [prefixSum]
  | succ n ih =>
    change (∑ i ∈ Finset.range (n + 1), blockSum f w i) = _
    rw [Finset.sum_range_succ]
    change prefixSum (blockSum f w) n + blockSum f w n = _
    rw [ih, Nat.mul_add, Nat.mul_one]
    simp only [prefixSum, blockSum, Finset.sum_range_add]

theorem mergeCounts_blocks (w n : ℕ) (hw : 0 < w) (f : ℕ → ℕ)
    (hf : ∀ i, f i ≤ 1) :
    mergeCounts w n (pack (2 ^ w) (2 * n) (blockSum f w)) =
      pack (2 ^ (2 * w)) n (blockSum f (2 * w)) := by
  rw [mergeCounts_sound w n hw _ (fun i hi =>
    (blockSum_le f hf w i).trans_lt Nat.lt_two_pow_self)]
  apply pack_congr
  intro i hi
  exact (blockSum_pair f w i).symm

/-- Five pairwise merge stages give one population count per 32-bit digit. -/
def packedCounts32 (mask n : ℕ) : ℕ :=
  RosserScan.forceNat (mergeCounts 1 (16 * n) mask) fun x =>
  RosserScan.forceNat (mergeCounts 2 (8 * n) x) fun x =>
  RosserScan.forceNat (mergeCounts 4 (4 * n) x) fun x =>
  RosserScan.forceNat (mergeCounts 8 (2 * n) x) fun x =>
    mergeCounts 16 n x

theorem packedCounts32_sound (mask n : ℕ) (hm : mask < 2 ^ (32 * n)) :
    packedCounts32 mask n = pack (2 ^ 32) n (blockSum (bitValue mask) 32) := by
  have hzero : pack 2 (32 * n) (blockSum (bitValue mask) 1) = mask := by
    calc
      _ = pack 2 (32 * n) (fun i => mask / 2 ^ i % 2) := by
        apply pack_congr
        intro i hi
        rw [blockSum_one, bitValue_eq_digit]
      _ = mask := by
        simpa only [Nat.one_mul, pow_one] using
          pack_digits 1 (32 * n) mask (by omega) (by simpa using hm)
  have h1 := mergeCounts_blocks 1 (16 * n) (by omega) (bitValue mask) (bitValue_le_one mask)
  have h2 := mergeCounts_blocks 2 (8 * n) (by omega) (bitValue mask) (bitValue_le_one mask)
  have h4 := mergeCounts_blocks 4 (4 * n) (by omega) (bitValue mask) (bitValue_le_one mask)
  have h8 := mergeCounts_blocks 8 (2 * n) (by omega) (bitValue mask) (bitValue_le_one mask)
  have h16 := mergeCounts_blocks 16 n (by omega) (bitValue mask) (bitValue_le_one mask)
  norm_num only [← Nat.mul_assoc, Nat.reduceMul] at h1 h2 h4 h8 h16
  rw [hzero] at h1
  simp only [packedCounts32, forceNat_eq, h1, h2, h4, h8, h16]
  norm_num

/-- With half-width guards, subtraction is digitwise and every comparison is checked. -/
theorem guard_sound32 (n : ℕ) (f g : ℕ → ℕ)
    (hf : ∀ i < n, f i < 2 ^ 31) (hg : ∀ i < n, g i < 2 ^ 31)
    (hcheck :
      ((pack (2 ^ 32) n g + pack (2 ^ 32) n (fun _ => 2 ^ 31) -
        pack (2 ^ 32) n f) &&& pack (2 ^ 32) n (fun _ => 2 ^ 31)) =
          pack (2 ^ 32) n (fun _ => 2 ^ 31)) :
    ∀ i < n, f i ≤ g i := by
  have hsub :
      pack (2 ^ 32) n g + pack (2 ^ 32) n (fun _ => 2 ^ 31) - pack (2 ^ 32) n f =
        pack (2 ^ 32) n (fun i => g i + 2 ^ 31 - f i) := by
    rw [← pack_add, pack_sub]
    intro i hi
    have := hf i hi
    omega
  rw [hsub] at hcheck
  have hout : ∀ i < n, g i + 2 ^ 31 - f i < 2 ^ 32 := by
    intro i hi
    have := hg i hi
    omega
  intro i hi
  have hb := congrArg (fun x : ℕ => x.testBit (32 * i + 31)) hcheck
  rw [Nat.testBit_and, pack_testBit 32 n i 31 hout hi (by omega),
    pack_testBit 32 n i 31 (by intro j hj; norm_num) hi (by omega)] at hb
  have hguard : (2 ^ 31 : ℕ).testBit 31 = true := by decide
  simp only [hguard, Bool.and_true] at hb
  simp only [Nat.testBit_eq_decide_div_mod_eq, decide_eq_true_eq] at hb
  have := hout i hi
  omega

theorem pack_index_identity (q n : ℕ) (hq : 1 ≤ q) (hn : 0 < n) :
    (q - 1) * pack q n (fun i => i) + pack q n (fun _ => 1) =
      (n - 1) * q ^ n + 1 := by
  have hprefix := pack_prefix_identity q n (fun _ => 1) hq
  have heq : pack q n (fun i => prefixSum (fun _ => 1) (i + 1)) =
      pack q n (fun i => i) + pack q n (fun _ => 1) := by
    rw [← pack_add]
    apply pack_congr
    intro i hi
    simp [prefixSum]
  rw [heq] at hprefix
  simp [prefixSum] at hprefix
  have hr := pack_one_identity q n hq
  have hn' := Nat.sub_add_cancel (by omega : 1 ≤ n)
  have hn'' := congrArg (fun x => x * q ^ n) hn'
  nlinarith

theorem pack_index_eq (q n : ℕ) (hq : 1 < q) (hn : 0 < n) :
    pack q n (fun i => i) =
      ((n - 1) * q ^ n + 1 - pack q n (fun _ => 1)) / (q - 1) := by
  have h := pack_index_identity q n (by omega) hn
  have heq : (n - 1) * q ^ n + 1 - pack q n (fun _ => 1) =
      (q - 1) * pack q n (fun i => i) := by omega
  rw [heq, Nat.mul_div_cancel_left _ (by omega)]

def checkFromCounts (counts n intercept slope : ℕ) : Bool :=
  RosserScan.forceNat (32 * n) fun L =>
  RosserScan.forceNat ((2 ^ L - 1) / (2 ^ 32 - 1)) fun R =>
  RosserScan.forceNat ((((counts <<< L) - counts) / (2 ^ 32 - 1)) % 2 ^ L) fun pref =>
  RosserScan.forceNat (32 * (((n - 1) * 2 ^ L + 1 - R) / (2 ^ 32 - 1))) fun pos =>
  RosserScan.forceNat (16384 * pref) fun lhs =>
  RosserScan.forceNat (intercept * R + slope * pos) fun rhs =>
  RosserScan.forceNat (2 ^ 31 * R) fun guard =>
    decide (((rhs + guard - lhs) &&& guard) = guard)

theorem packed_prefix_formula (n : ℕ) (f : ℕ → ℕ)
    (hsum : prefixSum f n < 2 ^ 32) :
    ((((pack (2 ^ 32) n f <<< (32 * n)) - pack (2 ^ 32) n f) /
      (2 ^ 32 - 1)) % 2 ^ (32 * n)) =
      pack (2 ^ 32) n (fun i => prefixSum f (i + 1)) := by
  have hr := pack_one_identity (2 ^ 32) n (by norm_num)
  have hp : 2 ^ (32 * n) - 1 =
      (2 ^ 32 - 1) * pack (2 ^ 32) n (fun _ => 1) := by
    rw [pow_mul]
    omega
  rw [Nat.shiftLeft_eq]
  have hnum : pack (2 ^ 32) n f * 2 ^ (32 * n) - pack (2 ^ 32) n f =
      (pack (2 ^ 32) n f * pack (2 ^ 32) n (fun _ => 1)) * (2 ^ 32 - 1) := by
    calc
      _ = pack (2 ^ 32) n f * (2 ^ (32 * n) - 1) := by
        rw [Nat.mul_sub_left_distrib, Nat.mul_one]
      _ = _ := by rw [hp]; ring
  rw [hnum, Nat.mul_div_cancel _ (by norm_num), pow_mul]
  exact pack_prefix_mod (2 ^ 32) n f (by norm_num) hsum

/-- The prefix/guard stage, with a semantic specification for its packed count input. -/
theorem checkFromCounts_sound (n intercept slope : ℕ) (f : ℕ → ℕ)
    (hn : 0 < n) (hcount : 16384 * prefixSum f n < 2 ^ 31)
    (hrhs : intercept + slope * (32 * (n - 1)) < 2 ^ 31)
    (hcheck : checkFromCounts (pack (2 ^ 32) n f) n intercept slope = true) :
    ∀ i < n, 16384 * prefixSum f (i + 1) ≤ intercept + slope * (32 * i) := by
  have hsum : prefixSum f n < 2 ^ 32 := by omega
  have hR : (2 ^ (32 * n) - 1) / (2 ^ 32 - 1) =
      pack (2 ^ 32) n (fun _ => 1) := by
    rw [pack_const_one _ _ (by norm_num), pow_mul]
  have hpos : ((n - 1) * 2 ^ (32 * n) + 1 - pack (2 ^ 32) n (fun _ => 1)) /
      (2 ^ 32 - 1) = pack (2 ^ 32) n (fun i => i) := by
    rw [pack_index_eq _ _ (by norm_num) hn, pow_mul]
  simp only [checkFromCounts, forceNat_eq, decide_eq_true_eq] at hcheck
  rw [hR, packed_prefix_formula n f hsum, hpos] at hcheck
  have hguard := guard_sound32 n
    (fun i => 16384 * prefixSum f (i + 1))
    (fun i => intercept + slope * (32 * i))
  apply hguard
  · intro i hi
    exact (Nat.mul_le_mul_left _ (prefixSum_mono f (by omega))).trans_lt hcount
  · intro i hi
    exact (Nat.add_le_add_left (Nat.mul_le_mul_left slope
      (Nat.mul_le_mul_left 32 (by omega : i ≤ n - 1))) intercept).trans_lt hrhs
  · simp only [pack_add, pack_mul, pack_const (2 ^ 32) n intercept,
      pack_const (2 ^ 32) n (2 ^ 31)]
    rw [show pack (2 ^ 32) n (HMul.hMul 32) =
      32 * pack (2 ^ 32) n (fun i => i) from pack_mul (2 ^ 32) n 32 (fun i => i)]
    exact hcheck

theorem candidateCount_mono (mask : ℕ) {a b : ℕ} (h : a ≤ b) :
    candidateCount mask a ≤ candidateCount mask b := by
  rw [candidateCount_eq_sum, candidateCount_eq_sum]
  exact prefixSum_mono _ h

theorem bitValue_eq_zero (mask len i : ℕ) (hm : mask < 2 ^ len) (hi : len ≤ i) :
    bitValue mask i = 0 := by
  have hb := Nat.testBit_eq_false_of_lt
    (hm.trans_le (Nat.pow_le_pow_right (by omega) hi))
  simp [bitValue, hb]

theorem candidateCount_pad (mask len top : ℕ) (hm : mask < 2 ^ len) (hl : len ≤ top) :
    candidateCount mask top = candidateCount mask len := by
  rw [candidateCount_eq_sum, candidateCount_eq_sum]
  have ht : top = len + (top - len) := by omega
  rw [ht]
  simp only [prefixSum, Finset.sum_range_add]
  have hz : ∑ i ∈ Finset.range (top - len), bitValue mask (len + i) = 0 := by
    apply Finset.sum_eq_zero
    intro i hi
    exact bitValue_eq_zero mask len (len + i) hm (by omega)
  rw [hz, Nat.add_zero]

def packedCheck (mask len intercept slope : ℕ) : Bool :=
  RosserScan.forceNat ((len + 31) / 32) fun n =>
  RosserScan.forceNat (packedCounts32 mask n) fun counts =>
    checkFromCounts counts n intercept slope

/-- A successful packed test bounds every candidate prefix, including a partial final bucket. -/
theorem packedCheck_sound (mask len intercept slope : ℕ)
    (hlen : 0 < len) (hm : mask < 2 ^ len)
    (hcount : 16384 * candidateCount mask len < 2 ^ 31)
    (hrhs : intercept + slope * (32 * ((len + 31) / 32 - 1)) < 2 ^ 31)
    (hcheck : packedCheck mask len intercept slope = true) :
    ∀ d ≤ len, 16384 * candidateCount mask d ≤
      intercept + slope * 32 * ((d - 1) / 32) := by
  let n := (len + 31) / 32
  have hn : 0 < n := by dsimp [n]; omega
  have hl : len ≤ 32 * n := by dsimp [n]; omega
  have hm32 : mask < 2 ^ (32 * n) :=
    hm.trans_le (Nat.pow_le_pow_right (by omega) hl)
  have hsum : prefixSum (blockSum (bitValue mask) 32) n = candidateCount mask len := by
    rw [prefixSum_blocks, ← candidateCount_eq_sum, candidateCount_pad mask len _ hm hl]
  have hc : checkFromCounts (pack (2 ^ 32) n (blockSum (bitValue mask) 32))
      n intercept slope = true := by
    simp only [packedCheck, forceNat_eq] at hcheck
    change checkFromCounts (packedCounts32 mask n) n intercept slope = true at hcheck
    rw [packedCounts32_sound mask n hm32] at hcheck
    exact hcheck
  have hbound := checkFromCounts_sound n intercept slope (blockSum (bitValue mask) 32)
    hn (by simpa only [hsum] using hcount) hrhs hc
  intro d hd
  by_cases hz : d = 0
  · subst d
    simp [candidateCount]
  · have hi : (d - 1) / 32 < n := by dsimp [n]; omega
    have hend : d ≤ 32 * ((d - 1) / 32 + 1) := by omega
    have hb := hbound ((d - 1) / 32) hi
    rw [prefixSum_blocks, ← candidateCount_eq_sum] at hb
    exact (Nat.mul_le_mul_left 16384 (candidateCount_mono mask hend)).trans
      (by simpa only [Nat.mul_assoc] using hb)

end RosserPackedBarrier

-- Source: Solutions/RosserBitMoments.lean
/-! Compute the three moments of a bit window by bytes. A single packed
256-entry lookup table replaces eight recursive bit inspections. Its entire
contents are certified by `decide +kernel`; no native computation is trusted. -/

namespace RosserBitMoments

open RosserBitSieve AlternativeProductMoments

theorem moments_append (xs ys : List ℕ) :
    moments (xs ++ ys) = merge (moments xs) (moments ys) := by
  simp [moments, merge, List.map_append, List.sum_append]

theorem moments_shift (ds : List ℕ) (offset : ℕ) :
    moments (ds.map (fun d => offset + d)) = translate offset (moments ds) := by
  induction ds with
  | nil => simp [moments, translate]
  | cons d ds ih =>
    have hi := congrArg Moments.first ih
    have hj := congrArg Moments.second ih
    simp only [moments, translate] at hi hj
    apply Moments.ext
    · simp [moments, translate]
    · simp only [moments, translate, List.map_cons, List.sum_cons, List.length_cons]
      rw [hi]
      ring
    · simp only [moments, translate, List.map_cons, List.sum_cons, List.length_cons]
      rw [hj]
      ring

theorem moments_perm {xs ys : List ℕ} (h : xs.Perm ys) : moments xs = moments ys := by
  apply Moments.ext
  · exact h.length_eq
  · exact h.sum_eq
  · exact (h.map (fun (d : ℕ) => d ^ 2)).sum_eq

theorem enumBits_shift (depth start mask : ℕ) :
    enumBits depth start mask = (enumBits depth 0 mask).map (fun d => start + d) := by
  induction depth generalizing start mask with
  | zero => simp only [enumBits]; split <;> simp
  | succ depth ih =>
    simp only [enumBits]
    split
    · simp
    · rw [ih start, ih (start + 2 ^ depth), ih (0 + 2 ^ depth), List.map_append,
        List.map_map]
      simp only [Nat.zero_add, Function.comp_def, Nat.add_assoc]

theorem enumBits_mod_perm (depth start mask : ℕ) :
    (enumBits depth start (mask % 2 ^ (2 ^ depth))).Perm (enumBits depth start mask) := by
  apply (List.perm_ext_iff_of_nodup (enumBits_nodup _ _ _) (enumBits_nodup _ _ _)).mpr
  intro x
  simp only [mem_enumBits, Nat.testBit_mod_two_pow, Bool.and_eq_true, decide_eq_true_eq]
  constructor
  · rintro ⟨hlo, hhi, _, hb⟩
    exact ⟨hlo, hhi, hb⟩
  · rintro ⟨hlo, hhi, hb⟩
    exact ⟨hlo, hhi, by omega, hb⟩

set_option maxRecDepth 100000 in
set_option maxHeartbeats 8000000 in
theorem byteMoments_table : ∀ byte : Fin 256,
    byteMoments byte = moments (enumBits 3 0 byte) := by decide +kernel

theorem byteMoments_sound (mask : ℕ) :
    byteMoments (mask % 256) = moments (enumBits 3 0 mask) := by
  have h := byteMoments_table ⟨mask % 256, Nat.mod_lt _ (by decide)⟩
  have hm := moments_perm (enumBits_mod_perm 3 0 mask)
  norm_num only [Nat.reducePow] at hm
  exact h.trans hm

theorem fastMoments_sound (depth start mask : ℕ) :
    fastMoments depth start mask = moments (enumBits (depth + 3) start mask) := by
  induction depth generalizing start mask with
  | zero =>
    rw [fastMoments, byteMoments_sound, enumBits_shift 3 start mask, moments_shift]
  | succ depth ih =>
    change (if mask == 0 then _ else _) =
      moments (enumBits ((depth + 3) + 1) start mask)
    rw [enumBits]
    split
    · rfl
    · dsimp only
      rw [moments_append, ih, ih]

theorem windowMoments_sound (mask shift len : ℕ) :
    windowMoments mask shift len = moments (windowOffsets 13 mask shift len) := by
  rw [windowMoments, fastMoments_sound]
  change moments (enumBits 13 1 _) = _
  rw [enumBits_shift]
  simp only [windowOffsets, Nat.add_comm]

theorem stepFromMoments_eq (v a : ℕ) (ds : List ℕ) :
    stepFromMoments v a (moments ds) = momentStep v a ds := by
  rfl

theorem fastMomentStep_eq (v a mask shift len : ℕ) :
    fastMomentStep v a mask shift len =
      momentStep v a (windowOffsets 13 mask shift len) := by
  rw [fastMomentStep, windowMoments_sound, stepFromMoments_eq]

end RosserBitMoments

-- Source: Solutions/RosserScan.lean
/-!
Generic verifier for an interval. A shared bit mask covers all primes in the
interval; short blocks reuse windows of this mask. Successful execution is
proved to imply both the real inequality and the next reciprocal bound.
-/

namespace RosserScan

open RosserBitSieve AlternativeProductMoments RosserMomentBridge
open RosserLogCertificate RosserBlockCheck
open RosserBitMoments

theorem forceNat_eq {α : Type} (n : ℕ) (f : ℕ → α) : forceNat n f = f n := by
  cases n <;> rfl

def Covers (base top mask : ℕ) : Prop :=
  ∀ p, Nat.Prime p → base < p → p ≤ top → mask.testBit (p - (base + 1)) = true

theorem sieve_covers (divisors : List ℕ) (base top : ℕ)
    (hds : ∀ d ∈ divisors, 2 ≤ d ∧ d < base + 1) :
    Covers base top (candidateMask divisors (base + 1) (top - base)) := by
  intro p hp hlo hhi
  apply candidateMask_preserves_prime _ _ _ _ hds (by omega)
  simpa only [Nat.add_sub_of_le (show base + 1 ≤ p by omega)] using hp

def StepGood (a b w : ℕ) : Prop :=
  a < b ∧ (w : ℝ) / scale ≤ reciprocalProduct b ∧
    ∀ x : ℝ, (a : ℝ) ≤ x → x ≤ b → Bound x

theorem step_sound (base top mask a b v : ℕ)
    (hcover : Covers base top mask) (hbase : base ≤ a) (hbt : b ≤ top)
    (hv : (v : ℝ) / scale ≤ reciprocalProduct a)
    (hc : stepCheck a b v (stepOffsets base mask a b) = true) :
    StepGood a b (momentStep v a (stepOffsets base mask a b)) := by
  simp only [stepCheck, Bool.and_eq_true, decide_eq_true_eq] at hc
  obtain ⟨⟨ha, hab, hlen, hfirst, hupper⟩, hcheck⟩ := hc
  have hbounds : ∀ d ∈ stepOffsets base mask a b, 0 < d ∧ d ≤ b - a := by
    intro d hd
    have h := (mem_windowOffsets _ _ _ _ _).mp hd
    exact ⟨h.1, h.2.1⟩
  have hprimes : ∀ p, Nat.Prime p → a < p → p ≤ b →
      p - a ∈ stepOffsets base mask a b := by
    intro p hp hlo hhi
    apply (mem_windowOffsets _ _ _ _ _).mpr
    refine ⟨by omega, by omega, by omega, ?_⟩
    have he : p - a - 1 + (a - base) = p - (base + 1) := by omega
    rw [he]
    exact hcover p hp (by omega) (by omega)
  have hnext := momentStep_reciprocalProduct scale v a b _ scale_pos hab.le ha
    (windowOffsets_nodup _ _ _ _) hbounds hprimes hfirst hupper hv
  exact ⟨hab, hnext, fun x hax hxb => check_sound a b _ (by omega) hcheck hnext x hax hxb⟩

theorem stepData_eq (base mask a b v : ℕ) :
    stepData base mask a b v =
      (stepCheck a b v (stepOffsets base mask a b),
        momentStep v a (stepOffsets base mask a b)) := by
  unfold stepData
  rw [windowMoments_sound]
  rfl

theorem attempt_sound (base top mask a v fuel width b w : ℕ)
    (hcover : Covers base top mask) (hbase : base ≤ a)
    (hv : (v : ℝ) / scale ≤ reciprocalProduct a)
    (h : attempt base top mask a v fuel width = some (b, w)) :
    b ≤ top ∧ StepGood a b w := by
  induction fuel generalizing width with
  | zero => simp [attempt] at h
  | succ fuel ih =>
    simp only [attempt, stepData_eq] at h
    split at h
    · rename_i hc
      have he := Option.some.inj h
      have hb := congrArg Prod.fst he
      have hw := congrArg Prod.snd he
      dsimp only at hb hw
      subst b w
      exact ⟨min_le_left _ _, step_sound _ _ _ _ _ _ hcover hbase
        (min_le_left _ _) hv hc⟩
    · exact ih (width / 2) h

theorem run_sound (base top mask fuel a v w : ℕ)
    (hcover : Covers base top mask) (hbase : base ≤ a)
    (hv : (v : ℝ) / scale ≤ reciprocalProduct a)
    (h : run base top mask fuel a v = some w) :
    (w : ℝ) / scale ≤ reciprocalProduct top ∧
      ∀ x : ℝ, (a : ℝ) < x → x ≤ top → Bound x := by
  induction fuel generalizing a v with
  | zero =>
    simp only [run, forceNat_eq] at h
    split at h
    · rename_i ha
      have ha' : a = top := by simpa using ha
      have hv' : v = w := Option.some.inj h
      subst a w
      exact ⟨hv, by intro x hx hxt; linarith⟩
    · contradiction
  | succ fuel ih =>
    simp only [run, forceNat_eq] at h
    split at h
    · rename_i ha
      have ha' : a = top := by simpa using ha
      have hv' : v = w := Option.some.inj h
      subst a w
      exact ⟨hv, by intro x hx hxt; linarith⟩
    · split at h
      · contradiction
      · rename_i b w' htry
        have hs := attempt_sound base top mask a v 20 _ b w'
          hcover hbase hv htry
        have hab := hs.2.1
        have hi := ih b w' (by omega) hs.2.2.1 h
        refine ⟨hi.1, ?_⟩
        intro x hax hxt
        by_cases hxb : x ≤ b
        · exact hs.2.2.2 x hax.le hxb
        · exact hi.2 x (lt_of_not_ge hxb) hxt

end RosserScan

-- Source: Solutions/RosserPrefixBridge.lean
/-! Connect prime coverage of a block to the fast packed prefix counter. -/

namespace RosserPrefixBridge

open RosserPackedBarrier

theorem prime_card_le_candidateCount (a b n mask : ℕ)
    (han : a ≤ n) (hnb : n ≤ b)
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b →
      mask.testBit (p - (a + 1)) = true) :
    (Nat.primesLE n \ Nat.primesLE a).card ≤
      candidateCount mask (n - a) := by
  let t := Nat.primesLE n \ Nat.primesLE a
  let s := (List.range (n - a)).filter (fun i => mask.testBit i)
  have hmap : Set.MapsTo (fun p : ℕ => p - (a + 1))
      (t : Set ℕ) (s.toFinset : Set ℕ) := by
    intro p hp
    obtain ⟨hpn, hpa⟩ := Finset.mem_sdiff.mp hp
    obtain ⟨hpn', hpprime⟩ := Nat.mem_primesLE.mp hpn
    have hap : a < p := by
      by_contra h
      exact hpa (Nat.mem_primesLE.mpr ⟨by omega, hpprime⟩)
    apply List.mem_toFinset.mpr
    apply List.mem_filter.mpr
    constructor
    · apply List.mem_range.mpr
      change p - (a + 1) < n - a
      omega
    · exact hcover p hpprime hap (by omega)
  have hinj : (t : Set ℕ).InjOn
      (fun p : ℕ => p - (a + 1)) := by
    intro p hp q hq heq
    have hp' := Finset.mem_sdiff.mp hp
    have hq' := Finset.mem_sdiff.mp hq
    have hpprime := (Nat.mem_primesLE.mp hp'.1).2
    have hqprime := (Nat.mem_primesLE.mp hq'.1).2
    have hap : a < p := by
      by_contra h
      exact hp'.2 (Nat.mem_primesLE.mpr ⟨by omega, hpprime⟩)
    have haq : a < q := by
      by_contra h
      exact hq'.2 (Nat.mem_primesLE.mpr ⟨by omega, hqprime⟩)
    change p - (a + 1) = q - (a + 1) at heq
    omega
  have hc := Finset.card_le_card_of_injOn (fun p : ℕ => p - (a + 1)) hmap hinj
  have hs : s.toFinset.card ≤ s.length := List.toFinset_card_le s
  have hfinal := hc.trans hs
  simpa only [t, s, candidateCount] using hfinal

theorem packed_affine_count (a : ℕ) (x : ℝ) (mask len intercept slope : ℕ)
    (hlen : 0 < len) (hm : mask < 2 ^ len) (hI : 0 < intercept)
    (hcount : 16384 * candidateCount mask len < 2 ^ 31)
    (hrhs : (intercept - 1) + slope *
      (32 * ((len + 31) / 32 - 1)) < 2 ^ 31)
    (hcheck : packedCheck mask len (intercept - 1) slope = true)
    (hax : (a : ℝ) ≤ x)
    (hfloor : ⌊x⌋₊ ≤ a + len) :
    (candidateCount mask (⌊x⌋₊ - a) : ℝ) <
      (intercept : ℝ) / 16384 +
      (slope : ℝ) / 16384 * (x - a) := by
  have han : a ≤ ⌊x⌋₊ := Nat.le_floor hax
  have hlen' : ⌊x⌋₊ - a ≤ len := by omega
  have hb := packedCheck_sound mask len (intercept - 1) slope
    hlen hm hcount hrhs hcheck (⌊x⌋₊ - a) hlen'
  let pos := 32 * ((⌊x⌋₊ - a - 1) / 32)
  have hpos : pos ≤ ⌊x⌋₊ - a := by dsimp [pos]; omega
  have hfl : (⌊x⌋₊ : ℝ) ≤ x := Nat.floor_le (by linarith only [hax])
  have hposreal : (pos : ℝ) ≤ x - a := by
    have hsub : ((⌊x⌋₊ - a : ℕ) : ℝ) = (⌊x⌋₊ : ℝ) - a :=
      Nat.cast_sub han
    have hposcast : (pos : ℝ) ≤ (⌊x⌋₊ - a : ℕ) := by exact_mod_cast hpos
    exact hposcast.trans (by rw [hsub]; linarith only [hfl])
  have hraw : 16384 * candidateCount mask (⌊x⌋₊ - a) <
      intercept + slope * pos := by
    have hb' : 16384 * candidateCount mask (⌊x⌋₊ - a) ≤
        (intercept - 1) + slope * pos := by
      simpa only [pos, Nat.mul_assoc] using hb
    omega
  have hraw' : (16384 : ℝ) * candidateCount mask (⌊x⌋₊ - a) <
      (intercept : ℝ) + slope * pos := by exact_mod_cast hraw
  have hsl : (slope : ℝ) * pos ≤ slope * (x - a) :=
    mul_le_mul_of_nonneg_left hposreal (by positivity)
  have htarget : (16384 : ℝ) * candidateCount mask (⌊x⌋₊ - a) <
      (intercept : ℝ) + slope * (x - a) := by
    linarith only [hraw', hsl]
  have heq : (intercept : ℝ) / 16384 +
      (slope : ℝ) / 16384 * (x - a) =
      ((intercept : ℝ) + slope * (x - a)) / 16384 := by ring
  rw [heq]
  apply (lt_div_iff₀ (by norm_num : (0 : ℝ) < 16384)).mpr
  simpa only [mul_comm] using htarget

theorem block_sound (a b v mask : ℕ)
    (hvalid : (RosserPrefixParams.parameters a b v).valid = true)
    (hm : mask < 2 ^ (b - a))
    (hI : 0 < (RosserPrefixParams.parameters a b v).intercept)
    (hcount : 16384 * candidateCount mask (b - a) < 2 ^ 31)
    (hrhs :
      ((RosserPrefixParams.parameters a b v).intercept - 1) +
        (RosserPrefixParams.parameters a b v).slope *
          (32 * (((b - a) + 31) / 32 - 1)) < 2 ^ 31)
    (hcheck : packedCheck mask (b - a)
      ((RosserPrefixParams.parameters a b v).intercept - 1)
      (RosserPrefixParams.parameters a b v).slope = true)
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b →
      mask.testBit (p - (a + 1)) = true)
    (hv : ((v : ℝ) / RosserLogCertificate.scale) ≤
      RosserMomentBridge.reciprocalProduct a)
    (x : ℝ) (hax : (a : ℝ) ≤ x) (hxb : x ≤ b) :
    RosserBlockCheck.Bound x := by
  have hab := (RosserPrefixParams.parameters_valid a b v hvalid).2.1
  have hlen : 0 < b - a := by omega
  have hfloor : ⌊x⌋₊ ≤ b := Nat.floor_le_of_le hxb
  have hfloor' : ⌊x⌋₊ ≤ a + (b - a) := by omega
  have hcard := prime_card_le_candidateCount a b ⌊x⌋₊ mask
    (Nat.le_floor hax) hfloor hcover
  have hprefix := packed_affine_count a x mask (b - a)
    (RosserPrefixParams.parameters a b v).intercept
    (RosserPrefixParams.parameters a b v).slope
    hlen hm hI hcount hrhs hcheck hax hfloor'
  exact RosserPrefixParams.parameterized_bound a b v
    (candidateCount mask (⌊x⌋₊ - a)) x hvalid hax hxb hv hcard hprefix

theorem window_mask_covers (base top mask a b : ℕ)
    (hcover : RosserScan.Covers base top mask)
    (hbase : base ≤ a) (hbt : b ≤ top) :
    ∀ p, Nat.Prime p → a < p → p ≤ b →
      ((mask / 2 ^ (a - base)) % 2 ^ (b - a)).testBit
        (p - (a + 1)) = true := by
  intro p hp hap hpb
  have hi : p - (a + 1) < b - a := by omega
  have heq : p - (a + 1) + (a - base) = p - (base + 1) := by omega
  rw [Nat.testBit_mod_two_pow, Nat.testBit_div_two_pow]
  simp only [show decide (p - (a + 1) < b - a) = true by simp [hi],
    Bool.true_and, heq]
  exact hcover p hp (by omega) (by omega)

end RosserPrefixBridge

-- Source: Solutions/RosserSieveData.lean
/-! Sieve divisors are untrusted numerical hints. Their only required property
is the elementary range check below; their primality is not assumed. -/
namespace RosserSieveData
open RosserBitSieve RosserScan RosserMomentBridge RosserLogCertificate

theorem divisors_ge_two : ∀ d ∈ divisors, 2 ≤ d := by decide +kernel

theorem smallDivisors_bounds (base : ℕ) :
    ∀ d ∈ smallDivisors base, 2 ≤ d ∧ d < base + 1 := by
  intro d hd
  obtain ⟨hd, hle⟩ := List.mem_filter.mp hd
  exact ⟨divisors_ge_two d hd, by have := of_decide_eq_true hle; omega⟩

theorem segment_sound (base top v w : ℕ)
    (hv : (v : ℝ) / scale ≤ reciprocalProduct base)
    (h : segment base top v = some w) :
    (w : ℝ) / scale ≤ reciprocalProduct top ∧
      ∀ x : ℝ, (base : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  simp only [segment, forceNat_eq] at h
  exact run_sound base top (mask base top) 4096 base v w
    (sieve_covers _ _ _ (smallDivisors_bounds base)) (le_refl _) hv h

end RosserSieveData

-- Source: Solutions/RosserCachedSieve.lean
/-! A reusable table of periodic divisor masks for the fixed-size segments. -/

namespace RosserCachedSieve

open RosserBitSieve RosserScan

def withMasks {α : Type} (len : ℕ) : List ℕ → (List (ℕ × ℕ) → α) → α
  | [], f => f []
  | d :: ds, f =>
    forceNat (periodicMask d ((len + d - 1) / d)) fun m =>
      withMasks len ds fun rest => f ((d, m) :: rest)

def pairs (len : ℕ) (ds : List ℕ) : List (ℕ × ℕ) :=
  ds.map (fun d => (d, periodicMask d ((len + d - 1) / d)))

theorem withMasks_eq {α : Type} (len : ℕ) (ds : List ℕ)
    (f : List (ℕ × ℕ) → α) : withMasks len ds f = f (pairs len ds) := by
  induction ds generalizing f with
  | nil => rfl
  | cons d ds ih =>
    simp only [withMasks, RosserScan.forceNat_eq, ih, pairs, List.map_cons]

def mask (ds : List (ℕ × ℕ)) (base top : ℕ) : ℕ :=
  let len := top - base
  let composite := ds.foldl (fun acc dm =>
    if dm.1 ≤ base then
      acc ||| (dm.2 * 2 ^ ((dm.1 - (base + 1) % dm.1) % dm.1))
    else acc) 0
  (2 ^ len - 1) ^^^ (composite % 2 ^ len)

theorem mask_lt (ds : List (ℕ × ℕ)) (base top : ℕ) :
    mask ds base top < 2 ^ (top - base) := by
  unfold mask
  apply Nat.xor_lt_two_pow
  · exact Nat.sub_lt (by positivity) (by norm_num)
  · exact Nat.mod_lt _ (by positivity)

theorem pairs_fold_eq (fixedLen base : ℕ) (ds : List ℕ) (acc : ℕ) :
    (pairs fixedLen ds).foldl (fun acc dm =>
      if dm.1 ≤ base then
        acc ||| (dm.2 * 2 ^ ((dm.1 - (base + 1) % dm.1) % dm.1))
      else acc) acc =
    (ds.filter (fun d => decide (d ≤ base))).foldl (fun acc d =>
      acc ||| divisorMask (base + 1) fixedLen d) acc := by
  induction ds generalizing acc with
  | nil => rfl
  | cons d ds ih =>
    simp only [pairs, List.map_cons, List.foldl_cons, List.filter_cons]
    by_cases hd : d ≤ base
    · simp only [hd, decide_true, if_true]
      change (pairs fixedLen ds).foldl _
        (acc ||| divisorMask (base + 1) fixedLen d) = _
      exact ih _
    · simp only [hd, decide_false, Bool.false_eq_true, if_false]
      exact ih _

theorem mask_prime (fixedLen base top : ℕ) (ds : List ℕ)
    (hds : ∀ d ∈ ds, 2 ≤ d) (hbase : base < top)
    (hlen : top - base ≤ fixedLen) :
    ∀ p, Nat.Prime p → base < p → p ≤ top →
      (mask (pairs fixedLen ds) base top).testBit (p - (base + 1)) = true := by
  intro p hp hbp hpt
  let small := ds.filter (fun d => decide (d ≤ base))
  have hsmall : ∀ d ∈ small, 2 ≤ d ∧ d < base + 1 := by
    intro d hd
    obtain ⟨hdmem, hdle⟩ := List.mem_filter.mp hd
    exact ⟨hds d hdmem, by have := of_decide_eq_true hdle; omega⟩
  have hi : p - (base + 1) < top - base := by omega
  have hprim : Nat.Prime ((base + 1) + (p - (base + 1))) := by
    simpa only [Nat.add_sub_of_le (by omega : base + 1 ≤ p)] using hp
  have hcomp := compositeMask_preserves_prime small (base + 1) fixedLen
    (p - (base + 1)) hsmall hprim
  unfold mask
  rw [pairs_fold_eq]
  change ((2 ^ (top - base) - 1) ^^^
    (compositeMask small (base + 1) fixedLen % 2 ^ (top - base))).testBit
      (p - (base + 1)) = true
  simp [Nat.testBit_xor, Nat.testBit_two_pow_sub_one,
    Nat.testBit_mod_two_pow, hi, hcomp]

end RosserCachedSieve

-- Source: Solutions/RosserFastStep.lean
/-! Generic soundness of a fast finite block once its moments and bit mask
have been certified. -/

namespace RosserFastStep

open RosserBitSieve RosserBitMoments RosserMomentBridge
open RosserPrefixBridge RosserPackedBarrier RosserLogCertificate
open AlternativeProductMoments

theorem step_sound (a b v mask depth : ℕ) (s : Moments)
    (hvalid : (RosserPrefixParams.parameters a b v).valid = true)
    (hm : mask < 2 ^ (b - a))
    (hdepth : b - a ≤ 2 ^ depth)
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b →
      mask.testBit (p - (a + 1)) = true)
    (hmom : s = moments (windowOffsets depth mask 0 (b - a)))
    (hfirst : s.first ≤ s.count * a)
    (hupper : s.count * a ^ 2 - a * s.first + s.second ≤ a ^ 3)
    (hI : 0 < (RosserPrefixParams.parameters a b v).intercept)
    (hcount : 16384 * candidateCount mask (b - a) < 2 ^ 31)
    (hrhs : ((RosserPrefixParams.parameters a b v).intercept - 1) +
      (RosserPrefixParams.parameters a b v).slope *
        (32 * (((b - a) + 31) / 32 - 1)) < 2 ^ 31)
    (hcheck : packedCheck mask (b - a)
      ((RosserPrefixParams.parameters a b v).intercept - 1)
      (RosserPrefixParams.parameters a b v).slope = true)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a) :
    ((stepFromMoments v a s : ℝ) / scale ≤ reciprocalProduct b) ∧
      ∀ x : ℝ, (a : ℝ) ≤ x → x ≤ b → RosserBlockCheck.Bound x := by
  have hab := (RosserPrefixParams.parameters_valid a b v hvalid).2.1
  have ha : 2 ≤ a := by
    have ha' := (RosserPrefixParams.parameters_valid a b v hvalid).1
    omega
  let ds := windowOffsets depth mask 0 (b - a)
  have hnodup : ds.Nodup := windowOffsets_nodup depth mask 0 (b - a)
  have hbounds : ∀ d ∈ ds, 0 < d ∧ d ≤ b - a := by
    intro d hd
    have hb := (mem_windowOffsets depth mask 0 (b - a) d).mp hd
    exact ⟨hb.1, hb.2.1⟩
  have hprimes : ∀ p, Nat.Prime p → a < p → p ≤ b → p - a ∈ ds := by
    intro p hp hap hpb
    apply (mem_windowOffsets depth mask 0 (b - a) (p - a)).mpr
    refine ⟨by omega, by omega, by omega, ?_⟩
    have heq : p - a - 1 + 0 = p - (a + 1) := by omega
    rw [heq]
    exact hcover p hp hap hpb
  have hfirst' : firstMoment ds ≤ ds.length * a := by
    simpa only [hmom, moments, firstMoment] using hfirst
  have hupper' : upperNumerator a ds ≤ a ^ 3 := by
    simpa only [hmom, moments, upperNumerator, firstMoment,
      secondMoment] using hupper
  have hnext := momentStep_reciprocalProduct scale v a b ds scale_pos hab.le ha
    hnodup hbounds hprimes hfirst' hupper' hv
  have heq : stepFromMoments v a s = momentStep v a ds := by
    rw [hmom]
    exact stepFromMoments_eq v a ds
  refine ⟨by simpa only [heq] using hnext, ?_⟩
  intro x hax hxb
  exact block_sound a b v mask hvalid hm hI hcount hrhs hcheck
    hcover hv x hax hxb

end RosserFastStep

-- Source: Solutions/RosserPackedMomentsSound.lean
/-! Correctness of packed first and second moments. -/

namespace RosserPackedMoments

open RosserBitMoments RosserScan

def strictMoments {α : Type} (s : Moments) (f : Moments → α) : α :=
  forceNat s.count fun c => forceNat s.first fun a => forceNat s.second fun b =>
    f ⟨c, a, b⟩

def bytes (mask stripe : Nat) : Nat → Moments → Moments
  | 0, s => s
  | j + 1, s =>
    forceNat ((mask >>> j) &&& stripe) fun bit =>
      strictMoments ⟨s.count + bit, s.first + j * bit, s.second + j * j * bit⟩
        (bytes mask stripe j)

def combine (bits half : Nat) (s : Moments) : Moments :=
  let stripe := RosserBitSieve.periodicMask (2 * half) (bits / (2 * half)) *
    (2 ^ half - 1)
  forceNat stripe fun stripe =>
  forceNat ((s.count >>> half) &&& stripe) fun cr =>
  forceNat ((s.first >>> half) &&& stripe) fun fr =>
    ⟨(s.count &&& stripe) + cr,
     (s.first &&& stripe) + fr + half * cr,
     (s.second &&& stripe) + ((s.second >>> half) &&& stripe) +
       2 * half * fr + half * half * cr⟩

def reduce (bits : Nat) : Nat → Nat → Moments → Moments
  | 0, _, s => s
  | fuel + 1, half, s =>
    strictMoments (combine bits half s) (reduce bits fuel (2 * half))

def packedMoments (depth mask : Nat) : Moments :=
  let bits := 2 ^ (depth + 3)
  forceNat (RosserBitSieve.periodicMask 8 (bits / 8)) fun stripe =>
    strictMoments (bytes mask stripe 8 ⟨0, 0, 0⟩) fun s =>
      translate 1 (reduce bits depth 8 s)



open RosserPackedBarrier

theorem strictMoments_eq {α : Type} (s : Moments) (f : Moments → α) :
    strictMoments s f = f s := by
  cases s
  simp only [strictMoments, RosserPackedBarrier.forceNat_eq]

def packed (w n : ℕ) (f : ℕ → Moments) : Moments :=
  ⟨pack (2 ^ w) n (fun i => (f i).count),
   pack (2 ^ w) n (fun i => (f i).first),
   pack (2 ^ w) n (fun i => (f i).second)⟩

def lane (mask w i : ℕ) : Moments :=
  ⟨∑ j ∈ Finset.range w, bitValue mask (w * i + j),
   ∑ j ∈ Finset.range w, j * bitValue mask (w * i + j),
   ∑ j ∈ Finset.range w, j * j * bitValue mask (w * i + j)⟩

theorem pair_extract (w n : ℕ) (hw : 0 < w) (f : ℕ → ℕ)
    (hf : ∀ i < 2 * n, f i < 2 ^ w) :
    let stripe := pack (2 ^ (2 * w)) n (fun _ => 2 ^ w - 1)
    (pack (2 ^ w) (2 * n) f &&& stripe =
      pack (2 ^ (2 * w)) n (fun i => f (2 * i))) ∧
    ((pack (2 ^ w) (2 * n) f >>> w) &&& stripe =
      pack (2 ^ (2 * w)) n (fun i => f (2 * i + 1))) := by
  dsimp only
  have hq : 0 < 2 ^ w := by positivity
  have hpow : 2 ^ w * 2 ^ w = 2 ^ (2 * w) := by rw [two_mul, pow_add]
  let g := fun i => f (2 * i) + 2 ^ w * f (2 * i + 1)
  have hg : ∀ i < n, g i < 2 ^ (2 * w) := by
    intro i hi
    have h0 := hf (2 * i) (by omega)
    have h1 := hf (2 * i + 1) (by omega)
    dsimp [g]
    rw [← hpow]
    nlinarith
  have hm : ∀ i < n, 2 ^ w - 1 < 2 ^ (2 * w - w) := by
    intro i hi
    rw [show 2 * w - w = w by omega]
    omega
  rw [pack_pair, hpow]
  change (_ &&& _) = _ ∧ (_ >>> w &&& _) = _
  constructor
  · rw [pack_and (2 * w) n (by omega) g _ hg (fun i hi => (hm i hi).trans_le
      (Nat.pow_le_pow_right (by omega) (by omega)))]
    apply pack_congr
    intro i hi
    simp only [g, Nat.and_two_pow_sub_one_eq_mod, Nat.add_mul_mod_self_left,
      Nat.mod_eq_of_lt (hf (2 * i) (by omega))]
  · rw [pack_shift_and (2 * w) n w (by omega) (by omega) g _ hg hm]
    apply pack_congr
    intro i hi
    simp only [g, Nat.shiftRight_eq_div_pow, Nat.add_mul_div_left _ _ hq,
      Nat.div_eq_of_lt (hf (2 * i) (by omega)), Nat.zero_add,
      Nat.and_two_pow_sub_one_eq_mod, Nat.mod_eq_of_lt (hf (2 * i + 1) (by omega))]

theorem combine_sound (w n : ℕ) (hw : 0 < w) (f : ℕ → Moments)
    (hc : ∀ i < 2 * n, (f i).count < 2 ^ w)
    (hf : ∀ i < 2 * n, (f i).first < 2 ^ w)
    (hs : ∀ i < 2 * n, (f i).second < 2 ^ w) :
    combine (2 * w * n) w (packed w (2 * n) f) =
      packed (2 * w) n (fun i => merge (f (2 * i)) (translate w (f (2 * i + 1)))) := by
  have hstripe : RosserBitSieve.periodicMask (2 * w) ((2 * w * n) / (2 * w)) *
      (2 ^ w - 1) = pack (2 ^ (2 * w)) n (fun _ => 2 ^ w - 1) := by
    rw [Nat.mul_div_cancel_left _ (by omega), pack_const]
    unfold RosserBitSieve.periodicMask
    rw [pack_const_one _ _ (Nat.one_lt_two_pow (by omega)), pow_mul]
    ring
  obtain ⟨hcl, hcr⟩ := pair_extract w n hw (fun i => (f i).count) hc
  obtain ⟨hfl, hfr⟩ := pair_extract w n hw (fun i => (f i).first) hf
  obtain ⟨hsl, hsr⟩ := pair_extract w n hw (fun i => (f i).second) hs
  simp only [combine, RosserPackedBarrier.forceNat_eq, hstripe, packed]
  rw [hcl, hcr, hfl, hfr, hsl, hsr]
  apply Moments.ext <;> simp only [merge, translate, pack_add, pack_mul] <;> ring

theorem lane_pair (mask w i : ℕ) :
    lane mask (2 * w) i = merge (lane mask w (2 * i))
      (translate w (lane mask w (2 * i + 1))) := by
  apply Moments.ext
  · exact blockSum_pair (bitValue mask) w i
  · simp only [lane, merge, translate]
    rw [show 2 * w = w + w by omega, Finset.sum_range_add]
    have hpos : ∀ j : ℕ, (w + w) * i + (w + j) = w * (2 * i + 1) + j := by
      intro j; ring
    have hpos' : ∀ j : ℕ, (w + w) * i + j = w * (2 * i) + j := by
      intro j; ring
    simp only [hpos, hpos']
    have hsum :
        (∑ j ∈ Finset.range w, (w + j) * bitValue mask (w * (2 * i + 1) + j)) =
        w * (∑ j ∈ Finset.range w, bitValue mask (w * (2 * i + 1) + j)) +
        (∑ j ∈ Finset.range w, j * bitValue mask (w * (2 * i + 1) + j)) := by
      simp only [Finset.mul_sum, ← Finset.sum_add_distrib]
      apply Finset.sum_congr rfl
      intro j hj
      ring
    rw [hsum]
    ring
  · simp only [lane, merge, translate]
    rw [show 2 * w = w + w by omega, Finset.sum_range_add]
    have hpos : ∀ j : ℕ, (w + w) * i + (w + j) = w * (2 * i + 1) + j := by
      intro j; ring
    have hpos' : ∀ j : ℕ, (w + w) * i + j = w * (2 * i) + j := by
      intro j; ring
    simp only [hpos, hpos']
    have hsum :
        (∑ j ∈ Finset.range w, (w + j) * (w + j) * bitValue mask (w * (2 * i + 1) + j)) =
        (∑ j ∈ Finset.range w, j * j * bitValue mask (w * (2 * i + 1) + j)) +
        2 * w * (∑ j ∈ Finset.range w, j * bitValue mask (w * (2 * i + 1) + j)) +
        w * w * (∑ j ∈ Finset.range w, bitValue mask (w * (2 * i + 1) + j)) := by
      simp only [Finset.mul_sum, ← Finset.sum_add_distrib]
      apply Finset.sum_congr rfl
      intro j hj
      ring
    rw [hsum]
    ring

theorem bytes_eq (mask stripe j : ℕ) (s : Moments) :
    bytes mask stripe j s =
      ⟨s.count + ∑ i ∈ Finset.range j, ((mask >>> i) &&& stripe),
       s.first + ∑ i ∈ Finset.range j, i * ((mask >>> i) &&& stripe),
       s.second + ∑ i ∈ Finset.range j, i * i * ((mask >>> i) &&& stripe)⟩ := by
  induction j generalizing s with
  | zero => simp [bytes]
  | succ j ih =>
    simp only [bytes, RosserPackedBarrier.forceNat_eq, strictMoments_eq, ih, Finset.sum_range_succ]
    apply Moments.ext <;> dsimp only <;> ring

theorem pack_sum (q n terms : ℕ) (f : ℕ → ℕ → ℕ) :
    pack q n (fun i => ∑ j ∈ Finset.range terms, f i j) =
      ∑ j ∈ Finset.range terms, pack q n (fun i => f i j) := by
  induction terms with
  | zero => simp only [Finset.range_zero, Finset.sum_empty]; rw [pack_const q n 0]; simp
  | succ terms ih => simp only [Finset.sum_range_succ, pack_add, ih]

theorem byte_plane (mask n j : ℕ) (hj : j < 8) (hm : mask < 2 ^ (8 * n)) :
    ((mask >>> j) &&& RosserBitSieve.periodicMask 8 n) =
      pack 256 n (fun i => bitValue mask (8 * i + j)) := by
  let f := fun i => mask / 2 ^ (8 * i) % 2 ^ 8
  have hf : ∀ i < n, f i < 2 ^ 8 := fun i hi => Nat.mod_lt _ (by positivity)
  have hp : pack (2 ^ 8) n f = mask := pack_digits 8 n mask (by omega) hm
  have hs : RosserBitSieve.periodicMask 8 n = pack (2 ^ 8) n (fun _ => 1) := by
    unfold RosserBitSieve.periodicMask
    rw [pack_const_one _ _ (by norm_num), pow_mul]
  rw [← hp, hs, pack_shift_and 8 n j (by omega) (by omega) f _ hf
    (fun i hi => Nat.one_lt_two_pow (by omega))]
  have hbase : (2 ^ 8 : ℕ) = 256 := by norm_num
  rw [hbase]
  apply pack_congr
  intro i hi
  have hb := pack_testBit 8 n i j hf hi hj
  rw [hp] at hb
  simp only [Nat.and_one_is_mod, Nat.shiftRight_eq_div_pow]
  rw [← bitValue_eq_digit]
  rw [← hbase, hp]
  exact (congrArg Bool.toNat hb).symm

theorem bytes_sound (mask n : ℕ) (hm : mask < 2 ^ (8 * n)) :
    bytes mask (RosserBitSieve.periodicMask 8 n) 8 ⟨0, 0, 0⟩ =
      packed 8 n (lane mask 8) := by
  rw [bytes_eq]
  apply Moments.ext <;> simp only [packed, lane, Nat.zero_add, pack_sum]
  · apply Finset.sum_congr rfl
    intro j hj
    exact byte_plane mask n j (Finset.mem_range.mp hj) hm
  · apply Finset.sum_congr rfl
    intro j hj
    rw [byte_plane mask n j (Finset.mem_range.mp hj) hm, pack_mul]
    norm_num
  · apply Finset.sum_congr rfl
    intro j hj
    rw [byte_plane mask n j (Finset.mem_range.mp hj) hm, pack_mul]
    norm_num


def laneBudget (w : ℕ) : ℕ := ∑ j ∈ Finset.range w, (j + 1) ^ 2

theorem lane_le_budget (mask w i : ℕ) :
    (lane mask w i).count ≤ laneBudget w ∧
    (lane mask w i).first ≤ laneBudget w ∧
    (lane mask w i).second ≤ laneBudget w := by
  have hb := fun j => bitValue_le_one mask (w * i + j)
  dsimp only [lane, laneBudget]
  constructor
  · apply Finset.sum_le_sum
    intro j hj
    exact (hb j).trans (Nat.succ_le_of_lt (by positivity))
  constructor
  · apply Finset.sum_le_sum
    intro j hj
    have := hb j
    nlinarith
  · apply Finset.sum_le_sum
    intro j hj
    have h := Nat.mul_le_mul_left (j * j) (hb j)
    simp only [Nat.mul_one] at h
    nlinarith

theorem laneBudget_le_cube (w : ℕ) : laneBudget w ≤ w ^ 3 := by
  calc
    laneBudget w ≤ ∑ j ∈ Finset.range w, w ^ 2 := by
      apply Finset.sum_le_sum
      intro j hj
      have h := Finset.mem_range.mp hj
      exact Nat.pow_le_pow_left (by omega) 2
    _ = w ^ 3 := by simp; ring

theorem triple_lt_power (d : ℕ) : 3 * (d + 4) < 2 ^ (d + 4) := by
  induction d with
  | zero => norm_num
  | succ d ih =>
    rw [show d + 1 + 4 = (d + 4) + 1 by omega, pow_succ]
    omega

theorem laneBudget_lt (d : ℕ) : laneBudget (2 ^ (d + 3)) < 2 ^ (2 ^ (d + 3)) := by
  cases d with
  | zero => decide
  | succ d =>
    have h := laneBudget_le_cube (2 ^ (d + 4))
    have hp : (2 ^ (d + 4)) ^ 3 < 2 ^ (2 ^ (d + 4)) := by
      rw [← pow_mul]
      apply Nat.pow_lt_pow_right (by omega)
      simpa only [Nat.mul_comm] using triple_lt_power d
    simpa only [Nat.add_assoc] using h.trans_lt hp

theorem packed_congr (w n : ℕ) {f g : ℕ → Moments}
    (h : ∀ i < n, f i = g i) : packed w n f = packed w n g := by
  apply Moments.ext <;> apply pack_congr <;> intro i hi <;> rw [h i hi]

theorem combine_lane (d n mask : ℕ) :
    combine (2 * 2 ^ (d + 3) * n) (2 ^ (d + 3))
      (packed (2 ^ (d + 3)) (2 * n) (lane mask (2 ^ (d + 3)))) =
      packed (2 * 2 ^ (d + 3)) n (lane mask (2 * 2 ^ (d + 3))) := by
  have hb := laneBudget_lt d
  rw [combine_sound _ _ (by positivity) _
    (fun i hi => ((lane_le_budget mask _ i).1).trans_lt hb)
    (fun i hi => ((lane_le_budget mask _ i).2.1).trans_lt hb)
    (fun i hi => ((lane_le_budget mask _ i).2.2).trans_lt hb)]
  apply packed_congr
  intro i hi
  exact (lane_pair mask _ i).symm

theorem reduce_sound (fuel d mask : ℕ) :
    reduce (2 ^ (fuel + d + 3)) fuel (2 ^ (d + 3))
      (packed (2 ^ (d + 3)) (2 ^ fuel) (lane mask (2 ^ (d + 3)))) =
      lane mask (2 ^ (fuel + d + 3)) 0 := by
  induction fuel generalizing d with
  | zero => simp [reduce, packed, pack]
  | succ fuel ih =>
    have hbits : 2 ^ (fuel + 1 + d + 3) = 2 * 2 ^ (d + 3) * 2 ^ fuel := by
      rw [show fuel + 1 + d + 3 = 1 + (d + 3) + fuel by omega]
      simp only [pow_add, pow_one]
    have hnext : 2 * 2 ^ (d + 3) = 2 ^ ((d + 1) + 3) := by
      rw [show d + 1 + 3 = 1 + (d + 3) by omega]
      simp only [pow_add, pow_one]
    simp only [reduce, strictMoments_eq]
    rw [hbits, show 2 ^ (fuel + 1) = 2 * 2 ^ fuel by rw [pow_succ]; omega,
      combine_lane, hnext]
    rw [← pow_add]
    convert ih (d + 1) using 1 <;> congr 2 <;> omega

theorem moments_filter_range (mask w : ℕ) :
    moments ((List.range w).filter (fun i => mask.testBit i)) = lane mask w 0 := by
  induction w with
  | zero => simp [moments, lane]
  | succ w ih =>
    have hc := congrArg Moments.count ih
    have hf := congrArg Moments.first ih
    have hs := congrArg Moments.second ih
    simp only [moments, lane, Nat.mul_zero, Nat.zero_add] at hc hf hs
    apply Moments.ext <;>
      simp only [moments, List.range_succ, List.filter_append,
        List.length_append, List.sum_append, List.map_append, lane,
        Nat.mul_zero, Nat.zero_add, Finset.sum_range_succ]
    · rw [hc]
      cases h : mask.testBit w <;> simp [List.filter, h, bitValue]
    · rw [hf]
      cases h : mask.testBit w <;> simp [List.filter, h, bitValue]
    · rw [hs]
      cases h : mask.testBit w <;> simp [List.filter, h, bitValue, pow_two]

theorem enumBits_perm_filter (depth mask : ℕ) :
    (RosserBitSieve.enumBits depth 0 mask).Perm
      ((List.range (2 ^ depth)).filter (fun i => mask.testBit i)) := by
  apply (List.perm_ext_iff_of_nodup (RosserBitSieve.enumBits_nodup _ _ _)
    ((List.nodup_range).filter _)).mpr
  intro x
  simp only [RosserBitSieve.mem_enumBits, Nat.zero_le, Nat.zero_add, Nat.sub_zero,
    true_and, List.mem_filter, List.mem_range]

theorem lane_eq_moments (depth mask : ℕ) :
    lane mask (2 ^ depth) 0 = moments (RosserBitSieve.enumBits depth 0 mask) := by
  rw [moments_perm (enumBits_perm_filter depth mask), moments_filter_range]

/-- All three SWAR moments are exactly the moments of the selected offsets. -/
theorem packedMoments_sound (depth mask : ℕ) (hm : mask < 2 ^ (2 ^ (depth + 3))) :
    packedMoments depth mask =
      moments (RosserBitSieve.enumBits (depth + 3) 1 mask) := by
  have hbits : 2 ^ (depth + 3) = 8 * 2 ^ depth := by
    rw [pow_add]
    norm_num
    omega
  have hdiv : 2 ^ (depth + 3) / 8 = 2 ^ depth := by
    rw [hbits, Nat.mul_div_cancel_left _ (by omega)]
  have hmask : mask < 2 ^ (8 * 2 ^ depth) := by rwa [← hbits]
  simp only [packedMoments, RosserPackedBarrier.forceNat_eq, strictMoments_eq, hdiv]
  rw [bytes_sound mask (2 ^ depth) hmask]
  have hr := reduce_sound depth 0 mask
  simp only [Nat.add_zero, Nat.zero_add] at hr
  norm_num only [Nat.reducePow] at hr
  rw [hr, lane_eq_moments, enumBits_shift (depth + 3) 1 mask, moments_shift]

/-- Padding a mask adds no selected offsets. -/
theorem candidateCount_eq_enumBits_length (depth mask len : ℕ)
    (hm : mask < 2 ^ len) (hlen : len ≤ 2 ^ (depth + 3)) :
    candidateCount mask len = (RosserBitSieve.enumBits (depth + 3) 1 mask).length := by
  rw [enumBits_shift, List.length_map]
  rw [← candidateCount_pad mask len (2 ^ (depth + 3)) hm hlen]
  exact (enumBits_perm_filter (depth + 3) mask).length_eq.symm

theorem packedMoments_eq_fastMoments (depth mask : ℕ)
    (hm : mask < 2 ^ (2 ^ (depth + 3))) :
    packedMoments depth mask = fastMoments depth 1 mask := by
  rw [packedMoments_sound depth mask hm, fastMoments_sound]

#print axioms packedMoments_sound
#print axioms candidateCount_eq_enumBits_length

end RosserPackedMoments

-- Source: Solutions/RosserFastCompute.lean
/-! The fast numerical block verifier, parameterized by a certified moments
implementation. -/

namespace RosserFastCompute

open RosserScan RosserBitMoments RosserPackedBarrier
open RosserPrefixParams RosserLogCertificate

def strictMoments {α : Type} (s : Moments) (f : Moments → α) : α :=
  forceNat s.count fun c => forceNat s.first fun u => forceNat s.second fun t =>
    f ⟨c, u, t⟩

theorem strictMoments_eq {α : Type} (s : Moments) (f : Moments → α) :
    strictMoments s f = f s := by
  cases s with
  | mk c u t => simp only [strictMoments, RosserScan.forceNat_eq]

def depthFor (len : ℕ) : ℕ :=
  if len ≤ 8 then 0 else Nat.log2 ((len - 1) / 8) + 1

def stepWith (mom : ℕ → ℕ → Moments) (mask a b v : ℕ) : Option ℕ :=
  let len := b - a
  let depth := depthFor len
  strictMoments (mom depth mask) fun s =>
  let par := parameters a b v
  forceNat par.intercept fun intercept =>
  forceNat par.slope fun slope =>
    if par.valid && decide (0 < intercept ∧
      16384 * s.count < 2 ^ 31 ∧
      intercept + slope * (32 * ((len + 31) / 32 - 1)) < 2 ^ 31 ∧
      mask < 2 ^ len ∧ len ≤ 2 ^ (depth + 3) ∧
      s.first ≤ s.count * a ∧
      s.count * a ^ 2 - a * s.first + s.second ≤ a ^ 3) &&
      packedCheck mask len (intercept - 1) slope then
        some (stepFromMoments v a s)
    else none

theorem windowOffsets_eq_enumBits (depth mask len : ℕ) (hm : mask < 2 ^ len) :
    RosserBitSieve.windowOffsets (depth + 3) mask 0 len =
      RosserBitSieve.enumBits (depth + 3) 1 mask := by
  simp only [RosserBitSieve.windowOffsets, pow_zero, Nat.div_one,
    Nat.mod_eq_of_lt hm]
  rw [RosserBitMoments.enumBits_shift (depth + 3) 1 mask]
  apply List.map_congr_left
  intro d hd
  omega

theorem stepWith_sound (mom : ℕ → ℕ → Moments)
    (hmom : ∀ depth mask len, mask < 2 ^ len →
      len ≤ 2 ^ (depth + 3) →
      mom depth mask = RosserBitMoments.moments
        (RosserBitSieve.windowOffsets (depth + 3) mask 0 len))
    (mask a b v w : ℕ)
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b →
      mask.testBit (p - (a + 1)) = true)
    (hv : ((v : ℝ) / scale) ≤ RosserMomentBridge.reciprocalProduct a)
    (h : stepWith mom mask a b v = some w) :
    ((w : ℝ) / scale ≤ RosserMomentBridge.reciprocalProduct b) ∧
      ∀ x : ℝ, (a : ℝ) ≤ x → x ≤ b → RosserBlockCheck.Bound x := by
  let len := b - a
  let depth := depthFor len
  let s := mom depth mask
  let par := parameters a b v
  simp only [stepWith, strictMoments_eq, RosserScan.forceNat_eq] at h
  change (if par.valid && decide (0 < par.intercept ∧
      16384 * s.count < 2 ^ 31 ∧
      par.intercept + par.slope * (32 * ((len + 31) / 32 - 1)) < 2 ^ 31 ∧
      mask < 2 ^ len ∧ len ≤ 2 ^ (depth + 3) ∧
      s.first ≤ s.count * a ∧
      s.count * a ^ 2 - a * s.first + s.second ≤ a ^ 3) &&
      packedCheck mask len (par.intercept - 1) par.slope then
        some (stepFromMoments v a s)
    else none) = some w at h
  let ok := par.valid && decide (0 < par.intercept ∧
      16384 * s.count < 2 ^ 31 ∧
      par.intercept + par.slope * (32 * ((len + 31) / 32 - 1)) < 2 ^ 31 ∧
      mask < 2 ^ len ∧ len ≤ 2 ^ (depth + 3) ∧
      s.first ≤ s.count * a ∧
      s.count * a ^ 2 - a * s.first + s.second ≤ a ^ 3) &&
      packedCheck mask len (par.intercept - 1) par.slope
  change (if ok then some (stepFromMoments v a s) else none) = some w at h
  have hc : ok = true := by
    cases hok : ok with
    | false => simp only [hok, ite_false] at h; cases h
    | true => rfl
  simp only [hc, ite_true] at h
  have hw : stepFromMoments v a s = w := Option.some.inj h
  simp only [ok, Bool.and_eq_true, decide_eq_true_eq] at hc
  rcases hc with ⟨⟨hvalid, hn⟩, hcheck⟩
  obtain ⟨hI, hscount, hrhs0, hmask, hdepth, hfirst, hupper⟩ :=
    hn
  have hmomeq := hmom depth mask len hmask hdepth
  have hlen : len ≤ 2 ^ (depth + 3) := hdepth
  have hcnt : RosserPackedBarrier.candidateCount mask len = s.count := by
    rw [RosserPackedMoments.candidateCount_eq_enumBits_length depth mask len hmask hlen]
    change (RosserBitSieve.enumBits (depth + 3) 1 mask).length =
      (mom depth mask).count
    rw [hmomeq, windowOffsets_eq_enumBits depth mask len hmask]
    rfl
  have hscount' : 16384 * RosserPackedBarrier.candidateCount mask len < 2 ^ 31 := by
    rwa [hcnt]
  have hrhs : (par.intercept - 1) + par.slope *
      (32 * ((len + 31) / 32 - 1)) < 2 ^ 31 := by
    omega
  have hs := RosserFastStep.step_sound a b v mask (depth + 3) s
    hvalid hmask hdepth hcover hmomeq hfirst hupper hI hscount' hrhs hcheck hv
  simpa only [hw] using hs

def step (mask a b v : ℕ) : Option ℕ :=
  stepWith RosserPackedMoments.packedMoments mask a b v

theorem step_sound (mask a b v w : ℕ)
    (hcover : ∀ p, Nat.Prime p → a < p → p ≤ b →
      mask.testBit (p - (a + 1)) = true)
    (hv : ((v : ℝ) / scale) ≤ RosserMomentBridge.reciprocalProduct a)
    (h : step mask a b v = some w) :
    ((w : ℝ) / scale ≤ RosserMomentBridge.reciprocalProduct b) ∧
      ∀ x : ℝ, (a : ℝ) ≤ x → x ≤ b → RosserBlockCheck.Bound x := by
  exact stepWith_sound RosserPackedMoments.packedMoments
    (by
      intro depth mask len hmask hlen
      apply (RosserPackedMoments.packedMoments_sound depth mask
        (hmask.trans_le (Nat.pow_le_pow_right (by omega) hlen))).trans
      rw [windowOffsets_eq_enumBits depth mask len hmask])
    mask a b v w hcover hv h

end RosserFastCompute

-- Source: Solutions/RosserMediumChain.lean
/-! Compose checked prefix blocks using cached sieve masks for segments of at most 2^20 integers. -/

namespace RosserMediumChain

/-- The shared periodic masks cover every segment of this maximum length. -/
def fixedLen : ℕ := 1048576

open RosserScan RosserLogCertificate RosserMomentBridge

structure Checkpoint where
  a : ℕ
  b : ℕ
  initial : ℕ
  final : ℕ

structure Group where
  base : ℕ
  top : ℕ
  initial : ℕ
  final : ℕ
  checkpoints : List Checkpoint

def checkPoints (mask base : ℕ) : List Checkpoint → Bool
  | [] => true
  | c :: cs =>
    (forceNat ((mask >>> (c.a - base)) &&& (2 ^ (c.b - c.a) - 1)) fun window =>
      RosserFastCompute.step window c.a c.b c.initial == some c.final) &&
        checkPoints mask base cs

def checkGroups (ds : List (ℕ × ℕ)) : List Group → Bool
  | [] => true
  | g :: gs =>
    (forceNat (RosserCachedSieve.mask ds g.base g.top) fun mask =>
      checkPoints mask g.base g.checkpoints) && checkGroups ds gs

theorem checkGroups_append (ds : List (ℕ × ℕ)) (xs ys : List Group) :
    checkGroups ds (xs ++ ys) = (checkGroups ds xs && checkGroups ds ys) := by
  induction xs with
  | nil => simp [checkGroups]
  | cons g gs ih =>
    simp only [List.cons_append, checkGroups, ih, Bool.and_assoc]

def allGroups (gs : List Group) : Bool :=
  RosserCachedSieve.withMasks fixedLen RosserSieveData.divisors fun ds =>
    checkGroups ds gs

theorem checkPoints_sound (mask base : ℕ) (cs : List Checkpoint)
    (h : checkPoints mask base cs = true) :
    ∀ c ∈ cs, RosserFastCompute.step
      (mask / 2 ^ (c.a - base) % 2 ^ (c.b - c.a))
      c.a c.b c.initial = some c.final := by
  induction cs with
  | nil => simp
  | cons c cs ih =>
    simp only [checkPoints, RosserScan.forceNat_eq, Nat.shiftRight_eq_div_pow,
      Nat.and_two_pow_sub_one_eq_mod, Bool.and_eq_true] at h
    obtain ⟨hc, hcs⟩ := h
    intro d hd
    rcases List.mem_cons.mp hd with rfl | hd
    · exact beq_iff_eq.mp hc
    · exact ih hcs d hd

theorem checkGroups_sound (ds : List (ℕ × ℕ)) (gs : List Group)
    (h : checkGroups ds gs = true) :
    ∀ g ∈ gs, ∀ c ∈ g.checkpoints,
      RosserFastCompute.step
        (RosserCachedSieve.mask ds g.base g.top /
          2 ^ (c.a - g.base) % 2 ^ (c.b - c.a))
        c.a c.b c.initial = some c.final := by
  induction gs with
  | nil => simp
  | cons g gs ih =>
    simp only [checkGroups, RosserScan.forceNat_eq, Bool.and_eq_true] at h
    obtain ⟨hg, hgs⟩ := h
    intro g' hg' c hc
    rcases List.mem_cons.mp hg' with rfl | hg'
    · exact checkPoints_sound _ _ _ hg c hc
    · exact ih hgs g' hg' c hc

def Linked (a v top w : ℕ) : List Checkpoint → Prop
  | [] => a = top ∧ v = w
  | c :: cs =>
      c.a = a ∧ c.initial = v ∧ a < c.b ∧ c.b ≤ top ∧
        Linked c.b c.final top w cs

def LinkedGroups (a v top : ℕ) : List Group → Prop
  | [] => a = top
  | g :: gs =>
      g.base = a ∧ g.initial = v ∧ g.base < g.top ∧
        g.top - g.base ≤ fixedLen ∧
        Linked g.base g.initial g.top g.final g.checkpoints ∧
        LinkedGroups g.top g.final top gs

def linkedPoints (a v top w : ℕ) : List Checkpoint → Bool
  | [] => decide (a = top ∧ v = w)
  | c :: cs =>
      decide (c.a = a ∧ c.initial = v ∧ a < c.b ∧ c.b ≤ top) &&
        linkedPoints c.b c.final top w cs

def linkedGroups (a v top : ℕ) : List Group → Bool
  | [] => decide (a = top)
  | g :: gs =>
      decide (g.base = a ∧ g.initial = v ∧ g.base < g.top ∧
        g.top - g.base ≤ fixedLen) &&
        linkedPoints g.base g.initial g.top g.final g.checkpoints &&
        linkedGroups g.top g.final top gs

theorem linkedPoints_sound (a v top w : ℕ) (cs : List Checkpoint)
    (h : linkedPoints a v top w cs = true) : Linked a v top w cs := by
  induction cs generalizing a v with
  | nil => simpa only [linkedPoints, decide_eq_true_eq, Linked] using h
  | cons c cs ih =>
    simp only [linkedPoints, Bool.and_eq_true, decide_eq_true_eq] at h
    rcases h with ⟨hc, hrest⟩
    exact ⟨hc.1, hc.2.1, hc.2.2.1, hc.2.2.2,
      ih c.b c.final hrest⟩

theorem linkedGroups_sound (a v top : ℕ) (gs : List Group)
    (h : linkedGroups a v top gs = true) : LinkedGroups a v top gs := by
  induction gs generalizing a v with
  | nil => simpa only [linkedGroups, decide_eq_true_eq, LinkedGroups] using h
  | cons g gs ih =>
    simp only [linkedGroups, Bool.and_eq_true, decide_eq_true_eq] at h
    rcases h with ⟨⟨hg, hp⟩, hrest⟩
    exact ⟨hg.1, hg.2.1, hg.2.2.1, hg.2.2.2,
      linkedPoints_sound _ _ _ _ _ hp, ih g.top g.final hrest⟩

theorem linked_sound (mask base top a v w : ℕ) (cs : List Checkpoint)
    (hcover : RosserScan.Covers base top mask)
    (hbase : base ≤ a)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a)
    (hlinked : Linked a v top w cs)
    (hchecks : ∀ c ∈ cs, RosserFastCompute.step
      (mask / 2 ^ (c.a - base) % 2 ^ (c.b - c.a))
      c.a c.b c.initial = some c.final) :
    ((w : ℝ) / scale ≤ reciprocalProduct top) ∧
      ∀ x : ℝ, (a : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  induction cs generalizing a v with
  | nil =>
    obtain ⟨rfl, rfl⟩ := hlinked
    refine ⟨hv, ?_⟩
    intro x hax hxt
    linarith
  | cons c cs ih =>
    obtain ⟨hca, hcv, hab, hbt, hrest⟩ := hlinked
    have hstep := hchecks c (by simp)
    have hcover' := RosserPrefixBridge.window_mask_covers base top mask
      c.a c.b hcover (by omega) hbt
    have hrec : ((c.initial : ℝ) / scale) ≤ reciprocalProduct c.a := by
      simpa only [hca, hcv] using hv
    have hs := RosserFastCompute.step_sound _ _ _ _ _ hcover' hrec hstep
    have htail : ∀ d ∈ cs, RosserFastCompute.step
        (mask / 2 ^ (d.a - base) % 2 ^ (d.b - d.a))
        d.a d.b d.initial = some d.final := by
      intro d hd
      exact hchecks d (List.mem_cons_of_mem _ hd)
    have ht := ih c.b c.final (by omega) hs.1 hrest htail
    refine ⟨ht.1, ?_⟩
    intro x hax hxt
    by_cases hxb : x ≤ c.b
    · exact hs.2 x (by exact_mod_cast (show a = c.a by omega) ▸ le_of_lt hax) hxb
    · exact ht.2 x (lt_of_not_ge hxb) hxt

def cachedPairs : List (ℕ × ℕ) :=
  RosserCachedSieve.pairs fixedLen RosserSieveData.divisors

theorem group_sound (g : Group)
    (hshape : g.base < g.top ∧ g.top - g.base ≤ fixedLen)
    (hlink : Linked g.base g.initial g.top g.final g.checkpoints)
    (hcheck : checkPoints
      (RosserCachedSieve.mask cachedPairs g.base g.top)
      g.base g.checkpoints = true)
    (hv : ((g.initial : ℝ) / scale) ≤ reciprocalProduct g.base) :
    ((g.final : ℝ) / scale ≤ reciprocalProduct g.top) ∧
      ∀ x : ℝ, (g.base : ℝ) < x → x ≤ g.top → RosserBlockCheck.Bound x := by
  let m := RosserCachedSieve.mask cachedPairs g.base g.top
  have hcover : RosserScan.Covers g.base g.top m := by
    intro p hp hbp hpt
    exact RosserCachedSieve.mask_prime fixedLen g.base g.top
      RosserSieveData.divisors RosserSieveData.divisors_ge_two
      hshape.1 hshape.2 p hp hbp hpt
  have hs := checkPoints_sound m g.base g.checkpoints hcheck
  exact linked_sound m g.base g.top g.base g.initial g.final
    g.checkpoints hcover (le_refl _) hv hlink hs

theorem groups_sound (gs : List Group) (a v top : ℕ)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a)
    (hlink : LinkedGroups a v top gs)
    (hcheck : checkGroups cachedPairs gs = true) :
    ∀ x : ℝ, (a : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  induction gs generalizing a v with
  | nil =>
    intro x hax hxt
    change a = top at hlink
    subst top
    linarith
  | cons g gs ih =>
    obtain ⟨hga, hgv, hgt, hwidth, hpoints, hrest⟩ := hlink
    simp only [checkGroups, RosserScan.forceNat_eq, Bool.and_eq_true] at hcheck
    obtain ⟨hgc, hgs⟩ := hcheck
    have hv' : ((g.initial : ℝ) / scale) ≤ reciprocalProduct g.base := by
      simpa only [hga, hgv] using hv
    have hg := group_sound g ⟨hgt, hwidth⟩ hpoints hgc hv'
    have ht := ih g.top g.final hg.1 hrest hgs
    intro x hax hxt
    by_cases hxg : x ≤ g.top
    · apply hg.2 x
      · have : (a : ℝ) = g.base := by exact_mod_cast hga.symm
        linarith only [hax, this]
      · exact hxg
    · exact ht x (lt_of_not_ge hxg) hxt

theorem allGroups_sound (gs : List Group) (a v top : ℕ)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a)
    (hlink : LinkedGroups a v top gs)
    (hcheck : allGroups gs = true) :
    ∀ x : ℝ, (a : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  simp only [allGroups, RosserCachedSieve.withMasks_eq] at hcheck
  exact groups_sound gs a v top hv hlink hcheck


theorem allGroups_append (xs ys : List Group) :
    allGroups (xs ++ ys) = (allGroups xs && allGroups ys) := by
  simp only [allGroups, RosserCachedSieve.withMasks_eq, checkGroups_append]

theorem allGroups_append_true {xs ys : List Group}
    (hx : allGroups xs = true) (hy : allGroups ys = true) :
    allGroups (xs ++ ys) = true := by
  rw [allGroups_append, hx, hy]
  rfl

#print axioms allGroups_sound

end RosserMediumChain

-- Source: Solutions/RosserMediumSqrtChain.lean
/-! A medium-segment verifier that stops the divisor list at the square-root
cutoff. Its prime-covering proof only uses that selected divisors come from the
original list; no equality with the unfiltered sieve is assumed. -/

namespace RosserMediumSqrtChain

open RosserScan RosserLogCertificate RosserMomentBridge

abbrev Checkpoint := RosserMediumChain.Checkpoint
abbrev Group := RosserMediumChain.Group
abbrev fixedLen := RosserMediumChain.fixedLen
abbrev checkPoints := RosserMediumChain.checkPoints
abbrev Linked := RosserMediumChain.Linked
abbrev LinkedGroups := RosserMediumChain.LinkedGroups
abbrev linkedGroups := RosserMediumChain.linkedGroups
abbrev linkedGroups_sound := RosserMediumChain.linkedGroups_sound

def select (top : ℕ) (ds : List (ℕ × ℕ)) : List (ℕ × ℕ) :=
  ds.takeWhile (fun dm => decide (dm.1 * dm.1 ≤ top))

def mask (ds : List (ℕ × ℕ)) (base top : ℕ) : ℕ :=
  RosserCachedSieve.mask (select top ds) base top

theorem select_pairs (len top : ℕ) (ds : List ℕ) :
    select top (RosserCachedSieve.pairs len ds) =
      RosserCachedSieve.pairs len
        (ds.takeWhile (fun d => decide (d * d ≤ top))) := by
  simp only [select, RosserCachedSieve.pairs, List.takeWhile_map,
    Function.comp_def]

theorem mask_prime (len base top : ℕ) (ds : List ℕ)
    (hds : ∀ d ∈ ds, 2 ≤ d) (hbase : base < top)
    (hlen : top - base ≤ len) :
    Covers base top (mask (RosserCachedSieve.pairs len ds) base top) := by
  unfold mask
  rw [select_pairs]
  apply RosserCachedSieve.mask_prime len base top _ _ hbase hlen
  intro d hd
  exact hds d ((List.takeWhile_subset _ ) hd)

def checkGroups (ds : List (ℕ × ℕ)) : List Group → Bool
  | [] => true
  | g :: gs =>
    (forceNat (mask ds g.base g.top) fun mask =>
      checkPoints mask g.base g.checkpoints) && checkGroups ds gs

theorem checkGroups_append (ds : List (ℕ × ℕ)) (xs ys : List Group) :
    checkGroups ds (xs ++ ys) = (checkGroups ds xs && checkGroups ds ys) := by
  induction xs with
  | nil => simp [checkGroups]
  | cons g gs ih =>
    simp only [List.cons_append, checkGroups, ih, Bool.and_assoc]

def allGroups (gs : List Group) : Bool :=
  RosserCachedSieve.withMasks fixedLen RosserSieveData.divisors fun ds =>
    checkGroups ds gs

def cachedPairs : List (ℕ × ℕ) :=
  RosserCachedSieve.pairs fixedLen RosserSieveData.divisors

theorem group_sound (g : Group)
    (hshape : g.base < g.top ∧ g.top - g.base ≤ fixedLen)
    (hlink : Linked g.base g.initial g.top g.final g.checkpoints)
    (hcheck : checkPoints (mask cachedPairs g.base g.top)
      g.base g.checkpoints = true)
    (hv : ((g.initial : ℝ) / scale) ≤ reciprocalProduct g.base) :
    ((g.final : ℝ) / scale ≤ reciprocalProduct g.top) ∧
      ∀ x : ℝ, (g.base : ℝ) < x → x ≤ g.top → RosserBlockCheck.Bound x := by
  have hcover : Covers g.base g.top (mask cachedPairs g.base g.top) :=
    mask_prime fixedLen g.base g.top RosserSieveData.divisors
      RosserSieveData.divisors_ge_two hshape.1 hshape.2
  exact RosserMediumChain.linked_sound _ _ _ _ _ _ _ hcover (le_refl _) hv hlink
    (RosserMediumChain.checkPoints_sound _ _ _ hcheck)

theorem groups_sound (gs : List Group) (a v top : ℕ)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a)
    (hlink : LinkedGroups a v top gs)
    (hcheck : checkGroups cachedPairs gs = true) :
    ∀ x : ℝ, (a : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  induction gs generalizing a v with
  | nil =>
    intro x hax hxt
    change a = top at hlink
    subst top
    linarith
  | cons g gs ih =>
    obtain ⟨hga, hgv, hgt, hwidth, hpoints, hrest⟩ := hlink
    simp only [checkGroups, RosserScan.forceNat_eq, Bool.and_eq_true] at hcheck
    obtain ⟨hgc, hgs⟩ := hcheck
    have hv' : ((g.initial : ℝ) / scale) ≤ reciprocalProduct g.base := by
      simpa only [hga, hgv] using hv
    have hg := group_sound g ⟨hgt, hwidth⟩ hpoints hgc hv'
    have ht := ih g.top g.final hg.1 hrest hgs
    intro x hax hxt
    by_cases hxg : x ≤ g.top
    · apply hg.2 x
      · have : (a : ℝ) = g.base := by exact_mod_cast hga.symm
        linarith only [hax, this]
      · exact hxg
    · exact ht x (lt_of_not_ge hxg) hxt

theorem allGroups_sound (gs : List Group) (a v top : ℕ)
    (hv : ((v : ℝ) / scale) ≤ reciprocalProduct a)
    (hlink : LinkedGroups a v top gs)
    (hcheck : allGroups gs = true) :
    ∀ x : ℝ, (a : ℝ) < x → x ≤ top → RosserBlockCheck.Bound x := by
  simp only [allGroups, RosserCachedSieve.withMasks_eq] at hcheck
  exact groups_sound gs a v top hv hlink hcheck

theorem allGroups_append (xs ys : List Group) :
    allGroups (xs ++ ys) = (allGroups xs && allGroups ys) := by
  simp only [allGroups, RosserCachedSieve.withMasks_eq, checkGroups_append]

theorem allGroups_append_true {xs ys : List Group}
    (hx : allGroups xs = true) (hy : allGroups ys = true) :
    allGroups (xs ++ ys) = true := by
  rw [allGroups_append, hx, hy]
  rfl

#print axioms allGroups_sound

end RosserMediumSqrtChain
Source
Axler, Elementary proof of the Chebyshev theta bounds, internal certificate modules.

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