# When are Ehrhart functions of compact convex sets polynomials?

Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is a polynomial. We know that if $P$ is a convex polytope with vertices in $L$ then $P$ is nice and $f_P(L,t)$ is its Ehrhart polynomial. My question is about some converse of this statement.

Are there some mild assumptions (for example convexity etc.) on $P$, under which if $f_P(L,t)$ is a polynomial with respect to at least some lattice $L$ then $P$ must be a convex polytope? Or a weaker question: Is any polynomial arising this way also the Ehrhart polynomial of some polytope?

P.S. I haven't thought much about this question so I apologize if it is well-known or it has an obvious negative answer. Also feel free to retag.

Richard Stanley suggested the following in the comments (edited to take into account a trivial family of counter-examples):

Could the following be true? It seems more in line with the question. Let $P$ be a compact convex $n$-dimensional set in $\mathbb R^n$. Suppose that the Ehrhart function $f_P(t)$ is a polynomial for positive integers $t$. Then $P$ is a translation of a rational polytope.

Edit: I would also be interested in a slightly weaker statement: Suppose a convex set has positive curvature almost everywhere, must the Ehrhart function necessarily be non-polynomial?

For example given an arbitrary lattice, what would be the easiest way to see that a circle doesnt have a polynomial Ehrhart function?

-
A bit of nitpicking: Ehrhart polynomial is defined for $\textit{convex}$ polytopes. –  Victor Protsak Jun 8 '10 at 1:26
I guess you know that the lattice point counting function of a rational polytope is in general a quasi-polynomial, i.e., possibly given by a different polynomial on each residue class modulo $N$ for some fixed positive integer $N$. I did a little bit of work on this in the very special case of n-simplices in $\mathbb{R}^{n+}$. Even in this very simple case the question of how many distinct polynomials arise was (and is) not obvious to me. –  Pete L. Clark Jun 8 '10 at 1:27
On the other hand, a finite polyhedral complex in $\mathbb{R}^n$ whose cells are convex lattice polytopes need not be convex, but its lattice volume is still given by a polynomial, so the conclusion shouldn't be "P is a convex polytope". –  Victor Protsak Jun 8 '10 at 1:45
Could the following be true? It seems more in line with the question. Let $P$ be a compact convex $n$-dimensional set in $\mathbb{R}^n$. Suppose that the Ehrhart function $f_P(t)$ is a polynomial for positive integers $t$. Then $P$ is a rational polytope. –  Richard Stanley Jun 10 '10 at 0:22
The answer to the question in my previous comment is no, as shown by the 1-dimensional polytope with vertices $\alpha$ and $1+\alpha$, where $\alpha$ is irrational. However, it is possible that the only counterexamples are of a similar trivial nature. Thus one can change the conclusion to: $P$ is the translate of a rational polytope (and only very special rational polytopes, since in general the translate of a rational polytope does not have a quasipolynomial Ehrhart function). –  Richard Stanley Jun 19 '10 at 2:04

Just to remark that for a rational polytope whose vertices are not integral, the function $f_P(t)$ could still be a polynomial (and not just a quasipolynomial). A large class of examples is provided by degenerations of flag varieties $G/B$. There are many degenerations, each corresponding to a representation of the longest word $w\in W$ in the Weil group as the shortest product of standard reflections. All of these correspond to rational polytopes. They all have the same Erhart function. Some of them are integral but others are not.

For more details, see R. Chiriv`ı, LS algebras and application to Schubert varieties, Transform. Groups 5 (2000), no. 3, 245–264, or Alexeev-Brion Toric degenerations of spherical varieties.

-
Also MR2096742, De Loera, Jesús A., McAllister, Tyrrell B.(1-CAD) Vertices of Gelfand-Tsetlin polytopes. Discrete Comput. Geom. 32 (2004), no. 4, 459--470. The counting problem is weight multiplicity (Kostka number). According the review, this was the first example of an infinite family of non-integral rational polytopes with polynomial Ehrhart polynomials. –  Victor Protsak Jun 8 '10 at 2:53

I believe that the strong form of the conjecture is false. In lieu of a simple counterexample, let me point you towards a centrally symmetric 10-gon $\hat P$ in arXiv:0801.2812, Figure 6. It is a bit of a mess to explain exactly what it is, but it has something to do with Picard lattice of a toric DM stack. It need not be rational or a translate of rational.

The key properties of $\hat P$ are

(1) It is centrally symmetric.

(2) The midpoints of all the sides are lattice points. As a result, opposite sides are lattice translates of each other.

As a result, generic translates of $\hat P$ have the same number of lattice points. Indeed, as you move the polytope in a plane along a general curve as soon as a point appears on one side of it, another point exits from the opposite side. This implies that the opposite sides of $\hat P$ glue together to give a "no-gaps" cover of the torus $\mathbb R^2/L$ (preimage of a generic point has the same cardinality $k$). Then if one takes a $t$-multiple of it, one gets a "no-gaps" cover of $\mathbb R^2/tL$, and will thus have $kt^2$ points in $t(\hat P+ c)$ for a generic shift $c$.

I assume that this construction can be simplified to give something more explicit and palatable, so long as the property that the opposite sides are lattice translates of each other is satisfied.

It clearly requires flat sides to be able to glue them together on the torus, so this idea is not going to work for the positive curvature problem.

-

If you want to dive into some Ehrhart theory then I highly recommend you pick up Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra by Matthias Beck and Sinai Robins.

Here is the website for the text with a free but nonprintable version: http://math.sfsu.edu/beck/ccd.html

-
Of course I have no desire to disrespect the authors' wishes, but I have to ask: what does "nonprintable version" mean? It seems like a regular pdf with regular formatting to me. –  Pietro KC Jun 11 '10 at 17:29
Nonprintable means that it has DRM built into it. Of course, it is a bit silly because it is up to the PDF software to decide if it wants to obey it. So for example, the print option is not there in acrobat, but it would be in xpdf. –  Steven Sam Aug 5 '11 at 5:28