Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Claim 2, p. 8 (restated with its context) — the solutions of (12) have Euclidean norm at most a rational v* of small complexity

Proved
MIQPInNP.SmallSol.claim_2

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexitymixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polyhedraquadratic-programming

This is Claim 2 of the proof of Theorem 1, restated with the objects of its context as hypotheses.

Let P={x:A′x≤b′}⊆RnP = \{x : A'x\le b'\}\subseteq\mathbb R^nP={x:A′x≤b′}⊆Rn be a rational polytope, let r1,…,rk∈Qnr^1,\dots,r^k\in\mathbb Q^nr1,…,rk∈Qn be linearly independent, and let H∈Qn×nH\in\mathbb Q^{n\times n}H∈Qn×n, c∈Qnc\in\mathbb Q^nc∈Qn, d∈Qd\in\mathbb Qd∈Q. Put J={j:(rj)⊤Hrj=0}J = \{j : (r^j)^\top Hr^j = 0\}J={j:(rj)⊤Hrj=0}, FJ=cone⁡(rj)j∉JF_J = \operatorname{cone}(r^j)_{j\notin J}FJ​=cone(rj)j∈/J​ and FJI=int.cone⁡(rj)j∉JF^I_J = \operatorname{int.cone}(r^j)_{j\notin J}FJI​=int.cone(rj)j∈/J​, and assume

r⊤Hr>0for every nonzero r∈FJ.r^\top Hr>0\quad\text{for every nonzero } r\in F_J .r⊤Hr>0for every nonzero r∈FJ​.

There is a single polynomial ggg, fixed before nnn, the number of rows of A′A'A′, kkk, and the data, such that there is a rational number v∗v^*v∗ with size⁡(v∗)≤g(size⁡(A′)+size⁡(b′)+∑jsize⁡(rj)+size⁡(H)+size⁡(c)+size⁡(d))\operatorname{size}(v^*)\le g\big(\operatorname{size}(A')+\operatorname{size}(b')+\sum_j\operatorname{size}(r^j)+\operatorname{size}(H)+\operatorname{size}(c)+\operatorname{size}(d)\big)size(v∗)≤g(size(A′)+size(b′)+∑j​size(rj)+size(H)+size(c)+size(d)) and, for every xxx satisfying (12),

x⊤Hx+c⊤x+d≤0,x∈P+FJI⟹∥x∥≤v∗,x^\top Hx + c^\top x + d\le 0,\quad x\in P+F^I_J\qquad\Longrightarrow\qquad \|x\|\le v^* ,x⊤Hx+c⊤x+d≤0,x∈P+FJI​⟹∥x∥≤v∗,

where ∥⋅∥\|\cdot\|∥⋅∥ 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 JJJ; the page prints it "for all r∈FJr\in F_Jr∈FJ​", which fails at r=0r=0r=0, so it is stated for nonzero rrr.

Differences from the source:

  • generalization: the context of pp. 7–8 (P=PiˉP=P_{\bar i}P=Piˉ​, the rjr^jrj from Lemma 7, Case 2 and the definition of JJJ, "F\mathcal FF-small complexity") → any rational polytope, any linearly independent rational rjr^jrj with r⊤Hr>0r^\top Hr>0r⊤Hr>0 on FJ∖{0}F_J\setminus\{0\}FJ​∖{0}, 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 F\mathcal FF-small, so the statement specializes to the source's claim.
  • encoding: ∥x∥\|x\|∥x∥ → Euclidean norm euclidNorm; reason: Lean's default norm on Fin n → ℝ is the sup norm, and the proof uses ∥pˉ∥≤n⋅v4∗\|\bar p\|\le\sqrt n\cdot v_4^*∥pˉ​∥≤n​⋅v4∗​.
Preamble
import Mathlib
import Definitions.Def_MIQPInNP_SmallSol_Setting
Formal statement
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
Source
Del Pia, Dey & Molinaro, Mixed-integer quadratic programming is in NP, arXiv:1407.4798v1, p. 8, Claim 2 and Equation (12) (context pp. 7–8)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me