ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 2, Number 1, August 1996

THE EHRHART POLYNOMIAL OF A LATTICE n-SIMPLEX

RICARDO DIAZ AND SINAI ROBINS

(Communicated by Svetlana Katok)

Abstract. The problem of counting the number of lattice points inside a lattice polytope in ℝ^{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.

The number of lattice points inside a convex lattice polytope in ℝ^{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 [3]. Number theorists have estimated lattice point counts inside symmetric bodies in ℝ^{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 [14] and Randol’s estimates for lattice points inside dilates of general planar regions [13]). Differential geometers have also become interested in lattice point counts in polytopes in connection with the Durfree conjecture [18].

Let ℤ^{n} denote the n-dimensional integer lattice in ℝ^{n}, and let P be an ndimensional lattice polytope in ℝ^{n}. Consider the function of an integer-valued variable t that describes the number of lattice points that lie inside the dilated polytope tP:

L(P, t) = the cardinality of {tP} ∩ ℤ^{n}.

Ehrhart [4] inaugurated the systematic study of general properties of this function by proving that it is always a polynomial in t ∈ ℕ, and that in fact

L(P, t) = Vol(P)t^{n} + \frac{1}{2}Vol(∂P)t^{n−1} + ⋯ + χ(P)

\begin{matrix}c \\ ◯ \end{matrix}1996 American Mathematical Society

Received by the editors August 4, 1995, and, in revised form, December 1, 1995.

1991 Mathematics Subject Classification. Primary 52B20, 52C07, 14D25, 42B10, 11P21, 11F20, 05A15; Secondary 14M25, 11H06.

Key words and phrases. Lattice polytopes, Ehrhart polynomials, Fourier analysis, Laplace transforms, cones, Dedekind sums.

Research partially supported by NSF Grant #9508965.

for closed polytopes P. Here χ(P) is the Euler characteristic of P, and Vol(∂P) is the surface area of P normalized with respect to the sub-lattice on each face of P. The Ehrhart-MacDonald reciprocity law L(P^{int}, t) = (−1)^{n}L(P^{clos}, −t) established that the study of the open polytope P is essentially equivalent to the study of its closure.

The other coefficients of L(P, t) remained a mystery, even for a general lattice 3-simplex, until the recent work of Pommersheim [12] in ℝ^{3}, Kantor and Khovanskii [6] in ℝ^{4}, and most recently Cappell and Shaneson [2] in ℝ^{n}. [12] and [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 [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

𝔊(P, s) = ∑_{t=0}^{∞} L(P, t)e^{−2πst}. (1)

A geometrical interpretation of this expression can be given that provides a direct link with Fourier analysis and the Poisson summation formula. The polytope P ⊂ ℝ^{n} and its dilates can be regarded as parallel sections of a convex cone K ⊂ ℝ^{n+1} with vertex {0} ∈ ℝ^{n+1}, generated by P × {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 [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

K^{∗} = {η ∈ ℝ^{n+1} : ⟨x, η⟩ < 0, ∀x ∈ K}.

For each η ∈ K^{∗} consider the convergent sum

𝔊(K, η) = ∑_{x∈ℤ^{n+1}} χ_{K}(x) exp(2π⟨x, η⟩),

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 𝔊(K, η) to the positive ray η = sη_{0} where s ∈ ℝ^{+} and η_{0} = (0, 0, 0, …, −1) ∈ K^{∗}, because 𝔊(K, sη_{0}) = 𝔊(P, s) is the generating function of the Ehrhart polynomial of the simplex P that generates K. We evaluate 𝔊(K, η) 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 𝔊(P, s) has been determined, it is easy to recover the Ehrhart function itself. Precisely because L(P, t) is a polynomial in t, the generating function is a rational function in e^{−2π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 𝔊(P, s) in its Laurent expansion at s = 0.

Given any n-dimensional lattice simplex P in ℝ^{n}, translate the simplex if necessary to arrange for one vertex to be the origin. The position vectors of the remaining n vertices of P can be arranged in arbitrary order as the column vectors of an associated n × 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 [9]. Since unimodular transformations are bijective transformations of the lattice ℤ^{n}, the image of P by this left unimodular action contains the same number of lattice points as P itself. Applying the same reasoning to the integral dilates of P, we see that the Ehrhart polynomial is an invariant under unimodular transformations of P. Thus we assume henceforth, without loss of generality, that the matrix whose columns are the vertices of P is lower-triangular.

Now let K denote the convex cone in ℝ^{n+1} generated by a copy of P placed on the hyperplane ℝ^{n} × {1} ⊂ ℝ^{n+1}. K consists of rays through the origin of ℝ^{n+1} that intersect the hyperplane x_{n+1} = 1 at points of the form (x, 1), where x ∈ P. 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:

M = (\begin{matrix}a_{1,1} \\ a_{2,1} & a_{2,2} \\ ⋮ & ⋮ \\ a_{n,1} & a_{n,2} & ⋯ & a_{n,n} \\ 1 & 1 & ⋯ & 1 & 1 \end{matrix}) .

The Fourier-Laplace transform of the characteristic function of the set K is defined by the integral formula

χ̂_{K}(ζ) = ∫_{x∈K} exp(−2πi⟨ζ, x⟩) dx

that incorporates the complex frequency vector ζ = ξ + iη ∈ ℝ^{n+1} + iℝ^{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 χ_{K} is just the Fourier transform ∫_{x} f_{η}(x) exp(−2πi⟨x, ξ⟩) dx of the function

f_{η}(x) = χ_{K}(x) exp(2π⟨x, η⟩),

which is absolutely integrable if η lies in the polar cone K^{∗}. It is traditional to denote both transforms by the same symbol: ˆ .

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

Lemma 1. For every complex frequency vector ζ satisfying Im ζ ∈ 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:

χ̂_{K}(ζ) = | det M| ∏_{k=1}^{n+1} \frac{1}{⟨2πiζ, M_{k}⟩}.

□

Taking ζ = (ξ_{1}, ξ_{2}, …, ξ_{n+1}) − i(0, 0, …, s) ∈ ℤ^{n+1} + iK^{∗} we see that Lemma 1 gives the explicit formula

f̂_{sη_{0}} (ξ) = \frac{| det M|}{(2π)^{n+1}} ∏_{k=1}^{n+1} \frac{1}{s + il_{k}(ξ)}, (2)

where the linear forms l_{k}(ξ) = ⟨ξ, M_{k}⟩ are determined by the columns of M. Note that since M is a lower-triangular matrix, the linear form l_{k}(0, 0, …, ξ_{k}, …, ξ_{n+1}) depends only on the last n + 1 − k coordinates of ξ.

We would like to use the Poisson summation formula to sum expression (2) over all integral frequency vectors ξ = (ξ_{1}, …, ξ_{n+1}) ∈ ℤ^{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_{η}(x) by convolution. The mollifier will be taken to be an approximate identity ϕ_{ϵ}(x) constructed from a dilated version of f_{η_{0}}(x), normalized to have mass one. This normalization condition is equivalent to requiring that ϕ̂_{ϵ}(0) = 1. For each real ϵ ≠ 0 we therefore multiply (2) by

ϕ̂_{ϵ}(ξ) = \frac{f̂_{η_{0}}(ϵξ)}{f̂_{η_{0}}(0)} = ∏_{k=1}^{n+1} \frac{1}{(1 + iϵl_{k}(ξ))}

to get

{ \atop (f_{sη} ∗ ϕ_{ϵ})}(ξ) = \frac{| det M|}{(2π)^{n+1}} ∏_{k=1}^{n+1} \frac{1}{(s + il_{k}(ξ))(1 + iϵl_{k}(ξ))}. (3)

Lemma 2. Suppose that ϵ ≠ 0 and η ∈ K^{∗}.

(i) The Poisson summation formula holds for f_{η} ∗ ϕ_{ϵ} in the sense that the following two sums are both absolutely convergent representations of a common expression:

𝔊_{ϵ}(K, η) := ∑_{x∈ℤ^{n+1}}(f_{η} ∗ ϕ_{ϵ})(x) = ∑_{ξ∈ℤ^{n+1}} f̂_{η}(ξ)ϕ̂_{ϵ}(ξ).

(ii) The preceding expression, 𝔊_{ϵ}(K, η), possesses one-sided limits as ϵ → 0^{±}; and these one-sided limits are the discrete Laplace transforms of the characteristic functions of the interior and closure of K:

(ii.a) lim_{ϵ→0^{+}} 𝔊_{ϵ}(K, η) = ∑_{x∈ℤ^{n+1}} χ_{K^{int}}(x) exp(2π⟨x, η⟩) = 𝔊(K^{int}, η);

(ii.b) lim_{ϵ→0^{−}} 𝔊_{ϵ}(K, η) = ∑_{x∈ℤ^{n+1}} χ_{K^{clos}}(x) exp(2π⟨x, η⟩) = 𝔊(K^{clos}, η).

□

In view of Lemma 1 it is natural to investigate the sum ∑_{ξ∈ℤ^{n+1}} f̂_{η}(ξ)ϕ̂_{ϵ}(ξ) using (3). To describe the main result let G be the finite abelian group (ℤ/p_{1}ℤ) × ⋯ × (ℤ/p_{n}ℤ), where p_{k} = ∏_{i<k} a_{i,i} for k ≤ n and p_{n+1} = p_{n}. For each group element r = (r_{1}, …, r_{n}) ∈ G, let m_{k}(r) = l_{k}(0, r_{1}, …, r_{n}) denote the linear form that l_{k}(ξ) = ⟨ξ, M_{k}⟩ induces on the group G.

Theorem.

∑_{t=0}^{∞} L(P^{int}, t)e^{−2πst} =\frac{1}{2^{n+1}} \frac{1}{|G|} ∑_{r∈G} ∏_{k=1}^{n+1} (1 + coth \frac{π}{p_{k}} (s + im_{k}(r)));

1 + ∑_{t=1}^{∞} L(P^{clos}, t)e^{−2πst} =\frac{1}{2^{n+1}} \frac{1}{|G|} ∑_{r∈G} ∏_{k=1}^{n+1} (−1 + coth \frac{π}{p_{k}} (s + im_{k}(r))) .
□

Corollary. L(P^{int}, t) is a polynomial in t ∈ ℕ, and if L(P^{int}, t) = ∑_{i=0}^{n} c_{i}t^{i}, then c_{m} is the coefficient of s^{−m−1} in the Laurent expansion at s = 0 of

\frac{π^{m+1}}{m!2^{n−m}} \frac{1}{|G|} ∑_{r∈G} ∏_{k=1}^{n+1} (1 + coth \frac{π}{p_{k}} (s + im_{k}(r))) .

□

We remark that for three-dimensional polytopes P, the only coefficient of the Ehrhart polynomial L(P, t) = c_{3}t^{3}+c_{2}t^{2}+c_{1}t+1 that is difficult to determine is the codimension two coefficient c_{1} (see [12]). This coefficient can be found by solving for the coefficient of s^{−2} in the Laurent expansion of the product of cotangents given by the corollary. Consider for example the “Mordell-Pommersheim” Tetrahedron, whose vertices are (0, 0, 0), P = (a, 0, 0), Q = (0, b, 0), and R = (0, 0, c); where a, b, c ∈ ℕ [8], [12]. There is no loss of generality in asssuming that gcd(a, b, c) = 1. Define A = gcd(b, c), B = gcd(a, c), C = gcd(a, b), and d = ABC.

We recall that the classical Dedekind sum 𝔰(q, p) can be defined for gcd(p, q) = 1 in terms of cotangent expansions [5] by

𝔰(q, p) = \frac{1}{4p} ∑_{m=1}^{p−1} cot \frac{πm}{p} cot \frac{πmq}{p} .

Using the previous corollary, it is easy to recover Theorem 5 of [12]:

c_{1} = \frac{1}{4} (A + B + C + a + b + c) + \frac{1}{12} (\frac{bc}{a} + \frac{ac}{b} + \frac{ab}{c} + \frac{d^{2}}{abc})

− A 𝔰 (\frac{bc}{d}, \frac{aA}{d}) − B 𝔰 (\frac{ac}{d}, \frac{bB}{d} ) − C 𝔰 (\frac{ab}{d}, \frac{cC}{d} ) .

As other corollaries of the main theorem, one quickly recovers the Ehrhart-MacDonald Reciprocity Law [4], [7], [16] and higher dimensional Dedekind sums appearing in Hirzebruch’s and Zagier’s work [5], [19].

References

1. M. Brion, Points entiere dans les polyèdres convexes, Ann. Sci. Ecole Nor. Sup. (4^{c}) 21 (1988), 653–663. MR 90d:52020

2. S. E. Cappell and J. L. Shaneson, Genera of algebraic varieties and counting of lattice points, Bulletin of the AMS (Jan. 1994), 62–69. MR 94f:14018 3. V. I. Danilov, The geometry of toric varieties, Russian Math. Surveys 33 (1978), 97–154. MR

80g:14001

4. E. Ehrhart, Sur un problème de géométrie diophantienne linéaire II, J. Reine Angew. Math. 227 (1967), 25–49. MR 36:105

5. F. Hirzebruch and D. Zagier, The Atiyah-Singer index theorem and elementary number theory, Publish or Perish Press, Boston, MA, 1974. MR 58:31291

6. J. M. Kantor and A. Khovanskii, Une application du Théorème de Riemann-Roch combinatoire au polynôme d’Ehrhart des polytopes entier de ℝ^{d}, C. R. Acad. Sci. Paris, Series I 317 (1993), 501–507. MR 94k:52018

7. I. G. MacDonald, Polynomials associated with finite cell complexes, J. London Math. Soc. (2) 4 (1971), 181–192. MR 45:7594

8. L. J. Mordell, Lattice points in a tetrahedron and generalized Dedekind sums, J. Indian Math. 15 (1951), 41–46. MR 13:322b

9. M. Newman, Integral matrices, Academic Press, New York, 1972. MR 49:5038

10. G. Pick, Geometrisches zur Zahlenlehre, Sitzungber. Lotos (Prague) 19 (1899), 311–319.

11. M. A. Pinsky, Pointwise Fourier inversion in several variables, Notices of the AMS 42 (1995), 330–334. MR 96b:42010

12. J. Pommersheim, Toric varieties, lattice points, and Dedekind sums, Math. Annalen 295, 1 (1993), 1–24. MR 94c:14043

13. B. Randol, On the Fourier transform of the indicator function of a planar set, Trans. of the AMS (1969), 271–278. MR 40:4678a

14. C. L. Siegel, Über Gitterpunkte in konvexen Körpern und ein damit zusammenhängendes Extremalproblem, Acta Math. 65 (1935), 307–323.

15. E. Stein and G. Weiss, Fourier analysis on Euclidean spaces, Princeton University Press, Princeton, NJ, 1971. MR 46:4102

16. R. Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194–253. MR 54:111

17. D. Gabai, Genera of the arborescent links, and W. Thurston, A norm for the homology of 3-manifolds, Memoirs of the AMS 59 (1986). MR 87h:57010; MR 88h:57014

18. Y.-J. Xu and S.S.-T. Yau, A sharp estimate of the number of integral points in a tetrahedron, J. Reine Angew. Math. 423 (1992), 119–219. MR 93d:11067

19. D. Zagier, Higher dimensional Dedekind sums, Math. Ann. 202 (1973), 149–172. MR 50:9801

Department of Mathematics, University of Northern Colorado, Greeley, Colorado 80639

E-mail address: rdiaz@bentley.univnorthco.edu

Department of Mathematics, UCSD 9500 Gilman Drive, La Jolla, CA 92093-0112

E-mail address: srobins@ucsd.edu