Execute bounded rational interval reconstruction
ProvedLax109476Proofs.RamRationalReconstruction.reconstruct_spec_nativealgorithmscomputational-complexitygraph-theory
Let be rational endpoints with , each of height at most , and let be a natural denominator bound. Suppose the reconstruction stack has length covering the source’s depth bound, the host width meets the reconstruction bound and . The fixed native reconstruction command returns exactly
with the source’s full optional-result encoding and instruction bound . This equality covers every endpoint pair satisfying the stated bounds; no promised rational witness is required.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBoundsInterfaces namespace Lax109476Proofs.RamRationalReconstruction end Lax109476Proofs.RamRationalReconstruction
Formal statement
theorem Lax109476Proofs.RamRationalReconstruction.reconstruct_spec_native : ∀ (S N w D : Nat) (l u : Rat),
@LE.le Rat Rat.instLE (@OfNat.ofNat Rat (nat_lit 0) (@Rat.instOfNat (nat_lit 0))) u →
Lax109476Proofs.RationalArithmeticBounds.Height l
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S) →
Lax109476Proofs.RationalArithmeticBounds.Height u
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S) →
@LE.le Nat instLENat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) (Lax109476Proofs.RamRationalReconstruction.depthBound S)
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
N →
@LE.le Nat instLENat (Lax109476Proofs.RamRationalReconstruction.wordWidth S) w →
@LT.lt Nat instLTNat D
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w) →
Lax808846Proofs.Reasoning.Spec
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w)
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (Lax109476Proofs.RamRationalScalars.Value "recon.lo" l σ)
(And (Lax109476Proofs.RamRationalScalars.Value "recon.hi" u σ)
(And (@Eq Nat (σ.vars "recon.bound") D) (@Eq Nat (@List.length Nat (σ.arrs "cf.stack")) N))))
Lax109476Proofs.RamRationalReconstruction.reconstruct
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamReconstructionRecord.Output
(Lax109476Proofs.RationalReconstruction.reconstruct l u D) τ)
(Lax109476Proofs.RamRationalReconstruction.instructionBound S) := by sorrySource