These pages are not updated anymore. They reflect the state of . 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