7
$\begingroup$

Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the multiples $t\cdot P$ of $P$ is a quasi-polynomial instead of a polynomial, as in the integral case. This is the so-called Ehrhart quasi-polynomial of $P$.

This means that if $L(t,P)=\#\{x\in\mathbb{Z}^d:x\in t\cdot P\}$, then there exists a finite number of polynomial functions $f_1,\dots, f_D$, all of degree $\dim P$, such that $L(t,P)=f_i(t)$ whenever $t\equiv i\mod D$ (n.b. $D$ is the period of the polytope and if the polytope is integral we have $D=1$ and recover the usual Ehrhart polynomial of $P$).

What I want to know is how much can these polynomial functions differ from one another. That is, are there known bounds to the order of $f_i-f_j$ for all $i$ and $j$? How sharp are these bounds?

The case I'm dealing with is for $\dim P=2$, so if there are sharper results for this case than in general that'd be great.

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you clarify what kind of bound you are looking for? Do you care about estimating $|f_i(t)-f_j(t)|$ for small $t$, or only asymptotically? $\endgroup$
    – Christian Gaetz
    Commented May 24, 2018 at 15:29
  • $\begingroup$ @ChristianGaetz I'm looking for the asymptotics, but if you also can say something about the small $t$ case that'd be really interesting! $\endgroup$
    – user347489
    Commented May 24, 2018 at 15:50
  • $\begingroup$ Did you forget a $t$ in the definition of $L(t,P)$? $\endgroup$
    – Avi Steiner
    Commented May 24, 2018 at 17:25
  • 1
    $\begingroup$ A good (and somewhat commonly used) name for a "component" of a quasipolynomial is constituent. $\endgroup$
    – matthias beck
    Commented May 28, 2018 at 4:47

2 Answers 2

Reset to default
6
$\begingroup$

Let $d=\dim(P)$. First, since $L(t,P)$ is non-decreasing in $t$, for any positive integer $n$ we have $$f_i((n-1)D+i) \leq f_j((n-1)D+j) \leq f_i(nD+i) \leq f_j(nD+j)$$ whenever $i \leq j$. Thus it is easy to see that the coefficients of $t^d$ in $f_i,f_j$ must be the same (in fact this coefficient is a normalized volume of $P$). Thus $f_i(t)-f_j(t)$ is $O(t^{d-1})$.

It is easy to see that $\Omega(t^{d-1})$ can be achieved. For example, if $P$ is the $d$-cube with side-length $1/2$ in the positive quadrant with a vertex at the origin, then $$f_1(t)=\left(\frac{1}{2}\right)^d (t+1)^d$$ and $$f_2(t)=\left(\frac{1}{2}\right)^d (t+2)^d$$ so the difference is at least $\frac{d}{2^d}t^{d-1}$. Probably one can improve this constant.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I see, I guess this is what I was expecting. I know how the proof about the volume goes using toric geometry in the integral case. Perhaps the same argument can be adapted for the rational one? Thanks for the good answer! PS. Minor edit: it should be $O$ instead of $\Omega$ $\endgroup$
    – user347489
    Commented May 24, 2018 at 17:54
3
$\begingroup$

I'll complement Christian's answer with an example in the other direction. Consider the polytope of $8\times 8$ symmetric doubly-stochastic matrices with 0 diagonal. The period of the Ehrhart quasipolymonial is 2 and the degree is 20. However the difference between the polynomials for even and odd dilations has degree only 5. I don't know (but would like to know) what happens for larger matrices.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note that if we drop the "with 0 diagonal" condition, the answer is known exactly. Namely, the Ehrhart quasi-polynomial then is of the form $P_n(r)+(-1)^rQ_n(r)$ where the degree of $P_n(r)$ is $\binom{n}{2}$ and the degree of $Q_n(r)$ is $\binom{n-1}{2}-1$ if $n$ is odd and $\binom{n-2}{2}-1$ if $n$ is even. See Stanley, "Magic labelings of graphs, symmetric magic squares ..." (doi.org/10.1215/S0012-7094-76-04342-8) and Jia, "Symmetric magic squares and multivariate splines" (doi.org/10.1016/0024-3795(95)00451-3). $\endgroup$
    – Sam Hopkins
    Commented Oct 4, 2020 at 21:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .