Execution of bounded rational feasible-point recovery
ProvedLax109476Proofs.RamRecoverFeasibleSystem.recover_specLet be an integer program with constraints and variables whose rational constraint system has a feasible point. Let , assume the entries of have absolute value at most , and let the word width meet the published recovery-width bound. Let the allocated reconstruction stack length be at least the reconstruction-depth bound for the recovery precision, plus one.
From the encoded recovery input, the command produces a vector and a complete persistent recovery state such that
Here is the published integer-certificate coordinate bound, and height bounds numerator magnitude and positive denominator. The execution uses at most the explicit recovery instruction bound for . All allocated array and stack conditions are retained in the input predicate. This result recovers an actual bounded rational witness rather than only a feasibility decision.
import Definitions.Def_EdgeSublinearMWIS_Main_NativeCertificateInterfaces
theorem Lax109476Proofs.RamRecoverFeasibleSystem.recover_spec : ∀ (m n S N w : ℕ) (P : Lax109476.LinearProgram.Program ℤ m n),
m + n ≤ S →
Lax109476Proofs.RamRecoverFeasibleSystem.wordWidth m n S ≤ w →
Lax109476Proofs.RamRationalReconstruction.depthBound (Lax109476Proofs.RamRecoverFeasibleSystem.recoveryBits S) +
1 ≤
N →
(∀ (i : Fin m) (j : Fin n), (P.A i j).natAbs ≤ 2 ^ (2 * S)) →
(∀ (i : Fin m), (P.b i).natAbs ≤ 2 ^ (2 * S)) →
(∃ (x : Fin n → ℚ),
Lax109476.LinearProgram.PrimalFeasible (Lax109476Proofs.IntegerEncoding.rationalProgram P) x) →
Lax808846Proofs.Reasoning.Spec (2 ^ w) (Lax109476Proofs.RamRecoverFeasibleSystem.Input P S N)
Lax109476Proofs.RamRecoverFeasibleSystem.recover
(fun (x τ : Lax808846Proofs.Imp.Env) =>
∃ (z : Fin (n + m) → ℚ),
Lax109476Proofs.RamRecoveryThreshold.Persistent
(Lax109476Proofs.RamStandardPointRecovery.program
(Lax109476Proofs.IntegerPointRecovery.slackMatrix P) P.b)
z (n + m) τ ∧
(Lax109476.LinearProgram.PrimalFeasible (Lax109476Proofs.IntegerEncoding.rationalProgram P)
fun (j : Fin n) => z (Fin.castAdd m j)) ∧
∀ (j : Fin (n + m)),
Lax109476Proofs.RationalArithmeticBounds.Height (z j)
(Lax109476Proofs.IntegerCertificates.coordinateCap m n (2 ^ (2 * S))))
(Lax109476Proofs.RamRecoverFeasibleSystem.instructionBound m n S) := by sorry