One-step strong -step construction for spindles
ProvedHirsch.spindle_one_stepThis is the inductive step of Santos' strong -step theorem for spindles (the polar form of the prismatoid construction in Section 2.2).
Let be a nonempty bounded H-polytope described by inequalities, with and . Suppose are extreme points of such that every describing inequality is tight at exactly one of or (a spindle with apices ), and there is no padded vertex-edge walk of length from to .
Then there exist a nonempty bounded H-polytope described by inequalities, together with extreme points of , such that is again a spindle with apices , and there is no padded vertex-edge walk of length from to .
Iterating this step times produces a spindle of dimension with facets and length greater than , which is the content of the strong -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.
import Mathlib import Definitions.Def_Hirsch_model open scoped RealInnerProductSpace
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