Simple Explicit Formula for Counting Lattice Points of Polyhedra

J.B. Lasserre(lasserrelaas.fr)
E.S. Zeron(eszeronmath.cinvestav.mx)

Abstract: Given $z\in C^n$ and $A\in Z^{m\times n}$, we consider the problem of evaluating the counting function $h(y;z):=\sum\{z^x : x \in Z^n; Ax = y, x \geq 0\}$. We provide an explicit expression for $h(y;z)$ as well as an algorithm with possibly numerous but simple computations. In addition, we exhibit finitely many fixed convex cones of $R^n$ explicitly and exclusively defined by $A$ such that for any $y\in Z^m$, the sum $h(y;z)$ can be obtained by a simple formula involving the evaluation of $\sum z^x$ over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.

Keywords: Computational geometry; lattice polytopes.

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Integer Programming (Other )

Citation: To be presented at IPCO 2007, Cornell, June 2007

Download: [PDF]

Entry Submitted: 02/14/2007
Entry Accepted: 02/14/2007
Entry Last Modified: 02/14/2007

Modify/Update this entry