ON COUNTING LATTICE POINTS IN POLYHEDRA

Some reductions of the computational problem of counting all the integer lattice points in an arbitrary convex polyhedron in a fixed number of dimensions d are considered. It is shown that only odd d need to be studied. In three dimensions the problem is reduced to the computation of Dedekind sums. Hence it is shown that the counting problem in three or four dimensions is in polynomial time. A corresponding reduction of the five-dimensional problem is also examined, but is not shown to lead to polynomial-time algorithms.