Larman's layer recursion: summing the layer steps along a facet decomposition
ProvedHirsch.larman_layer_recursionLet be a bounded H-polytope with all normals nonzero, in which every vertex has at least one tight inequality. Let and . Assume:
- (layer step) for every base vertex , row , set of rows , and vertices on the facet with tight rows in such that every vertex of carrying a row outside is strictly closer to than , one has (this is
Hirsch.larman_layer_step); - (arithmetic) for every and every family with ,
Then : the combinatorial diameter of is at most .
This is Larman's argument as presented by Kim--Santos. From a base vertex , stratify the vertices by distance into layers with , , where is the largest distance of a vertex sharing a facet with some vertex at distance . Let be the rows tight at some vertex of and . Because a facet active in two layers is active in all layers between (Hirsch.tight_row_interval) and the choice of is maximal, no row is active in three layers, so . The layer step applied to , , a vertex at distance and a vertex at distance gives , and summing over yields .
Formalization Note The hypothesis that every vertex has a tight row holds automatically when (the tight normals span, Hirsch.vertex_tight_rows_span), and is stated explicitly to keep the recursion dimension-free. The layer-step hypothesis is quantified over all base vertices and all finsets of rows.
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk open scoped RealInnerProductSpace
namespace Hirsch
theorem larman_layer_recursion (d n : ℕ)
(a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
(hane : ∀ j, a j ≠ 0) (hbd : Bornology.IsBounded (Hpoly a b))
(htight : ∀ v ∈ Set.extremePoints ℝ (Hpoly a b), ∃ j, ⟪a j, v⟫ = b j)
(β : ℕ → ℕ) (Bd : ℕ)
(hstep : ∀ u ∈ Set.extremePoints ℝ (Hpoly a b), ∀ (r : Fin n) (T : Finset (Fin n)), r ∈ T →
∀ y ∈ Set.extremePoints ℝ (Hpoly a b), ∀ z ∈ Set.extremePoints ℝ (Hpoly a b),
⟪a r, y⟫ = b r → ⟪a r, z⟫ = b r →
(∀ j, ⟪a j, y⟫ = b j → j ∈ T) → (∀ j, ⟪a j, z⟫ = b j → j ∈ T) →
(∀ w ∈ Set.extremePoints ℝ (Hpoly a b), ⟪a r, w⟫ = b r →
(∃ j, j ∉ T ∧ ⟪a j, w⟫ = b j) → gdist (Hpoly a b) u w + 1 ≤ gdist (Hpoly a b) u y) →
gdist (Hpoly a b) u z ≤ gdist (Hpoly a b) u y + β T.card)
(harith : ∀ (k : ℕ) (m : Fin k → ℕ), (∀ i, 1 ≤ m i) →
∑ i, m i ≤ 2 * n → ∑ i, β (m i) + k ≤ Bd + 1) :
DiamLE (Hpoly a b) Bd := by sorry
end Hirsch