Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

A ddd-spindle has at least 2d2d2d inequalities

Proved
Hirsch.spindle_n_ge_two_d

by jjosh · Sep 5, 2026 · Mathlib c5ea003 (Lean v4.30.0)

combinatorial-optimizationpolytope-theory

A spindle in dimension ddd cannot be described by fewer than 2d2d2d inequalities.

Let P⊆RdP\subseteq\mathbb R^dP⊆Rd be an H-polytope cut out by nnn inequalities, and let u,vu,vu,v be extreme points of PPP such that every describing inequality is tight at exactly one of uuu or vvv. If d>0d>0d>0, then

n≥2d.n\ge 2d.n≥2d.

The two tight sets are disjoint by the spindle (XOR) hypothesis. Each extreme point of a ddd-dimensional polytope is the unique solution of at least ddd linearly independent tight inequalities (otherwise a line through the point would remain in PPP), so each tight set has cardinality at least ddd.

This is the observation that the asimpliciality s=n−2ds=n-2ds=n−2d of a spindle is nonnegative, used as the induction parameter in Santos' strong ddd-step theorem.

Formalization Note. The H-polytope may include redundant inequalities; the bound counts all describing inequalities, so it remains valid in the presence of redundancy.

Preamble
import Mathlib
import Definitions.Def_Hirsch_model

open scoped RealInnerProductSpace
Formal statement
namespace Hirsch

theorem spindle_n_ge_two_d (d n : ℕ) (hd : 0 < d)
    (a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
    (u v : EuclideanSpace ℝ (Fin d))
    (hu : u ∈ Set.extremePoints ℝ (Hpoly a b))
    (hv : v ∈ Set.extremePoints ℝ (Hpoly a b))
    (hspindle : ∀ i, (⟪a i, u⟫ = b i) ↔ ⟪a i, v⟫ ≠ b i) :
    2 * d ≤ n := by sorry

end Hirsch
Source
F. Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics 176 (2012) 383-412, https://arxiv.org/abs/1006.2814, Definition 1.4 and the induction on s=n−2ds=n-2ds=n−2d in Theorem 2.6 (base s=0s=0s=0 requires n≥2dn\ge 2dn≥2d).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me