Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · AlgebraicFunctions · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_AlgebraicFunctions

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexInterval
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FTC
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Polynomial

set_option autoImplicit true

namespace ComputableAnalysis

/-!
# Algebraic functions

This file collects algebraic-function algorithms.  In particular, square root
is treated here as the algebraic function cut out by `w^2 = z`; the rational
input algorithm below is the real branch on nonnegative rational inputs.
-/

namespace Polynomial

/-- One Newton step for a rational polynomial at a rational point.

The step is partial: if `p' x = 0`, Newton's method is not defined at `x`, so
the algorithm returns `none`. -/
def newtonStep? (coeffs : List Rat) (x : Rat) : Option Rat :=
  let slope := eval (derivative coeffs) x
  if slope = 0 then none else some (x - eval coeffs x / slope)

/-- The `n`th rational Newton iterate from `seed`, stopping if a derivative
vanishes along the way. -/
def newtonIterate? (coeffs : List Rat) : Nat -> Rat -> Option Rat
  | 0, seed => some seed
  | n + 1, seed =>
      match newtonIterate? coeffs n seed with
      | none => none
      | some x => newtonStep? coeffs x

/-- The `n`th Newton iterate, displayed as an exact point interval when the
iteration is defined.  This is deliberately not claimed to be a valid
`RealCompute`; convergence and certification require separate hypotheses. -/
def newtonPointInterval? (coeffs : List Rat) (seed : Rat) (n : Nat) :
    Option QInterval :=
  (newtonIterate? coeffs n seed).map fun x => { lo := x, hi := x }

end Polynomial

namespace CPoly

def derivative : Coeffs -> Coeffs
  | [] => []
  | _ :: cs =>
      cs.zipIdx.map fun (c, i) =>
        QComplex.scaleRat ((i + 1 : Nat) : Rat) c

def ofRatCoeffs (coeffs : List Rat) : Coeffs :=
  coeffs.map QComplex.ofRat

/-- One complex Newton step for a polynomial with rational-complex
coefficients at a rational-complex point. -/
def newtonStep? (coeffs : Coeffs) (z : QComplex) : Option QComplex :=
  let slope := eval (derivative coeffs) z
  match QComplex.div? (eval coeffs z) slope with
  | none => none
  | some correction => some (QComplex.sub z correction)

/-- The `n`th rational-complex Newton iterate from `seed`, stopping if the
derivative vanishes along the way. -/
def newtonIterate? (coeffs : Coeffs) : Nat -> QComplex -> Option QComplex
  | 0, seed => some seed
  | n + 1, seed =>
      match newtonIterate? coeffs n seed with
      | none => none
      | some z => newtonStep? coeffs z

def newtonIterateFromRatPoly? (coeffs : List Rat) (seed : QComplex)
    (n : Nat) : Option QComplex :=
  newtonIterate? (ofRatCoeffs coeffs) n seed

/-- The `n`th complex Newton iterate as an exact point box, when defined.
As with the rational version, this is a computational trace, not a validity
certificate. -/
def newtonPointBox? (coeffs : Coeffs) (seed : QComplex) (n : Nat) :
    Option QBox :=
  (newtonIterate? coeffs n seed).map QBox.point

end CPoly

namespace BiPoly

/-- Bivariate complex polynomials.  The outer list is in `z`; each inner
polynomial is in `w`. -/
abbrev Coeffs := List CPoly.Coeffs

def eval (P : Coeffs) (z w : QComplex) : QComplex :=
  P.foldr (fun row acc => QComplex.add (CPoly.eval row w) (QComplex.mul z acc)) QComplex.zero

def evalBox (P : Coeffs) (Z W : QBox) : QBox :=
  P.foldr (fun row acc => QBox.add (QBox.evalPoly row W) (QBox.mul Z acc)) QBox.zero

def onCurve (P : Coeffs) (z w : QComplex) : Prop :=
  eval P z w = QComplex.zero

/-- `w^2 - z`, viewed as an equation for square-root branches. -/
def sqrtEquation : Coeffs :=
  [[QComplex.zero, QComplex.zero, QComplex.one], [QComplex.ofRat (-1)]]

end BiPoly

namespace AlgebraicFunction

/-- A raw algebraic-function branch.  The branch is computational; the equation
records the algebraic relation it is intended to satisfy. -/
structure Raw where
  equation : BiPoly.Coeffs
  branch : FunctionRaw

namespace Raw

def domain (f : Raw) : QComplex -> Prop := f.branch.domain

def evalRaw (f : Raw) (z : QComplex) (hz : f.domain z) : ComplexCompute :=
  f.branch.evalRaw z hz

/-- Certification target: the computed boxes for the branch satisfy the
equation at every requested precision.  The input is exact rational-complex;
the output is a box. -/
def SatisfiesEquation (f : Raw) : Prop :=
  forall z (hz : f.domain z) n,
    let Z := QBox.point z
    let W := f.branch.compute z hz n
    let eps : QPos := if hn : n = 0 then
      { val := 1, property := by decide +kernel }
    else
      { val := (1 / (n : Rat)), property := one_div_nat_pos (Nat.pos_of_ne_zero hn) }
    QBox.Overlaps (BiPoly.evalBox f.equation Z W) (QBox.zeroAround eps)

/-- Agreement of algebraic branches is still agreement of their underlying
raw functions on the common domain. -/
def AgreeOnCommonDomain (f g : Raw) : Prop :=
  FunctionRaw.AgreeOnCommonDomain f.branch g.branch

end Raw

/-- Target shape for a square-root branch: a domain, a raw algorithm, and the
equation `w^2 = z`. -/
def sqrtBranch (branch : FunctionRaw) : Raw where
  equation := BiPoly.sqrtEquation
  branch := branch

end AlgebraicFunction

def sq (x : Rat) : Rat := x * x
def maxRat (a b : Rat) : Rat := if a <= b then b else a
def sqrtUpperBound (q : Rat) : Rat := maxRat 1 q

theorem sqrtUpperBound_eq_one {q : Rat} (hq : q <= 1) :
    sqrtUpperBound q = 1 := by
  unfold sqrtUpperBound maxRat
  by_cases hle : (1 : Rat) <= q
  · have hqeq : q = 1 := Rat.le_antisymm hq hle
    simp [hqeq]
  · simp [hle]

def sqrtBisectStep (q : Rat) (I : QInterval) : QInterval :=
  let m := I.midpoint
  if sq m <= q then { lo := m, hi := I.hi } else { lo := I.lo, hi := m }

def sqrtBisect (q : Rat) : Nat -> QInterval -> QInterval
  | 0, I => I
  | n + 1, I => sqrtBisect q n (sqrtBisectStep q I)

def sqrtFuel (q : Rat) (eps : QPos) : Nat := eps.val.den + (sqrtUpperBound q).den + 8

def sqrtApprox? (q : Rat) (eps : QPos) : Option QInterval :=
  if q < 0 then none else some (sqrtBisect q (sqrtFuel q eps) { lo := 0, hi := sqrtUpperBound q })

def sqrtDomain (q : Rat) : Prop := ¬ q < 0

def sqrtStageEps (n : Nat) : QPos :=
  if hn : n = 0 then
    { val := 1, property := by decide +kernel }
  else
    { val := (1 / (n : Rat)), property := by
        rw [Rat.div_def, Rat.one_mul]
        exact (Rat.inv_pos).2
          ((Rat.natCast_pos).2 (Nat.pos_of_ne_zero hn)) }

theorem one_div_natCast_den_eq (n : Nat) (hn : n ≠ 0) :
    (1 / (n : Rat)).den = n := by
  rw [Rat.div_def]
  rw [Rat.inv_def]
  change (1 * Rat.divInt 1 (n : Int)).den = n
  rw [Rat.one_mul]
  change (Rat.divInt 1 (Int.ofNat n)).den = n
  rw [Rat.divInt.eq_1]
  change (mkRat 1 n).den = n
  simp [mkRat, Rat.normalize_eq, hn]

theorem sqrtStageEps_den_eq (n : Nat) (hn : n ≠ 0) :
    (sqrtStageEps n).val.den = n := by
  simp [sqrtStageEps, hn]
  exact one_div_natCast_den_eq n hn

theorem sqrtFuel_sqrtStageEps_eq (q : Rat) (n : Nat) (hn : n ≠ 0) :
    sqrtFuel q (sqrtStageEps n) = n + (sqrtUpperBound q).den + 8 := by
  unfold sqrtFuel
  rw [sqrtStageEps_den_eq n hn]

def sqrtApproxOnDomain (q : Rat) (_h : sqrtDomain q) (n : Nat) : QInterval :=
  sqrtBisect q (sqrtFuel q (sqrtStageEps n)) { lo := 0, hi := sqrtUpperBound q }

def sqrtPartialRaw : PartialRealFunRaw where
  definedAt := sqrtDomain
  compute := sqrtApproxOnDomain

def sqrtCompute? (q : Rat) : Option (Nat -> QInterval) :=
  if hneg : q < 0 then
    none
  else
    some (sqrtPartialRaw.compute q hneg)

def sqrtCertified? (q : Rat) : Prop :=
  Exists fun compute : Nat -> QInterval =>
    sqrtCompute? q = some compute /\ RealCompute.ValidCompute compute

def sqrtRaw (q : Rat) (h : sqrtDomain q) : RealCompute where
  compute := fun n => sqrtApproxOnDomain q h n

def sqrtReal (q : Rat) (h : sqrtDomain q)
    (hvalid : (sqrtRaw q h).Valid) : RealCompute.Certified :=
  RealCompute.Certified.ofRaw (sqrtRaw q h) hvalid

namespace Rat

def sqrt (q : Rat) : Option (Nat -> QInterval) := sqrtCompute? q

end Rat

namespace RealCompute

def Nonnegative (x : RealCompute) : Prop :=
  forall eps, 0 <= (x.compute eps).hi

structure SqrtDomain (x : RealCompute) where
  valid : x.Valid
  nonnegative : x.Nonnegative

/-- Real square root as a partial operation target.

Unlike rational input, arbitrary computable-real nonnegativity is not generally
decidable, so the domain proof is an explicit argument.  The implementation of
the algorithm and the theorem that it computes a square root are later work.
-/
def sqrt (x : RealCompute) (_h : SqrtDomain x) : Prop :=
  Exists fun y : RealCompute => y.Valid

end RealCompute

def SqrtIntervalSpec (q : Rat) (I : QInterval) : Prop := 0 <= I.lo /\ I.lo <= I.hi /\ sq I.lo <= q /\ q <= sq I.hi

private theorem sqrtUpperBound_nonneg {q : Rat} (hq : 0 <= q) :
    0 <= sqrtUpperBound q := by
  unfold sqrtUpperBound maxRat
  by_cases hle : (1 : Rat) <= q
  case pos => simp [hle, hq]
  case neg => simpa [hle] using (by decide +kernel : (0 : Rat) <= 1)

private theorem sqrtUpperBound_sq_ge {q : Rat} (hq : 0 <= q) :
    q <= sq (sqrtUpperBound q) := by
  unfold sqrtUpperBound maxRat
  by_cases hle : (1 : Rat) <= q
  case pos =>
    simp [hle, sq]
    calc
      q = q * 1 := by grind
      _ <= q * q := Rat.mul_le_mul_of_nonneg_left hle hq
  case neg =>
    simp [hle, sq]
    have hqle : q <= 1 := by grind
    simpa using hqle

private theorem sqrtInitialSpec {q : Rat} (hq : 0 <= q) :
    SqrtIntervalSpec q { lo := 0, hi := sqrtUpperBound q } := by
  unfold SqrtIntervalSpec
  constructor
  case left => simp
  case right =>
    constructor
    case left => exact sqrtUpperBound_nonneg hq
    case right =>
      constructor
      case left => simpa [sq] using hq
      case right => exact sqrtUpperBound_sq_ge hq

private theorem midpoint_le_hi {I : QInterval} (h : I.lo <= I.hi) :
    I.midpoint <= I.hi := by
  unfold QInterval.midpoint
  have h2b : I.lo + I.hi <= 2 * I.hi := by grind
  calc
    (I.lo + I.hi) / 2 <= (2 * I.hi) / 2 := by
      rw [Rat.div_def, Rat.div_def]
      exact Rat.mul_le_mul_of_nonneg_right h2b
        (Rat.le_of_lt ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 2)))
    _ = I.hi := by
      rw [Rat.div_def]
      have hne : (2 : Rat) != 0 := by decide +kernel
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]

private theorem lo_le_midpoint {I : QInterval} (h : I.lo <= I.hi) :
    I.lo <= I.midpoint := by
  unfold QInterval.midpoint
  have h2a : 2 * I.lo <= I.lo + I.hi := by grind
  calc
    I.lo = (2 * I.lo) / 2 := by
      rw [Rat.div_def]
      have hne : (2 : Rat) != 0 := by decide +kernel
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
    _ <= (I.lo + I.hi) / 2 := by
      rw [Rat.div_def, Rat.div_def]
      exact Rat.mul_le_mul_of_nonneg_right h2a
        (Rat.le_of_lt ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 2)))

private theorem midpoint_nonneg {I : QInterval}
    (hlo : 0 <= I.lo) (hle : I.lo <= I.hi) :
    0 <= I.midpoint := by
  exact Rat.le_trans hlo (lo_le_midpoint hle)

theorem sqrtBisectStep_width_eq_half (q : Rat) (I : QInterval) :
    (sqrtBisectStep q I).width = I.width / 2 := by
  unfold sqrtBisectStep QInterval.width QInterval.midpoint
  by_cases h : sq ((I.lo + I.hi) / 2) <= q
  · simp [h]
    grind [Rat.sub_eq_add_neg, Rat.div_def, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
      Rat.mul_inv_cancel]
  · simp [h]
    grind [Rat.sub_eq_add_neg, Rat.div_def, Rat.mul_add, Rat.add_mul,
      Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm,
      Rat.mul_inv_cancel]

theorem sqrtBisect_width_eq (q : Rat) (fuel : Nat) (I : QInterval) :
    (sqrtBisect q fuel I).width =
      I.width / (((2 ^ fuel : Nat) : Rat)) := by
  induction fuel generalizing I with
  | zero =>
      simp [sqrtBisect]
      rw [Rat.div_def]
      grind [Rat.mul_inv_cancel]
  | succ fuel ih =>
      simp [sqrtBisect]
      rw [ih]
      rw [sqrtBisectStep_width_eq_half]
      rw [Rat.div_def, Rat.div_def, Rat.div_def]
      have hpow :
          (((2 ^ (fuel + 1) : Nat) : Rat)) =
            (((2 ^ fuel : Nat) : Rat)) * 2 := by
        exact_mod_cast (by simpa using (Nat.pow_succ 2 fuel))
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]

theorem sqrtApproxOnDomain_width_eq
    (q : Rat) (h : sqrtDomain q) (n : Nat) :
    (sqrtApproxOnDomain q h n).width =
      sqrtUpperBound q /
        (((2 ^ sqrtFuel q (sqrtStageEps n) : Nat) : Rat)) := by
  unfold sqrtApproxOnDomain
  rw [sqrtBisect_width_eq]
  simp [QInterval.width]
  rw [Rat.div_def]
  grind [Rat.mul_inv_cancel]

theorem sqrtApproxOnDomain_width_eq_positive_stage
    (q : Rat) (h : sqrtDomain q) (n : Nat) (hn : n ≠ 0) :
    (sqrtApproxOnDomain q h n).width =
      sqrtUpperBound q /
        (((2 ^ (n + (sqrtUpperBound q).den + 8) : Nat) : Rat)) := by
  rw [sqrtApproxOnDomain_width_eq]
  rw [sqrtFuel_sqrtStageEps_eq q n hn]

/-- On a rational input in the unit interval, the square-root bisection
box has an exact dyadic width.  The extra nine bisections are the fixed
initial safety margin of the public square-root algorithm.  This is useful
when a geometric construction chooses its evaluation precision from a mesh
size: it gives a literal error budget rather than only convergence. -/
theorem sqrtApproxOnDomain_width_eq_unit
    {q : Rat} (h : sqrtDomain q) (hq : q <= 1) (n : Nat) (hn : n ≠ 0) :
    (sqrtApproxOnDomain q h n).width =
      1 / (((2 ^ (n + 9) : Nat) : Rat)) := by
  rw [sqrtApproxOnDomain_width_eq_positive_stage q h n hn]
  rw [sqrtUpperBound_eq_one hq]
  change 1 / (((2 ^ (n + 1 + 8) : Nat) : Rat)) =
    1 / (((2 ^ (n + 9) : Nat) : Rat))
  congr 3 <;> omega

theorem sqrtStageEps_den_mono {n m : Nat} (hnm : n <= m) :
    (sqrtStageEps n).val.den <= (sqrtStageEps m).val.den := by
  by_cases hm0 : m = 0
  · have hn0 : n = 0 := by omega
    simp [sqrtStageEps, hn0, hm0]
  · by_cases hn0 : n = 0
    · have hmpos : 0 < m := Nat.pos_of_ne_zero hm0
      rw [sqrtStageEps_den_eq m hm0]
      simp [sqrtStageEps, hn0]
      exact hmpos
    · rw [sqrtStageEps_den_eq n hn0, sqrtStageEps_den_eq m hm0]
      exact hnm

theorem sqrtFuel_sqrtStageEps_mono
    (q : Rat) {n m : Nat} (hnm : n <= m) :
    sqrtFuel q (sqrtStageEps n) <= sqrtFuel q (sqrtStageEps m) := by
  unfold sqrtFuel
  have hden := sqrtStageEps_den_mono hnm
  omega

theorem sqrtBisectStep_contains
    (q : Rat) {I : QInterval} (hI : I.lo <= I.hi) :
    I.ContainsInterval (sqrtBisectStep q I) := by
  unfold QInterval.ContainsInterval sqrtBisectStep QInterval.midpoint
  by_cases h : sq ((I.lo + I.hi) / 2) <= q
  · simp [h]
    exact lo_le_midpoint hI
  · simp [h]
    exact midpoint_le_hi hI

theorem sqrtBisectStep_spec {q : Rat} {I : QInterval}
    (hI : SqrtIntervalSpec q I) :
    SqrtIntervalSpec q (sqrtBisectStep q I) := by
  have hlo : 0 <= I.lo := hI.1
  have hlohi : I.lo <= I.hi := hI.2.1
  have hloSq : sq I.lo <= q := hI.2.2.1
  have hhiSq : q <= sq I.hi := hI.2.2.2
  have hlom : I.lo <= I.midpoint := lo_le_midpoint hlohi
  have hmhi : I.midpoint <= I.hi := midpoint_le_hi hlohi
  have hmnonneg : 0 <= I.midpoint := midpoint_nonneg hlo hlohi
  unfold sqrtBisectStep
  by_cases htest : sq I.midpoint <= q
  case pos =>
    simp [htest, SqrtIntervalSpec, hmnonneg, hmhi, hhiSq]
  case neg =>
    have hqle : q <= sq I.midpoint := by grind
    simp [htest, SqrtIntervalSpec, hlo, hlom, hloSq, hqle]

theorem sqrtBisect_spec (q : Rat) :
    forall fuel I, SqrtIntervalSpec q I ->
      SqrtIntervalSpec q (sqrtBisect q fuel I)
  | 0, _I, hI => hI
  | fuel + 1, I, hI =>
      sqrtBisect_spec q fuel (sqrtBisectStep q I) (sqrtBisectStep_spec hI)

private theorem qinterval_contains_refl (I : QInterval) :
    I.ContainsInterval I := by
  unfold QInterval.ContainsInterval
  exact ⟨Rat.le_refl, Rat.le_refl⟩

private theorem qinterval_contains_trans {I J K : QInterval}
    (hIJ : I.ContainsInterval J) (hJK : J.ContainsInterval K) :
    I.ContainsInterval K := by
  unfold QInterval.ContainsInterval at *
  exact ⟨Rat.le_trans hIJ.1 hJK.1, Rat.le_trans hJK.2 hIJ.2⟩

theorem sqrtBisect_succ_right (q : Rat) (fuel : Nat) (I : QInterval) :
    sqrtBisect q (fuel + 1) I = sqrtBisectStep q (sqrtBisect q fuel I) := by
  induction fuel generalizing I with
  | zero => rfl
  | succ fuel ih =>
      simpa [sqrtBisect] using ih (sqrtBisectStep q I)

theorem sqrtBisect_step_refines_of_spec
    {q : Rat} {I : QInterval} (hI : SqrtIntervalSpec q I) (fuel : Nat) :
    (sqrtBisect q fuel I).ContainsInterval
      (sqrtBisect q (fuel + 1) I) := by
  rw [sqrtBisect_succ_right]
  exact sqrtBisectStep_contains q (sqrtBisect_spec q fuel I hI).2.1

theorem sqrtBisect_contains_of_le_fuel
    {q : Rat} {I : QInterval} (hI : SqrtIntervalSpec q I)
    {fuel₁ fuel₂ : Nat} (hle : fuel₁ <= fuel₂) :
    (sqrtBisect q fuel₁ I).ContainsInterval
      (sqrtBisect q fuel₂ I) := by
  induction hle with
  | refl =>
      exact qinterval_contains_refl (sqrtBisect q fuel₁ I)
  | step hle ih =>
      rename_i k
      exact qinterval_contains_trans ih
        (sqrtBisect_step_refines_of_spec hI k)

theorem sqrtApproxOnDomain_spec (q : Rat) (h : sqrtDomain q) (n : Nat) :
    SqrtIntervalSpec q (sqrtApproxOnDomain q h n) := by
  have hq : 0 <= q := by
    unfold sqrtDomain at h
    grind
  unfold sqrtApproxOnDomain
  exact sqrtBisect_spec q _ _ (sqrtInitialSpec hq)

theorem le_of_sq_le_sq_of_nonneg_right {a b : Rat}
    (hb : 0 <= b) (h : sq a <= sq b) : a <= b := by
  by_cases hab : a <= b
  case pos => exact hab
  case neg =>
    have hba : b < a := by grind
    have hapos : 0 < a := by grind
    have hblea : b <= a := by grind
    have h1 : b * a < a * a := Rat.mul_lt_mul_of_pos_right hba hapos
    have h0 : b * b <= b * a := Rat.mul_le_mul_of_nonneg_left hblea hb
    unfold sq at h
    grind

theorem SqrtIntervalSpec.lo_le_of_sq_le
    {q r : Rat} {I : QInterval}
    (hI : SqrtIntervalSpec q I) (hr : 0 <= r) (hqr : q <= sq r) :
    I.lo <= r :=
  le_of_sq_le_sq_of_nonneg_right hr (Rat.le_trans hI.2.2.1 hqr)

theorem SqrtIntervalSpec.le_hi_of_sq_le
    {q r : Rat} {I : QInterval}
    (hI : SqrtIntervalSpec q I) (hrq : sq r <= q) :
    r <= I.hi := by
  have hhi_nonneg : 0 <= I.hi := Rat.le_trans hI.1 hI.2.1
  exact le_of_sq_le_sq_of_nonneg_right hhi_nonneg
    (Rat.le_trans hrq hI.2.2.2)

/-- A rational lower square certificate lies below the certified bisection
lower endpoint after paying exactly the enclosing interval's width.  This is
the finite replacement for appealing to an unrepresented exact square root:
it applies directly to rational geometric lower bounds such as chord cross
products. -/
theorem SqrtIntervalSpec.sub_width_le_lo_of_sq_le
    {q r : Rat} {I : QInterval}
    (hI : SqrtIntervalSpec q I) (hrq : sq r <= q) :
    r - I.width <= I.lo := by
  have hrhi : r <= I.hi := hI.le_hi_of_sq_le hrq
  unfold QInterval.width at hrhi ⊢
  grind [Rat.sub_eq_add_neg]

/-- A lower square certificate gives a quantitative lower bound for the
finite bisection result.  Unlike a statement about an exact square root, this
uses only the rational interval width produced by the algorithm. -/
theorem sqrtApproxOnDomain_sub_width_le_lo_of_sq_le
    (q : Rat) (h : sqrtDomain q) (n : Nat) {r : Rat}
    (hrq : sq r <= q) :
    r - (sqrtApproxOnDomain q h n).width <=
      (sqrtApproxOnDomain q h n).lo :=
  (sqrtApproxOnDomain_spec q h n).sub_width_le_lo_of_sq_le hrq

theorem sqrtPartialRaw_sub_width_le_lo_of_sq_le
    (q : Rat) (h : sqrtDomain q) (n : Nat) {r : Rat}
    (hrq : sq r <= q) :
    r - (sqrtPartialRaw.compute q h n).width <=
      (sqrtPartialRaw.compute q h n).lo := by
  simpa [sqrtPartialRaw] using
    (sqrtApproxOnDomain_sub_width_le_lo_of_sq_le q h n hrq)

def sqrtIntervalSpecBool (q : Rat) (I : QInterval) : Bool := decide (0 <= I.lo /\ I.lo <= I.hi /\ sq I.lo <= q /\ q <= sq I.hi)

def sqrtApproxOk? (q : Rat) (eps : QPos) : Option Bool :=
  match sqrtApprox? q eps with | none => none | some I => some (I.widthOk eps && sqrtIntervalSpecBool q I)

def SqrtRealComputeSpec (q : Rat) (x : RealCompute) : Prop := x.Valid /\ forall eps, SqrtIntervalSpec q (x.compute eps)

theorem sqrtRaw_stage_spec (q : Rat) (h : sqrtDomain q) (n : Nat) :
    SqrtIntervalSpec q ((sqrtRaw q h).compute n) := by
  simpa [sqrtRaw] using sqrtApproxOnDomain_spec q h n

def SqrtRawSpec (q : Rat) (h : sqrtDomain q) : Prop :=
  SqrtRealComputeSpec q (sqrtRaw q h)

theorem sqrt_spec_equiv_of_spec {q : Rat} {x y : RealCompute}
    (hx : SqrtRealComputeSpec q x) (hy : SqrtRealComputeSpec q y) :
    x.Equiv y := by
  intro n
  apply (RealCompute.compareAt_overlap_iff x y n n).2
  have hxs := hx.2 n
  have hys := hy.2 n
  unfold SqrtIntervalSpec at hxs hys
  have hxy : (x.compute n).lo <= (y.compute n).hi := by
    apply (Rat.not_lt).mp
    intro hnot
    have hlt : (y.compute n).hi < (x.compute n).lo := by grind
    have hdiff : 0 < (x.compute n).lo - (y.compute n).hi := by grind
    have hsum : 0 < (x.compute n).lo + (y.compute n).hi := by
      grind
    have hsq_lt : sq (y.compute n).hi < sq (x.compute n).lo := by
      unfold sq
      have hprod : 0 <
          ((x.compute n).lo - (y.compute n).hi) *
            ((x.compute n).lo + (y.compute n).hi) :=
        Rat.mul_pos hdiff hsum
      grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg]
    have hleft : sq (x.compute n).lo <= sq (y.compute n).hi :=
      Rat.le_trans hxs.2.2.1 hys.2.2.2
    grind
  have hyx : (y.compute n).lo <= (x.compute n).hi := by
    apply (Rat.not_lt).mp
    intro hnot
    have hlt : (x.compute n).hi < (y.compute n).lo := by grind
    have hdiff : 0 < (y.compute n).lo - (x.compute n).hi := by grind
    have hsum : 0 < (y.compute n).lo + (x.compute n).hi := by
      grind
    have hsq_lt : sq (x.compute n).hi < sq (y.compute n).lo := by
      unfold sq
      have hprod : 0 <
          ((y.compute n).lo - (x.compute n).hi) *
            ((y.compute n).lo + (x.compute n).hi) :=
        Rat.mul_pos hdiff hsum
      grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg]
    have hleft : sq (y.compute n).lo <= sq (x.compute n).hi :=
      Rat.le_trans hys.2.2.1 hxs.2.2.2
    grind
  change (x.compute n).lo <= (y.compute n).hi /\
    (y.compute n).lo <= (x.compute n).hi
  exact ⟨hxy, hyx⟩

def sqrtWidthConstant (q : Rat) : Nat :=
  (sqrtUpperBound q).num.natAbs + 1

private theorem rat_le_num_natAbs_succ (q : Rat) :
    q <= (((q.num.natAbs + 1 : Nat) : Rat)) := by
  by_cases hqpos : 0 < q
  · have hdenpos : 0 < ((q.den : Nat) : Rat) := by
      exact (Rat.natCast_pos).2 (Nat.pos_of_ne_zero q.den_nz)
    apply Rat.le_of_mul_le_mul_right (c := ((q.den : Nat) : Rat))
    · rw [Rat.mul_comm q ((q.den : Nat) : Rat), rat_den_mul_self]
      have hnumpos : 0 < q.num := rat_num_pos_of_pos hqpos
      have hnum_nonneg : 0 <= q.num := Int.le_of_lt hnumpos
      have hcast : (((q.num.natAbs : Nat) : Rat)) = (q.num : Rat) := by
        exact_mod_cast (Int.natAbs_of_nonneg hnum_nonneg)
      calc
        (q.num : Rat) = ((q.num.natAbs : Nat) : Rat) := by rw [hcast]
        _ <= (((q.num.natAbs + 1 : Nat) : Rat)) := by
          exact_mod_cast (Nat.le_succ q.num.natAbs)
        _ <= (((q.num.natAbs + 1 : Nat) : Rat)) *
            ((q.den : Nat) : Rat) := by
          exact_mod_cast (Nat.le_mul_of_pos_right (q.num.natAbs + 1)
            (Nat.pos_of_ne_zero q.den_nz))
    · exact hdenpos
  · have hqnonpos : q <= 0 := by grind
    have hzero : (0 : Rat) <= (((q.num.natAbs + 1 : Nat) : Rat)) :=
      Rat.natCast_nonneg
    exact Rat.le_trans hqnonpos hzero

private theorem succ_le_two_pow (n : Nat) : n + 1 <= 2 ^ n := by
  induction n with
  | zero => simp
  | succ n ih =>
      calc
        n + 1 + 1 <= 2 * (n + 1) := by omega
        _ <= 2 * 2 ^ n := Nat.mul_le_mul_left 2 ih
        _ = 2 ^ (n + 1) := by
          rw [Nat.pow_succ]
          omega

theorem sqrtApproxOnDomain_width_le_nat_over_succ
    (q : Rat) (h : sqrtDomain q) (n : Nat) :
    (sqrtApproxOnDomain q h n).width <=
      (sqrtWidthConstant q : Rat) / (((n + 1 : Nat) : Rat)) := by
  let B : Rat := sqrtUpperBound q
  let C : Nat := sqrtWidthConstant q
  let fuel : Nat := sqrtFuel q (sqrtStageEps n)
  have hBC : B <= (C : Rat) := by
    dsimp [B, C, sqrtWidthConstant]
    exact rat_le_num_natAbs_succ (sqrtUpperBound q)
  have hfuel_ge : n <= fuel := by
    dsimp [fuel]
    by_cases hn : n = 0
    · omega
    · rw [sqrtFuel_sqrtStageEps_eq q n hn]
      omega
  have hsucc_pow : n + 1 <= 2 ^ fuel := by
    exact Nat.le_trans (succ_le_two_pow n)
      (Nat.pow_le_pow_right (by omega : 0 < 2) hfuel_ge)
  have hden_pos : 0 < (((2 ^ fuel : Nat) : Rat)) := by
    exact (Rat.natCast_pos).2 (Nat.pow_pos (by omega : 0 < 2))
  have hone_den_nonneg : 0 <= 1 / (((2 ^ fuel : Nat) : Rat)) := by
    rw [Rat.div_def]
    exact Rat.le_of_lt (Rat.mul_pos (by decide +kernel : (0 : Rat) < 1)
      ((Rat.inv_pos).2 hden_pos))
  have hone :
      (1 / (((2 ^ fuel : Nat) : Rat))) <=
        1 / (((n + 1 : Nat) : Rat)) := by
    exact FTC.one_div_nat_antitone (Nat.succ_pos n)
      (Nat.pow_pos (by omega : 0 < 2)) hsucc_pow
  rw [sqrtApproxOnDomain_width_eq]
  dsimp [B, fuel] at *
  calc
    sqrtUpperBound q /
        (((2 ^ sqrtFuel q (sqrtStageEps n) : Nat) : Rat)) =
        B * (1 / (((2 ^ fuel : Nat) : Rat))) := by
      dsimp [B, fuel]
      rw [Rat.div_def, Rat.div_def]
      grind [Rat.mul_assoc, Rat.mul_comm]
    _ <= (C : Rat) * (1 / (((2 ^ fuel : Nat) : Rat))) := by
      exact Rat.mul_le_mul_of_nonneg_right hBC hone_den_nonneg
    _ <= (C : Rat) * (1 / (((n + 1 : Nat) : Rat))) := by
      exact Rat.mul_le_mul_of_nonneg_left hone Rat.natCast_nonneg
    _ = (sqrtWidthConstant q : Rat) / (((n + 1 : Nat) : Rat)) := by
      dsimp [C, sqrtWidthConstant]
      rw [Rat.div_def]
      grind [Rat.mul_assoc, Rat.mul_comm]

private theorem widthsShrink_of_natOverSuccBound_local
    {compute : Nat -> QInterval} {C : Nat}
    (hbound : forall n,
      (compute n).width <= (C : Rat) / (((n + 1 : Nat) : Rat))) :
    RealCompute.WidthsShrinkToZero compute := by
  intro eps
  refine ⟨C * (eps.val.den + 1), ?_⟩
  intro n hn
  have hmain :
      (C : Rat) / (((n + 1 : Nat) : Rat)) <=
        1 / (((eps.val.den + 1 : Nat) : Rat)) := by
    let A : Rat := ((n + 1 : Nat) : Rat)
    let B : Rat := ((eps.val.den + 1 : Nat) : Rat)
    let K : Rat := (C : Rat)
    have hApos : 0 < A := by
      dsimp [A]
      exact (Rat.natCast_pos).2 (Nat.succ_pos n)
    have hBpos : 0 < B := by
      dsimp [B]
      exact (Rat.natCast_pos).2 (Nat.succ_pos eps.val.den)
    have hAne : A ≠ 0 := Rat.ne_of_gt hApos
    have hBne : B ≠ 0 := Rat.ne_of_gt hBpos
    have hABpos : 0 < A * B := Rat.mul_pos hApos hBpos
    have hscaledRat : K * B <= A := by
      dsimp [A, B, K]
      exact_mod_cast (by omega :
        C * (eps.val.den + 1) <= n + 1)
    apply Rat.le_of_mul_le_mul_right (c := A * B)
    · calc
        (K / A) * (A * B) = K * B := by
          rw [Rat.div_def]
          have hcancel : A * A⁻¹ = 1 := Rat.mul_inv_cancel A hAne
          grind [Rat.mul_assoc, Rat.mul_comm]
        _ <= A := hscaledRat
        _ = (1 / B) * (A * B) := by
          rw [Rat.div_def]
          have hcancel : B * B⁻¹ = 1 := Rat.mul_inv_cancel B hBne
          grind [Rat.mul_assoc, Rat.mul_comm]
    · exact hABpos
  exact Rat.le_trans (hbound n)
    (Rat.le_trans hmain
      (FTC.one_div_den_succ_le_of_pos eps.property))

theorem sqrtApproxOnDomain_widthsShrink
    (q : Rat) (h : sqrtDomain q) :
    RealCompute.WidthsShrinkToZero (sqrtApproxOnDomain q h) :=
  widthsShrink_of_natOverSuccBound_local
    (sqrtApproxOnDomain_width_le_nat_over_succ q h)

theorem sqrtApproxOnDomain_ordered (q : Rat) (h : sqrtDomain q) (n : Nat) :
    0 <= (sqrtApproxOnDomain q h n).width := by
  have hspec := sqrtApproxOnDomain_spec q h n
  unfold SqrtIntervalSpec at hspec
  unfold QInterval.width
  grind

theorem sqrtApproxOnDomain_contains_of_le
    (q : Rat) (h : sqrtDomain q) {n m : Nat} (hnm : n <= m) :
    (sqrtApproxOnDomain q h n).ContainsInterval
      (sqrtApproxOnDomain q h m) := by
  have hq : 0 <= q := by
    unfold sqrtDomain at h
    grind
  unfold sqrtApproxOnDomain
  exact sqrtBisect_contains_of_le_fuel (sqrtInitialSpec hq)
    (sqrtFuel_sqrtStageEps_mono q hnm)

/-- Every finite square-root bisection box remains inside its explicit
initial interval.  This public endpoint bound is useful when a later
calculus certificate must control products of the finite endpoints. -/
theorem sqrtApproxOnDomain_hi_le_upperBound
    (q : Rat) (h : sqrtDomain q) (n : Nat) :
    (sqrtApproxOnDomain q h n).hi <= sqrtUpperBound q := by
  have hq0 : 0 <= q := by
    unfold sqrtDomain at h
    grind
  have hcontains :
      ({ lo := 0, hi := sqrtUpperBound q } : QInterval).ContainsInterval
        (sqrtApproxOnDomain q h n) := by
    unfold sqrtApproxOnDomain
    exact sqrtBisect_contains_of_le_fuel (sqrtInitialSpec hq0) (Nat.zero_le _)
  exact hcontains.2

theorem sqrtApproxOnDomain_nested
    (q : Rat) (h : sqrtDomain q) :
    forall n m, n <= m ->
      (sqrtApproxOnDomain q h n).lo <=
        (sqrtApproxOnDomain q h m).lo /\
      (sqrtApproxOnDomain q h m).lo <=
        (sqrtApproxOnDomain q h m).hi /\
      (sqrtApproxOnDomain q h m).hi <=
        (sqrtApproxOnDomain q h n).hi := by
  intro n m hnm
  have hcontains := sqrtApproxOnDomain_contains_of_le q h hnm
  have hspecm := sqrtApproxOnDomain_spec q h m
  unfold QInterval.ContainsInterval at hcontains
  exact ⟨hcontains.1, hspecm.2.1, hcontains.2⟩

theorem sqrtApproxOnDomain_valid (q : Rat) (h : sqrtDomain q) :
    RealCompute.ValidCompute (sqrtApproxOnDomain q h) := by
  exact ⟨sqrtApproxOnDomain_ordered q h,
    sqrtApproxOnDomain_nested q h,
    sqrtApproxOnDomain_widthsShrink q h⟩

theorem sqrtRaw_valid (q : Rat) (h : sqrtDomain q) :
    (sqrtRaw q h).Valid := by
  change RealCompute.ValidCompute (sqrtApproxOnDomain q h)
  exact sqrtApproxOnDomain_valid q h

theorem sqrtRaw_spec (q : Rat) (h : sqrtDomain q) :
    SqrtRawSpec q h :=
  ⟨sqrtRaw_valid q h, sqrtRaw_stage_spec q h⟩

/-! The square-root specification is strong enough to recover the defining
equation at the raw-real level.  This is the algebraic invariant used by the
constructive half-angle induction: it compares rational intervals directly,
without selecting an exact real square root. -/
theorem sqrtRaw_mul_self_equiv_of_domain (q : Rat) (h : sqrtDomain q) :
    (sqrtRaw q h * sqrtRaw q h).Equiv (RealCompute.ofRat q) := by
  intro n
  have hsvalid := sqrtRaw_valid q h
  have horder := RealCompute.interval_order_of_valid (sqrtRaw q h) hsvalid n
  have hspec := sqrtRaw_stage_spec q h n
  apply (RealCompute.compareAt_overlap_iff
    (sqrtRaw q h * sqrtRaw q h) (RealCompute.ofRat q) n n).2
  change QInterval.Overlaps
    (QBox.mulRealInterval
      ((sqrtRaw q h).compute n).lo
      ((sqrtRaw q h).compute n).hi
      ((sqrtRaw q h).compute n).lo
      ((sqrtRaw q h).compute n).hi)
    { lo := q, hi := q }
  rw [QBox.mulRealInterval_self_of_nonneg hspec.1 horder]
  unfold QInterval.Overlaps
  exact ⟨hspec.2.2.1, hspec.2.2.2⟩

theorem ofRat_add_equiv (a b : Rat) :
    (RealCompute.ofRat a + RealCompute.ofRat b).Equiv
      (RealCompute.ofRat (a + b)) := by
  intro n
  apply (RealCompute.compareAt_overlap_iff
    (RealCompute.ofRat a + RealCompute.ofRat b)
    (RealCompute.ofRat (a + b)) n n).2
  change QInterval.Overlaps
    { lo := a + b, hi := a + b }
    { lo := a + b, hi := a + b }
  exact ⟨by grind, by grind⟩

/-! Raw-real form of the elementary circle identity.  This separates the
algebraic part of the half-angle proof from the geometric theorem that
constructs the two square-root representatives. -/
theorem raw_square_sum_equiv_of_rational_square_sum
    {s c : RealCompute} {q r : Rat}
    (hss : (s * s).Valid) (hcc : (c * c).Valid)
    (hsq : (s * s).Equiv (RealCompute.ofRat q))
    (hcq : (c * c).Equiv (RealCompute.ofRat r))
    (hsum : q + r = 1) :
    (s * s + c * c).Equiv (RealCompute.ofRat 1) := by
  have hqvalid : (RealCompute.ofRat q).Valid := by
    unfold RealCompute.ofRat RealCompute.Valid
    exact RealCompute.ofRat_valid q
  have hrvalid : (RealCompute.ofRat r).Valid := by
    unfold RealCompute.ofRat RealCompute.Valid
    exact RealCompute.ofRat_valid r
  have honevalid : (RealCompute.ofRat (1 : Rat)).Valid := by
    unfold RealCompute.ofRat RealCompute.Valid
    exact RealCompute.ofRat_valid 1
  have hadd := RealCompute.add_equiv hss
    hqvalid hcc hrvalid hsq hcq
  have hrat := ofRat_add_equiv q r
  rw [hsum] at hrat
  have hmid : (RealCompute.ofRat q + RealCompute.ofRat r).Valid :=
    RealCompute.add_valid hqvalid hrvalid
  exact RealCompute.equiv_trans
    (RealCompute.add_valid hss hcc)
    hmid honevalid
    hadd hrat

theorem sqrtRaw_equiv_of_spec {q : Rat} (h : sqrtDomain q)
    {x : RealCompute} (hx : SqrtRealComputeSpec q x) :
    (sqrtRaw q h).Equiv x := by
  exact sqrt_spec_equiv_of_spec (sqrtRaw_spec q h) hx

theorem sqrtCertified_of_domain (q : Rat) (h : sqrtDomain q) :
    sqrtCertified? q := by
  unfold sqrtCertified? sqrtCompute?
  simp
  refine ⟨sqrtPartialRaw.compute q h, ?_, ?_⟩
  · exact ⟨h, rfl⟩
  · exact sqrtApproxOnDomain_valid q h

theorem sq_le_sq_of_nonneg_le {a b : Rat} (ha : 0 <= a) (hab : a <= b) :
    sq a <= sq b := by
  have hb : 0 <= b := Rat.le_trans ha hab
  unfold sq
  calc
    a * a <= b * a := Rat.mul_le_mul_of_nonneg_right hab ha
    _ <= b * b := Rat.mul_le_mul_of_nonneg_left hab hb

theorem sq_qabs (x : Rat) :
    sq (qabs x) = sq x := by
  unfold qabs sq
  by_cases hneg : x < 0
  case pos =>
    simp [hneg]
    grind [Rat.neg_mul, Rat.mul_neg, Rat.neg_neg]
  case neg =>
    simp [hneg]

theorem sq_sub_factor (lo hi : Rat) :
    sq hi - sq lo = (hi - lo) * (hi + lo) := by
  unfold sq
  grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm,
    Rat.mul_assoc, Rat.mul_comm, Rat.sub_eq_add_neg]

theorem sq_lt_sq_of_nonneg_lt {a b : Rat} (ha : 0 <= a) (hab : a < b) :
    sq a < sq b := by
  have hdiff : 0 < sq b - sq a := by
    rw [sq_sub_factor]
    exact Rat.mul_pos (by grind) (by grind)
  grind

theorem sqrt_spec_sq_gap_le_stage_bound {q r : Rat} {x : RealCompute}
    (hx : SqrtRealComputeSpec q x)
    (hover : x.SameStageOverlap (RealCompute.ofRat r))
    (n : Nat) :
    qabs (sq r - q) <=
      (x.compute n).width * (2 * (x.compute 0).hi + 1) := by
  have hspec := hx.2 n
  have hr : (x.compute n).lo <= r /\ r <= (x.compute n).hi := by
    have h := (RealCompute.compareAt_overlap_iff x (RealCompute.ofRat r) n n).1
      (hover n)
    simpa [RealCompute.ofRat, QInterval.Overlaps] using h
  have hsq_lo_r : sq (x.compute n).lo <= sq r :=
    sq_le_sq_of_nonneg_le hspec.1 hr.1
  have hr_nonneg : 0 <= r := Rat.le_trans hspec.1 hr.1
  have hsq_r_hi : sq r <= sq (x.compute n).hi :=
    sq_le_sq_of_nonneg_le hr_nonneg hr.2
  have hgapStage :
      qabs (sq r - q) <= sq (x.compute n).hi - sq (x.compute n).lo :=
    qabs_sub_le_of_common_bounds
      hsq_lo_r hsq_r_hi hspec.2.2.1 hspec.2.2.2
  have hnest := hx.1.2.1 0 n (Nat.zero_le n)
  have hsum :
      (x.compute n).hi + (x.compute n).lo <=
        2 * (x.compute 0).hi + 1 := by
    have hlo_le_hi0 : (x.compute n).lo <= (x.compute 0).hi :=
      Rat.le_trans hspec.2.1 hnest.2.2
    have hhi_le_hi0 : (x.compute n).hi <= (x.compute 0).hi := hnest.2.2
    grind
  have hwidth_nonneg : 0 <= (x.compute n).hi - (x.compute n).lo := by
    simpa [QInterval.width] using hx.1.1 n
  have hprod :
      sq (x.compute n).hi - sq (x.compute n).lo <=
        (x.compute n).width * (2 * (x.compute 0).hi + 1) := by
    rw [sq_sub_factor, QInterval.width]
    exact Rat.mul_le_mul_of_nonneg_left hsum hwidth_nonneg
  exact Rat.le_trans hgapStage hprod

theorem eq_of_qabs_sub_le_width_mul_of_valid {a b C : Rat} {x : RealCompute}
    (hx : x.Valid) (hCpos : 0 < C)
    (hbound : forall n, qabs (a - b) <= (x.compute n).width * C) :
    a = b := by
  by_cases hEq : a = b
  case pos => exact hEq
  case neg =>
    exfalso
    let gap : Rat := qabs (a - b)
    have hdiff_ne : Not (a - b = 0) := by
      intro hzero
      apply hEq
      grind
    have hgap_pos : 0 < gap := by
      dsimp [gap]
      exact qabs_pos_of_ne hdiff_ne
    have htwoCpos : 0 < 2 * C := by grind
    have hepsPos : 0 < gap / (2 * C) := by
      rw [Rat.div_def]
      exact Rat.mul_pos hgap_pos ((Rat.inv_pos).2 htwoCpos)
    obtain ⟨N, hsmall⟩ := hx.2.2
      { val := gap / (2 * C), property := hepsPos }
    let n : Nat := N
    have hboundN : gap <= (x.compute n).width * C := by
      dsimp [gap]
      exact hbound n
    have hsmallN : (x.compute n).width <= gap / (2 * C) :=
      hsmall n (Nat.le_refl n)
    have hmul :
        (x.compute n).width * C <= (gap / (2 * C)) * C :=
      Rat.mul_le_mul_of_nonneg_right hsmallN (Rat.le_of_lt hCpos)
    have hgapLe : gap <= (gap / (2 * C)) * C :=
      Rat.le_trans hboundN hmul
    have hhalf : (gap / (2 * C)) * C = gap / 2 := by
      rw [Rat.div_def, Rat.div_def]
      have h2Cne : (2 * C : Rat) != 0 := by grind
      have h2ne : (2 : Rat) != 0 := by decide +kernel
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
    have hgapLeHalf : gap <= gap / 2 := by
      rw [hhalf] at hgapLe
      exact hgapLe
    have hhalfLt : gap / 2 < gap := by
      have htwo : (0 : Rat) < 2 := by decide +kernel
      rw [Rat.div_lt_iff htwo]
      grind
    have hgapLtHalf : gap < gap / 2 :=
      Rat.lt_of_le_of_ne hgapLeHalf (Rat.ne_of_gt hhalfLt)
    grind

theorem sq_eq_of_sqrt_spec_equiv_rat {q r : Rat} {x : RealCompute}
    (hx : SqrtRealComputeSpec q x)
    (heq : x.Equiv (RealCompute.ofRat r)) :
    sq r = q := by
  let C : Rat := 2 * (x.compute 0).hi + 1
  have hspec0 := hx.2 0
  have hhi0_nonneg : 0 <= (x.compute 0).hi :=
    Rat.le_trans hspec0.1 hspec0.2.1
  have hCpos : 0 < C := by
    dsimp [C]
    grind
  have hratValid : (RealCompute.ofRat r).Valid := by
    change RealCompute.ValidCompute (RealCompute.ofRat r).compute
    exact RealCompute.ofRat_valid r
  have hover := RealCompute.sameStageOverlap_of_equiv hx.1 hratValid heq
  exact eq_of_qabs_sub_le_width_mul_of_valid hx.1 hCpos (by
    intro n
    dsimp [C]
    exact sqrt_spec_sq_gap_le_stage_bound hx hover n)

/-- Squaring as an exact rational interval function.  This is the forward map
for the first concrete inverse-function example: its inverse on the
nonnegative unit interval is the existing square-root bisection algorithm. -/
def squareRaw : PartialRealFunRaw where
  definedAt := fun _ => True
  compute := fun x _ _ => { lo := sq x, hi := sq x }

theorem squareRaw_valid (x : Rat) (hx : squareRaw.definedAt x) :
    RealCompute.ValidCompute (squareRaw.compute x hx) := by
  simpa [squareRaw] using RealCompute.ofRat_valid (sq x)

/-- The exact squaring function restricted to the nonnegative unit interval. -/
def squareOnUnit : FunctionOnInterval where
  raw := squareRaw
  lower := 0
  upper := 1
  defined_on := by
    intro _ _
    trivial
  valid_on := by
    intro x hx
    exact squareRaw_valid x hx

/-- Endpoint evaluation is an enclosure for squaring on a nonnegative input
interval. -/
def squareUnitEvalInterval (I : QInterval) : QInterval :=
  { lo := sq I.lo, hi := sq I.hi }

theorem squareUnitEvalInterval_width (I : QInterval) :
    (squareUnitEvalInterval I).width = I.width * (I.hi + I.lo) := by
  unfold squareUnitEvalInterval QInterval.width sq
  grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
    Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]

private theorem squareUnit_interval_width_scale (w : Rat) (n : Nat)
    (hn : n ≠ 0)
    (hw : w <= 1 / ((2 * n : Nat) : Rat)) :
    2 * w <= 1 / (n : Rat) := by
  calc
    2 * w <= 2 * (1 / ((2 * n : Nat) : Rat)) :=
      Rat.mul_le_mul_of_nonneg_left hw (by decide)
    _ = 1 / (n : Rat) := by
      rw [Rat.div_def]
      rw [show ((2 * n : Nat) : Rat) = (2 : Rat) * (n : Rat) by
        exact Rat.natCast_mul 2 n]
      have htwo : (2 : Rat) ≠ 0 := by decide
      have hn' : (n : Rat) ≠ 0 :=
        Rat.ne_of_gt ((Rat.natCast_pos).2 (Nat.pos_of_ne_zero hn))
      rw [Rat.inv_mul_rev]
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]

/-- Squaring is interval-regular on `[0,1]`, with a direct rational modulus.
The `n + 1` target convention lets stage zero retain a positive finite error
budget, as required for non-exact interval functions such as square root. -/
def squareOnUnit_intervalRegular : IntervalRegularOn squareOnUnit := by
  refine
    { evalInterval := fun I _ _ => squareUnitEvalInterval I
      inputPrecision := fun n => 2 * (n + 1)
      inputPrecision_pos := by
        intro n
        omega
      output_width := ?_
      contains_point_values := ?_ }
  · intro I hI n hwidth
    rcases hI with ⟨hlo, hord, hhi⟩
    have hwidth_nonneg : 0 <= I.width := by
      unfold QInterval.width
      grind [Rat.sub_eq_add_neg]
    have hsum_nonneg : 0 <= I.hi + I.lo := by
      have hhi_nonneg : 0 <= I.hi := Rat.le_trans hlo hord
      exact Rat.add_nonneg hhi_nonneg hlo
    have hsum_le_two : I.hi + I.lo <= 2 := by
      change (0 : Rat) <= I.lo at hlo
      change I.hi <= 1 at hhi
      grind
    constructor
    · rw [squareUnitEvalInterval_width]
      exact Rat.mul_nonneg hwidth_nonneg hsum_nonneg
    · rw [squareUnitEvalInterval_width]
      calc
        I.width * (I.hi + I.lo) <= I.width * 2 :=
          Rat.mul_le_mul_of_nonneg_left hsum_le_two hwidth_nonneg
        _ = 2 * I.width := by grind [Rat.mul_comm]
        _ <= 1 / (((n + 1 : Nat) : Rat)) :=
          squareUnit_interval_width_scale I.width (n + 1)
            (Nat.succ_ne_zero n) hwidth
  · intro I hI x hx n hxlo hxhi
    rcases hI with ⟨hIlo, hord, hIhi⟩
    change (0 : Rat) <= I.lo at hIlo
    have hlo_nonneg : 0 <= I.lo := hIlo
    have hx_nonneg : 0 <= x := Rat.le_trans hlo_nonneg hxlo
    have hlo_sq : sq I.lo <= sq x :=
      sq_le_sq_of_nonneg_le hlo_nonneg hxlo
    have hhi_sq : sq x <= sq I.hi :=
      sq_le_sq_of_nonneg_le hx_nonneg hxhi
    change squareUnitEvalInterval I |>.ContainsInterval
      (squareOnUnit.compute x hx n)
    change QInterval.ContainsInterval
      { lo := sq I.lo, hi := sq I.hi }
      { lo := sq x, hi := sq x }
    exact ⟨hlo_sq, hhi_sq⟩

/-- The concrete continuous squaring map used by the unit square-root
inverse example. -/
def squareOnUnit_continuous : ContinuousFunctionOnInterval where
  function := squareOnUnit
  regular := squareOnUnit_intervalRegular

/-- The square map on the unit interval satisfies the project's literal
rational epsilon--delta continuity predicate, without a topology import. -/
theorem squareOnUnit_epsilonDeltaContinuous :
    EpsilonDeltaContinuousOn squareOnUnit :=
  squareOnUnit_intervalRegular.epsilonDeltaContinuous

theorem squareOnUnit_nondecreasing : NondecreasingOnInterval squareOnUnit := by
  intro x y hx hy hxy _
  have hx_nonneg : 0 <= x := hx.1
  have hsq : sq x <= sq y := sq_le_sq_of_nonneg_le hx_nonneg hxy
  change sq x <= sq y
  exact hsq

/-- On `[0,1]`, a separation of `1/(n+1)` in the input strictly separates the
exact output boxes after squaring.  This is the nondecreasing effective
inverse-separation certificate. -/
def squareOnUnit_effectiveInverseSeparation :
    EffectiveInverseSeparation squareOnUnit where
  kind := .nondecreasing
  inputPrecision := fun n => n + 1
  inputPrecision_pos := fun n => Nat.succ_pos n
  outputPrecision := fun _ => 0
  separated := by
    intro x y hx hy n hsep
    have hx_nonneg : 0 <= x := hx.1
    have hstep_pos : 0 < (1 / (((n + 1 : Nat) : Rat))) :=
      one_div_nat_pos (Nat.succ_pos n)
    have hxy : x < y := by
      grind
    have hsq : sq x < sq y := sq_lt_sq_of_nonneg_lt hx_nonneg hxy
    change sq x < sq y
    exact hsq

/-- The unit-interval square map supplies the constructive data required by
the monotone inverse-function interface. -/
def squareOnUnit_invertible : InvertibleFunctionOnInterval where
  continuous := squareOnUnit_continuous
  source_ordered := by decide +kernel
  monotone := MonotoneOnInterval.ofNondecreasing squareOnUnit_nondecreasing
  separation := squareOnUnit_effectiveInverseSeparation
  orientation := trivial

/-- A rational target in the unit range of squaring, represented by its exact
rational point box and enclosed by the exact endpoint values of the square
branch. -/
def squareOnUnitRationalTarget (q : Rat) (hq : inDomainInterval 0 1 q) :
    InRangeRaw squareOnUnit_invertible where
  value := RealCompute.ofRat q
  value_valid := by
    change RealCompute.ValidCompute (RealCompute.ofRat q).compute
    exact RealCompute.ofRat_valid q
  rangePrecision := fun _ => 0
  in_range := by
    intro n
    change 0 <= q ∧ q <= 1 at hq
    simpa [InvertibleFunctionOnInterval.EndpointRangeContains,
      InvertibleFunctionOnInterval.function,
      InvertibleFunctionOnInterval.lowerValueBox,
      InvertibleFunctionOnInterval.upperValueBox,
      FunctionOnInterval.compute,
      squareOnUnit_invertible, squareOnUnit_continuous,
      squareOnUnit_effectiveInverseSeparation,
      squareOnUnit, squareRaw, sq, RealCompute.ofRat] using hq

private theorem sqrtDomain_of_unit {q : Rat} (hq : inDomainInterval 0 1 q) :
    sqrtDomain q := by
  unfold sqrtDomain
  change 0 <= q /\ q <= 1 at hq
  grind

/-- The rational square-root bisection never leaves `[0,1]` for a rational
target in `[0,1]`. -/
theorem sqrtApproxOnUnit_subinterval (q : Rat) (hq : inDomainInterval 0 1 q)
    (n : Nat) :
    subintervalOf (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n) 0 1 := by
  have hcontains :
      ({ lo := 0, hi := sqrtUpperBound q } : QInterval).ContainsInterval
        (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n) := by
    unfold sqrtApproxOnDomain
    exact sqrtBisect_contains_of_le_fuel (sqrtInitialSpec hq.1) (Nat.zero_le _)
  have hspec := sqrtApproxOnDomain_spec q (sqrtDomain_of_unit hq) n
  unfold QInterval.ContainsInterval at hcontains
  refine ⟨hcontains.1, hspec.2.1, ?_⟩
  simpa [sqrtUpperBound_eq_one hq.2] using hcontains.2

theorem sqrtRaw_halfAngle_square_sum_equiv_one
    {q r : Rat}
    (hq : inDomainInterval 0 1 q)
    (hr : inDomainInterval 0 1 r)
    (hsum : q + r = 1) :
    ((sqrtRaw q (sqrtDomain_of_unit hq) *
        sqrtRaw q (sqrtDomain_of_unit hq)) +
      (sqrtRaw r (sqrtDomain_of_unit hr) *
        sqrtRaw r (sqrtDomain_of_unit hr))).Equiv
      (RealCompute.ofRat 1) := by
  have hqvalid : (sqrtRaw q (sqrtDomain_of_unit hq) *
      sqrtRaw q (sqrtDomain_of_unit hq)).Valid := by
    apply RealCompute.mulSelf_valid_of_nonneg_bounded
      (B := (1 : Rat))
      (sqrtRaw_valid q (sqrtDomain_of_unit hq)) (by decide +kernel)
    intro n
    have hsub := sqrtApproxOnUnit_subinterval q hq n
    simpa [sqrtRaw] using (show
      0 <= (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n).lo /\
        (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n).hi <= 1 from
      ⟨hsub.1, hsub.2.2⟩)
  have hrvalid : (sqrtRaw r (sqrtDomain_of_unit hr) *
      sqrtRaw r (sqrtDomain_of_unit hr)).Valid := by
    apply RealCompute.mulSelf_valid_of_nonneg_bounded
      (B := (1 : Rat))
      (sqrtRaw_valid r (sqrtDomain_of_unit hr)) (by decide +kernel)
    intro n
    have hsub := sqrtApproxOnUnit_subinterval r hr n
    simpa [sqrtRaw] using (show
      0 <= (sqrtApproxOnDomain r (sqrtDomain_of_unit hr) n).lo /\
        (sqrtApproxOnDomain r (sqrtDomain_of_unit hr) n).hi <= 1 from
      ⟨hsub.1, hsub.2.2⟩)
  apply raw_square_sum_equiv_of_rational_square_sum hqvalid hrvalid
  · exact sqrtRaw_mul_self_equiv_of_domain q (sqrtDomain_of_unit hq)
  · exact sqrtRaw_mul_self_equiv_of_domain r (sqrtDomain_of_unit hr)
  · exact hsum

/-- The existing rational square-root bisection is a concrete inverse search
for each exact rational target in the unit range of squaring. -/
def sqrtOnUnitBisectionSearch (q : Rat) (hq : inDomainInterval 0 1 q) :
    InverseBisectionSearch squareOnUnit_invertible
      (squareOnUnitRationalTarget q hq) where
  compute_preimage := sqrtApproxOnDomain q (sqrtDomain_of_unit hq)
  valid_preimage := sqrtApproxOnDomain_valid q (sqrtDomain_of_unit hq)
  preimage_subinterval := sqrtApproxOnUnit_subinterval q hq
  value_overlaps := by
    intro n
    have hspec := sqrtApproxOnDomain_spec q (sqrtDomain_of_unit hq) n
    change sq (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n).lo <= q /\
      q <= sq (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) n).hi
    exact ⟨hspec.2.2.1, hspec.2.2.2⟩

/-- A represented target with an explicit rational anchor can reuse the
existing square-root bisection trace.  The anchor is not a chosen exact real
root: it is finite input data together with an `Equiv` certificate saying
that the target representative and the rational point overlap at every
stage.  The value-overlap field is then transported through the common
rational point, so this remains a represented-target certificate rather than
an appeal to a completed-real inverse or an IVT. -/
def sqrtOnUnitRepresentedTargetSearch
    (y : InRangeRaw squareOnUnit_invertible)
    (q : Rat) (hq : inDomainInterval 0 1 q)
    (heq : y.value.Equiv (RealCompute.ofRat q)) :
    InverseBisectionSearch squareOnUnit_invertible y where
  compute_preimage := (sqrtOnUnitBisectionSearch q hq).compute_preimage
  valid_preimage := (sqrtOnUnitBisectionSearch q hq).valid_preimage
  preimage_subinterval := (sqrtOnUnitBisectionSearch q hq).preimage_subinterval
  value_overlaps := by
    intro n
    let E := squareOnUnit_invertible.continuous.regular.evalInterval
      ((sqrtOnUnitBisectionSearch q hq).compute_preimage n)
      ((sqrtOnUnitBisectionSearch q hq).preimage_subinterval n) n
    have hEq : QInterval.Overlaps E ((RealCompute.ofRat q).compute n) := by
      change QInterval.Overlaps E ((RealCompute.ofRat q).compute n)
      exact (sqrtOnUnitBisectionSearch q hq).value_overlaps n
    have hE : E.lo <= q /\ q <= E.hi := by
      simpa [RealCompute.ofRat, QInterval.Overlaps] using hEq
    have hTarget : QInterval.Overlaps
        (y.value.compute n) ((RealCompute.ofRat q).compute n) := by
      exact (RealCompute.compareAt_overlap_iff y.value (RealCompute.ofRat q) n n).1
        (heq n)
    have hY : (y.value.compute n).lo <= q /\ q <= (y.value.compute n).hi := by
      simpa [RealCompute.ofRat, QInterval.Overlaps] using hTarget
    change QInterval.Overlaps E (y.value.compute n)
    unfold QInterval.Overlaps
    exact ⟨Rat.le_trans hE.1 hY.2, Rat.le_trans hY.1 hE.2⟩

/- A represented-target stage certificate.  The rational anchor supplies the
endpoint-square bracket and width budget, while the transported target field
supplies the actual overlap with the represented value. -/
theorem sqrtOnUnitRepresentedTargetSearch_stage_certificate
    (y : InRangeRaw squareOnUnit_invertible)
    (q : Rat) (hq : inDomainInterval 0 1 q)
    (heq : y.value.Equiv (RealCompute.ofRat q))
    (n : Nat) (hn : n ≠ 0) (eps : Rat)
    (hbudget : 1 / (((2 ^ (n + 9) : Nat) : Rat)) <= eps) :
    let search := sqrtOnUnitRepresentedTargetSearch y q hq heq
    let I := search.compute_preimage n
    subintervalOf I 0 1 /\
      I.lo * I.lo <= q /\
      q <= I.hi * I.hi /\
      I.width <= eps /\
      QInterval.Overlaps
        (squareOnUnit_invertible.continuous.regular.evalInterval I
          (search.preimage_subinterval n) n)
        (y.value.compute n) := by
  have hdomain : sqrtDomain q := by
    exact sqrtDomain_of_unit hq
  have hsub := sqrtApproxOnUnit_subinterval q hq n
  have hspec := sqrtApproxOnDomain_spec q hdomain n
  have hwidth := sqrtApproxOnDomain_width_eq_unit hdomain hq.2 n hn
  have hover :=
    (sqrtOnUnitRepresentedTargetSearch y q hq heq).value_overlaps n
  dsimp [sqrtOnUnitRepresentedTargetSearch]
  refine ⟨hsub, hspec.2.2.1, hspec.2.2.2, ?_, hover⟩
  change (sqrtApproxOnDomain q hdomain n).width <= eps
  rw [hwidth]
  exact hbudget

/-- A logarithmic number of bisections suffices for the unit branch's
reciprocal-stage error budget. Keep the schedule opaque to interval elaboration. -/
@[irreducible] def sqrtOnUnitStage (n : Nat) : Nat := Nat.log2 (32*(n+1))+1

def sqrtOnUnitSchedule : RealCompute.StageSchedule where
  stage := sqrtOnUnitStage
  monotone := by
    intro i j hij
    unfold sqrtOnUnitStage
    have hi : 32*(i+1) ≠ 0 := by omega
    have hj : 32*(j+1) ≠ 0 := by omega
    have hm : 32*(i+1) ≤ 32*(j+1) := by omega
    have hl := (Nat.le_log2 hj).2 (Nat.le_trans (Nat.log2_self_le hi) hm)
    omega
  cofinal := by
    intro target
    refine ⟨2^target, ?_⟩
    unfold sqrtOnUnitStage
    have hn : (32*(2^target+1):Nat) ≠ 0 :=
      Nat.ne_of_gt (Nat.mul_pos (by decide +kernel) (Nat.succ_pos (2^target)))
    have hl := (Nat.le_log2 hn).2 (by omega : 2^target ≤ 32*(2^target+1))
    omega

/-- Square root as a represented rational-domain function on `[0,1]`.  At a
point it is the existing certified rational bisection algorithm, merely read
through `sqrtOnUnitSchedule`; hence it introduces neither an ambient real
number nor a completeness principle. -/
def sqrtOnUnit : FunctionOnInterval where
  raw :=
    { definedAt := sqrtDomain
      compute := fun q h n =>
        (sqrtApproxOnDomain q h (sqrtOnUnitSchedule.stage n)) }
  lower := 0
  upper := 1
  defined_on := by
    intro q hq
    exact sqrtDomain_of_unit hq
  valid_on := by
    intro q hq
    have hscheduled := RealCompute.schedule_valid
      (sqrtRaw q hq) (sqrtRaw_valid q hq) sqrtOnUnitSchedule
    change RealCompute.ValidCompute
      (fun n => sqrtApproxOnDomain q hq (sqrtOnUnitSchedule.stage n)) at hscheduled
    exact hscheduled

/-- Point evaluation of the unit square-root branch is exactly the scheduled
rational bisection box. -/
theorem sqrtOnUnit_compute (q : Rat) (hq : inDomainInterval 0 1 q) (n : Nat) :
    sqrtOnUnit.compute q hq n =
      sqrtApproxOnDomain q (sqrtDomain_of_unit hq) (sqrtOnUnitSchedule.stage n) :=
  rfl

/-- Rescheduling the unit branch preserves the value of the original
certified rational square-root computation. -/
theorem sqrtOnUnit_agrees_raw (q : Rat) (hq : inDomainInterval 0 1 q) :
    (sqrtOnUnit.raw.evalRaw q (sqrtDomain_of_unit hq)).Equiv
      (sqrtRaw q (sqrtDomain_of_unit hq)) := by
  intro n
  simpa only [sqrtOnUnit, PartialRealFunRaw.evalRaw, sqrtRaw,
    RealCompute.schedule, RealCompute.compareAt] using
    (RealCompute.equiv_symm (RealCompute.schedule_equiv
      (sqrtRaw q (sqrtDomain_of_unit hq))
      (sqrtRaw_valid q (sqrtDomain_of_unit hq)) sqrtOnUnitSchedule)) n

/-- On the unit input range the generic bisection width constant is the
literal finite constant two. -/
private theorem sqrtWidthConstant_eq_two_on_unit
    {q : Rat} (hq : inDomainInterval 0 1 q) :
    sqrtWidthConstant q = 2 := by
  simp [sqrtWidthConstant, sqrtUpperBound_eq_one hq.2]

/-- A unit-range bisection box at stage `m` has width at most `2/(m+1)`.
This is the uniform quantitative fact used by the interval evaluator below. -/
private theorem sqrtApproxOnUnit_width_le_two_over_succ
    (q : Rat) (hq : inDomainInterval 0 1 q) (m : Nat) :
    (sqrtApproxOnDomain q (sqrtDomain_of_unit hq) m).width <=
      2 / (((m + 1 : Nat) : Rat)) := by
  have h := sqrtApproxOnDomain_width_le_nat_over_succ q
    (sqrtDomain_of_unit hq) m
  rw [sqrtWidthConstant_eq_two_on_unit hq] at h
  exact h

/-- The scheduled unit square-root point boxes fit within the explicit
`1/(32(n+1))` local error budget. -/
private theorem sqrtOnUnit_width_le_errorBudget
    (q : Rat) (hq : inDomainInterval 0 1 q) (n : Nat) :
    (sqrtOnUnit.compute q hq n).width <=
      1 / ((32 * (n + 1 : Nat) : Nat) : Rat) := by
  rw [sqrtOnUnit_compute]
  have hn : sqrtOnUnitSchedule.stage n ≠ 0 := by
    change sqrtOnUnitStage n ≠ 0
    unfold sqrtOnUnitStage
    omega
  rw [sqrtApproxOnDomain_width_eq_unit (sqrtDomain_of_unit hq) hq.2 _ hn]
  have hstage : 32*(n+1) ≤ 2^(sqrtOnUnitSchedule.stage n) := by
    have ht := Nat.lt_log2_self (n := 32*(n+1))
    change 32*(n+1) ≤ 2^(sqrtOnUnitStage n)
    unfold sqrtOnUnitStage
    omega
  have hp : 2^(sqrtOnUnitSchedule.stage n) ≤ 2^(sqrtOnUnitSchedule.stage n+9) :=
    Nat.pow_le_pow_right (by decide +kernel : 1≤2) (by omega)
  exact FTC.one_div_nat_antitone
    (by omega : 0<32*(n+1))
    (Nat.pow_pos (by decide +kernel : 0<2)) (Nat.le_trans hstage hp)

/-- The explicit pointwise error budget for the scheduled unit square-root
branch. -/
private def sqrtUnitErrorBudget (n : Nat) : Rat :=
  1 / ((32 * (n + 1 : Nat) : Nat) : Rat)

/-- The input modulus used by the square-root interval evaluator.  The square
is essential near zero: square root is uniformly continuous on `[0,1]`, but
does not have a global linear modulus there. -/
private def sqrtUnitInputPrecision (n : Nat) : Nat :=
  16 * (n + 1) * (n + 1)

/-- An interval enclosure for all scheduled square-root point boxes over a
subinterval of `[0,1]`.  The endpoint bisections provide the main bracket;
the explicit pointwise budget makes it an enclosure for every rational point
between them. -/
private def sqrtUnitEvalInterval (I : QInterval)
    (hI : subintervalOf I 0 1) (n : Nat) : QInterval :=
  let hlo : inDomainInterval 0 1 I.lo := ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
  let hhi : inDomainInterval 0 1 I.hi := ⟨Rat.le_trans hI.1 hI.2.1, hI.2.2⟩
  { lo := (sqrtOnUnit.compute I.lo hlo n).lo - sqrtUnitErrorBudget n
    hi := (sqrtOnUnit.compute I.hi hhi n).hi + sqrtUnitErrorBudget n }

/-- The endpoint-expanded square-root interval contains every scheduled
pointwise bisection box in its input interval. -/
private theorem sqrtUnitEvalInterval_contains_point
    (I : QInterval) (hI : subintervalOf I 0 1)
    (x : Rat) (hx : inDomainInterval 0 1 x)
    (n : Nat) (hxlo : I.lo <= x) (hxhi : x <= I.hi) :
    (sqrtUnitEvalInterval I hI n).ContainsInterval
      (sqrtOnUnit.compute x hx n) := by
  let hlo : inDomainInterval 0 1 I.lo :=
    ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
  let hhi : inDomainInterval 0 1 I.hi :=
    ⟨Rat.le_trans hI.1 hI.2.1, hI.2.2⟩
  let A := sqrtOnUnit.compute I.lo hlo n
  let B := sqrtOnUnit.compute I.hi hhi n
  let Y := sqrtOnUnit.compute x hx n
  let D := sqrtUnitErrorBudget n
  have hA : SqrtIntervalSpec I.lo A := by
    dsimp [A]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.lo (sqrtDomain_of_unit hlo)
      (sqrtOnUnitSchedule.stage n)
  have hB : SqrtIntervalSpec I.hi B := by
    dsimp [B]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.hi (sqrtDomain_of_unit hhi)
      (sqrtOnUnitSchedule.stage n)
  have hY : SqrtIntervalSpec x Y := by
    dsimp [Y]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec x (sqrtDomain_of_unit hx)
      (sqrtOnUnitSchedule.stage n)
  have hYwidth : Y.width <= D := by
    dsimp [Y, D, sqrtUnitErrorBudget]
    exact sqrtOnUnit_width_le_errorBudget x hx n
  have hAlo_le_Yhi : A.lo <= Y.hi := by
    have hYhi_nonneg : 0 <= Y.hi := Rat.le_trans hY.1 hY.2.1
    apply le_of_sq_le_sq_of_nonneg_right hYhi_nonneg
    exact Rat.le_trans hA.2.2.1
      (Rat.le_trans hxlo hY.2.2.2)
  have hYlo_le_Bhi : Y.lo <= B.hi := by
    have hBhi_nonneg : 0 <= B.hi := Rat.le_trans hB.1 hB.2.1
    apply le_of_sq_le_sq_of_nonneg_right hBhi_nonneg
    exact Rat.le_trans hY.2.2.1
      (Rat.le_trans hxhi hB.2.2.2)
  have hlo : A.lo - D <= Y.lo := by
    unfold QInterval.width at hYwidth
    grind [Rat.sub_eq_add_neg]
  have hhi : Y.hi <= B.hi + D := by
    unfold QInterval.width at hYwidth
    grind [Rat.sub_eq_add_neg]
  unfold QInterval.ContainsInterval
  simp [sqrtUnitEvalInterval, A, B, Y, D, hlo, hhi]

/-! Public interface for interval-valued nested-radical algorithms.  The
implementation above deliberately keeps its scheduling details local; this
wrapper exposes only the finite enclosure contract needed by other
constructive algorithms, such as the dyadic sine table. -/

def sqrtOnUnitEvalInterval (I : QInterval)
    (hI : subintervalOf I 0 1) (n : Nat) : QInterval :=
  sqrtUnitEvalInterval I hI n

theorem sqrtOnUnitEvalInterval_contains_point
    (I : QInterval) (hI : subintervalOf I 0 1)
    (x : Rat) (hx : inDomainInterval 0 1 x)
    (n : Nat) (hxlo : I.lo <= x) (hxhi : x <= I.hi) :
    (sqrtOnUnitEvalInterval I hI n).ContainsInterval
      (sqrtOnUnit.compute x hx n) := by
  exact sqrtUnitEvalInterval_contains_point I hI x hx n hxlo hxhi

/-- A total executable wrapper for callers that are constructing an
interval recursively.  The fallback is never used once the caller has proved
the input interval lies in `[0,1]`; keeping it explicit makes the raw
algorithm total before that proof is attached. -/
def sqrtOnUnitEvalIntervalTotal (I : QInterval) (n : Nat) : QInterval :=
  if hI : 0 <= I.lo ∧ I.lo <= I.hi ∧ I.hi <= 1 then
    sqrtOnUnitEvalInterval I hI n
  else
    { lo := 0, hi := 1 }

theorem sqrtOnUnitEvalIntervalTotal_eq
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat) :
    sqrtOnUnitEvalIntervalTotal I n = sqrtOnUnitEvalInterval I hI n := by
  change 0 <= I.lo ∧ I.lo <= I.hi ∧ I.hi <= 1 at hI
  simp [sqrtOnUnitEvalIntervalTotal, hI]

theorem sqrtOnUnitEvalIntervalTotal_contains_point
    (I : QInterval) (hI : subintervalOf I 0 1)
    (x : Rat) (hx : inDomainInterval 0 1 x)
    (n : Nat) (hxlo : I.lo <= x) (hxhi : x <= I.hi) :
    (sqrtOnUnitEvalIntervalTotal I n).ContainsInterval
      (sqrtOnUnit.compute x hx n) := by
  rw [sqrtOnUnitEvalIntervalTotal_eq I hI n]
  exact sqrtOnUnitEvalInterval_contains_point I hI x hx n hxlo hxhi

/-! Clipping is harmless for the unit square-root branch: the exact point
box already lies in `[0,1]`, while clipping removes only error padding that
falls outside the geometric range. -/

theorem sqrtOnUnit_compute_subinterval
    (q : Rat) (hq : inDomainInterval 0 1 q) (n : Nat) :
    subintervalOf (sqrtOnUnit.compute q hq n) 0 1 := by
  rw [sqrtOnUnit_compute]
  exact sqrtApproxOnUnit_subinterval q hq
    (sqrtOnUnitSchedule.stage n)

def sqrtOnUnitEvalIntervalClipped (I : QInterval) (n : Nat) : QInterval :=
  QInterval.intersection
    (sqrtOnUnitEvalIntervalTotal I n) { lo := 0, hi := 1 }

theorem sqrtOnUnitEvalIntervalClipped_width_le_total
    (I : QInterval) (n : Nat) :
    (sqrtOnUnitEvalIntervalClipped I n).width <=
      (sqrtOnUnitEvalIntervalTotal I n).width := by
  apply QInterval.width_le_of_contains
  unfold sqrtOnUnitEvalIntervalClipped
  exact QInterval.intersection_contained_left
    (sqrtOnUnitEvalIntervalTotal I n) { lo := 0, hi := 1 }

theorem sqrtOnUnitEvalIntervalClipped_subinterval
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat) :
    subintervalOf (sqrtOnUnitEvalIntervalClipped I n) 0 1 := by
  let hx : inDomainInterval 0 1 I.lo :=
    ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
  have hpoint := sqrtOnUnit_compute_subinterval I.lo hx n
  have htotal := sqrtOnUnitEvalIntervalTotal_contains_point I hI I.lo hx n
    Rat.le_refl hI.2.1
  have hunit : QInterval.ContainsInterval
      { lo := 0, hi := 1 } (sqrtOnUnit.compute I.lo hx n) :=
    ⟨hpoint.1, hpoint.2.2⟩
  have hinter := QInterval.intersection_contains htotal hunit
  have hunitContained := QInterval.intersection_contained_right
    (sqrtOnUnitEvalIntervalTotal I n) { lo := 0, hi := 1 }
  unfold sqrtOnUnitEvalIntervalClipped subintervalOf
  exact ⟨hunitContained.1,
    Rat.le_trans hinter.1 (Rat.le_trans hpoint.2.1 hinter.2),
    hunitContained.2⟩

/-! The scheduled error padding cannot disappear under clipping.  This is
useful for recursive interval algorithms: every valid unit-branch square-root
box has a genuinely positive rational width, including at exact endpoint
inputs. -/
theorem sqrtOnUnitEvalIntervalClipped_width_pos
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat) :
    0 < (sqrtOnUnitEvalIntervalClipped I n).width := by
  change 0 < (QInterval.intersection
    (sqrtOnUnitEvalIntervalTotal I n) { lo := 0, hi := 1 }).width
  rw [sqrtOnUnitEvalIntervalTotal_eq I hI n]
  let hlo : inDomainInterval 0 1 I.lo :=
    ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
  let hhi : inDomainInterval 0 1 I.hi :=
    ⟨Rat.le_trans hI.1 hI.2.1, hI.2.2⟩
  let A := sqrtOnUnit.compute I.lo hlo n
  let B := sqrtOnUnit.compute I.hi hhi n
  let D := sqrtUnitErrorBudget n
  have hA := sqrtOnUnit_compute_subinterval I.lo hlo n
  have hB := sqrtOnUnit_compute_subinterval I.hi hhi n
  have hAs : SqrtIntervalSpec I.lo A := by
    dsimp [A]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.lo (sqrtDomain_of_unit hlo)
      (sqrtOnUnitSchedule.stage n)
  have hBs : SqrtIntervalSpec I.hi B := by
    dsimp [B]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.hi (sqrtDomain_of_unit hhi)
      (sqrtOnUnitSchedule.stage n)
  have hcross : A.lo <= B.hi := by
    have hsq : sq A.lo <= I.hi :=
      Rat.le_trans hAs.2.2.1 hI.2.1
    exact hBs.le_hi_of_sq_le hsq
  have hD : 0 < D := by
    dsimp [D, sqrtUnitErrorBudget]
    exact one_div_nat_pos (by omega)
  have hleft : A.lo - D < 1 := by
    have hAle : A.lo <= 1 := by
      dsimp [A]
      exact Rat.le_trans hA.2.1 hA.2.2
    grind
  have hright : 0 < B.hi + D := by
    have hBge : 0 <= B.hi := by
      dsimp [B]
      exact Rat.le_trans hB.1 hB.2.1
    grind
  unfold sqrtOnUnitEvalInterval sqrtUnitEvalInterval
  simp only [A, B, D]
  unfold QInterval.intersection QInterval.width
  by_cases hlo' : (sqrtOnUnit.compute I.lo hlo n).lo -
      sqrtUnitErrorBudget n <= 0
  · simp [Rat.max_def, hlo']
    by_cases hhi' : (sqrtOnUnit.compute I.hi hhi n).hi +
        sqrtUnitErrorBudget n <= 1
    · simp [Rat.min_def, hhi']
      grind
    · simp [Rat.min_def, hhi']
      grind
  · simp [Rat.max_def, hlo']
    by_cases hhi' : (sqrtOnUnit.compute I.hi hhi n).hi +
        sqrtUnitErrorBudget n <= 1
    · simp [Rat.min_def, hhi']
      grind
    · simp [Rat.min_def, hhi']
      grind

theorem sqrtOnUnitEvalIntervalClipped_contains_point
    (I : QInterval) (hI : subintervalOf I 0 1)
    (x : Rat) (hx : inDomainInterval 0 1 x)
    (n : Nat) (hxlo : I.lo <= x) (hxhi : x <= I.hi) :
    (sqrtOnUnitEvalIntervalClipped I n).ContainsInterval
      (sqrtOnUnit.compute x hx n) := by
  apply QInterval.intersection_contains
  · exact sqrtOnUnitEvalIntervalTotal_contains_point I hI x hx n hxlo hxhi
  · have h := sqrtOnUnit_compute_subinterval x hx n
    exact ⟨h.1, h.2.2⟩

theorem sqrtOnUnitEvalIntervalClipped_square_contains_input
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat) :
    sq (sqrtOnUnitEvalIntervalClipped I n).lo <= I.lo /\
      I.hi <= sq (sqrtOnUnitEvalIntervalClipped I n).hi := by
  let J := sqrtOnUnitEvalIntervalClipped I n
  have hJ : subintervalOf J 0 1 := by
    exact sqrtOnUnitEvalIntervalClipped_subinterval I hI n
  have hlo : inDomainInterval 0 1 I.lo :=
    ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
  have hhi : inDomainInterval 0 1 I.hi :=
    ⟨Rat.le_trans hI.1 hI.2.1, hI.2.2⟩
  have hloJ := sqrtOnUnitEvalIntervalClipped_contains_point
    I hI I.lo hlo n Rat.le_refl hI.2.1
  have hhiJ := sqrtOnUnitEvalIntervalClipped_contains_point
    I hI I.hi hhi n hI.2.1 Rat.le_refl
  have hslo := sqrtApproxOnDomain_spec I.lo
    (sqrtDomain_of_unit hlo) (sqrtOnUnitSchedule.stage n)
  have hshi := sqrtApproxOnDomain_spec I.hi
    (sqrtDomain_of_unit hhi) (sqrtOnUnitSchedule.stage n)
  have hlo_sq : sq J.lo <= sq
      (sqrtOnUnit.compute I.lo hlo n).lo := by
    apply sq_le_sq_of_nonneg_le hJ.1
    exact hloJ.1
  have hhi_sq : sq (sqrtOnUnit.compute I.hi hhi n).hi <= sq J.hi := by
    apply sq_le_sq_of_nonneg_le
      (by
        have hp := sqrtOnUnit_compute_subinterval I.hi hhi n
        have hp0 : 0 <= (sqrtOnUnit.compute I.hi hhi n).hi :=
          Rat.le_trans hp.1 hp.2.1
        simpa [sqrtOnUnit_compute] using hp0)
    exact hhiJ.2
  constructor
  · exact Rat.le_trans hlo_sq (by
      rw [sqrtOnUnit_compute]
      exact hslo.2.2.1)
  · exact Rat.le_trans hshi.2.2.2 (Rat.le_trans hhi_sq Rat.le_refl)

private theorem sqrtUnitErrorBudget_pos (n : Nat) :
    0 < sqrtUnitErrorBudget n := by
  unfold sqrtUnitErrorBudget
  exact one_div_nat_pos (by omega)

private theorem sqrtUnitInputPrecision_pos (n : Nat) :
    0 < sqrtUnitInputPrecision n := by
  unfold sqrtUnitInputPrecision
  exact Nat.mul_pos
    (Nat.mul_pos (by omega) (Nat.succ_pos n))
    (Nat.succ_pos n)

/-- The quadratic input modulus is exactly the square of the radius used in
the elementary square-root gap estimate. -/
private theorem sqrtUnitInputPrecision_inverse_eq_radius_sq (n : Nat) :
    1 / ((sqrtUnitInputPrecision n : Nat) : Rat) =
      sq (1 / ((4 * (n + 1 : Nat) : Nat) : Rat)) := by
  let T : Rat := ((n + 1 : Nat) : Rat)
  have hcast16 : ((16 * (n + 1) * (n + 1) : Nat) : Rat) =
      (16 : Rat) * T * T := by
    dsimp [T]
    repeat rw [Rat.natCast_mul]
    have h16 : ((16 : Nat) : Rat) = (16 : Rat) := by
      decide +kernel
    rw [h16]
  have hcast4 : ((4 * (n + 1) : Nat) : Rat) = (4 : Rat) * T := by
    dsimp [T]
    exact Rat.natCast_mul 4 (n + 1)
  have hnum : (16 : Rat)⁻¹ = (4 : Rat)⁻¹ * (4 : Rat)⁻¹ := by
    decide +kernel
  unfold sqrtUnitInputPrecision sq
  repeat rw [Rat.div_def]
  rw [hcast16, hcast4]
  repeat rw [Rat.inv_mul_rev]
  rw [hnum]
  grind [Rat.mul_assoc, Rat.mul_comm]

/-- The radius `1/(4(n+1))` is eight of the scheduled pointwise error
budgets. -/
private theorem sqrtUnitRadius_eq_eight_errorBudget (n : Nat) :
    1 / ((4 * (n + 1 : Nat) : Nat) : Rat) =
      8 * sqrtUnitErrorBudget n := by
  let T : Rat := ((n + 1 : Nat) : Rat)
  have hcast4 : ((4 * (n + 1) : Nat) : Rat) = (4 : Rat) * T := by
    dsimp [T]
    exact Rat.natCast_mul 4 (n + 1)
  have hcast32 : ((32 * (n + 1) : Nat) : Rat) = (32 : Rat) * T := by
    dsimp [T]
    exact Rat.natCast_mul 32 (n + 1)
  have hnum : (4 : Rat)⁻¹ = 8 * (32 : Rat)⁻¹ := by
    decide +kernel
  unfold sqrtUnitErrorBudget
  repeat rw [Rat.div_def]
  rw [hcast4, hcast32]
  repeat rw [Rat.inv_mul_rev]
  rw [hnum]
  grind [Rat.mul_assoc, Rat.mul_comm]

private theorem sqrtUnit_thirteen_errorBudget_le_target (n : Nat) :
    13 * sqrtUnitErrorBudget n <=
      1 / ((n + 1 : Nat) : Rat) := by
  let T : Rat := ((n + 1 : Nat) : Rat)
  have hTpos : 0 < T := by
    dsimp [T]
    exact (Rat.natCast_pos).2 (Nat.succ_pos n)
  have hTne : T ≠ 0 := Rat.ne_of_gt hTpos
  have hprodpos : 0 < (32 : Rat) * T :=
    Rat.mul_pos (by decide +kernel) hTpos
  have hcast32 : ((32 * (n + 1) : Nat) : Rat) = (32 : Rat) * T := by
    dsimp [T]
    exact Rat.natCast_mul 32 (n + 1)
  apply Rat.le_of_mul_le_mul_right (c := (32 : Rat) * T)
  · unfold sqrtUnitErrorBudget
    repeat rw [Rat.div_def]
    rw [hcast32]
    calc
      (13 * (1 * ((32 : Rat) * T)⁻¹)) * ((32 : Rat) * T) = 13 := by
        calc
          (13 * (1 * ((32 : Rat) * T)⁻¹)) * ((32 : Rat) * T) =
              13 * (((32 : Rat) * T)⁻¹ * ((32 : Rat) * T)) := by
                grind [Rat.mul_assoc, Rat.mul_comm]
          _ = 13 := by
            rw [Rat.inv_mul_cancel _ (Rat.ne_of_gt hprodpos)]
            grind
      _ <= 32 := by decide +kernel
      _ = (1 * T⁻¹) * ((32 : Rat) * T) := by
        calc
          (32 : Rat) = 32 * (T⁻¹ * T) := by
            rw [Rat.inv_mul_cancel _ hTne]
            grind
          _ = (1 * T⁻¹) * ((32 : Rat) * T) := by
            grind [Rat.mul_assoc, Rat.mul_comm]
  · exact hprodpos

/-- The square-root interval enclosure has the literal `1/(n+1)` output
width required by `IntervalRegularOn`, provided the input box has the
quadratic modulus `1/(16(n+1)^2)`. -/
private theorem sqrtUnitEvalInterval_width_le
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat)
    (hinput : I.width <= 1 / ((sqrtUnitInputPrecision n : Nat) : Rat)) :
    (sqrtUnitEvalInterval I hI n).width <=
      1 / ((n + 1 : Nat) : Rat) := by
  have hIlo : 0 <= I.lo := hI.1
  have hIord : I.lo <= I.hi := hI.2.1
  have hIhi : I.hi <= 1 := hI.2.2
  let hlo : inDomainInterval 0 1 I.lo :=
    ⟨hIlo, Rat.le_trans hIord hIhi⟩
  let hhi : inDomainInterval 0 1 I.hi :=
    ⟨Rat.le_trans hIlo hIord, hIhi⟩
  let W : Rat := I.width
  let hW : inDomainInterval 0 1 W := by
    have hWnonneg : 0 <= I.width := by
      unfold QInterval.width
      grind [Rat.sub_eq_add_neg]
    have hWle : I.width <= 1 := by
      unfold QInterval.width
      grind [Rat.sub_eq_add_neg]
    exact ⟨hWnonneg, hWle⟩
  let A := sqrtOnUnit.compute I.lo hlo n
  let B := sqrtOnUnit.compute I.hi hhi n
  let S := sqrtOnUnit.compute W hW n
  let D := sqrtUnitErrorBudget n
  let R : Rat := 1 / ((4 * (n + 1 : Nat) : Nat) : Rat)
  have hA : SqrtIntervalSpec I.lo A := by
    dsimp [A]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.lo (sqrtDomain_of_unit hlo)
      (sqrtOnUnitSchedule.stage n)
  have hB : SqrtIntervalSpec I.hi B := by
    dsimp [B]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec I.hi (sqrtDomain_of_unit hhi)
      (sqrtOnUnitSchedule.stage n)
  have hS : SqrtIntervalSpec W S := by
    dsimp [S]
    rw [sqrtOnUnit_compute]
    exact sqrtApproxOnDomain_spec W (sqrtDomain_of_unit hW)
      (sqrtOnUnitSchedule.stage n)
  have hAwidth : A.width <= D := by
    dsimp [A, D, sqrtUnitErrorBudget]
    exact sqrtOnUnit_width_le_errorBudget I.lo hlo n
  have hBwidth : B.width <= D := by
    dsimp [B, D, sqrtUnitErrorBudget]
    exact sqrtOnUnit_width_le_errorBudget I.hi hhi n
  have hSwidth : S.width <= D := by
    dsimp [S, D, sqrtUnitErrorBudget]
    exact sqrtOnUnit_width_le_errorBudget W hW n
  have hWleRsq : W <= sq R := by
    dsimp [W, R]
    calc
      I.width <= 1 / ((sqrtUnitInputPrecision n : Nat) : Rat) := hinput
      _ = sq (1 / ((4 * (n + 1 : Nat) : Nat) : Rat)) :=
        sqrtUnitInputPrecision_inverse_eq_radius_sq n
  have hRnonneg : 0 <= R := by
    dsimp [R]
    exact Rat.le_of_lt (one_div_nat_pos (by omega))
  have hSlo_le_R : S.lo <= R :=
    SqrtIntervalSpec.lo_le_of_sq_le hS hRnonneg hWleRsq
  have hShi_le_R_add_D : S.hi <= R + D := by
    unfold QInterval.width at hSwidth
    grind [Rat.sub_eq_add_neg]
  let C : Rat := B.lo - A.hi
  have hC_le_Shi : C <= S.hi := by
    by_cases hCnonpos : C <= 0
    · exact Rat.le_trans hCnonpos (Rat.le_trans hS.1 hS.2.1)
    · have hCnonneg : 0 <= C := Rat.le_of_lt (by grind)
      have hC_le_sum : C <= B.lo + A.hi := by
        dsimp [C]
        have hAhi_nonneg : 0 <= A.hi := Rat.le_trans hA.1 hA.2.1
        grind [Rat.sub_eq_add_neg]
      have hdiffSq : sq B.lo - sq A.hi <= W := by
        have hBloSq : sq B.lo <= I.hi := hB.2.2.1
        have hAhiSq : I.lo <= sq A.hi := hA.2.2.2
        dsimp [W]
        unfold QInterval.width
        grind [Rat.sub_eq_add_neg]
      have hCsq : sq C <= W := by
        calc
          sq C = C * C := rfl
          _ <= C * (B.lo + A.hi) :=
            Rat.mul_le_mul_of_nonneg_left hC_le_sum hCnonneg
          _ = sq B.lo - sq A.hi := by
            dsimp [C, sq]
            grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul,
              Rat.add_assoc, Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
          _ <= W := hdiffSq
      have hShi_nonneg : 0 <= S.hi := Rat.le_trans hS.1 hS.2.1
      apply le_of_sq_le_sq_of_nonneg_right hShi_nonneg
      exact Rat.le_trans hCsq hS.2.2.2
  have hC_le_R_add_D : C <= R + D :=
    Rat.le_trans hC_le_Shi hShi_le_R_add_D
  have htotal : B.hi + D - (A.lo - D) <= R + 5 * D := by
    unfold QInterval.width at hAwidth hBwidth
    dsimp [C] at hC_le_R_add_D
    grind [Rat.sub_eq_add_neg]
  have htarget : R + 5 * D <= 1 / ((n + 1 : Nat) : Rat) := by
    rw [show R = 8 * D by
      dsimp [R, D]
      exact sqrtUnitRadius_eq_eight_errorBudget n]
    calc
      8 * D + 5 * D = 13 * D := by
        grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm]
      _ <= 1 / ((n + 1 : Nat) : Rat) := by
        dsimp [D]
        exact sqrtUnit_thirteen_errorBudget_le_target n
  unfold QInterval.width
  simpa [sqrtUnitEvalInterval, A, B, D] using Rat.le_trans htotal htarget

/-- The quantitative width bound for the public interval wrapper.  The
    quadratic input budget is the computable modulus needed near zero; no
    ambient real-valued continuity theorem is involved. -/
theorem sqrtOnUnitEvalInterval_width_le
    (I : QInterval) (hI : subintervalOf I 0 1) (n : Nat)
    (hinput : I.width <=
      1 / (((16 * (n + 1) * (n + 1) : Nat) : Rat))) :
    (sqrtOnUnitEvalIntervalTotal I n).width <=
      1 / (((n + 1 : Nat) : Rat)) := by
  have hinput' : I.width <=
      1 / ((sqrtUnitInputPrecision n : Nat) : Rat) := by
    simpa [sqrtUnitInputPrecision] using hinput
  rw [sqrtOnUnitEvalIntervalTotal_eq I hI n]
  exact sqrtUnitEvalInterval_width_le I hI n hinput'

/-- Square root is interval-regular on the nonnegative unit interval.  Its
quadratic input modulus is an entirely finite rational estimate, so the
result supplies literal epsilon--delta continuity without topology or an
ambient completed real line. -/
def sqrtOnUnit_intervalRegular : IntervalRegularOn sqrtOnUnit where
  evalInterval := sqrtUnitEvalInterval
  inputPrecision := sqrtUnitInputPrecision
  inputPrecision_pos := sqrtUnitInputPrecision_pos
  output_width := by
    intro I hI n hinput
    constructor
    · let hx : inDomainInterval 0 1 I.lo :=
        ⟨hI.1, Rat.le_trans hI.2.1 hI.2.2⟩
      have hcontains := sqrtUnitEvalInterval_contains_point I hI I.lo hx n
        Rat.le_refl hI.2.1
      have hpoint := sqrtOnUnit.valid_on I.lo (sqrtOnUnit.defined_on I.lo hx)
      have hpointWidth : 0 <= (sqrtOnUnit.compute I.lo hx n).width := by
        simpa [FunctionOnInterval.compute] using hpoint.1 n
      unfold QInterval.ContainsInterval at hcontains
      unfold QInterval.width at hpointWidth ⊢
      grind [Rat.sub_eq_add_neg]
    · exact sqrtUnitEvalInterval_width_le I hI n hinput
  contains_point_values := sqrtUnitEvalInterval_contains_point

/-- The scheduled bisection square-root branch is a continuous function in
the project's rational epsilon--delta sense. -/
def sqrtOnUnit_continuous : ContinuousFunctionOnInterval where
  function := sqrtOnUnit
  regular := sqrtOnUnit_intervalRegular

theorem sqrtOnUnit_epsilonDeltaContinuous :
    EpsilonDeltaContinuousOn sqrtOnUnit :=
  sqrtOnUnit_intervalRegular.epsilonDeltaContinuous

namespace Rat

def IsNatSquare (n : Nat) : Prop :=
  Exists fun k : Nat => k * k = n

/-- An integer square, stated in a way that exposes the finite search:
negative integers are excluded, and otherwise one searches natural squares up to
`z.natAbs`. -/
def IsIntSquare (z : Int) : Prop :=
  0 <= z /\ IsNatSquare z.natAbs

/-- A rational square.  We do not require the witness to be nonnegative:
if `r^2 = q`, then the nonnegative square-root value is `|r|`. -/
def IsSquare (q : Rat) : Prop :=
  Exists fun r : Rat => sq r = q

def NotSquare (q : Rat) : Prop :=
  ¬ IsSquare q

/-- Finite normal-form criterion: a reduced rational is a square precisely when
its numerator and denominator are squares. -/
def IsSquareInLowestTerms (q : Rat) : Prop :=
  IsIntSquare q.num /\ IsNatSquare q.den

/-- Finite normal-form nonsquare criterion.

For a reduced rational, it is enough for either the numerator or the denominator
to fail the finite square test.  Requiring both to be nonsquares is a useful
sufficient special case, but not necessary: `2 / 9` and `4 / 3` are already
nonsquares. -/
def IsNonSquareInLowestTerms (q : Rat) : Prop :=
  ¬ IsIntSquare q.num ∨ ¬ IsNatSquare q.den

theorem sq_num (r : Rat) : (sq r).num = r.num * r.num := by
  unfold sq
  unfold HMul.hMul instHMul Mul.mul Rat.instMul Rat.mul
  simp [r.reduced]
  rfl

theorem sq_den (r : Rat) : (sq r).den = r.den * r.den := by
  unfold sq
  unfold HMul.hMul instHMul Mul.mul Rat.instMul Rat.mul
  simp [r.reduced]
  rfl

theorem sq_num_nonneg (r : Rat) : 0 <= (sq r).num := by
  rw [sq_num]
  rw [← Int.natAbs_mul_self]
  exact Int.natCast_nonneg _

theorem sq_num_isIntSquare (r : Rat) : IsIntSquare (sq r).num := by
  constructor
  · exact sq_num_nonneg r
  · refine ⟨r.num.natAbs, ?_⟩
    rw [sq_num]
    simp [Int.natAbs_mul]

theorem sq_den_isNatSquare (r : Rat) : IsNatSquare (sq r).den := by
  refine ⟨r.den, ?_⟩
  rw [sq_den]

/-- Euclid's normal-form observation: when a reduced rational is a square, its
normalized numerator and denominator are squares. -/
theorem isSquareInLowestTerms_of_isSquare {q : Rat} :
    IsSquare q -> IsSquareInLowestTerms q := by
  intro hq
  rcases hq with ⟨r, hr⟩
  rw [← hr]
  exact ⟨sq_num_isIntSquare r, sq_den_isNatSquare r⟩

theorem isSquare_of_isSquareInLowestTerms {q : Rat} :
    IsSquareInLowestTerms q -> IsSquare q := by
  intro hs
  rcases hs.1 with ⟨hnum_nonneg, hnum_square⟩
  rcases hnum_square with ⟨a, ha⟩
  rcases hs.2 with ⟨b, hb⟩
  have haRat : (a : Rat) * (a : Rat) = (q.num : Rat) := by
    have haInt : ((a * a : Nat) : Int) = q.num := by
      rw [ha]
      exact Int.natAbs_of_nonneg hnum_nonneg
    exact_mod_cast haInt
  have hbRat : (b : Rat) * (b : Rat) = (q.den : Rat) := by
    exact_mod_cast hb
  have hb_ne_zero : b ≠ 0 := by
    intro hb0
    apply q.den_nz
    rw [← hb]
    simp [hb0]
  have hbRat_ne_zero : (b : Rat) ≠ 0 := by
    exact_mod_cast hb_ne_zero
  refine Exists.intro ((a : Rat) / (b : Rat)) ?_
  apply rat_eq_of_den_mul_eq_num (q := q)
  rw [← hbRat, ← haRat]
  unfold sq
  rw [Rat.div_def]
  grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel, Rat.inv_mul_cancel]

theorem square_iff_lowest_terms_square (q : Rat) :
    IsSquare q ↔ IsSquareInLowestTerms q :=
  ⟨isSquareInLowestTerms_of_isSquare, isSquare_of_isSquareInLowestTerms⟩

/-- Contrapositive form used for irrational square roots: if either normalized
part is not a square, then the rational is not a rational square. -/
theorem notSquare_of_nonSquareInLowestTerms {q : Rat} :
    IsNonSquareInLowestTerms q -> NotSquare q := by
  intro hns hsq
  have hs := isSquareInLowestTerms_of_isSquare hsq
  cases hns with
  | inl hnum => exact hnum hs.1
  | inr hden => exact hden hs.2

theorem notSquare_iff_lowest_terms_nonsquare (q : Rat) :
    NotSquare q ↔ IsNonSquareInLowestTerms q := by
  constructor
  · intro hn
    classical
    by_cases hnum : IsIntSquare q.num
    · right
      intro hden
      exact hn (isSquare_of_isSquareInLowestTerms ⟨hnum, hden⟩)
    · left
      exact hnum
  · exact notSquare_of_nonSquareInLowestTerms

theorem integer_square_criterion (z : Int) :
    IsSquare (z : Rat) ↔ IsIntSquare z := by
  exact Iff.trans (square_iff_lowest_terms_square (z : Rat)) (by
    unfold IsSquareInLowestTerms
    constructor
    · intro h
      simpa using h.1
    · intro hz
      constructor
      · simpa using hz
      · refine ⟨1, ?_⟩
        simp)

theorem square_root_denominator_bound (q r : Rat) (hr : sq r = q) :
    r.den <= q.den := by
  rw [← hr, sq_den]
  exact Nat.le_mul_of_pos_right r.den (Nat.pos_of_ne_zero r.den_nz)

end Rat

/-- General theorem target for rational square roots:
if `q` is a rational square, then the computable real produced by the rational
sqrt algorithm for `q` is rational.  The expected rational representative is
`|r|`, since the sqrt algorithm computes the nonnegative root. -/
theorem sqrt_rational_of_square
    (q r : Rat) (hq : sqrtDomain q) (h : SqrtRawSpec q hq)
    (hr : sq r = q) :
    (sqrtReal q hq h.1).Equiv (RealCompute.Certified.ofRat (qabs r)) := by
  apply RealCompute.sameStageOverlap_equiv
  intro n
  have hI := h.2 n
  have habs_nonneg : 0 <= qabs r := qabs_nonneg r
  have hq_le_sq : q <= sq (qabs r) := by
    rw [sq_qabs, hr]
    exact Rat.le_refl
  have hsq_le_q : sq (qabs r) <= q := by
    rw [sq_qabs, hr]
    exact Rat.le_refl
  have hlo : ((sqrtRaw q hq).compute n).lo <= qabs r :=
    SqrtIntervalSpec.lo_le_of_sq_le hI habs_nonneg hq_le_sq
  have hhi : qabs r <= ((sqrtRaw q hq).compute n).hi :=
    SqrtIntervalSpec.le_hi_of_sq_le hI hsq_le_q
  exact (RealCompute.compareAt_overlap_iff (sqrtRaw q hq)
    (RealCompute.ofRat (qabs r)) n n).2
    (by simpa [RealCompute.ofRat, QInterval.Overlaps] using And.intro hlo hhi)

/-- Equivalently: for nonnegative rational input, the rational sqrt algorithm
produces a rational computable real exactly for rational-square inputs. -/
theorem sqrt_rational_iff_square
    (q : Rat) (hq : sqrtDomain q) (h : SqrtRawSpec q hq) :
    RealCompute.Certified.Rational (sqrtReal q hq h.1) ↔ Rat.IsSquare q := by
  constructor
  case mp =>
    intro hrational
    rcases hrational with ⟨r, heq⟩
    refine Exists.intro r ?_
    have heqRaw : (sqrtRaw q hq).Equiv (RealCompute.ofRat r) := by
      simpa [sqrtReal, RealCompute.Certified.ofRat, RealCompute.Certified.Equiv, RealCompute.Certified.ofRaw] using heq
    exact sq_eq_of_sqrt_spec_equiv_rat h heqRaw
  case mpr =>
    intro hsquare
    rcases hsquare with ⟨r, hr⟩
    refine Exists.intro (qabs r) ?_
    exact sqrt_rational_of_square q r hq h hr

/-- Lowest-terms version of the classification: the rationality of the
computable real `sqrt(q)` is determined by whether the normalized numerator and
denominator of `q` are both squares. -/
theorem sqrt_rational_iff_lowest_terms_square
    (q : Rat) (hq : sqrtDomain q) (h : SqrtRawSpec q hq) :
    RealCompute.Certified.Rational (sqrtReal q hq h.1) ↔
      Rat.IsSquareInLowestTerms q := by
  exact Iff.trans (sqrt_rational_iff_square q hq h)
    (Rat.square_iff_lowest_terms_square q)

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