Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 (Yannakakis) — rank+(S)≤r\mathrm{rank}_+(S)\le rrank+​(S)≤r iff an extension with ≤r\le r≤r facets iff an EF with ≤r\le r≤r inequalities

Proved
ExtensionComplexity.TSP.yannakakis_factorization

by mikedeng1 · 1 vote · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

extension-complexityfactorization-theoremnonnegative-rankp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1yannakakis

Let P={x∈Rι:Ax≤b}=conv(V)P=\{x\in\mathbb R^{\iota} : Ax\le b\}=\mathrm{conv}(V)P={x∈Rι:Ax≤b}=conv(V) be a polytope with A∈Rm×ιA\in\mathbb R^{m\times\iota}A∈Rm×ι, b∈Rmb\in\mathbb R^mb∈Rm and V={v1,…,vN}V=\{v_1,\dots,v_N\}V={v1​,…,vN​}, of dimension dim⁡(P)≥1\dim(P)\ge 1dim(P)≥1, and let SSS be the slack matrix of PPP with respect to Ax≤bAx\le bAx≤b and VVV. Theorem 3 (Yannakakis 1991): for every positive integer rrr the following are equivalent:

  1. rank+(S)≤r\mathrm{rank}_+(S)\le rrank+​(S)≤r;
  2. PPP has an extension of size at most rrr, i.e. a polytope Q⊆ReQ\subseteq\mathbb R^{e}Q⊆Re with at most rrr facets and a linear map π\piπ with π(Q)=P\pi(Q)=Pπ(Q)=P;
  3. PPP has an EF of size at most rrr, i.e. with at most rrr inequalities.

In short, xc(P)=rank+(S)\mathrm{xc}(P)=\mathrm{rank}_+(S)xc(P)=rank+​(S): lower bounds on extension complexity are lower bounds on the nonnegative rank of any slack matrix, and conversely.

Formalization Note Rd\mathbb R^dRd is Rι\mathbb R^{\iota}Rι for a finite index type ι\iotaι. dim⁡(P)≥1\dim(P)\ge 1dim(P)≥1 is stated as "PPP contains two distinct points", which is equivalent for a nonempty convex set. The slack matrix is taken with respect to the given A,b,VA,b,VA,b,V (not only facets and vertices). Condition 2 lets the ambient dimension eee of QQQ be any natural number; condition 3 is "an EF of some size r′≤rr'\le rr′≤r".

Preamble
import Mathlib
import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity
import Definitions.Def_ExtensionComplexity_TSP_Polytope
import Definitions.Def_ExtensionComplexity_TSP_SlackMatrix

open Matrix
Formal statement
namespace ExtensionComplexity.TSP

/-- **Theorem 3** [Yannakakis 1991] (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:10): let
`P = {x | Ax ≤ b} = conv(V)` be a polytope with `dim(P) ≥ 1`, and let `S` be the slack matrix of
`P` with respect to `Ax ≤ b` and `V`. For every positive integer `r` the following are equivalent:
(i) `rank₊(S) ≤ r`; (ii) `P` has an extension with at most `r` facets; (iii) `P` has an EF with at
most `r` inequalities. `dim(P) ≥ 1` is stated as: `P` contains two distinct points. -/
theorem yannakakis_factorization {ι : Type*} [Fintype ι] {m N : ℕ}
    (A : Matrix (Fin m) ι ℝ) (b : Fin m → ℝ) (V : Fin N → ι → ℝ) (P : Set (ι → ℝ))
    (hPA : P = {x | A *ᵥ x ≤ b}) (hPV : P = convexHull ℝ (Set.range V))
    (hdim : ∃ x ∈ P, ∃ y ∈ P, x ≠ y) (r : ℕ) (hr : 1 ≤ r) :
    List.TFAE
      [nonnegRank (slackMatrix A b V) ≤ r,
       ∃ (e : ℕ) (Q : Set (Fin e → ℝ)), IsExtension Q P ∧ HasAtMostFacets Q r,
       ∃ r' ≤ r, IsEFOfSize P r'] := by sorry

end ExtensionComplexity.TSP
Source
Fiorini, Massar, Pokutta, Tiwary, de Wolf, Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62(2) (2015), Art. 17, p. 17:10, Theorem 3
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 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