Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · RealMultiplication · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_RealMultiplication

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexMultiplication
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Differential

set_option autoImplicit true

/-!
# General multiplication of raw interval reals

`RealCompute.mul` is the literal four-corner interval product already defined in
`Basic`.  The early API certified it only under nonnegativity hypotheses.
This file proves the general signed closure theorem directly from finite
rational interval estimates.  No completed real multiplication is used.
-/

namespace ComputableAnalysis

namespace QInterval

/-- Both endpoints of a rational interval are bounded in absolute value. -/
def AbsBounded (I : QInterval) (B : Rat) : Prop :=
  qabs I.lo <= B /\ qabs I.hi <= B

/-- A strictly positive rational bound for both endpoints. -/
def absRadius (I : QInterval) : Rat :=
  1 + qabs I.lo + qabs I.hi

theorem absRadius_pos (I : QInterval) : 0 < I.absRadius := by
  unfold absRadius
  grind [qabs_nonneg I.lo, qabs_nonneg I.hi]

theorem absBounded_absRadius (I : QInterval) :
    I.AbsBounded I.absRadius := by
  unfold AbsBounded absRadius
  constructor
  · grind [qabs_nonneg I.hi]
  · grind [qabs_nonneg I.lo]

theorem AbsBounded.mono {I : QInterval} {B C : Rat}
    (hI : I.AbsBounded B) (hBC : B <= C) : I.AbsBounded C := by
  exact ⟨Rat.le_trans hI.1 hBC, Rat.le_trans hI.2 hBC⟩

private theorem qabs_le_of_endpoint_bounds {a b x B : Rat}
    (ha : qabs a <= B) (hb : qabs b <= B)
    (hax : a <= x) (hxb : x <= b) : qabs x <= B := by
  apply qabs_le_of_neg_le_le
  · calc
      -B <= -qabs a := Rat.neg_le_neg ha
      _ <= a := neg_qabs_le_self a
      _ <= x := hax
  · calc
      x <= b := hxb
      _ <= qabs b := self_le_qabs b
      _ <= B := hb

/-- An ordered interval contained in an absolute-bounded interval inherits
the same bound. -/
theorem absBounded_of_contains {inner outer : QInterval} {B : Rat}
    (hinner : inner.lo <= inner.hi)
    (hcontains : outer.ContainsInterval inner)
    (houter : outer.AbsBounded B) : inner.AbsBounded B := by
  constructor
  · exact qabs_le_of_endpoint_bounds houter.1 houter.2
      hcontains.1 (Rat.le_trans hinner hcontains.2)
  · exact qabs_le_of_endpoint_bounds houter.1 houter.2
      (Rat.le_trans hcontains.1 hinner) hcontains.2

/-- Every rational point in an absolute-bounded interval inherits the same
absolute bound. -/
theorem qabs_le_of_mem_absBounded {I : QInterval} {x B : Rat}
    (hI : I.AbsBounded B) (hx : I.lo <= x /\ x <= I.hi) :
    qabs x <= B :=
  qabs_le_of_endpoint_bounds hI.1 hI.2 hx.1 hx.2

/-- Products of two pairs of overlapping ordered intervals overlap. -/
theorem mulRealInterval_overlaps_of_overlaps
    {A A' B B' : QInterval}
    (hA : A.lo <= A.hi) (hA' : A'.lo <= A'.hi)
    (hB : B.lo <= B.hi) (hB' : B'.lo <= B'.hi)
    (hAA' : A.Overlaps A') (hBB' : B.Overlaps B') :
    (QBox.mulRealInterval A.lo A.hi B.lo B.hi).Overlaps
      (QBox.mulRealInterval A'.lo A'.hi B'.lo B'.hi) := by
  unfold Overlaps at hAA' hBB'
  let x : Rat := if A.lo <= A'.lo then A'.lo else A.lo
  let y : Rat := if B.lo <= B'.lo then B'.lo else B.lo
  have hxA : A.lo <= x := by dsimp [x]; split <;> grind
  have hxA' : A'.lo <= x := by dsimp [x]; split <;> grind
  have hxAh : x <= A.hi := by
    dsimp [x]
    split <;> grind
  have hxA'h : x <= A'.hi := by
    dsimp [x]
    split <;> grind
  have hyB : B.lo <= y := by dsimp [y]; split <;> grind
  have hyB' : B'.lo <= y := by dsimp [y]; split <;> grind
  have hyBh : y <= B.hi := by
    dsimp [y]
    split <;> grind
  have hyB'h : y <= B'.hi := by
    dsimp [y]
    split <;> grind
  have hp := QBox.mulRealInterval_contains hxA hxAh hyB hyBh
  have hp' := QBox.mulRealInterval_contains hxA' hxA'h hyB' hyB'h
  exact ⟨Rat.le_trans hp.1 hp'.2, Rat.le_trans hp'.1 hp.2⟩

private theorem qabs_minRat_le {a b R : Rat}
    (ha : qabs a <= R) (hb : qabs b <= R) :
    qabs (minRat a b) <= R := by
  unfold minRat
  split <;> assumption

private theorem qabs_maxRat2_le {a b R : Rat}
    (ha : qabs a <= R) (hb : qabs b <= R) :
    qabs (maxRat2 a b) <= R := by
  unfold maxRat2
  split <;> assumption

private theorem qabs_min4_le {a b c d R : Rat}
    (ha : qabs a <= R) (hb : qabs b <= R)
    (hc : qabs c <= R) (hd : qabs d <= R) :
    qabs (min4 a b c d) <= R := by
  exact qabs_minRat_le (qabs_minRat_le ha hb) (qabs_minRat_le hc hd)

private theorem qabs_max4_le {a b c d R : Rat}
    (ha : qabs a <= R) (hb : qabs b <= R)
    (hc : qabs c <= R) (hd : qabs d <= R) :
    qabs (max4 a b c d) <= R := by
  exact qabs_maxRat2_le (qabs_maxRat2_le ha hb) (qabs_maxRat2_le hc hd)

/-- The endpoints selected by the four-corner product inherit the product of
two supplied absolute endpoint bounds. -/
theorem mulRealInterval_absBounded
    {I J : QInterval} {A B : Rat}
    (hI : I.AbsBounded A) (hJ : J.AbsBounded B) :
    (QBox.mulRealInterval I.lo I.hi J.lo J.hi).AbsBounded (A * B) := by
  have hll : qabs (I.lo * J.lo) <= A * B := by
    rw [qabs_mul]
    exact rat_mul_le_mul_of_nonneg (qabs_nonneg _) hI.1
      (qabs_nonneg _) hJ.1
  have hlh : qabs (I.lo * J.hi) <= A * B := by
    rw [qabs_mul]
    exact rat_mul_le_mul_of_nonneg (qabs_nonneg _) hI.1
      (qabs_nonneg _) hJ.2
  have hhl : qabs (I.hi * J.lo) <= A * B := by
    rw [qabs_mul]
    exact rat_mul_le_mul_of_nonneg (qabs_nonneg _) hI.2
      (qabs_nonneg _) hJ.1
  have hhh : qabs (I.hi * J.hi) <= A * B := by
    rw [qabs_mul]
    exact rat_mul_le_mul_of_nonneg (qabs_nonneg _) hI.2
      (qabs_nonneg _) hJ.2
  change qabs (min4 (I.lo * J.lo) (I.lo * J.hi)
      (I.hi * J.lo) (I.hi * J.hi)) <= A * B /\
    qabs (max4 (I.lo * J.lo) (I.lo * J.hi)
      (I.hi * J.lo) (I.hi * J.hi)) <= A * B
  exact ⟨qabs_min4_le hll hlh hhl hhh,
    qabs_max4_le hll hlh hhl hhh⟩

end QInterval

namespace RealCompute

/-! The public signed multiplication laws now live in `ComplexMultiplication`.
Retain these earlier proof bodies privately for the interval-function assembly
below, without redeclaring the imported public theorem names. -/

/-- Every stage of the literal product of valid raw reals is ordered. -/
private theorem legacyMulComputeOrdered {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) (n : Nat) :
    0 <= ((mul x y).compute n).width := by
  change 0 <= (QBox.mulRealInterval
    (x.compute n).lo (x.compute n).hi
    (y.compute n).lo (y.compute n).hi).width
  have hordered := QBox.mulRealInterval_ordered
    (interval_order_of_valid x hx n) (interval_order_of_valid y hy n)
  unfold QInterval.width
  grind [Rat.sub_eq_add_neg]

/-- Literal product intervals refine whenever both input intervals refine. -/
private theorem legacyMulComputeNested {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) {n m : Nat} (hnm : n <= m) :
    ((mul x y).compute n).ContainsInterval ((mul x y).compute m) := by
  have hxn := hx.2.1 n m hnm
  have hyn := hy.2.1 n m hnm
  change (QBox.mulRealInterval
      (x.compute n).lo (x.compute n).hi
      (y.compute n).lo (y.compute n).hi).ContainsInterval
    (QBox.mulRealInterval
      (x.compute m).lo (x.compute m).hi
      (y.compute m).lo (y.compute m).hi)
  exact QBox.mulRealInterval_nested
    hxn.1 hxn.2.1 hxn.2.2 hyn.1 hyn.2.1 hyn.2.2

/-- Order, nesting, and a supplied width-shrink proof assemble general
raw-real product validity. -/
private theorem legacyMulValidOfWidthsShrink {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid)
    (hshrink : WidthsShrinkToZero (mul x y).compute) :
    (mul x y).Valid := by
  constructor
  · exact legacyMulComputeOrdered hx hy
  · constructor
    · intro n m hnm
      have hnest := legacyMulComputeNested hx hy hnm
      have horderWidth := legacyMulComputeOrdered hx hy m
      have horder : ((mul x y).compute m).lo <=
          ((mul x y).compute m).hi := by
        unfold QInterval.width at horderWidth
        grind [Rat.sub_eq_add_neg]
      exact ⟨hnest.1, horder, hnest.2⟩
    · exact hshrink

/-- Arbitrary valid raw interval reals are closed under the signed
four-corner product. -/
private theorem legacyMulValid {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) : (mul x y).Valid := by
  apply legacyMulValidOfWidthsShrink hx hy
  intro eps
  let Bx : Rat := (x.compute 0).absRadius
  let By : Rat := (y.compute 0).absRadius
  let B : Rat := Bx + By
  have hBxpos : 0 < Bx := QInterval.absRadius_pos _
  have hBypos : 0 < By := QInterval.absRadius_pos _
  have hBpos : 0 < B := by dsimp [B]; grind
  have h4B : 0 < (4 : Rat) * B :=
    Rat.mul_pos (by decide +kernel) hBpos
  let delta : QPos :=
    { val := eps.val / ((4 : Rat) * B)
      property := by
        rw [Rat.div_def]
        exact Rat.mul_pos eps.property ((Rat.inv_pos).2 h4B) }
  obtain ⟨Nx, hNx⟩ := hx.2.2 delta
  obtain ⟨Ny, hNy⟩ := hy.2.2 delta
  refine ⟨Nat.max Nx Ny, ?_⟩
  intro n hn
  have hxw := hNx n (Nat.le_trans (Nat.le_max_left _ _) hn)
  have hyw := hNy n (Nat.le_trans (Nat.le_max_right _ _) hn)
  have hxb : (x.compute n).AbsBounded B := by
    apply QInterval.AbsBounded.mono
      (QInterval.absBounded_of_contains
        (interval_order_of_valid x hx n)
        ⟨(hx.2.1 0 n (Nat.zero_le n)).1,
          (hx.2.1 0 n (Nat.zero_le n)).2.2⟩
        (QInterval.absBounded_absRadius _))
    dsimp [B, Bx, By]
    grind [Rat.le_of_lt hBypos]
  have hyb : (y.compute n).AbsBounded B := by
    apply QInterval.AbsBounded.mono
      (QInterval.absBounded_of_contains
        (interval_order_of_valid y hy n)
        ⟨(hy.2.1 0 n (Nat.zero_le n)).1,
          (hy.2.1 0 n (Nat.zero_le n)).2.2⟩
        (QInterval.absBounded_absRadius _))
    dsimp [B, Bx, By]
    grind [Rat.le_of_lt hBxpos]
  have hp := QBox.mulRealInterval_width_le_of_abs_bounded
    (interval_order_of_valid x hx n) (interval_order_of_valid y hy n)
    hxb.1 hyb.1 hyb.2
  have hsum :
      (x.compute n).width + (y.compute n).width <= 2 * delta.val := by
    grind
  calc
    ((mul x y).compute n).width <=
        2 * B * ((x.compute n).width + (y.compute n).width) := hp
    _ <= 2 * B * (2 * delta.val) :=
      Rat.mul_le_mul_of_nonneg_left hsum (by grind [Rat.le_of_lt hBpos])
    _ = eps.val := by
      dsimp [delta]
      rw [Rat.div_def]
      have hne : (4 : Rat) * B ≠ 0 := Rat.ne_of_gt h4B
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]

/-- General signed multiplication respects overlap equality. -/
private theorem legacyMulEquiv {x x' y y' : RealCompute}
    (hx : x.Valid) (hx' : x'.Valid) (hy : y.Valid) (hy' : y'.Valid)
    (hxx' : x.Equiv x') (hyy' : y.Equiv y') :
    (mul x y).Equiv (mul x' y') := by
  intro n
  have hxx := (compareAt_overlap_iff x x' n n).1
    (sameStageOverlap_of_equiv hx hx' hxx' n)
  have hyy := (compareAt_overlap_iff y y' n n).1
    (sameStageOverlap_of_equiv hy hy' hyy' n)
  apply (compareAt_overlap_iff (mul x y) (mul x' y') n n).2
  exact QInterval.mulRealInterval_overlaps_of_overlaps
    (interval_order_of_valid x hx n) (interval_order_of_valid x' hx' n)
    (interval_order_of_valid y hy n) (interval_order_of_valid y' hy' n)
    hxx hyy

end RealCompute

namespace RealFunRaw

/-- Pointwise multiplication of arbitrary valid interval-real functions is
valid.  Stage-zero enclosures provide the finite local bounds automatically. -/
theorem mul_valid {f g : RealFunRaw} (hf : f.Valid) (hg : g.Valid) :
    (mul f g).Valid := by
  intro x hx
  let X : RealCompute := { compute := f.compute x }
  let Y : RealCompute := { compute := g.compute x }
  have hX : X.Valid := by
    simpa [X, RealCompute.Valid, RealFunRaw.applyCompute] using hf x hx.1
  have hY : Y.Valid := by
    simpa [Y, RealCompute.Valid, RealFunRaw.applyCompute] using hg x hx.2
  have hproduct : (RealCompute.mul X Y).Valid := RealCompute.mul_valid hX hY
  change RealCompute.ValidCompute (RealCompute.mulCompute X Y) at hproduct
  change RealCompute.ValidCompute (RealCompute.mulCompute X Y)
  exact hproduct

end RealFunRaw

namespace FunctionOnInterval

/-- A uniform finite rational absolute bound for every endpoint produced by
an interval function on its chart.  This is executable quantitative metadata,
not a compactness theorem: clients provide the radius and its endpoint proof. -/
structure UniformAbsBound (F : FunctionOnInterval) where
  radius : Rat
  radius_pos : 0 < radius
  endpoints : forall x (hx : inDomainInterval F.lower F.upper x) n,
    (F.compute x hx n).AbsBounded radius

namespace UniformAbsBound

/-- Enlarge a uniform bound to any larger strictly positive rational radius. -/
def mono {F : FunctionOnInterval} (B : UniformAbsBound F)
    (radius : Rat) (hradius : 0 < radius) (hle : B.radius <= radius) :
    UniformAbsBound F where
  radius := radius
  radius_pos := hradius
  endpoints := fun x hx n => (B.endpoints x hx n).mono hle

end UniformAbsBound

/-- Pointwise multiplication of arbitrary valid functions on a common
rational interval.  Unlike the earlier positive-bounded constructor, no sign
or externally supplied range bound is required. -/
def mul
    (F G : FunctionOnInterval)
    (same_lower : F.lower = G.lower)
    (same_upper : F.upper = G.upper) : FunctionOnInterval where
  raw :=
    { definedAt := fun x =>
        inDomainInterval F.lower F.upper x /\
          F.raw.definedAt x /\ G.raw.definedAt x
      compute := fun x hx n =>
        QBox.mulRealInterval
          (F.raw.compute x hx.2.1 n).lo (F.raw.compute x hx.2.1 n).hi
          (G.raw.compute x hx.2.2 n).lo (G.raw.compute x hx.2.2 n).hi }
  lower := F.lower
  upper := F.upper
  defined_on := by
    intro x hx
    refine ⟨hx, F.defined_on x hx, G.defined_on x ?_⟩
    constructor
    · rw [← same_lower]
      exact hx.1
    · rw [← same_upper]
      exact hx.2
  valid_on := by
    intro x hx
    let X : RealCompute := { compute := F.raw.compute x hx.2.1 }
    let Y : RealCompute := { compute := G.raw.compute x hx.2.2 }
    have hX : X.Valid := by
      simpa [X, RealCompute.Valid] using F.valid_on x hx.2.1
    have hY : Y.Valid := by
      simpa [Y, RealCompute.Valid] using G.valid_on x hx.2.2
    have hproduct := RealCompute.mul_valid hX hY
    change RealCompute.ValidCompute
      (fun n => QBox.mulRealInterval
        (F.raw.compute x hx.2.1 n).lo (F.raw.compute x hx.2.1 n).hi
        (G.raw.compute x hx.2.2 n).lo (G.raw.compute x hx.2.2 n).hi)
    change RealCompute.ValidCompute (RealCompute.mulCompute X Y) at hproduct
    exact hproduct

@[simp] theorem mul_compute
    (F G : FunctionOnInterval)
    (same_lower : F.lower = G.lower)
    (same_upper : F.upper = G.upper)
    (x : Rat) (hx : inDomainInterval F.lower F.upper x) (n : Nat) :
    (mul F G same_lower same_upper).compute x
      (by simpa [mul] using
        (show inDomainInterval F.lower F.upper x from hx)) n =
      QBox.mulRealInterval
        (F.compute x hx n).lo (F.compute x hx n).hi
        (G.compute x (by
          constructor
          · rw [← same_lower]
            exact hx.1
          · rw [← same_upper]
            exact hx.2) n).lo
        (G.compute x (by
          constructor
          · rw [← same_lower]
            exact hx.1
          · rw [← same_upper]
            exact hx.2) n).hi := by
  rfl

namespace UniformAbsBound

/-- The pointwise product of uniformly bounded interval functions is
uniformly bounded by the product of their radii. -/
def mul {F G : FunctionOnInterval}
    (same_lower : F.lower = G.lower) (same_upper : F.upper = G.upper)
    (BF : UniformAbsBound F) (BG : UniformAbsBound G) :
    UniformAbsBound (FunctionOnInterval.mul F G same_lower same_upper) where
  radius := BF.radius * BG.radius
  radius_pos := Rat.mul_pos BF.radius_pos BG.radius_pos
  endpoints := by
    intro x hx n
    have hFx : inDomainInterval F.lower F.upper x := by
      simpa [FunctionOnInterval.mul] using hx
    have hGx : inDomainInterval G.lower G.upper x := by
      constructor
      · rw [← same_lower]
        exact hFx.1
      · rw [← same_upper]
        exact hFx.2
    change (QBox.mulRealInterval
      (F.compute x hFx n).lo (F.compute x hFx n).hi
      (G.compute x hGx n).lo (G.compute x hGx n).hi).AbsBounded
        (BF.radius * BG.radius)
    exact QInterval.mulRealInterval_absBounded
      (BF.endpoints x hFx n) (BG.endpoints x hGx n)

end UniformAbsBound

/-- General signed pointwise multiplication transports along the local
representation graph. -/
theorem equivalent_mul
    (F F' G G' : FunctionOnInterval)
    (hFF' : Equivalent F F') (hGG' : Equivalent G G')
    (same_lower_FG : F.lower = G.lower) (same_upper_FG : F.upper = G.upper)
    (same_lower_F'G' : F'.lower = G'.lower)
    (same_upper_F'G' : F'.upper = G'.upper) :
    Equivalent
      (FunctionOnInterval.mul F G same_lower_FG same_upper_FG)
      (FunctionOnInterval.mul F' G' same_lower_F'G' same_upper_F'G') := by
  refine ⟨hFF'.1, hFF'.2.1, ?_⟩
  intro x hx hx'
  let hxG : inDomainInterval G.lower G.upper x :=
    ⟨by rw [← same_lower_FG]; exact hx.1,
      by rw [← same_upper_FG]; exact hx.2⟩
  let hxG' : inDomainInterval G'.lower G'.upper x :=
    ⟨by rw [← same_lower_F'G']; exact hx'.1,
      by rw [← same_upper_F'G']; exact hx'.2⟩
  have hXF : (PartialRealFunRaw.apply F.raw F.valid_on x
      (F.defined_on x hx)).Valid := by
    change RealCompute.ValidCompute (F.raw.compute x (F.defined_on x hx))
    exact F.valid_on x (F.defined_on x hx)
  have hXG : (PartialRealFunRaw.apply G.raw G.valid_on x
      (G.defined_on x hxG)).Valid := by
    change RealCompute.ValidCompute (G.raw.compute x (G.defined_on x hxG))
    exact G.valid_on x (G.defined_on x hxG)
  have hXF' : (PartialRealFunRaw.apply F'.raw F'.valid_on x
      (F'.defined_on x hx')).Valid := by
    change RealCompute.ValidCompute (F'.raw.compute x (F'.defined_on x hx'))
    exact F'.valid_on x (F'.defined_on x hx')
  have hXG' : (PartialRealFunRaw.apply G'.raw G'.valid_on x
      (G'.defined_on x hxG')).Valid := by
    change RealCompute.ValidCompute (G'.raw.compute x (G'.defined_on x hxG'))
    exact G'.valid_on x (G'.defined_on x hxG')
  change (RealCompute.mul
      (PartialRealFunRaw.apply F.raw F.valid_on x (F.defined_on x hx))
      (PartialRealFunRaw.apply G.raw G.valid_on x
        (G.defined_on x hxG))).Equiv
    (RealCompute.mul
      (PartialRealFunRaw.apply F'.raw F'.valid_on x
        (F'.defined_on x hx'))
      (PartialRealFunRaw.apply G'.raw G'.valid_on x
        (G'.defined_on x hxG')))
  exact RealCompute.mul_equiv hXF hXF' hXG hXG'
    (hFF'.2.2 x hx hx') (hGG'.2.2 x hxG hxG')

end FunctionOnInterval

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