Prepare a stored integer system for exact ellipsoid feasibility
ProvedLax109476Proofs.RamFeasibilitySetup.setup_spec_nativealgorithmscomputational-complexitygraph-theory
Let be an integer system with , and suppose every matrix and right-hand-side coefficient has magnitude at most . At every host width meeting the explicit feasibility-setup bound, the fixed command constructs the normalized integer matrix, rational right-hand side and search budget:
From its full stored input predicate, it returns the complete initialized search-input predicate within instructions. The coordinate cap, normalization scale, precision denominator and budget are computed by the command.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBoundsInterfaces namespace Lax109476Proofs.RamFeasibilitySetup end Lax109476Proofs.RamFeasibilitySetup
Formal statement
theorem Lax109476Proofs.RamFeasibilitySetup.setup_spec_native : ∀ (m n S w : Nat) (P : Lax109476.LinearProgram.Program Int m n),
@LE.le Nat instLENat (@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m n) S →
(∀ (i : Fin m) (j : Fin n),
@LE.le Nat instLENat (@Lax109476.LinearProgram.Program.A Int m n P i j).natAbs
(@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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) (@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
S))) →
(∀ (i : Fin m),
@LE.le Nat instLENat (@Lax109476.LinearProgram.Program.b Int m n P i).natAbs
(@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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S))) →
@LE.le Nat instLENat (Lax109476Proofs.RamFeasibilitySetup.wordWidth S) 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)
(@Lax109476Proofs.RamFeasibilitySetup.Input m n P S) Lax109476Proofs.RamFeasibilitySetup.setup
(fun (x τ : Lax808846Proofs.Imp.Env) =>
@Lax109476Proofs.RamSearchBounds.Input (@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) m n) n
(@Lax109476Proofs.NormalizedFeasibility.normalizedMatrix m n P
(Lax109476Proofs.NormalizedFeasibility.outerScale n
(Lax109476Proofs.IntegerCertificates.coordinateCap m n
(@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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S)))))
(@Lax109476Proofs.NormalizedFeasibility.normalizedBound m n P
(@HDiv.hDiv Rat Rat Rat (@instHDiv Rat Rat.instDiv)
(@OfNat.ofNat Rat (nat_lit 1) (@Rat.instOfNat (nat_lit 1)))
(@Nat.cast Rat Rat.instNatCast
(Lax109476Proofs.NormalizedFeasibility.precisionDenominator m n
(@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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S))))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(Lax109476Proofs.EllipsoidSequence.thresholdSteps n
(Lax109476Proofs.NormalizedFeasibility.ballExponent m n
(@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)))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) S))))
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
τ)
(Lax109476Proofs.RamFeasibilitySetup.instructionBound S) := by sorrySource