Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

One-step strong ddd-step construction for spindles

Proved
Hirsch.spindle_one_step

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

combinatorial-optimizationlinear-programmingpolytope-theory

This is the inductive step of Santos' strong ddd-step theorem for spindles (the polar form of the prismatoid construction in Section 2.2).

Let P⊆RdP\subseteq\mathbb R^dP⊆Rd be a nonempty bounded H-polytope described by nnn inequalities, with 0<d0<d0<d and n>2dn>2dn>2d. Suppose u,vu,vu,v are extreme points of PPP such that every describing inequality is tight at exactly one of uuu or vvv (a spindle with apices u,vu,vu,v), and there is no padded vertex-edge walk of length ddd from uuu to vvv.

Then there exist a nonempty bounded H-polytope P′⊆Rd+1P'\subseteq\mathbb R^{d+1}P′⊆Rd+1 described by n+1n+1n+1 inequalities, together with extreme points u′,v′u',v'u′,v′ of P′P'P′, such that P′P'P′ is again a spindle with apices u′,v′u',v'u′,v′, and there is no padded vertex-edge walk of length d+1d+1d+1 from u′u'u′ to v′v'v′.

Iterating this step n−2dn-2dn−2d times produces a spindle of dimension n−dn-dn−d with 2n−2d2n-2d2n−2d facets and length greater than n−dn-dn−d, which is the content of the strong ddd-step theorem.

Formalization Note. Length is encoded by the non-existence of a padded walk of length equal to the ambient dimension, matching Hirsch.strong_dstep_spindle. The construction is the polar of the one-point-suspension-plus-perturbation of a prismatoid in Santos, Theorem 2.6.

Preamble
import Mathlib
import Definitions.Def_Hirsch_model

open scoped RealInnerProductSpace
Formal statement
namespace Hirsch

theorem spindle_one_step (d n : ℕ) (hd : 0 < d) (hn : 2 * d < n)
    (a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
    (u v : EuclideanSpace ℝ (Fin d))
    (hne : (Hpoly a b).Nonempty) (hbd : Bornology.IsBounded (Hpoly a b))
    (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)
    (hlong : ∀ w : ℕ → EuclideanSpace ℝ (Fin d),
      ¬ (w 0 = u ∧ w d = v ∧
          ∀ j < d, w j = w (j + 1) ∨ Adj (Hpoly a b) (w j) (w (j + 1)))) :
    ∃ (a' : Fin (n + 1) → EuclideanSpace ℝ (Fin (d + 1)))
      (b' : Fin (n + 1) → ℝ)
      (u' v' : EuclideanSpace ℝ (Fin (d + 1))),
      (Hpoly a' b').Nonempty ∧
      Bornology.IsBounded (Hpoly a' b') ∧
      u' ∈ Set.extremePoints ℝ (Hpoly a' b') ∧
      v' ∈ Set.extremePoints ℝ (Hpoly a' b') ∧
      (∀ i, (⟪a' i, u'⟫ = b' i) ↔ ⟪a' i, v'⟫ ≠ b' i) ∧
      ∀ w : ℕ → EuclideanSpace ℝ (Fin (d + 1)),
        ¬ (w 0 = u' ∧ w (d + 1) = v' ∧
            ∀ j < d + 1, w j = w (j + 1) ∨
              Adj (Hpoly a' b') (w j) (w (j + 1))) := 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, Theorem 1.5 and Theorem 2.6 (inductive step, Section 2.2), polar/prismatoid form.

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