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:
- A computable ℚ version
- 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.
Equations
- IsRat.instOfNat0 = { q := 0, eq := IsRat.instOfNat0._proof_1 }
Equations
- IsRat.instOfNat1 = { q := 1, eq := IsRat.instOfNat1._proof_1 }
Decidable ≤ for IsRat values
Equations
Decidable < for IsRat values
Equations
Decidable = for IsRat values
Equations
Positive Rationals #
Equations
- One or more equations did not get rendered due to their size.
Instances For
Computable Absolute Value #
Computable Scaled Norm #
Computable Weighted ℓ¹ Norm (Finite) #
Computable Matrix Column Norm #
Computable matrix norm: max over columns
Equations
- finWeightedMatrixNorm_rat ν A = Finset.univ.sup' ⋯ fun (j : Fin (n + 1)) => matrixColNorm_rat ν A j
Instances For
Computable Cauchy Product (Finite) #
Computable Cauchy product at index n
Equations
- cauchyProduct_rat a b n = ∑ kl ∈ Finset.antidiagonal n, a kl.1 * b kl.2
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.
Decidability for ℚ comparisons #
Computable Max (Finset.sup') #
Expansion for finWeightedMatrixNorm_rat
Finite Sequence as Zero-Padded Infinite Sequence #
Computable Cauchy Product with Reflection #
Cauchy product at index k for zero-padded sequences
Equations
- cauchyProduct_fin_rat a b k = cauchyProduct_rat (finToSeq_rat a) (finToSeq_rat b) k
Instances For
Component-wise Cauchy product definition
Reflection: CauchyProduct on ℚ sequences casts correctly
F(ā) = ā ⋆ ā - c computation #
Computable F₀ = ā₀² - λ₀
Equations
- F_component_rat a c k = cauchyProduct_fin_rat a a k - c k
Instances For
The paramSeq c = (λ₀, 1, 0, 0, ...)
Equations
- paramSeq_rat lam0 0 = lam0
- paramSeq_rat lam0 1 = 1
- paramSeq_rat lam0 x✝ = 0
Instances For
Full Y₀ Computation #
Y₀ tail part: (1/(2|ā₀|)) * Σₙ₌ₙ₊₁²ᴺ (Σ convolution terms) * νⁿ
Equations
- Y₀_tail_rat ν a = 1 / (2 * (a 0).abs) * ∑ k ∈ Finset.Icc (n + 1) (2 * n), (∑ ij ∈ Finset.Icc (k - n) n, (finToSeq_rat a ij).abs * (finToSeq_rat a (k - ij)).abs) * ν ^ k
Instances For
Z₁ Computation (simplest) #
Z₀ Computation #
Z₂ Computation #
Full Radii Polynomial #
Reflection Lemmas: Abstract ℝ = Computable ℚ #
These lemmas bridge abstract Mathlib definitions to computable ℚ versions,
enabling native_decide verification of bounds.
Reflection for Cauchy product of finite ℚ sequences
ApproxSolution over ℚ #
A ℚ version of ApproxSolution that enables computational reflection.
Convert to real ApproxSolution
Instances For
The ℚ sequence (zero-padded)
Equations
Instances For
toSeq of toReal = cast of toSeq_rat
lpWeighted.toSeq of toL1 = cast of toSeq_rat
Matrix over ℚ #
Full Reflection Lemmas for Bounds #
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.
Instances For
DF_fin reflection
Z₁_bound on ℚ inputs = Z₁_rat
F_fin reflection: abstract F_fin equals F_fin_rat on ℚ inputs