Computational Stress Test of the Tropical Upper Bound Conjecture

Max-plus (tropical) geometry rebuilds ordinary geometry with "max" in place of addition and "+" in place of multiplication. Straight lines become staircases, and polytopes become rigid piecewise-linear shapes. The field has proved tropical versions of classical theorems that bound how complicated a shape can get. Its central conjecture of this kind states which tropical polyhedron has the most corners, and it has never been checked on a single computer instance. Every paper in this line is pen-and-paper mathematics with no datasets, code, or runtimes. This proposal builds that missing evidence. We will write an exact counter for the corners (extreme rays) of tropical cones. We will then run a structured adversarial search, a search that deliberately hunts for the worst-case shapes, trying to beat the conjectured maximizers. The same counter will measure whether the predicted "tropical shapes are much simpler" advantage appears at sizes one can actually compute.

In two sentences: the tropical Upper Bound Theorem makes finite, checkable predictions, namely an explicit bound, a conjectured extremal family, and linear growth in fixed dimension. We turn those predictions into an exact computational benchmark and attack them with search, so each conjecture either survives a serious attempt to break it or falls to a certified counterexample.

Core Claim

The number of extreme points of tropical polyhedra is the source of every prediction we test. It proves three things:

  • A tropical cone cut out by $p$ tropical halfspaces in dimension $d$ has at most $U(p+d, d-1)$ extreme rays. Here $U(n,k)$ is McMullen's classical maximal count for a $k$-dimensional polytope with $n$ facets.
  • The bound is asymptotically tight as $d \to \infty$ with $p$ fixed.
  • For fixed $d \ge 5$, tropical counts grow only linearly in $p$ (Remark 3).

A tropical halfspace here means a set of the form $\{x : \max_i(a_i + x_i) \ge \max_j(b_j + x_j)\}$. The paper's tools are a tropical Cramer's rule, a characterization of extreme rays (Theorem 5), and an exact correspondence between extreme rays of signed cyclic polar cones and "tropically allowed lattice paths" (Theorem 2). With these it conjectures that the polars of signed cyclic polyhedral cones achieve the maximum (Conjecture 1). It also notes that finding the maximizing sign pattern is computationally hard.

Our claim has two parts. First, Conjecture 1 and the finite-$p$ growth law can be tested exactly on integer data, because max-plus arithmetic on integers involves no rounding at all. Second, a search that moves between combinatorial types of tropical cones, seeded by the cyclic family, is the right instrument for the test. The outcome is informative either way. A certified instance exceeding the best signed cyclic count at some $(p, d)$ refutes Conjecture 1. A failed search at matched budget, across a grid of sizes, is the first empirical support the conjecture has ever had.

Research Program

Exact counting. The first artifact is an exact extreme-ray enumerator for tropical cones given by integer halfspace data. It works incrementally, intersecting one halfspace at a time. Each candidate ray is kept only if it passes the minimality test of Theorem 5. A second, independent check recomputes each kept ray through tropical Cramer's rule, so every reported count carries a certificate: an explicit list of rays, each verified extreme by both routes. For signed cyclic polar cones the enumerator is also cross-checked against the lattice-path count of Theorem 2. This gives an exact ground truth on the one family where the theory already predicts the answer.

Structured search. The second artifact is the search. The number of extreme rays depends only on the combinatorial type of the arrangement, meaning which terms attain each maximum. It does not depend on the precise real coefficients. The search therefore moves between types rather than through raw coefficient space. It starts from signed cyclic configurations across sign patterns and applies small integer perturbations that flip exactly one tie pattern. It accepts or rejects moves by the exact count, running simulated annealing and a cross-entropy sampler over sign patterns and perturbation directions. Because the sign-pattern problem is hard, we also enumerate all sign patterns exhaustively where the grid is small enough. The search then serves as the tool for larger sizes.

Timing. The third artifact is a timing and memory study. It compares the tropical enumerator with classical vertex enumeration run on classical "lifts" of the same instances. A lift is built by the deformation argument of Allamigeon et al.: each tropical coefficient $a$ becomes a classical coefficient on the order of $e^{t a}$, and the tropical cone is the limit as the scale parameter $t$ grows.

Measurement. We measure three things:

  • The ratio of the maximal count found to $U(p+d, d-1)$.
  • The ratio to the best signed cyclic count.
  • The fitted slope of count against $p$ for $d = 5, 6, 7$.

The fit tests whether Remark 3's linear regime already appears at small $p$, and at what constant.

What this is not. It is not another tropical neural-network paper. Tropical Geometry of Deep Neural Networks shows that ReLU networks are tropical rational maps. On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspective, TropNNC and Adapter Pruning using Tropical Characterization turn that observation into pruning methods. All four use zonotopes, which are Minkowski sums of segments, together with Hausdorff or $L_{1,1}$ deformation losses. None of them evaluates a max-plus analogue of a discrete-geometry theorem. Those works motivate the claim that tropical theory can be made empirical. They do not supply a method for this question, which concerns the theorems themselves.

Baselines

Uniform random instances (naive reference). This baseline draws halfspace coefficients uniformly from a bounded integer range, keeping the same range and the same number of exact-count evaluations as the search. It shows what "typical" tropical cones look like. The search must beat it by a wide margin before any claim about extremal structure means anything.

Signed cyclic polar cones (strongest existing method). This is the conjectured maximizer family of The number of extreme points of tropical polyhedra. We evaluate it at the best sign pattern, found by exhaustive enumeration where feasible and by the same search budget elsewhere. It is the strongest competitor because it is the only explicit construction in the literature with proven near-tightness. The paper reports that, for sign patterns tied to parity, the classical ray count equals $U(p+d, d-1)$ (Theorem 7). For the tropical count at specific finite $(p, d)$, no reported result was found on Lacuna. Our first deliverable is therefore that table. Beating this baseline means one thing only: a certified instance with strictly more extreme rays than every signed cyclic polar at the same $(p, d)$.

Unstructured coefficient search (ablation). This ablation isolates the key ingredient, which is searching over combinatorial types from cyclic seeds. It runs the same annealing and cross-entropy search directly on raw coefficients from random starts, at an identical evaluation budget. If it matches the structured search, the type-level design adds nothing and we will say so.

Classical vertex enumeration on lifts. This is the reference for the timing study. We run standard double-description vertex enumeration on classical lifts at increasing $t$, using exact rationals and floating point separately, on the same machine and time limits as the tropical enumerator.

Why not just…?

Why not just prove Conjecture 1 instead? Proof is the goal, but the known proof tools are thin. Tropical Carathéodory with Matroids shows that the topological arguments used classically fail in the rigid tropical setting, and that each theorem needs new combinatorial machinery. Carathéodory, Helly and the Others in the Max-Plus World needed delicate case analysis just to handle $-\infty$ coordinates. Exact small-case data is what usually guides such proofs, or cuts them short with a counterexample. That data does not exist.

Why not just sample random instances and report the maximum? Random sampling is our naive baseline, and it will likely do poorly. Extremal configurations here are highly structured: the tight cases are specific cyclic sign patterns, and Allamigeon et al. note that finding the best pattern is hard. Uniform coefficients almost surely produce generic, low-count types. The comparison against the ablation and the random baseline settles this empirically.

Why not just count on classical lifts with existing polyhedral software? This is a real alternative for small $t$, and we run it. The deformation argument, however, only recovers the tropical cone in the limit, at scales where coefficients like $e^{t a}$ overflow floating point or blow up exact-rational bit lengths. The central-path results in Short-step methods are not strongly polynomial-time likewise rely on large $t$. If classical lifts at moderate $t$ already reproduce the tropical counts cheaply, the timing study will show it, and we will report that the tropical enumerator is unnecessary for counting.

Why not just apply tropical Carathéodory to neural-network pruning? A max-plus Carathéodory bound would be the obvious bridge to TropNNC. That work reports 68.95% top-1 on ResNet18/ImageNet against 66.80% for CUP at equal parameter count, and 93.58% against 93.64% on VGG/CIFAR-10 at about 65% parameter reduction. But pruning acts on zonotopes, which are Minkowski sums, while Carathéodory-type theorems concern tropical convex hulls. A Carathéodory-selected subset has no clear guarantee on the zonotope distance that pruning actually controls. A reviewer would rightly expect K-means or magnitude selection, the latter combined with tropical pruning in Adapter Pruning using Tropical Characterization, to match it. We therefore do not pursue this route.

Proposed Experiments and Decisive Checks

Scope of the grid. The benchmark is a grid over $d = 3$ to $8$ and $p$ up to the largest value at which exact enumeration completes within a fixed per-instance time limit. The limit and machine are held constant across all methods, and reporting where enumeration breaks down is itself an output.

Validation of the counter. Before any search result is trusted, the enumerator must reproduce Theorem 2's lattice-path counts exactly on every signed cyclic instance in the grid.

The decisive check on Conjecture 1. At each $(p, d)$ we compare three numbers: the best structured-search count, the best unstructured-search count, and the best signed cyclic count, all at equal evaluation budgets. Any structured-search instance that strictly exceeds the cyclic count is released with its full ray certificate as a counterexample. The absence of such instances, across the grid and after budgets several times larger than the point where search curves plateau, is reported as quantified support.

The growth check. For $d = 5, 6, 7$ we fit maximal count against $p$ and report the slope and the smallest $p$ at which linear growth becomes visible. Tropical counts are then set against classical $U(p+d, d-1)$ counts at the same sizes. This tests whether the simplicity promised by Remark 3 exists at computable sizes or only asymptotically.

The timing check. We report wall-clock time and peak memory for tropical enumeration versus classical enumeration on lifts, as functions of $p$, $d$ and $t$. We also report the value of $t$ at which the lifted classical count first matches the tropical count, and the failure point of floating-point lifts.