The many aspects of counting lattice points in polytopes (Q2491985): Difference between revisions

This well-written survey discusses applications of lattice-point enumeration problems in convex rational polytopes. Any such counting problem can be formulated in terms of the function \[ \phi_A(b) = \# \left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\} , \] for some integral \(d \times n\) matrix \(A\) and \(b \in {\mathbb Z}^d\). The author surveys some specific applications, such as knapsack problems, integral network flows, transportation polytopes and contingency tables, magic squares, Gelfand-Tsetlin patterns, and Hilbert series of monomial algebras. The paper gives the main structure theorem about \(\phi_A(b)\), namely that this function is a piecewise-defined quasipolynomial [\textit{B. Sturmfels}, J. Comb. Theory, Ser. A 72, No. 2, 302--309 (1995; Zbl 0837.11055)]. A fundamental specialization of this counting function is given by \(\phi_A(tb)\) for a fixed \(b\); hence \(t\) becomes an integral parameter which can be thought of as a dilation factor of the polytope \(\left\{ x \in {\mathbb Z}_{ \geq 0 }^n : \;Ax = b \right\}\). If this polytope has integral vertices, Ehrhart's theorem asserts that \(\phi_A(tb)\) is a polynomial in \(t\) whose leading term is the volume of \(P\) [\textit{E. Ehrhart}, C. R. Acad. Sci., Paris 254, 616--618 (1962; Zbl 0100.27601)]. The author finishes with a description of Barvinok's algorithm, which computes the lattice-point count for a rational polytope in fixed dimension in polynomial time. The paper concludes with some alternative algorithmic approaches and a brief discussion of lattice-point problems for regions other than convex polytopes.