What is LattE?

The name ``LattE'' is an abbreviation for ``Lattice point Enumeration.'' So what exactly does LattE do? The software's main function is to count the lattice points contained in convex polyhedra defined by linear equations and inequalities with integer coefficients. The polyhedra can be of any (reasonably small) dimension, and LattE uses an algorithm that runs in polynomial time for fixed dimension: Barvinok's algorithm [1]. To learn more about the exact details of our implementation and algorithmic techniques involved, the interested reader can consult [3,4,5] and the references listed therein. Here we give a rather short description of the mathematical objects used by LattE, Barvinok's Rational Functions:

Given a convex polyhedron $P = \{u\in{\mathbb{R}}^d:Au\leq b\}$ , where $A$ and $b$ are integral, the fundamental object that we compute is a short representation of the infinite power series:

$$f(P;x) \quad = \sum_{\alpha\in P\cap{\mathbb{Z}}^d} x_1^{\alpha_1} x_2^{\alpha_2} \ldots x_d^{\alpha_d}.$$

Here each lattice point is given by one monomial. Note that this can be a rather long sum, in fact for a polyhedral cone it can be infinite, but the good news is that it admits short representations.

Example: Let $P$ be the quadrangle with vertices $V_1=(0,0)$ , $V_2=(5,0)$ , $V_3=(4,2)$ , and $V_4=(0,2)$ .

$f(P;x,y)={x}^{5}+{x}^{4}y+{x}^{4}+{x}^{4}{y}^{2}+y{x}^{3}+{x}^{3}+ {x}^{3}{y}^{2}+y{x}^{2}+{x}^{2}+{x}^{2}{y}^{2}+xy+x+x{y}^{2}+y+1+ {y}^{2}$

The fundamental theorem of Barvinok (circa 1993, see [1]) says that you can write $f(P;x)$ as a sum of short rational functions, in polynomial time when the dimension of the polyhedron is fixed. In our running example we easily see that the 16 monomial polynomial can be written as shorter rational function sum:

$f(P;x,y)=f(K_{V_1};x,y)+f(K_{V_2};x,y)+f(K_{V_3};x,y)+f(K_{V_4};x,y)$

where

$f(K_{V_1};x,y)={\frac {1}{\left (1-x\right )\left (1-y\right )}} \quad f(K_{V_2};x,y)=\frac{({x}^{5}+{x}^{4}y)}{ (1-{x}^{-1}) (1-y^2x^{-1})}$

$f(K_{V_3};x,y)=\frac{({x}^{4}{y}^{2}+{x}^{4})}{ (1-{x}^{-1}) (1-xy^{-2})} \quad f(K_{V_4};x,y)=\frac{y^{2}}{(1-{y}^{-1} )(1-x )}$

$f(P; 1,1)=16$

Counting the lattice points in convex polyhedra is a powerful tool which allows many applications in areas such as Combinatorics, Statistics, Optimization, and Number Theory.