Английская Википедия:Ehrhart polynomial

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

In mathematics, an integral polytope has an associated Ehrhart polynomial that 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 the 1960s.

Definition

Informally, if Шаблон:Math is a polytope, and Шаблон:Math is the polytope formed by expanding Шаблон:Math by a factor of Шаблон:Math in each dimension, then Шаблон:Math is the number of integer lattice points in Шаблон:Math.

More formally, consider a lattice <math>\mathcal{L}</math> in Euclidean space <math>\R^n</math> and a Шаблон:Math-dimensional polytope Шаблон:Math in <math>\R^n</math> with the property that all vertices of the polytope are points of the lattice. (A common example is <math>\mathcal{L} = \Z^n</math> and a polytope for which all vertices have integer coordinates.) For any positive integer Шаблон:Math, let Шаблон:Math be the Шаблон:Math-fold dilation of Шаблон:Math (the polytope formed by multiplying each vertex coordinate, in a basis for the lattice, by a factor of Шаблон:Math), and let

<math>L(P,t) = \#\left(tP \cap \mathcal{L}\right)</math>

be the number of lattice points contained in the polytope Шаблон:Math. Ehrhart showed in 1962 that Шаблон:Math is a rational polynomial of degree Шаблон:Math in Шаблон:Math, i.e. there exist rational numbers <math>L_0(P),\dots,L_d(P)</math> such that:

<math>L(P, t) = L_d(P) t^d + L_{d-1}(P) t^{d-1} + \cdots + L_0(P)</math>

for all positive integers Шаблон:Math.

The Ehrhart polynomial of the interior of a closed convex polytope Шаблон:Math can be computed as:

<math> L(\operatorname{int}(P), t) = (-1)^d L(P, -t),</math>

where Шаблон:Math is the dimension of Шаблон:Math. This result is known as Ehrhart–Macdonald reciprocity.

Examples

Файл:Second dilate of a unit square.png

This is the second dilate, <math>t = 2</math>, of a unit square. It has nine integer points.

Let Шаблон:Math be a Шаблон:Math-dimensional unit hypercube whose vertices are the integer lattice points all of whose coordinates are 0 or 1. In terms of inequalities,

<math> P = \left\{x\in\R^d : 0 \le x_i \le 1; 1 \le i \le d\right\}.</math>

Then the Шаблон:Math-fold dilation of Шаблон:Math is a cube with side length Шаблон:Math, containing Шаблон:Math integer points. That is, the Ehrhart polynomial of the hypercube is Шаблон:Math. Additionally, if we evaluate Шаблон:Math at negative integers, then

<math>L(P, -t) = (-1)^d (t - 1)^d = (-1)^d L(\operatorname{int}(P), t),</math>

as we would expect from Ehrhart–Macdonald reciprocity.

Many other figurate numbers 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 Шаблон:Math.

Ehrhart quasi-polynomials

Let Шаблон:Math be a rational polytope. In other words, suppose

<math>P = \left\{ x\in\R^d : Ax \le b\right\},</math>

where <math>A \in \Q^{k \times d}</math> and <math>b \in \Q^k.</math> (Equivalently, Шаблон:Math is the convex hull of finitely many points in <math>\Q^d.</math>) Then define

<math>L(P, t) = \#\left(\left\{x\in\Z^d : Ax \le tb \right\} \right). </math>

In this case, Шаблон:Math is a quasi-polynomial in Шаблон:Math. Just as with integral polytopes, Ehrhart–Macdonald reciprocity holds, that is,

<math> L(\operatorname{int}(P), t) = (-1)^d L(P, -t). </math>

Examples of Ehrhart quasi-polynomials

Let Шаблон:Math be a polygon with vertices (0,0), (0,2), (1,1) and (Шаблон:Sfrac, 0). The number of integer points in Шаблон:Math will be counted by the quasi-polynomial

<math> L(P, t) = \frac{7t^2}{4} + \frac{5t}{2} + \frac{7 + (-1)^t}{8}. </math>

Interpretation of coefficients

If Шаблон:Math is closed (i.e. the boundary faces belong to Шаблон:Math), some of the coefficients of Шаблон:Math have an easy interpretation:

• the leading coefficient, <math>L_d(P)</math>, is equal to the Шаблон:Math-dimensional volume of Шаблон:Math, divided by Шаблон:Math (see lattice for an explanation of the content or covolume Шаблон:Math of a lattice);

• the second coefficient, <math>L_{d-1}(P)</math>, can be computed as follows: the lattice Шаблон:Math induces a lattice Шаблон:Math on any face Шаблон:Math of Шаблон:Math; take the Шаблон:Math-dimensional volume of Шаблон:Math, divide by Шаблон:Math, and add those numbers for all faces of Шаблон:Math;

• the constant coefficient, <math>L_0(P)</math>, is the Euler characteristic of Шаблон:Math. When Шаблон:Math is a closed convex polytope, <math>L_0(P)=1</math>.

The Betke–Kneser theorem

Ulrich Betke and Martin Kneser established the following characterization of the Ehrhart coefficients. A functional <math>Z</math> defined on integral polytopes is an <math>\operatorname{SL}(n,\Z)</math> and translation invariant valuation if and only if there are real numbers <math>c_0,\ldots, c_n</math> such that

<math> Z= c_0 L_0+\cdots +c_n L_n.</math>

Ehrhart series

We can define a generating function for the Ehrhart polynomial of an integral Шаблон:Math-dimensional polytope Шаблон:Math as

<math> \operatorname{Ehr}_P(z) = \sum_{t\ge 0} L(P, t)z^t. </math>

This series can be expressed as a rational function. Specifically, Ehrhart proved (1962) that there exist complex numbers <math>h_j^*</math>, <math>0 \le j \le d</math>, such that the Ehrhart series of Шаблон:Math is

<math>\operatorname{Ehr}_P(z) = \frac{\sum_{j=0}^d h_j^\ast(P) z^j}{(1 - z)^{d + 1}}, \qquad \sum_{j=0}^d h_j^\ast(P) \neq 0.</math>

Additionally, Richard P. Stanley's non-negativity theorem states that under the given hypotheses, <math>h_j^*</math> will be non-negative integers, for <math>0 \le j \le d</math>.

Another result by Stanley shows that if Шаблон:Math is a lattice polytope contained in Шаблон:Math, then <math>h_j^*(P) \le h_j^*(Q)</math> for all Шаблон:Math. The <math>h^*</math>-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 Шаблон:Math, where Шаблон:Math is the smallest integer such that Шаблон:Math is an integer polytope (Шаблон:Math is called the denominator of Шаблон:Math), then one has

<math>\operatorname{Ehr}_P(z) = \sum_{t\ge 0} L(P, t)z^t = \frac{\sum_{j=0}^{D(d+1)} h_j^\ast(P) z^j}{\left(1 - z^D\right)^{d + 1}},</math>

where the <math>h_j^*</math> are still non-negative integers.

Non-leading coefficient bounds

The polynomial's non-leading coefficients <math>c_0,\dots,c_{d-1}</math> in the representation

<math>L(P,t) = \sum_{r=0}^d c_r t^r</math>

can be upper bounded:

<math>c_r \leq (-1)^{d-r}\begin{bmatrix}d \\ r \end{bmatrix} c_d +\frac{(-1)^{d-r-1}}{(d-1)!}\begin{bmatrix}d\\ r+1\end{bmatrix}</math>

where <math>\left [\begin{smallmatrix}n\\ k\end{smallmatrix} \right ]</math> is a Stirling number of the first kind. Lower bounds also exist.

Toric variety

The case <math>n=d=2</math> and <math>t = 1</math> of these statements yields Pick's theorem. Formulas for the other coefficients are much harder to get; Todd classes of toric varieties, the Riemann–Roch theorem as well as Fourier analysis have been used for this purpose.

If Шаблон:Math is the toric variety corresponding to the normal fan of Шаблон:Math, then Шаблон:Math defines an ample line bundle on Шаблон:Math, and the Ehrhart polynomial of Шаблон:Math coincides with the Hilbert polynomial of this line bundle.

Ehrhart polynomials can be studied for their own sake. For instance, one could ask questions related to the roots of an Ehrhart polynomial. Furthermore, some authors have pursued the question of how these polynomials could be classified.

Generalizations

It is possible to study the number of integer points in a polytope Шаблон:Math if we dilate some facets of Шаблон:Math but not others. In other words, one would like to know the number of integer points in semi-dilated polytopes. It turns out that such a counting function will be what is called a multivariate quasi-polynomial. An Ehrhart-type reciprocity theorem will also hold for such a counting function.

Counting the number of integer points in semi-dilations of polytopes has applications in enumerating the number of different dissections of regular polygons and the number of non-isomorphic unrestricted codes, a particular kind of code in the field of coding theory.

See also

• Quasi-polynomial
• Stanley's reciprocity theorem

Further reading

• Шаблон:Citation. Introduces the Fourier analysis approach and gives references to other related articles.
• Шаблон:Citation.