Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · Differential · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_Differential

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Calculus

set_option autoImplicit true

/-!
# Constructive differential calculus

This file contains the small derivative vocabulary needed before proving
calculus identities for the elementary representations.  It is intentionally
interval-valued and rational-only.
-/

namespace ComputableAnalysis

/-- Equality of real-valued functions on rational inputs.

This is the function-level equality notion we use in the project: for every
rational input in the common domain, the two output `RealCompute`s are equivalent
by interval overlap at every precision. -/
def RealFunRaw.EquivalentWith (f g : RealFunRaw)
    (hf : f.Valid) (hg : g.Valid) : Prop :=
  forall x (hfx : f.domain x) (hgx : g.domain x),
    (f.apply hf x hfx).Equiv (g.apply hg x hgx)

def RealFunRaw.Equivalent (f g : RealFunRaw) : Prop :=
  Exists fun hf : f.Valid => Exists fun hg : g.Valid =>
    f.EquivalentWith g hf hg

namespace RealFunRaw

/-! The same representation-graph laws are available for the stable
`x,n ↦ QInterval` function layer.  Transitivity explicitly asks that the
middle evaluator be defined wherever the two outer evaluators are defined;
unlike `FunctionOnInterval`, arbitrary `RealFunRaw`s need not share a domain. -/

theorem equivalentWith_refl (f : RealFunRaw) (hf : f.Valid) :
    f.EquivalentWith f hf hf := by
  intro x hfx hfx'
  exact RealCompute.equiv_refl (f.apply hf x hfx) (hf x hfx)

theorem equivalentWith_symm
    {f g : RealFunRaw} {hf : f.Valid} {hg : g.Valid}
    (h : f.EquivalentWith g hf hg) :
    g.EquivalentWith f hg hf := by
  intro x hgx hfx
  exact RealCompute.equiv_symm (h x hfx hgx)

theorem equivalentWith_trans
    {f g h : RealFunRaw}
    {hf : f.Valid} {hg : g.Valid} {hh : h.Valid}
    (hdom : forall x, f.domain x -> h.domain x -> g.domain x)
    (hfg : f.EquivalentWith g hf hg)
    (hgh : g.EquivalentWith h hg hh) :
    f.EquivalentWith h hf hh := by
  intro x hfx hhx
  have hgx := hdom x hfx hhx
  have hFvalid : (f.apply hf x hfx).Valid := by
    change RealCompute.ValidCompute (f.applyCompute x)
    exact hf x hfx
  have hGvalid : (g.apply hg x hgx).Valid := by
    change RealCompute.ValidCompute (g.applyCompute x)
    exact hg x hgx
  have hHvalid : (h.apply hh x hhx).Valid := by
    change RealCompute.ValidCompute (h.applyCompute x)
    exact hh x hhx
  exact RealCompute.equiv_trans hFvalid hGvalid hHvalid
    (hfg x hfx hgx) (hgh x hgx hhx)

theorem equivalent_refl {f : RealFunRaw} (hf : f.Valid) :
    f.Equivalent f :=
  ⟨hf, ⟨hf, equivalentWith_refl f hf⟩⟩

theorem equivalent_symm {f g : RealFunRaw}
    (h : f.Equivalent g) : g.Equivalent f := by
  rcases h with ⟨hf, hg, hfg⟩
  exact ⟨hg, ⟨hf, equivalentWith_symm hfg⟩⟩

theorem equivalent_trans {f g h : RealFunRaw}
    (hdom : forall x, f.domain x -> h.domain x -> g.domain x)
    (hfg : f.Equivalent g) (hgh : g.Equivalent h) :
    f.Equivalent h := by
  rcases hfg with ⟨hf, hg, hfg⟩
  rcases hgh with ⟨hg', hh, hgh⟩
  have hproof : hg = hg' := Subsingleton.elim _ _
  cases hproof
  exact ⟨hf, ⟨hh, equivalentWith_trans hdom hfg hgh⟩⟩

end RealFunRaw

def derivativeCheckExact (f g : Rat -> Rat) (x h tolerance : Rat) : Bool :=
  if h = 0 then
    false
  else
    decide (qabs (((f (x + h) - f x) / h) - g x) <= tolerance)

namespace ExactFunction

private theorem one_div_den_succ_le_of_pos {q : Rat} (hq : 0 < q) :
    1 / (((q.den + 1 : Nat) : Rat)) <= q := by
  let d : Rat := ((q.den + 1 : Nat) : Rat)
  have hdpos : 0 < d := by
    dsimp [d]
    exact (Rat.natCast_pos).2 (Nat.succ_pos q.den)
  have hnumpos : 0 < q.num := rat_num_pos_of_pos hq
  have hnumgeInt : (1 : Int) <= q.num := by omega
  have hnumge : (1 : Rat) <= (q.num : Rat) := by
    exact_mod_cast hnumgeInt
  have hqd : q * d = (q.num : Rat) + q := by
    dsimp [d]
    have hden := rat_den_mul_self q
    grind [Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]
  have hqd_ge_one : 1 <= q * d := by
    rw [hqd]
    grind [Rat.le_of_lt hq]
  apply Rat.le_of_mul_le_mul_right (c := d)
  · calc
      (1 / d) * d = 1 := by
        rw [Rat.div_def]
        have hdne : d ≠ 0 := Rat.ne_of_gt hdpos
        grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
      _ <= q * d := hqd_ge_one
  · exact hdpos

def affine (m c : Rat) (x : Rat) : Rat := m * x + c
def constant (m : Rat) (_x : Rat) : Rat := m
def square (x : Rat) : Rat := x * x
def cube (x : Rat) : Rat := x ^ 3
def doubleId (x : Rat) : Rat := 2 * x

/-- Effective derivative of an affine function:
the finite-difference quotient is exactly the constant slope. -/
def affineDerivative (m c : Rat) :
    EffectiveDerivativeExact (affine m c) (constant m) where
  stepRadius := fun eps => eps
  good := by
    intro x h eps hhpos _hhle
    unfold affine constant qabs
    have hcalc :
        (((m * (x + h) + c - (m * x + c)) / h) - m) = 0 := by
      rw [Rat.div_def]
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc, Rat.add_comm,
        Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
    rw [hcalc]
    simp
    exact Rat.le_of_lt eps.property

/-! First complete FTC instance.  The derivative of an affine rational
function is constant, so the one-cell rectangle computation is already exact.
This is the finite prototype for later polynomial and special-function FTC
certificates. -/
def affineFTCExact (m c a b : Rat) :
    EffectiveFTCExact (affine m c) (constant m) a b where
  derivative := affineDerivative m c
  chooseN := fun _ => 1
  good := by
    intro eps
    unfold ftcErrorExact
    change qabs
      (riemannLeftExact (fun _ => m) a b 1 -
        (affine m c b - affine m c a)) <= eps.val
    rw [riemannLeftExact_constant_one]
    unfold affine
    simp [qabs]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc, Rat.add_comm,
      Rat.mul_assoc, Rat.mul_comm]

/-! The first nonlinear finite FTC error is the nonnegative missing strip.
This form is convenient for choosing a stage from a rational error budget:
the analytic-looking estimate has become the explicit square of the cell
width divided by the number of cells. -/
theorem ftcErrorExact_square_doubleId_of_pos
    {a b : Rat} (hab : a <= b) {n : Nat} (hn : 0 < n) :
    ftcErrorExact square doubleId a b n =
      (b - a) ^ 2 / (n : Rat) := by
  unfold ftcErrorExact doubleId square
  rw [riemannLeftExact_doubleId_of_pos hn]
  have hwidth : 0 <= (b - a) ^ 2 := by
    have hpow : (b - a) ^ 2 = (b - a) * (b - a) := by
      grind [Rat.pow_succ]
    rw [hpow]
    by_cases h : 0 <= b - a
    · exact Rat.mul_nonneg h h
    · have hneg : 0 <= -(b - a) := by grind
      have hsq := Rat.mul_nonneg hneg hneg
      simpa [Rat.mul_neg, Rat.neg_mul, Rat.neg_neg] using hsq
  have hden : 0 < (n : Rat) := (Rat.natCast_pos).2 hn
  have hterm : 0 <= (b - a) ^ 2 / (n : Rat) := by
    rw [Rat.div_def]
    exact Rat.mul_nonneg hwidth
      (Rat.le_of_lt ((Rat.inv_pos).2 hden))
  have hdiff :
      ((b ^ 2 - a ^ 2) - (b - a) ^ 2 / (n : Rat)) -
        (b * b - a * a) = -((b - a) ^ 2 / (n : Rat)) := by
    grind [Rat.sub_eq_add_neg, Rat.pow_succ]
  rw [hdiff]
  unfold qabs
  by_cases hzero : (b - a) ^ 2 / (n : Rat) = 0
  · simp [hzero]
  · rw [if_pos (by grind : -((b - a) ^ 2 / (n : Rat)) < 0)]
    grind

/-! The cubic rung has the same status, but its finite left-rectangle error
has the next explicit polynomial numerator.  This is still a rational
identity; no assertion about an infinite sum is involved. -/
theorem ftcErrorExact_cube_threeSquare_unit_of_pos
    {n : Nat} (hn : 0 < n) :
    ftcErrorExact cube (fun x => 3 * x ^ 2) 0 1 n =
      (3 * (n : Rat) - 1) / (2 * (n : Rat) ^ 2) := by
  unfold ftcErrorExact cube
  rw [riemannLeftExact_threeSquare_unit_of_pos hn]
  have hN : (n : Rat) ≠ 0 :=
    Rat.ne_of_gt ((Rat.natCast_pos).2 hn)
  have hformula :
      3 * (1 / (n : Rat)) ^ 3 *
          (((n : Rat) * ((n : Rat) - 1) *
            (2 * (n : Rat) - 1)) / 6) -
        (1 ^ 3 - 0 ^ 3) =
        -((3 * (n : Rat) - 1) / (2 * (n : Rat) ^ 2)) := by
    grind [Rat.div_def, Rat.pow_succ, Rat.mul_assoc, Rat.mul_comm,
      Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg,
      Rat.mul_inv_cancel]
  rw [hformula]
  have hnum : 0 <= 3 * (n : Rat) - 1 := by
    have hnone : (1 : Rat) <= (n : Rat) := by
      exact_mod_cast (Nat.one_le_iff_ne_zero.mpr (Nat.ne_of_gt hn))
    grind
  have hdenpos : 0 < 2 * (n : Rat) ^ 2 := by
    have hsq : 0 < (n : Rat) ^ 2 := by
      rw [show (n : Rat) ^ 2 = (n : Rat) * (n : Rat) by
        grind [Rat.pow_succ]]
      exact Rat.mul_pos ((Rat.natCast_pos).2 hn)
        ((Rat.natCast_pos).2 hn)
    exact Rat.mul_pos (by decide +kernel) hsq
  have hterm : 0 <= (3 * (n : Rat) - 1) / (2 * (n : Rat) ^ 2) := by
    rw [Rat.div_def]
    exact Rat.mul_nonneg hnum (Rat.le_of_lt ((Rat.inv_pos).2 hdenpos))
  unfold qabs
  by_cases hzero : (3 * (n : Rat) - 1) / (2 * (n : Rat) ^ 2) = 0
  · simp [hzero]
  · rw [if_pos (by grind :
      -((3 * (n : Rat) - 1) / (2 * (n : Rat) ^ 2)) < 0)]
    grind

theorem affine_derivative_effective (m c : Rat) :
    Nonempty (EffectiveDerivativeExact (affine m c) (constant m)) :=
  ⟨affineDerivative m c⟩

/-- Effective derivative of `x^2`:
the finite-difference quotient is exactly `2x + h`, hence it is within `eps`
of `2x` whenever `0 < h <= eps`. -/
def squareDerivative : EffectiveDerivativeExact square doubleId where
  stepRadius := fun eps => eps
  good := by
    intro x h eps hhpos hhle
    unfold square doubleId qabs
    have hcalc :
        (((x + h) * (x + h) - x * x) / h - 2 * x) = h := by
      rw [Rat.div_def]
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc, Rat.add_comm,
        Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
    rw [hcalc]
    have hnot : ¬ h < 0 := by grind
    simp [hnot]
    exact hhle

theorem square_derivative_effective :
    Nonempty (EffectiveDerivativeExact square doubleId) :=
  ⟨squareDerivative⟩

/-! A first nonlinear FTC instance.  On `[0,1]`, the left rectangles for
`2*x` miss the exact area under the square primitive by precisely `1/n`.
Choosing the denominator of the requested rational precision therefore gives
an explicit finite certificate of the integral, with no completeness axiom. -/
def squareFTCExactUnit :
    EffectiveFTCExact square doubleId 0 1 where
  derivative := squareDerivative
  chooseN := fun eps => eps.val.den + 1
  good := by
    intro eps
    let n : Nat := eps.val.den + 1
    have hn : 0 < n := by
      dsimp [n]
      omega
    unfold ftcErrorExact
    change qabs
      (riemannLeftExact (fun x => 2 * x) 0 1 n -
        (square 1 - square 0)) <= eps.val
    rw [riemannLeftExact_doubleId_of_pos hn]
    unfold square
    have hcalc :
        (1 ^ 2 - 0 ^ 2 - (1 - 0) ^ 2 / (n : Rat) -
          (1 * 1 - 0 * 0)) = -(1 / (n : Rat)) := by
      grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.div_def,
        Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
    rw [hcalc]
    have hposinv : 0 < 1 / (n : Rat) := by
      simpa [Rat.div_def] using
        ((Rat.inv_pos).2 ((Rat.natCast_pos).2 hn))
    have hneg : -(1 / (n : Rat)) < 0 := by grind
    have habs : qabs (-(1 / (n : Rat))) = 1 / (n : Rat) := by
      unfold qabs
      rw [if_pos hneg]
      grind
    rw [habs]
    dsimp [n]
    exact one_div_den_succ_le_of_pos eps.property

/-- The exact rational difference quotient used by the finite product
identities below. -/
def differenceQuotient (f : Rat -> Rat) (x h : Rat) : Rat :=
  (f (x + h) - f x) / h

theorem differenceQuotient_add (f g : Rat -> Rat) {x h : Rat}
    (hh : h ≠ 0) :
    differenceQuotient (fun z => f z + g z) x h =
      differenceQuotient f x h + differenceQuotient g x h := by
  unfold differenceQuotient
  rw [Rat.div_def, Rat.div_def, Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
    Rat.mul_comm]

theorem differenceQuotient_scale (c : Rat) (f : Rat -> Rat) {x h : Rat}
    (hh : h ≠ 0) :
    differenceQuotient (fun z => c * f z) x h =
      c * differenceQuotient f x h := by
  unfold differenceQuotient
  rw [Rat.div_def, Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
    Rat.mul_comm]

/- A finite L'Hopital-style cancellation certificate: away from the common
zero `a`, the quotient of the factored numerator and denominator is the
derivative ratio at `a`, namely `2 * a / 1`, plus its exact linear remainder.
This is only a rational identity; it makes no assertion about a limit. -/
theorem quadratic_linear_factored_quotient_derivative_ratio
    {a x : Rat} (hx : x - a ≠ 0) :
    (x ^ 2 - a ^ 2) / (x - a) = (2 * a) / 1 + (x - a) := by
  rw [Rat.div_def]
  have hcancel : (x - a) * (x - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x - a) hx
  grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/- The cubic companion records the exact finite remainder after cancelling
the common linear factor.  It is the cubic L'Hopital-style certificate, not a
statement about a limiting quotient. -/
theorem cubic_linear_factored_quotient_derivative_ratio
    {a x : Rat} (hx : x - a ≠ 0) :
    (x ^ 3 - a ^ 3) / (x - a) =
      3 * a ^ 2 + 3 * a * (x - a) + (x - a) ^ 2 := by
  rw [Rat.div_def]
  have hcancel : (x - a) * (x - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x - a) hx
  grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/- A reusable finite cancellation certificate for a general factored
polynomial evaluator.  The factor `g` may be any rational function here,
and in particular may be a finite polynomial evaluator; the only required
side condition is that the displayed linear factor is nonzero.  This is an
exact rational identity, not a limit or a completed-real quotient theorem. -/
theorem factored_linear_quotient_cancel
    {a x : Rat} {g : Rat -> Rat} (hx : x - a ≠ 0) :
    ((x - a) * g x) / (x - a) = g x := by
  rw [Rat.div_def]
  have hcancel : (x - a) * (x - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x - a) hx
  grind [Rat.mul_assoc, Rat.mul_comm]

/- A two-function finite L'Hopital certificate: if numerator and denominator
share the same nonzero linear factor, their quotient is exactly the quotient
of the remaining rational evaluators.  The denominator remainder must also
be nonzero; this is the finite algebraic analogue of cancelling a common
vanishing factor before comparing derivative ratios. -/
theorem common_linear_factor_quotient_cancel
    {a x : Rat} {g h : Rat -> Rat}
    (hx : x - a ≠ 0) (hh : h x ≠ 0) :
    ((x - a) * g x) / ((x - a) * h x) = g x / h x := by
  have hscaled : (x - a) * h x ≠ 0 := by
    intro hzero
    rcases Rat.mul_eq_zero.mp hzero with hleft | hright
    · exact hx hleft
    · exact hh hright
  rw [Rat.div_def, Rat.div_def]
  have hcancel : (x - a) * (x - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x - a) hx
  have hscaled_inv : ((x - a) * h x)⁻¹ = (x - a)⁻¹ * (h x)⁻¹ := by
    rw [Rat.inv_mul_rev]
    grind [Rat.mul_comm]
  have hhc : h x * (h x)⁻¹ = 1 := Rat.mul_inv_cancel (h x) hh
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem affine_differenceQuotient {m c x h : Rat} (hh : h ≠ 0) :
    differenceQuotient (affine m c) x h = m := by
  unfold differenceQuotient affine
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/- The exact finite chain-rule analogue for an affine inner map.  The
composition is evaluated at rational points, and the inner difference
quotient is transported by its slope; the only side conditions are the
nonzero outer mesh and the nonzero affine slope.  This is a finite rational
identity, with no limit or completed-real interpretation. -/
theorem differenceQuotient_affine_comp
    (f : Rat -> Rat) {m c x h : Rat} (hm : m ≠ 0) (hh : h ≠ 0) :
    differenceQuotient (fun z => f (affine m c z)) x h =
      m * differenceQuotient f (affine m c x) (m * h) := by
  have hmh : m * h ≠ 0 := by
    intro hzero
    rcases Rat.mul_eq_zero.mp hzero with hmzero | hhzero
    · exact hm hmzero
    · exact hh hhzero
  unfold differenceQuotient affine
  rw [Rat.div_def, Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  have hmhcancel : (m * h) * (m * h)⁻¹ = 1 :=
    Rat.mul_inv_cancel (m * h) hmh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/-! The zero-slope case is not an analytic exception: the affine inner map is
constant, so its finite difference quotient is exactly zero.  Including it
gives one total finite chain-rule identity, while the nonzero-slope theorem
above remains the useful transport form for inverse-coordinate arguments. -/
theorem differenceQuotient_affine_comp_of_step
    (f : Rat -> Rat) {m c x h : Rat} (hh : h ≠ 0) :
    differenceQuotient (fun z => f (affine m c z)) x h =
      m * differenceQuotient f (affine m c x) (m * h) := by
  by_cases hm : m = 0
  · subst m
    simp [differenceQuotient, affine, Rat.div_def]
    grind
  · exact differenceQuotient_affine_comp f hm hh

/-! An affine reparametrization transports the finite left-rectangle sum
exactly.  This is the computational core of substitution: it is an identity
of rational folds, before any shrinking or abstract integral is introduced.
The identity is total in the slope; positivity is needed only later when the
affine map is required to preserve orientation. -/
theorem riemannLeftExact_affine_substitution
    (g : Rat -> Rat) {m c a b : Rat} (n : Nat) :
    riemannLeftExact (fun x => m * g (affine m c x)) a b n =
      riemannLeftExact g (affine m c a) (affine m c b) n := by
  have hmesh : ∀ q : Nat,
      mesh (affine m c a) (affine m c b) q = m * mesh a b q := by
    intro q
    by_cases hq : q = 0
    · simp [mesh, hq]
    · have hqr : (q : Rat) ≠ 0 := by
        exact Rat.ne_of_gt ((Rat.natCast_pos).2 (Nat.pos_of_ne_zero hq))
      unfold mesh affine
      rw [if_neg hq, if_neg hq, Rat.div_def, Rat.div_def]
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
        Rat.mul_comm, Rat.mul_inv_cancel]
  have hpoint : ∀ (q k : Nat),
      leftPoint (affine m c a) (affine m c b) q k =
        affine m c (leftPoint a b q k) := by
    intro q k
    unfold leftPoint
    rw [hmesh q]
    unfold affine
    grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm]
  have hsum : ∀ q : Nat,
      (List.range q).foldl
          (fun acc k => acc + mesh a b q * (m * g (affine m c (leftPoint a b q k)))) 0 =
        (List.range q).foldl
          (fun acc k => acc + mesh (affine m c a) (affine m c b) q *
            g (leftPoint (affine m c a) (affine m c b) q k)) 0 := by
    intro q
    have hfold : ∀ (xs : List Nat),
        (∀ k, k ∈ xs ->
          mesh a b q * (m * g (affine m c (leftPoint a b q k))) =
            mesh (affine m c a) (affine m c b) q *
              g (leftPoint (affine m c a) (affine m c b) q k)) ->
        ∀ acc : Rat,
          (xs.foldl
            (fun acc k => acc + mesh a b q *
              (m * g (affine m c (leftPoint a b q k)))) acc) =
          (xs.foldl
            (fun acc k => acc + mesh (affine m c a) (affine m c b) q *
              g (leftPoint (affine m c a) (affine m c b) q k)) acc) := by
      intro xs
      induction xs with
      | nil => intro _h acc; rfl
      | cons k ks ih =>
          intro hxs acc
          dsimp
          rw [hxs k (by simp)]
          exact ih (fun j hj => hxs j (by simp [hj])) _
    apply hfold (List.range q)
    intro k hk
    rw [hmesh q, hpoint q k]
    grind [Rat.mul_assoc, Rat.mul_comm]
  simpa [riemannLeftExact] using hsum n

/- A positive affine change of endpoint coordinates transports a finite
secant bracket.  The source bracket is stated at rational endpoints `a,b`,
while `hxa` and `hyb` identify those endpoints with the translated/scaled
coordinates `x,y`.  Thus this is an endpoint-level companion to
`secant_of_finite_derivative_bracket`, not a second mesh theorem. -/
theorem secant_bracket_affine_endpoint_transport
    {f : Rat -> Rat} {a b x y m c lower upper : Rat}
    (hm : 0 < m) (hab : b - a ≠ 0)
    (hxa : affine m c x = a) (hyb : affine m c y = b)
    (hbracket :
      lower <= differenceQuotient f a (b - a) /\
        differenceQuotient f a (b - a) <= upper) :
    m * lower <=
        differenceQuotient (fun z => f (affine m c z)) x (y - x) /\
      differenceQuotient (fun z => f (affine m c z)) x (y - x) <=
        m * upper := by
  have hmne : m ≠ 0 := Rat.ne_of_gt hm
  have hmstep : m * (y - x) = b - a := by
    unfold affine at hxa hyb
    grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg,
      Rat.add_assoc, Rat.add_comm, Rat.add_left_comm]
  have hstep : y - x ≠ 0 := by
    intro hzero
    apply hab
    rw [← hmstep, hzero, Rat.mul_zero]
  have htransport := differenceQuotient_affine_comp
    f (m := m) (c := c) (x := x) (h := y - x) hmne hstep
  rw [htransport, hmstep, hxa]
  have hnonneg : 0 <= m := Rat.le_of_lt hm
  constructor
  · exact (Rat.mul_le_mul_of_nonneg_left hbracket.1 hnonneg)
  · exact (Rat.mul_le_mul_of_nonneg_left hbracket.2 hnonneg)

theorem affine_root_of_nonzero_slope {m c : Rat} (hm : m ≠ 0) :
    affine m c (-c / m) = 0 := by
  unfold affine
  rw [Rat.div_def]
  have hcancel : m * m⁻¹ = 1 := Rat.mul_inv_cancel m hm
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem affine_root_between_of_sign_change
    {m c a b : Rat} (hmpos : 0 < m)
    (ha : affine m c a <= 0) (hb : 0 <= affine m c b) :
    a <= -c / m ∧ -c / m <= b ∧ affine m c (-c / m) = 0 := by
  have hma : m * a <= -c := by
    unfold affine at ha
    grind
  have hmb : -c <= m * b := by
    unfold affine at hb
    grind
  have hleft : a <= -c / m := by
    apply Rat.le_of_mul_le_mul_right (c := m)
    · calc
        a * m = m * a := by rw [Rat.mul_comm]
        _ <= -c := hma
        _ = (-c / m) * m := by
          rw [Rat.div_def]
          grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel,
            Rat.neg_mul]
    · exact hmpos
  have hright : -c / m <= b := by
    apply Rat.le_of_mul_le_mul_right (c := m)
    · calc
        (-c / m) * m = -c := by
          rw [Rat.div_def]
          grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel,
            Rat.neg_mul]
        _ <= m * b := hmb
        _ = b * m := by rw [Rat.mul_comm]
    · exact hmpos
  exact ⟨hleft, hright, affine_root_of_nonzero_slope (Rat.ne_of_gt hmpos)⟩

theorem affine_root_between_of_negative_sign_change
    {m c a b : Rat} (hmneg : m < 0)
    (ha : 0 <= affine m c a) (hb : affine m c b <= 0) :
    a <= -c / m ∧ -c / m <= b ∧ affine m c (-c / m) = 0 := by
  have hma : -m * a <= c := by
    unfold affine at ha
    grind
  have hmb : c <= -m * b := by
    unfold affine at hb
    grind
  have hpos : 0 < -m := by grind
  have hleft : a <= -c / m := by
    apply Rat.le_of_mul_le_mul_right (c := -m)
    · calc
        a * (-m) = -m * a := by rw [Rat.mul_comm]
        _ <= c := hma
        _ = (-c / m) * (-m) := by
          rw [Rat.div_def]
          have hmne : m ≠ 0 := Rat.ne_of_lt hmneg
          grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel,
            Rat.neg_mul]
    · exact hpos
  have hright : -c / m <= b := by
    apply Rat.le_of_mul_le_mul_right (c := -m)
    · calc
        (-c / m) * (-m) = c := by
          rw [Rat.div_def]
          have hmne : m ≠ 0 := Rat.ne_of_lt hmneg
          grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel,
            Rat.neg_mul]
        _ <= -m * b := hmb
        _ = b * (-m) := by rw [Rat.mul_comm]
    · exact hpos
  exact ⟨hleft, hright, affine_root_of_nonzero_slope (Rat.ne_of_lt hmneg)⟩

theorem cube_differenceQuotient {x h : Rat} (hh : h ≠ 0) :
    differenceQuotient cube x h = 3 * x ^ 2 + 3 * x * h + h ^ 2 := by
  unfold differenceQuotient cube
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.pow_succ, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem cube_midpoint_secant {a b : Rat} (hab : b - a ≠ 0) :
    differenceQuotient cube a (b - a) =
      3 * ((a + b) / 2) ^ 2 + (b - a) ^ 2 / 4 := by
  rw [cube_differenceQuotient hab]
  grind [Rat.div_def, Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
    Rat.pow_succ]

theorem quartic_differenceQuotient {x h : Rat} (hh : h ≠ 0) :
    differenceQuotient (fun z => z ^ 4) x h =
      4 * x ^ 3 + 6 * x ^ 2 * h + 4 * x * h ^ 2 + h ^ 3 := by
  unfold differenceQuotient
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.pow_succ, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem quartic_midpoint_secant {a b : Rat} (hab : b - a ≠ 0) :
    differenceQuotient (fun z => z ^ 4) a (b - a) =
      4 * ((a + b) / 2) ^ 3 + ((a + b) / 2) * (b - a) ^ 2 := by
  rw [quartic_differenceQuotient hab]
  grind [Rat.div_def, Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
    Rat.pow_succ]

theorem quintic_differenceQuotient {x h : Rat} (hh : h ≠ 0) :
    differenceQuotient (fun z => z ^ 5) x h =
      5 * x ^ 4 + 10 * x ^ 3 * h + 10 * x ^ 2 * h ^ 2 +
        5 * x * h ^ 3 + h ^ 4 := by
  unfold differenceQuotient
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.pow_succ, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem sextic_differenceQuotient {x h : Rat} (hh : h ≠ 0) :
    differenceQuotient (fun z => z ^ 6) x h =
      6 * x ^ 5 + 15 * x ^ 4 * h + 20 * x ^ 3 * h ^ 2 +
        15 * x ^ 2 * h ^ 3 + 6 * x * h ^ 4 + h ^ 5 := by
  unfold differenceQuotient
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.pow_succ, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem quintic_midpoint_secant {a b : Rat} (hab : b - a ≠ 0) :
    differenceQuotient (fun z => z ^ 5) a (b - a) =
      5 * ((a + b) / 2) ^ 4 +
        (5 / 2) * ((a + b) / 2) ^ 2 * (b - a) ^ 2 +
        (b - a) ^ 4 / 16 := by
  rw [quintic_differenceQuotient hab]
  grind [Rat.div_def, Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
    Rat.pow_succ]

theorem sextic_midpoint_secant {a b : Rat} (hab : b - a ≠ 0) :
    differenceQuotient (fun z => z ^ 6) a (b - a) =
      6 * ((a + b) / 2) ^ 5 +
        5 * ((a + b) / 2) ^ 3 * (b - a) ^ 2 +
        (3 / 8) * ((a + b) / 2) * (b - a) ^ 4 := by
  rw [sextic_differenceQuotient hab]
  grind [Rat.div_def, Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
    Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
    Rat.pow_succ]

theorem square_quotient_by_id {x : Rat} (hx : x ≠ 0) :
    square x / x = x := by
  unfold square
  rw [Rat.div_def]
  have hcancel : x * x⁻¹ = 1 := Rat.mul_inv_cancel x hx
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem cube_quotient_by_id {x : Rat} (hx : x ≠ 0) :
    cube x / x = x ^ 2 := by
  unfold cube
  rw [Rat.div_def]
  have hcancel : x * x⁻¹ = 1 := Rat.mul_inv_cancel x hx
  grind [Rat.pow_succ, Rat.mul_assoc, Rat.mul_comm]

theorem power_succ_quotient_by_id (n : Nat) {x : Rat} (hx : x ≠ 0) :
    x ^ (n + 1) / x = x ^ n := by
  rw [Rat.pow_succ, Rat.div_def]
  have hcancel : x * x⁻¹ = 1 := Rat.mul_inv_cancel x hx
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem power_succ_quotient_by_power (n : Nat) {x : Rat} (hx : x ≠ 0) :
    x ^ (n + 1) / x ^ n = x := by
  have hpow : x ^ n ≠ 0 := by
    induction n with
    | zero => simp
    | succ n ih =>
        rw [Rat.pow_succ]
        intro hzero
        rcases Rat.mul_eq_zero.mp hzero with hleft | hright
        · exact ih hleft
        · exact hx hright
  rw [Rat.pow_succ, Rat.div_def]
  have hcancel : x ^ n * (x ^ n)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x ^ n) hpow
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem power_add_quotient_by_power (m n : Nat) {x : Rat} (hx : x ≠ 0) :
    x ^ (m + n) / x ^ m = x ^ n := by
  have hpow : x ^ m ≠ 0 := by
    induction m with
    | zero => simp
    | succ m ih =>
        rw [Rat.pow_succ]
        intro hzero
        rcases Rat.mul_eq_zero.mp hzero with hleft | hright
        · exact ih hleft
        · exact hx hright
  have hpowadd : x ^ (m + n) = x ^ m * x ^ n := by
    induction n with
    | zero => simp
    | succ n ih =>
        rw [show m + (n + 1) = m + n + 1 by omega,
          Rat.pow_succ, ih, Rat.pow_succ]
        grind [Rat.mul_assoc, Rat.mul_comm]
  rw [hpowadd, Rat.div_def]
  have hcancel : x ^ m * (x ^ m)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x ^ m) hpow
  grind [Rat.mul_assoc, Rat.mul_comm]

/-! Scalar-weighted form of the same finite cancellation. -/

theorem mul_power_add_quotient_by_power (y : Rat) (m n : Nat)
    {x : Rat} (hx : x ≠ 0) :
    (y * x ^ (m + n)) / x ^ m = y * x ^ n := by
  have hpow : x ^ m ≠ 0 := by
    induction m with
    | zero => simp
    | succ m ih =>
        rw [Rat.pow_succ]
        intro hzero
        rcases Rat.mul_eq_zero.mp hzero with hleft | hright
        · exact ih hleft
        · exact hx hright
  have hpowadd : x ^ (m + n) = x ^ m * x ^ n := by
    induction n with
    | zero => simp
    | succ n ih =>
        rw [show m + (n + 1) = m + n + 1 by omega,
          Rat.pow_succ, ih, Rat.pow_succ]
        grind [Rat.mul_assoc, Rat.mul_comm]
  rw [hpowadd, Rat.div_def]
  have hcancel : x ^ m * (x ^ m)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x ^ m) hpow
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem mul_power_add_quotient_by_scaled_power
    (y z : Rat) (m n : Nat) {x : Rat} (hx : x ≠ 0) (hz : z ≠ 0) :
    (y * x ^ (m + n)) / (z * x ^ m) = (y / z) * x ^ n := by
  have hpow : x ^ m ≠ 0 := by
    induction m with
    | zero => simp
    | succ m ih =>
        rw [Rat.pow_succ]
        intro hzero
        rcases Rat.mul_eq_zero.mp hzero with hleft | hright
        · exact ih hleft
        · exact hx hright
  have hpowadd : x ^ (m + n) = x ^ m * x ^ n := by
    induction n with
    | zero => simp
    | succ n ih =>
        rw [show m + (n + 1) = m + n + 1 by omega,
          Rat.pow_succ, ih, Rat.pow_succ]
        grind [Rat.mul_assoc, Rat.mul_comm]
  have hscaled : z * x ^ m ≠ 0 := by
    intro hzero
    rcases Rat.mul_eq_zero.mp hzero with hleft | hright
    · exact hz hleft
    · exact hpow hright
  rw [hpowadd, Rat.div_def, Rat.div_def]
  have hcancel : x ^ m * (x ^ m)⁻¹ = 1 :=
    Rat.mul_inv_cancel (x ^ m) hpow
  have hzcancel : z * z⁻¹ = 1 := Rat.mul_inv_cancel z hz
  have hscaled_inv : (z * x ^ m)⁻¹ = z⁻¹ * (x ^ m)⁻¹ := by
    rw [Rat.inv_mul_rev]
    grind [Rat.mul_comm]
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem square_midpoint_mean_value {a b : Rat} (hab : b - a ≠ 0) :
    differenceQuotient square a (b - a) = 2 * ((a + b) / 2) := by
  unfold differenceQuotient square
  rw [Rat.div_def]
  have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (b - a) hab
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

theorem quadratic_midpoint_mean_value
    (c₀ c₁ c₂ a b : Rat) (hab : b - a ≠ 0) :
    differenceQuotient (fun z => c₀ + c₁ * z + c₂ * z * z) a (b - a) =
      c₁ + 2 * c₂ * ((a + b) / 2) := by
  unfold differenceQuotient
  rw [Rat.div_def]
  have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
    Rat.mul_inv_cancel (b - a) hab
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/- A finite mean-value certificate for the cubic on a nonnegative interval.
The secant quotient is trapped between the endpoint derivatives; this is an
explicit rational inequality, not an appeal to an attained intermediate
point or to a completed real interval. -/
theorem cube_secant_derivative_bracket {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (hne : b - a ≠ 0) :
    3 * a * a <= differenceQuotient cube a (b - a) /\
      differenceQuotient cube a (b - a) <= 3 * b * b := by
  have hcalc :
      differenceQuotient cube a (b - a) = a * a + a * b + b * b := by
    unfold differenceQuotient cube
    rw [Rat.div_def]
    have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
      Rat.mul_inv_cancel (b - a) hne
    grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
  rw [hcalc]
  have hba : 0 <= b - a := by grind
  have hb : 0 <= b := by grind
  have hleft : 0 <= b + 2 * a := by grind
  have hright : 0 <= 2 * b + a := by grind
  have hleftprod : 0 <= (b - a) * (b + 2 * a) :=
    Rat.mul_nonneg hba hleft
  have hrightprod : 0 <= (b - a) * (2 * b + a) :=
    Rat.mul_nonneg hba hright
  constructor
  · grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm]
  · grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm]

/-- A pointwise computable MVT witness for the cubic.

The witness is supplied as a rational `t`; the only equation to check is that
the cubic secant slope agrees with the derivative value `3 * t^2`.  This is
the project-style replacement for asserting an existential intermediate real
point: the interval location and the secant identity are both finite data. -/
theorem cube_secant_supplied_mvt_witness {a b t : Rat}
    (hab : a < b) (hat : a < t) (htb : t < b)
    (hsec : a * a + a * b + b * b = 3 * t * t) :
    a < t /\ t < b /\
      differenceQuotient cube a (b - a) = 3 * t * t := by
  have hne : b - a ≠ 0 := by
    exact Rat.ne_of_gt (by grind)
  have hcalc :
      differenceQuotient cube a (b - a) = a * a + a * b + b * b := by
    unfold differenceQuotient cube
    rw [Rat.div_def]
    have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
      Rat.mul_inv_cancel (b - a) hne
    grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
  exact ⟨hat, htb, hcalc.trans hsec⟩

/- A finite mean-value certificate for the square on a nonnegative interval.
The secant quotient is trapped between the endpoint derivatives by the
identity `(b^2 - a^2) / (b - a) = a + b`; all quantities remain rational and
finite. -/
theorem square_secant_derivative_bracket {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (hne : b - a ≠ 0) :
    2 * a <= differenceQuotient square a (b - a) /\
      differenceQuotient square a (b - a) <= 2 * b := by
  have hcalc :
      differenceQuotient square a (b - a) = a + b := by
    unfold differenceQuotient square
    rw [Rat.div_def]
    have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
      Rat.mul_inv_cancel (b - a) hne
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
      Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
  rw [hcalc]
  have hb : 0 <= b := by grind
  constructor <;> grind

/- A finite mean-value certificate for the quartic on a nonnegative interval.
The secant quotient is trapped between the endpoint derivatives by two
explicit factorizations; this records the finite certificate without
selecting an intermediate real point. -/
theorem quartic_secant_derivative_bracket {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (hne : b - a ≠ 0) :
    4 * a ^ 3 <= differenceQuotient (fun z => z ^ 4) a (b - a) /\
      differenceQuotient (fun z => z ^ 4) a (b - a) <= 4 * b ^ 3 := by
  have hcalc :
      differenceQuotient (fun z => z ^ 4) a (b - a) =
        a ^ 3 + a ^ 2 * b + a * b ^ 2 + b ^ 3 := by
    unfold differenceQuotient
    rw [Rat.div_def]
    have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
      Rat.mul_inv_cancel (b - a) hne
    grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
  rw [hcalc]
  have hba : 0 <= b - a := by grind
  have hb : 0 <= b := by grind
  have hleft : 0 <= b ^ 2 + 2 * a * b + 3 * a ^ 2 := by
    have hbsq : 0 <= b ^ 2 := Rat.pow_nonneg hb
    have habprod : 0 <= a * b := Rat.mul_nonneg ha hb
    have hasq : 0 <= a ^ 2 := Rat.pow_nonneg ha
    have htwoprod : 0 <= 2 * a * b := by
      have htwoprod' : 0 <= 2 * (a * b) :=
        Rat.mul_nonneg (by grind) habprod
      grind [Rat.mul_assoc]
    have hthreesq : 0 <= 3 * a ^ 2 :=
      Rat.mul_nonneg (by grind) hasq
    exact Rat.add_nonneg (Rat.add_nonneg hbsq htwoprod) hthreesq
  have hright : 0 <= 3 * b ^ 2 + 2 * a * b + a ^ 2 := by
    have hbsq : 0 <= b ^ 2 := Rat.pow_nonneg hb
    have habprod : 0 <= a * b := Rat.mul_nonneg ha hb
    have hasq : 0 <= a ^ 2 := Rat.pow_nonneg ha
    have threebsq : 0 <= 3 * b ^ 2 :=
      Rat.mul_nonneg (by grind) hbsq
    have htwoprod : 0 <= 2 * a * b := by
      have htwoprod' : 0 <= 2 * (a * b) :=
        Rat.mul_nonneg (by grind) habprod
      grind [Rat.mul_assoc]
    exact Rat.add_nonneg (Rat.add_nonneg threebsq htwoprod) hasq
  have hleftprod :
      0 <= (b - a) * (b ^ 2 + 2 * a * b + 3 * a ^ 2) :=
    Rat.mul_nonneg hba hleft
  have hrightprod :
      0 <= (b - a) * (3 * b ^ 2 + 2 * a * b + a ^ 2) :=
    Rat.mul_nonneg hba hright
  constructor <;> grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add,
    Rat.add_mul, Rat.mul_assoc, Rat.mul_comm]

/- The finite kernel for the secant of the monomial `x^(n+1)`.  It is
defined by the same recurrence as the finite factorization quotient, so its
use below stays entirely within rational arithmetic. -/
def monomialSecantKernel (a b : Rat) : Nat -> Rat
  | 0 => 1
  | n + 1 => a ^ (n + 1) + b * monomialSecantKernel a b n

private theorem monomial_power_mono_nonneg {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (n : Nat) :
    a ^ n <= b ^ n := by
  induction n with
  | zero => simp
  | succ n ih =>
      rw [Rat.pow_succ, Rat.pow_succ]
      have hleft := Rat.mul_le_mul_of_nonneg_right ih ha
      have hb : 0 <= b := by grind
      have hbn : 0 <= b ^ n := Rat.pow_nonneg hb
      have hright := Rat.mul_le_mul_of_nonneg_left hab hbn
      exact Rat.le_trans hleft hright

private theorem monomialSecantKernel_factorization {a b : Rat} {n : Nat}
    (hne : b - a ≠ 0) :
    (b ^ (n + 1) - a ^ (n + 1)) / (b - a) =
      monomialSecantKernel a b n := by
  induction n with
  | zero =>
      unfold monomialSecantKernel
      rw [Rat.div_def]
      have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
        Rat.mul_inv_cancel (b - a) hne
      grind [Rat.sub_eq_add_neg]
  | succ n ih =>
      rw [show n + 1 + 1 = (n + 1) + 1 by omega,
        Rat.pow_succ, monomialSecantKernel]
      rw [Rat.div_def]
      have hcancel : (b - a) * (b - a)⁻¹ = 1 :=
        Rat.mul_inv_cancel (b - a) hne
      have hstep :
          (b ^ (n + 1) - a ^ (n + 1)) * (b - a)⁻¹ =
            monomialSecantKernel a b n := by
        simpa [Rat.div_def] using ih
      grind [Rat.sub_eq_add_neg, Rat.pow_succ, Rat.mul_add, Rat.add_mul,
        Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

private theorem monomialSecantKernel_lower {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (n : Nat) :
    (n + 1 : Rat) * a ^ n <= monomialSecantKernel a b n := by
  induction n with
  | zero =>
      unfold monomialSecantKernel
      grind
  | succ n ih =>
      rw [monomialSecantKernel]
      have hb : 0 <= b := by grind
      have hpow : 0 <= a ^ n := Rat.pow_nonneg ha
      have hstep : a ^ n * a <= a ^ n * b :=
        Rat.mul_le_mul_of_nonneg_left hab hpow
      have hscaled :
          (n + 1 : Rat) * (a ^ n * a) <=
            (n + 1 : Rat) * (a ^ n * b) :=
        Rat.mul_le_mul_of_nonneg_left hstep (by grind)
      have hihb :
          (n + 1 : Rat) * (a ^ n * b) <=
            b * monomialSecantKernel a b n := by
        have hmul := Rat.mul_le_mul_of_nonneg_left ih hb
        grind [Rat.mul_assoc, Rat.mul_comm]
      rw [Rat.pow_succ]
      calc
        (↑(n + 1) + 1) * (a ^ n * a) <=
            (n + 1 : Rat) * (a ^ n * b) + a ^ n * a := by
              grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_add, Rat.add_mul]
        _ <= b * monomialSecantKernel a b n + a ^ n * a :=
              (Rat.add_le_add_right).2 hihb
        _ = a ^ n * a + b * monomialSecantKernel a b n := by
              grind [Rat.add_comm]

private theorem monomialSecantKernel_upper {a b : Rat}
    (ha : 0 <= a) (hab : a <= b) (n : Nat) :
    monomialSecantKernel a b n <= (n + 1 : Rat) * b ^ n := by
  induction n with
  | zero =>
      unfold monomialSecantKernel
      grind
  | succ n ih =>
      rw [monomialSecantKernel]
      have hb : 0 <= b := by grind
      have hpow : 0 <= b ^ n := Rat.pow_nonneg hb
      have hstep : a ^ (n + 1) <= b ^ (n + 1) :=
        monomial_power_mono_nonneg ha hab (n + 1)
      have hscaled := Rat.mul_le_mul_of_nonneg_left ih hb
      have hstep' : a ^ n * a <= b ^ (n + 1) := by
        simpa [Rat.pow_succ] using hstep
      rw [Rat.pow_succ]
      calc
        a ^ n * a + b * monomialSecantKernel a b n <=
            b ^ (n + 1) + b * monomialSecantKernel a b n :=
              (Rat.add_le_add_right).2 hstep'
        _ <= b ^ (n + 1) + b * ((n + 1 : Rat) * b ^ n) :=
              (Rat.add_le_add_left).2 hscaled
        _ = (↑(n + 1) + 1) * b ^ (n + 1) := by
              rw [Rat.pow_succ]
              grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_add, Rat.add_mul]

/-- A finite monomial mean-value bracket.  For a nonnegative rational
interval `[a,b]`, the secant quotient of `x^(n+1)` is bounded by the two
endpoint finite-power derivatives `(n+1)*a^n` and `(n+1)*b^n`.

The proof is a finite factorization and positivity induction: it selects no
intermediate point and assumes neither a limit nor completeness. -/
theorem monomial_succ_secant_derivative_bracket {a b : Rat} (n : Nat)
    (ha : 0 <= a) (hab : a <= b) (hne : b - a ≠ 0) :
    (n + 1 : Rat) * a ^ n <=
        differenceQuotient (fun z => z ^ (n + 1)) a (b - a) /\
      differenceQuotient (fun z => z ^ (n + 1)) a (b - a) <=
        (n + 1 : Rat) * b ^ n := by
  have hfactor :=
    monomialSecantKernel_factorization (a := a) (b := b) (n := n) hne
  have hkernelLower := monomialSecantKernel_lower ha hab n
  have hkernelUpper := monomialSecantKernel_upper ha hab n
  have hquotient :
      differenceQuotient (fun z => z ^ (n + 1)) a (b - a) =
        monomialSecantKernel a b n := by
    unfold differenceQuotient
    have habsum : a + (b - a) = b := by grind
    rw [habsum]
    exact hfactor
  rw [hquotient]
  exact ⟨hkernelLower, hkernelUpper⟩

/- A finite mesh transport for a mean-value-style certificate.  Each cell
supplies a rational bracket for its forward secant (the finite derivative
certificate), and telescoping transports the common bracket to the whole
endpoint secant.  The endpoint relation and positive mesh width are explicit;
no intermediate point, limit, or completeness principle is used. -/
theorem secant_of_finite_derivative_bracket
    {f : Rat -> Rat} {a b h lower upper : Rat} {n : Nat}
    (hn : 0 < n) (hh : 0 < h)
    (hend : b = a + (n : Rat) * h)
    (hcell : ∀ k : Nat, k < n →
      lower <= differenceQuotient f (a + (k : Rat) * h) h /\
        differenceQuotient f (a + (k : Rat) * h) h <= upper) :
    lower <= differenceQuotient f a (b - a) /\
      differenceQuotient f a (b - a) <= upper := by
  have hmesh : ∀ m : Nat,
      m <= n ->
      lower * (m : Rat) * h <= f (a + (m : Rat) * h) - f a /\
        f (a + (m : Rat) * h) - f a <= upper * (m : Rat) * h := by
    intro m
    induction m with
    | zero =>
        intro _
        constructor <;> grind
    | succ m ih =>
        intro hm
        have hlocal := hcell m (by omega)
        have hprev := ih (by omega)
        unfold differenceQuotient at hlocal
        have hstep :
            (a + (↑m : Rat) * h) + h = a + (↑(m + 1) : Rat) * h := by
          rw [Rat.natCast_add]
          grind [Rat.mul_add, Rat.add_mul, Rat.add_assoc, Rat.add_comm,
            Rat.mul_assoc, Rat.mul_comm]
        rw [hstep] at hlocal
        constructor
        · have hscaled := Rat.mul_le_mul_of_nonneg_right hlocal.1
            (Rat.le_of_lt hh)
          rw [Rat.div_def] at hscaled
          have hcancel : h⁻¹ * h = 1 := Rat.inv_mul_cancel _
            (Rat.ne_of_gt hh)
          have hinc :
              lower * h <=
                f (a + (↑(m + 1) : Rat) * h) - f (a + (↑m : Rat) * h) := by
            calc
              lower * h <=
                  (f (a + (↑(m + 1) : Rat) * h) -
                    f (a + (↑m : Rat) * h)) * h⁻¹ * h := hscaled
              _ = f (a + (↑(m + 1) : Rat) * h) -
                    f (a + (↑m : Rat) * h) := by
                rw [Rat.mul_assoc, hcancel, Rat.mul_one]
          have hadd := rat_add_le_add hprev.1 hinc
          rw [Rat.natCast_add]
          grind [Rat.mul_add, Rat.add_mul, Rat.add_assoc, Rat.add_comm,
            Rat.mul_assoc, Rat.mul_comm]
        · have hscaled := Rat.mul_le_mul_of_nonneg_right hlocal.2
            (Rat.le_of_lt hh)
          rw [Rat.div_def] at hscaled
          have hcancel : h⁻¹ * h = 1 := Rat.inv_mul_cancel _
            (Rat.ne_of_gt hh)
          have hinc :
              f (a + (↑(m + 1) : Rat) * h) - f (a + (↑m : Rat) * h) <=
                upper * h := by
            calc
              f (a + (↑(m + 1) : Rat) * h) -
                    f (a + (↑m : Rat) * h) =
                  (f (a + (↑(m + 1) : Rat) * h) -
                    f (a + (↑m : Rat) * h)) * h⁻¹ * h := by
                rw [Rat.mul_assoc, hcancel, Rat.mul_one]
              _ <= upper * h := hscaled
          have hadd := rat_add_le_add hprev.2 hinc
          rw [Rat.natCast_add]
          grind [Rat.mul_add, Rat.add_mul, Rat.add_assoc, Rat.add_comm,
            Rat.mul_assoc, Rat.mul_comm]
  have hba : b - a = (n : Rat) * h := by grind
  rw [hba, differenceQuotient]
  have hmeshN := hmesh n (Nat.le_refl n)
  have hdenpos : 0 < (n : Rat) * h :=
    Rat.mul_pos ((Rat.natCast_pos).2 hn) hh
  rw [Rat.div_def]
  have hcancel : ((n : Rat) * h)⁻¹ * ((n : Rat) * h) = 1 :=
    Rat.inv_mul_cancel _ (Rat.ne_of_gt hdenpos)
  constructor
  · apply Rat.le_of_mul_le_mul_right (c := (n : Rat) * h)
    · rw [Rat.mul_assoc, hcancel]
      grind [hmeshN.1]
    · exact hdenpos
  · apply Rat.le_of_mul_le_mul_right (c := (n : Rat) * h)
    · rw [Rat.mul_assoc, hcancel]
      grind [hmeshN.2]
    · exact hdenpos

/- A generic finite bisection budget for rational brackets.  The denominator
is the exact number of subintervals after `n` halvings, so the statement is
an algorithmic termination/error certificate rather than a claim about a
completed limit or an attained root. -/
def rationalBisectionWidth (a b : Rat) (n : Nat) : Rat :=
  (b - a) / (((2 ^ n : Nat) : Rat))

theorem rationalBisectionWidth_le_error_budget
    {a b eps : Rat} {n : Nat}
    (hbudget : b - a <= eps * (((2 ^ n : Nat) : Rat))) :
    rationalBisectionWidth a b n <= eps := by
  unfold rationalBisectionWidth
  have hpowNat : 0 < 2 ^ n := Nat.pow_pos (by omega)
  have hpow : 0 < (((2 ^ n : Nat) : Rat)) :=
    (Rat.natCast_pos).2 hpowNat
  have hpowne : (((2 ^ n : Nat) : Rat)) ≠ 0 := Rat.ne_of_gt hpow
  apply Rat.le_of_mul_le_mul_right
    (c := (((2 ^ n : Nat) : Rat)))
  · rw [Rat.div_def, Rat.mul_assoc]
    have hcancel : (((2 ^ n : Nat) : Rat))⁻¹ *
        (((2 ^ n : Nat) : Rat)) = 1 := by
      rw [Rat.mul_comm]
      exact Rat.mul_inv_cancel _ hpowne
    rw [hcancel]
    simpa using hbudget
  · exact hpow

/-- The exact finite-difference product decomposition with the second factor
evaluated at the right endpoint.  This is the algebraic core of the product
rule before any continuity or limiting certificate is invoked. -/
theorem product_differenceQuotient_right
    (u v : Rat -> Rat) (x h : Rat) (hh : h ≠ 0) :
    (u (x + h) * v (x + h) - u x * v x) / h =
      u x * ((v (x + h) - v x) / h) +
        v (x + h) * ((u (x + h) - u x) / h) := by
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/-- The equivalent finite-difference product decomposition with both main
terms evaluated at the left endpoint.  The last term is the explicit corner
remainder which a constructive product-derivative proof must bound. -/
theorem product_differenceQuotient_corner
    (u v : Rat -> Rat) (x h : Rat) (hh : h ≠ 0) :
    (u (x + h) * v (x + h) - u x * v x) / h =
      u x * ((v (x + h) - v x) / h) +
        v x * ((u (x + h) - u x) / h) +
          h * ((u (x + h) - u x) / h) *
            ((v (x + h) - v x) / h) := by
  rw [Rat.div_def]
  have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

/-- The finite product-rule error is bounded by the two supplied
difference-quotient errors and one explicit corner remainder.  This is a
rational inequality, before it is lifted to interval enclosures or any
continuity certificate. -/
theorem product_differenceQuotient_error_le_qabs
    (u du v dv : Rat -> Rat) (x h : Rat) (hh : h ≠ 0) :
    qabs (differenceQuotient (fun z => u z * v z) x h -
      (u x * dv x + v x * du x)) <=
      qabs (u x) * qabs (differenceQuotient v x h - dv x) +
        qabs (v x) * qabs (differenceQuotient u x h - du x) +
          qabs h * qabs (differenceQuotient u x h) *
            qabs (differenceQuotient v x h) := by
  have hdecomp :
      differenceQuotient (fun z => u z * v z) x h -
          (u x * dv x + v x * du x) =
        u x * (differenceQuotient v x h - dv x) +
          v x * (differenceQuotient u x h - du x) +
            h * differenceQuotient u x h * differenceQuotient v x h := by
    unfold differenceQuotient
    rw [product_differenceQuotient_corner u v x h hh]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
  rw [hdecomp]
  calc
    qabs
        (u x * (differenceQuotient v x h - dv x) +
          v x * (differenceQuotient u x h - du x) +
            h * differenceQuotient u x h * differenceQuotient v x h) <=
        qabs
          (u x * (differenceQuotient v x h - dv x) +
            v x * (differenceQuotient u x h - du x)) +
          qabs (h * differenceQuotient u x h * differenceQuotient v x h) :=
      qabs_add_le _ _
    _ <= (qabs (u x * (differenceQuotient v x h - dv x)) +
          qabs (v x * (differenceQuotient u x h - du x))) +
          qabs (h * differenceQuotient u x h * differenceQuotient v x h) :=
      (Rat.add_le_add_right).2 (qabs_add_le _ _)
    _ = qabs (u x) * qabs (differenceQuotient v x h - dv x) +
          qabs (v x) * qabs (differenceQuotient u x h - du x) +
            qabs h * qabs (differenceQuotient u x h) *
              qabs (differenceQuotient v x h) := by
      rw [qabs_mul, qabs_mul, qabs_mul, qabs_mul]

/-- The nonnegative-step form of the two-sided product-error estimate.  This
is convenient for forward mesh arguments, while the absolute-step theorem
above is the form used by the interval derivative interface. -/
theorem product_differenceQuotient_error_le
    (u du v dv : Rat -> Rat) (x h : Rat) (hh : h ≠ 0) (h0 : 0 <= h) :
    qabs (differenceQuotient (fun z => u z * v z) x h -
      (u x * dv x + v x * du x)) <=
      qabs (u x) * qabs (differenceQuotient v x h - dv x) +
        qabs (v x) * qabs (differenceQuotient u x h - du x) +
          h * qabs (differenceQuotient u x h) *
            qabs (differenceQuotient v x h) := by
  calc
    qabs (differenceQuotient (fun z => u z * v z) x h -
      (u x * dv x + v x * du x)) <=
        qabs (u x) * qabs (differenceQuotient v x h - dv x) +
          qabs (v x) * qabs (differenceQuotient u x h - du x) +
            qabs h * qabs (differenceQuotient u x h) *
              qabs (differenceQuotient v x h) :=
      product_differenceQuotient_error_le_qabs u du v dv x h hh
    _ = qabs (u x) * qabs (differenceQuotient v x h - dv x) +
          qabs (v x) * qabs (differenceQuotient u x h - du x) +
            h * qabs (differenceQuotient u x h) *
              qabs (differenceQuotient v x h) := by
      rw [qabs_eq_self_of_nonneg h0]
end ExactFunction

namespace QInterval

def scaleRat (r : Rat) (I : QInterval) : QInterval :=
  if 0 <= r then
    { lo := r * I.lo, hi := r * I.hi }
  else
    { lo := r * I.hi, hi := r * I.lo }

def neg (I : QInterval) : QInterval :=
  { lo := -I.hi, hi := -I.lo }

def sub (I J : QInterval) : QInterval :=
  { lo := I.lo - J.hi, hi := I.hi - J.lo }

def divRat (I : QInterval) (h : Rat) : QInterval :=
  scaleRat (1 / h) I

def differenceQuotient (fxh fx : QInterval) (h : Rat) : QInterval :=
  divRat (sub fxh fx) h

/-- A difference quotient of two ordered interval enclosures is itself an
ordered interval, for either sign of the rational step. -/
theorem differenceQuotient_ordered
    (fxh fx : QInterval)
    (hxh : fxh.lo <= fxh.hi) (hx : fx.lo <= fx.hi) (h : Rat) :
    (differenceQuotient fxh fx h).lo <=
      (differenceQuotient fxh fx h).hi := by
  have hsub : fxh.lo - fx.hi <= fxh.hi - fx.lo := by grind
  unfold differenceQuotient divRat sub scaleRat
  split
  · exact Rat.mul_le_mul_of_nonneg_left hsub ‹0 <= 1 / h›
  · have hinv : 1 / h <= 0 :=
      Rat.le_of_lt (Rat.not_le.mp ‹¬0 <= 1 / h›)
    exact rat_mul_le_mul_of_nonpos_left hsub hinv

/-- Refining both endpoint enclosures narrows their rational difference
quotient, including when the step is negative. -/
theorem differenceQuotient_contains_of_contains
    {A B A' B' : QInterval} (hA : A.ContainsInterval A')
    (hB : B.ContainsInterval B') (h : Rat) :
    (differenceQuotient B A h).ContainsInterval
      (differenceQuotient B' A' h) := by
  have hleft : B.lo - A.hi <= B'.lo - A'.hi := by
    rcases hA with ⟨_, ha⟩
    rcases hB with ⟨hb, _⟩
    grind
  have hright : B'.hi - A'.lo <= B.hi - A.lo := by
    rcases hA with ⟨ha, _⟩
    rcases hB with ⟨_, hb⟩
    grind
  unfold differenceQuotient divRat sub scaleRat
  split
  · exact ⟨Rat.mul_le_mul_of_nonneg_left hleft ‹0 <= 1 / h›,
      Rat.mul_le_mul_of_nonneg_left hright ‹0 <= 1 / h›⟩
  · have hn : 1 / h <= 0 :=
      Rat.le_of_lt (Rat.not_le.mp ‹¬0 <= 1 / h›)
    exact ⟨rat_mul_le_mul_of_nonpos_left hright hn,
      rat_mul_le_mul_of_nonpos_left hleft hn⟩

/-- Refining both intervals in a near pair costs at most three times the
original tolerance: the gap and both refined widths are each bounded by the
original near tolerance. -/
theorem nearAt_refine {A B A' B' : QInterval} {eps delta : QPos}
    (h : A.NearAt B eps) (hA : A.ContainsInterval A')
    (hB : B.ContainsInterval B')
    (ha : A'.lo <= A'.hi) (hb : B'.lo <= B'.hi)
    (hbudget : 3 * eps.val <= delta.val) : A'.NearAt B' delta := by
  rcases h with ⟨h1, h2, h3, h4⟩
  rcases hA with ⟨ha1, ha2⟩
  rcases hB with ⟨hb1, hb2⟩
  have he := eps.property
  unfold NearAt width at *
  constructor
  · grind
  constructor
  · grind
  constructor <;> grind

/-! Finite difference quotients distribute over interval addition.  This is
the interval counterpart of the exact rational identity above; the proof is
just endpoint arithmetic, with the sign split belonging to interval division.
No limiting argument is involved. -/
theorem differenceQuotient_addInterval
    (A B C D : QInterval) (h : Rat) :
    differenceQuotient (addInterval A B) (addInterval C D) h =
      addInterval (differenceQuotient A C h)
        (differenceQuotient B D h) := by
  by_cases hinv : 0 <= 1 / h
  · cases A
    cases B
    cases C
    cases D
    simp [differenceQuotient, divRat, sub, addInterval, scaleRat,
      Rat.div_def, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]
  · cases A
    cases B
    cases C
    cases D
    simp [differenceQuotient, divRat, sub, addInterval, scaleRat,
      Rat.div_def, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]

/-- Subtracting interval enclosures adds their widths exactly. -/
theorem sub_width (I J : QInterval) :
    (sub I J).width = I.width + J.width := by
  unfold sub width
  grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

/-- Nonnegative scaling preserves the exact width factor. -/
theorem scaleRat_width_of_nonneg {r : Rat} (hr : 0 <= r) (I : QInterval) :
    (scaleRat r I).width = r * I.width := by
  unfold scaleRat width
  rw [if_pos hr]
  grind [Rat.sub_eq_add_neg, Rat.mul_add]

/-- Nonnegative scaling preserves finite interval overlap. -/
theorem scaleRat_overlaps_of_nonneg {r : Rat} (hr : 0 <= r)
    {I J : QInterval} (hover : I.Overlaps J) :
    (scaleRat r I).Overlaps (scaleRat r J) := by
  unfold scaleRat QInterval.Overlaps
  simp only [if_pos hr]
  constructor
  · exact Rat.mul_le_mul_of_nonneg_left hover.1 hr
  · exact Rat.mul_le_mul_of_nonneg_left hover.2 hr

/-- Nonnegative scaling also preserves enclosure. -/
theorem scaleRat_contains_of_nonneg {r : Rat} (hr : 0 <= r)
    {outer inner : QInterval} (hcontains : outer.ContainsInterval inner) :
    (scaleRat r outer).ContainsInterval (scaleRat r inner) := by
  unfold scaleRat QInterval.ContainsInterval
  simp only [if_pos hr]
  constructor
  · exact Rat.mul_le_mul_of_nonneg_left hcontains.1 hr
  · exact Rat.mul_le_mul_of_nonneg_left hcontains.2 hr

theorem differenceQuotient_scaleRat_of_nonneg {r : Rat} (hr : 0 <= r)
    (A B : QInterval) (h : Rat) :
    differenceQuotient (scaleRat r A) (scaleRat r B) h =
      scaleRat r (differenceQuotient A B h) := by
  by_cases hinv : 0 <= 1 / h
  · cases A
    cases B
    simp [differenceQuotient, divRat, sub, scaleRat, Rat.div_def,
      if_pos hr, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]
  · cases A
    cases B
    simp [differenceQuotient, divRat, sub, scaleRat, Rat.div_def,
      if_pos hr, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]

theorem differenceQuotient_neg (A B : QInterval) (h : Rat) :
    differenceQuotient (neg A) (neg B) h =
      neg (differenceQuotient A B h) := by
  by_cases hinv : 0 <= 1 / h
  · cases A
    cases B
    simp [differenceQuotient, divRat, sub, neg, scaleRat,
      Rat.div_def, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]
  · cases A
    cases B
    simp [differenceQuotient, divRat, sub, neg, scaleRat,
      Rat.div_def, hinv]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm, Rat.add_assoc, Rat.add_comm]

/-! Negative scalar multiplication is reduced to the already-certified
nonnegative case plus endpoint negation.  Keeping this identity explicit
prevents a sign-sensitive interval multiplication from being hidden in a
later derivative proof. -/
theorem scaleRat_neg_eq_neg_scaleRat_neg {r : Rat} (hr : r < 0)
    (I : QInterval) :
    scaleRat r I = neg (scaleRat (-r) I) := by
  have hr0pos : 0 < -r := by
    simpa using (Rat.neg_lt_neg hr)
  have hr0 : 0 <= -r := Rat.le_of_lt hr0pos
  unfold scaleRat neg
  rw [if_neg (Rat.not_le.mpr hr),
    if_pos hr0]
  cases I
  dsimp
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
    Rat.mul_comm, Rat.add_comm, Rat.neg_mul, Rat.mul_neg, Rat.neg_neg]

theorem differenceQuotient_scaleRat_of_neg {r : Rat} (hr : r < 0)
    (A B : QInterval) (h : Rat) :
    differenceQuotient (scaleRat r A) (scaleRat r B) h =
      scaleRat r (differenceQuotient A B h) := by
  rw [scaleRat_neg_eq_neg_scaleRat_neg hr A,
    scaleRat_neg_eq_neg_scaleRat_neg hr B,
    differenceQuotient_neg]
  rw [differenceQuotient_scaleRat_of_nonneg (by grind : 0 <= -r)]
  exact (scaleRat_neg_eq_neg_scaleRat_neg hr
    (differenceQuotient A B h)).symm

/-- Dividing the difference of two exact singleton boxes gives the exact
rational difference quotient.  The sign split in interval division is harmless
here because both endpoints coincide. -/
theorem differenceQuotient_singleton
    (y x h : Rat) :
    differenceQuotient { lo := y, hi := y } { lo := x, hi := x } h =
      { lo := (y - x) / h, hi := (y - x) / h } := by
  unfold differenceQuotient divRat sub scaleRat
  simp [Rat.div_def, Rat.mul_comm]

/-! A positive cell width cancels the interval quotient denominator.  This is
the algebraic bridge used by the effective FTC: a finite secant enclosure can
be transported back to an endpoint-difference enclosure before the local
boxes are summed. -/

theorem scaleRat_differenceQuotient_of_pos
    {A B : QInterval} {h : Rat} (hpos : 0 < h) :
    scaleRat h (differenceQuotient B A h) = sub B A := by
  have hnonneg : 0 <= h := Rat.le_of_lt hpos
  have hne : h ≠ 0 := Rat.ne_of_gt hpos
  unfold differenceQuotient divRat scaleRat sub
  simp only [if_pos hnonneg]
  rw [if_pos]
  · simp only [Rat.div_def]
    have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hne
    grind [Rat.mul_assoc, Rat.mul_comm, Rat.sub_eq_add_neg]
  · exact by
      rw [Rat.div_def]
      exact Rat.mul_nonneg (by decide +kernel)
        (Rat.le_of_lt ((Rat.inv_pos).2 hpos))

theorem nearAt_symm {I J : QInterval} {eps : QPos} :
    I.NearAt J eps -> J.NearAt I eps := by
  intro h
  unfold NearAt at *
  rcases h with ⟨hIJ, hJI, hIw, hJw⟩
  exact ⟨hJI, hIJ, hJw, hIw⟩

/-! A near secant quotient gives a concrete scaled endpoint enclosure. -/

theorem scaleRat_differenceQuotient_contains_of_near
    {A B D : QInterval} {h : Rat} {eps : QPos}
    (hpos : 0 < h)
    (hnear : (differenceQuotient B A h).NearAt D eps) :
    (scaleRat h (expand D (2 * eps.val))).ContainsInterval (sub B A) := by
  have hnear' : D.NearAt (differenceQuotient B A h) eps :=
    nearAt_symm hnear
  have hcontains := expand_contains_right_of_near hnear'
  have hscaled := scaleRat_contains_of_nonneg
    (Rat.le_of_lt hpos) hcontains
  rw [scaleRat_differenceQuotient_of_pos hpos] at hscaled
  exact hscaled

/-- Reversing a positive finite step reverses both interval endpoints and the
sign of its denominator, leaving the enclosure of the difference quotient
unchanged.  This is the finite algebra needed to transport a forward
derivative certificate to a backward step. -/
theorem differenceQuotient_reverse_of_pos {A B : QInterval} {h : Rat}
    (hpos : 0 < h) :
    differenceQuotient B A (-h) = differenceQuotient A B h := by
  have hhne : h ≠ 0 := Rat.ne_of_gt hpos
  have hnegne : -h ≠ 0 := by grind
  have hinvpos' : 0 < h⁻¹ := (Rat.inv_pos).2 hpos
  have hinvneg_eq : (-h)⁻¹ = -h⁻¹ := by
    have hnegmul : (-h) * (-h⁻¹) = 1 := by
      have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hhne
      grind [Rat.mul_assoc, Rat.mul_comm]
    calc
      (-h)⁻¹ = (-h)⁻¹ * 1 := by grind
      _ = (-h)⁻¹ * ((-h) * (-h⁻¹)) := by rw [hnegmul]
      _ = ((-h)⁻¹ * (-h)) * (-h⁻¹) := by
        rw [Rat.mul_assoc]
      _ = 1 * (-h⁻¹) := by
        rw [Rat.inv_mul_cancel _ hnegne]
      _ = -h⁻¹ := by grind
  have hinvpos : 0 <= 1 / h := by
    rw [Rat.div_def]
    simpa using Rat.le_of_lt hinvpos'
  have hinvneg : ¬ 0 <= 1 / (-h) := by
    rw [Rat.div_def]
    rw [hinvneg_eq]
    apply Rat.not_le.mpr
    simpa using Rat.neg_lt_neg hinvpos'
  unfold differenceQuotient divRat sub scaleRat
  rw [if_neg hinvneg, if_pos hinvpos]
  rw [Rat.div_def, hinvneg_eq]
  cases A
  cases B
  dsimp
  congr 1 <;>
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm]

/-- A finite secant certificate can be converted directly into the endpoint
difference enclosure used by the FTC layer.  More precisely, if the interval
quotient over a positive rational step is near a derivative box, then the
endpoint difference lies in the step times that box widened by twice the
requested tolerance.  The second tolerance pays for the quotient box's own
width; no limiting or completeness principle is involved. -/
theorem scaleByRat_expand_contains_subInterval_of_differenceQuotient_near
    {A B D : QInterval} {h : Rat} {eps : QPos}
    (hpos : 0 < h)
    (hnear : (differenceQuotient B A h).NearAt D eps) :
    (scaleByRat h (expand D (2 * eps.val))).ContainsInterval
      (subInterval B A) := by
  have h0 : 0 <= h := Rat.le_of_lt hpos
  have hne : h ≠ 0 := Rat.ne_of_gt hpos
  have hinv : 0 <= 1 / h := by
    rw [Rat.div_def]
    simpa using Rat.le_of_lt ((Rat.inv_pos).2 hpos)
  have hcancel : h * (1 / h) = 1 := by
    simpa [Rat.div_def] using Rat.mul_inv_cancel h hne
  have hlo : (1 / h) * (B.lo - A.hi) <= D.hi + eps.val := by
    simpa [differenceQuotient, divRat, sub, scaleRat, if_pos hinv] using
      hnear.1
  have hDlo : D.lo <= (1 / h) * (B.hi - A.lo) + eps.val := by
    simpa [differenceQuotient, divRat, sub, scaleRat, if_pos hinv] using
      hnear.2.1
  have hwidth :
      (1 / h) * (B.hi - A.lo) - (1 / h) * (B.lo - A.hi) <= eps.val := by
    simpa [differenceQuotient, divRat, sub, scaleRat, if_pos hinv,
      QInterval.width] using hnear.2.2.1
  have hDlo' : D.lo - 2 * eps.val <= (1 / h) * (B.lo - A.hi) := by
    grind [Rat.sub_eq_add_neg]
  have hDhi' : (1 / h) * (B.hi - A.lo) <= D.hi + 2 * eps.val := by
    grind [Rat.sub_eq_add_neg]
  unfold ContainsInterval scaleByRat expand subInterval
  rw [if_pos h0]
  constructor
  · calc
      h * (D.lo - 2 * eps.val) <=
          h * ((1 / h) * (B.lo - A.hi)) :=
            Rat.mul_le_mul_of_nonneg_left hDlo' h0
      _ = B.lo - A.hi := by
            rw [← Rat.mul_assoc, hcancel]
            grind
  · calc
      B.hi - A.lo = h * ((1 / h) * (B.hi - A.lo)) := by
        rw [← Rat.mul_assoc, hcancel]
        grind
      _ <= h * (D.hi + 2 * eps.val) :=
            Rat.mul_le_mul_of_nonneg_left hDhi' h0

/-- Combine two finite nearness certificates into one derivative-bound box.

The first certificate places a positive-step secant near a derivative box;
the second places a candidate value near a possibly differently evaluated
base derivative box.  The hull of the two twice-widened boxes contains both
the candidate value and the scaled endpoint difference.  Its width is at
most ten times the requested tolerance.  This is the local algebra needed to
combine a step-aware derivative evaluator with a continuity evaluator before
forming a common FTC cell bound. -/
theorem common_secant_derivative_bound_of_near
    {A B secantDerivative baseDerivative candidateValue : QInterval}
    {h : Rat} {eps : QPos}
    (hpos : 0 < h)
    (hsecant :
      (differenceQuotient B A h).NearAt secantDerivative eps)
    (hvalue : baseDerivative.NearAt candidateValue eps)
    (hover : secantDerivative.Overlaps baseDerivative)
    (hsecantOrdered : 0 <= secantDerivative.width)
    (hbaseOrdered : 0 <= baseDerivative.width) :
    let bound :=
      hull (expand secantDerivative (2 * eps.val))
        (expand baseDerivative (2 * eps.val))
    bound.ContainsInterval candidateValue /\
      (scaleByRat h bound).ContainsInterval (subInterval B A) /\
        bound.width <= 10 * eps.val := by
  let left := expand secantDerivative (2 * eps.val)
  let right := expand baseDerivative (2 * eps.val)
  let bound := hull left right
  have hzero : 0 <= eps.val := Rat.le_of_lt eps.property
  have hvalueRight : right.ContainsInterval candidateValue := by
    dsimp [right]
    exact expand_contains_right_of_near hvalue
  have hboundRight : bound.ContainsInterval right := by
    dsimp [bound]
    exact hull_contains_right left right
  have hcandidate : bound.ContainsInterval candidateValue :=
    ⟨Rat.le_trans hboundRight.1 hvalueRight.1,
      Rat.le_trans hvalueRight.2 hboundRight.2⟩
  have hsecantLeft :
      (scaleByRat h left).ContainsInterval (subInterval B A) := by
    dsimp [left]
    exact scaleByRat_expand_contains_subInterval_of_differenceQuotient_near
      hpos hsecant
  have hboundLeft : bound.ContainsInterval left := by
    dsimp [bound]
    exact hull_contains_left left right
  have hscaledBound :
      (scaleByRat h bound).ContainsInterval (scaleByRat h left) :=
    scaleByRat_contains_of_nonneg (Rat.le_of_lt hpos) hboundLeft
  have hendpoint :
      (scaleByRat h bound).ContainsInterval (subInterval B A) :=
    ⟨Rat.le_trans hscaledBound.1 hsecantLeft.1,
      Rat.le_trans hsecantLeft.2 hscaledBound.2⟩
  have hleftOrdered : 0 <= left.width := by
    rw [show left = expand secantDerivative (2 * eps.val) by rfl,
      expand_width]
    grind [Rat.mul_nonneg]
  have hrightOrdered : 0 <= right.width := by
    rw [show right = expand baseDerivative (2 * eps.val) by rfl,
      expand_width]
    grind [Rat.mul_nonneg]
  have hleftRightOverlap : left.Overlaps right := by
    dsimp [left, right]
    unfold Overlaps at hover
    unfold Overlaps expand
    constructor <;> grind [Rat.sub_eq_add_neg]
  have hwidth :
      bound.width <= left.width + right.width := by
    dsimp [bound]
    exact hull_width_le_add_of_overlaps hleftOrdered hrightOrdered
      hleftRightOverlap
  have hwidthBound : bound.width <= 10 * eps.val := by
    calc
      bound.width <= left.width + right.width := hwidth
      _ = (secantDerivative.width + 2 * (2 * eps.val)) +
            (baseDerivative.width + 2 * (2 * eps.val)) := by
            rw [show left = expand secantDerivative (2 * eps.val) by rfl,
              show right = expand baseDerivative (2 * eps.val) by rfl,
              expand_width, expand_width]
      _ <= 10 * eps.val := by
            have hsecantWidth : secantDerivative.width <= eps.val :=
              hsecant.2.2.2
            have hbaseWidth : baseDerivative.width <= eps.val :=
              hvalue.2.2.1
            grind
  exact ⟨hcandidate, hendpoint, hwidthBound⟩

end QInterval

/-- Two identical exact singleton boxes are near at every requested precision.
This small lemma is the interval-valued replacement for treating a rational
calculation as an exact real value. -/
theorem intervalNearAtPrecision_singleton_self (q : Rat) (n : Nat) :
    intervalNearAtPrecision { lo := q, hi := q } { lo := q, hi := q } n := by
  unfold intervalNearAtPrecision QInterval.NearAt QInterval.width
  have heps : 0 <= (precisionAtStage n).val :=
    Rat.le_of_lt (precisionAtStage n).property
  constructor
  · grind
  constructor
  · grind
  constructor <;> grind [Rat.sub_eq_add_neg]

/-- Two interval functions represent the same function on the same rational
interval when all point-values overlap at every precision.

This is deliberately local to a chosen interval; raw partial functions with
different domains do not have a global transitive equivalence relation. -/
def FunctionOnInterval.Equivalent (f g : FunctionOnInterval) : Prop :=
  f.lower = g.lower /\
  f.upper = g.upper /\
  forall x
      (hxF : inDomainInterval f.lower f.upper x)
      (hxG : inDomainInterval g.lower g.upper x),
    (PartialRealFunRaw.apply f.raw f.valid_on x (f.defined_on x hxF)).Equiv
      (PartialRealFunRaw.apply g.raw g.valid_on x (g.defined_on x hxG))

/-- Arbitrarily close cofinal lower endpoints imply equality of represented
functions. This exposes the exact convergence step needed after a quantitative
mesh comparison: for each rational input and each pair of requested raw
stages, later mesh samples must be cofinal and their lower endpoints must be
arbitrarily close. -/
theorem FunctionOnInterval.equivalent_of_cofinal_lower_endpoint_closeness
    {f g : FunctionOnInterval}
    (hlower : f.lower = g.lower) (hupper : f.upper = g.upper)
    (hclose : forall x
      (hxF : inDomainInterval f.lower f.upper x)
      (hxG : inDomainInterval g.lower g.upper x)
      n m (eps : QPos),
      exists N M, n <= N /\ m <= M /\
        qabs
          (((PartialRealFunRaw.apply f.raw f.valid_on x (f.defined_on x hxF)).compute N).lo -
           ((PartialRealFunRaw.apply g.raw g.valid_on x (g.defined_on x hxG)).compute M).lo)
          <= eps.val) :
    FunctionOnInterval.Equivalent f g := by
  refine ⟨hlower, hupper, ?_⟩
  intro x hxF hxG
  have hFvalid :
      (PartialRealFunRaw.apply f.raw f.valid_on x (f.defined_on x hxF)).Valid :=
    f.valid_on x (f.defined_on x hxF)
  have hGvalid :
      (PartialRealFunRaw.apply g.raw g.valid_on x (g.defined_on x hxG)).Valid :=
    g.valid_on x (g.defined_on x hxG)
  apply RealCompute.equiv_of_cofinal_lower_endpoint_closeness
    hFvalid hGvalid
  intro n m eps
  obtain ⟨N, M, hnN, hmM, hsample⟩ := hclose x hxF hxG n m eps
  exact ⟨N, M, hnN, hmM, hsample⟩

namespace FunctionOnInterval

/-! Equivalence edges form the local representation graph for a function.
These laws are proved at the `realCompute` level, so a chain of different native
stage schedules can be composed without selecting a completed function. -/

theorem equivalent_refl (f : FunctionOnInterval) :
    Equivalent f f := by
  refine ⟨rfl, rfl, ?_⟩
  intro x hxF hxG
  exact RealCompute.equiv_refl
    (PartialRealFunRaw.apply f.raw f.valid_on x (f.defined_on x hxF))
    (f.valid_on x (f.defined_on x hxF))

theorem equivalent_symm {f g : FunctionOnInterval}
    (h : Equivalent f g) : Equivalent g f := by
  refine ⟨h.1.symm, h.2.1.symm, ?_⟩
  intro x hxG hxF
  have hfg := h.2.2 x hxF hxG
  exact RealCompute.equiv_symm hfg

theorem equivalent_trans {f g h : FunctionOnInterval}
    (hfg : Equivalent f g) (hgh : Equivalent g h) :
    Equivalent f h := by
  refine ⟨hfg.1.trans hgh.1, hfg.2.1.trans hgh.2.1, ?_⟩
  intro x hxF hxH
  have hxG : inDomainInterval g.lower g.upper x := by
    simpa [← hfg.1, ← hfg.2.1] using hxF
  have hFvalid :
      (PartialRealFunRaw.apply f.raw f.valid_on x
        (f.defined_on x hxF)).Valid := by
    change RealCompute.ValidCompute (f.raw.compute x (f.defined_on x hxF))
    exact f.valid_on x (f.defined_on x hxF)
  have hGvalid :
      (PartialRealFunRaw.apply g.raw g.valid_on x
        (g.defined_on x hxG)).Valid := by
    change RealCompute.ValidCompute (g.raw.compute x (g.defined_on x hxG))
    exact g.valid_on x (g.defined_on x hxG)
  have hHvalid :
      (PartialRealFunRaw.apply h.raw h.valid_on x
        (h.defined_on x hxH)).Valid := by
    change RealCompute.ValidCompute (h.raw.compute x (h.defined_on x hxH))
    exact h.valid_on x (h.defined_on x hxH)
  exact RealCompute.equiv_trans hFvalid hGvalid hHvalid
    (hfg.2.2 x hxF hxG) (hgh.2.2 x hxG hxH)

/-! Product evaluation transports along the local representation graph. -/
theorem equivalent_mulOfNonnegBounded
    (F F' G G' : FunctionOnInterval)
    (hFF' : Equivalent F F') (hGG' : Equivalent G G')
    (same_lower_FG : F.lower = G.lower) (same_upper_FG : F.upper = G.upper)
    (same_lower_F'G' : F'.lower = G'.lower) (same_upper_F'G' : F'.upper = G'.upper)
    (Fbounds : forall x (hx : inDomainInterval F.lower F.upper x),
      Exists fun B : Rat => 0 < B /\ forall n,
        0 <= (F.compute x hx n).lo /\ (F.compute x hx n).hi <= B)
    (Gbounds : forall x (hx : inDomainInterval G.lower G.upper x),
      Exists fun B : Rat => 0 < B /\ forall n,
        0 <= (G.compute x hx n).lo /\ (G.compute x hx n).hi <= B)
    (F'bounds : forall x (hx : inDomainInterval F'.lower F'.upper x),
      Exists fun B : Rat => 0 < B /\ forall n,
        0 <= (F'.compute x hx n).lo /\ (F'.compute x hx n).hi <= B)
    (G'bounds : forall x (hx : inDomainInterval G'.lower G'.upper x),
      Exists fun B : Rat => 0 < B /\ forall n,
        0 <= (G'.compute x hx n).lo /\ (G'.compute x hx n).hi <= B) :
    Equivalent
      (mulOfNonnegBounded F G same_lower_FG same_upper_FG Fbounds Gbounds)
      (mulOfNonnegBounded F' G' same_lower_F'G' same_upper_F'G' F'bounds G'bounds) := by
  refine ⟨hFF'.1, hFF'.2.1, ?_⟩
  intro x hx hx'
  let hxG : inDomainInterval G.lower G.upper x :=
    ⟨by rw [← same_lower_FG]; exact hx.1, by rw [← same_upper_FG]; exact hx.2⟩
  let hxG' : inDomainInterval G'.lower G'.upper x :=
    ⟨by rw [← same_lower_F'G']; exact hx'.1, by rw [← same_upper_F'G']; exact hx'.2⟩
  have hnonneg : forall (H : FunctionOnInterval)
      (bounds : forall y (hy : inDomainInterval H.lower H.upper y),
        Exists fun B : Rat => 0 < B /\ forall n,
          0 <= (H.compute y hy n).lo /\ (H.compute y hy n).hi <= B)
      (y : Rat) (hy : inDomainInterval H.lower H.upper y) n,
      0 <= (H.raw.compute y (H.defined_on y hy) n).lo := by
    intro H bounds y hy n
    rcases bounds y hy with ⟨B, hB, h⟩
    exact (h n).1
  have hXF : (PartialRealFunRaw.apply F.raw F.valid_on x
      (F.defined_on x hx)).Valid := by
    change RealCompute.ValidCompute (F.raw.compute x (F.defined_on x hx))
    exact F.valid_on x (F.defined_on x hx)
  have hXG : (PartialRealFunRaw.apply G.raw G.valid_on x
      (G.defined_on x hxG)).Valid := by
    change RealCompute.ValidCompute (G.raw.compute x (G.defined_on x hxG))
    exact G.valid_on x (G.defined_on x hxG)
  have hXF' : (PartialRealFunRaw.apply F'.raw F'.valid_on x
      (F'.defined_on x hx')).Valid := by
    change RealCompute.ValidCompute (F'.raw.compute x (F'.defined_on x hx'))
    exact F'.valid_on x (F'.defined_on x hx')
  have hXG' : (PartialRealFunRaw.apply G'.raw G'.valid_on x
      (G'.defined_on x hxG')).Valid := by
    change RealCompute.ValidCompute (G'.raw.compute x (G'.defined_on x hxG'))
    exact G'.valid_on x (G'.defined_on x hxG')
  have h := RealCompute.mul_equiv_of_nonneg
    hXF hXF' hXG hXG'
    (hnonneg F Fbounds x hx) (hnonneg F' F'bounds x hx')
    (hnonneg G Gbounds x hxG) (hnonneg G' G'bounds x hxG')
    (hFF'.2.2 x hx hx') (hGG'.2.2 x hxG hxG')
  change (RealCompute.mul
      (PartialRealFunRaw.apply F.raw F.valid_on x (F.defined_on x hx))
      (PartialRealFunRaw.apply G.raw G.valid_on x (G.defined_on x hxG))).Equiv
    (RealCompute.mul
      (PartialRealFunRaw.apply F'.raw F'.valid_on x (F'.defined_on x hx'))
      (PartialRealFunRaw.apply G'.raw G'.valid_on x (G'.defined_on x hxG')))
  exact h

end FunctionOnInterval

/-- Effective derivative on a rational interval.

For every requested output precision, small enough rational steps make the
finite-difference interval lie within the derivative interval's requested
tolerance.  Literal overlap would incorrectly demand equality at every finite
nonzero step. -/
structure HasDerivativeOnInterval (f df : FunctionOnInterval) where
  same_lower : df.lower = f.lower
  same_upper : df.upper = f.upper
  stepPrecision : Nat -> Nat
  /-- Interval evaluators need a step-aware precision schedule: a fixed
  nonzero box width would be magnified without bound when divided by an
  arbitrarily smaller rational step. -/
  evalPrecision : Rat -> Rat -> Nat -> Nat
  close :
    forall x h n
      (hx : inDomainInterval f.lower f.upper x)
      (hxh : inDomainInterval f.lower f.upper (x + h))
      (hdx : inDomainInterval df.lower df.upper x),
      h ≠ 0 ->
      qabs h <= (1 / ((stepPrecision n : Nat) : Rat)) ->
        intervalNearAtPrecision
          (QInterval.differenceQuotient
            (f.compute (x + h) hxh (evalPrecision x h n))
            (f.compute x hx (evalPrecision x h n))
            h)
          (df.compute x hdx (evalPrecision x h n))
          n

/-- Restrict a derivative certificate to a closed rational subinterval. The
underlying computations and precision schedules are unchanged; only interval
membership evidence is transported into the original domain. This is the
derivative-side closure operation needed when local ODE uniqueness is proved
on a finite rational partition. -/
def HasDerivativeOnInterval.restrict
    {f df : FunctionOnInterval} (D : HasDerivativeOnInterval f df)
    (a b : Rat) (hlo : f.lower <= a) (hab : a <= b)
    (hhi : b <= f.upper) :
    HasDerivativeOnInterval
      (FunctionOnInterval.restrict f a b hlo hab hhi)
      (FunctionOnInterval.restrict df a b
        (by rw [D.same_lower]; exact hlo) hab
        (by rw [D.same_upper]; exact hhi)) where
  same_lower := rfl
  same_upper := rfl
  stepPrecision := D.stepPrecision
  evalPrecision := D.evalPrecision
  close := by
    intro x h n hx hxh hdx hh hsmall
    have hx' : inDomainInterval f.lower f.upper x :=
      ⟨Rat.le_trans hlo hx.1, Rat.le_trans hx.2 hhi⟩
    have hxh' : inDomainInterval f.lower f.upper (x + h) :=
      ⟨Rat.le_trans hlo hxh.1, Rat.le_trans hxh.2 hhi⟩
    have hdx' : inDomainInterval df.lower df.upper x := by
      rw [D.same_lower, D.same_upper]
      exact hx'
    have hclose := D.close x h n hx' hxh' hdx' hh hsmall
    simpa [FunctionOnInterval.restrict, FunctionOnInterval.compute] using hclose

/-- Reindex an interval function by a cofinal computation-stage schedule.
This changes its raw evaluator while retaining the same rational domain. -/
def FunctionOnInterval.reindexStages (f : FunctionOnInterval)
    (sigma : RealCompute.StageSchedule) : FunctionOnInterval where
  raw :=
    { definedAt := f.raw.definedAt
      compute := fun x hx n => f.raw.compute x hx (sigma.stage n) }
  lower := f.lower
  upper := f.upper
  defined_on := f.defined_on
  valid_on := by
    intro x hx
    let value : RealCompute := { compute := fun n => f.raw.compute x hx n }
    have hvalid := RealCompute.schedule_valid value (f.valid_on x hx) sigma
    change RealCompute.Valid (RealCompute.schedule sigma value)
    exact hvalid

@[simp] theorem FunctionOnInterval.reindexStages_compute (f : FunctionOnInterval)
    (sigma : RealCompute.StageSchedule) (x : Rat)
    (hx : inDomainInterval f.lower f.upper x) (n : Nat) :
    (f.reindexStages sigma).compute x hx n = f.compute x hx (sigma.stage n) := rfl

/-- A cofinal stage schedule changes the computation, but not its represented
value at any rational input. -/
theorem FunctionOnInterval.reindexStages_equivalent (f : FunctionOnInterval)
    (sigma : RealCompute.StageSchedule) :
    FunctionOnInterval.Equivalent f (f.reindexStages sigma) := by
  refine ⟨rfl, rfl, ?_⟩
  intro x hxF hxG
  have hx : inDomainInterval f.lower f.upper x := hxF
  change ({ compute := f.compute x hx } : RealCompute).Equiv
    (RealCompute.schedule sigma ({ compute := f.compute x hx } : RealCompute))
  exact RealCompute.schedule_equiv
    ({ compute := f.compute x hx } : RealCompute)
    (f.valid_on x (f.defined_on x hx)) sigma

/-- Reindex a function and its derivative evaluator by the same cofinal
stage schedule. The derivative proof chooses a finer request for the original
certificate, then encloses each reindexed quotient and derivative box inside
the corresponding original boxes. Thus its exact equality meaning is
preserved while the executable stage schedule changes. -/
def HasDerivativeOnInterval.reindexStages
    {f df : FunctionOnInterval} (D : HasDerivativeOnInterval f df)
    (sigma : RealCompute.StageSchedule)
    (inner step : Nat -> Nat) (eval : Rat -> Rat -> Nat -> Nat)
    (hbudget : forall n,
      3 * (precisionAtStage (inner n)).val <= (precisionAtStage n).val)
    (hstep : forall n,
      1 / ((step n : Nat) : Rat) <=
        1 / ((D.stepPrecision (inner n) : Nat) : Rat))
    (heval : forall x h n,
      D.evalPrecision x h (inner n) <= sigma.stage (eval x h n)) :
    HasDerivativeOnInterval (f.reindexStages sigma) (df.reindexStages sigma) where
  same_lower := D.same_lower
  same_upper := D.same_upper
  stepPrecision := step
  evalPrecision := eval
  close := by
    intro x h n hx hxh hdx hh hsmall
    have hsmall' := Rat.le_trans hsmall (hstep n)
    have hold := D.close x h (inner n) hx hxh hdx hh hsmall'
    let oldStage := D.evalPrecision x h (inner n)
    let newStage := sigma.stage (eval x h n)
    have hstage : oldStage <= newStage := heval x h n
    have hxF : inDomainInterval f.lower f.upper x := hx
    have hxhF : inDomainInterval f.lower f.upper (x + h) := hxh
    have hdxF : inDomainInterval df.lower df.upper x := hdx
    have hfx := (f.valid_on x (f.defined_on x hxF)).2.1
      oldStage newStage hstage
    have hfxh := (f.valid_on (x + h) (f.defined_on (x + h) hxhF)).2.1
      oldStage newStage hstage
    have hdf := (df.valid_on x (df.defined_on x hdxF)).2.1
      oldStage newStage hstage
    have hquotient := QInterval.differenceQuotient_contains_of_contains
      ⟨hfx.1, hfx.2.2⟩ ⟨hfxh.1, hfxh.2.2⟩ h
    have hleftOrdered :
        (f.compute (x + h) hxhF newStage).lo <=
          (f.compute (x + h) hxhF newStage).hi := by
      have hw := (f.valid_on (x + h) (f.defined_on (x + h) hxhF)).1 newStage
      change 0 <= (f.compute (x + h) hxhF newStage).width at hw
      grind [QInterval.width]
    have hbaseOrdered :
        (f.compute x hxF newStage).lo <= (f.compute x hxF newStage).hi := by
      have hw := (f.valid_on x (f.defined_on x hxF)).1 newStage
      change 0 <= (f.compute x hxF newStage).width at hw
      grind [QInterval.width]
    have hquotientOrdered := QInterval.differenceQuotient_ordered
      (f.compute (x + h) hxhF newStage) (f.compute x hxF newStage)
      hleftOrdered hbaseOrdered h
    have hdfOrdered :
        (df.compute x hdxF newStage).lo <= (df.compute x hdxF newStage).hi := by
      have hw := (df.valid_on x (df.defined_on x hdxF)).1 newStage
      change 0 <= (df.compute x hdxF newStage).width at hw
      grind [QInterval.width]
    change QInterval.NearAt
      (QInterval.differenceQuotient
        (f.compute (x + h) hxhF newStage) (f.compute x hxF newStage) h)
      (df.compute x hdxF newStage) (precisionAtStage n)
    exact QInterval.nearAt_refine hold hquotient
      ⟨hdf.1, hdf.2.2⟩ hquotientOrdered hdfOrdered (hbudget n)

/-! A local FTC bridge for one positive rational cell.  The derivative
certificate controls the finite secant quotient; scaling that quotient back
by the cell width produces an enclosure of the endpoint difference.  The
explicit expansion pays twice the requested stage tolerance, so this is a
finite statement about rational interval computations rather than a limit
argument. -/
theorem HasDerivativeOnInterval.endpointDifference_contains_of_pos
    {f df : FunctionOnInterval}
    (D : HasDerivativeOnInterval f df)
    {x h : Rat} {n : Nat}
    (hx : inDomainInterval f.lower f.upper x)
    (hxh : inDomainInterval f.lower f.upper (x + h))
    (hdx : inDomainInterval df.lower df.upper x)
    (hpos : 0 < h)
    (hsmall : qabs h <=
      (1 / ((D.stepPrecision n : Nat) : Rat))) :
    (QInterval.scaleByRat h
      (QInterval.expand
        (df.compute x hdx (D.evalPrecision x h n))
        (2 * (precisionAtStage n).val))).ContainsInterval
      (QInterval.subInterval
        (f.compute (x + h) hxh (D.evalPrecision x h n))
        (f.compute x hx (D.evalPrecision x h n))) := by
  have hnear := D.close x h n hx hxh hdx (Rat.ne_of_gt hpos) hsmall
  change (QInterval.differenceQuotient
      (f.compute (x + h) hxh (D.evalPrecision x h n))
      (f.compute x hx (D.evalPrecision x h n)) h).NearAt
      (df.compute x hdx (D.evalPrecision x h n)) (precisionAtStage n) at hnear
  exact QInterval.scaleByRat_expand_contains_subInterval_of_differenceQuotient_near
    hpos hnear

/-! Closure under addition is stated for certificates using a common stage
schedule.  This is intentional: an evaluator's stage parameter is an
algorithmic resource, so combining two implementations must say how their
stages are synchronized.  The inner stage may be chosen finer than the
requested output stage to pay for the two summands' error budgets. -/
def HasDerivativeOnInterval.addOfCommonSchedule
    {f g df dg : FunctionOnInterval}
    (hf : HasDerivativeOnInterval f df)
    (hg : HasDerivativeOnInterval g dg)
    (hfgLower : f.lower = g.lower)
    (hfgUpper : f.upper = g.upper)
    (hdfgLower : df.lower = dg.lower)
    (hdfgUpper : df.upper = dg.upper)
    (hstep : hf.stepPrecision = hg.stepPrecision)
    (heval : hf.evalPrecision = hg.evalPrecision)
    (inner : Nat -> Nat)
    (hprecision : forall n,
      2 * (precisionAtStage (inner n)).val <= (precisionAtStage n).val) :
    HasDerivativeOnInterval
      (FunctionOnInterval.add f g hfgLower hfgUpper)
      (FunctionOnInterval.add df dg hdfgLower hdfgUpper) where
  same_lower := by
    calc
      (FunctionOnInterval.add df dg hdfgLower hdfgUpper).lower = df.lower := rfl
      _ = f.lower := hf.same_lower
      _ = (FunctionOnInterval.add f g hfgLower hfgUpper).lower := rfl
  same_upper := by
    calc
      (FunctionOnInterval.add df dg hdfgLower hdfgUpper).upper = df.upper := rfl
      _ = f.upper := hf.same_upper
      _ = (FunctionOnInterval.add f g hfgLower hfgUpper).upper := rfl
  stepPrecision := fun n => hf.stepPrecision (inner n)
  evalPrecision := fun x h n => hf.evalPrecision x h (inner n)
  close := by
    intro x h n hx hxh hdx hh hsmall
    have hxg : inDomainInterval g.lower g.upper x := by
      constructor
      · rw [← hfgLower]
        exact hx.1
      · rw [← hfgUpper]
        exact hx.2
    have hxhg : inDomainInterval g.lower g.upper (x + h) := by
      constructor
      · rw [← hfgLower]
        exact hxh.1
      · rw [← hfgUpper]
        exact hxh.2
    have hdxg : inDomainInterval dg.lower dg.upper x := by
      constructor
      · rw [← hdfgLower]
        exact hdx.1
      · rw [← hdfgUpper]
        exact hdx.2
    have hsmallG : qabs h <=
        (1 / ((hg.stepPrecision (inner n) : Nat) : Rat)) := by
      simpa [hstep] using hsmall
    have hcloseF := hf.close x h (inner n) hx hxh hdx hh hsmall
    have hcloseG₀ := hg.close x h (inner n) hxg hxhg hdxg hh hsmallG
    have hcloseG : intervalNearAtPrecision
        (QInterval.differenceQuotient
          (g.compute (x + h) hxhg (hf.evalPrecision x h (inner n)))
          (g.compute x hxg (hf.evalPrecision x h (inner n))) h)
        (dg.compute x hdxg (hf.evalPrecision x h (inner n))) (inner n) := by
      simpa [heval] using hcloseG₀
    have hcombined := intervalNearAtPrecision_addInterval
      hcloseF hcloseG (hprecision n)
    change intervalNearAtPrecision
      (QInterval.differenceQuotient
        (QInterval.addInterval
          (f.compute (x + h) hxh (hf.evalPrecision x h (inner n)))
          (g.compute (x + h) hxhg (hf.evalPrecision x h (inner n))))
        (QInterval.addInterval
          (f.compute x hx (hf.evalPrecision x h (inner n)))
          (g.compute x hxg (hf.evalPrecision x h (inner n)))) h)
      (QInterval.addInterval
        (df.compute x hdx (hf.evalPrecision x h (inner n)))
        (dg.compute x hdxg (hf.evalPrecision x h (inner n)))) n
    rw [QInterval.differenceQuotient_addInterval]
    exact hcombined

/-- A pointwise forward finite-difference derivative certificate.

This deliberately records only positive rational steps from one specified
basepoint.  It is useful for boundary calculations before the separate
two-sided and transport arguments needed by an interval derivative
certificate. -/
structure HasForwardDerivativeAt (f : FunctionOnInterval)
    (x : Rat) (derivative : RealCompute) where
  x_mem : inDomainInterval f.lower f.upper x
  derivative_valid : derivative.Valid
  stepPrecision : Nat -> Nat
  /-- The evaluator stage may depend on the positive rational step because
later non-exact certificates may divide a box by that step. -/
  evalPrecision : Rat -> Nat -> Nat
  close :
    forall h n
      (hxh : inDomainInterval f.lower f.upper (x + h)),
      0 < h ->
      h <= (1 / ((stepPrecision n : Nat) : Rat)) ->
        intervalNearAtPrecision
          (QInterval.differenceQuotient
            (f.compute (x + h) hxh (evalPrecision h n))
            (f.compute x x_mem (evalPrecision h n))
            h)
          (derivative.compute (evalPrecision h n))
          n

namespace FunctionOnInterval

/-! Pointwise negation preserves the rational chart and validity of interval
values. -/
def neg (F : FunctionOnInterval) : FunctionOnInterval where
  raw :=
    { definedAt := F.raw.definedAt
      compute := fun x hx n => QInterval.neg (F.raw.compute x hx n) }
  lower := F.lower
  upper := F.upper
  defined_on := F.defined_on
  valid_on := by
    intro x hx
    let X : RealCompute := { compute := F.raw.compute x hx }
    have hX : X.Valid := by
      change RealCompute.ValidCompute X.compute
      exact F.valid_on x hx
    change RealCompute.ValidCompute (RealCompute.negCompute X)
    exact RealCompute.negCompute_valid hX

@[simp] theorem neg_compute (F : FunctionOnInterval)
    (x : Rat) (hx : inDomainInterval F.lower F.upper x) (n : Nat) :
    (neg F).compute x hx n = QInterval.neg (F.compute x hx n) := by
  rfl

/-! Subtraction is exposed as addition with pointwise negation.  Keeping this
definition factored lets all validity and derivative closure proofs reuse the
two primitive finite interval operations. -/
def sub
    (F G : FunctionOnInterval)
    (same_lower : F.lower = G.lower)
    (same_upper : F.upper = G.upper) : FunctionOnInterval :=
  add F (neg G) same_lower same_upper

/-- Rationally scale every interval value of an interval-domain function.
The domain is deliberately unchanged: scalar multiplication is a pointwise
operation, not an extension of the function's rational chart. -/
def scaleRat (r : Rat) (F : FunctionOnInterval) : FunctionOnInterval where
  raw :=
    { definedAt := F.raw.definedAt
      compute := fun x hx n => QInterval.scaleRat r (F.raw.compute x hx n) }
  lower := F.lower
  upper := F.upper
  defined_on := by
    intro x hx
    exact F.defined_on x hx
  valid_on := by
    intro x hraw
    let X : RealCompute :=
      { compute := F.raw.compute x hraw }
    have hX : X.Valid := by
      change RealCompute.ValidCompute X.compute
      exact F.valid_on x hraw
    change RealCompute.ValidCompute
      (fun n => QInterval.scaleRat r (F.raw.compute x hraw n))
    change RealCompute.ValidCompute (RealCompute.scaleRatCompute r X)
    exact RealCompute.scaleRatCompute_valid (r := r) hX

/-- The pointwise evaluator for a rationally scaled interval function. -/
theorem scaleRat_compute (r : Rat) (F : FunctionOnInterval)
    (x : Rat) (hx : inDomainInterval F.lower F.upper x) (n : Nat) :
    (scaleRat r F).compute x hx n = QInterval.scaleRat r (F.compute x hx n) := by
  rfl

/-- Exact affine rational functions satisfy the interval-valued derivative
definition on every rational interval.  The certificate uses no limiting
operation: each finite quotient is literally the constant rational slope. -/
def exactRatAffineDerivative (a b m c : Rat) :
    HasDerivativeOnInterval
      (exactRat (fun x => m * x + c) a b)
      (exactRat (fun _x => m) a b) where
  same_lower := rfl
  same_upper := rfl
  stepPrecision := fun _n => 1
  evalPrecision := fun _x _h _n => 0
  close := by
    intro x h n _hx _hxh _hdx hh _hsmall
    change intervalNearAtPrecision
      (QInterval.differenceQuotient
        { lo := m * (x + h) + c, hi := m * (x + h) + c }
        { lo := m * x + c, hi := m * x + c } h)
      { lo := m, hi := m } n
    rw [QInterval.differenceQuotient_singleton]
    have hcalc : (m * (x + h) + c - (m * x + c)) / h = m := by
      rw [Rat.div_def]
      have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc,
        Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
    rw [hcalc]
    exact intervalNearAtPrecision_singleton_self m n

/-- The exact unit coordinate has derivative one in the interval-valued
finite-difference sense used by the calculus layer. -/
def exactRatIdDerivative (a b : Rat) :
    HasDerivativeOnInterval
      (exactRat (fun x => x) a b)
      (exactRat (fun _x => 1) a b) := by
  simpa [Rat.one_mul, Rat.add_zero] using
    exactRatAffineDerivative a b 1 0

/-- The exact square is the first non-affine example of the interval-valued
derivative definition.  Its finite quotient differs from twice its input by
exactly the signed step, so the precision-indexed step budget closes the four
interval-nearness inequalities without a limit principle. -/
def exactRatSquareDerivative (a b : Rat) :
    HasDerivativeOnInterval
      (exactRat (fun x => x * x) a b)
      (exactRat (fun x => 2 * x) a b) where
  same_lower := rfl
  same_upper := rfl
  stepPrecision := fun n => if n = 0 then 1 else n
  evalPrecision := fun _x _h _n => 0
  close := by
    intro x h n _hx _hxh _hdx hh hsmall
    change intervalNearAtPrecision
      (QInterval.differenceQuotient
        { lo := (x + h) * (x + h), hi := (x + h) * (x + h) }
        { lo := x * x, hi := x * x } h)
      { lo := 2 * x, hi := 2 * x } n
    rw [QInterval.differenceQuotient_singleton]
    have hcalc : ((x + h) * (x + h) - x * x) / h = 2 * x + h := by
      rw [Rat.div_def]
      have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_assoc,
        Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
    rw [hcalc]
    have hprecision : qabs h <= (precisionAtStage n).val := by
      change qabs h <=
        1 / (((if n = 0 then 1 else n : Nat) : Rat)) at hsmall
      by_cases hn : n = 0
      · subst n
        have hsmall' : qabs h <= 1 / (1 : Rat) := by
          simpa [if_pos rfl] using hsmall
        calc
          qabs h <= 1 / (1 : Rat) := hsmall'
          _ = (precisionAtStage 0).val := by decide +kernel
      · simpa [precisionAtStage, hn] using hsmall
    have hupper : h <= (precisionAtStage n).val :=
      Rat.le_trans (self_le_qabs h) hprecision
    have hlower : -h <= (precisionAtStage n).val :=
      Rat.le_trans (by simpa [qabs_neg] using self_le_qabs (-h)) hprecision
    unfold intervalNearAtPrecision QInterval.NearAt QInterval.width
    constructor
    · grind
    constructor
    · grind
    constructor <;> grind [Rat.sub_eq_add_neg]

end FunctionOnInterval

namespace QInterval

/-- Scaling both endpoint values by two commutes with the finite difference
quotient, including for a negative rational step. -/
theorem differenceQuotient_scaleRat_two (A B : QInterval) (h : Rat) :
    differenceQuotient (scaleRat 2 A) (scaleRat 2 B) h =
      scaleRat 2 (differenceQuotient A B h) := by
  have htwo : (0 : Rat) <= 2 := by decide +kernel
  by_cases hinv : 0 <= 1 / h
  · cases A
    cases B
    congr 1 <;>
      simp [differenceQuotient, divRat, sub, scaleRat, htwo, hinv] <;>
        grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]
  · cases A
    cases B
    congr 1 <;>
      simp [differenceQuotient, divRat, sub, scaleRat, htwo, hinv] <;>
        grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]

end QInterval

/-! A nonnegative rational scaling transports a finite near-certificate when
the internal error is multiplied into the requested output budget. -/
theorem intervalNearAtPrecision_scaleRat_of_nonneg
    {r : Rat} (hr : 0 <= r)
    {I J : QInterval} {m n : Nat}
    (hnear : intervalNearAtPrecision I J m)
    (hprecision : r * (precisionAtStage m).val <=
      (precisionAtStage n).val) :
    intervalNearAtPrecision (QInterval.scaleRat r I)
      (QInterval.scaleRat r J) n := by
  unfold intervalNearAtPrecision QInterval.NearAt at hnear ⊢
  rcases hnear with ⟨hleft, hright, hwidthI, hwidthJ⟩
  unfold QInterval.scaleRat
  simp only [if_pos hr]
  constructor
  · calc
      r * I.lo <= r * (J.hi + (precisionAtStage m).val) :=
        Rat.mul_le_mul_of_nonneg_left hleft hr
      _ = r * J.hi + r * (precisionAtStage m).val := by
        rw [Rat.mul_add]
      _ <= r * J.hi + (precisionAtStage n).val := by
        exact (Rat.add_le_add_left).2 hprecision
  constructor
  · calc
      r * J.lo <= r * (I.hi + (precisionAtStage m).val) :=
        Rat.mul_le_mul_of_nonneg_left hright hr
      _ = r * I.hi + r * (precisionAtStage m).val := by
        rw [Rat.mul_add]
      _ <= r * I.hi + (precisionAtStage n).val := by
        exact (Rat.add_le_add_left).2 hprecision
  constructor
  · change r * I.hi - r * I.lo <= (precisionAtStage n).val
    calc
      r * I.hi - r * I.lo = r * I.width := by
        unfold QInterval.width
        grind [Rat.sub_eq_add_neg, Rat.mul_add]
      _ <= r * (precisionAtStage m).val :=
        Rat.mul_le_mul_of_nonneg_left hwidthI hr
      _ <= (precisionAtStage n).val := hprecision
  · change r * J.hi - r * J.lo <= (precisionAtStage n).val
    calc
      r * J.hi - r * J.lo = r * J.width := by
        unfold QInterval.width
        grind [Rat.sub_eq_add_neg, Rat.mul_add]
      _ <= r * (precisionAtStage m).val :=
        Rat.mul_le_mul_of_nonneg_left hwidthJ hr
      _ <= (precisionAtStage n).val := hprecision

theorem intervalNearAtPrecision_neg
    {I J : QInterval} {n : Nat}
    (hnear : intervalNearAtPrecision I J n) :
    intervalNearAtPrecision (QInterval.neg I) (QInterval.neg J) n := by
  unfold intervalNearAtPrecision QInterval.NearAt at hnear ⊢
  rcases hnear with ⟨hleft, hright, hwidthI, hwidthJ⟩
  unfold QInterval.neg QInterval.width
  constructor
  · grind [Rat.sub_eq_add_neg]
  constructor
  · grind [Rat.sub_eq_add_neg]
  constructor
  · simpa [QInterval.width, Rat.sub_eq_add_neg, Rat.add_comm] using hwidthI
  · simpa [QInterval.width, Rat.sub_eq_add_neg, Rat.add_comm] using hwidthJ

/-- If two interval boxes are close at a sufficiently finer precision, then
doubling both boxes remains close at the requested precision.  This is the
finite error-budget step behind the scalar-multiple derivative rule. -/
theorem intervalNearAtPrecision_scaleRat_two
    {I J : QInterval} {m n : Nat}
    (hnear : intervalNearAtPrecision I J m)
    (hprecision : 2 * (precisionAtStage m).val <= (precisionAtStage n).val) :
    intervalNearAtPrecision (QInterval.scaleRat 2 I) (QInterval.scaleRat 2 J) n := by
  unfold intervalNearAtPrecision QInterval.NearAt at hnear ⊢
  rcases hnear with ⟨hleft, hright, hwidthI, hwidthJ⟩
  have htwo : (0 : Rat) <= 2 := by decide +kernel
  unfold QInterval.scaleRat
  simp only [if_pos htwo]
  constructor
  · calc
      2 * I.lo <= 2 * (J.hi + (precisionAtStage m).val) :=
        Rat.mul_le_mul_of_nonneg_left hleft htwo
      _ = 2 * J.hi + 2 * (precisionAtStage m).val := by
        grind [Rat.mul_add]
      _ <= 2 * J.hi + (precisionAtStage n).val :=
        (Rat.add_le_add_left).2 hprecision
  constructor
  · calc
      2 * J.lo <= 2 * (I.hi + (precisionAtStage m).val) :=
        Rat.mul_le_mul_of_nonneg_left hright htwo
      _ = 2 * I.hi + 2 * (precisionAtStage m).val := by
        grind [Rat.mul_add]
      _ <= 2 * I.hi + (precisionAtStage n).val :=
        (Rat.add_le_add_left).2 hprecision
  constructor
  · change 2 * I.hi - 2 * I.lo <= (precisionAtStage n).val
    calc
      2 * I.hi - 2 * I.lo = 2 * I.width := by
        unfold QInterval.width
        grind [Rat.sub_eq_add_neg, Rat.mul_add]
      _ <= 2 * (precisionAtStage m).val :=
        Rat.mul_le_mul_of_nonneg_left hwidthI htwo
      _ <= (precisionAtStage n).val := hprecision
  · change 2 * J.hi - 2 * J.lo <= (precisionAtStage n).val
    calc
      2 * J.hi - 2 * J.lo = 2 * J.width := by
        unfold QInterval.width
        grind [Rat.sub_eq_add_neg, Rat.mul_add]
      _ <= 2 * (precisionAtStage m).val :=
        Rat.mul_le_mul_of_nonneg_left hwidthJ htwo
      _ <= (precisionAtStage n).val := hprecision

private theorem one_div_nat_antitone_for_derivative_precision {n m : Nat}
    (hn : 0 < n) (hm : 0 < m) (hnm : n <= m) :
    (1 / (m : Rat)) <= 1 / (n : Rat) := by
  apply Rat.le_of_mul_le_mul_right (c := (n : Rat) * (m : Rat))
  · calc
      (1 / (m : Rat)) * ((n : Rat) * (m : Rat)) = (n : Rat) := by
        have hmne : (m : Rat) ≠ 0 := Rat.ne_of_gt ((Rat.natCast_pos).2 hm)
        grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
      _ <= (m : Rat) := by exact_mod_cast hnm
      _ = (1 / (n : Rat)) * ((n : Rat) * (m : Rat)) := by
        have hnne : (n : Rat) ≠ 0 := Rat.ne_of_gt ((Rat.natCast_pos).2 hn)
        grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
  · exact Rat.mul_pos ((Rat.natCast_pos).2 hn) ((Rat.natCast_pos).2 hm)

/-- The doubled function evaluates its derivative certificate at a finer
stage.  The resulting finite interval error remains within the original
precision budget after multiplication by two. -/
theorem precisionAtStage_scaleRat_two (n : Nat) :
    2 * (precisionAtStage (2 * (n + 1))).val <= (precisionAtStage n).val := by
  have hscaled :
      2 * (precisionAtStage (2 * (n + 1))).val =
        1 / (((n + 1 : Nat) : Rat)) := by
    have hstage : 2 * (n + 1) ≠ 0 := by omega
    change 2 * (1 / (((2 * (n + 1) : Nat) : Rat))) =
      1 / (((n + 1 : Nat) : Rat))
    rw [Rat.natCast_mul]
    rw [Rat.div_def, Rat.inv_mul_rev]
    have htwo : (2 : Rat) * (2 : Rat)⁻¹ = 1 := by decide +kernel
    grind [Rat.mul_assoc, Rat.mul_comm]
  rw [hscaled]
  by_cases hn : n = 0
  · subst n
    decide +kernel
  · rw [precisionAtStage, dif_neg hn]
    exact one_div_nat_antitone_for_derivative_precision
      (Nat.pos_of_ne_zero hn) (Nat.succ_pos n) (Nat.le_succ n)

/-- A two-sided interval derivative certificate is closed under multiplication
by two.  This is a literal rational-box calculation, not a topology or a
completed-real linearity rule. -/
def HasDerivativeOnInterval.scaleRat_two
    {f df : FunctionOnInterval}
    (D : HasDerivativeOnInterval f df) :
    HasDerivativeOnInterval
      (FunctionOnInterval.scaleRat 2 f)
      (FunctionOnInterval.scaleRat 2 df) where
  same_lower := D.same_lower
  same_upper := D.same_upper
  stepPrecision := fun n => D.stepPrecision (2 * (n + 1))
  evalPrecision := fun x h n => D.evalPrecision x h (2 * (n + 1))
  close := by
    intro x h n hx hxh hdx hh hsmall
    change inDomainInterval f.lower f.upper x at hx
    change inDomainInterval f.lower f.upper (x + h) at hxh
    change inDomainInterval df.lower df.upper x at hdx
    have hbase := D.close x h (2 * (n + 1)) hx hxh hdx hh hsmall
    have hscaled := intervalNearAtPrecision_scaleRat_two hbase
      (precisionAtStage_scaleRat_two n)
    simpa only [FunctionOnInterval.scaleRat_compute,
      QInterval.differenceQuotient_scaleRat_two] using hscaled

/-! General nonnegative rational scalar closure.  The caller supplies the
internal stage schedule and its finite error-budget proof; this keeps the
computational cost visible instead of baking in a convergence-rate theorem. -/
def HasDerivativeOnInterval.scaleRat_of_nonneg
    {r : Rat} (hr : 0 <= r)
    {f df : FunctionOnInterval}
    (D : HasDerivativeOnInterval f df)
    (inner : Nat -> Nat)
    (hprecision : forall n,
      r * (precisionAtStage (inner n)).val <= (precisionAtStage n).val) :
    HasDerivativeOnInterval
      (FunctionOnInterval.scaleRat r f)
      (FunctionOnInterval.scaleRat r df) where
  same_lower := D.same_lower
  same_upper := D.same_upper
  stepPrecision := fun n => D.stepPrecision (inner n)
  evalPrecision := fun x h n => D.evalPrecision x h (inner n)
  close := by
    intro x h n hx hxh hdx hh hsmall
    change inDomainInterval f.lower f.upper x at hx
    change inDomainInterval f.lower f.upper (x + h) at hxh
    change inDomainInterval df.lower df.upper x at hdx
    have hbase := D.close x h (inner n) hx hxh hdx hh hsmall
    have hscaled := intervalNearAtPrecision_scaleRat_of_nonneg hr
      hbase (hprecision n)
    simpa only [FunctionOnInterval.scaleRat_compute,
      QInterval.differenceQuotient_scaleRat_of_nonneg hr] using hscaled

/-! Full rational scalar closure.  Nonnegative scalars use interval scaling
directly; negative scalars use the proved sign decomposition and the negation
closure.  In both cases the caller supplies the finite precision budget
`|r| * eps_inner <= eps`. -/
def HasDerivativeOnInterval.scaleRat
    {r : Rat}
    {f df : FunctionOnInterval}
    (D : HasDerivativeOnInterval f df)
    (inner : Nat -> Nat)
    (hprecision : forall n,
      qabs r * (precisionAtStage (inner n)).val <=
        (precisionAtStage n).val) :
    HasDerivativeOnInterval
      (FunctionOnInterval.scaleRat r f)
      (FunctionOnInterval.scaleRat r df) := by
  by_cases hr : 0 <= r
  · exact D.scaleRat_of_nonneg hr inner (by
      intro n
      simpa [qabs_eq_self_of_nonneg hr] using hprecision n)
  · have hrneg : r < 0 := Rat.not_le.mp hr
    have hnonneg : 0 <= -r := by
      have hpos : 0 < -r := by
        simpa using (Rat.neg_lt_neg hrneg)
      exact Rat.le_of_lt hpos
    have hprecision' : forall n,
        (-r) * (precisionAtStage (inner n)).val <=
          (precisionAtStage n).val := by
      have hrq : qabs r = -r :=
        qabs_eq_neg_of_nonpos (Rat.le_of_lt hrneg)
      intro n
      simpa [hrq] using hprecision n
    refine
      { same_lower := D.same_lower
        same_upper := D.same_upper
        stepPrecision := fun n => D.stepPrecision (inner n)
        evalPrecision := fun x h n => D.evalPrecision x h (inner n)
        close := ?_ }
    intro x h n hx hxh hdx hh hsmall
    change inDomainInterval f.lower f.upper x at hx
    change inDomainInterval f.lower f.upper (x + h) at hxh
    change inDomainInterval df.lower df.upper x at hdx
    have hbase := D.close x h (inner n) hx hxh hdx hh hsmall
    have hscaled := intervalNearAtPrecision_scaleRat_of_nonneg hnonneg
      hbase (hprecision' n)
    have hneg := intervalNearAtPrecision_neg hscaled
    have hsecant :=
      (QInterval.scaleRat_neg_eq_neg_scaleRat_neg hrneg
        (QInterval.differenceQuotient
          (f.compute (x + h) hxh (D.evalPrecision x h (inner n)))
          (f.compute x hx (D.evalPrecision x h (inner n))) h)).symm
    have hderivative :=
      (QInterval.scaleRat_neg_eq_neg_scaleRat_neg hrneg
        (df.compute x hdx (D.evalPrecision x h (inner n)))).symm
    simpa only [FunctionOnInterval.scaleRat_compute,
      QInterval.differenceQuotient_scaleRat_of_neg hrneg, hsecant,
      hderivative] using hneg

/-! Negation needs no finer stage: it reverses both interval endpoints but
does not enlarge widths or the finite nearness budget. -/
def HasDerivativeOnInterval.neg
    {f df : FunctionOnInterval}
    (D : HasDerivativeOnInterval f df) :
    HasDerivativeOnInterval (FunctionOnInterval.neg f)
      (FunctionOnInterval.neg df) where
  same_lower := D.same_lower
  same_upper := D.same_upper
  stepPrecision := D.stepPrecision
  evalPrecision := D.evalPrecision
  close := by
    intro x h n hx hxh hdx hh hsmall
    change inDomainInterval f.lower f.upper x at hx
    change inDomainInterval f.lower f.upper (x + h) at hxh
    change inDomainInterval df.lower df.upper x at hdx
    have hbase := D.close x h n hx hxh hdx hh hsmall
    have hneg := intervalNearAtPrecision_neg hbase
    simpa only [FunctionOnInterval.neg_compute,
      QInterval.differenceQuotient_neg] using hneg

def HasDerivativeOnInterval.subOfCommonSchedule
    {f g df dg : FunctionOnInterval}
    (hf : HasDerivativeOnInterval f df)
    (hg : HasDerivativeOnInterval g dg)
    (hfgLower : f.lower = g.lower)
    (hfgUpper : f.upper = g.upper)
    (hdfgLower : df.lower = dg.lower)
    (hdfgUpper : df.upper = dg.upper)
    (hstep : hf.stepPrecision = hg.stepPrecision)
    (heval : hf.evalPrecision = hg.evalPrecision)
    (inner : Nat -> Nat)
    (hprecision : forall n,
      2 * (precisionAtStage (inner n)).val <= (precisionAtStage n).val) :
    HasDerivativeOnInterval
      (FunctionOnInterval.sub f g hfgLower hfgUpper)
      (FunctionOnInterval.add df (FunctionOnInterval.neg dg)
        hdfgLower hdfgUpper) := by
  simpa [FunctionOnInterval.sub] using
    (HasDerivativeOnInterval.addOfCommonSchedule hf (HasDerivativeOnInterval.neg hg)
      hfgLower hfgUpper hdfgLower hdfgUpper hstep heval inner hprecision)

/-! A named linear-combination wrapper for the two primitive closures.  The
scaled certificates are supplied explicitly so their sign splits and stage
schedules remain visible; this theorem only performs the common-chart
addition and its finite doubled-error budget. -/
def HasDerivativeOnInterval.linearCombinationOfCommonSchedule
    {r s : Rat} {f g df dg : FunctionOnInterval}
    (hf : HasDerivativeOnInterval
      (FunctionOnInterval.scaleRat r f)
      (FunctionOnInterval.scaleRat r df))
    (hg : HasDerivativeOnInterval
      (FunctionOnInterval.scaleRat s g)
      (FunctionOnInterval.scaleRat s dg))
    (hfgLower : (FunctionOnInterval.scaleRat r f).lower =
      (FunctionOnInterval.scaleRat s g).lower)
    (hfgUpper : (FunctionOnInterval.scaleRat r f).upper =
      (FunctionOnInterval.scaleRat s g).upper)
    (hdfgLower : (FunctionOnInterval.scaleRat r df).lower =
      (FunctionOnInterval.scaleRat s dg).lower)
    (hdfgUpper : (FunctionOnInterval.scaleRat r df).upper =
      (FunctionOnInterval.scaleRat s dg).upper)
    (hstep : hf.stepPrecision = hg.stepPrecision)
    (heval : hf.evalPrecision = hg.evalPrecision)
    (inner : Nat -> Nat)
    (hprecision : forall n,
      2 * (precisionAtStage (inner n)).val <= (precisionAtStage n).val) :
    HasDerivativeOnInterval
      (FunctionOnInterval.add
        (FunctionOnInterval.scaleRat r f)
        (FunctionOnInterval.scaleRat s g) hfgLower hfgUpper)
      (FunctionOnInterval.add
        (FunctionOnInterval.scaleRat r df)
        (FunctionOnInterval.scaleRat s dg) hdfgLower hdfgUpper) :=
  HasDerivativeOnInterval.addOfCommonSchedule hf hg
    hfgLower hfgUpper hdfgLower hdfgUpper hstep heval inner hprecision

/-- A function solving `f' = f` on an interval with a specified initial value.

This is the constructive uniqueness route for comparing exponential
representations without appealing to classical real completeness. -/
structure SolvesSelfDerivativeOnInterval (f : FunctionOnInterval) where
  derivative_self : HasDerivativeOnInterval f f
  /-- The small-step condition must admit positive rational steps at every
  requested precision. Without this field, choosing `stepPrecision n = 0`
  makes the implication in `HasDerivativeOnInterval.close` vacuous. -/
  step_precision_pos : forall n, 0 < derivative_self.stepPrecision n
  initial : Rat
  initial_mem : inDomainInterval f.lower f.upper initial
  initial_value : RealCompute
  initial_value_valid : initial_value.Valid
  initial_value_equiv :
    (PartialRealFunRaw.apply f.raw f.valid_on initial
      (f.defined_on initial initial_mem)).Equiv initial_value

/-- Uniqueness principle for `f' = f`.

The future proof should be constructive: estimate the difference of two
solutions on a finite rational subdivision, rather than invoking a classical
ODE theorem. The shared rational domain, initial coordinate, and raw-real
initial value are explicit hypotheses; none is inferred from the differential
equation. -/
def SelfDerivativeInitialValueUnique : Prop :=
  forall f g,
    (hf : SolvesSelfDerivativeOnInterval f) ->
    (hg : SolvesSelfDerivativeOnInterval g) ->
    f.lower = g.lower ->
    f.upper = g.upper ->
    hf.initial = hg.initial ->
    hf.initial_value.Equiv hg.initial_value ->
    FunctionOnInterval.Equivalent f g

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