COEFFICIENTS AND ROOTS OF EHRHART POLYNOMIALS

M. BECK, J. A. DE LOERA, M. DEVELIN, J. PFEIFLE, AND R. P. STANLEY

Abstract. The Ehrhart polynomial of a convex lattice polytope counts integer points in integral dilates of the polytope. We present new linear inequalities satisfied by the coefficients of Ehrhart polynomials and relate them to known inequalities. We also investigate the roots of Ehrhart polynomials. We prove that for fixed d, there exists a bounded region of ℂ containing all roots of Ehrhart polynomials of d-polytopes, and that all real roots of these polynomials lie in [−d, ⌊d/2⌋). In contrast, we prove that when the dimension d is not fixed the positive real roots can be arbitrarily large. We finish with an experimental investigation of the Ehrhart polynomials of cyclic polytopes and 0/1-polytopes.

1. Introduction

In this article, a lattice polytope P ⊂ ℝ^{d} is a convex polytope whose vertices have integral coordinates. (For all notions regarding convex polytopes we refer to [25].) In 1967 Eugène Ehrhart proved that the function which counts the lattice points in the n-fold dilated copy of P,

i_{P} : ℕ → ℕ, i_{P} (n) = # (nP ∩ ℤ^{d}) ,

is a polynomial in n (see [6, 7] and the description in [8]). In particular, i_{P} can be naturally extended to all complex numbers n. In this paper we investigate linear inequalities satisfied by the coefficients of Ehrhart polynomials and the distribution of the roots of Ehrhart polynomials in the complex plane.

The coefficients of Ehrhart polynomials are very special. For example, it is well known that the leading term of i_{P} (n) equals the volume of P, normalized with respect to the sublattice ℤ^{d} ∩ aff(P). The second term of i_{P} (t) equals half the surface area of P normalized with respect to the sublattice on each facet of P, and the constant term equals 1. Moreover, the function i_{P}^{∘} (n) counting the number of interior lattice points in nP satisfies the reciprocity law i_{P} (−n) = (−1)^{dim P} i_{P}^{∘} (n) [8, 14, 18].

Our first contribution is to establish new linear relations satisfied by the coefficients of all Ehrhart polynomials. This is a continuation of the pioneering work of Stanley, Betke & McMullen, and Hibi [19, 21, 1, 11], who established several families of linear inequalities for the coefficients (see Theorems 3.1 and 3.4). If we think of an Ehrhart polynomial i_{P} (n) = c_{d}x^{d} + c_{d−1}x^{d−1} + ⋯ + c_{1}x + 1 as a point in d-space, given by the coefficient vector (c_{d}, c_{d−1}, …, c_{1}), their results imply that the Ehrhart polynomials of all d-polytopes lie in a certain polyhedral complex. Betke and McMullen raised the issue [1, page 262] of whether other linear inequalities are possible. We were indeed able to find such new inequalities in the form of bounds for the k-th difference of the Ehrhart polynomial i_{P} (n). These are defined recursively via

Δi_{P} (n) = i_{P} (n + 1) − i_{P} (n)

and

Δ^{k}i_{P} (n) = Δ (Δ^{k−1}i_{P} (n)) for k ≥ 1 and Δ^{0}i_{P} (n) = i_{P} (n).

Our first result (proved in Section 3) is as follows.

Theorem 1.1. If the lattice d-polytope P ⊂ ℝ^{d} has Ehrhart polynomial i_{P} (n) = c_{d} n^{d} +⋯+ c_{0}, then

\binom{d}{ℓ}Δ^{k}i_{P} (0) ≤ \binom{d}{k}Δ^{ℓ}i_{P} (0) for 0 ≤ k < ℓ ≤ d.

In particular (put k = 0 resp. ℓ = d),

\binom{d}{k} ≤ Δ^{k}i_{P} (0) ≤ \binom{d}{k}d! c_{d} for 0 ≤ k ≤ d.

In Section 3 we give a proof of Theorem 1.1 using the language of rational generating functions as established in [1, 22], and make a summary of known linear constraints and their strength.

The relation between the coefficients and the roots of polynomials, via elementary symmetric functions, suggests that once we understand the size of the coefficients of Ehrhart polynomials we could predict the distribution of their roots in the complex plane. The second contribution of this paper is a general study of the roots of Ehrhart polynomials.

There is clearly something special about the roots of Ehrhart polynomials. Take for instance the integer roots: Since a lattice polytope always contains some integer points (namely, its vertices), all integer roots of its Ehrhart polynomial are negative. More precisely, by the reciprocity law, the integer roots of an Ehrhart polynomial are those −n for which the open polytope nP^{∘} contains no lattice point. For instance, the Ehrhart polynomial \binom{n+d}{d} of the standard simplex in ℝ^{d} (with vertices at the origin and the unit vectors on the coordinate axes) has integer roots at n = −d, −d + 1, …, −1.

The roots of the Ehrhart polynomial of the cross polytope

O^{d} = {(x_{1}, …, x_{d}) ∈ ℝ^{d} : |x_{1}| + ⋯ + |x_{d}| ≤ 1} ,

also exhibit special behavior: Bump et al. [3] and Rodriguez [16] proved that the zeros of i_{O^{d}} all have real parts equal to −1/2.

Using classical results from complex analysis and the linear inequalities of Theorem 3.5, we derive in Section 4 the following theorems:

Theorem 1.2. (a) The roots of Ehrhart polynomials of lattice d-polytopes are bounded

in norm by 1 + (d + 1)! .

(b) All real roots of Ehrhart polynomials of d-dimensional lattice polytopes lie in the half-open interval [−d, ⌊d/2⌋).

The upper bound we present in Theorem 1.2 (b) is not tight. For example, in Proposition 4.7, we give a very short self-contained proof of the fact that Ehrhart polynomials for polytopes of dimension d ≤ 4 have real roots in the interval [0, 1). In contrast with the above theorem we can also prove the following result.

Theorem 1.3. For any positive real number t there exist an Ehrhart polynomial of sufficiently large degree with a real root strictly larger than t. In fact, for every d there is a d-dimensional 0/1-polytope whose Ehrhart polynomial has a real zero α_{d} such that lim_{d→∞} α_{d}/d = 1/(2πe) = 0.0585 · · ·.

Our third contribution is an experimental study of the roots and coefficients of Ehrhart polynomials of concrete families of lattice polytopes. Our investigations and conjectures are supported by computer experimentation using LattE [4, 5] and polymake [12]. For the complex roots, we offer the following conjecture, based on experimental data.

Conjecture 1.4. All roots α of Ehrhart polynomials of lattice d-polytopes satisfy −d ≤ Re α ≤ d − 1.

We also computed the Ehrhart polynomials of all 0/1-polytopes of dimension less than or equal to 4 and for many cyclic polytopes:

Conjecture 1.5. For the cyclic polytope C(n, d) realized with integral vertices on the moment curve ν_{d}(t) := (t, t^{2}, …, t^{d}),

i_{C(n,d)}(m) = vol(C(n, d)) m^{d} + i_{C(n,d−1)}(m).

Equivalently,

i_{C(n,d)}(m) = ∑_{k=0}^{d} vol_{k}(C(n, k)) m^{k}.

We have experimentally verified this conjecture in many cases.

2. An appetizer: dimension two

Since Ehrhart polynomials of lattice 1-polytopes (segments) are of the form ℓn + 1, where ℓ is the length of the segment, we know everything about their coefficients and roots: the set of roots of these polynomials is {−1/ℓ : ℓ ≥ 1} ⊂ [−1, 0).

The first interesting case is dimension d = 2. Pick’s Theorem tells us that the Ehrhart polynomial of a lattice 2-polytope P is

i_{P} (n) = c_{2} n^{2} + c_{1} n + 1 ,

where c_{2} is the area of P and c_{1} equals 1/2 times the number of boundary integer points of P. In 1976, Scott established the following linear relations. Two polytopes are unimodularly equivalent if there is a function which maps one to the other and which preserves the integer lattice.

Theorem 2.1. [17] Let i_{P} (n) = c_{2} n^{2} + c_{1} n + 1 be the Ehrhart polynomial of the lattice 2-polytope P. If P contains an interior integer point, and P is not unimodularly equivalent to conv {(0, 0), (3, 0), (0, 3)}, then

c_{1} ≤ \frac{1}{2}c_{2} + 2 .

By Pick’s Theorem, for 2-polytopes with no interior lattice points, we have c_{1} = c_{2} + 1. For P = conv {(0, 0), (3, 0), (0, 3)}, we obtain i_{P} (n) = 9/2 n^{2} + 9/2 n + 1.

It is interesting to ask which degree-2 polynomials can possibly be Ehrhart polynomials. Since the constant term has to be 1, we can think of such a polynomial as a point (c_{2}, c_{1}) in the plane. From the geometry of lattice 2-polytopes, we know such an Ehrhart polynomial must have half-integral coordinates. Aside from Scott’s inequality, we can trivially bound c_{1} ≥ 3/2, since every lattice 2-polytope has at least 3 integral points, namely its vertices. From these considerations, we arrive at Figure 1, which shows regions of possible Ehrhart polynomials of 2-polytopes.

Depicted are (parts of) three lines:

(i) c_{1} = 3/2 (ii) c_{1} = c_{2}/2 + 2 (iii) c_{1} = c_{2} + 1 Figure 1. Regions in which Ehrhart polynomials of lattice 2-polytopes lie. It consists of 3 half lines, an open region (only points with half-integral coordinates are possible), plus an exceptional point.

and the point (c_{2}, c_{1}) = (9/2, 9/2). The ray (i) shows the lower bound c_{1} ≥ 3/2. This is a sharp lower bound, in the sense that we can have polygons with exactly three boundary integer points but arbitrarily large area. The ray (ii) is Scott’s bound, and the point (c_{2}, c_{1}) = (9/2, 9/2) corresponds to the “exceptional” polytope conv {(0, 0), (3, 0), (0, 3)} in Theorem 2.1. The rectangles conv {(0, 0), (2, 0), (2, x), (0, x)}, where x is a positive integer, show that there is a point on (ii) for every half integer. Finally, (iii) corresponds to 2-polytopes which contain no interior lattice point. There is a point on (iii) for every half integer, corresponding to the triangles conv {(0, 0), (1, 0), (0, x)} for a positive integer x. The rays (i) and (iii) meet in the point (1/2, 3/2), which corresponds to the standard triangle conv {(0, 0), (1, 0), (0, 1)}. So the polyhedral complex containing all Ehrhart vectors consists of the polyhedron bounded by (i), (ii), and (iii) (shaded in Figure 1), plus the ray (iii), plus the extra point (c_{2}, c_{1}) = (9/2, 9/2). In fact, only points with half-integral coordinates inside the complex are valid Ehrhart vectors. From these constraints, we can locate possible roots of Ehrhart polynomials of lattice 2-polytope fairly precisely.

Theorem 2.2. The roots of the Ehrhart polynomial of any lattice 2-polytope are contained in

\{−2, −1, −\frac{2}{3}\} ∪ \{x + iy ∈ ℂ : −\frac{1}{2} ≤ x < 0, |y| ≤ \frac{\sqrt{15}}{6}\} .

Proof. We consider three cases, according to Scott’s Theorem 2.1. First, if the lattice 2polytope P contains no interior lattice point then i_{P} (n) = An^{2} + (A + 1)n + 1 (by Pick’s Theorem), where A denotes the area of P. The roots of i_{P} are at −1 and −1/A. Note that A is half integral.

The second case is the “exceptional” polytope P = conv {(0, 0), (3, 0), (0, 3)} whose Ehrhart polynomial i_{P} (n) = 9/2n^{2} + 9/2n + 1 has roots −2/3 and −1/2.

This leaves, as the last case, 2-polytopes which contain an interior lattice point and which are not unimodularly equivalent to conv {(0, 0), (3, 0), (0, 3)}. The corresponding Ehrhart polynomials i_{P} (n) = c_{2}n^{2} + c_{1}n + 1 satisfy the Scott inequality c_{1} ≤ c_{2}/2 + 2. Note that (because P has an interior lattice point) the area of P satisfies c_{2} ≥ 3/2. We have two possibilities:

(A) The discriminant c_{1}^{2} − 4c_{2} is negative. Then the real part of a root of i_{P} equals −\frac{c_{1}}{2c_{2}} (which is negative). By Pick’s Theorem c_{1} = c_{2} − I + 1 where I is the number of interior lattice points, that is, −\frac{c_{1}}{2c_{2}} = −\frac{1}{2} − \frac{1−I}{2c_{2}} . For fixed area c_{2}, this fraction is minimized when I is smallest possible, that is I = 1. The imaginary part of a root of i_{P} is plus or minus

\frac{1}{2c_{2}} \sqrt{4c_{2} − c_{1}^{2}} ≤ \frac{1}{2c_{2}} \sqrt{4c_{2} − \frac{9}{4}} = \sqrt{\frac{1}{c_{2}} − (\frac{3}{4c_{2}} )^{2}} ;

here we used c_{1} ≥ 3/2. As a function in c_{2}, this upper bound is decreasing for c_{2} ≥ 1. Since c_{2} ≥ 3/2, we obtain as an upper bound for the magnitude of the imaginary part of a root

\sqrt{\frac{2}{3} − (\frac{1}{2})^{2}} = \frac{\sqrt{15}}{6} .

(B) The discriminant c_{1}^{2} − 4c_{2} is nonnegative. Then the smaller root of i_{P} is

−\frac{c_{1}}{2c_{2}} − \frac{1}{2c_{2}} \sqrt{c_{1}^{2} − 4c_{2}} ≥ −\frac{1}{4} − \frac{1}{c_{2}} − \frac{1}{2c_{2}} \sqrt{(\frac{c_{2}}{2} + 2)^{2} − 4c_{2}}
= −\frac{1}{4} − \frac{1}{c_{2}} − \frac{1}{2c_{2}} (\frac{c_{2}}{2} − 2) = −\frac{1}{2}

(Note that in this case c_{2} ≥ 4.)

Finally, the larger root is negative, since all the coefficients of i_{P} are positive. □

3. Linear inequalities for the coefficients of Ehrhart polynomials

In this section, we prove Theorem 1.1, which bounds the ratio of the k-th and ℓ-th differences of any Ehrhart polynomial solely in terms of d, k, and ℓ. It is perhaps worth observing that most of our arguments are valid for a somewhat larger class of polynomials. To describe this class, we define the generating function of the polynomial p as

S_{p}(x) = ∑_{n≥0} p(n) x^{n} .

It is well known (see, e.g., [22, Chapter 4]) that, if p is of degree d, then S_{p} is a rational function of the form

(1)  S_{p}(x) = \frac{f(x)}{(1 − x)^{d+1}} ,

where f is a polynomial of degree at most d. Most of our results hold for polynomials p for which the numerator of S_{p} has only nonnegative coefficients. Ehrhart polynomials are a particular case, as seen from the following theorem of Stanley.

Theorem 3.1. [19, Theorem 2.1] Suppose P is a convex lattice polytope. Then the generating function ∑_{n≥0} i_{P} (n) x^{n} can be written in the form of (1), where f(x) is a polynomial of degree at most d with nonnegative integer coefficients.

Another well-known (and easy-to-prove) fact about rational generating functions (see, e.g., [22, Chapter 4]) is the following.

Lemma 3.2. Suppose that p ∈ ℝ[n] is a polynomial of degree d with generating function S_{p}(x) = (a_{d}x^{d} + ⋯ + a_{1}x + a_{0})/(1 − x)^{d+1}. Then p can be recovered as

(2)  p(n) = ∑_{j=0}^{d} a_{j}\binom{d + n − j}{d} .

More generally, we have the identity

(3)  Δ^{k}p(n) = ∑_{j=0}^{d} a_{j}\binom{d + n − j}{d − k}  for k ≥ 0.

Proof. Equation (2) follows from expanding 1/(1 − x)^{d+1} into a binomial series. For (3), we proceed by induction on k. For k = 0, the statement is (2), while for k ≥ 1 we have by the induction hypothesis

Δ^{k}p(n) = Δ^{k−1}p(n + 1) − Δ^{k−1}p(n)

= ∑_{j=0}^{d} a_{j} (\binom{d + n + 1 − j}{d − k + 1} − \binom{d + n − j}{d − k + 1})

= ∑_{j=0}^{d} a_{j}\binom{d + n − j}{d − k} .

□

Combining Theorem 3.1 and Lemma 3.2 immediately yields the following fact.

Corollary 3.3. For any lattice polytope P and k ≥ 0, we have Δ^{k} i_{P} (0) ≥ 0.

Proof. This follows because those binomial coefficients in the final expression for Δ^{k}p(n) are either positive or zero. □

Proof of Theorem 1.1. We will use the falling-power notation d\underline{j} = d(d − 1) ⋯ (d − j + 1), along with the obvious relation k\underline{j} < ℓ\underline{j} for j ≤ k < ℓ, and the identity

\binom{d − j}{d − k} = \binom{d}{k}\frac{k\underline{j}}{d\underline{j}} .

The statement now follows from Lemma 3.2 (3) by

\binom{d}{ℓ}\binom{d − j}{d − k} = \binom{d}{ℓ}\binom{d}{k}\frac{k\underline{j}}{d\underline{j}} < \binom{d}{k}\binom{d}{ℓ} \frac{ℓ\underline{j}}{d\underline{j}} = \binom{d}{k}\binom{d − j}{d − ℓ}.

□

Theorem 1.1 is not the first set of linear inequalities on coefficient vectors of Ehrhart polynomials. Indeed, in 1984, Betke and McMullen [1, Theorem 6] obtained the following inequalities.

Theorem 3.4. Let P be a lattice d-polytope whose Ehrhart polynomial is ∑_{i=0}^{d} c_{i}n^{i}. Then

c_{r} ≤ (−1)^{d−r}s(d, r) c_{d} + (−1)^{d−r−1} \frac{s(d, r + 1)}{(d − 1)!} for r = 1, 2, …, d − 1,

where s(k, j) denote the Stirling numbers of the first kind. □

In that paper, Betke and McMullen sent out a challenge to the community to discover new inequalities for these coefficient vectors. The following theorem sums up the current state of affairs.

Theorem 3.5. Let P be a d-dimensional lattice polytope, with Ehrhart polynomial i_{P} (n) = ∑_{i=0}^{d} c_{i}n^{i} = ∑_{i=0}^{d} a_{i}\binom{n+d−i}{d}. Then the following inequalities are valid for 0 ≤ k < ℓ ≤ d and 0 ≤ i ≤ d:

(4)  c_{r} ≤ (−1)^{d−r}s(d, r) c_{d} + (−1)^{d−r−1} \frac{s(d, r + 1)}{(d − 1)!},

\begin{aligned}\binom{d}{k}Δ^{ℓ} i_{P} (0) & ≥ & \binom{d}{ℓ}Δ^{k} i_{P} (0), & (5) \\ \binom{d + 1}{2} c_{d} & ≥ & c_{d−1}, & (6) \\ i_{P} (1) & ≥ & d + 1, & (7) \\ Δ^{k} i_{P} (0) & ≥ & \binom{d}{k}, & (8) \end{aligned}  \begin{aligned}c_{d} & ≥ & c_{0}/d!, & (9) \\ c_{d−1} & ≥ & c_{0} \frac{d + 1}{2(d − 1)!}, & (10) \\ ∑_{i=0}^{d}(−1)^{d−i}c_{i} & ≥ & 0, & (11) \\ a_{i} & ≥ & 0. & (12) \end{aligned}

Moreover,

(13) a_{d} + a_{d−1} + ⋯ + a_{d−i} ≤ a_{0} + a_{1} + ⋯ + a_{i} + a_{i+1} for all 0 ≤ i ≤ ⌊(d − 1)/2⌋ .

Whenever a_{s} ≠ 0 but a_{s+1} = ⋯ = a_{d} = 0, then

(14)  a_{0} + a_{1} + ⋯ + a_{i} ≤ a_{s} + a_{s−1} + ⋯ + a_{s−i}  for all 0 ≤ i ≤ s;

finally, if a_{d} ≠ 0, then

(15)  a_{1} ≤ a_{i}  for all 2 ≤ i < d .

Proof. The inequalities (4) and (5) are the contents of Theorems 3.4 and 1.1; while (6), (7), and (8) are the special cases (k, ℓ) = (d − 1, d), (k, ℓ) = (0, 1), and k = 0, respectively.

(9) and (10) say that the volume and the normalized surface are at least as big as for a primitive simplex. Inequality (11) follows from Ehrhart reciprocity. Inequality (12) is the statement of Theorem 3.1. Incidentally, (9) also follows from (8), and (11) follows from (12), both by specializing to i = d. Inequality (14) was proved by Stanley [21], and inequalities (13) and (15) by Hibi [11, 10]. □

It is illuminating to compare these inequalities with each other. Since inequality (12) was used to prove Theorem 3.4 (by Betke and McMullen) and Theorem 1.1, it seems stronger than the other inequalities. Indeed, the only inequality among (4)–(12) which does not follow from (12) is (10). Experimental data for small d shows that neither (4) nor (5) imply the other.

The set of linear inequalities of Theorem 3.5 describes an unbounded complex of half-open polyhedra in ℝ^{d+1} inside which all coefficient vectors of Ehrhart polynomials live. From this, we obtain a bounded complex Q^{d} by cutting with the normalizing hyperplane c_{d} = 1. By (14) each constraint a_{s} ≠ 0, a_{s+1} = ⋯ = a_{d} = 0 for s = 1, 2, …, d defines a half-open polytope E_{s} ∈ Q^{d} of dimension s that is missing one facet; E_{0} is a single point.

Here are some particular cases: The bounded complex Q^{3} consists of one half-open sdimensional simplex for each s = 0, 1, 2, 3 (Figure 2), and the half-open 3- and 4-dimensional polytopes of Q^{4} are shown in Figure 3.

Figure 2. The complex Q^{3} of half-open polytopes, inside which the possible Ehrhart coefficients of all 3-dimensional polytopes lie. The facets of the tetrahedron corresponding to a_{3} ≠ 0 are a_{0} ≥ 0, c_{2} ≥ 1, (14) and (15); those of the triangle corresponding to a_{3} = 0, a_{2} ≠ 0 are a_{0}, a_{1} ≥ 0 and (14); and those of the segment a_{2} = a_{3} = 0, a_{1} ≠ 0 are a_{0} ≥ 0 and (14).

An important question about any linear inequality is whether or not it defines a facet of Q^{d}. We rephrase Betke and McMullen’s question [1]:

Figure 3. The 4-dimensional (top) and 3-dimensional (bottom) member of the complex Q^{4}. The facets of the 4-dimensional polytope are a_{0} ≥ 0, c_{3} ≥ 5/12, (14) for i = 0, (13) for i = 0, 1, and (15) for i = 2, 3; those of the 3dimensional one corresponding to a_{4} = 0 but a_{3} ≠ 0 are a_{0}, a_{1} ≥ 0, c_{3} ≥ 5/12,

(13) for i = 1, (14) for i = 1, and (15) for i = 2; etc.

Problem. Are there other linear inequalities for the coefficients of an Ehrhart polynomial aside from those in Theorem 3.5? Do they define facets of the polyhedral complex inside which all coefficient vectors of Ehrhart polynomials live?

4. The roots of Ehrhart polynomials

When one has a family of polynomials, a natural thing to look at are its roots. What is the general behavior of complex roots of Ehrhart polynomials? As a consequence of the inequalities on its coefficients, we give bounds on the norm of roots of any Ehrhart polynomial in dimension d. The basis \{\binom{d+n−j}{d} : 0 ≤ j ≤ d\} of the vector space of polynomials of degree d turns out to be much more natural than the basis {n^{i} : 0 ≤ i ≤ d} for deriving bounds on the roots of Ehrhart polynomials i_{P} (n) = ∑_{i=0}^{d} a_{i}\binom{n+d−i}{d} = ∑_{i=0}^{d} c_{i}n^{i}. Also, recall the following classical result of Cauchy (see, for example, [15, Chapter VII]).

Lemma 4.1. The roots of the polynomial p(n) = c_{d}n^{d} + c_{d−1}n^{d−1} + ⋯ + c_{0} lie in the open disc

\{z ∈ ℂ : |z| < 1 + max_{0≤j≤d} |\frac{c_{j}}{c_{d}} |\} .

□

Now we study roots of Ehrhart polynomials in general dimension. We first give an easy proof bounding the norm of all roots.

Proof of Theorem 1.2(a). By Lemma 4.1 and Theorem 3.4, the maximal norm of the roots of i_{P} is bounded by

1 + max_{0≤j≤d} |\frac{c_{j}}{c_{d}} | ≤ 1 + max_{0≤j≤d} |(−1)^{d−j}s(d, j) + (−1)^{d−j−1} \frac{s(d, j + 1)}{(d − 1)! c_{d}} |
≤ 1 + d! + d!d = 1 + (d + 1)! .

Here we have used the estimate s(d, j) ≤ |s(d, j)| ≤ d! and the fact that c_{d} ≥ 1/d!. □

While using crude estimates gives us a bound of 1+(d+1)!, which makes the main point that there exists a bound dependent only on d, the actual bound on the roots can be improved greatly for specific values of d. First of all, for small d, we can compute the inequalities exactly; here the inequalities from Theorem 1.1 are used along with the Betke-McMullen inequalities. This gives appropriate bounds on the ratios of the coefficients of the Ehrhart polynomial. Second of all, Lemma 4.1 is not the best tool to use for specific cases, since calculating the inequalities for small d yields much lower bounds for c_{i}/c_{d} when i is large. Instead, we use the following proposition.

Proposition 4.2 (Theorem 27.1 [15]). Let p(n) = c_{d}n^{d} +c_{d−1}n^{d−1} +⋯+c_{0} be a polynomial. Then the maximal value of the norm of a root of p(n) is the value of the maximal root of p′(n) = |c_{d}|n^{d} − |c_{d−1}|n^{d−1} − |c_{d−2}|n^{d−2} − ⋯ − |c_{0}|. □

We use this and the exact calculation of the inequalities in question to obtain the following tighter bounds on the roots of Ehrhart polynomials of d-polytopes.

\begin{matrix}d & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ bound & 3.6 & 8.5 & 15.8 & 25.7 & 38.3 & 53.5 & 71.4 & 92.0 \end{matrix}

The bound appears to grow roughly quadratically. We suspect that there is a bound for the roots of Ehrhart polynomials of d-polytopes which is polynomial in d. For real roots this is certainly the case; we prove next that all real roots of Ehrhart polynomials of d-polytopes lie in the interval [−d, ⌊d/2⌋). For this, we will use the following well-known bound.

Lemma 4.3. (Newton Bound) Let f ∈ ℝ[n] be a polynomial of degree d and B ∈ ℝ be such that all derivatives of f are positive at B: f^{(ℓ)}(B) > 0 for ℓ = 0, 1, …, d. Then all real roots of f are contained in (−∞, B). □

Proof of Theorem 1.2(b). The lower bound follows from Theorem 3.1 and the simple observation that for (real numbers) n < −d the binomial coefficients in

i_{P} (n) = ∑_{i=0}^{d} a_{i}\binom{n + d − i}{d}

are all positive or all negative, depending on the parity of d.

As for the upper bound, let B = ⌊d/2⌋. We now show that α < B for any real root α of i_{P} (n). For this, we will make use of the fact that the second highest coefficient of any Ehrhart polynomial measures half the normalized surface area. This coefficient reads

c_{d−1} = \frac{1}{(d − 1)!} ∑_{i=0}^{d} a_{i} (d − 2i + 1)

when expressed in terms of the a_{i}’s, so that the following inequality is valid:

(16)  (d − 1)! c_{d−1} = ∑_{i=0}^{d} a_{i} (d − 2i + 1) > 0 .

Note that the coefficient s(i) = d − 2i + 1 of a_{i} in (16) is positive for 0 ≤ i ≤ B and nonpositive for B + 1 ≤ i ≤ d. We now express the ℓ-th derivative of i_{P} evaluated at n = B as i_{P}^{(ℓ)}(B) = (ℓ!/d!) ∑_{i=0}^{d} a_{i} g_{i}(B, ℓ), and claim that for 0 ≤ ℓ ≤ d, there exists a λ(ℓ) > 0 with

g_{i}(B, ℓ) > λ(ℓ) s(i) for all 0 ≤ i ≤ d.

This claim is the statement of Lemma 4.5 below. The proof of Theorem 1.2(b) now follows from this relation, inequality (16), a_{0} = 1 and a_{i} ≥ 0 for 1 ≤ i ≤ d via the following chain of inequalities:

0 < ∑_{i=0}^{d} (g_{i}(B, ℓ) − λ(ℓ) s(i))a_{i}

< ∑_{i=0}^{d} (g_{i}(B, ℓ) − λ(ℓ) s(i))a_{i} + λ(ℓ) ∑_{i=0}^{d} s(i) a_{i}

= ∑_{i=0}^{d} g_{i}(B, ℓ) a_{i} = i_{P}^{(ℓ)}(B) .
□

Remark. It is a well-known fact that Ehrhart polynomials of lattice polytopes form a special class of Hilbert polynomials. More strongly, they are special examples of Hilbert polynomials of Cohen-Macaulay semi-standard graded k-algebras [21] (this is essentially the content of Theorem 3.1). It is then natural to ask whether Ehrhart polynomials are special or whether the bounds proved above hold in more generality. We stress that inequality (16), used in previous arguments, comes from geometric information about Ehrhart polynomials i_{P} (n). Indeed, from the following proposition and Theorem 1.2(b), Ehrhart polynomials are special in their root distribution:

Proposition 4.4. For degree d Hilbert polynomials associated to arbitrary semi-standard graded k-algebras the negative real roots are arbitrarily small and d−1 may appear as a root. In contrast, for fixed degree d, Hilbert polynomials of Cohen-Macaulay semi-standard graded k-algebras have all its real roots in the interval [−d, d − 1).

Proof. Indeed, it follows from [2, Theorem 3.8] that for fixed d and positive integers a_{0}, …, a_{d}, the polynomial a_{0}(x + a_{1})(x + a_{2}) … (x + a_{d}) is the Hilbert polynomial of a semi-standard graded k-algebra. Also, observe that the chromatic polynomial of the complete graph on d vertices has highest root d − 1, and that chromatic polynomials are known to be Hilbert polynomials of standard graded algebras by a result attributed to Almkvist (see the proof given by Steingrímsson [23]). Thus the first statement holds.

Now, in a Cohen-Macaulay semi-standard graded algebra, the Hilbert polynomial can be written as p(n) = ∑_{i=0}^{d} a_{i}\binom{n+d−i}{d}, where a_{i} ≥ 0 for 0 ≤ i ≤ d. Observe that all the binomial coefficients in p(n) are positive for (real numbers) n > d − 1, which establishes the upper bound of d−1. For the lower bound, observe that for (real numbers) n < −d all the binomial coefficients are positive, respectively negative, depending on the parity of d. □

To complete the proof of Theorem 1.2 (b), we need only to prove the following lemma.

Lemma 4.5. Fix 0 ≤ ℓ ≤ d − 1 and consider again the functions s, g : {0, 1, …, d} → ℤ defined by s(i) = d − 2i + 1 and g(i) = g_{i}(B, ℓ). Moreover, if we set

(17)  λ(ℓ) = \frac{1}{2} (g(B) − g(B + 1)) = \frac{d}{2} ∑_{I∈\binom{[d−1]}{d−ℓ−1}} ∏_{k∈I} (d − k) > 0 ,

then

(18)  g(i) ≥ λ(ℓ) s(i)  for i = 0, 1, …, d .

For this, we will also need to prove Lemma 4.6 below. We will write [d−1]_{0} = {0, 1, …, d−1}, [d − 1] = \{1, 2, …, d − 1\}, and \binom{S}{t} for the set of all t-element subsets of the finite set S. Now we express i_{P} (n) as

i_{P} (n) = \frac{1}{d!} ∑_{i=0}^{d} a_{i} ∏_{k=0}^{d−1} (n + d − i − k),

so that the ℓ-th derivative of i_{P} is

i_{P}^{(ℓ)}(n) = \frac{ℓ!}{d!} ∑_{i=0}^{d} a_{i} ∑_{I∈\binom{[d−1]_{0}}{ℓ}} ∏_{k∈[d−1]_{0}\I}(n + d − i − k)

= \frac{ℓ!}{d!} ∑_{i=0}^{d} a_{i} ∑_{I∈\binom{[d−1]_{0}}{d−ℓ}} ∏_{k∈I} (n + d − i − k) .

Note that we now have an explicit formula for the coefficient of a_{i} in (d!/ℓ!) i_{P}^{(ℓ)}:

(19)  g_{i}(n, ℓ) = ∑_{I∈\binom{[d−1]_{0}}{d−ℓ}} ∏_{k∈I} (n + d − i − k) .

The following lemma shows that the piece-wise linear function interpolating g : {0, 1, …, d} → ℤ, g(i) = g_{i}(B, ℓ) is positive, and its slope weakly increases in the range 0 ≤ ℓ ≤ d and 0 ≤ i ≤ B + 1. See Figure 4.

Lemma 4.6. The following inequalities are satisfied for 0 ≤ ℓ ≤ d and 0 ≤ i ≤ B + 1:

(20)  g_{i}(B, ℓ) > 0,
(21)  g_{i}(B, ℓ) − g_{i+1}(B, ℓ) > g_{i+1}(B, ℓ) − g_{i+2}(B, ℓ).

Proof. Equation (20) follows because k ≤ d − 1 and i ≤ B + 1 imply B + d − i − k ≥ 0. To show (21), we abbreviate m := B + d − i and inspect the difference

g_{i}(B, ℓ) − g_{i+1}(B, ℓ) = ∑_{I∈\binom{[d−1]_{0}}{d−ℓ}} ∏_{k∈I} (m − k) − ∑_{J∈\binom{[d−1]_{0}}{d−ℓ}} ∏_{k∈J} (m − k − 1) .

If 0 ∉ I, then the term corresponding to I in the first sum cancels with the term corresponding to J = {i − 1 : i ∈ I} in the second sum:

∏_{k∈I} (m − k) − ∏_{k∈J} (m − k − 1) = ∏_{k∈I} ((m − k) − (m − (k − 1) − 1)) = 0,

so we are left with summing over the sets I ∈ \binom{[d−1]_{0}}{d−ℓ} that contain 0 and the sets J that contain d − 1. But for such summation sets, the difference simplifies to

g_{i}(B, ℓ) − g_{i+1}(B, ℓ) = (m − 0) ∑_{I∈\binom{[d−1]}{d−ℓ−1}} ∏_{k∈I} (m − k) − (m − d) ∑_{J∈\binom{[d−2]_{0}}{d−ℓ−1}} ∏_{k∈I} (m − (k + 1))

= d ∑_{I∈\binom{[d−1]}{d−ℓ−1}} ∏_{k∈I} (B − d − i − k) ,

and (21) follows by comparing the expressions g_{i}(B, ℓ)−g_{i+1}(B, ℓ) and g_{i+1}(B, ℓ)−g_{i+2}(B, ℓ) term by term. □

In the following, we will use Iverson’s notation (see [9]): the expression [S] evaluates to 1 resp. 0 according to the truth or falsity of the logical statement S.

Proof of Lemma 4.5. First note that s(B) = 1 for even d, so that

g(B) − λs(B) = \frac{1}{2}g(B) + \frac{1}{2}g(B + 1) > 0 ;

for odd d, we have s(B + 1) = 0. Now note that the graph of (the piecewise-linear function interpolating) λs is a line, while g(B + 1) > 0 by (20) and the slope of the graph of g is weakly increasing on [0, B+2] by (21) (see Figure 4); this proves (18) for 0 ≤ i ≤ B+[d odd].

Set j = i − B, so that we still need to prove (18) for 1 + [d odd] ≤ j ≤ d − B. By plugging (19) and (17) into (18) and rearranging, we must show that for these values of j

(22)  ∑_{I∈\binom{[d−1]_{0}}{d−ℓ}} ∏_{k∈I}(d − j − k) + \frac{d}{2} (2j − [d odd] − 1) ∑_{J∈\binom{[d−1]}{d−ℓ−1}} ∏_{k∈J}(d − k) > 0 .

Note that each term in the second sum of (22) is positive, and decompose the index sets I in the first sum into disjoint unions I = I_{+} ∪ K such that I_{+} ⊂ {0, 1, …, d − 2j} and K ⊂ {d − 2j + 1, …, d − 1}, and therefore d − j − k > 0 for all k ∈ I_{+}.

B + 1 λs (d even) λs (d odd) B g  B + 2

Figure 4. The graphs of the functions g and λs (solid for odd d, dashed for even d).

k  0 1 ⋯ d − 2j d − 2j + 1 ⋯ d − j ⋯ d − 1
value of d − j − k d − j  ⋯  j  j − 1 ⋯ 0 ⋯ −(j − 1)
set in I = I_{+} ∪ K  I_{+}  K

If |K| is odd, then the summand σ(K) corresponding to I_{+} ∪ K cancels with the one corresponding to I_{+} ∪ (d − j − K), so we only need to consider even |K|. In that case, σ(K) > 0 (resp. σ(K) < 0) if |K ∩ [d − j + 1, d − 1]| is even (resp. odd). In total, there are more than enough positive terms in (22) to cancel the negative summands. □

Proposition 4.7. We have α < 1 for any real root α of an Ehrhart polynomial i_{P} of a lattice polytope P of dimension d ≤ 4 .

Proof. It is enough to prove the statement in dimension 4 because of Theorem 1.2(b). Suppose f(n) = pn^{4} + qn^{3} + rn^{2} + sn + 1 is the Ehrhart polynomial of a lattice 4-polytope P. We know p > 0 and q > 0. Because f(1) counts the lattice points in P, we know that p+q +r +s+1 ≥ 5. By the reciprocity law, f(−1) ≥ 0, so p−q +r −s+1 ≥ 0. The top two coefficients of the shifted polynomial g(n) = f(n + 1) = pn^{4} + (4p + q)n^{3} + g_{2}n^{2} + g_{1}n + g_{0} are positive, as is the constant term g_{0} = g(0) = f(1). We will show that g_{2} and g_{1} are nonnegative, and hence, by Descartes’ rule of signs, g does not have a positive root. This implies that f(n) = g(n − 1) does not have a real root larger than 1. To prove that g_{2} ≥ 0, we add the inequalities f(1) ≥ 5 and f(−1) ≥ 0 to obtain 2p + 2r ≥ 3 or r ≥ \frac{3}{2} − p, whence g_{2} = 6p + 3q + r ≥ 5p + 3q + \frac{3}{2} ≥ 0 (because p, q ≥ 0). A similar reasoning yields

g_{1} = 4p + 3q + 2r + s = (p + q + r + s) + (3p + 2q + r) ≥ 4 + 2p + 2q + \frac{3}{2} ≥ 0 ;

here we used the inequality f(1) ≥ 5 again. □

We now conclude with the proof of Theorem 1.3:

Proof of Theorem 1.3. Given a positive integer d, consider the convex polytope P_{d} defined by the facet inequalities:

0 ≤ x_{0} ≤ x_{k} ≤ 1 for 1 ≤ k ≤ d − 1.

P_{d} is an order polytope in the sense of [20] and thus it has 0/1 vertices. We claim that the Ehrhart polynomial of P_{d} is given by i_{P_{d}}(n) = (B_{d}(n + 2) − B_{d}(0))/d where B_{d}(x) is the d-th Bernoulli polynomial.

Indeed, from the facet-defining inequalities of P_{d} one sees that i_{P_{d}}(n) is the number of dtuples of nonnegative integers (a_{0}, a_{1}, …, a_{d−1}) such that a_{0} ≤ a_{k} ≤ n. If a_{0} = j then there are n − j + 1 choices for each a_{k} (k > 0). Hence i_{P_{d}}(n) = ∑_{j=0}^{n}(n − j + 1)^{d−1} = ∑_{j=1}^{n+1} j^{d−1}. A classical identity of Bernoulli that says ∑_{k=0}^{n−1} k^{d−1} = (B_{d}(n) − B_{d}(0))/d. Thus we get i_{P_{d}}(n) = (B_{d}(n + 2) − B_{d}(0))/d, a polynomial of degree d. Note that when d is odd then B_{d}(0) = 0. Finally, the results of [24] imply that the largest real zero of B_{d}(n) is asymptotically d/(2πe). Therefore, as stated, as the degree d grows, the Ehrhart polynomial of P_{d} has larger and larger real roots. It is worth remarking that since d is the degree of the Ehrhart polynomial of P_{d} it differs from the upper bound of ⌊d/2⌋ in Theorem 1.2 only by a constant factor. □

5. Special families of polytopes

We begin this section with some charts showing the behavior of roots for hundreds of Ehrhart polynomials computed using LattE and Polymake. In Figure 5 we show the distribution of roots of a large sample of Ehrhart polynomials of lattice 3-polytopes.

In Table 1 we collected a small sample of Ehrhart polynomials of 0/1 polytopes and cyclic polytopes from the experiments we performed.

COEFFICIENTS AND ROOTS OF EHRHART POLYNOMIALS 19

name  Ehrhart polynomial P (s)
cube  t^{3} + 3 t^{2} + 3 t + 1
cube minus corner  5/6 t^{3} + 5/2 t^{2} + 8/3 t + 1
prism  1/2 t^{3} + 2 t^{2} + 5/2 t + 1
nameless  2/3 t^{3} + 2 t^{2} + 7/3 t + 1
octahedron  2/3 t^{3} + 2 t^{2} + 7/3 t + 1
square pyramid  1/3 t^{3} + 3/2 t^{2} + \frac{13}{6} t + 1
bypyramid  1/2 t^{3} + 3/2 t^{2} + 2 t + 1
unimodular tetrahedron  1/6 t^{3} + t^{2} + \frac{11}{6} t + 1
fat tetrahedron  1/3 t^{3} + t^{2} + 5/3 t + 1
as:6-18.poly  \frac{83}{240} x^{6} + \frac{307}{240} x^{5} + \frac{41}{16} x^{4} + \frac{217}{48} x^{3} + \frac{611}{120} x^{2} + \frac{16}{5} x + 1
cf:10-11.poly  \frac{11}{3628800} x^{10} + \frac{11}{725760} x^{9} + \frac{17}{60480} x^{8} + \frac{121}{24192} x^{7} + \frac{7643}{172800} x^{6} + \frac{8591}{34560} x^{5} + \frac{340873}{362880} x^{4} + \frac{84095}{36288} x^{3} + \frac{59071}{16800} x^{2} + \frac{7381}{2520} x + 1
cf:4-5.poly  1/12 x^{4} + 1/2 x^{3} + \frac{17}{12} x^{2} + 2 x + 1
cf:9-10.poly  \frac{1}{120960} x^{9} + \frac{1}{4480} x^{8} + \frac{61}{20160} x^{7} + \frac{79}{2880} x^{6} + \frac{997}{5760} x^{5} + \frac{4223}{5760} x^{4} + \frac{30043}{15120} x^{3} + \frac{32651}{10080} x^{2} + \frac{2383}{840} x + 1
cf:8-9.poly  \frac{11}{40320} x^{8} + \frac{1}{1120} x^{7} + \frac{1}{64} x^{6} + \frac{9}{80} x^{5} + \frac{1039}{1920} x^{4} + \frac{267}{160} x^{3} + \frac{5933}{2016} x^{2} + \frac{761}{280} x + 1
oa:6-13.poly  \frac{9}{80} x^{6} + \frac{43}{80} x^{5} + \frac{23}{16} x^{4} + \frac{143}{48} x^{3} + \frac{79}{20} x^{2} + \frac{179}{60} x + 1
cut(4)  \frac{2}{45} x^{6} + \frac{4}{15} x^{5} + \frac{7}{9} x^{4} + 4/3 x^{3} + \frac{98}{45} x^{2} + \frac{12}{5} x + 1
cyclic01:5-8.poly  \frac{7}{60} x^{5} + \frac{5}{12} x^{4} + 5/4 x^{3} + \frac{31}{12} x^{2} + \frac{79}{30} x + 1
halfcube(5)  \frac{13}{15} x^{5} + 11/3 x^{4} + 16/3 x^{3} + 10/3 x^{2} + 9/5 x + 1
Cyclic(2,5)  10x^{2} + 4x + 1
Cyclic(3,5)  16x^{3} + 10x^{2} + 4x + 1
Cyclic(4,5)  12x^{4} + 16x^{3} + 10x^{2} + 4x + 1
Cyclic(2,6)  20x^{2} + 5x + 1
Cyclic(3,6)  70x^{3} + 20x^{2} + 5x + 1
Cyclic(4,6)  192x^{4} + 70x^{3} + 20x^{2} + 5x + 1
Cyclic(5,6)  288x^{5} + 192x^{4} + 70x^{3} + 20x^{2} + 5x + 1
Cyclic(2,7)  35x^{2} + 6x + 1
Cyclic(3,7)  224x^{3} + 35x^{2} + 6x + 1
Cyclic(4,7)  1512x^{4} + 224x^{3} + 35x^{2} + 6x + 1
Cyclic(2,8)  56x^{2} + 7x + 1
Cyclic(3,8)  588x^{3} + 56x^{2} + 7x + 1
Cyclic(4,8)  8064x^{4} + 588x^{3} + 56x^{2} + 7x + 1

Table 1. The Ehrhart polynomials for some well-known lattice polytopes. The choice of coordinates for cyclic polytopes was t = 1, ..., n. The rest are listed Ehrhart polynomials comes from 0/1 polytopes selected from Ziegler’s list. It includes the Ehrhart polynomials of all 3-dimensional 0/1-polytopes.

Figure 5. The zeros of Ehrhart polynomials corresponding to 100000 random 3-dimensional lattice simplices.

5.1. 0/1-polytopes. We computed the Ehrhart polynomials for all 0/1 polytopes of dimension less or equal to 4 (up to symmetry there are 354 different 4-polytopes). In Figure 6 we plotted their roots. In our computations we relied on the on-line data sets of 0/1 polytopes available from Polymake’s web page and those discussed in Ziegler’s lectures on 0/1 polytopes [13]. Several phenomena are evident from the data we collected. For example, in Table 1 we see two combinatorially different polytopes that have the same Ehrhart polynomial. These are the so called “nameless” polytope of coordinates (1, 0, 0, 0), (1, 1, 0, 0), (1, 0, 1, 0), (1, 1, 1, 0), (1, 0, 1, 1), (1, 1, 0, 1) and the octahedron. Another example of regular distribution appears also in Figure 6. We show the roots of the Ehrhart polynomials associated to the Birkhoff polytope of doubly stochastic n × n matrices for n = 2, …, 9.

5.2. Cyclic polytopes. Cyclic polytopes form a family whose combinatorial structure (i.e. f-vector, face lattice, etc) is well understood. The canonical choice of coordinates is given using the moment curve

(23)  ν_{d} : \{ \begin{matrix}ℝ & → & ℝ^{d}, \\ t & ↦ & (t^{1}, t^{2}, …, t^{d}). \end{matrix}

A cyclic polytope is obtained as the convex hull of n points along the moment curve. Thus we fix t_{1}, t_{2}, …, t_{n} and define C(n, d) := conv{ν_{d}(t_{1}), ν_{d}(t_{2}), …, ν_{d}(t_{n})}. Cyclic polytopes Figure 6. Top: The zeros of the Ehrhart polynomials of all 3 and 4 dimensional 0/1 polytopes. Bottom: The zeros of Ehrhart polynomials for the Birkhoff polytopes up to n = 9 are lattice polytopes exactly when t_{i} ∈ ℤ. There is a natural linear projection connecting these cyclic polytopes.

Lemma 5.1. Consider the projection π : ℝ^{d} → ℝ^{d−1} that forgets the last coordinate. The inverse image under π of a lattice point y ∈ C(n, d − 1) ∩ ℤ^{d−1} is a line that intersects the boundary of C(n, d) in exactly two integral points.

Proof. We need to prove that, given t_{1}, t_{2}, …, t_{d} ∈ ℤ and λ_{1}, λ_{2}, …, λ_{d} ∈ ℝ,

∀ 1 ≤ j < d : ∑_{k=1}^{d} λ_{k} t_{k}^{j} ∈ ℤ  ⟹  ∑_{k=1}^{d} λ_{k} t_{k}^{d} ∈ ℤ .

For 1 ≤ j ≤ d, let y_{j} = ∑_{k=1}^{d} λ_{k} t_{k}^{j}; we know that y_{1}, y_{2}, …, y_{d−1} ∈ ℤ. We need to prove that

y = (y_{1}, …, y_{d}) = ∑_{k=1}^{d} λ_{k} ν_{d}(t_{k}) ∈ ℤ^{d} .

This identity means that y lies on the hyperplane spanned by ν_{d}(t_{1}), …, ν_{d}(t_{d}), which can be expressed via a determinant:

det \binom{1 1 … 1}{y ν_{d}(t_{1}) ν_{d}(t_{d})} = 0 .

Writing this determinant out through the first column and solving for y_{d} gives

y_{d} = − \frac{1}{D} det ( \begin{matrix}t_{1} & ⋯ & t_{d} \\ ⋮ & & ⋮ \\ t_{1}^{d} & ⋯ & t_{d}^{d} \end{matrix} ) − \frac{y_{1}}{D} det ( \begin{matrix}1 & ⋯ & 1 \\ t_{1}^{2} & ⋯ & t_{d}^{2} \\ ⋮ & & ⋮ \\ t_{1}^{d} & ⋯ & t_{d}^{d} \end{matrix} ) − ⋯

− \frac{y_{d−1}}{D} det ( \begin{matrix}1 & ⋯ & 1 \\ t_{1} & ⋯ & t_{d} \\ ⋮ & & ⋮ \\ t_{1}^{d−2} & ⋯ & t_{d}^{d−2} \\ t_{1}^{d} & ⋯ & t_{d}^{d} \end{matrix} ) ,

where

D = det ( \begin{matrix}1 & ⋯ & 1 \\ t_{1} & ⋯ & t_{d} \\ ⋮ & & ⋮ \\ t_{1}^{d−1} & ⋯ & t_{d}^{d−1} \end{matrix} ) = ∏_{1≤j<k≤d} (t_{j} − t_{k}) .

This expression yields an integer if we can prove that D divides the determinants appearing in the numerators. Equivalently, the substitution t_{j} = t_{k} in any of the numerators evaluates the determinant to zero, which is apparent. □

Consequently, Conjecture 1.5 is equivalent to saying that the number of lattice points in a dilation of a cyclic polytope by a positive integer m is equal to its volume plus the number of lattice points in its lower envelope. From the above lemma and Pick’s theorem, it follows that Conjecture 1.5 is true for d = 2.

Acknowledgements. We thank David Eisenbud, Francisco Santos, Bernd Sturmfels, Thomas Zaslavsky and Günter M. Ziegler for helpful discussions and suggestions. This research was supported in part by and the Mathematical Sciences Research Institute. Mike Develin was also supported by the American Institute of Mathematics. Jesús De Loera and Richard Stanley were partially supported by NSF grants DMS-0309694 and DMS-9988459 respectively.

References

1. U. Betke and P. McMullen, Lattice points in lattice polytopes, Monatsh. Math. 99 (1985), no. 4, 253–265.

2. F. Brenti, Hilbert polynomials in combinatorics, J. of Algebraic Combinatorics 7 (1998), 127–156.

3. D. Bump, K.-K. Choi, P. Kurlberg, and J. Vaaler, A local Riemann hypothesis. I, Math. Z. 233 (2000), no. 1, 1–19.

4. J. A. De Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, and R. Yoshida, A user’s guide for latte, (2003), software package LattE and manual are available at http://www.math.ucdavis.edu/∼latte/.

5. J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, Journal of Symbolic Computation (2003), to appear, available at

http://www.math.ucdavis.edu/∼latte/.

6. E. Ehrhart, Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux, J. Reine Angew. Math. 226 (1967), 1–29.

7. , Sur un problème de géométrie diophantienne linéaire. II. Systèmes diophantiens linéaires, J. Reine Angew. Math. 227 (1967), 25–49.

8. , Polynômes arithmétiques et méthode des polyèdres en combinatoire, Birkhäuser Verlag, Basel, 1977, International Series of Numerical Mathematics, Vol. 35.

9. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics: a foundation for computer science, 2nd ed., Addison-Wesley, 1994.

10. T. Hibi, A lower bound theorem for Ehrhart polynomials of convex polytopes, Advances in Math. 105 (1994), 162–165.

11. , Star-shaped complexes and Ehrhart polynomials, Proc. Amer. Math. Soc. 123 (1995), 723–726.

12. M. Joswig and E. Gawrilow, polymake: A framework for analyzing convex polytopes, in Kalai and Ziegler [13], pp. 43–73.

13. G. Kalai and G.M. Ziegler (eds.), Polytopes - Combinatorics and Computation, DMV-Seminar Oberwolfach, Germany, November 1997, DMV Semin., vol. 29, Birkhäuser, 2000.

14. I. G. Macdonald, Polynomials associated with finite cell-complexes, J. London Math. Soc. (2) 4 (1971), 181–192.

15. M. Marden, Geometry of polynomials, second ed., Mathematical Surveys, no. 3, American Mathematical Society, Providence, R.I., 1966.

16. F. Rodriguez-Villegas, On the zeros of certain polynomials, Proc. Amer. Math. Soc. 130 (2002), no. 8, 2251–2254.

17. P. R. Scott, On convex lattice polygons, Bull. Austral. Math. Soc. 15 (1976), no. 3, 395–399.

18. R. P. Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194–253.

19. , Decompositions of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333–342, Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978).

20. , Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23.

21. , On the Hilbert function of a graded Cohen-Macaulay domain, J. Pure Appl. Alg. 73 (1991), 307–314.

22. , Enumerative Combinatorics, 2nd ed., vol. I, Cambridge University Press, 1997.

23. E. Steingrímsson, The coloring ideal and coloring complex of a graph, J. Algebraic Combinatorics 14 (2001), 73–84.

24. A.P Veselov and J.P. Ward, On the real roots of the Bernoulli polynomials and the Hurwitz zeta-function, preprint available at www.lboro.ac.uk/departments/ma/preprints/papers99/99-35.pdf.

25. G. M. Ziegler, Lectures on polytopes, Springer-Verlag, New York, revised edition, 1998.

Max-Planck-Institut für Mathematik, Vivatsgasse 7, 53111 Bonn, Germany

E-mail address: beck@mpim-bonn.mpg.de

Department of Mathematics, University of California, One Shields Avenue, Davis, CA 95616-8633, USA

E-mail address: deloera@math.ucdavis.edu

Department of Mathematics, University of California, Berkeley, California 94720, USA

E-mail address: develin@post.harvard.edu

Institut de Matemàtica, Universitat de Barcelona, Gran Via de les Corts Catalanes 585, E-08007 Barcelona, Spain

E-mail address: julian@imub.ub.es

Department of Mathematics 2-375, Massachusetts Institute of Technology, Cambridge, MA 02139-4307, USA

E-mail address: rstan@math.mit.edu