In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an
integral polytope
In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points.
Integral polytopes are also c ...
has an associated Ehrhart polynomial that encodes the relationship between the volume of a
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
and the number of
integer point
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or gr ...
s the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of
Pick's theorem
In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick i ...
in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...
.
These polynomials are named after
Eugène Ehrhart who studied them in the 1960s.
Definition
Informally, if is a
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
, and is the polytope formed by expanding by a factor of in each dimension, then is the number of
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid ...
points in .
More formally, consider a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
in
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...
and a -
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
al polytope in
with the property that all vertices of the polytope are points of the lattice. (A common example is
and a polytope for which all vertices have
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
coordinates.) For any positive integer , let be the -fold dilation of (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of ), and let
:
be the number of lattice points contained in the polytope . Ehrhart showed in 1962 that is a rational
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
of degree in , i.e. there exist
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
s
such that:
:
for all positive integers .
The Ehrhart polynomial of the
interior of a closed convex polytope can be computed as:
:
where is the dimension of . This result is known as Ehrhart–Macdonald reciprocity.
Examples
Let be a -dimensional
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
hypercube whose vertices are the integer lattice points all of whose coordinates are 0 or 1. In terms of inequalities,
:
Then the -fold dilation of is a cube with side length , containing integer points. That is, the Ehrhart polynomial of the hypercube is . Additionally, if we evaluate at negative integers, then
:
as we would expect from Ehrhart–Macdonald reciprocity.
Many other
figurate number
The term figurate number is used by different writers for members of different sets of numbers, generalizing from triangular numbers to different shapes (polygonal numbers) and different dimensions (polyhedral numbers). The term can mean
* polyg ...
s can be expressed as Ehrhart polynomials. For instance, the
square pyramidal numbers are given by the Ehrhart polynomials of a
square pyramid with an integer unit square as its base and with height one; the Ehrhart polynomial in this case is .
Ehrhart quasi-polynomials
Let be a rational polytope. In other words, suppose
:
where
and
(Equivalently, is the
convex hull of finitely many points in
) Then define
:
In this case, is a
quasi-polynomial
In mathematics, a quasi-polynomial (pseudo-polynomial) is a generalization of polynomials. While the coefficients of a polynomial come from a ring, the coefficients of quasi-polynomials are instead periodic functions with integral period. Quasi-p ...
in . Just as with integral polytopes, Ehrhart–Macdonald reciprocity holds, that is,
:
Examples of Ehrhart quasi-polynomials
Let be a polygon with vertices (0,0), (0,2), (1,1) and (, 0). The number of integer points in will be counted by the quasi-polynomial
:
Interpretation of coefficients
If is
closed (i.e. the boundary faces belong to ), some of the coefficients of have an easy interpretation:
* the leading coefficient,
, is equal to the -dimensional
volume
Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). Th ...
of , divided by (see
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
for an explanation of the content or covolume of a lattice);
* the second coefficient,
, can be computed as follows: the lattice induces a lattice on any face of ; take the -dimensional volume of , divide by , and add those numbers for all faces of ;
* the constant coefficient is the
Euler characteristic of . When is a closed convex polytope,
.
The Betke–Kneser theorem
Ulrich Betke and
Martin Kneser
Martin Kneser (21 January 1928 – 16 February 2004) was a German mathematician. His father Hellmuth Kneser and grandfather Adolf Kneser were also mathematicians.
He obtained his PhD in 1950 from Humboldt University of Berlin with the disser ...
established the following characterization of the Ehrhart coefficients. A functional
defined on integral polytopes is an
and translation invariant
valuation if and only if there are real numbers
such that
:
Ehrhart series
We can define a
generating function for the Ehrhart polynomial of an integral -dimensional polytope as
:
This series can be expressed as a
rational function. Specifically, Ehrhart proved (1962) that there exist complex numbers
,
, such that the Ehrhart series of is
:
Additionally,
Richard P. Stanley
Richard Peter Stanley (born June 23, 1944) is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He r ...
's non-negativity theorem states that under the given hypotheses,
will be non-negative integers, for
.
Another result by Stanley shows that if is a lattice polytope contained in , then
for all . The
-vector is in general not unimodal, but it is whenever it is symmetric, and the polytope has a regular unimodular triangulation.
Ehrhart series for rational polytopes
As in the case of polytopes with integer vertices, one defines the Ehrhart series for a rational polytope. For a ''d''-dimensional rational polytope , where is the smallest integer such that is an integer polytope ( is called the denominator of ), then one has
:
where the
are still non-negative integers.
Non-leading coefficient bounds
The polynomial's non-leading coefficients
in the representation
:
can be upper bounded:
:
where