Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

% **************************************************************************
% * The TeX source for AMS journal articles is the publisher's TeX code    *
% * which may contain special commands defined for the AMS production      *
% * environment.  Therefore, it may not be possible to process these files *
% * through TeX without errors.  To display a typeset version of a journal *
% * article easily, we suggest that you either view the HTML version or    *
% * retrieve the article in DVI, PostScript, or PDF format.                *
% **************************************************************************
%  Author Package
%% Translation via Omnimark script a2l, May 22, 1996 (all in one day!)
%\controldates{16-JUL-1996,16-JUL-1996,16-JUL-1996,23-JUL-1996}
\documentclass{era-l}
\usepackage{amssymb}

%\revdate December1,1995\endrevdate 
%\issueinfo{2}{1}{}{1996}
\copyrightinfo{1996}{American Mathematical Society}

%% Declarations:

\theoremstyle{plain}
\newtheorem*{theorem1}{Lemma 1}
\newtheorem*{theorem2}{Lemma 2}
\newtheorem*{theorem3}{Theorem}
\newtheorem*{theorem4}{Corollary}

\DeclareMathOperator{\im}{Im}
%\DeclareMathOperator{\gcd}{gcd}
%% User definitions:

\newcommand{\latticeP}{{L({\mathcal{P}} , t)}}
\newcommand{\latticePint}{{L({\mathcal{P}}^{int} , t)}}
\newcommand{\latticePclos}{{L({\mathcal{P}}^{clos} , t)}}
\newcommand{\Pe}{{\mathcal{P}}}
\newcommand{\gen}{\frak G}
\newcommand{\biglat}{{\mathbb{Z}}^{n+1}}
\newcommand{\phiep}{\phi _{\epsilon }}
\newcommand{\zn}{{\mathbb{Z}}^{n+1}}
\newcommand{\fsub}{f_{\eta }}


\begin{document}

\title[The Ehrhart polynomial]{The Ehrhart polynomial of a 
lattice $n$-simplex}
\author{Ricardo Diaz}
\address{Department of Mathematics,
University of Northern Colorado, Greeley, Colorado 80639}
\email{rdiaz@bentley.univnorthco.edu}
\author{Sinai Robins}
\address{Department of Mathematics, UCSD
9500 Gilman Drive, La Jolla, CA 92093-0112 }
\email{srobins@ucsd.edu}
\thanks{Research partially supported by NSF Grant \#9508965.}
\keywords{Lattice polytopes, Ehrhart polynomials, Fourier analysis, 
Laplace transforms, cones, Dedekind sums}

\subjclass{Primary 52B20, 52C07, 14D25, 42B10, 11P21, 11F20, 05A15;
Secondary 14M25, 11H06}
\commby{Svetlana Katok}
\date{August 4, 1995, and, in revised form, December 1, 1995}
\begin{abstract}The problem of counting the
 number of lattice points inside a lattice polytope in
$\mathbb{R}^{n}$ has been studied from a variety of perspectives, including the recent
work of Pommersheim and
 Kantor-Khovanskii using toric varieties and Cappell-Shaneson
using Grothendieck-Riemann-Roch. 
Here we show that  the  Ehrhart polynomial of a 
lattice $n$-simplex has a simple analytical interpretation from the perspective 
of Fourier Analysis on the
$n$-torus. We  obtain closed forms in terms  of  cotangent
expansions for the coefficients of the Ehrhart polynomial,
that  shed additional light on  previous descriptions of the 
Ehrhart polynomial. 
\end{abstract}
\maketitle

The number of lattice points inside a convex lattice
polytope in
$\mathbb{R}^{n}$  (a polytope whose  vertices have integer coordinates) has been
studied intensively  by combinatorialists,  algebraic geometers,
number theorists, Fourier analysts, and differential geometers.
  Algebraic geometers have shown that the
Hilbert polynomials of toric varieties associated to convex lattice polytopes
precisely describe the number of lattice points inside their  dilates  
\cite{3}.   
Number theorists have estimated  lattice point counts 
inside symmetric bodies in
$\mathbb{R}^{n}$   to get bounds on ideal norms and class numbers
of number fields. 
Fourier analysts have estimated the number of lattice points
in simplices using Poisson summation   (see Siegel's
classic solution of the Minkowski problem \cite{14} and  Randol's  estimates for lattice points inside
dilates of general planar regions  \cite{13}). Differential geometers have also become interested in lattice point counts in  polytopes 
in connection with the  Durfree conjecture  \cite{18}. 

Let $\mathbb{Z}^{n}$ denote the  $n$-dimensional integer lattice  in $\mathbb{R}^{n}$, and
let $\Pe $ be an $n$-dimensional lattice polytope in $\mathbb{R}^{n}$. 
Consider the function of an integer-valued variable $t$
that describes the number of lattice points that lie inside the dilated polytope
$t\Pe $:  
\begin{equation*}\latticeP = \text{the cardinality of } \{t\Pe \} \cap \mathbb{Z}^{n}.
\end{equation*}
Ehrhart \cite{4} inaugurated the systematic study of general properties of
this function by proving that
it is always a polynomial in
$t \in \mathbb{N}$, and  that in fact
\begin{equation*}\latticeP = \text{Vol} (\Pe ) t^{n} + \frac{1}{2} \text{Vol} (\partial \Pe ) t^{n-1} + \cdots +
\chi (\Pe ) 
\end{equation*}
for closed polytopes $\Pe $.
Here $\chi (\Pe )$ is the Euler characteristic of $\Pe $, and $\text{Vol} (\partial \Pe )$
is the surface area of $\Pe $  normalized with respect to the sub-lattice on
each face of $\Pe $.    The Ehrhart-MacDonald reciprocity law 
$L( \Pe ^{int}, t) = (-1)^{n} L(\Pe ^{clos}, -t)$  
 established that the study of the open polytope $\Pe $ is essentially
equivalent to the study of its closure. 

 The other coefficients of $\latticeP $ 
 remained a mystery, even for a general lattice
$3$-simplex, until the recent work of Pommersheim \cite{12} in 
$\mathbb{R}^{3}$, Kantor and Khovanskii  \cite{6} in $\mathbb{R}^{4}$, and
most recently Cappell and Shaneson \cite{2} in $\mathbb{R}^{n}$.
\cite{12} and \cite{6} used techniques from algebraic geometry 
related to the  Todd classes of toric varieties to express these
coefficients in terms of Dedekind sums and other cotangent expansions, and \cite{2} used Grothendieck-Riemann-Roch  for 
their work on convex lattice polytopes.  The present paper introduces Fourier methods
into the study of lattice polytopes, and some known recent results are shown
to be easy corollaries of the main theorem.  In the course of the page proofs 
Brion and Vergne have  communicated to us that they recently and independently
found another characterization of the Ehrhart polynomial using Fourier methods.    

  We compute the Ehrhart polynomial via Fourier integrals on the $n$-torus
by first finding an
explicit description of an associated generating function, defined by 
\begin{equation*}\gen (\Pe , s) =  \sum _{t=0}^{\infty } \latticeP e^{-2\pi s t}.  \tag{{1}}
\end{equation*}
A geometrical interpretation of this expression can be given that
provides a direct link with Fourier analysis and the Poisson summation formula. 
The polytope
$\Pe \subset {\mathbb{R}}^{n}$  and its dilates can be regarded as parallel
 sections of a convex cone
$K \subset {\mathbb{R}}^{n+1}$  with vertex $\{ 0\}\in {\mathbb{R}}^{n+1} $,
 generated by
 $\Pe \times \{ 1 \}$; and the generating
function can be regarded as the sum of the values of an exponentially decaying 
function taken over all integral 
 lattice points lying in $K$. For a related construction see
\cite{1}. In order to investigate the general properties of such sums
systematically it is convenient to  introduce some notation and terminology.  
The polar cone associated to a convex cone
$K$ is  the convex cone defined by 
\begin{equation*}K^{*} =
\{ \eta \in {\mathbb{R}}^{n+1}: \langle x , \eta \rangle <0, \ \forall x
 \in K \}.\end{equation*}
 For each $\eta \in K^{*}$ consider the  convergent sum
\begin{equation*}
\gen (K, \eta ) = \sum _{x \in \biglat }\chi _{K}( x)  \exp (2 \pi \langle x, 
\eta \rangle ),
\end{equation*}
which can be regarded as a discrete, multi-variable Laplace transform of the
characteristic function of $K$. We are interested in the  behavior of the restriction of
$\gen (K,
\eta )$ to the positive  ray $\eta = s\eta _{0}$
where  $ s\in {\mathbb{R}}^{+}$ and $\eta _{0}= 
(0, 0, 0, \dots , -1) \in K^{*}$, because $\gen (K, s \eta _{0}) = \gen (\Pe , s)$
is the generating function of the Ehrhart polynomial of the simplex  $\Pe $  that
generates $K$. 
We  evaluate $\gen ( K, \eta )$  by first computing  the (continuous) Fourier-Laplace
transform of smoothed versions of the exponentially damped characteristic function of $K$, and
then applying the Poisson summation formula to pass from the continuous to the discrete setting.

Once the generating function $\gen (\Pe ,s)$  has been determined, it is easy to recover the 
Ehrhart function itself. Precisely because
$\latticeP $ is a polynomial in $t$,  the generating function is a rational
function in  $e^{-2\pi s}$. Its meromorphic continuation into
the  complex $s$-plane has a pole at $s=0$, and
 the Ehrhart polynomial coefficients are
recovered from  the singular part of the generating function
$\gen (\Pe , s)$   in its Laurent expansion at $s=0$.

Given any  $n$-dimensional lattice simplex $\Pe $ in $\mathbb{R}^{n}$,  translate the
simplex if necessary to arrange for one vertex to be the origin. The position
vectors of the remaining
$n$ vertices of $\Pe $ can be arranged in arbitrary order  
 as the column vectors of an associated
$n \times n$ matrix with integer entries. Reduce this integer matrix  to its
(unique) Hermite normal form, which is a lower  triangular matrix, by
unimodular transformations acting on the left \cite{9}. Since unimodular transformations are
bijective transformations of the lattice ${\mathbb{Z}}^{n}$, the image of
$\Pe $  by this left unimodular action contains the same number of lattice points as $\Pe $
itself. Applying the same reasoning to the integral dilates of $\Pe $, 
we see that the Ehrhart
polynomial is an invariant under unimodular transformations of $\Pe $.
 Thus we assume henceforth, without  loss of generality, that the matrix whose columns
are the vertices of
$\Pe $ is lower-triangular. 

Now let $K$ denote the convex cone in  $\mathbb{R}^{n+1}$ generated by 
a copy of  $\Pe $ placed on the hyperplane 
$   \mathbb{R}^{n} \times \{1\}
\subset {\mathbb{R}}^{n+1}$. $K$  consists of rays through the origin of ${\mathbb{R}}^{n+1}$ 
that intersect the hyperplane $x_{n+1}=1$ at points of the form  
$(x,1)$, where $x\in \Pe $. The $(n+1)$-dimensional simplex obtained by retaining
the portion of $K$ that lies on one side of this hyperplane is
also represented by a lower-triangular integer matrix:

\begin{equation*}M = \left ( \begin{matrix}a_{1,1}  \\
    a_{2,1}   & a_{2,2}  \\
					 \vdots &  \vdots \\
					a_{n,1}  &  a_{n,2} & \cdots & a_{n, n}   \\
            1 &    1     & \cdots & 1        & 1  \\
\end{matrix}
\right ).
\end{equation*}

The Fourier-Laplace transform of the characteristic function of the
set $K$ is defined by the integral formula
\begin{equation*}\hat \chi _{K} (\zeta ) =  \int _{x\in K} \exp (- 2\pi i\langle \zeta , x \rangle ) \ dx
\end{equation*} 
that incorporates  the  {\em complex} frequency vector 
$\zeta =   \xi + i \eta \in {\mathbb{R}}^{n+1} + i {\mathbb{R}}^{n+1}$. 
This function of a complex vector can also be expressed in terms of the traditional
Fourier transform (which is defined for real frequency vectors only): the
Fourier-Laplace transform  of $\chi _{K}$ is just the Fourier transform $\int _{x} f_{\eta } (x) \exp (-2\pi i \langle x, \xi \rangle ) \ dx$  of the  function
\begin{equation*}f_{\eta }(x) =  \chi _{K} (x)  \exp (2\pi \langle x , \eta \rangle ), 
\end{equation*}
which is absolutely
integrable if
$\eta $ lies in the polar cone  $K^{*}$.
It is traditional to denote both transforms by the same symbol: $ \hat {}$  .  

The Fourier-Laplace transform $\hat \chi _{K}
(\zeta )$  will now be computed explicitly. (Note incidentally that the following
lemma holds for the cone over any simplex, not necessarily a lattice simplex.)

\vbox {\begin{theorem1}
For every complex frequency vector $\zeta $ satisfying  
$\im \zeta \in K^{*}$, the  Fourier-Laplace transform of the
characteristic function of the cone
$K$ is a product of reciprocals of linear forms determined by the columns of
the matrix $M$ that generates $K$:
\begin{equation*}\hat \chi _{K} (\zeta )=  |\det M| \ \prod _{k=1}^{n+1} 
\frac{1}{\langle 2 \pi i \zeta , M_{k} \rangle }.  
\end{equation*}
\end{theorem1}
\hfill $\square $}


Taking $\zeta =  
(\xi _{1}, \xi _{2}, \dots , \xi _{n+1}) -i (0, 0,  \dots , s)
\in {\mathbb{Z}}^{n+1} +i K^{*}$  we see that Lemma 1 gives 
the explicit formula 
\begin{equation*}
\hat f_{s\eta _{0}} \ (\xi ) =\frac{|\det M|}{ (2\pi )^{n+1}} 
\prod _{k=1}^{n+1}\frac{1}{ 
s+ il_{k}(\xi )} , \tag{2}
\end{equation*}
where  the linear forms $l_{k}(\xi ) = \langle \xi , M_{k}\rangle $ are determined by the
columns of $M$. 
Note that since $M$ is a lower-triangular
matrix, the linear form $l_{k}(0, 0, \dots , \xi _{k}, \dots , \xi _{n+1}
)$  depends only on the last $n+1-k$ coordinates of  $\xi $.  

We would like to use the Poisson summation formula to sum expression (2) over
all  integral frequency vectors $\xi = (\xi _{1},  \dots , \xi _{n+1})\in {\mathbb{Z}}^{n+1}$, but before doing so we multiply (2) by  an additional damping
function  in the frequency domain that makes the resulting series absolutely
summable. This is equivalent to mollifying the function $f_{\eta }(x)$ by
convolution. The mollifier will be taken to be an approximate identity $\phi _{\epsilon }(x)$  constructed from a dilated version of
$f_{\eta _{0} }(x)$, normalized to have mass one. This normalization
condition is equivalent to requiring that   
$\hat \phi _{\epsilon } (0) =1$.
 For each real $\epsilon \ne 0$    we therefore multiply (2) by
\begin{equation*}\hat \phi _{\epsilon }(\xi ) = 
\frac{ \hat f _{\eta _{0}} (\epsilon \xi )}{\hat f_{\eta _{0}}(0)} =
\prod _{k=1}^{n+1} 
\frac{1}{(1+ i\epsilon l_{k}( \xi ))}
\end{equation*} 
to get
\begin{equation*}\widehat { (f_{s\eta } * \phi _{\epsilon })}(\xi ) = 
\frac{|\det M|}{ (2\pi )^{n+1}} 
\prod _{k=1}^{n+1} \frac{1}{ (s+ il_{k}(\xi )) (1+ i\epsilon l_{k}( \xi ))}.
\tag{{3}}
\end{equation*}

 \begin{theorem2} Suppose that $\epsilon \ne 0$ and $\eta \in K^{*}$.

(i) The Poisson
summation formula holds for
$\fsub *\phiep $ in the sense that the following two sums  are both absolutely
convergent representations of a common expression:
\begin{equation*}\gen _{\epsilon }  (K, \eta ):= \sum _{x\in \zn } (\fsub *\phiep ) (x)= \sum _{\xi \in \zn }\hat \fsub (\xi )
\hat \phiep (\xi ).
\end{equation*}

(ii)  The preceding expression, $\gen _{\epsilon }(K, \eta )$, possesses one-sided limits  as
$\epsilon \rightarrow 0^{\pm }$; and  these one-sided limits are the discrete Laplace transforms of the
 characteristic functions of the interior and closure of $K$:
\begin{equation*}(ii.a)  \lim _{ \epsilon \rightarrow 0^{+}} \gen _{\epsilon } (K, \eta ) = \sum _{x\in \zn }
\chi _{\mathcal{K}^{\text{int}}} (x) \exp (2\pi \langle x, \eta \rangle ) = \gen ( K^{\text{int}}, \eta );\end{equation*}
\begin{equation*}(ii.b)  \lim _{ \epsilon \rightarrow 0^{-}} \gen _{\epsilon } (K, \eta ) = \sum _{x\in \zn }
\chi _{\mathcal{K}^{\text{clos}}} (x)
\exp (2 \pi \langle x,
\eta \rangle ) = \gen ( K^{\text{clos}}, \eta ).
\end{equation*}
\hfill $\square $
\end{theorem2}

%\enlargethispage*{1\baselineskip}

In view of Lemma 1 it is natural to investigate the sum $\sum _{\xi \in \biglat } \hat \fsub (\xi ) \hat \phiep (\xi )$  using  (3).  To describe the main result
let $\mathcal{G}$ be the finite abelian group $(\mathbb{Z} /{p_{1} \mathbb{Z} }) \times \cdots \times (\mathbb{Z}/{p_{n} \mathbb{Z}})$, where 
$p_{k} = \prod _{i