Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · DirichletSeries · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_DirichletSeries

by liuyao · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ca-fd889115-k1

Private dependency for the Distribution Theory mission. Module ComputableAnalysis/DirichletSeries.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FTC

set_option autoImplicit true

/-!
# Dirichlet series

Computable Dirichlet-series style algorithms: zeta values, Dirichlet
L-functions, and the Dirichlet beta value behind Leibniz pi.
-/

namespace ComputableAnalysis

namespace DirichletSeries

def zetaTwoTerm (k : Nat) : Rat :=
  let m : Rat := ((k + 1 : Nat) : Rat)
  1 / (m * m)

/-- The finite partial sum `sum_{k=1}^n 1/k^2`. -/
def zetaTwoPartial : Nat -> Rat
  | 0 => 0
  | n + 1 => zetaTwoPartial n + zetaTwoTerm n

theorem zetaTwoPartial_succ (n : Nat) :
    zetaTwoPartial (n + 1) = zetaTwoPartial n + zetaTwoTerm n := by
  rfl

theorem zetaTwoTerm_nonneg (k : Nat) : 0 <= zetaTwoTerm k := by
  unfold zetaTwoTerm
  let m : Rat := ((k + 1 : Nat) : Rat)
  have hmpos : 0 < m := by
    dsimp [m]
    exact (Rat.natCast_pos).2 (Nat.succ_pos k)
  exact Rat.le_of_lt (by
    rw [Rat.div_def, Rat.one_mul]
    exact (Rat.inv_pos).2 (Rat.mul_pos hmpos hmpos))

theorem zetaTwoTerm_pos (k : Nat) : 0 < zetaTwoTerm k := by
  unfold zetaTwoTerm
  let m : Rat := ((k + 1 : Nat) : Rat)
  have hmpos : 0 < m := by
    dsimp [m]
    exact (Rat.natCast_pos).2 (Nat.succ_pos k)
  rw [Rat.div_def, Rat.one_mul]
  exact (Rat.inv_pos).2 (Rat.mul_pos hmpos hmpos)

theorem zetaTwoPartial_nonneg (n : Nat) :
    0 <= zetaTwoPartial n := by
  induction n with
  | zero => simp [zetaTwoPartial]
  | succ n ih =>
      rw [zetaTwoPartial_succ]
      exact Rat.add_nonneg ih (zetaTwoTerm_nonneg n)

theorem zetaTwoPartial_le_succ (n : Nat) :
    zetaTwoPartial n <= zetaTwoPartial (n + 1) := by
  change zetaTwoPartial n <= zetaTwoPartial n + zetaTwoTerm n
  grind [zetaTwoTerm_nonneg n]

theorem zetaTwoPartial_lt_succ (n : Nat) :
    zetaTwoPartial n < zetaTwoPartial (n + 1) := by
  change zetaTwoPartial n < zetaTwoPartial n + zetaTwoTerm n
  have h : zetaTwoPartial n + 0 <
      zetaTwoPartial n + zetaTwoTerm n :=
    (Rat.add_lt_add_left).2 (zetaTwoTerm_pos n)
  grind

theorem zetaTwoPartial_le_of_le {n m : Nat} :
    n <= m -> zetaTwoPartial n <= zetaTwoPartial m := by
  intro h
  induction h with
  | refl => exact Rat.le_refl
  | step _ ih =>
      exact Rat.le_trans ih (zetaTwoPartial_le_succ _)

/-- A finite tail after the first `n` terms:
`sum_{j=0}^{count-1} 1/(n+j+1)^2`. -/
def zetaTwoFiniteTail (n : Nat) : Nat -> Rat
  | 0 => 0
  | count + 1 => zetaTwoFiniteTail n count + zetaTwoTerm (n + count)

theorem zetaTwoFiniteTail_succ (n count : Nat) :
    zetaTwoFiniteTail n (count + 1) =
      zetaTwoFiniteTail n count + zetaTwoTerm (n + count) := by
  rfl

/-- Finite tails concatenate exactly at the shifted starting index.  This is
the blockwise accounting law used when several finite error budgets are
combined. -/
theorem zetaTwoFiniteTail_add (n count extra : Nat) :
    zetaTwoFiniteTail n (count + extra) =
      zetaTwoFiniteTail n count +
        zetaTwoFiniteTail (n + count) extra := by
  induction extra with
  | zero => grind [zetaTwoFiniteTail]
  | succ extra ih =>
      have hcount : count + (extra + 1) = (count + extra) + 1 := by omega
      rw [hcount, zetaTwoFiniteTail_succ]
      rw [ih]
      have hshift : n + (count + extra) = (n + count) + extra := by omega
      rw [hshift, zetaTwoFiniteTail_succ]
      grind [Rat.add_assoc]

theorem zetaTwoFiniteTail_nonneg (n count : Nat) :
    0 <= zetaTwoFiniteTail n count := by
  induction count with
  | zero => simp [zetaTwoFiniteTail]
  | succ count ih =>
      rw [zetaTwoFiniteTail_succ]
      exact Rat.add_nonneg ih (zetaTwoTerm_nonneg (n + count))

theorem zetaTwoFiniteTail_pos (n count : Nat) (hcount : 0 < count) :
    0 < zetaTwoFiniteTail n count := by
  cases count with
  | zero => omega
  | succ count =>
      rw [zetaTwoFiniteTail_succ]
      have hterm := zetaTwoTerm_pos (n + count)
      have htail := zetaTwoFiniteTail_nonneg n count
      grind

private theorem rat_add_le_add {a b c d : Rat}
    (hab : a <= b) (hcd : c <= d) :
    a + c <= b + d := by
  grind

/-- One term of the zeta tail is bounded by the corresponding telescoping
difference:

`1/(m+1)^2 <= 1/m - 1/(m+1)`.
-/
theorem zetaTwoTerm_le_telescopeStep (m : Nat) (hm : 0 < m) :
    zetaTwoTerm m <=
      1 / (m : Rat) - 1 / ((m + 1 : Nat) : Rat) := by
  unfold zetaTwoTerm
  let M : Rat := (m : Rat)
  let S : Rat := ((m + 1 : Nat) : Rat)
  have hMpos : 0 < M := by
    dsimp [M]
    exact (Rat.natCast_pos).2 hm
  have hSpos : 0 < S := by
    dsimp [S]
    exact (Rat.natCast_pos).2 (Nat.succ_pos m)
  have hMne : M ≠0 := Rat.ne_of_gt hMpos
  have hSne : S ≠0 := Rat.ne_of_gt hSpos
  have hSSne : S * S ≠0 := by
    exact Rat.ne_of_gt (Rat.mul_pos hSpos hSpos)
  have hMleS : M <= S := by
    dsimp [M, S]
    exact_mod_cast (Nat.le_succ m)
  apply Rat.le_of_mul_le_mul_right (c := (S * S) * M)
  · calc
      (1 / (S * S)) * ((S * S) * M) = M := by
        rw [Rat.div_def]
        have hcancel : (S * S) * (S * S)⁻¹= 1 :=
          Rat.mul_inv_cancel (S * S) hSSne
        grind [Rat.mul_assoc, Rat.mul_comm]
      _ <= S := hMleS
      _ = (1 / M - 1 / S) * ((S * S) * M) := by
        rw [Rat.div_def, Rat.div_def]
        have hMcancel : M * M⁻¹= 1 := Rat.mul_inv_cancel M hMne
        have hScancel : S * S⁻¹= 1 := Rat.mul_inv_cancel S hSne
        grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc, Rat.add_comm,
          Rat.mul_assoc, Rat.mul_comm]
  · exact Rat.mul_pos (Rat.mul_pos hSpos hSpos) hMpos

def telescopingTailBound (n : Nat) (count : Nat) : Rat :=
  1 / (n : Rat) - 1 / ((n + count : Nat) : Rat)

private theorem telescopingTailBound_step (n : Nat) (count : Nat) :
    telescopingTailBound n count +
      (1 / ((n + count : Nat) : Rat) -
        1 / (((n + count) + 1 : Nat) : Rat)) =
      telescopingTailBound n (count + 1) := by
  unfold telescopingTailBound
  have hnat : n + (count + 1) = (n + count) + 1 := by omega
  rw [hnat]
  grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

/-- Finite telescoping proof of the zeta(2) tail estimate:

`sum_{j=0}^{count-1} 1/(n+j+1)^2 <= 1/n - 1/(n+count)`.
-/
theorem zetaTwoFiniteTail_le_telescoping
    (n : Nat) (hn : 0 < n) (count : Nat) :
    zetaTwoFiniteTail n count <= telescopingTailBound n count := by
  induction count with
  | zero =>
      unfold zetaTwoFiniteTail telescopingTailBound
      grind [Rat.sub_eq_add_neg]
  | succ count ih =>
      unfold zetaTwoFiniteTail
      have hstep :
          zetaTwoTerm (n + count) <=
            1 / ((n + count : Nat) : Rat) -
              1 / (((n + count) + 1 : Nat) : Rat) :=
        zetaTwoTerm_le_telescopeStep (n + count) (Nat.add_pos_left hn count)
      calc
        zetaTwoFiniteTail n count + zetaTwoTerm (n + count)
            <= telescopingTailBound n count +
                (1 / ((n + count : Nat) : Rat) -
                  1 / (((n + count) + 1 : Nat) : Rat)) :=
              rat_add_le_add ih hstep
        _ = telescopingTailBound n (count + 1) :=
              telescopingTailBound_step n count

/-- The finite tail estimate in the coarser form used by the interval
algorithm. -/
theorem zetaTwoFiniteTail_le_tailBound (n : Nat) (hn : 0 < n) (count : Nat) :
    zetaTwoFiniteTail n count <= 1 / (n : Rat) := by
  have htel := zetaTwoFiniteTail_le_telescoping n hn count
  have hdenpos : 0 < ((n + count : Nat) : Rat) := by
    exact (Rat.natCast_pos).2 (Nat.add_pos_left hn count)
  have hnonneg : 0 <= 1 / ((n + count : Nat) : Rat) :=
    Rat.le_of_lt (by
      rw [Rat.div_def, Rat.one_mul]
      exact (Rat.inv_pos).2 hdenpos)
  exact Rat.le_trans htel (by
    unfold telescopingTailBound
    grind [Rat.sub_eq_add_neg])

theorem zetaTwoFiniteTail_lt_one_div
    (n : Nat) (hn : 0 < n) (count : Nat) (hcount : 0 < count) :
    zetaTwoFiniteTail n count < 1 / (n : Rat) := by
  have hbound := zetaTwoFiniteTail_le_telescoping n hn count
  have hsumpos : 0 < n + count := by omega
  have htailpos : 0 < 1 / ((n + count : Nat) : Rat) := by
    rw [Rat.div_def, Rat.one_mul]
    exact (Rat.inv_pos).2 ((Rat.natCast_pos).2 hsumpos)
  unfold telescopingTailBound at hbound
  grind

/-- The endpoint padding used by the Basel-series interval algorithm.

This is part of the raw algorithm's definition.  The finite telescoping
lemmas above explain why this is the traditional tail padding, but validity
of the raw real only uses the interval order, nesting, and width shrinking
proved below. -/
def zetaTwoTailBound (n : Nat) : Rat :=
  if n = 0 then 2 else 1 / (n : Rat)

def zetaTwoUpper (n : Nat) : Rat :=
  zetaTwoPartial n + zetaTwoTailBound n

theorem zetaTwoUpper_succ_le (n : Nat) (hn : 0 < n) :
    zetaTwoUpper (n + 1) <= zetaTwoUpper n := by
  unfold zetaTwoUpper zetaTwoTailBound
  rw [if_neg (Nat.succ_ne_zero n)]
  rw [if_neg (Nat.ne_of_gt hn)]
  change zetaTwoPartial n + zetaTwoTerm n +
      1 / ((n + 1 : Nat) : Rat) <=
    zetaTwoPartial n + 1 / (n : Rat)
  have hstep := zetaTwoTerm_le_telescopeStep n hn
  have hwithPartial :
      zetaTwoPartial n + zetaTwoTerm n <=
        zetaTwoPartial n +
          (1 / (n : Rat) - 1 / ((n + 1 : Nat) : Rat)) :=
    rat_add_le_add (by exact Rat.le_refl) hstep
  calc
    zetaTwoPartial n + zetaTwoTerm n +
        1 / ((n + 1 : Nat) : Rat)
        <= zetaTwoPartial n +
            (1 / (n : Rat) - 1 / ((n + 1 : Nat) : Rat)) +
              1 / ((n + 1 : Nat) : Rat) :=
          rat_add_le_add hwithPartial (by exact Rat.le_refl)
    _ = zetaTwoPartial n + 1 / (n : Rat) := by
          grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

theorem zetaTwoUpper_le_of_le {n m : Nat}
    (hn : 0 < n) (h : n <= m) :
    zetaTwoUpper m <= zetaTwoUpper n := by
  induction h with
  | refl => exact Rat.le_refl
  | step h ih =>
      have hmpos : 0 < _ := Nat.lt_of_lt_of_le hn h
      exact Rat.le_trans (zetaTwoUpper_succ_le _ hmpos) ih

/-- Every finite reciprocal-square partial sum stays below the initial
stage-one padded endpoint.  This is a global finite bound for the Basel
certificate, not an assertion of the infinite sum. -/
theorem zetaTwoPartial_le_two (n : Nat) :
    zetaTwoPartial n ≤ 2 := by
  by_cases hn0 : n = 0
  · simp [hn0, zetaTwoPartial]
    decide +kernel
  · have hn : 0 < n := Nat.pos_of_ne_zero hn0
    have hpartial_upper : zetaTwoPartial n ≤ zetaTwoUpper n := by
      unfold zetaTwoUpper zetaTwoTailBound
      simp [hn0]
      have htail_pos : 0 < 1 / (n : Rat) := one_div_nat_pos hn
      have htail_nonneg : 0 ≤ 1 / (n : Rat) := Rat.le_of_lt htail_pos
      simpa only [Rat.add_zero] using (Rat.add_le_add_left (a := (0 : Rat))
        (b := 1 / (n : Rat)) (c := zetaTwoPartial n)).2 htail_nonneg
    have hupper : zetaTwoUpper n ≤ zetaTwoUpper 1 :=
      zetaTwoUpper_le_of_le (by omega : 0 < (1 : Nat)) hn
    have hstage_one : zetaTwoUpper 1 = 2 := by
      decide +kernel
    calc
      zetaTwoPartial n ≤ zetaTwoUpper n := hpartial_upper
      _ ≤ zetaTwoUpper 1 := hupper
      _ = 2 := hstage_one

/-- Computable interval for `zeta(2)` at stage `n`.

The lower endpoint is the first `n` terms.  The upper endpoint adds the
elementary rational tail bound `1/n`.
-/
def zetaTwoInterval (n : Nat) : QInterval :=
  let s := zetaTwoPartial n
  { lo := s, hi := s + zetaTwoTailBound n }

theorem zetaTwoInterval_width (n : Nat) :
    (zetaTwoInterval n).width = zetaTwoTailBound n := by
  unfold zetaTwoInterval QInterval.width
  grind [Rat.sub_eq_add_neg]

theorem zetaTwoInterval_width_nonneg (n : Nat) :
    0 <= (zetaTwoInterval n).width := by
  rw [zetaTwoInterval_width]
  unfold zetaTwoTailBound
  by_cases hn0 : n = 0
  · simp [hn0]
    decide +kernel
  · simp [hn0]
    exact Rat.le_of_lt (by
      rw [Rat.div_def, Rat.one_mul]
      exact (Rat.inv_pos).2 ((Rat.natCast_pos).2 (Nat.pos_of_ne_zero hn0)))

theorem zetaTwoInterval_width_pos (n : Nat) (hn : 0 < n) :
    0 < (zetaTwoInterval n).width := by
  rw [zetaTwoInterval_width]
  unfold zetaTwoTailBound
  simp [Nat.ne_of_gt hn]
  exact one_div_nat_pos hn

theorem zetaTwoInterval_lo_nonneg (n : Nat) :
    0 <= (zetaTwoInterval n).lo := by
  change 0 <= zetaTwoPartial n
  exact zetaTwoPartial_nonneg n

theorem zetaTwoInterval_hi_pos (n : Nat) :
    0 < (zetaTwoInterval n).hi := by
  change 0 < zetaTwoPartial n + zetaTwoTailBound n
  by_cases hn0 : n = 0
  · simp [hn0, zetaTwoPartial, zetaTwoTailBound]
    decide +kernel
  · have hn : 0 < n := Nat.pos_of_ne_zero hn0
    have htail : 0 < zetaTwoTailBound n := by
      unfold zetaTwoTailBound
      simp [hn0]
      exact one_div_nat_pos hn
    grind [zetaTwoPartial_nonneg n]

theorem zetaTwoInterval_width_le_one_div (n : Nat) (hn : 0 < n) :
    (zetaTwoInterval n).width <= 1 / (n : Rat) := by
  rw [zetaTwoInterval_width]
  unfold zetaTwoTailBound
  simp [Nat.ne_of_gt hn]

theorem zetaTwoInterval_ordered (n : Nat) :
    (zetaTwoInterval n).lo <= (zetaTwoInterval n).hi := by
  have h := zetaTwoInterval_width_nonneg n
  unfold QInterval.width at h
  grind [Rat.sub_eq_add_neg]

theorem zetaTwoInterval_nested (n m : Nat) (hnm : n <= m) :
    (zetaTwoInterval n).lo <= (zetaTwoInterval m).lo /\
      (zetaTwoInterval m).lo <= (zetaTwoInterval m).hi /\
      (zetaTwoInterval m).hi <= (zetaTwoInterval n).hi := by
  constructor
  · change zetaTwoPartial n <= zetaTwoPartial m
    exact zetaTwoPartial_le_of_le hnm
  · constructor
    · exact zetaTwoInterval_ordered m
    · change zetaTwoUpper m <= zetaTwoUpper n
      by_cases hn0 : n = 0
      · by_cases hm0 : m = 0
        · simp [hn0, hm0, zetaTwoUpper, zetaTwoTailBound]
        · have hmpos : 0 < m := Nat.pos_of_ne_zero hm0
          calc
            zetaTwoUpper m <= zetaTwoUpper 1 :=
              zetaTwoUpper_le_of_le (by omega : 0 < (1 : Nat)) hmpos
            _ = zetaTwoUpper n := by
              rw [hn0]
              decide +kernel
      · exact zetaTwoUpper_le_of_le (Nat.pos_of_ne_zero hn0) hnm

/-- Every later finite partial sum is enclosed by the earlier interval's
upper endpoint.  The proof exposes the finite decomposition into the first
`n` terms and the next `count` terms, then applies the explicit telescoping
tail bound.  This is a finite convergence certificate; it does not identify
the raw value with `pi^2 / 6`. -/
theorem zetaTwoPartial_add_finiteTail_le_interval_hi
    (n count : Nat) (hn : 0 < n) :
    zetaTwoPartial (n + count) <= (zetaTwoInterval n).hi := by
  have hsplit :
    zetaTwoPartial (n + count) =
        zetaTwoPartial n + zetaTwoFiniteTail n count := by
    induction count with
    | zero => simp [zetaTwoFiniteTail, Rat.add_zero]
    | succ count ih =>
        rw [show n + (count + 1) = (n + count) + 1 by omega]
        rw [zetaTwoPartial_succ, ih, zetaTwoFiniteTail_succ]
        grind [Rat.add_assoc]
  rw [hsplit]
  change zetaTwoPartial n + zetaTwoFiniteTail n count <=
    zetaTwoPartial n + zetaTwoTailBound n
  rw [show zetaTwoTailBound n = 1 / (n : Rat) by
    simp [zetaTwoTailBound, Nat.ne_of_gt hn]]
  exact (Rat.add_le_add_left).2
    (zetaTwoFiniteTail_le_tailBound n hn count)

/-- A nonempty finite tail lies strictly below the interval's padded upper
endpoint.  This is the strict finite counterpart of
`zetaTwoPartial_add_finiteTail_le_interval_hi`; it does not use a completed
zeta value. -/
theorem zetaTwoPartial_add_nonempty_finiteTail_lt_interval_hi
    (n count : Nat) (hn : 0 < n) (hcount : 0 < count) :
    zetaTwoPartial (n + count) < (zetaTwoInterval n).hi := by
  have hsplit :
      zetaTwoPartial (n + count) =
        zetaTwoPartial n + zetaTwoFiniteTail n count := by
    clear hcount
    induction count with
    | zero => simp [zetaTwoFiniteTail, Rat.add_zero]
    | succ count ih =>
        rw [show n + (count + 1) = (n + count) + 1 by omega]
        rw [zetaTwoPartial_succ, ih, zetaTwoFiniteTail_succ]
        grind [Rat.add_assoc]
  rw [hsplit]
  change zetaTwoPartial n + zetaTwoFiniteTail n count <
    zetaTwoPartial n + zetaTwoTailBound n
  rw [show zetaTwoTailBound n = 1 / (n : Rat) by
    simp [zetaTwoTailBound, Nat.ne_of_gt hn]]
  exact (Rat.add_lt_add_left).2
    (zetaTwoFiniteTail_lt_one_div n hn count hcount)

/-- A checked finite endpoint certificate for the Basel target.

The stage-1000 interval contains the rational decimal `1.644934`.  This is
only a finite comparison with a proposed target interval; it does not identify
the raw zeta value with `pi^2 / 6`.
-/
theorem zetaTwoInterval_contains_basel_decimal_1000 :
    (zetaTwoInterval 1000).lo <= (822467 : Rat) / 500000 /\
      (822467 : Rat) / 500000 <= (zetaTwoInterval 1000).hi := by
  decide +kernel

theorem zetaTwoInterval_later_inside_stage_10000 {m : Nat}
    (hm : 10000 <= m) :
    (zetaTwoInterval 10000).lo <= (zetaTwoInterval m).lo /\
      (zetaTwoInterval m).hi <= (zetaTwoInterval 10000).hi := by
  have hnested := zetaTwoInterval_nested 10000 m hm
  exact ⟨hnested.1, hnested.2.2⟩

theorem zetaTwoPartial_later_inside_stage_10000 {m : Nat}
    (hm : 10000 <= m) :
    (zetaTwoInterval 10000).lo <= zetaTwoPartial m /\
      zetaTwoPartial m <= (zetaTwoInterval 10000).hi := by
  have hpartial_lo : zetaTwoPartial 10000 <= zetaTwoPartial m :=
    zetaTwoPartial_le_of_le hm
  have hpartial_hi : zetaTwoPartial m <= (zetaTwoInterval m).hi := by
    change (zetaTwoInterval m).lo <= (zetaTwoInterval m).hi
    exact zetaTwoInterval_ordered m
  have hnested := zetaTwoInterval_later_inside_stage_10000 hm
  constructor
  · exact hpartial_lo
  · exact Rat.le_trans hpartial_hi hnested.2

private theorem one_div_nat_le_one_div_nat_of_le
    {a b : Nat} (ha : 0 < a) (hab : a <= b) :
    1 / (b : Rat) <= 1 / (a : Rat) := by
  let A : Rat := (a : Rat)
  let B : Rat := (b : Rat)
  have hApos : 0 < A := by
    dsimp [A]
    exact (Rat.natCast_pos).2 ha
  have hBpos : 0 < B := by
    dsimp [B]
    exact (Rat.natCast_pos).2 (Nat.lt_of_lt_of_le ha hab)
  have hAne : A ≠0 := Rat.ne_of_gt hApos
  have hBne : B ≠0 := Rat.ne_of_gt hBpos
  have hABpos : 0 < A * B := Rat.mul_pos hApos hBpos
  have hAleB : A <= B := by
    dsimp [A, B]
    exact_mod_cast hab
  apply Rat.le_of_mul_le_mul_right (c := A * B)
  · calc
      (1 / B) * (A * B) = A := by
        rw [Rat.div_def]
        have hcancel : B * B⁻¹= 1 := Rat.mul_inv_cancel B hBne
        grind [Rat.mul_assoc, Rat.mul_comm]
      _ <= B := hAleB
      _ = (1 / A) * (A * B) := by
        rw [Rat.div_def]
        have hcancel : A * A⁻¹= 1 := Rat.mul_inv_cancel A hAne
        grind [Rat.mul_assoc, Rat.mul_comm]
  · exact hABpos

/-- An explicit denominator/stage budget turns the finite Basel interval width
into a prescribed rational error bound.  The hypothesis
`eps.den + 1 <= n` is a natural-number certificate: at stage `n`, the
interval width is at most `eps`.  This is an endpoint/width estimate for the
finite evaluator only; it does not assert a completed zeta sum or identify it
with `pi^2 / 6`.
-/
theorem zetaTwoInterval_width_le_of_denominator_budget {n : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) :
    (zetaTwoInterval n).width <= eps := by
  have hbase : 0 < eps.den + 1 := Nat.succ_pos eps.den
  have hn : 0 < n := Nat.lt_of_lt_of_le hbase hbudget
  calc
    (zetaTwoInterval n).width <= 1 / (n : Rat) :=
      zetaTwoInterval_width_le_one_div n hn
    _ <= 1 / (((eps.den + 1 : Nat) : Rat)) :=
      one_div_nat_le_one_div_nat_of_le hbase hbudget
    _ <= eps := FTC.one_div_den_succ_le_of_pos heps

/-- The denominator budget has an executable stage-selector form.  For every
positive rational tolerance, the finite reciprocal-square interval algorithm
returns a natural stage whose width is below that tolerance; no completed
zeta value is introduced. -/
theorem zetaTwoInterval_reaches_of_positive_tolerance (eps : QPos) :
    ∃ n : Nat, (zetaTwoInterval n).width <= eps.val := by
  refine ⟨eps.val.den + 1, ?_⟩
  exact zetaTwoInterval_width_le_of_denominator_budget
    eps.property (Nat.le_refl (eps.val.den + 1))

/-- A supplied rational target interval can be used as a finite comparison
anchor for all later zeta-two stages.  The endpoint hypothesis says that the
target contains the stage-`n` interval; nesting transports that comparison to
stage `m`, while the denominator budget gives the requested finite width
bound.  This is only a comparison of rational interval evaluators and makes
no claim about a completed zeta value or the Basel identity. -/
theorem zetaTwoInterval_later_contained_in_target_of_budget
    (target : QInterval) {n m : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) (hnm : n <= m)
    (htarget : target.ContainsInterval (zetaTwoInterval n)) :
    target.ContainsInterval (zetaTwoInterval m) /\
      (zetaTwoInterval m).width <= eps := by
  have htarget_stage := zetaTwoInterval_nested n m hnm
  have hmBudget : eps.den + 1 <= m := Nat.le_trans hbudget hnm
  constructor
  · unfold QInterval.ContainsInterval at htarget ⊢
    constructor
    · exact Rat.le_trans htarget.1 htarget_stage.1
    · exact Rat.le_trans htarget_stage.2.2 htarget.2
  · exact zetaTwoInterval_width_le_of_denominator_budget heps hmBudget

/-- Every later finite partial sum lies inside a supplied rational target
interval anchored at an earlier Basel-series stage.  This is the endpoint
form of the interval propagation certificate: the lower endpoint comes from
monotonicity of the partial sums, while the upper endpoint comes from the
telescoping tail enclosure and the target's upper endpoint.  The same
denominator budget records the width of the later rational interval. -/
theorem zetaTwoPartial_later_in_target_of_budget
    (target : QInterval) {n m : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) (hnm : n <= m)
    (htarget : target.ContainsInterval (zetaTwoInterval n)) :
    target.lo <= zetaTwoPartial m /\
      zetaTwoPartial m <= target.hi /\
      (zetaTwoInterval m).width <= eps := by
  have htarget_stage := zetaTwoInterval_nested n m hnm
  have hmBudget : eps.den + 1 <= m := Nat.le_trans hbudget hnm
  have hwidth := zetaTwoInterval_width_le_of_denominator_budget heps hmBudget
  have hordered := zetaTwoInterval_ordered m
  have hpartial_hi : zetaTwoPartial m <= (zetaTwoInterval m).hi := by
    change (zetaTwoInterval m).lo <= (zetaTwoInterval m).hi
    exact hordered
  constructor
  · exact Rat.le_trans htarget.1 htarget_stage.1
  · constructor
    · exact Rat.le_trans hpartial_hi
        (Rat.le_trans htarget_stage.2.2 htarget.2)
    · exact hwidth

theorem zetaTwoWidthsShrinkToZero :
    RealCompute.WidthsShrinkToZero zetaTwoInterval := by
  intro eps
  let N : Nat := eps.val.den + 1
  have hNpos : 0 < N := by
    dsimp [N]
    omega
  exact ⟨N, by
    intro n hn
    rw [zetaTwoInterval_width]
    unfold zetaTwoTailBound
    rw [if_neg (Nat.ne_of_gt (Nat.lt_of_lt_of_le hNpos hn))]
    have hsmallN : 1 / (N : Rat) <= eps.val := by
      dsimp [N]
      exact FTC.one_div_den_succ_le_of_pos eps.property
    exact Rat.le_trans
      (one_div_nat_le_one_div_nat_of_le (a := N) (b := n) hNpos hn)
      hsmallN⟩
theorem zetaTwoRaw_validCompute :
    RealCompute.ValidCompute zetaTwoInterval := by
  constructor
  · exact zetaTwoInterval_width_nonneg
  · constructor
    · exact zetaTwoInterval_nested
    · exact zetaTwoWidthsShrinkToZero

/-- Raw zeta(2) algorithm. -/
def zetaTwoRaw : RealCompute where
  compute := zetaTwoInterval
  rate := .power
    1 1 1 (by omega)
    (by
      intro n hn
      rw [zetaTwoInterval_width]
      unfold zetaTwoTailBound
      rw [if_neg (by omega : n ≠ 0)]
      rw [Rat.pow_one]
      exact Rat.le_refl)

/-!
## Integer-exponent zeta values

For every natural exponent `p >= 2`, the same interval trick works:

`sum_{k=1}^n 1/k^p <= zeta(p) <= sum_{k=1}^n 1/k^p + 1/n`.

The padding is intentionally coarse but very robust.  Since
`1/k^p <= 1/k^2` for `p >= 2`, the Basel telescoping estimate certifies
nesting for the whole integer-exponent family.
-/

def zetaNatTerm (p : Nat) (k : Nat) : Rat :=
  let m : Rat := ((k + 1 : Nat) : Rat)
  1 / (m ^ p)

def zetaNatPartial (p : Nat) : Nat -> Rat
  | 0 => 0
  | n + 1 => zetaNatPartial p n + zetaNatTerm p n

/-! The same finite-tail accumulator used for `zeta(2)`, now exposed for
every fixed natural exponent. -/
def zetaNatFiniteTail (p n : Nat) : Nat -> Rat
  | 0 => 0
  | count + 1 =>
      zetaNatFiniteTail p n count + zetaNatTerm p (n + count)

theorem zetaNatFiniteTail_succ (p n count : Nat) :
    zetaNatFiniteTail p n (count + 1) =
      zetaNatFiniteTail p n count + zetaNatTerm p (n + count) := by
  rfl

theorem zetaNatPartial_add_finiteTail_eq (p n count : Nat) :
    zetaNatPartial p (n + count) =
      zetaNatPartial p n + zetaNatFiniteTail p n count := by
  induction count with
  | zero => simp [zetaNatFiniteTail, Rat.add_zero]
  | succ count ih =>
      rw [show n + (count + 1) = (n + count) + 1 by omega]
      rw [show zetaNatPartial p ((n + count) + 1) =
        zetaNatPartial p (n + count) + zetaNatTerm p (n + count) by rfl]
      rw [ih, zetaNatFiniteTail_succ]
      grind [Rat.add_assoc]

def zetaNatTailBound (n : Nat) : Rat :=
  if n = 0 then 2 else 1 / (n : Rat)

def zetaNatUpper (p : Nat) (n : Nat) : Rat :=
  zetaNatPartial p n + zetaNatTailBound n

def zetaNatInterval (p : Nat) (n : Nat) : QInterval :=
  { lo := zetaNatPartial p n, hi := zetaNatUpper p n }

private theorem rat_pow_add (q : Rat) (m n : Nat) :
    q ^ (m + n) = q ^ m * q ^ n := by
  induction n with
  | zero => simp
  | succ n ih =>
      rw [show m + (n + 1) = m + n + 1 by omega]
      rw [Rat.pow_succ, ih, Rat.pow_succ]
      grind [Rat.mul_assoc, Rat.mul_comm]

private theorem one_le_pow_of_one_le {q : Rat}
    (hq : 1 <= q) (n : Nat) :
    1 <= q ^ n := by
  induction n with
  | zero => simp
  | succ n ih =>
      rw [Rat.pow_succ]
      have hq_nonneg : 0 <= q := by grind
      have hpow_nonneg : 0 <= q ^ n := Rat.pow_nonneg hq_nonneg
      have hleft : q ^ n * 1 <= q ^ n * q :=
        Rat.mul_le_mul_of_nonneg_left hq hpow_nonneg
      have hone : 1 <= q ^ n * 1 := by simpa using ih
      exact Rat.le_trans hone hleft

private theorem rat_pow_two_le_pow_of_two_le {q : Rat}
    (hq : 1 <= q) {p : Nat} (hp : 2 <= p) :
    q ^ 2 <= q ^ p := by
  have hrewrite : p = 2 + (p - 2) := by omega
  rw [hrewrite, rat_pow_add]
  have hq_nonneg : 0 <= q := by grind
  have hq2_nonneg : 0 <= q ^ 2 := Rat.pow_nonneg hq_nonneg
  have htail : 1 <= q ^ (p - 2) := one_le_pow_of_one_le hq _
  calc
    q ^ 2 = q ^ 2 * 1 := by rw [Rat.mul_one]
    _ <= q ^ 2 * q ^ (p - 2) :=
      Rat.mul_le_mul_of_nonneg_left htail hq2_nonneg

private theorem one_div_le_one_div_of_pos_of_le
    {a b : Rat} (ha : 0 < a) (hab : a <= b) :
    1 / b <= 1 / a := by
  have hb : 0 < b := by grind
  have hane : a ≠0 := Rat.ne_of_gt ha
  have hbne : b ≠0 := Rat.ne_of_gt hb
  have hprod : 0 < a * b := Rat.mul_pos ha hb
  apply Rat.le_of_mul_le_mul_right (c := a * b)
  · calc
      (1 / b) * (a * b) = a := by
        rw [Rat.div_def]
        have hcancel : b * b⁻¹= 1 := Rat.mul_inv_cancel b hbne
        grind [Rat.mul_assoc, Rat.mul_comm]
      _ <= b := hab
      _ = (1 / a) * (a * b) := by
        rw [Rat.div_def]
        have hcancel : a * a⁻¹= 1 := Rat.mul_inv_cancel a hane
        grind [Rat.mul_assoc, Rat.mul_comm]
  · exact hprod

theorem zetaTwoTerm_antitone {n m : Nat} (hnm : n <= m) :
    zetaTwoTerm m <= zetaTwoTerm n := by
  unfold zetaTwoTerm
  let a : Rat := ((n + 1 : Nat) : Rat)
  let b : Rat := ((m + 1 : Nat) : Rat)
  have ha : 0 < a := by
    dsimp [a]
    exact (Rat.natCast_pos).2 (Nat.succ_pos n)
  have hb : 0 < b := by
    dsimp [b]
    exact (Rat.natCast_pos).2 (Nat.succ_pos m)
  have hab : a <= b := by
    dsimp [a, b]
    exact_mod_cast (Nat.add_le_add_right hnm 1)
  have hsq : a * a <= b * b := by
    calc
      a * a <= b * a :=
        Rat.mul_le_mul_of_nonneg_right hab (Rat.le_of_lt ha)
      _ <= b * b :=
        Rat.mul_le_mul_of_nonneg_left hab (Rat.le_of_lt hb)
  exact one_div_le_one_div_of_pos_of_le (Rat.mul_pos ha ha) hsq

/-- A finite rectangular certificate for a zeta(2) block.

Every term in the block beginning after `n` is no larger than the first
term, so the whole finite block is bounded by `count` copies of that first
term.  This is a reusable rational block estimate; it uses only finite
induction and order, with no limiting or completeness principle. -/
theorem zetaTwoFiniteTail_le_firstTerm_block
    (n count : Nat) :
    zetaTwoFiniteTail n count <= (count : Rat) * zetaTwoTerm n := by
  induction count with
  | zero => simp [zetaTwoFiniteTail]
  | succ count ih =>
      rw [zetaTwoFiniteTail_succ]
      have hterm := zetaTwoTerm_antitone (n := n) (m := n + count)
        (Nat.le_add_right n count)
      have hcount : (count : Rat) * zetaTwoTerm n + zetaTwoTerm n =
          ((count + 1 : Nat) : Rat) * zetaTwoTerm n := by
        rw [Rat.natCast_add]
        simp [Rat.add_mul]
      calc
        zetaTwoFiniteTail n count + zetaTwoTerm (n + count)
            <= (count : Rat) * zetaTwoTerm n + zetaTwoTerm n :=
              rat_add_le_add ih hterm
        _ = ((count + 1 : Nat) : Rat) * zetaTwoTerm n := hcount

theorem zetaNatTerm_nonneg (p k : Nat) :
    0 <= zetaNatTerm p k := by
  unfold zetaNatTerm
  let m : Rat := ((k + 1 : Nat) : Rat)
  have hmpos : 0 < m := by
    dsimp [m]
    exact (Rat.natCast_pos).2 (Nat.succ_pos k)
  exact Rat.le_of_lt (by
    rw [Rat.div_def, Rat.one_mul]
    exact (Rat.inv_pos).2 (Rat.pow_pos hmpos))

theorem zetaNatTerm_le_zetaTwoTerm
    (p k : Nat) (hp : 2 <= p) :
    zetaNatTerm p k <= zetaTwoTerm k := by
  unfold zetaNatTerm zetaTwoTerm
  let m : Rat := ((k + 1 : Nat) : Rat)
  have hmpos : 0 < m := by
    dsimp [m]
    exact (Rat.natCast_pos).2 (Nat.succ_pos k)
  have hmone : 1 <= m := by
    dsimp [m]
    exact_mod_cast (Nat.succ_le_succ (Nat.zero_le k))
  have hpow : m ^ 2 <= m ^ p := rat_pow_two_le_pow_of_two_le hmone hp
  have hm2 : m ^ 2 = m * m := by
    rw [show (2 : Nat) = 1 + 1 by omega]
    rw [Rat.pow_succ]
    simp [Rat.pow_succ, Rat.mul_comm]
  change 1 / (m ^ p) <= 1 / (m * m)
  rw [←hm2]
  exact one_div_le_one_div_of_pos_of_le
    (Rat.pow_pos hmpos) hpow

theorem zetaNatFiniteTail_le_zetaTwoFiniteTail
    (p n count : Nat) (hp : 2 <= p) :
    zetaNatFiniteTail p n count <= zetaTwoFiniteTail n count := by
  induction count with
  | zero => simp [zetaNatFiniteTail, zetaTwoFiniteTail]
  | succ count ih =>
      rw [zetaNatFiniteTail_succ, zetaTwoFiniteTail_succ]
      exact rat_add_le_add ih
        (zetaNatTerm_le_zetaTwoTerm p (n + count) hp)

theorem zetaNatFiniteTail_le_tailBound
    (p n count : Nat) (hp : 2 <= p) (hn : 0 < n) :
    zetaNatFiniteTail p n count <= 1 / (n : Rat) := by
  exact Rat.le_trans
    (zetaNatFiniteTail_le_zetaTwoFiniteTail p n count hp)
    (zetaTwoFiniteTail_le_tailBound n hn count)

theorem zetaNatPartial_add_finiteTail_le_interval_hi
    (p n count : Nat) (hp : 2 <= p) (hn : 0 < n) :
    zetaNatPartial p (n + count) <= (zetaNatInterval p n).hi := by
  rw [zetaNatPartial_add_finiteTail_eq]
  change zetaNatPartial p n + zetaNatFiniteTail p n count <=
    zetaNatPartial p n + zetaNatTailBound n
  rw [show zetaNatTailBound n = 1 / (n : Rat) by
    simp [zetaNatTailBound, Nat.ne_of_gt hn]]
  exact (Rat.add_le_add_left).2
    (zetaNatFiniteTail_le_tailBound p n count hp hn)

theorem zetaNatPartial_le_succ (p n : Nat) :
    zetaNatPartial p n <= zetaNatPartial p (n + 1) := by
  change zetaNatPartial p n <=
    zetaNatPartial p n + zetaNatTerm p n
  grind [zetaNatTerm_nonneg p n]

theorem zetaNatPartial_le_of_le (p : Nat) {n m : Nat} :
    n <= m -> zetaNatPartial p n <= zetaNatPartial p m := by
  intro h
  induction h with
  | refl => exact Rat.le_refl
  | step _ ih =>
      exact Rat.le_trans ih (zetaNatPartial_le_succ p _)

theorem zetaNatInterval_contains_partial_add_finiteTail
    (p n count : Nat) (hp : 2 <= p) (hn : 0 < n) :
    (zetaNatInterval p n).lo <= zetaNatPartial p (n + count) /\
      zetaNatPartial p (n + count) <= (zetaNatInterval p n).hi := by
  constructor
  · change zetaNatPartial p n <= zetaNatPartial p (n + count)
    exact zetaNatPartial_le_of_le p (Nat.le_add_right n count)
  · exact zetaNatPartial_add_finiteTail_le_interval_hi p n count hp hn

theorem zetaNatUpper_succ_le
    (p n : Nat) (hp : 2 <= p) (hn : 0 < n) :
    zetaNatUpper p (n + 1) <= zetaNatUpper p n := by
  unfold zetaNatUpper zetaNatTailBound
  rw [if_neg (Nat.succ_ne_zero n)]
  rw [if_neg (Nat.ne_of_gt hn)]
  change zetaNatPartial p n + zetaNatTerm p n +
      1 / ((n + 1 : Nat) : Rat) <=
    zetaNatPartial p n + 1 / (n : Rat)
  have hstepTwo := zetaTwoTerm_le_telescopeStep n hn
  have hterm : zetaNatTerm p n <=
      1 / (n : Rat) - 1 / ((n + 1 : Nat) : Rat) :=
    Rat.le_trans (zetaNatTerm_le_zetaTwoTerm p n hp) hstepTwo
  have hwithPartial :
      zetaNatPartial p n + zetaNatTerm p n <=
        zetaNatPartial p n +
          (1 / (n : Rat) - 1 / ((n + 1 : Nat) : Rat)) :=
    rat_add_le_add (by exact Rat.le_refl) hterm
  calc
    zetaNatPartial p n + zetaNatTerm p n +
        1 / ((n + 1 : Nat) : Rat)
        <= zetaNatPartial p n +
            (1 / (n : Rat) - 1 / ((n + 1 : Nat) : Rat)) +
              1 / ((n + 1 : Nat) : Rat) :=
          rat_add_le_add hwithPartial (by exact Rat.le_refl)
    _ = zetaNatPartial p n + 1 / (n : Rat) := by
          grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

theorem zetaNatUpper_le_of_le
    (p : Nat) (hp : 2 <= p) {n m : Nat}
    (hn : 0 < n) (h : n <= m) :
    zetaNatUpper p m <= zetaNatUpper p n := by
  induction h with
  | refl => exact Rat.le_refl
  | step h ih =>
      have hmpos : 0 < _ := Nat.lt_of_lt_of_le hn h
      exact Rat.le_trans (zetaNatUpper_succ_le p _ hp hmpos) ih

theorem zetaNatInterval_width (p : Nat) (n : Nat) :
    (zetaNatInterval p n).width = zetaNatTailBound n := by
  unfold zetaNatInterval zetaNatUpper QInterval.width
  grind [Rat.sub_eq_add_neg]

theorem zetaNatInterval_width_nonneg (p : Nat) (n : Nat) :
    0 <= (zetaNatInterval p n).width := by
  rw [zetaNatInterval_width]
  unfold zetaNatTailBound
  by_cases hn0 : n = 0
  · simp [hn0]
    decide +kernel
  · simp [hn0]
    exact Rat.le_of_lt (by
      rw [Rat.div_def, Rat.one_mul]
      exact (Rat.inv_pos).2 ((Rat.natCast_pos).2 (Nat.pos_of_ne_zero hn0)))

theorem zetaNatInterval_ordered (p : Nat) (n : Nat) :
    (zetaNatInterval p n).lo <= (zetaNatInterval p n).hi := by
  have h := zetaNatInterval_width_nonneg p n
  unfold QInterval.width at h
  grind [Rat.sub_eq_add_neg]

theorem zetaNatInterval_nested
    (p : Nat) (hp : 2 <= p)
    (n m : Nat) (hnm : n <= m) :
    (zetaNatInterval p n).lo <= (zetaNatInterval p m).lo /\
      (zetaNatInterval p m).lo <= (zetaNatInterval p m).hi /\
      (zetaNatInterval p m).hi <= (zetaNatInterval p n).hi := by
  constructor
  · exact zetaNatPartial_le_of_le p hnm
  · constructor
    · exact zetaNatInterval_ordered p m
    · by_cases hn0 : n = 0
      · by_cases hm0 : m = 0
        · simp [hn0, hm0, zetaNatInterval, zetaNatUpper, zetaNatTailBound]
        · have hmpos : 0 < m := Nat.pos_of_ne_zero hm0
          change zetaNatUpper p m <= zetaNatUpper p n
          calc
            zetaNatUpper p m <= zetaNatUpper p 1 :=
              zetaNatUpper_le_of_le p hp (by omega : 0 < (1 : Nat)) hmpos
            _ = zetaNatUpper p n := by
              rw [hn0]
              unfold zetaNatUpper zetaNatTailBound zetaNatPartial zetaNatTerm
              simp
              change (0 : Rat) + 1 / (1 : Rat) ^ p + 1 / 1 = 0 + 2
              have hpow : (1 : Rat) ^ p = 1 := by
                clear hp
                induction p with
                | zero => simp
                | succ p ih =>
                    rw [Rat.pow_succ, ih]
                    decide +kernel
              rw [hpow]
              decide +kernel
      · exact zetaNatUpper_le_of_le p hp (Nat.pos_of_ne_zero hn0) hnm

theorem zetaNatWidthsShrinkToZero (p : Nat) :
    RealCompute.WidthsShrinkToZero (zetaNatInterval p) := by
  intro eps
  let N : Nat := eps.val.den + 1
  have hNpos : 0 < N := by
    dsimp [N]
    omega
  exact ⟨N, by
    intro n hn
    rw [zetaNatInterval_width]
    unfold zetaNatTailBound
    rw [if_neg (Nat.ne_of_gt (Nat.lt_of_lt_of_le hNpos hn))]
    have hsmallN : 1 / (N : Rat) <= eps.val := by
      dsimp [N]
      exact FTC.one_div_den_succ_le_of_pos eps.property
    exact Rat.le_trans
      (one_div_nat_le_one_div_nat_of_le (a := N) (b := n) hNpos hn)
      hsmallN⟩

theorem zetaNatInterval_width_le_one_div (p n : Nat) (hn : 0 < n) :
    (zetaNatInterval p n).width <= 1 / (n : Rat) := by
  rw [zetaNatInterval_width]
  unfold zetaNatTailBound
  simp [Nat.ne_of_gt hn]

theorem zetaNatInterval_width_le_of_denominator_budget
    (p : Nat) {n : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) :
    (zetaNatInterval p n).width <= eps := by
  have hbase : 0 < eps.den + 1 := Nat.succ_pos eps.den
  have hn : 0 < n := Nat.lt_of_lt_of_le hbase hbudget
  calc
    (zetaNatInterval p n).width <= 1 / (n : Rat) :=
      zetaNatInterval_width_le_one_div p n hn
    _ <= 1 / (((eps.den + 1 : Nat) : Rat)) :=
      one_div_nat_le_one_div_nat_of_le hbase hbudget
    _ <= eps := FTC.one_div_den_succ_le_of_pos heps

theorem zetaNatInterval_reaches_of_positive_tolerance
    (p : Nat) (eps : QPos) :
    ∃ n : Nat, (zetaNatInterval p n).width <= eps.val := by
  refine ⟨eps.val.den + 1, ?_⟩
  exact zetaNatInterval_width_le_of_denominator_budget
    p eps.property (Nat.le_refl (eps.val.den + 1))

theorem zetaNatInterval_later_contained_in_target_of_budget
    (p : Nat) (hp : 2 <= p) (target : QInterval)
    {n m : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) (hnm : n <= m)
    (htarget : target.ContainsInterval (zetaNatInterval p n)) :
    target.ContainsInterval (zetaNatInterval p m) /\
      (zetaNatInterval p m).width <= eps := by
  have htarget_stage := zetaNatInterval_nested p hp n m hnm
  have hmBudget : eps.den + 1 <= m := Nat.le_trans hbudget hnm
  constructor
  · unfold QInterval.ContainsInterval at htarget ⊢
    constructor
    · exact Rat.le_trans htarget.1 htarget_stage.1
    · exact Rat.le_trans htarget_stage.2.2 htarget.2
  · exact zetaNatInterval_width_le_of_denominator_budget p heps hmBudget

theorem zetaNatPartial_later_in_target_of_budget
    (p : Nat) (hp : 2 <= p) (target : QInterval)
    {n m : Nat} {eps : Rat}
    (heps : 0 < eps) (hbudget : eps.den + 1 <= n) (hnm : n <= m)
    (htarget : target.ContainsInterval (zetaNatInterval p n)) :
    target.lo <= zetaNatPartial p m /\
      zetaNatPartial p m <= target.hi /\
      (zetaNatInterval p m).width <= eps := by
  have htarget_stage := zetaNatInterval_nested p hp n m hnm
  have hmBudget : eps.den + 1 <= m := Nat.le_trans hbudget hnm
  have hwidth := zetaNatInterval_width_le_of_denominator_budget p heps hmBudget
  have hordered := zetaNatInterval_ordered p m
  have hpartial_hi : zetaNatPartial p m <= (zetaNatInterval p m).hi := by
    change (zetaNatInterval p m).lo <= (zetaNatInterval p m).hi
    exact hordered
  constructor
  · exact Rat.le_trans htarget.1 htarget_stage.1
  · constructor
    · exact Rat.le_trans hpartial_hi
        (Rat.le_trans htarget_stage.2.2 htarget.2)
    · exact hwidth

theorem zetaNatRaw_validCompute (p : Nat) (hp : 2 <= p) :
    RealCompute.ValidCompute (zetaNatInterval p) := by
  constructor
  · exact zetaNatInterval_width_nonneg p
  · constructor
    · exact zetaNatInterval_nested p hp
    · exact zetaNatWidthsShrinkToZero p

def zetaNatRaw (p : Nat) : RealCompute where
  compute := zetaNatInterval p
  rate := .power
    1 1 1 (by omega)
    (by
      intro n hn
      rw [zetaNatInterval_width]
      unfold zetaNatTailBound
      rw [if_neg (by omega : n ≠ 0)]
      rw [Rat.pow_one]
      exact Rat.le_refl)

def zetaNat (p : Nat) (hp : 2 <= p) : RealCompute.Certified :=
  RealCompute.Certified.ofRaw (zetaNatRaw p) (zetaNatRaw_validCompute p hp)


/-- Constructive data for a Dirichlet character: a conductor and a computable
complex-valued function on natural numbers.

The character laws are kept as predicates below, so we can first build and
compute with explicit characters, then prove the laws as needed. -/
structure DirichletCharacter where
  conductor : Nat
  value : Nat -> QComplex

namespace DirichletCharacter

def IsPeriodic (chi : DirichletCharacter) : Prop :=
  forall n : Nat, chi.value (n + chi.conductor) = chi.value n

def VanishesOffUnits (chi : DirichletCharacter) : Prop :=
  forall n : Nat, Nat.gcd n chi.conductor ≠ 1 -> chi.value n = QComplex.zero

def IsMultiplicative (chi : DirichletCharacter) : Prop :=
  forall m n : Nat, chi.value (m * n) = QComplex.mul (chi.value m) (chi.value n)

def IsGenuine (chi : DirichletCharacter) : Prop :=
  chi.IsPeriodic /\ chi.VanishesOffUnits /\ chi.IsMultiplicative

end DirichletCharacter

/-- One term `chi(k) / k^s`, with the conventional indexing `k >= 1`. -/
def dirichletLTerm (chi : DirichletCharacter) (s k : Nat) : QComplex :=
  QComplex.scaleRat (1 / ((k : Rat) ^ s)) (chi.value k)

/-- The finite partial sum `sum_{k=1}^n chi(k) / k^s`. -/
def dirichletLPartial (chi : DirichletCharacter) (s n : Nat) : QComplex :=
  (List.range n).foldl
    (fun acc k => QComplex.add acc (dirichletLTerm chi s (k + 1)))
    QComplex.zero

def chi4Value (n : Nat) : QComplex :=
  QComplex.ofRat
    (if n % 2 = 0 then 0 else if n % 4 = 1 then 1 else -1)

/-- The primitive character of conductor 4. -/
def chi4 : DirichletCharacter where
  conductor := 4
  value := chi4Value

/-- The real-valued function behind `chi4`, useful for the alternating
one-dimensional computation. -/
def characterModFour (n : Nat) : Rat :=
  (chi4.value n).re

/-- Finite odd-denominator partial sums for `L(1, chi)`, for real-valued
characters. -/
def dirichletLOddPartialAtOne (chi : Nat -> Rat) (n : Nat) : Rat :=
  (List.range n).foldl
    (fun acc k => acc + chi (2 * k + 1) / ((2 * k + 1 : Nat) : Rat)) 0

def dirichletLChi4OddPartialAtOne (n : Nat) : Rat :=
  dirichletLOddPartialAtOne characterModFour n

/-- The Dirichlet L-value `L(1, chi4)` as a raw real. -/
def dirichletLChi4AtOne : RealCompute where
  compute := fun n =>
    let state : Prod Rat Rat := (List.range n).foldl
      (fun state (i : Nat) =>
        let term1 : Rat := 1 / (4 * i + 3)
        let term2 : Rat := 1 / (4 * i + 5)
        let lo := state.1 - term1
        let hi := lo + term2
        (hi, lo))
      (1, 0)
    { lo := state.2, hi := state.1 }

/-- Conventional alias: the Dirichlet beta function is `L(s, chi4)`. -/
def dirichletBetaAtOne : RealCompute :=
  dirichletLChi4AtOne

end DirichletSeries

end ComputableAnalysis

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