Multivariate volume, Ehrhart, and h⁎-polynomials of polytropes

Marie-Charlotte Brandenburg, Sophia Elia, Leon ZhangJournal of Symbolic Computation 2022 · DOI · arXiv

Abstract

This research explores the intersection of tropical geometry and classical discrete geometry, focusing on polytropes. By transitioning from standard univariate polynomials to multivariate ones, the authors uncover combinatorial structures linking the volume of these shapes to their underlying subdivisions. The study provides a systematic algebraic framework to compute multivariate volume, Ehrhart, and $h^*$-polynomials for polytropes up to dimension 4, revealing that polynomial coefficients serve as a combinatorial map of regular central subdivisions of fundamental root polytopes.

Introduction: The Geometry of Polytropes

Computing the volume of a polytope is a #P-hard problem. While lattice polytopes—shapes with vertices on a grid—are well-studied via the Ehrhart polynomial, polytropes present unique challenges. Polytropes are defined by being both classically convex and tropically convex.

A weighted directed graph (left) and its corresponding 2D polytrope (right) defined by inequalities derived from edge weights.

Standard analysis uses a univariate Ehrhart polynomial $L_P(t)$ to count lattice points in a scaled polytope. However, this single variable collapses significant geometric detail. This paper addresses the challenge of computing multivariate versions of these polynomials, where each facet is assigned its own variable, to reveal hidden structural patterns.

Methodology

The authors combine several advanced techniques to build their computational pipeline:

  1. Toric Geometry: Polytrope volume is represented as an integral of a cohomology class on a toric variety, utilizing the Stanley-Reisner ideal to define the cohomology ring.
  2. Algebraic Algorithms: They implement a Gröbner basis-driven algorithm to compute these integrals systematically.
  3. The Todd Operator: To transition from continuous volume to discrete lattice point counts, they apply a multivariate Todd operator involving Bernoulli numbers.
  4. Change of Basis: Eulerian polynomials are used to transform Ehrhart results into $h^*$-polynomials, which possess desirable combinatorial properties like non-negativity and symmetry.

Key Insights and Results

The study relies on the classification of "maximal tropical types" of polytropes. While dimension 2 has only 1 type (the hexagon) and dimension 3 has 6, dimension 4 contains 27,248 distinct types.

The 3D Combinatorial Map

For 3D polytropes, the authors established that volume polynomial coefficients have direct combinatorial meanings. Theorem 1.2 provides a complete description of these coefficients in terms of subdivisions of the fundamental root polytope $FP_3$.

The structure of a root polytope, which serves as the basis for the combinatorial mapping of volume polynomial coefficients.

Hidden Structure in 4D

In 4D, the 27,248 volume polynomials exist within a massive 8,855-dimensional space. Surprisingly, the authors discovered (Theorem 1.4) that all these polynomials lie on a tiny 70-dimensional affine subspace. This suggests the geometry of polytropes is far more constrained than previously assumed.

Conclusion and Future Work

The multivariate algebraic approach proved significantly more efficient than general-purpose tools like Normaliz, reducing computation times from 12 hours to 5 minutes for certain 4D cases. Future work aims to scale this approach to dimension 5 and beyond, bridge the "gap" in the 4D combinatorial relationship, and formally prove the unimodality conjecture for $h^*$-vectors.

Code and datasets are available on GitHub.

Summary updated

BibTeX
@article{brandenburg2022multivariate,
  author = {Marie-Charlotte Brandenburg and Sophia Elia and Leon Zhang},
  title = {{Multivariate volume, Ehrhart, and h⁎-polynomials of polytropes}},
  journal = {Journal of Symbolic Computation},
  year = {2022},
  doi = {10.1016/j.jsc.2022.04.011},
}
Figure