![IP polytope with LP relaxation](https://upload.wikimedia.org/wikipedia/commons/0/06/IP_polytope_with_LP_relaxation.svg)
The study of integer points in convex polyhedra is motivated by questions such as "how many nonnegative
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 language ...
-valued solutions does a
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
with nonnegative coefficients have" or "how many solutions does an
integer linear program
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objectiv ...
have". Counting integer points in
polyhedra
In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is the convex hull of finitely many points, not all on t ...
or other questions about them arise in
representation theory
Representation theory is a branch of mathematics that studies abstract algebraic structures by ''representing'' their elements as linear transformations of vector spaces, and studies modules over these abstract algebraic structures. In essen ...
,
commutative algebra
Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra. Prominent ...
,
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
,
statistics
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
, and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
.
The set of integer points, or, more generally, the set of points of an
affine lattice
In geometry and group theory, a lattice in the real coordinate space \mathbb^n is an infinite set of points in this space with the properties that coordinate wise addition or subtraction of two points in the lattice produces another lattice poin ...
, in a polyhedron is called Z-polyhedron, from the mathematical notation
or Z for the set of integer numbers.
["Computations on Iterated Spaces" in: The Compiler Design Handbook: Optimizations and Machine Code Generation, ]CRC Press
The CRC Press, LLC is an American publishing group that specializes in producing technical books. Many of their books relate to engineering, science and mathematics. Their scope also includes books on business, forensics and information tec ...
2007, 2nd edition,
p.15-7
/ref>
Properties
For 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 ornam ...
Λ, Minkowski's theorem
In mathematics, Minkowski's theorem is the statement that every convex set in \mathbb^n which is symmetric with respect to the origin and which has volume greater than 2^n contains a non-zero integer point (meaning a point in \Z^n that is not t ...
relates the number d(Λ) (the volume of a fundamental parallelepiped of the lattice) and the volume of a given symmetric convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
''S'' to the number of lattice points contained in ''S''.
The number of lattice points contained in 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 -d ...
all of whose vertices are elements of the lattice is described by the polytope's 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 highe ...
. Formulas for some of the coefficients of this polynomial involve d(Λ) as well.
Applications
Loop optimization
In certain approaches to loop optimization
In compiler theory, loop optimization is the process of increasing execution speed and reducing the overheads associated with loops. It plays an important role in improving cache performance and making effective use of parallel processing capabi ...
, the set of the executions of the loop body is viewed as the set of integer points in a polyhedron defined by loop constraints.
See also
*Convex lattice 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 ...
*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 in 18 ...
References and notes
Further reading
*
*
*{{citation
, last1 = Beck , first1 = Matthias
, last2 = Haase , first2 = Christian
, last3 = Reznick , first3 = Bruce , author3-link = Bruce Reznick
, last4 = Vergne , first4 = Michèle , author4-link = Michèle Vergne
, last5 = Welker , first5 = Volkmar
, last6 = Yoshida , first6 = Ruriko , author6-link = Ruriko Yoshida
, doi = 10.1090/conm/452
, isbn = 978-0-8218-4173-0
, mr = 2416261
, publisher = American Mathematical Society , location = Providence, RI
, series = Contemporary Mathematics
, title = Integer Points In Polyhedra: Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics
, volume = 452
, year = 2008, url = https://hal.archives-ouvertes.fr/hal-00134312/file/SAUVE-barvinokvaluations.pdf
Lattice points
Linear algebra
Linear programming
Polytopes