Log-concavity and Approximate Counting for Totally Unimodular Polytopes

Abstract

We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity''). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.

Berry--Esseen Bounds for Faces in Unimodular Triangulations of Random Polytopes
Zhonggen Su, Huilian Zheng
arXiv20 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
Unimodular defect and antipodal lattice points of smooth reflexive polytopes
Binnan Tu
arXiv19 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Counting symmetric unimodular triangulations
Kamillo Ferry, Michael Joswig, Jörg Rambau
arXiv15 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
Zhidan Li, Kuan Yang
arXiv26 Sep 2026PreprintCC BY 4.0Full textProbabilityarXiv
Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion
Qiang Wu
arXiv27 Oct 2026PreprintCC BY 4.0Full textProbability Condensed matterarXiv

Cite

BibTeX RIS

BibTeX

@misc{leake2026logconcavity,
  title = {{Log-concavity and Approximate Counting for Totally Unimodular Polytopes}},
  author = {Jonathan Leake and Maryam Mohammadi Yekta},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.39917},
  eprint = {2609.39917},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.39917},
}

RIS

TY  - UNPB
TI  - Log-concavity and Approximate Counting for Totally Unimodular Polytopes
AU  - Jonathan Leake
AU  - Maryam Mohammadi Yekta
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.39917
UR  - https://arxiv.org/abs/2609.39917
AB  - We present a new lower bound on the number of lattice points of all totally unimodular polytopes, generalizing previous lower bounds on contingency tables, integer flows, and beyond. Our bound is based on the Gurvits capacity convex optimization problem, and thus our result implies an efficient deterministic algorithm for approximate counting of the lattice points up to an explicit exponential factor. We achieve our bounds by showing that the associated generating polynomials fit into a new general class of log-concave polynomials called VLC ("variable-wise log-concavity''). This also implies a conjecture of Ferroni and Higashitani on the evaluations of the Ehrhart polynomials of unimodular polytopes. The essential ingredient for these results is the resolution of Barvinok's log-concavity conjecture for contingency tables on lines, which was proven using ChatGPT 6 Astra. We conjecture a generalization of Barvinok's conjecture, which we believe will lead to stronger and more general bounds.
ER  -

Abstract

Related

Cite