Ehrhart polynomial
Encyclopedia
In mathematics
, an integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem
in the Euclidean plane.
These polynomials are named after Eugène Ehrhart
who studied them in 1960s.
or polytope
, and tP is the polytope formed by expanding P by a factor of t in each dimension, then L(int P, t) is the number of integer lattice
points in tP.
More formally, consider a lattice
L in Euclidean space
Rn and a d-dimension
al polytope P in Rn, and assume that all the vertices of the polytope are points of the lattice. (A common example is L = Zn and a polytope with all its vertex coordinates being integer
s.) For any positive integer t, let tP be the t-fold dilation of P (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of t), and let
be the number of lattice points contained in tP. Ehrhart showed in 1962 that L is a rational polynomial
of degree d in t, i.e. there exist rational number
s a0,...,ad such that:
The Ehrhart polynomial of the interior
of a closed convex polytope P can be computed as:
hypercube
whose vertices are the integer lattice points all of whose coordinates are 0 or 1, then the t-fold dilation of P is a cube with side length t, containing (t + 1)d integer points. That is, the Ehrhart polynomial of the hypercube is L(P,t) = (t + 1)d.
Many other figurate number
s can be expressed as Ehrhart polynomials. For instance, the square pyramidal number
s 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 (t + 1)(t + 2)(2t + 3)/6.
(i.e. the boundary faces belong to P), some of the coefficients of L(P, t) have an easy interpretation:
. Formulas for the other coefficients are much harder to get; Todd class
es of toric varieties, the Riemann–Roch theorem
as well as Fourier analysis have been used for this purpose.
If X is the toric variety corresponding to the normal fan of P, then P defines an ample line bundle
on X, and the Ehrhart polynomial of P coincides with the Hilbert polynomial
of this line bundle.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, an integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a higher-dimensional generalization of Pick's theorem
Pick's theorem
Given a simple polygon constructed on a grid of equal-distanced points such that all the polygon's vertices are grid points, Pick's theorem provides a simple formula for calculating the area A of this polygon in terms of the number i of lattice points in the interior located in the polygon and the...
in the Euclidean plane.
These polynomials are named after Eugène Ehrhart
Eugène Ehrhart
Eugène Ehrhart was a French mathematician who introduced Ehrhart polynomials in the 1960s. Ehrhart received his high school diploma at the age of 22. He was a mathematics teacher in several high schools, and did mathematics research on his own time...
who studied them in 1960s.
Definition
Informally, if P is any polyhedronPolyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
or polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
, and tP is the polytope formed by expanding P by a factor of t in each dimension, then L(int P, t) is the number of integer lattice
Integer lattice
In mathematics, the n-dimensional integer lattice , denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are n-tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid lattice. Zn is the simplest example of a root lattice...
points in tP.
More formally, consider a lattice
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
L in Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
Rn and a d-dimension
Dimension
In physics and mathematics, the dimension of a 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 because only one coordinate is needed to specify a point on it...
al polytope P in Rn, and assume that all the vertices of the polytope are points of the lattice. (A common example is L = Zn and a polytope with all its vertex coordinates being integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.) For any positive integer t, let tP be the t-fold dilation of P (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of t), and let
be the number of lattice points contained in tP. Ehrhart showed in 1962 that L is a rational polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
of degree d in t, i.e. there exist rational number
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s a0,...,ad such that:
- L(P, t) = adtd + ad−1td−1 + … + a0 for all positive integers t.
The Ehrhart polynomial of the interior
Interior (topology)
In mathematics, specifically in topology, the interior of a set S of points of a topological space consists of all points of S that do not belong to the boundary of S. A point that is in the interior of S is an interior point of S....
of a closed convex polytope P can be computed as:
- L(int P, t) = (−1)n L(P, −t).
Examples
If P is a d-dimensional unitUnit cube
A unit cube, sometimes called a cube of side 1, is a cube whose sides are 1 unit long. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.- Unit Hypercube :...
hypercube
Hypercube
In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
whose vertices are the integer lattice points all of whose coordinates are 0 or 1, then the t-fold dilation of P is a cube with side length t, containing (t + 1)d integer points. That is, the Ehrhart polynomial of the hypercube is L(P,t) = (t + 1)d.
Many other figurate number
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 and different dimensions...
s can be expressed as Ehrhart polynomials. For instance, the square pyramidal number
Square pyramidal number
In mathematics, a pyramid number, or square pyramidal number, is a figurate number that represents the number of stacked spheres in a pyramid with a square base...
s are given by the Ehrhart polynomials of a square pyramid
Square pyramid
In geometry, a square pyramid is a pyramid having a square base. If the apex is perpendicularly above the center of the square, it will have C4v symmetry.- Johnson solid :...
with an integer unit square as its base and with height one; the Ehrhart polynomial in this case is (t + 1)(t + 2)(2t + 3)/6.
Interpretation of coefficients
If P is closedClosed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points...
(i.e. the boundary faces belong to P), some of the coefficients of L(P, t) have an easy interpretation:
- the leading coefficient, ad, is equal to the d-dimensional volumeVolumeVolume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....
of P, divided by d(L) (see latticeLattice (group)In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
for an explanation of the content or covolume d(L) of a lattice); - the second coefficient, ad−1, can be computed as follows: the lattice L induces a lattice LF on any face F of P; take the (d−1)-dimensional volume of F, divide by 2d(LF), and add those numbers for all faces of P;
- the constant coefficient a0 is the Euler characteristicEuler characteristicIn mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent...
of P. When P is a closed convex polytope, a0 = 1.
Related topics
The case n = d = 2 and t = 1 of these statements yields Pick's theoremPick's theorem
Given a simple polygon constructed on a grid of equal-distanced points such that all the polygon's vertices are grid points, Pick's theorem provides a simple formula for calculating the area A of this polygon in terms of the number i of lattice points in the interior located in the polygon and the...
. Formulas for the other coefficients are much harder to get; Todd class
Todd class
In mathematics, the Todd class is a certain construction now considered a part of the theory in algebraic topology of characteristic classes. The Todd class of a vector bundle can be defined by means of the theory of Chern classes, and is encountered where Chern classes exist — most notably...
es of toric varieties, the Riemann–Roch theorem
Riemann–Roch theorem
The Riemann–Roch theorem is an important tool in mathematics, specifically in complex analysis and algebraic geometry, for the computation of the dimension of the space of meromorphic functions with prescribed zeroes and allowed poles...
as well as Fourier analysis have been used for this purpose.
If X is the toric variety corresponding to the normal fan of P, then P defines an ample line bundle
Ample line bundle
In algebraic geometry, a very ample line bundle is one with enough global sections to set up an embedding of its base variety or manifold M into projective space. An ample line bundle is one such that some positive power is very ample...
on X, and the Ehrhart polynomial of P coincides with the Hilbert polynomial
Hilbert polynomial
In commutative algebra, the Hilbert polynomial of a graded commutative algebra or graded module is a polynomial in one variable that measures the rate of growth of the dimensions of its homogeneous components...
of this line bundle.