info prev up next book cdrom email home

Ehrhart Polynomial

Let $\Delta$ denote an integral convex Polytope of Dimension $n$ in a lattice $M$, and let $l_\Delta(k)$ denote the number of Lattice Points in $\Delta$ dilated by a factor of the integer $k$,

l_\Delta(k)=\char93 (k\Delta\cap M)
\end{displaymath} (1)

for $k\in\Bbb{Z}^+$. Then $l_\Delta$ is a polynomial function in $k$ of degree $n$ with rational coefficients
\end{displaymath} (2)

called the Ehrhart polynomial (Ehrhart 1967, Pommersheim 1993). Specific coefficients have important geometric interpretations.
1. $a_n$ is the Content of $\Delta$.

2. $a_{n-1}$ is half the sum of the Contents of the $(n-1)$-D faces of $\Delta$.

3. $a_0=1$.
Let $S_2(\Delta)$ denote the sum of the lattice lengths of the edges of $\Delta$, then the case $n=2$ corresponds to Pick's Theorem,
l_\Delta(k)=\mathop{\rm Vol}(\Delta)k^2+{\textstyle{1\over 2}}S_2(\Delta)+1.
\end{displaymath} (3)

Let $S_3(\Delta)$ denote the sum of the lattice volumes of the 2-D faces of $\Delta$, then the case $n=3$ gives
l_\Delta(k)=\mathop{\rm Vol}(\Delta)k^3+{\textstyle{1\over 2}}S_3(\Delta)k^2+a_1 k+1,
\end{displaymath} (4)

where a rather complicated expression is given by Pommersheim (1993), since $a_1$ can unfortunately not be interpreted in terms of the edges of $\Delta$. The Ehrhart polynomial of the tetrahedron with vertices at (0, 0, 0), ($a$, 0, 0), (0, $b$, 0), (0, 0, $c$) is

$l_\Delta(k)={\textstyle{1\over 6}}abc k^3+{\textstyle{1\over 4}}(ab+ac+bc+d)k^2$
$\quad +\left[{{1\over 12}\left({{ac\over b}+{bc\over a}+{ab\over c}+{d^2\over abc}}\right)+{\textstyle{1\over 4}}(a+b+c+A+B+C)}\right.$
$\quad \left.{-As\left({{bc\over d}, {aA\over d}}\right)-Bs\left({{ac\over d}, {bB\over d}}\right)-Cs\left({{ab\over d}, {cC\over d}}\right)}\right]k +1,$ (5)
where $s(x,y)$ is a Dedekind Sum, $A=\gcd(b,c)$, $B=\gcd(a,c)$, $C=\gcd(a,b)$ (here, gcd is the Greatest Common Divisor), and $d=ABC$ (Pommersheim 1993).

See also Dehn Invariant, Pick's Theorem


Ehrhart, E. ``Sur une problème de géométrie diophantine linéaire.'' J. Reine angew. Math. 227, 1-29, 1967.

MacDonald, I. G. ``The Volume of a Lattice Polyhedron.'' Proc. Camb. Phil. Soc. 59, 719-726, 1963.

McMullen, P. ``Valuations and Euler-Type Relations on Certain Classes of Convex Polytopes.'' Proc. London Math. Soc. 35, 113-135, 1977.

Pommersheim, J. ``Toric Varieties, Lattices Points, and Dedekind Sums.'' Math. Ann. 295, 1-24, 1993.

Reeve, J. E. ``On the Volume of Lattice Polyhedra.'' Proc. London Math. Soc. 7, 378-395, 1957.

Reeve, J. E. ``A Further Note on the Volume of Lattice Polyhedra.'' Proc. London Math. Soc. 34, 57-62, 1959.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein