Integer points in convex polyhedra

Last updated
The red dots are the integer lattice points within the blue polygon, the latter representing a two-dimensional linear program IP polytope with LP relaxation.svg
The red dots are the integer lattice points within the blue polygon, the latter representing a two-dimensional linear program

The study of integer points in convex polyhedra [1] is motivated by 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. [2]

Contents

The set of integer points, or, more generally, the set of points of an affine lattice, in a polyhedron is called Z-polyhedron, [3] from the mathematical notation or Z for the set of integer numbers. [4]

Properties

For a lattice Λ, Minkowski's theorem relates the number d(Λ) (the volume of a fundamental parallelepiped of the lattice) and the volume of a given 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

Loop optimization

In certain approaches to loop optimization, 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

References and notes

  1. In some contexts convex polyhedra are called simply "polyhedra".
  2. Integer points in polyhedra. Geometry, Number Theory, Representation Theory, Algebra, Optimization, Statistics, ACM--SIAM Joint Summer Research Conference, 2006
  3. The term "Z-polyhedron" is also used as a synonym to convex lattice polytope, the convex hull of finitely many points in an affine lattice.
  4. "Computations on Iterated Spaces" in: The Compiler Design Handbook: Optimizations and Machine Code Generation, CRC Press 2007, 2nd edition, ISBN   1-4200-4382-X, p.15-7

Further reading

Related Research Articles

<span class="mw-page-title-main">Dual polyhedron</span> Polyhedron associated with another by swapping vertices for faces

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

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 n as an n-dimensional polytope or n-polytope. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope. In this context, "flat sides" means that the sides of a (k + 1)-polytope consist of k-polytopes that may have (k – 1)-polytopes in common.

<span class="mw-page-title-main">Hyperplane</span> Subspace of n-space whose dimension is (n-1)

In geometry, a hyperplane is a subspace whose dimension is one less than that of its ambient space. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. This notion can be used in any general space in which the concept of the dimension of a subspace is defined.

<span class="mw-page-title-main">Geometry of numbers</span>

Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in and the study of these lattices provides fundamental information on algebraic numbers. The geometry of numbers was initiated by Hermann Minkowski (1910).

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.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Lattice (group)</span> Periodic set of points

In geometry and group theory, a lattice in the real coordinate space 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 point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

<span class="mw-page-title-main">Net (polyhedron)</span> Edge-joined polygons which fold into a polyhedron

In geometry, a net of a polyhedron is an arrangement of non-overlapping edge-joined polygons in the plane which can be folded to become the faces of the polyhedron. Polyhedral nets are a useful aid to the study of polyhedra and solid geometry in general, as they allow for physical models of polyhedra to be constructed from material such as thin cardboard.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

<span class="mw-page-title-main">Convex cone</span> Mathematical set closed under positive linear combinations

In linear algebra, a cone—sometimes called a linear cone for distinguishing it from other sorts of cones—is a subset of a vector space that is closed under scalar multiplication; that is, C is a cone if implies for every positive scalar s.

In mathematics, specifically in combinatorial commutative algebra, a convex lattice polytope P is called normal if it has the following property: given any positive integer n, every lattice point of the dilation nP, obtained from P by scaling its vertices by the factor n and taking the convex hull of the resulting points, can be written as the sum of exactly n lattice points in P. This property plays an important role in the theory of toric varieties, where it corresponds to projective normality of the toric variety determined by P. Normal polytopes have popularity in algebraic combinatorics. These polytopes also represent the homogeneous case of the Hilbert bases of finite positive rational cones and the connection to algebraic geometry is that they define projectively normal embeddings of toric varieties.

<span class="mw-page-title-main">Algebraic combinatorics</span> Area of combinatorics

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Integral polytope</span> A convex polytope whose vertices all have integer Cartesian coordinates

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 called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.

A purely combinatorial approach to mirror symmetry was suggested by Victor Batyrev using the polar duality for -dimensional convex polyhedra. The most famous examples of the polar duality provide Platonic solids: e.g., the cube is dual to octahedron, the dodecahedron is dual to icosahedron. There is a natural bijection between the -dimensional faces of a -dimensional convex polyhedron and -dimensional faces of the dual polyhedron and one has . In Batyrev's combinatorial approach to mirror symmetry the polar duality is applied to special -dimensional convex lattice polytopes which are called reflexive polytopes.

Bruce Reznick is an American mathematician long on the faculty at the University of Illinois at Urbana–Champaign. He is a prolific researcher noted for his contributions to number theory and the combinatorial-algebraic-analytic investigations of polynomials. In July 2019, to mark his 66th birthday, a day long symposium "Bruce Reznick 66 fest: A mensch of Combinatorial-Algebraic Mathematics" was held at the University of Bern, Switzerland.