Integer points in convex polyhedra
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Twri (talk | contribs) 15 years ago. (Update timer) |
Study of integer points in polyhedra is motivated by the questions, such as "how many nonnegative integer-valued solutions does a system of linear equations with nonnegative coefficients have" or "how many solutions does an integer linear program have". Counting integer points in polyhedra or other questions about them arise in representation theory, commutative algebra, algebraic geometry, statistics, and computer science.[1]
The set of integer points, or, more generally, the set of points of an affine lattice, in a polyhedron is called Z-polyhedron, from the mathematical notation or Z for the set of integer numbers. [2]
Properties
For a lattice Λ, Minkowski's theorem relates the number d(Λ) and the volume of a symmetric convex set S to the number of lattice points contained in S.
The number of lattice points contained in a polytope all of whose vertices are elements of the lattice is described by the polytope's Ehrhart polynomial. Formulas for some of the coefficients of this polynomial involve d(Λ) as well.
Applications
References
- ^ Integer points in polyhedra. Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics, ACM--SIAM Joint Summer Research Conference, 2006
- ^ "Computations on Iterated Spaces" in: The Compiler Design Handbook: Optimizations and Machine Code Generation, CRC Press 2007, 2nd edition, ISBN 142004382X, p.15-7