Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · RepresentedPositiveSquareRoot · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_RepresentedPositiveSquareRoot

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_AlgebraicFunctions
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexExponentialApproximation
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexReciprocalLift

set_option autoImplicit true

/-!
# Positive square roots of represented reals

This file starts the lift of the rational bisection square-root algorithm to
represented positive real inputs.  The key estimate is deliberately stated
only with rational interval data: square-root bisection midpoints are
Lipschitz away from zero, up to the widths of their certified bisection
boxes.  No completed real square root occurs in the statement or proof.
-/

namespace ComputableAnalysis
namespace RepresentedPositiveSquareRoot

/-- The midpoint of a square-root certificate lies within one certificate
width of each endpoint. -/
theorem midpoint_endpoint_bounds {I : QInterval} (hI : I.lo <= I.hi) :
    I.hi - I.width <= I.midpoint /\
      I.midpoint <= I.lo + I.width := by
  have hmid := QInterval.midpoint_mem hI
  unfold QInterval.width
  grind [Rat.sub_eq_add_neg]

private theorem sqrtCertificate_midpoint_sub_le
    {q r margin : Rat} {I J : QInterval}
    (hmargin : 0 < margin)
    (hI : SqrtIntervalSpec q I) (hJ : SqrtIntervalSpec r J)
    (hmq : sq margin <= q) (hqr : q <= r) :
    J.midpoint - I.midpoint <=
      margin⁻¹ * (r - q) + I.width + J.width := by
  have hmargin_ne : margin ≠ 0 := Rat.ne_of_gt hmargin
  have hmIhi : margin <= I.hi := hI.le_hi_of_sq_le hmq
  have hImid := midpoint_endpoint_bounds hI.2.1
  have hJmid := midpoint_endpoint_bounds hJ.2.1
  have hqr0 : 0 <= r - q := by grind [Rat.sub_eq_add_neg]
  by_cases hcross : J.lo <= I.hi
  · have hgap : J.midpoint - I.midpoint <= I.width + J.width := by
      grind [Rat.sub_eq_add_neg]
    have hinv0 : 0 <= margin⁻¹ :=
      Rat.le_of_lt ((Rat.inv_pos).2 hmargin)
    have hterm0 : 0 <= margin⁻¹ * (r - q) :=
      Rat.mul_nonneg hinv0 hqr0
    grind
  · have hgap0 : 0 < J.lo - I.hi := by grind [Rat.sub_eq_add_neg]
    have hsum : margin <= J.lo + I.hi := by
      have hJlo0 : 0 <= J.lo := hJ.1
      grind
    have hprod0 : 0 <= J.lo - I.hi := Rat.le_of_lt hgap0
    have hfactor :
        (J.lo - I.hi) * (J.lo + I.hi) = sq J.lo - sq I.hi := by
      unfold sq
      grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg]
    have hsq : sq J.lo - sq I.hi <= r - q := by
      have hj := hJ.2.2.1
      have hi := hI.2.2.2
      grind [Rat.sub_eq_add_neg]
    have hmul : (J.lo - I.hi) * margin <= r - q := by
      calc
        (J.lo - I.hi) * margin <=
            (J.lo - I.hi) * (J.lo + I.hi) :=
          Rat.mul_le_mul_of_nonneg_left hsum hprod0
        _ = sq J.lo - sq I.hi := hfactor
        _ <= r - q := hsq
    have hdivide : J.lo - I.hi <= margin⁻¹ * (r - q) := by
      apply Rat.le_of_mul_le_mul_right (c := margin)
      · calc
          (J.lo - I.hi) * margin <= r - q := hmul
          _ = (margin⁻¹ * (r - q)) * margin := by
            grind [Rat.mul_assoc, Rat.mul_comm,
              Rat.mul_inv_cancel margin hmargin_ne]
      · exact hmargin
    grind [Rat.sub_eq_add_neg]

/-- Quantitative rational square-root continuity away from zero.

If `I` and `J` certify square roots of `q` and `r`, and both radicands are at
least `margin^2`, then their rational midpoints differ by at most
`|r-q| / margin`, plus the two finite bisection widths.  This is the estimate
needed to lift rational bisection along moving midpoint samples of a
represented input. -/
theorem sqrtCertificate_midpoint_lipschitz
    {q r margin : Rat} {I J : QInterval}
    (hmargin : 0 < margin)
    (hI : SqrtIntervalSpec q I) (hJ : SqrtIntervalSpec r J)
    (hmq : sq margin <= q) (hmr : sq margin <= r) :
    qabs (J.midpoint - I.midpoint) <=
      margin⁻¹ * qabs (r - q) + I.width + J.width := by
  by_cases hqr : q <= r
  · have hdiff0 : 0 <= r - q := by grind [Rat.sub_eq_add_neg]
    rw [qabs_eq_self_of_nonneg hdiff0]
    apply qabs_le_of_neg_le_le
    · have hcross : I.lo <= J.hi := by
        have hJhi0 : 0 <= J.hi := Rat.le_trans hJ.1 hJ.2.1
        exact le_of_sq_le_sq_of_nonneg_right hJhi0
          (Rat.le_trans hI.2.2.1 (Rat.le_trans hqr hJ.2.2.2))
      have hImid := midpoint_endpoint_bounds hI.2.1
      have hJmid := midpoint_endpoint_bounds hJ.2.1
      have hinv0 : 0 <= margin⁻¹ :=
        Rat.le_of_lt ((Rat.inv_pos).2 hmargin)
      have hterm0 : 0 <= margin⁻¹ * (r - q) :=
        Rat.mul_nonneg hinv0 hdiff0
      grind [Rat.sub_eq_add_neg]
    · exact sqrtCertificate_midpoint_sub_le hmargin hI hJ hmq hqr
  · have hrq : r <= q := by grind
    have hdiff0 : r - q <= 0 := by grind [Rat.sub_eq_add_neg]
    rw [qabs_eq_neg_of_nonpos hdiff0]
    have hswap := sqrtCertificate_midpoint_sub_le
      hmargin hJ hI hmr hrq
    have hcross : J.lo <= I.hi := by
      have hIhi0 : 0 <= I.hi := Rat.le_trans hI.1 hI.2.1
      exact le_of_sq_le_sq_of_nonneg_right hIhi0
        (Rat.le_trans hJ.2.2.1 (Rat.le_trans hrq hI.2.2.2))
    have hImid := midpoint_endpoint_bounds hI.2.1
    have hJmid := midpoint_endpoint_bounds hJ.2.1
    have hinv0 : 0 <= margin⁻¹ :=
      Rat.le_of_lt ((Rat.inv_pos).2 hmargin)
    have hqr0 : 0 <= q - r := by grind [Rat.sub_eq_add_neg]
    have hterm0 : 0 <= margin⁻¹ * (q - r) :=
      Rat.mul_nonneg hinv0 hqr0
    apply qabs_le_of_neg_le_le
    · grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]
    · grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

/-! ## Lift to represented positive inputs -/

/-- A represented real together with the finite data needed by the positive
square-root chart.  `bound` is deliberately a natural number, so it also
supplies a simple uniform modulus for the fixed rational bisection bracket. -/
structure PositiveInput (bound : Nat) (margin : Rat) where
  raw : RealCompute
  valid : raw.Valid
  margin_pos : 0 < margin
  center_le_bound : forall n,
    (raw.compute n).midpoint <= (bound : Rat)
  margin_sq_le_center : forall n,
    sq margin <= (raw.compute n).midpoint

namespace PositiveInput

def rootBound (bound : Nat) : Rat := ((bound + 1 : Nat) : Rat)

theorem rootBound_pos (bound : Nat) : 0 < rootBound bound := by
  unfold rootBound
  exact (Rat.natCast_pos).2 (Nat.succ_pos bound)

theorem center_nonneg {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    0 <= (A.raw.compute n).midpoint := by
  have hm0 : 0 <= margin := Rat.le_of_lt A.margin_pos
  have hsq0 : 0 <= sq margin := by
    unfold sq
    exact Rat.mul_nonneg hm0 hm0
  exact Rat.le_trans hsq0 (A.margin_sq_le_center n)

theorem center_le_rootBound_sq {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    (A.raw.compute n).midpoint <= sq (rootBound bound) := by
  have hb : ((bound : Nat) : Rat) <= rootBound bound := by
    unfold rootBound
    exact_mod_cast (Nat.le_succ bound)
  have hB1 : 1 <= rootBound bound := by
    unfold rootBound
    exact_mod_cast (Nat.succ_le_succ (Nat.zero_le bound))
  have hB0 : 0 <= rootBound bound := Rat.le_trans (by decide +kernel) hB1
  calc
    (A.raw.compute n).midpoint <= (bound : Rat) := A.center_le_bound n
    _ <= rootBound bound := hb
    _ = rootBound bound * 1 := by grind
    _ <= rootBound bound * rootBound bound :=
      Rat.mul_le_mul_of_nonneg_left hB1 hB0
    _ = sq (rootBound bound) := rfl

def approximation {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) : QInterval :=
  sqrtBisect (A.raw.compute n).midpoint n
    { lo := 0, hi := rootBound bound }

theorem approximation_spec {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    SqrtIntervalSpec (A.raw.compute n).midpoint (approximation A n) := by
  apply sqrtBisect_spec
  unfold SqrtIntervalSpec
  refine ⟨(by decide +kernel : (0 : Rat) <= 0), ?_, ?_,
    center_le_rootBound_sq A n⟩
  · exact Rat.le_of_lt (rootBound_pos bound)
  · simpa [sq] using center_nonneg A n

theorem approximation_width_eq {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    (approximation A n).width =
      rootBound bound / (((2 ^ n : Nat) : Rat)) := by
  unfold approximation
  rw [sqrtBisect_width_eq]
  unfold QInterval.width
  grind [Rat.sub_eq_add_neg]

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

def approximationBudget (bound : Nat) (n : Nat) : Rat :=
  ((bound + 1 : Nat) : Rat) / (((2 ^ n : Nat) : Rat))

theorem approximation_width_le_budget {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    (approximation A n).width <= approximationBudget bound n := by
  rw [approximation_width_eq]
  exact Rat.le_refl

theorem approximationBudget_le_harmonic (bound n : Nat) :
    approximationBudget bound n≤((bound+1:Nat):Rat)/((n+1:Nat):Rat) := by
  unfold approximationBudget
  have hnum0 : 0 <= (((bound + 1 : Nat) : Rat)) := Rat.natCast_nonneg
  have hpow : n + 1 <= 2 ^ n := succ_le_two_pow n
  have hone := FTC.one_div_nat_antitone (Nat.succ_pos n)
    (Nat.pow_pos (by omega : 0 < 2)) hpow
  rw [Rat.div_def, Rat.div_def]
  exact Rat.mul_le_mul_of_nonneg_left (by
    simpa [Rat.div_def] using hone) hnum0

theorem approximationBudget_antitone (bound : Nat) {k n : Nat} (hkn : k≤n) :
    approximationBudget bound n≤approximationBudget bound k := by
  have hp : (0:Nat)<2 := by omega
  have h := FTC.one_div_nat_antitone (Nat.pow_pos hp) (Nat.pow_pos hp)
    (Nat.pow_le_pow_right hp hkn)
  have hm := Rat.mul_le_mul_of_nonneg_left h (Rat.natCast_nonneg (a := bound+1))
  simpa only [approximationBudget,Rat.div_def,Rat.one_mul] using hm

theorem approximationBudget_nonnegative (bound n : Nat) : 0≤approximationBudget bound n :=
  Rat.mul_nonneg Rat.natCast_nonneg
    (Rat.le_of_lt (Rat.inv_pos.mpr (Rat.natCast_pos.mpr (Nat.pow_pos (by omega : 0<2)))))

theorem approximationBudget_shrinks (bound : Nat) :
    ShrinksToZero (approximationBudget bound) := by
  apply shrinksToZero_of_natOverSuccBound (C := bound + 1)
  exact approximationBudget_le_harmonic bound

theorem midpoint_sub_le_width {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (k n : Nat) (hkn : k <= n) :
    qabs ((A.raw.compute n).midpoint - (A.raw.compute k).midpoint) <=
      (A.raw.compute k).width := by
  have hkwidth := A.valid.1 k
  have hnwidth := A.valid.1 n
  have hkordered : (A.raw.compute k).lo <= (A.raw.compute k).hi := by
    unfold QInterval.width at hkwidth
    grind [Rat.sub_eq_add_neg]
  have hnordered : (A.raw.compute n).lo <= (A.raw.compute n).hi := by
    unfold QInterval.width at hnwidth
    grind [Rat.sub_eq_add_neg]
  have hmidk := QInterval.midpoint_mem hkordered
  have hmidn := QInterval.midpoint_mem hnordered
  have hnest := A.valid.2.1 k n hkn
  apply qabs_sub_le_of_common_bounds
  · exact Rat.le_trans hnest.1 hmidn.1
  · exact Rat.le_trans hmidn.2 hnest.2.2
  · exact hmidk.1
  · exact hmidk.2

/-- Direct candidates retain the full certified rational bisection interval.
This is what later makes the equation `sqrt(x)^2 = x` an interval-containment
fact rather than a limit argument. -/
def candidate {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : ComplexCompute where
  compute := fun n => QBox.ofRealInterval (approximation A n)

theorem candidate_ordered {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    ((candidate A).compute n).Ordered := by
  have hs := approximation_spec A n
  unfold candidate QBox.ofRealInterval
  exact ⟨hs.2.1, Rat.le_refl⟩

theorem candidate_widths_shrink {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) :
    ComplexCompute.WidthsShrinkToZero (candidate A).compute := by
  intro eps
  obtain ⟨N, hN⟩ := approximationBudget_shrinks bound eps
  refine ⟨N, ?_⟩
  intro n hn
  constructor
  · change (approximation A n).width <= eps.val
    exact Rat.le_trans (approximation_width_le_budget A n) (hN n hn)
  · unfold candidate QBox.ofRealInterval QBox.height
    change (0 : Rat) - 0 <= eps.val
    grind [Rat.le_of_lt eps.property]

def radius {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) : Rat :=
  margin⁻¹ * (A.raw.compute n).width +
    3 * approximationBudget bound n

theorem radius_shrinks {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : ShrinksToZero (radius A) := by
  intro eps
  let inputEps : QPos :=
    ⟨eps.val * margin / 4, by
      exact Rat.mul_pos (Rat.mul_pos eps.property A.margin_pos)
        ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 4))⟩
  let budgetEps : QPos :=
    ⟨eps.val / 6, by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property
        ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 6))⟩
  obtain ⟨Ni, hNi⟩ := A.valid.2.2 inputEps
  obtain ⟨Nb, hNb⟩ := approximationBudget_shrinks bound budgetEps
  refine ⟨Nat.max Ni Nb, ?_⟩
  intro n hn
  have hi := (hNi n (Nat.le_trans (Nat.le_max_left _ _) hn))
  have hb := hNb n (Nat.le_trans (Nat.le_max_right _ _) hn)
  have hinv0 : 0 <= margin⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 A.margin_pos)
  unfold radius
  calc
    margin⁻¹ * (A.raw.compute n).width +
        3 * approximationBudget bound n <=
      margin⁻¹ * inputEps.val + 3 * budgetEps.val :=
        rat_add_le_add
          (Rat.mul_le_mul_of_nonneg_left hi hinv0)
          (Rat.mul_le_mul_of_nonneg_left hb (by decide +kernel))
    _ <= eps.val := by
      dsimp [inputEps, budgetEps]
      rw [Rat.div_def]
      have hm : margin ≠ 0 := Rat.ne_of_gt A.margin_pos
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel margin hm,
        Rat.mul_inv_cancel]

theorem candidate_future_contained_expand {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (k n : Nat) (hkn : k <= n) :
    ((candidate A).compute n).NestedIn
      (QBox.expand ((candidate A).compute k) (radius A k)) := by
  let q := (A.raw.compute k).midpoint
  let r := (A.raw.compute n).midpoint
  let x := (approximation A k).midpoint
  let y := (approximation A n).midpoint
  have hdist0 := sqrtCertificate_midpoint_lipschitz
    A.margin_pos (approximation_spec A k) (approximation_spec A n)
    (A.margin_sq_le_center k) (A.margin_sq_le_center n)
  have hinput := midpoint_sub_le_width A k n hkn
  have hwidthk := approximation_width_le_budget A k
  have hwidthn0 := approximation_width_le_budget A n
  have hbudget := approximationBudget_antitone bound hkn
  have hwidthn := Rat.le_trans hwidthn0 hbudget
  have hinv0 : 0 <= margin⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 A.margin_pos)
  have hbudget0 := approximationBudget_nonnegative bound k
  let midpointRadius : Rat :=
    margin⁻¹ * (A.raw.compute k).width +
      2 * approximationBudget bound k
  have hdist : qabs (y - x) <= midpointRadius := by
    have hm := Rat.mul_le_mul_of_nonneg_left hinput hinv0
    calc
      qabs (y - x) <=
          margin⁻¹ * qabs (r - q) +
            (approximation A k).width + (approximation A n).width := hdist0
      _ <= margin⁻¹ * (A.raw.compute k).width +
            approximationBudget bound k + approximationBudget bound k :=
        rat_add_le_add (rat_add_le_add hm hwidthk) hwidthn
      _ <= midpointRadius := by
        dsimp [midpointRadius]
        grind
  have hIk := (approximation_spec A k).2.1
  have hIn := (approximation_spec A n).2.1
  have hmk := QInterval.midpoint_mem hIk
  have hmn := QInterval.midpoint_mem hIn
  have hnk := midpoint_endpoint_bounds hIn
  have hlow : -midpointRadius <= y - x := by
    exact Rat.le_trans (by grind : -midpointRadius <= -qabs (y - x))
      (neg_qabs_le_self (y - x))
  have hupp : y - x <= midpointRadius :=
    Rat.le_trans (self_le_qabs (y - x)) hdist
  have hradius0 : 0 <= radius A k := by
    unfold radius
    exact Rat.add_nonneg
      (Rat.mul_nonneg hinv0 (A.valid.1 k))
      (Rat.mul_nonneg (by decide +kernel) hbudget0)
  have hcover : midpointRadius + approximationBudget bound k <= radius A k := by
    unfold radius
    grind
  unfold candidate QBox.ofRealInterval QBox.NestedIn QBox.expand
  simp only [QComplex.le_def]
  constructor
  · constructor
    · unfold QInterval.width at hwidthk hwidthn
      grind [Rat.sub_eq_add_neg]
    · grind
  · constructor
    · unfold QInterval.width at hwidthk hwidthn
      grind [Rat.sub_eq_add_neg]
    · grind

/-- Constructive positive square root, represented as the real part of a
finite-prefix stabilization of rational bisection midpoints. -/
def sqrtComplex {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : ComplexCompute :=
  ComplexCompute.cauchyStabilize (candidate A) (radius A)

def sqrt {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : RealCompute := (sqrtComplex A).realPart

theorem sqrtComplex_valid {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : (sqrtComplex A).Valid := by
  unfold sqrtComplex
  exact ComplexCompute.cauchyStabilize_valid
    (candidate_ordered A) (candidate_widths_shrink A)
    (candidate_future_contained_expand A) (radius_shrinks A)

theorem sqrt_valid {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : (sqrt A).Valid :=
  ComplexCompute.realPart_valid (sqrtComplex_valid A)

/-- Every output stage retains the full current rational bisection
certificate.  Combined with `approximation_spec`, this is the finite
algebraic certificate from which the represented square equation is derived. -/
theorem sqrt_contains_current_approximation
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) (n : Nat) :
    (sqrt A).compute n |>.ContainsInterval (approximation A n) := by
  have hcontains : ((candidate A).compute n).NestedIn
      ((sqrtComplex A).compute n) := by
    unfold sqrtComplex
    exact ComplexCompute.cauchyStabilize_contains_current
      (candidate_future_contained_expand A) n
  exact ⟨hcontains.1.1, hcontains.2.1⟩

/-- Squaring the current finite bisection box contains the sampled radicand
center.  This is the literal rational-box form of the algebraic equation. -/
theorem candidate_square_contains_center
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) (n : Nat) :
    (QBox.point
      { re := (A.raw.compute n).midpoint, im := 0 }).NestedIn
        (QBox.mul ((candidate A).compute n) ((candidate A).compute n)) := by
  have hs := approximation_spec A n
  have hmul := QBox.mulRealInterval_self_of_nonneg hs.1 hs.2.1
  have hzero := QBox.mulRealInterval_self_of_nonneg
    (by decide +kernel : (0 : Rat) <= 0) (Rat.le_refl : (0 : Rat) <= 0)
  have hrightZero := QBox.mulRealInterval_of_nonneg
    hs.1 hs.2.1 (by decide +kernel : (0 : Rat) <= 0)
      (Rat.le_refl : (0 : Rat) <= 0)
  have hleftZero := QBox.mulRealInterval_of_nonneg
    (by decide +kernel : (0 : Rat) <= 0) (Rat.le_refl : (0 : Rat) <= 0)
      hs.1 hs.2.1
  unfold candidate QBox.ofRealInterval QBox.mul QBox.point QBox.NestedIn
  simp only [QComplex.le_def]
  rw [hmul, hzero, hrightZero, hleftZero]
  unfold SqrtIntervalSpec sq at hs
  grind [Rat.sub_eq_add_neg]

/-- The constructed positive square root satisfies its defining equation as
an equivalence of represented complex numbers.  The proof uses, at every
stage, the rational radicand midpoint as a common point of the input box and
the square of the stabilized root box. -/
theorem sqrtComplex_square_equiv_raw
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) :
    (ComplexCompute.mul (sqrtComplex A) (sqrtComplex A)).Equiv
      (ComplexCompute.ofRealCompute A.raw) := by
  intro n
  apply (ComplexCompute.compareAt_overlap_iff
    (ComplexCompute.mul (sqrtComplex A) (sqrtComplex A))
    (ComplexCompute.ofRealCompute A.raw) n n).2
  let point : QComplex :=
    { re := (A.raw.compute n).midpoint, im := 0 }
  have hcandidate : ((candidate A).compute n).NestedIn
      ((sqrtComplex A).compute n) := by
    unfold sqrtComplex
    exact ComplexCompute.cauchyStabilize_contains_current
      (candidate_future_contained_expand A) n
  have hcandidateSq := candidate_square_contains_center A n
  have hmulNested :
      (QBox.mul ((candidate A).compute n) ((candidate A).compute n)).NestedIn
        (QBox.mul ((sqrtComplex A).compute n) ((sqrtComplex A).compute n)) :=
    QBox.mul_nested (candidate_ordered A n) (candidate_ordered A n)
      hcandidate hcandidate
  have hpointSq : (QBox.point point).NestedIn
      ((ComplexCompute.mul (sqrtComplex A) (sqrtComplex A)).compute n) :=
    QBox.nested_trans hcandidateSq hmulNested
  have hrawOrdered :
      (A.raw.compute n).lo <= (A.raw.compute n).hi := by
    have := A.valid.1 n
    unfold QInterval.width at this
    grind [Rat.sub_eq_add_neg]
  have hmid := QInterval.midpoint_mem hrawOrdered
  have hpointRaw : (QBox.point point).NestedIn
      ((ComplexCompute.ofRealCompute A.raw).compute n) := by
    unfold point QBox.point ComplexCompute.ofRealCompute QBox.NestedIn
    simp only [QComplex.le_def]
    exact ⟨⟨hmid.1, Rat.le_refl⟩, ⟨hmid.2, Rat.le_refl⟩⟩
  exact ⟨
    QComplex.le_trans hpointSq.1
      (QComplex.le_trans (QComplex.le_refl point) hpointRaw.2),
    QComplex.le_trans hpointRaw.1
      (QComplex.le_trans (QComplex.le_refl point) hpointSq.2)⟩

/-! ## A uniformly positive reboxing -/

/-- Extra bisection stages sufficient to make the rational square-root
certificate narrower than `margin/2`. -/
private def coarseGuardShift (bound : Nat) (margin : Rat) : Nat :=
  2 * (bound + 1) * (margin.den + 1)

private theorem coarse_guard_budget
    {bound : Nat} {margin : Rat} (hmargin : 0 < margin) (n : Nat) :
    approximationBudget bound (n + coarseGuardShift bound margin) <= margin / 2 := by
  let C : Nat := bound + 1
  let D : Nat := margin.den + 1
  let S : Nat := 2 * C * D
  have hC : 0 < C := by dsimp [C]; omega
  have hD : 0 < D := by dsimp [D]; omega
  have hS : 0 < S := Nat.mul_pos (Nat.mul_pos (by omega) hC) hD
  have hden : S <= n + S + 1 := by omega
  have hone := FTC.one_div_nat_antitone hS (by omega : 0 < n + S + 1) hden
  have hC0 : 0 <= (C : Rat) := Rat.natCast_nonneg
  have hscaled := Rat.mul_le_mul_of_nonneg_left hone hC0
  have hCDne : ((C : Rat) * ((2 * D : Nat) : Rat)) ≠ 0 := by
    exact Rat.ne_of_gt (Rat.mul_pos
      ((Rat.natCast_pos).2 hC)
      ((Rat.natCast_pos).2 (Nat.mul_pos (by omega) hD)))
  have hcancel :
      (C : Rat) / (S : Rat) = 1 / (((2 * D : Nat) : Rat)) := by
    dsimp [S]
    rw [show (((2 * C * D : Nat) : Rat)) =
      (C : Rat) * ((2 * D : Nat) : Rat) by
        exact_mod_cast (by
          simp [Nat.mul_comm, Nat.mul_left_comm] :
          2 * C * D = C * (2 * D))]
    rw [Rat.div_def, Rat.div_def]
    have hCne : (C : Rat) ≠ 0 := Rat.ne_of_gt ((Rat.natCast_pos).2 hC)
    have h2Dne : (((2 * D : Nat) : Rat)) ≠ 0 :=
      Rat.ne_of_gt ((Rat.natCast_pos).2 (Nat.mul_pos (by omega) hD))
    grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
  have hfirst : approximationBudget bound (n + coarseGuardShift bound margin) <=
      1 / (((2 * D : Nat) : Rat)) := by
    calc
      approximationBudget bound (n+coarseGuardShift bound margin)≤(C:Rat)/((n+S+1:Nat):Rat) :=
        approximationBudget_le_harmonic bound _
      _≤(C:Rat)/(S:Rat) := by simpa [Rat.div_def] using hscaled
      _=1/((2*D:Nat):Rat) := hcancel
  have hbase := FTC.one_div_den_succ_le_of_pos hmargin
  have hhalf : 1 / (((2 * D : Nat) : Rat)) <= margin / 2 := by
    have htwo : (0 : Rat) <= 1 / 2 := by
      rw [Rat.div_def]
      exact Rat.mul_nonneg (by decide +kernel)
        (Rat.le_of_lt ((Rat.inv_pos).2 (by decide +kernel)))
    have hmul := Rat.mul_le_mul_of_nonneg_right hbase htwo
    dsimp [D] at hmul ⊢
    rw [Rat.div_def, Rat.div_def] at hmul ⊢
    have hdne : (((margin.den + 1 : Nat) : Rat)) ≠ 0 :=
      Rat.ne_of_gt ((Rat.natCast_pos).2 (Nat.succ_pos margin.den))
    grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
  exact Rat.le_trans hfirst hhalf

/-- Search only as far as the actual dyadic bisection budget requires.
The coarse denominator bound occurs exclusively in the termination proof. -/
private def guardSearchFrom (bound : Nat) (margin : Rat) (hp : 0<margin) (n : Nat) : Nat :=
  if approximationBudget bound n≤margin/2 then n else guardSearchFrom bound margin hp (n+1)
termination_by coarseGuardShift bound margin-n
decreasing_by
  have h0 := coarse_guard_budget (bound := bound) hp 0
  have hn : n<coarseGuardShift bound margin := by
    by_cases hn : n<coarseGuardShift bound margin
    · exact hn
    · have hm := approximationBudget_antitone bound (show coarseGuardShift bound margin≤n by omega)
      have hb : approximationBudget bound n≤margin/2 := Rat.le_trans hm (by simpa only [Nat.zero_add] using h0)
      contradiction
  omega

private theorem guardSearchFrom_spec (bound : Nat) (margin : Rat) (hp : 0<margin) (n : Nat) :
    approximationBudget bound (guardSearchFrom bound margin hp n)≤margin/2 := by
  rw [guardSearchFrom]
  split
  · assumption
  · exact guardSearchFrom_spec bound margin hp (n+1)
termination_by coarseGuardShift bound margin-n
decreasing_by
  have h0 := coarse_guard_budget (bound := bound) hp 0
  have hn : n<coarseGuardShift bound margin := by
    by_cases hn : n<coarseGuardShift bound margin
    · exact hn
    · have hm := approximationBudget_antitone bound (show coarseGuardShift bound margin≤n by omega)
      have hb : approximationBudget bound n≤margin/2 := Rat.le_trans hm (by simpa only [Nat.zero_add] using h0)
      contradiction
  omega

/-- Extra bisection stages are selected by a terminating rational budget
search. Positive-input semantics and all later guard bounds are preserved. -/
def guardShift (bound : Nat) (margin : Rat) : Nat :=
  if hp : 0<margin then guardSearchFrom bound margin hp 0 else 0

theorem approximationBudget_shift_le_half_margin
    {bound : Nat} {margin : Rat} (hmargin : 0<margin) (n : Nat) :
    approximationBudget bound (n+guardShift bound margin)≤margin/2 := by
  simp only [guardShift,dif_pos hmargin]
  exact Rat.le_trans (approximationBudget_antitone bound (show
    guardSearchFrom bound margin hmargin 0≤n+guardSearchFrom bound margin hmargin 0 by omega))
    (guardSearchFrom_spec bound margin hmargin 0)

theorem half_margin_le_shifted_approximation_lo
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) (n : Nat) :
    margin / 2 <=
      (approximation A (n + guardShift bound margin)).lo := by
  let stage := n + guardShift bound margin
  have hspec := approximation_spec A stage
  have hlower := hspec.sub_width_le_lo_of_sq_le
    (A.margin_sq_le_center stage)
  have hwidth := approximation_width_le_budget A stage
  have hbudget := approximationBudget_shift_le_half_margin
    (bound := bound) A.margin_pos n
  have hwidthHalf : (approximation A stage).width <= margin / 2 :=
    Rat.le_trans hwidth hbudget
  dsimp [stage] at hlower hwidthHalf ⊢
  grind [Rat.sub_eq_add_neg, Rat.div_def]

theorem shifted_approximation_hi_le_rootBound
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) (n : Nat) :
    (approximation A (n + guardShift bound margin)).hi <= rootBound bound := by
  let stage := n + guardShift bound margin
  let q := (A.raw.compute stage).midpoint
  have hinitial : SqrtIntervalSpec q
      { lo := 0, hi := rootBound bound } := by
    unfold SqrtIntervalSpec
    refine ⟨(by decide +kernel : (0 : Rat) <= 0),
      Rat.le_of_lt (rootBound_pos bound), ?_, ?_⟩
    · simpa [q, sq] using center_nonneg A stage
    · simpa [q] using center_le_rootBound_sq A stage
  have hcontains := sqrtBisect_contains_of_le_fuel hinitial
    (Nat.zero_le stage)
  simpa [approximation, stage, q, sqrtBisect] using hcontains.2

def guardInterval (bound : Nat) (margin : Rat) : QInterval :=
  { lo := margin / 2, hi := rootBound bound }

theorem shifted_approximation_nested_guard
    {bound : Nat} {margin : Rat} (A : PositiveInput bound margin) (n : Nat) :
    (guardInterval bound margin).ContainsInterval
      (approximation A (n + guardShift bound margin)) :=
  ⟨half_margin_le_shifted_approximation_lo A n,
    shifted_approximation_hi_le_rootBound A n⟩

/-- The positive root reboxed into the explicit compact interval
`[margin/2, rootBound]`.  Its computation remains finite rational interval
arithmetic. -/
def awayRootRaw {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : ComplexCompute where
  compute := fun n => QBox.intersection
    ((sqrtComplex A).compute (n + guardShift bound margin))
    (QBox.ofRealInterval (guardInterval bound margin))

theorem awayRootRaw_valid {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) : (awayRootRaw A).Valid := by
  let shift := guardShift bound margin
  have hsqrt := sqrtComplex_valid A
  have hcommon : forall n,
      ((candidate A).compute (n + shift)).NestedIn
        ((awayRootRaw A).compute n) := by
    intro n
    unfold awayRootRaw
    apply QBox.intersection_contains
    · unfold sqrtComplex
      exact ComplexCompute.cauchyStabilize_contains_current
        (candidate_future_contained_expand A) (n + shift)
    · have hg := shifted_approximation_nested_guard A n
      unfold QInterval.ContainsInterval at hg
      unfold candidate QBox.ofRealInterval QBox.NestedIn
      simp only [QComplex.le_def]
      exact ⟨⟨hg.1, Rat.le_refl⟩, ⟨hg.2, Rat.le_refl⟩⟩
  constructor
  · intro n
    have hordered := QBox.ordered_of_nested
      (candidate_ordered A (n + shift)) (hcommon n)
    exact (QBox.ordered_iff_width_height_nonneg _).1 hordered
  · constructor
    · intro n m hnm
      have hbox : QBox.NestedIn
          (QBox.intersection ((sqrtComplex A).compute (m + shift))
            (QBox.ofRealInterval (guardInterval bound margin)))
          (QBox.intersection ((sqrtComplex A).compute (n + shift))
            (QBox.ofRealInterval (guardInterval bound margin))) := by
        apply QBox.intersection_contains
        · apply QBox.nested_trans
          · exact QBox.intersection_contained_left _ _
          · exact ComplexCompute.valid_nestedIn hsqrt (by omega)
        · exact QBox.intersection_contained_right _ _
      exact ⟨hbox.1.1, hbox.2.1, hbox.1.2, hbox.2.2⟩
    · intro eps
      obtain ⟨N, hN⟩ := hsqrt.2.2 eps
      refine ⟨N, ?_⟩
      intro n hn
      have hsource := hN (n + shift) (Nat.le_trans hn (Nat.le_add_right n shift))
      have hcontained := QBox.intersection_contained_left
        ((sqrtComplex A).compute (n + shift))
        (QBox.ofRealInterval (guardInterval bound margin))
      have hwh := QBox.width_height_le_of_nested hcontained
      exact ⟨Rat.le_trans hwh.1 hsource.1,
        Rat.le_trans hwh.2 hsource.2⟩

/-- Every guarded output box retains the literal square-root certificate at
the shifted bisection stage used to construct it. -/
theorem awayRootRaw_contains_shifted_approximation
    {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    ((candidate A).compute (n + guardShift bound margin)).NestedIn
      ((awayRootRaw A).compute n) := by
  unfold awayRootRaw
  apply QBox.intersection_contains
  · unfold sqrtComplex
    exact ComplexCompute.cauchyStabilize_contains_current
      (candidate_future_contained_expand A)
      (n + guardShift bound margin)
  · have hg := shifted_approximation_nested_guard A n
    unfold QInterval.ContainsInterval at hg
    unfold candidate QBox.ofRealInterval QBox.NestedIn
    simp only [QComplex.le_def]
    exact ⟨⟨hg.1, Rat.le_refl⟩, ⟨hg.2, Rat.le_refl⟩⟩

theorem awayRootRaw_equiv_sqrtComplex {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) :
    (awayRootRaw A).Equiv (sqrtComplex A) := by
  intro n
  apply (ComplexCompute.compareAt_overlap_iff (awayRootRaw A) (sqrtComplex A)
    n n).2
  let shift := guardShift bound margin
  have hleftOrdered := ComplexCompute.valid_ordered (awayRootRaw_valid A) n
  have hleftInShifted : ((awayRootRaw A).compute n).NestedIn
      ((sqrtComplex A).compute (n + shift)) := by
    exact QBox.intersection_contained_left _ _
  have hshiftedInCurrent : ((sqrtComplex A).compute (n + shift)).NestedIn
      ((sqrtComplex A).compute n) :=
    ComplexCompute.valid_nestedIn (sqrtComplex_valid A) (Nat.le_add_right n shift)
  have hleftInRight := QBox.nested_trans hleftInShifted hshiftedInCurrent
  exact ⟨
    QComplex.le_trans hleftOrdered hleftInRight.2,
    QComplex.le_trans hleftInRight.1 hleftOrdered⟩

theorem awayRootRaw_square_equiv_raw {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) :
    (ComplexCompute.mul (awayRootRaw A) (awayRootRaw A)).Equiv
      (ComplexCompute.ofRealCompute A.raw) := by
  exact ComplexCompute.equiv_trans
    (ComplexCompute.mul_valid (awayRootRaw_valid A) (awayRootRaw_valid A))
    (ComplexCompute.mul_valid (sqrtComplex_valid A) (sqrtComplex_valid A))
    (ComplexCompute.ofRealCompute_valid A.raw A.valid)
    (ComplexCompute.mul_equiv
      (awayRootRaw_valid A) (sqrtComplex_valid A)
      (awayRootRaw_valid A) (sqrtComplex_valid A)
      (awayRootRaw_equiv_sqrtComplex A) (awayRootRaw_equiv_sqrtComplex A))
    (sqrtComplex_square_equiv_raw A)

def awayRootMargin (margin : Rat) : Rat := sq (margin / 2)

theorem awayRootMargin_pos {margin : Rat} (hmargin : 0 < margin) :
    0 < awayRootMargin margin := by
  have hhalf : 0 < margin / 2 := by
    rw [Rat.div_def]
    exact Rat.mul_pos hmargin ((Rat.inv_pos).2 (by decide +kernel))
  unfold awayRootMargin sq
  exact Rat.mul_pos hhalf hhalf

theorem awayRootRaw_nested_guard {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    ((awayRootRaw A).compute n).NestedIn
      (QBox.ofRealInterval (guardInterval bound margin)) := by
  exact QBox.intersection_contained_right _ _

theorem awayRootRaw_center_bounds {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (n : Nat) :
    margin / 2 <= ((awayRootRaw A).compute n).center.re /\
      ((awayRootRaw A).compute n).center.re <= rootBound bound /\
      ((awayRootRaw A).compute n).center.im = 0 := by
  have hordered := ComplexCompute.valid_ordered (awayRootRaw_valid A) n
  have hcenter := QBox.center_mem hordered
  have hguard := awayRootRaw_nested_guard A n
  unfold QBox.ofRealInterval QBox.NestedIn at hguard
  simp only [QComplex.le_def] at hguard hcenter
  unfold guardInterval at hguard
  constructor
  · exact Rat.le_trans hguard.1.1 hcenter.1.1
  · constructor
    · exact Rat.le_trans hcenter.2.1 hguard.2.1
    · have hlo : 0 <= ((awayRootRaw A).compute n).center.im :=
        Rat.le_trans hguard.1.2 hcenter.1.2
      have hhi : ((awayRootRaw A).compute n).center.im <= 0 :=
        Rat.le_trans hcenter.2.2 hguard.2.2
      exact Rat.le_antisymm hhi hlo

/-- The positively reboxed root is uniformly bounded and separated from
zero, hence is directly accepted by the represented reciprocal API. -/
def awayInput {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) :
    ComplexReciprocalLift.AwayInput (rootBound bound) (awayRootMargin margin) where
  raw := awayRootRaw A
  valid := awayRootRaw_valid A
  bound_nonneg := Rat.le_of_lt (rootBound_pos bound)
  margin_pos := awayRootMargin_pos A.margin_pos
  center_normBound := by
    intro n
    have hb := awayRootRaw_center_bounds A n
    have hhalf0 : 0 <= margin / 2 := by
      rw [Rat.div_def]
      exact Rat.mul_nonneg (Rat.le_of_lt A.margin_pos)
        (Rat.le_of_lt ((Rat.inv_pos).2 (by decide +kernel)))
    have hre0 : 0 <= ((awayRootRaw A).compute n).center.re :=
      Rat.le_trans hhalf0 hb.1
    have hzero : qabs 0 = 0 := by decide +kernel
    unfold QComplex.normBound
    rw [hb.2.2, qabs_eq_self_of_nonneg hre0, hzero]
    grind
  center_normSq_ge := by
    intro n
    have hb := awayRootRaw_center_bounds A n
    have hhalf0 : 0 <= margin / 2 := by
      rw [Rat.div_def]
      exact Rat.mul_nonneg (Rat.le_of_lt A.margin_pos)
        (Rat.le_of_lt ((Rat.inv_pos).2 (by decide +kernel)))
    have hre0 : 0 <= ((awayRootRaw A).compute n).center.re :=
      Rat.le_trans hhalf0 hb.1
    have hmul := rat_mul_le_mul_of_nonneg hhalf0 hb.1 hhalf0 hb.1
    unfold awayRootMargin sq QComplex.normSq
    rw [hb.2.2]
    grind

/-! ## Independence of the represented input -/

theorem midpoint_sub_le_width_add_width_of_equiv
    {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (hAB : A.raw.Equiv B.raw)
    (m n : Nat) :
    qabs ((A.raw.compute m).midpoint - (B.raw.compute n).midpoint) <=
      (A.raw.compute m).width + (B.raw.compute n).width := by
  have hAw := A.valid.1 m
  have hBw := B.valid.1 n
  have hAo : (A.raw.compute m).lo <= (A.raw.compute m).hi := by
    unfold QInterval.width at hAw
    grind [Rat.sub_eq_add_neg]
  have hBo : (B.raw.compute n).lo <= (B.raw.compute n).hi := by
    unfold QInterval.width at hBw
    grind [Rat.sub_eq_add_neg]
  have hAm := QInterval.midpoint_mem hAo
  have hBm := QInterval.midpoint_mem hBo
  have hover := (RealCompute.compareAt_overlap_iff A.raw B.raw m n).1
    (RealCompute.allStagesOverlap_of_equiv A.valid B.valid hAB m n)
  apply qabs_le_of_neg_le_le
  · have hupper : (B.raw.compute n).midpoint -
        (A.raw.compute m).midpoint <=
        (B.raw.compute n).hi - (A.raw.compute m).lo := by
      grind [Rat.sub_eq_add_neg]
    have hbound : (B.raw.compute n).hi - (A.raw.compute m).lo <=
        (A.raw.compute m).width + (B.raw.compute n).width := by
      have hcross := hover.2
      unfold QInterval.width
      grind [Rat.sub_eq_add_neg]
    have := Rat.le_trans hupper hbound
    grind [Rat.sub_eq_add_neg]
  · have hupper : (A.raw.compute m).midpoint -
        (B.raw.compute n).midpoint <=
        (A.raw.compute m).hi - (B.raw.compute n).lo := by
      grind [Rat.sub_eq_add_neg]
    have hbound : (A.raw.compute m).hi - (B.raw.compute n).lo <=
        (A.raw.compute m).width + (B.raw.compute n).width := by
      have hcross := hover.1
      unfold QInterval.width
      grind [Rat.sub_eq_add_neg]
    exact Rat.le_trans hupper hbound

theorem width_antitone {bound : Nat} {margin : Rat}
    (A : PositiveInput bound margin) (k n : Nat) (hkn : k <= n) :
    (A.raw.compute n).width <= (A.raw.compute k).width := by
  apply QInterval.width_le_of_contains
  have hnest := A.valid.2.1 k n hkn
  exact ⟨hnest.1, hnest.2.2⟩

def crossRadius {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (n : Nat) : Rat :=
  margin⁻¹ * ((A.raw.compute n).width + (B.raw.compute n).width) +
    3 * approximationBudget bound n

theorem radius_le_crossRadius {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (n : Nat) :
    radius A n <= crossRadius A B n := by
  have hinv0 : 0 <= margin⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 A.margin_pos)
  have hBw : 0 <= (B.raw.compute n).width := B.valid.1 n
  unfold radius crossRadius
  exact rat_add_le_add
    (Rat.mul_le_mul_of_nonneg_left (by grind) hinv0) Rat.le_refl

theorem crossRadius_shrinks {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) :
    ShrinksToZero (crossRadius A B) := by
  intro eps
  let inputEps : QPos :=
    ⟨eps.val * margin / 8, by
      exact Rat.mul_pos (Rat.mul_pos eps.property A.margin_pos)
        ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 8))⟩
  let budgetEps : QPos :=
    ⟨eps.val / 6, by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property
        ((Rat.inv_pos).2 (by decide +kernel : (0 : Rat) < 6))⟩
  obtain ⟨NA, hNA⟩ := A.valid.2.2 inputEps
  obtain ⟨NB, hNB⟩ := B.valid.2.2 inputEps
  obtain ⟨Nc, hNc⟩ := approximationBudget_shrinks bound budgetEps
  refine ⟨Nat.max (Nat.max NA NB) Nc, ?_⟩
  intro n hn
  have hnAB : Nat.max NA NB <= n :=
    Nat.le_trans (Nat.le_max_left _ _) hn
  have hA := hNA n (Nat.le_trans (Nat.le_max_left _ _) hnAB)
  have hB := hNB n (Nat.le_trans (Nat.le_max_right _ _) hnAB)
  have hc := hNc n (Nat.le_trans (Nat.le_max_right _ _) hn)
  have hinv0 : 0 <= margin⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 A.margin_pos)
  unfold crossRadius
  calc
    margin⁻¹ * ((A.raw.compute n).width + (B.raw.compute n).width) +
        3 * approximationBudget bound n <=
      margin⁻¹ * (inputEps.val + inputEps.val) +
        3 * budgetEps.val :=
      rat_add_le_add
        (Rat.mul_le_mul_of_nonneg_left (rat_add_le_add hA hB) hinv0)
        (Rat.mul_le_mul_of_nonneg_left hc (by decide +kernel))
    _ <= eps.val := by
      dsimp [inputEps, budgetEps]
      rw [Rat.div_def]
      have hm : margin ≠ 0 := Rat.ne_of_gt A.margin_pos
      grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
        Rat.mul_inv_cancel margin hm, Rat.mul_inv_cancel]

theorem candidate_future_contained_cross_expand_of_equiv
    {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (hAB : A.raw.Equiv B.raw)
    (k n : Nat) (hkn : k <= n) :
    ((candidate A).compute n).NestedIn
      (QBox.expand ((candidate B).compute k) (crossRadius A B k)) := by
  let q := (B.raw.compute k).midpoint
  let r := (A.raw.compute n).midpoint
  let x := (approximation B k).midpoint
  let y := (approximation A n).midpoint
  have hdist0 := sqrtCertificate_midpoint_lipschitz
    A.margin_pos (approximation_spec B k) (approximation_spec A n)
    (B.margin_sq_le_center k) (A.margin_sq_le_center n)
  have hinput0 := midpoint_sub_le_width_add_width_of_equiv A B hAB n k
  have hAw := width_antitone A k n hkn
  have hinput : qabs (r - q) <=
      (A.raw.compute k).width + (B.raw.compute k).width :=
    Rat.le_trans hinput0 (rat_add_le_add hAw Rat.le_refl)
  have hwidthk := approximation_width_le_budget B k
  have hwidthn0 := approximation_width_le_budget A n
  have hbudget := approximationBudget_antitone bound hkn
  have hwidthn := Rat.le_trans hwidthn0 hbudget
  have hinv0 : 0 <= margin⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 A.margin_pos)
  have hbudget0 := approximationBudget_nonnegative bound k
  let midpointRadius : Rat :=
    margin⁻¹ * ((A.raw.compute k).width + (B.raw.compute k).width) +
      2 * approximationBudget bound k
  have hdist : qabs (y - x) <= midpointRadius := by
    calc
      qabs (y - x) <=
          margin⁻¹ * qabs (r - q) +
            (approximation B k).width + (approximation A n).width := hdist0
      _ <= margin⁻¹ * ((A.raw.compute k).width +
            (B.raw.compute k).width) +
            approximationBudget bound k + approximationBudget bound k :=
        rat_add_le_add
          (rat_add_le_add
            (Rat.mul_le_mul_of_nonneg_left hinput hinv0) hwidthk) hwidthn
      _ <= midpointRadius := by
        dsimp [midpointRadius]
        grind
  have hIk := (approximation_spec B k).2.1
  have hIn := (approximation_spec A n).2.1
  have hmk := QInterval.midpoint_mem hIk
  have hmn := QInterval.midpoint_mem hIn
  have hnk := midpoint_endpoint_bounds hIn
  have hlow : -midpointRadius <= y - x := by
    exact Rat.le_trans
      (by grind : -midpointRadius <= -qabs (y - x))
      (neg_qabs_le_self (y - x))
  have hupp : y - x <= midpointRadius :=
    Rat.le_trans (self_le_qabs (y - x)) hdist
  have hinputWidth0 : 0 <=
      (A.raw.compute k).width + (B.raw.compute k).width :=
    Rat.add_nonneg (A.valid.1 k) (B.valid.1 k)
  have hradius0 : 0 <= crossRadius A B k := by
    unfold crossRadius
    exact Rat.add_nonneg
      (Rat.mul_nonneg hinv0 hinputWidth0)
      (Rat.mul_nonneg (by decide +kernel) hbudget0)
  have hcover : midpointRadius + approximationBudget bound k <=
      crossRadius A B k := by
    unfold crossRadius
    grind
  unfold candidate QBox.ofRealInterval QBox.NestedIn QBox.expand
  simp only [QComplex.le_def]
  constructor
  · constructor
    · unfold QInterval.width at hwidthk hwidthn
      grind [Rat.sub_eq_add_neg]
    · grind
  · constructor
    · unfold QInterval.width at hwidthk hwidthn
      grind [Rat.sub_eq_add_neg]
    · grind

def crossSqrtComplex {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) : ComplexCompute :=
  ComplexCompute.cauchyStabilize (candidate A) (crossRadius A B)

theorem crossSqrtComplex_valid {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) :
    (crossSqrtComplex A B).Valid := by
  unfold crossSqrtComplex
  apply ComplexCompute.cauchyStabilize_valid
  · exact candidate_ordered A
  · exact candidate_widths_shrink A
  · intro k n hkn
    apply QBox.nested_trans (candidate_future_contained_expand A k n hkn)
    exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)
  · exact crossRadius_shrinks A B

theorem sqrtComplex_equiv_cross {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) :
    (sqrtComplex A).Equiv (crossSqrtComplex A B) := by
  unfold sqrtComplex crossSqrtComplex
  apply ComplexCompute.cauchyStabilize_equiv_of_common_candidate
  · exact candidate_ordered A
  · exact candidate_future_contained_expand A
  · intro k n hkn
    apply QBox.nested_trans (candidate_future_contained_expand A k n hkn)
    exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)

theorem crossRadius_comm {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (n : Nat) :
    crossRadius A B n = crossRadius B A n := by
  simp [crossRadius, Rat.add_comm]

theorem crossSqrtComplex_equiv_of_input_equiv
    {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (hAB : A.raw.Equiv B.raw) :
    (crossSqrtComplex A B).Equiv (crossSqrtComplex B A) := by
  intro n
  apply (ComplexCompute.compareAt_overlap_iff
    (crossSqrtComplex A B) (crossSqrtComplex B A) n n).2
  have hleft : ((candidate A).compute n).NestedIn
      ((crossSqrtComplex A B).compute n) := by
    unfold crossSqrtComplex
    apply ComplexCompute.cauchyStabilize_contains_external
      (external := fun m => (candidate A).compute m)
    · intro k m hkm
      apply QBox.nested_trans (candidate_future_contained_expand A k m hkm)
      exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)
    · exact Nat.le_refl n
  have hright : ((candidate A).compute n).NestedIn
      ((crossSqrtComplex B A).compute n) := by
    unfold crossSqrtComplex
    apply ComplexCompute.cauchyStabilize_contains_external
      (external := fun m => (candidate A).compute m)
    · intro k m hkm
      simpa [crossRadius_comm] using
        candidate_future_contained_cross_expand_of_equiv A B hAB k m hkm
    · exact Nat.le_refl n
  exact ⟨
    QComplex.le_trans hleft.1
      (QComplex.le_trans (candidate_ordered A n) hright.2),
    QComplex.le_trans hright.1
      (QComplex.le_trans (candidate_ordered A n) hleft.2)⟩

theorem sqrtComplex_equiv_of_input_equiv
    {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (hAB : A.raw.Equiv B.raw) :
    (sqrtComplex A).Equiv (sqrtComplex B) := by
  exact ComplexCompute.equiv_trans
    (sqrtComplex_valid A) (crossSqrtComplex_valid A B) (sqrtComplex_valid B)
    (sqrtComplex_equiv_cross A B)
    (ComplexCompute.equiv_trans
      (crossSqrtComplex_valid A B) (crossSqrtComplex_valid B A)
      (sqrtComplex_valid B)
      (crossSqrtComplex_equiv_of_input_equiv A B hAB)
      (ComplexCompute.equiv_symm (sqrtComplex_equiv_cross B A)))

theorem sqrt_equiv_of_input_equiv
    {bound : Nat} {margin : Rat}
    (A B : PositiveInput bound margin) (hAB : A.raw.Equiv B.raw) :
    (sqrt A).Equiv (sqrt B) :=
  ComplexCompute.realPart_equiv (sqrtComplex_equiv_of_input_equiv A B hAB)

end PositiveInput

end RepresentedPositiveSquareRoot
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