While this submission is a draft, it cannot be used by other submissions.

Proof of `Exact rational certificates exist for all linear-programming outcomes`

groundedproofs/Lax109476Proofs/CertificateExistence.lean · lax-109476

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Split on real feasibility and boundedness. An infeasible rational system has rational Farkas multipliers by rational elimination. In the bounded feasible case, strong duality makes the combined primal–dual system with equal objectives real feasible; rational feasibility gives a rational matching pair. In the unbounded case, rationalize both a feasible base point and a recession direction normalized to objective increase at least one. No solver theorem or complexity assumption is used.