About the problem
Let \(P\) be a polytope and let \(G(P)\) be its graph.
The Hirsch conjecture says that for any polytope \(P\) in \(\mathbb{R}^d\), the diameter of \(G(P)\) is at most \(n-d\), where \(n\) is the number of facets of \(P\). This conjecture was famously disproven by Santos in a 2012 Annals of Mathematics paper, where he presented a counterexample in dimension \(d = 43\). Shortly after, Matschke, Santos, and Weibel found a counterexample to Hirsch’s conjecture in dimension \(d = 20\). Learn more about the Hirsch conjecture from this survey.
The smallest \(d\) for which a counterexample to Hirsch’s conjecture is currently known is \(d = 19\). The 19-dimensional counterexample was posted in 2025 by DeepMind, and was found using the same idea as the paper of Matschke, Santos, and Weibel. On the other hand, the conjecture is true for \(d \leq 3\). The conjecture is open for dimensions \(d\) with \(4 \leq d \leq 18\).
This problem asks for a counterexample in dimension \(d = 4\). We ask for the lowest open dimension under the assumption that counterexamples in lower dimensions are more difficult to find, and so ideally a solution will require a new idea. The main risk with this is that the conjecture might be true for \(d = 4\).
Prompt
Let P be a bounded, full-dimensional convex polytope in R^4 with n facets. Its graph G(P) has the
vertices of P as nodes and the edges (1-dimensional faces) of P as arcs. The combinatorial diameter
of P is the largest graph distance between any two vertices of P.
Produce an explicit rational polytope P in R^4 whose combinatorial diameter is strictly greater
than n - 4, where n is its number of facets.
Submit P in BOTH representations, with every coordinate exact (no floating-point values):
* an H-representation: an integer matrix A (with n rows and 4 columns) and an integer vector b
(of length n) such that
P = { x in R^4 : A x <= b },
where the n rows of (A, b) are exactly the facets of P (each row is a facet; no row is
redundant, and no facet is omitted);
* the full V-representation: the complete list of vertices of P, each given as 4 exact rationals.
Format your answer as a single JSON object with these three keys:
{
"A": [[a_11, a_12, a_13, a_14], ..., [a_n1, a_n2, a_n3, a_n4]],
"b": [b_1, ..., b_n],
"vertices": [[v_11, v_12, v_13, v_14], ..., [v_m1, v_m2, v_m3, v_m4]]
}
The entries of A and b must be integers. Each vertex coordinate must be either an integer or a
string holding an exact rational, for example "3/2", "-7", or "0". Do not use floating-point
numbers anywhere in the submission.
Write this JSON object to a file and submit the path to that file.