\documentstyle[12pt]{article}
\textheight 8in
\parindent 0ex
\parskip 1.5ex
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newenvironment{proof}{\noindent{\bf Proof\,}}{\hfill$\Box$

}
\def\half{{\textstyle{1\over2}}}
\def\reals{{\bf R}}
\def\ints{{\bf Z}}
\def\complex{{\bf C}}
\def\recip#1{{1\over#1}}
\def\quarter{{\textstyle{1\over 4}}}
\def\ind{{\rm ind\,}}

\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\d{\delta}
\def\e{\epsilon}
\def\f{\phi}
\def\l{\lambda}
\def\n{\nu}
\def\s{\sigma}
\def\t{\tau}

\def\F{\Phi}
\def\G{\Gamma}
\def\L{\Lambda}
\def\OM{\Omega}

\begin{document}
\baselineskip 15pt \lineskip 3pt
 
\title{{\Large \bf  On Barvinok's Algorithm for
Counting Lattice Points in Fixed Dimension}}
\author{Martin Dyer\thanks{ Supported in part by Esprit Working 
Group RAND.}\\School of Computer Studies\\
University of Leeds, Leeds, UK
\and
Ravi Kannan\\Department of Computer Science\\Yale University,
New Haven CT, USA}
\maketitle
\begin{abstract}
We describe a simplification of a recent polynomial-time algorithm of  A. I. Barvinok 
for counting the number of lattice points in a polyhedron in fixed dimension. In particular,
we show that only very elementary properties of  exponential sums are needed to develop
a polynomial-time algorithm.
\end{abstract}
\section{Introduction}
In~\cite{barvinok}, Barvinok gives the first polynomial time algorithm for counting the
number of lattice points in a convex polyhedron in any fixed dimension $d$. This is a
significant achievement, improving dramatically on the previously known
cases for $d \leq 4$~\cite{dyer}. In fact, Barvinok's algorithm counts the number of
lattice points in a simplex with integer vertices, since it is known~\cite{dyer} that
the general problem can be reduced to this case. To do this,
the method employs {\em exponential sums}. For a given polyhedron 
$P \subseteq \reals^d$ and vector $c \in \reals^d$ this is an expression of the form
$$\s(P,c) = \sum_{x \in P \cap \ints^d} e^{-c.x}.$$
(Note that we have made a sign change from the notation of~\cite{barvinok}.)
In particular, if $K$ is a pointed polyhedral cone generated by the vectors
$u_i$ $(i=1,\ldots,k)$, the exponential sum converges provided $c.u_i > 0$
for $i=1,\ldots,k$. Barvinok's solution uses two deeper properties of these
sums. The first property is that the sum (regarded as a function of $c \in \complex^d)$
can be continued to a define a meromorphic function on $\complex^d$. The second
is an identity of Brion~\cite{brion} which relates the exponential sum over a polytope
to the sums over the cones generated by the edges at each vertex. The analytic continuation
is crucial here, since it is impossible to find a single $c$ for which all the required sums
converge. This introduces an element of symbolic computation, in order to avoid the
complication caused by poles of the sums. 

The remainder of Barvinok's procedure uses an inclusion-exclusion method to replace a 
sum over an arbitrary cone with a sum over a polynomial (in the size of the data) number of 
{\em primitive} cones. The sum over a primitive cone can be evaluated explicitly.
We discuss this in more detail below.

The purpose of this note is to indicate that the non-elementary properties of 
exponential sums invoked in Barvinok's algorithm are unnecessary to obtain a 
polynomial time algorithm for this problem.
We give an algorithm which uses only the reduction to primitive cones, replacing
the symbolic computation with arithmetic computation. This results from the fact that,
in our algorithm,  we can compute a $c$ for which all the sums involved converge.
We should emphasise, however, that our method still relies heavily on Barvinok's ideas.
\section{Definitions and Notation}
\label{defs}
The notation we use mainly follows~\cite{barvinok}, and the reader may seek further
information there on some of what follows.

Throughout, $K \subseteq \reals^d$ will be a cone pointed at the origin with linearly
independent integral generators $u_i$ $(i=1,\ldots,k)$. 
Then $u_{ij}$ will denote the $j$th component of $u_i$.
Different cones will be indicated by superscripts. Note that if $C= K+v$ is a cone
pointed at an integer point $v$, then $\s(C,c)=e^{-c.v}\s(K,c)$.

A {\em primitive} cone $K$  is a cone having a particular unique minimal set of generators 
such that  $x \in \ints^d \cap K$ if and only if $x$ can be expressed as a  linear combination
of these $u_i$ with nonnegative {\em integer} weights. It follows that, if $K$ is primitive,
$$ \s(K,c) = \prod_{i=1}^k \recip{1-e^{-c.u_i}}.$$

For given cone $K$,  the {\em index} $\ind K$ of $K$ can be defined in several
equivalent ways (see~\cite{barvinok}). We will use 
a computationally useful characterizarion of $\ind K$, as follows.
Let $U$ be the $d \times k$ matrix $[u_1 u_2 \cdots u_k]$ formed by the
generators of $K$. From the Hermite normal form consruction~\cite{schrijver}, 
there exists a $d \times d$ unimodular matrix $T$ such that
\[ TU = \left( \begin{array}{c} R \\ 0 \end{array} \right) ,\]
where $R$ is a nonsingular upper triangular matrix. Then $\ind K = | \det R|$.
These computations can be carried out in polynomial time~\cite{schrijver}.
It follows easily that $K$ is primitive if and only if $\ind K = 1$ and that,
if $K'$ is any face of $K$,  $\ind K' \leq \ind K$.

Following~\cite{barvinok}, for integers $\e_{m}$ and polyhedra $P^{m}$ $(m \in M)$, 
we will write
$$ P = \sum_{m \in M} \e_{m} P^{m}$$
to mean the corresponding identity on the characteristic functions of the polyhedra, where
the addition and scalar multiplication of  functions is pointwise. Let us call
the right hand side expression a {\em composition} of the polyhedra.  Note that these do not
correspond to the usual operations of addition and scalar multiplication of convex sets.
In general, a composition of convex sets would not necessarily be a characteristic function,
let alone that of a convex set. However, this will always be the case here.
\section{The algorithm}
We will first show that an integral simplex $S \subseteq \reals^{d-1}$ with vertices
$v_1,\ldots,v_d$ can be expressed as a composition of cones pointed at the vertices, 
such that all cones lie in the interior of some half-space. We will assume without loss
that $S$ is contained in the non-negative orthant of  $\reals^{d-1}$. This can always
be arranged with a suitable translation. We wish to determine $N$,
the number of integer points in $S$. Note that, if $\g_1= 1+\max_{i,j} v_{ij}$,
then $N < \g_1^d$.

While we could work directly in $\reals^{d-1}$,  it is easier for exposition to embed
the proof in $\reals^d$. (This is why we choose to start from a simplex in $\reals^{d-1}$.)
Thus we consider the cone $K^* \subseteq \reals^d$ with generators
$u^*_i = (1,v_i)$ ($i=1,\ldots,d$). Then, in an obvious notation,
$(1,S) = K^*\cap H_1$, where $H_1 = \{x : x_1=1\}$. 

Let us call $K \subseteq \reals^d$  a {\em standard} cone if its generators satisfy 
$u_{11}=1$ and $u_{i1}=0$ ($i=2,\ldots,k$), and each of the vectors $u_i$ is
lexicographically positive. Note that, if $K$ is a standard cone, and $(1,C) =K \cap H_1$ 
then $C$ is a cone with vertex $v$ where $(1,v)=u_1$. 
\begin{lemma}
\label{lm1}
The cone $K^*$ is a composition of standard cones $K^m$ ($m \in M$)  
with $|M| \leq 3^{d-1}$, $\e_m = \pm 1$ and $\ind K^m  \leq \ind K$ ($m \in M$).
Moreover, the required composition can be determined in polynomial time.
\end{lemma}
\begin{proof}
We will prove the Lemma by induction on $r$, for a cone $K$  with $k$ generators 
satisfying $u_{i1}=1$ ($i=1,\ldots,r$), $u_{i1}=0$ ($i=r+1,\ldots,k$) where
$1\leq r \leq k \leq d$. (We require the case $r=k=d$.) The basis for the
induction is $r=1$, when there is nothing to prove.

Assume the truth of the Lemma for  $(r-1)$ and suppose $r \geq 2$. 
We assume without loss that the generators of $K$ are
in  lexicographically decreasing order. Let $w=u_1-u_2$, so $w$ is lexicographically
positive and $w_1=0$.
We now use the ``inclusion-exclusion'' method, as in~\cite{dyer,barvinok},
to ``insert'' the vector $w$. Now $K'=K\cup K''$ ,where $K'$ has generators 
$w,u_2,\ldots,u_k$ and $K''$ has generators $u_1,w,\ldots,u_k$. 
Let $K'''= K\cap K''$ be the $(k-1)$-dimensional cone with generators
$u_1,u_3,\ldots,u_k$. Then clearly
$$ K' = K + K'' - K''',\qquad \mbox{i.e.}\ \ K = K' - K'' + K''' . $$
Thus $K$ is a composition of three cones, each with only $(r-1)$ generators having nonzero 
first component. Note that $\ind K' = \ind K'' = \ind K$, since they all generate the
same lattice, and $\ind K''' \leq \ind K$, since the generators of $K'''$ are a subset of 
those of $K$. Applying the inductive hypothesis gives the Lemma. The proof 
clearly indicates a polynomial time algorithm.
\end{proof}
We remark that this type of decomposition is well known. For
example, it is the starting point in~\cite{Varch} and it is mentioned there as
a ``folklore result''. It also leads to an  an elementary proof of the Brion's
identity in the spirit of~\cite{Khov}.

Now, we follow Barvinok's method to express each of the cones $K^m$ from Lemma~\ref{lm1}
as a composition of primitive cones. This is done in the following way. For a given cone
$K$ with $\ind K > 1$, determine the matrix $R$ as in section~\ref{defs} using a
Hermite normal form algorithm.
Compute the shortest  nonzero vector $\l$, in $\ell_\infty$ norm, in the lattice generated by the
columns of $R^{-1}$. This can be done in polynomial time, in fixed dimension, using the
basis reduction algorithm~\cite{schrijver} followed by enumeration.
By Minkowski's theorem (see e.g.~\cite[p 71]{schrijver}),
$$||\l||_\infty \leq | \det R^{-1}|^{1/k}= | \det R|^{-1/k}= (\ind K)^{-1/k}.$$ 
Now $\l = R^{-1}z$, for some integral $z$ so $z = R\l$ and hence
\[ w = T^{-1} \left( \begin{array}{c}  z  \\ 0  \end{array} \right) 
= T^{-1} \left( \begin{array}{c} R\\ 0 \end{array}\right) \l = U\l  ,\]
is a nonzero integer vector which is a linear combination of the generators of $K$ with
weights at most $(\ind K)^{-1/k}$ in absolute value. We may clearly insist that
$w$ is lexicographically positive. We now, using inclusion-exclusion, we can
express $K$ as a composition of faces of the cones $K^i$ with generators 
$u_1,\ldots,u_{i-1},w,u_{i+1},\ldots,u_k$. See~\cite{barvinok} for details.
There are at most $k2^k$ cones of this form. Suppose $U_i$ is the matrix
of generators of $K^i$. Note that $w=U\l$. Let $\L_i$ be
the matrix which is a $k \times k$ identity, except that the $i$th column is $\l$.
Then $U_i = U\L_i$. Let $T_i,T$ be the unimodular matrices which reduce
$U_i,U$ respectively to Hermite normal form, then
\[ \left( \begin{array}{c} R_i\\ 0 \end{array}\right) = T_iU_i = T_iU\L_i
= T_i T^{-1} \left( \begin{array}{c} R\L_i \\ 0 \end{array} \right) , \]
from which it follows that $| \det R_i |= | \det (R\L_i)|$. Hence
$$\ind K^i = \l_i \ind K \leq (\ind K)^{-1/k}\ind K = (\ind K)^{(k-1)/k}.$$
From this it follows that iterating this $O(\log \log \ind K)$ times we obtain cones
with $\ind K = 1$, i.e. primitive cones. The total number of cones generated is
then only polynomial in $\log \ind K$, for fixed $k$.

At the end of this process, we have expressed the simplex $S$ as a composition
of a polynomial number of primitive cones, such that all cones have vertex in the
non-negative orthant and all cone generators are lexicographically positive.
We now show that there is a polynomial-sized $c>0$ such that $c.u_i>0$  for all 
generators of all cones. 
\begin{lemma} 
Let $u_r \in \reals^d$ ($r=1,2,\ldots$) be any collection of lexicographically
positive integer vectors, such that $\g_2= 1 +\max_{r,j} |u_{r,j}| $ is bounded. Then the
vector $c_0 = (\g_2^{d-1}, \g_2^{d-2},\ldots,\g_2,1)$ satisfies $c_0.u_r \geq 1$ ($\forall r$).
\end{lemma}
\begin{proof}
Suppose $u_{r,s}\geq 1$ is the first nonzero element of $u_r$. Then
$$ c_0.u_r \geq \g_2^{d-s} - \sum_{j=0}^{d-s-1} (\g_2-1).\g_2^j = 1$$.
\end{proof}
Thus there exists a $c_0$ such that for any $c=\d c_0$ ($0< \d \leq 1$),
$\s(S,c)$ can be expressed as a sum of $\t$ terms of the form
\begin{equation}
\label{eq3}
 \pm \frac{e^{-c.v}}{\prod_{i=1}^d (1-e^{-c.u_i})} , 
\end{equation}
where $c.v >0$ and $c.u_i>0$ for $i=1,\ldots,d$ and $\t$ is bounded by a polynomial
in the size of the description of $S$.
We now show that we find a suitable $\d$ such that $\s(S,c)$ approximates $N$
closely enough. Let $\g = \max \{ \g_1,\g_2 \}$.
\begin{lemma}
\label{lm4} 
Let $\d = \min \{ 1/(4d\g^{2d}), 1/(8\t)\}$ and $c = \d c_0$, then 
$$\s(S,c) \leq N < \s(S,c) + \quarter.$$
\end{lemma}
\begin{proof}
For any $x \in S$ we have 
$$c.x \leq \d (d \g_2^{d-1})\g_1 < \quarter \g^{-d }$$
Hence $ 1 - \quarter \g^{-d}  < 1 - c.x  \leq  e^{-c.x}\leq 1$, and thus
$$ N - \quarter < \sum_{x \in S} e^{-c.x}\leq N ,$$
since $N < \g^d$.
\end{proof}
Clearly the $c$ determined in Lemma~\ref{lm4} is a rational vector
of polynomial size in the data. 

We now determine an approximation $\hat{\s}(S,c)$
to $\s(S,c)$ such that $| \hat{\s}(S,c) - \s(S,c)| \leq \quarter$. Then
$$ \hat{\s}(S,c)- \quarter \leq N < \hat{\s}(S,c)+ \half ,$$
and thus $N$ is $\hat{\s}(S,c)$ rounded to the nearest integer. Thus it suffices to determine
each term~(\ref{eq3}) to within $1/(4\t)$. 

Let $c.v = \a$, $c.u_i = \b_i$. Then $\a \leq \quarter$, and since
$$ 1 \leq c_0.u_i \leq \sum_{j=0}^{d-1} (\g_2 - 1)\g_2^j <   \g_2^d , $$
and $\d < \quarter$, we have
$$ \d \leq \b_i \leq \d \g_2^d < \d (4d \d)^{-1} \leq \half \sqrt{\d} < \quarter. $$
Now let $a(y)$ be the approximation to $e^{-y}$ using the first $(2d+3)$ terms
of its series expansion. This series is alternating and  we have $0 \leq  \a \leq \d$,
$\d \leq \b_i \leq \half \sqrt{\d}$. It follows that $a(\a)$ approximates $e^{-\a}$, 
and $(1-a(\b_i))$ approximates $(1-e^{-\b_i})$ with relative error less than 
$\half\d^{d+1}/(2d+3)!$. Thus using the approximation $a(y)$ in~(\ref{eq3})
leads to an approximation with  relative error less than $(d+1)\d^{d+1}/(2d+3)!$.
Now the term~(\ref{eq3}) is at most $(2/\d)^d$. Hence the absolute error due
to approximating~(\ref{eq3}) in this manner will be will be at most 
$2^{d}\d/(2d+3)! < \d \leq 1/(8\t)$. Thus it suffices to replace each exponential
by the fixed polynomial $a(x)$ of degree $2(d+1)$. It now follows that we can
compute the required  $\hat{\s}(S,c)$ in polynomial time.
\section*{Acknowledgement}
We are grateful to Alexander Barvinok for helpful comments.
\begin{thebibliography}{99}
\bibitem{barvinok}A. I. Barvinok, A polynomial time algorithm for counting integral
points in polyhedra when the dimension is fixed, in {\em Proceedings of the 34th Annual
Symposium on Foundations of Computer Science}, IEEE Computer Society Press, 1993, pp 566--572.
\bibitem{brion} M. Brion, Poly\`edres et r\'eseaux, {\em L'enseignement 
Math\'ematique} {\bf 38} (1992), 71--78.
\bibitem{dyer}M. E. Dyer, On counting lattice points in polyhedra,
{\em SIAM Journal on Computing} {\bf 20} (1991), 695--707.
\bibitem{Khov}  A.G. Khovanskii and A.V. Puhlikov, A Riemann-Roch theorem for
integrals and sums of quasipolynomials on virtual polytopes (Russian), {\it Algebra i analiz},
{\bf 4} (1992), N 4, 188--216, translated in {\it St. Petersburg Mathematical Journal},
{\bf 4} (1992), 789--812.
\bibitem{schrijver}A. Schrijver, {\em Theory of linear and integer programming,}
John Wiley, Chichester, 1986.
\bibitem{Varch}  A.N. Varchenko, Combinatorics and topology of the disposition of affine
hyperplanes in real space (Russian), {\it Funktsional. Anal. i Prilozhen.},
{\bf 21} (1987), N 1, 11-22, translated in {\it Funct. Anal. Appl.}, {\bf 21} (1987), 9-19.

\end{thebibliography}
\end{document}