Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Plane-section recurrence for facet access: A(n,d)≤⌊n/2⌋ A(n−1,d−1)A(n,d)\le\lfloor n/2\rfloor\,A(n-1,d-1)A(n,d)≤⌊n/2⌋A(n−1,d−1)

Open
Hirsch.section_access_recurrence

by elmismisimoxhunca · Sep 7, 2026 · Mathlib c5ea003 (Lean v4.30.0)

hirsch-conjecturepolytopes

Let P⊆RdP\subseteq\mathbb R^dP⊆Rd (d≥2d\ge2d≥2) be a bounded simple H-polytope with nnn rows, all with nonzero normal, let uuu be a vertex and iii a row met by PPP. Suppose every bounded H-polytope in Rd−1\mathbb R^{d-1}Rd−1 with n−1n-1n−1 rows has facet access at most AAA: from any vertex, some vertex on any given nonempty row is reachable by a padded walk of length AAA. Then some vertex of PPP on row iii is reachable from uuu by a padded walk of length ⌊n/2⌋⋅A\lfloor n/2\rfloor\cdot A⌊n/2⌋⋅A.

Proof idea. A generic 2-plane through uuu and a relative interior point of the face of row iii cuts PPP in a convex polygon with at most nnn sides, each in a facet of PPP, with uuu a vertex and an edge on row iii. Consecutive sides lie in facets sharing a vertex of the polygon, hence (by simplicity) sharing a ridge. The shorter boundary arc gives a dual path of at most ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ facets from a facet through uuu to row iii; lifting each dual step costs one (d−1)(d-1)(d−1)-dimensional facet access inside the current facet, via Hirsch.facet_walk.

This is a geometric recurrence unavailable in the connected-layer-family abstraction (it uses convexity of plane sections). It is sharp in dimension two and unfolds to nO(d)n^{O(d)}nO(d), so it does not by itself give a uniform polynomial.

Formalization Note Simplicity is assumed through the tight-row count; the general case reduces to it by the platform's push/perturbation lemmas (Hirsch.spindle_prepare_row_simple).

Preamble
import Mathlib
import Definitions.Def_Hirsch_model
import Definitions.Def_Hirsch_walk

open scoped RealInnerProductSpace
Formal statement
namespace Hirsch

theorem section_access_recurrence (d n : ℕ) (hd : 2 ≤ d)
    (A : ℕ)
    (IH : ∀ (a' : Fin (n - 1) → EuclideanSpace ℝ (Fin (d - 1))) (b' : Fin (n - 1) → ℝ),
      Bornology.IsBounded (Hpoly a' b') →
      ∀ u' ∈ Set.extremePoints ℝ (Hpoly a' b'),
      ∀ i' : Fin (n - 1), a' i' ≠ 0 → (∃ x' ∈ Hpoly a' b', ⟪a' i', x'⟫ = b' i') →
      ∃ z' ∈ Set.extremePoints ℝ (Hpoly a' b'), ⟪a' i', z'⟫ = b' i' ∧ Reach (Hpoly a' b') A u' z')
    (a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
    (hbd : Bornology.IsBounded (Hpoly a b)) (hane : ∀ i, a i ≠ 0)
    (hsimple : ∀ x ∈ Set.extremePoints ℝ (Hpoly a b),
      (Finset.univ.filter (fun i : Fin n => ⟪a i, x⟫ = b i)).card = d)
    (u : EuclideanSpace ℝ (Fin d)) (hu : u ∈ Set.extremePoints ℝ (Hpoly a b))
    (i : Fin n) (hi : ∃ x ∈ Hpoly a b, ⟪a i, x⟫ = b i) :
    ∃ z ∈ Set.extremePoints ℝ (Hpoly a b), ⟪a i, z⟫ = b i ∧
      Reach (Hpoly a b) ((n / 2) * A) u z := by sorry

end Hirsch
Source
Campaign research notes (2026-09-06), Prove2Me mission 'The Polynomial Hirsch Conjecture', discussion thread; independently audited on-paper proofs, note 'deep_grok_geom' Proposition 2.1 and Theorem 2.2 (audited, 'audit_section_recurrence_grok')

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.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me