Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Ehrhart polynomial
Summary
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.
Informally, if P is a polytope, and tP is the polytope formed by expanding P by a factor of t in each dimension, then L(P, t) is the number of integer lattice points in tP.
More formally, consider a lattice in Euclidean space and a d-dimensional polytope P 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 coordinates.) 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 the polytope tP. Ehrhart showed in 1962 that L is a rational polynomial of degree d in t, i.e. there exist rational numbers such that:
for all positive integers t.
The Ehrhart polynomial of the interior of a closed convex polytope P can be computed as:
where d is the dimension of P. This result is known as Ehrhart–Macdonald reciprocity.
Let P be a d-dimensional unit hypercube whose vertices are the integer lattice points all of whose coordinates are 0 or 1. In terms of inequalities,
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. Additionally, if we evaluate L(P, t) at negative integers, then
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 1/6(t + 1)(t + 2)(2t + 3).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.