Claim 2, p. 8 (restated with its context) — the solutions of (12) have Euclidean norm at most a rational v* of small complexity
ProvedMIQPInNP.SmallSol.claim_2This is Claim 2 of the proof of Theorem 1, restated with the objects of its context as hypotheses.
Let be a rational polytope, let be linearly independent, and let , , . Put , and , and assume
There is a single polynomial , fixed before , the number of rows of , , and the data, such that there is a rational number with and, for every satisfying (12),
where is the Euclidean norm.
The bound lets the proof of Theorem 1 fix the integer coordinates of a solution of (12) to values of small size and finish with Theorem 3.
Formalization Note The positivity hypothesis is the first sentence of the claim's proof (p. 8), which derives it from the conclusion of Lemma 7 and the definition of ; the page prints it "for all ", which fails at , so it is stated for nonzero .
Differences from the source:
- generalization: the context of pp. 7–8 (, the from Lemma 7, Case 2 and the definition of , "-small complexity") → any rational polytope, any linearly independent rational with on , bound polynomial in the sizes of the local data; reason: the source derives the positivity from its context in the first line of the proof, and its local data are -small, so the statement specializes to the source's claim.
- encoding: → Euclidean norm
euclidNorm; reason: Lean's default norm onFin n → ℝis the sup norm, and the proof uses .
import Mathlib import Definitions.Def_MIQPInNP_SmallSol_Setting
namespace MIQPInNP.SmallSol
open scoped Pointwise
/-- Claim 2, p. 8, restated with its context (Del Pia, Dey & Molinaro, arXiv:1407.4798v1). -/
theorem claim_2 :
∃ g : Polynomial ℕ, ∀ (n mP k : ℕ) (A' : Matrix (Fin mP) (Fin n) ℚ) (b' : Fin mP → ℚ)
(r : Fin k → Fin n → ℚ) (H : Matrix (Fin n) (Fin n) ℚ) (c : Fin n → ℚ) (d : ℚ),
Bornology.IsBounded (polyhedron A' b') →
LinearIndependent ℝ (fun j => toReal (r j)) →
(∀ x ∈ cone ((fun j => toReal (r j)) '' {j | quadForm H (toReal (r j)) ≠ 0}),
x ≠ 0 → 0 < quadForm H x) →
∃ v : ℚ,
bitSize v ≤ g.eval (matSize A' + vecSize b' + ∑ j, vecSize (r j) + matSize H + vecSize c
+ bitSize d) ∧
∀ x ∈ polyhedron A' b' + intCone ((fun j => toReal (r j)) '' {j | quadForm H (toReal (r j)) ≠ 0}),
quadVal H c d x ≤ 0 → euclidNorm x ≤ v := by sorry
end MIQPInNP.SmallSol
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.