PaperlayerView exact revision on arXiv

Source-linked AI summary

Log-concavity and Approximate Counting for Totally Unimodular Polytopes

Jonathan Leake, Maryam Mohammadi Yekta

arXiv:2609.39917v1math.COcs.DM

TL;DR

Estimating lattice-point counts in TU polytopes and understanding how they vary with the right-hand side are central questions, with no fully polynomial approximation scheme known for arbitrary TU polytopes. The paper proves log-concavity properties of their generating functions and uses Gurvits capacity methods to obtain lower bounds and a deterministic approximation algorithm. It also proves a line-log-concavity result and an Ehrhart log-concavity conjecture for unimodular polytopes.

  • Problem

    The paper asks how to estimate lattice-point counts of TU polytopes and how those counts vary with the right-hand side; no fully polynomial randomized or deterministic approximation scheme is known for arbitrary TU polytopes.

    Source: §1 · p. 1

  • Method

    The paper proves that truncations of the associated generating functions are VLC, enabling the Gurvits capacity method to be applied to these functions.

    Source: §1 · p. 2

  • Results

    The paper proves lower bounds for TU-polytope lattice-point counts, a deterministic polynomial-time algorithm to approximate the bound, and log-concavity of counts along rational lines.

    Source: §1 · p. 2, §1.1 · p. 3

  • Takeaways & Limitations

    The line-log-concavity result also implies the conjectured log-concavity of Ehrhart evaluations for unimodular polytopes.

    Source: §1 · p. 2

    The results do not extend to arbitrary IDP polytopes: Theorem 3.5 fails for general IDP polytopes.

    Source: §3.1 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

The paper studies how to estimate lattice-point counts in totally unimodular polytopes and how those counts vary with the right-hand side. It uses log-concavity of associated generating functions to derive bounds, an approximation algorithm, and results on Ehrhart evaluations.

1 Introduction

  • VLC means that after coefficient extractions and positive evaluations in all but one variable, the remaining polynomial has log-concave coefficients.The paper uses this property for truncations of the generating functions PM; it generalizes several studied log-concavity notions.Source: §1 · p. 2
  • For TU polytopes, lattice-point counts along any rational line in the right-hand side form a log-concave sequence, resolving the line version of Barvinok’s question for this setting.The full-strength version of Barvinok’s question for TU polytopes remains open.Source: §1 · p. 2

1.1 Our Results

  • Theorem 1.1 gives a lower bound for lattice-point counts in TU polytopes, and Theorem 1.3 provides a deterministic algorithm to approximate the bound in polynomial time.The algorithm computes an estimate of log E within additive error ε.Source: §1.1 · p. 3
  • The paper proves log-concavity of Ehrhart evaluations for unimodular polytopes, implying the conjecture of Ferroni and Higashitani.The inequality is EP(k)^2 ≥ EP(k−1)·EP(k+1) for k ≥ 1.Source: §1.1 · pp. 3–4

1.2 An Open Question

  • A generalization of Barvinok’s question asks whether lattice-point counts satisfy an inequality for a probability distribution on the integer right-hand sides with mean b; this remains open.The analogous statement for distributions over R^m follows from the line result, but convexity on lines does not generally imply global convexity over Z^m.Source: §1.2 · p. 4

1.3 Previous and Related Work

  • Existing approximation schemes cover important special classes, but no fully polynomial randomized or deterministic approximation scheme is known for arbitrary TU polytopes.The paper therefore seeks weaker approximation guarantees that apply uniformly to bounded TU polytopes.Source: §1.3 · p. 5

1.4 AI Declaration

  • The authors report using ChatGPT 6 Astra before the first draft on the line-log-concavity result and its generalization, and later for error checking and proof and presentation suggestions.They state that they verified and take responsibility for the paper’s contents.Source: §1.4 · p. 6

2 VLC Laurent polynomials

The paper introduces VLC Laurent polynomials as a weaker log-concavity class that still supports capacity lower bounds, addressing conditions that are too strong for totally unimodular polytopes. The section defines VLC and develops its properties and scope.

2 VLC Laurent polynomials

  • VLC weakens existing log-concavity requirements that are too strong for TU polynomials while retaining applicability of capacity lower bounds.The class is introduced as a tool for the paper’s capacity bounds.Source: §2 · p. 6

2.1 Definition and capacity bounds

  • Capacity lower bounds for coefficients of denormalized Lorentzian polynomials extend naturally to the broader VLC class.The construction uses variable-wise log-concavity conditions to extend those bounds.Source: §2.1 · p. 7
  • A nonnegative Laurent polynomial is VLC when positive evaluations in all but one variable yield log-concave coefficients, and coefficient extraction in any variable leaves a VLC polynomial.The definition applies recursively across variables.Source: §2.1 · p. 7

2.2 Examples and properties

  • Every denormalized Lorentzian polynomial and its shifts are VLC, but VLC also contains Laurent polynomials not necessarily denormalized Lorentzian.The section presents VLC as a substantially larger class.Source: §2.2 · p. 8
  • The support of a VLC Laurent polynomial is a finite saturated set, meaning it contains every lattice point in its convex hull.Saturation is necessary but not sufficient: some finite saturated sets cannot support any VLC polynomial.Source: §2.2 · p. 9
  • For S = {(0, 0), (1, 0), (2, 1)}, no positive coefficients make a + bx + cx^2y VLC, and the authors lack a necessary-and-sufficient support characterization.Evaluating y at a sufficiently large positive value breaks log-concavity of the resulting coefficient sequence.Source: §2.2 · p. 9
  • VLC polynomials are closed under scaling variables and under coefficient-wise limits when each approximating support is contained in the limit support.The limit-closure result requires the stated support containment condition.Source: §2.2 · pp. 9–10

3 Unimodular and Totally unimodular (TU) polytopes

Section 3 proves midpoint log-concavity for lattice-point counts under unimodular constraints, then uses it to show that k-solution Laurent polynomials of TU matrices are VLC and to derive capacity bounds.

3.1 Mid point log-concavity for unimodular polytopes

  • The midpoint-log-concavity proof is AI-assisted and adapts pair-decomposition and induction from graph orientations to lattice points in boxes under unimodular constraints.The proof assistance applies to Theorems 3.1, 3.2, and 3.3.Source: §3.1 · p. 11
  • For the midpoint split b=b+ + b−, the difference T(b,k1,k2;w)^2 − T(b+,k1,k2;w)·T(b−,k1,k2;w) has nonnegative Laurent coefficients.The proof expresses its coefficients using bounded-box lattice-point counts.Source: §3.1 · p. 12
  • The Ehrhart polynomial of a bounded unimodular polytope has log-concave evaluations at every integer t≥1.The stated inequality is EP(t)^2 ≥ EP(t−1)·EP(t+1).Source: §3.1 · p. 15
  • The argument does not extend to arbitrary IDP polytopes, and Theorem 3.5 fails for general IDP polytopes.The remark says the proof relies on a vertex-integrality property that does not hold for general IDP polytopes.Source: §3.1 · p. 15

3.2 Solution Laurent polynomials of TU matrices

  • The proof route does not directly extend to general unimodular matrices because splitting their rows need not preserve unimodularity.The VLC condition requires the relevant property for every partition of the rows.Source: §3.2 · p. 18
  • The k-solution Laurent polynomial of any TU matrix is VLC for every k≥0, enabling coefficient lower bounds through the capacity method.The section encodes the counts of nonnegative integer solutions to My=b as Laurent-polynomial coefficients.Source: §3.2 · pp. 15, 18

4 Capacity bounds for lattice points of TU polytopes

This section uses VLC polynomials and LP dual bounds on degree ranges to derive capacity bounds for lattice-point counts of totally unimodular polytopes and fiber cardinalities. It treats general TU matrices, specializes to matrices with nonnegative partial row sums, and applies the bounds to integer flows on directed acyclic graphs, with a corollary for Kostant partition functions.

4 Capacity bounds for lattice points of TU polytopes

  • Feasible points for the dual LPs yield capacity bounds: setting w = 0 works for general TU matrices, while setting z = 0 can give an alternative bound when a feasible w exists.The alternative applies in particular when the matrix has non-negative partial row sums and its rows sum to zero.Source: §4 · pp. 18–19

4.1 General capacity bounds for TU polytopes

  • For any TU matrix and integer vectors k and b, Theorem 4.2 gives a lower bound on B(0,k)(M, b) using capacity and degree bounds.The k-solution Laurent polynomial of a TU matrix is VLC, allowing the capacity lower-bound theorem to apply.Source: §4.1 · p. 19
  • For a finite fiber of a TU matrix, every coordinate satisfies y_i ≤ ||b||_1, enabling a capacity bound for B(M, b); for 0, ±1 matrices, the degree bounds use row counts of −1s and +1s.The row-wise bounds are α_i = −||b||_1 times the number of −1s and γ_i = ||b||_1 times the number of +1s in row i.Source: §4.1 · pp. 20–21
  • When ||b||_1 ≥ 6m · log(max{m, n}), a 0, ±1 TU matrix with finite fibers has a simply exponential lower bound for B(M, b).The paper presents this as a simplification of its preceding lower bound for sufficiently large integer vectors b.Source: §4.1 · pp. 21–22

4.2 Special cases: non-negative partial row sums

  • For a TU matrix M in {0, ±1} with nonnegative partial row sums and total row sum zero, Theorem 4.12 gives a lower bound for B(M, b), improved for directed acyclic graph incidence matrices to recover [LMY26, Theorem 1.1].Source: §4.2 · pp. 22, 26
  • For a directed acyclic graph with edges directed from larger to smaller vertices, Corollary 4.13 gives a result for its integer-flow Kostant partition function [LMY26, Theorem 1.1], see also.The excerpt identifies this as following the same steps as Theorem 4.12, with a different choice of feasible points for Theorem 4.1.Source: §4.2 · p. 26
  • In this graph orientation, the incidence matrix has nonnegative partial row sums and its rows sum to the zero vector.For each vertex i, the proof uses that no edges enter its connected component in the induced subgraph on vertices [i, n].Source: §4.2 · p. 27
  • A capacity bound applies to fibers of TU matrices whose partial row sums are nonnegative, provided the matrix has no all-zero column.The stated condition includes matrices with only 0–1 entries; the excerpt does not include the bound’s formula.Source: §4.2 · p. 27

5 Efficiency of Approximation

The section establishes an efficient deterministic method for approximating the logarithm of the lattice-point count through capacity optimization. Its ellipsoid-based implementation uses polynomial-time value and gradient approximations, with running time polynomial in the requested accuracy bits.

5 Efficiency of Approximation

  • The ellipsoid implementation uses the interiority argument of, with bounds verified directly for the Laurent polynomials rather than transferred from their 0/1 setting.The proof assumes M has full row rank; dependent rows can be removed without changing the lattice-point count or capacity, provided b remains consistent.Source: §5 · pp. 28–29
  • The deterministic algorithm approximates log E to additive error 2^-q in time polynomial in the input length and log 1/ε.Its running time has polynomial dependence on log 1/ε because the value and gradient oracles run in time polynomial in the requested accuracy bits.Source: §5 · pp. 28, 31
  • When b lies on the boundary of the Newton polytope, removing variables forced to endpoints reduces to a face where b is in the relative interior, preserving the coefficient and capacity.After this reduction, dependent rows are removed if necessary to restore full row rank.Source: §5 · p. 28
  • Facet normals of the zonotope M[0,k] can be chosen with entries in {0, +1, −1}, supplying the inequalities used to bound the minimizer.The proof uses total unimodularity to show that the determinants defining a facet normal are in {0, +1, −1}.Source: §5 · p. 29
  • The objective and its gradients admit polynomial-time approximations: the value uses geometric-series identities, while gradients use finite differences.For coordinatewise gradient error δ, the choice h = δ/(4H) and value-oracle error τ = δ²/(32H) yields total error below δ.Source: §5 · pp. 29–31
Loading 2609.39917v1…