Documentation

RadiiPolynomial.TaylorODE.Computable

Computational Reflection for Weighted ℓ¹ Spaces #

This file provides computable versions of key operations and reflection lemmas that allow native_decide to verify bounds when inputs are rational.

Strategy #

For each abstract ℝ operation, we provide:

  1. A computable ℚ version
  2. A reflection lemma: abstract_ℝ (↑q) = ↑(computable_ℚ q)

This bridges the gap between abstract Mathlib definitions and numerical verification.

IsRat: Typeclass for ℝ values that are really ℚ #

Inspired by ComputableReal's IsComputable typeclass. Source: https://github.com/Timeroot/ComputableReal.git

Tracks that an ℝ value equals a specific ℚ, enabling decidable comparisons.

class IsRat (x : ) :

Typeclass asserting that x : ℝ equals IsRat.q x for some rational

Instances
    instance IsRat.instRat (r : ) :
    IsRat r
    Equations
    instance IsRat.instNat (n : ) :
    IsRat n
    Equations
    instance IsRat.instInt (z : ) :
    IsRat z
    Equations
    instance IsRat.instNeg {x : } [hx : IsRat x] :
    IsRat (-x)
    Equations
    instance IsRat.instInv {x : } [hx : IsRat x] :
    Equations
    instance IsRat.instAdd {x y : } [hx : IsRat x] [hy : IsRat y] :
    IsRat (x + y)
    Equations
    instance IsRat.instSub {x y : } [hx : IsRat x] [hy : IsRat y] :
    IsRat (x - y)
    Equations
    instance IsRat.instMul {x y : } [hx : IsRat x] [hy : IsRat y] :
    IsRat (x * y)
    Equations
    instance IsRat.instDiv {x y : } [hx : IsRat x] [hy : IsRat y] :
    IsRat (x / y)
    Equations
    instance IsRat.instPow {x : } [hx : IsRat x] (n : ) :
    IsRat (x ^ n)
    Equations
    instance IsRat.instAbs {x : } [hx : IsRat x] :
    Equations
    instance IsRat.instDecidableLE {x y : } [hx : IsRat x] [hy : IsRat y] :

    Decidable ≤ for IsRat values

    Equations
    instance IsRat.instDecidableLT {x y : } [hx : IsRat x] [hy : IsRat y] :
    Decidable (x < y)

    Decidable < for IsRat values

    Equations
    instance IsRat.instDecidableEq {x y : } [hx : IsRat x] [hy : IsRat y] :
    Decidable (x = y)

    Decidable = for IsRat values

    Equations

    Positive Rationals #

    structure PosRat :

    Positive rationals

    Instances For
      def instDecidableEqPosRat.decEq (x✝ x✝¹ : PosRat) :
      Decidable (x✝ = x✝¹)
      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        @[simp]
        theorem PosRat.coe_pos (ν : PosRat) :
        0 < ν.val
        noncomputable def PosRat.toPosReal (ν : PosRat) :

        Convert to PosReal

        Equations
        Instances For
          @[simp]
          theorem PosRat.toPosReal_val (ν : PosRat) :
          ν.toPosReal = ν.val

          Computable Absolute Value #

          def Rat.abs (q : ) :

          Computable absolute value on ℚ

          Equations
          Instances For
            @[simp]
            theorem Rat.abs_nonneg (q : ) :
            0 q.abs
            theorem Rat.abs_eq_abs (q : ) :
            q.abs = |q|

            Computable Scaled Norm #

            def scaledNorm_rat (ν : ) (n : ) (x : ) :

            Computable scaled norm: |x| * ν^n

            Equations
            Instances For
              theorem scaledNorm_eq_rat (ν : PosRat) (n : ) (x : ) :
              |x| * ν.toPosReal ^ n = (scaledNorm_rat ν.val n x)

              Reflection: scaledNorm on ℚ inputs equals ℚ computation

              Computable Weighted ℓ¹ Norm (Finite) #

              def finl1Norm_rat {n : } (ν : ) (x : Fin n) :

              Computable finite weighted ℓ¹ norm: Σᵢ |xᵢ| * νⁱ

              Equations
              Instances For
                theorem finl1Norm_eq_rat {n : } (ν : PosRat) (x : Fin n) :
                i : Fin n, |x i| * ν.toPosReal ^ i = (finl1Norm_rat ν.val x)

                Reflection for finite weighted norm

                Computable Matrix Column Norm #

                def matrixColNorm_rat {m n : } (ν : ) (A : Matrix (Fin m) (Fin n) ) (j : Fin n) :

                Computable column norm: (1/ν^j) * Σᵢ |Aᵢⱼ| * νⁱ

                Equations
                Instances For
                  def finWeightedMatrixNorm_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) :

                  Computable matrix norm: max over columns

                  Equations
                  Instances For

                    Computable Cauchy Product (Finite) #

                    def cauchyProduct_rat (a b : ) (n : ) :

                    Computable Cauchy product at index n

                    Equations
                    Instances For
                      def cauchyProductFin_rat {n : } (a b : Fin (n + 1)) (k : ) :

                      Cauchy product for finite sequences (zero-padded)

                      Equations
                      Instances For

                        Example: Reflection for Y₀ Finite Part #

                        The finite part of Y₀ is: Σᵢ |Σⱼ Aᵢⱼ * Fⱼ| * νⁱ

                        This is computable when A, F are rational matrices/vectors.

                        def matVecMul_rat {m n : } (A : Matrix (Fin m) (Fin n) ) (v : Fin n) :
                        Fin m

                        Computable matrix-vector product

                        Equations
                        Instances For
                          def Y₀_fin_rat {m n : } (ν : ) (A : Matrix (Fin m) (Fin n) ) (v : Fin n) :

                          Computable Y₀ finite part: Σᵢ |[A·v]ᵢ| * νⁱ

                          Equations
                          Instances For

                            Decidability for ℚ comparisons #

                            Computable Max (Finset.sup') #

                            def finsetMax_rat {α : Type u_1} (s : Finset α) (hs : s.Nonempty) (f : α) :

                            Computable max over a Finset

                            Equations
                            Instances For
                              theorem finsetSup'_eq_rat {α : Type u_1} (s : Finset α) (hs : s.Nonempty) (f : α) :
                              (s.sup' hs f) = s.sup' hs fun (a : α) => (f a)

                              Reflection for Finset.sup' when f maps to ℚ

                              theorem finWeightedMatrixNorm_rat_eq_sup' {n : } (ν : PosRat) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) :
                              (finWeightedMatrixNorm_rat ν.val A) = Finset.univ.sup' fun (j : Fin (n + 1)) => (matrixColNorm_rat ν.val A j)

                              Expansion for finWeightedMatrixNorm_rat

                              Finite Sequence as Zero-Padded Infinite Sequence #

                              def finToSeq_rat {n : } (x : Fin (n + 1)) :

                              Zero-pad a finite sequence

                              Equations
                              Instances For
                                @[simp]
                                theorem finToSeq_rat_lt {n : } (x : Fin (n + 1)) (k : ) (hk : k n) :
                                finToSeq_rat x k = x k,
                                @[simp]
                                theorem finToSeq_rat_ge {n : } (x : Fin (n + 1)) (k : ) (hk : n < k) :

                                Computable Cauchy Product with Reflection #

                                def cauchyProduct_fin_rat {n : } (a b : Fin (n + 1)) (k : ) :

                                Cauchy product at index k for zero-padded sequences

                                Equations
                                Instances For
                                  theorem cauchyProduct_fin_rat_eq {n : } (a b : Fin (n + 1)) (k : ) :

                                  Component-wise Cauchy product definition

                                  theorem cauchyProduct_cast (a b : ) (k : ) :
                                  (cauchyProduct_rat a b k) = ((fun (i : ) => (a i)) fun (i : ) => (b i)) k

                                  Reflection: CauchyProduct on ℚ sequences casts correctly

                                  F(ā) = ā ⋆ ā - c computation #

                                  def F_component_rat {n : } (a : Fin (n + 1)) (c : ) (k : ) :

                                  Computable F₀ = ā₀² - λ₀

                                  Equations
                                  Instances For
                                    def paramSeq_rat (lam0 : ) :

                                    The paramSeq c = (λ₀, 1, 0, 0, ...)

                                    Equations
                                    Instances For
                                      @[simp]
                                      theorem paramSeq_rat_zero (lam0 : ) :
                                      paramSeq_rat lam0 0 = lam0
                                      @[simp]
                                      theorem paramSeq_rat_one (lam0 : ) :
                                      paramSeq_rat lam0 1 = 1
                                      @[simp]
                                      theorem paramSeq_rat_ge_two (lam0 : ) (k : ) (hk : 2 k) :
                                      paramSeq_rat lam0 k = 0

                                      Full Y₀ Computation #

                                      def Y₀_finite_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) (lam0 : ) :

                                      Y₀ finite part: Σᵢ₌₀ᴺ |[A·F(ā)]ᵢ| * νⁱ

                                      Equations
                                      Instances For
                                        def Y₀_tail_rat {n : } (ν : ) (a : Fin (n + 1)) :

                                        Y₀ tail part: (1/(2|ā₀|)) * Σₙ₌ₙ₊₁²ᴺ (Σ convolution terms) * νⁿ

                                        Equations
                                        Instances For
                                          def Y₀_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) (lam0 : ) :

                                          Full Y₀ bound

                                          Equations
                                          Instances For

                                            Z₁ Computation (simplest) #

                                            def Z₁_rat {n : } (ν : ) (a : Fin (n + 1)) :

                                            Z₁ = (1/|ā₀|) * Σₙ₌₁ᴺ |āₙ| * νⁿ

                                            Equations
                                            Instances For

                                              Z₀ Computation #

                                              def DF_fin_rat {n : } (a : Fin (n + 1)) :
                                              Matrix (Fin (n + 1)) (Fin (n + 1))

                                              DF(ā) finite block: 2 * lower triangular Toeplitz from ā. Takes raw ℚ vector. Used by Z₀_rat, Z₂_rat.

                                              Equations
                                              Instances For
                                                def IADF_rat {n : } (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) :
                                                Matrix (Fin (n + 1)) (Fin (n + 1))

                                                I - A·DF(ā)

                                                Equations
                                                Instances For
                                                  def Z₀_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) :

                                                  Z₀ = ‖I - A·DF(ā)‖_{1,ν}

                                                  Equations
                                                  Instances For

                                                    Z₂ Computation #

                                                    def Z₂_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) :

                                                    Z₂ = 2 * max(‖A‖_{1,ν}, 1/(2|ā₀|))

                                                    Equations
                                                    Instances For

                                                      Full Radii Polynomial #

                                                      def radiiPoly_rat (Y₀ Z₀ Z₁ Z₂ r : ) :

                                                      p(r) = Z₂·r² - (1 - Z₀ - Z₁)·r + Y₀

                                                      Equations
                                                      Instances For
                                                        def computeRadiiPoly_rat {n : } (ν : ) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (a : Fin (n + 1)) (lam0 r : ) :

                                                        All-in-one radii polynomial computation

                                                        Equations
                                                        Instances For

                                                          Reflection Lemmas: Abstract ℝ = Computable ℚ #

                                                          These lemmas bridge abstract Mathlib definitions to computable ℚ versions, enabling native_decide verification of bounds.

                                                          def Matrix.castRat {m k : } (A : Matrix (Fin m) (Fin k) ) :
                                                          Matrix (Fin m) (Fin k)

                                                          Cast ℚ matrix to ℝ matrix

                                                          Equations
                                                          Instances For
                                                            def Fin.castRat {k : } (v : Fin k) :
                                                            Fin k

                                                            Cast ℚ vector to ℝ vector

                                                            Equations
                                                            Instances For
                                                              theorem matrixColNorm_eq_rat {n : } (ν : PosRat) (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ) (j : Fin (n + 1)) :

                                                              Reflection for matrixColNorm

                                                              Reflection for finWeightedMatrixNorm

                                                              theorem Z₁_bound_eq_rat {n : } (ν : PosRat) (a : Fin (n + 1)) :
                                                              1 / |Fin.castRat a 0| * kFinset.Icc 1 n, |finToSeq_rat a k| * ν.toPosReal ^ k = (Z₁_rat ν.val a)

                                                              Reflection for Z₁_bound: (1/|ā₀|) * Σₙ₌₁ᴺ |āₙ| * νⁿ

                                                              theorem finToSeq_rat_cast {n : } (a : Fin (n + 1)) (k : ) :
                                                              (finToSeq_rat a k) = if h : k n then (a k, ) else 0

                                                              Helper: finToSeq_rat casts correctly

                                                              theorem cauchyProduct_fin_eq_rat {n : } (a b : Fin (n + 1)) (k : ) :
                                                              ((fun (i : ) => (finToSeq_rat a i)) fun (i : ) => (finToSeq_rat b i)) k = (cauchyProduct_fin_rat a b k)

                                                              Reflection for Cauchy product of finite ℚ sequences

                                                              ApproxSolution over ℚ #

                                                              A ℚ version of ApproxSolution that enables computational reflection.

                                                              structure ApproxSolution_rat (N : ) :

                                                              Approximate solution with ℚ coefficients

                                                              Instances For

                                                                Convert to real ApproxSolution

                                                                Equations
                                                                Instances For

                                                                  The ℚ sequence (zero-padded)

                                                                  Equations
                                                                  Instances For
                                                                    @[simp]
                                                                    theorem ApproxSolution_rat.toReal_aBar_fin {N : } (a : ApproxSolution_rat N) (i : Fin (N + 1)) :
                                                                    a.toReal.aBar_fin i = (a.aBar_fin i)

                                                                    toSeq of toReal = cast of toSeq_rat

                                                                    lpWeighted.toSeq of toL1 = cast of toSeq_rat

                                                                    Matrix over ℚ #

                                                                    def Matrix.ofRat {m n : } (A : Matrix (Fin m) (Fin n) ) :
                                                                    Matrix (Fin m) (Fin n)

                                                                    ℚ matrix cast to ℝ

                                                                    Equations
                                                                    Instances For
                                                                      @[simp]
                                                                      theorem Matrix.ofRat_apply {m n : } (A : Matrix (Fin m) (Fin n) ) (i : Fin m) (j : Fin n) :
                                                                      A.ofRat i j = (A i j)

                                                                      Full Reflection Lemmas for Bounds #

                                                                      def DF_fin_of_rat {N : } (a : ApproxSolution_rat N) :
                                                                      Matrix (Fin (N + 1)) (Fin (N + 1))

                                                                      DF(ā) finite block from ApproxSolution_rat. Same computation as DF_fin_rat, but takes ApproxSolution_rat instead of raw ℚ vector. Used for reflection lemmas connecting abstract Example_7_7.DF_fin to computable version.

                                                                      Equations
                                                                      Instances For
                                                                        theorem Z₀_bound_eq_rat' {N : } (ν : PosRat) (a : ApproxSolution_rat N) (A : Matrix (Fin (N + 1)) (Fin (N + 1)) ) :

                                                                        Z₀_bound on ℚ inputs = Z₀_rat

                                                                        theorem Z₂_bound_eq_rat' {N : } (ν : PosRat) (a : ApproxSolution_rat N) (A : Matrix (Fin (N + 1)) (Fin (N + 1)) ) :

                                                                        Z₁_bound on ℚ inputs = Z₁_rat

                                                                        def F_fin_rat {N : } (lam0 : ) (a : Fin (N + 1)) :
                                                                        Fin (N + 1)

                                                                        F_fin on ℚ inputs: the finite components of F(ā) = ā⋆ā - c

                                                                        Equations
                                                                        Instances For
                                                                          theorem F_fin_eq_rat {N : } (ν : PosRat) (lam0 : ) (a : ApproxSolution_rat N) (n : Fin (N + 1)) :
                                                                          Example_7_7.F_fin (↑lam0) a.toReal n = (F_fin_rat lam0 a.aBar_fin n)

                                                                          F_fin reflection: abstract F_fin equals F_fin_rat on ℚ inputs

                                                                          theorem Y₀_bound_eq_rat' {N : } (ν : PosRat) (lam0 : ) (a : ApproxSolution_rat N) (A : Matrix (Fin (N + 1)) (Fin (N + 1)) ) :
                                                                          Example_7_7.Y₀_bound (↑lam0) a.toReal A.ofRat = (Y₀_rat ν.val A a.aBar_fin lam0)

                                                                          Y₀_bound on ℚ inputs = Y₀_rat