An Algorithmic Theory of Lattice Points in Polyhedra
Alexander I. Barvinok, James Pommersheim · 1999
We discuss topics related to lattice points in rational polyhedra, including efficient enumeration of lattice points, “short” generating functions for lattice points in rational polyhedra, relations to classical and higher-dimensional Dedekind sums, complexity of the Presburger arithmetic, efficient computations with rational functions, and others. Although the main slant is algorithmic, structural results are discussed, such as relations to the general theory of valuations on polyhedra and connections with the theory of toric varieties. The paper surveys known results and presents some new results and connections. 1. Introduction: “A Formula for the Number of Lattice Points. .. “ The first main object of this paper is the integer lattice 𝕫 d ⊂ ℝ d consisting of the points with integer coordinates. We define the second main object. We are interested in the set P ⋂ 𝕫 d of lattice points belonging to a given rational polyhedron P . For example, we may be interested in finding a “formula” for the number of lattice points in a given rational or integer polytope P. But what does it mean to “find a formula“? We consider a few examples.