Proof of Lemma 12, p. 14 — case λ* ≤ 2ε‴: OPT ≥ α − 6R(r+1)ε‴ = α − ε (added |α| ≤ R; (6) row 2 corrected)
ProvedQZeroSum19.LPReduce.lemma_12_smalllinear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let the LP pair (4)/(5) with data , , satisfy the standing assumptions of §4 with constants , and optimal value , let with , let and , and let be the value of the game (6) (second row ). Then
This is the second case of the proof of Lemma 12: a small game value certifies that the LP reaches the objective level up to the additive error .
Formalization Note The hypothesis is not written in the lemma; the proof's step (7) needs it (see the item for (7)–(8)), and the context of §4 supplies it ( for the binary search; entries of (6) in ).
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem lemma_12_small {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(R r OPT α ε : ℝ) (hLP : LPStanding A b c R r OPT) (hα : |α| ≤ R) (hε : 0 < ε) :
QZeroSum19.GK.gameValue (gameMatrix A b c α R) ≤ 2 * epsGame ε R r → α - ε ≤ OPT := by sorry
end QZeroSum19.LPReduce
Source
van Apeldoorn and Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180v1, p. 14, proof of Lemma 12, second case ("OPT ≥ α − 6R(r + 1)ε‴ = α − ε")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.