The Hirsch conjecture fails in dimension : a rational counterexample
OpenHirschDim4.counterexample_dim4The Hirsch conjecture is false in dimension . There exist an integer , an integer matrix and an integer vector such that the polytope
is nonempty, bounded and full-dimensional, its rows are exactly its facets (each row irredundant), and its combinatorial diameter is strictly greater than :
Here is the vertex–edge graph of and the diameter is the largest graph distance between two vertices. This is the smallest open dimension of the Hirsch conjecture: it is known to hold for and for all -polytopes with at most facets, so any counterexample has . Integer data make a rational polytope, as the benchmark requires; a solution should exhibit explicit (and may compute the vertices).
Formalization Note. IsFacetPresentation encodes full-dimensionality (nonempty interior) plus irredundancy of every row, which for bounded makes the rows bijective with the facets. IsNonHirsch a b is ¬ Hirsch.DiamLE (Hpoly a b) (n-4), i.e. diameter ; since is forced, is genuine natural-number subtraction. The statement is equivalent to plain existence of a bounded -dimensional counterexample, because every combinatorial type of polytope admits a rational realization.
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk import Definitions.Def_SantosHirsch_Counter_Setting import Definitions.Def_HirschDim4_Setting open scoped RealInnerProductSpace
namespace HirschDim4
theorem counterexample_dim4 :
∃ (n : ℕ) (A : Matrix (Fin n) (Fin 4) ℤ) (b : Fin n → ℤ),
(Hirsch.Hpoly (intRows A) (intRhs b)).Nonempty ∧
Bornology.IsBounded (Hirsch.Hpoly (intRows A) (intRhs b)) ∧
SantosHirsch.Counter.IsFacetPresentation (intRows A) (intRhs b) ∧
SantosHirsch.Counter.IsNonHirsch (intRows A) (intRhs b) := by sorry
end HirschDim4Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.