The Combinatorics of Polytopes
Points in Polytopes and Polyhedra
Given a polygon, one might want to know how many integral points it contains, and one might want to list them. These are computed by different algorithms (although one can of course list the points and then count them). For point counting we use the methods of Barvinok and Pommersheim ([BP99]), as described in [DLHTY04]. More generally, one might want to know the number of points in integral dilations of a polytope: these numbers are the coefficients of a generating function, the Ehrhart series; this is discussed in a later section.
- v in C: TorLatElt, TorCon -> BoolElt
- v in P: TorLatElt, TorPol -> BoolElt
Returns
trueif and only if the point \(v\) is contained in the cone \(C\) or polyhedron \(P\).
- IsInInterior(v, C): TorLatElt, TorCon -> BoolElt
- IsInInterior(v, P): TorLatElt, TorPol -> BoolElt
Returns
trueif and only if the point \(v\) lies in the strict interior of the cone \(C\) or polyhedron \(P\).
- IsOnBoundary(v, C): TorLatElt, TorCon -> BoolElt
- IsOnBoundary(v, P): TorLatElt, TorPol -> BoolElt
Returns
trueif and only if the point \(v\) lies on the (relative) boundary of the cone \(C\) or polyhedron \(P\).
- HasIntegralPoint(P): TorPol -> BoolElt
Returns
trueif and only if the polyhedron \(P\) contains an integral lattice point.
- Points(P): TorPol -> SeqEnum[TorLatElt]
- InteriorPoints(P): TorPol -> SeqEnum[TorLatElt]
- BoundaryPoints(P): TorPol -> SeqEnum[TorLatElt]
The integral toric lattice points, the strictly interior lattice points, or the boundary lattice points of the polytope \(P\).
Ehrhart Theory of Polytopes
- EhrhartSeries(P): TorPol -> FldFunRatUElt
The rational generating function \({\rm Ehr}_P(t)\) of the Ehrhart series for the polytope \(P\). The coefficient \(c_m\) of \(t^m\) in the power-series expansion of \({\rm Ehr}_P(t)\) is equal to the number of lattice points in \(mP\).
- EhrhartDeltaVector(P): TorPol -> SeqEnum
The Ehrhart \(\delta\)-vector (also known as the \(h^*\)-vector) for the polytope \(P\). This is a sequence of integers defining the numerator of the Ehrhart generating function \({\rm Ehr}_P(t)\) of \(P\). More precisely, if \(n={\rm dim}(P)\) and \(k\in{\mathbb{Z}}_{>0}\) is the smallest dilation of \(P\) such that \(kP\) is a lattice polytope, then \({\rm Ehr}_P(t) = (\delta_0 + \delta_1t + \ldots + \delta_{k(n+1)-1}t^{k(n+1)-1}) / (1-t^k)^{n+1}\).
- EhrhartPolynomial(P): TorPol -> [RngUPolElt]
A sequence representing the Ehrhart (quasi-)polynomial for the polytope \(P\). That is, a sequence of polynomials \([p_0,\dots,p_{r-1}]\) of length \(r\), the quasi-period of the Ehrhart polynomial, so that the number of lattice points of the dilation \(mP\) is the value of \(p_{s}(k)\), where \(m=kr+s\) is the Euclidean division of \(m\) by \(r\); in other words, \(s\) is the least residue of \(m\) modulo \(r\). Note that since Magma indexes sequences from \(1\), we have that \(p_i =\)
EhrhartPolynomial(P)[i+1].
Isomorphism Testing and Normal Forms for Polytopes
It is often necessary to determine whether two convex polytopes \(P\) and \(Q\), embedded in a lattice \(\Lambda\), are isomorphic with respect to a lattice automorphism; that is, whether there exists an element of \(GL_n({\mathbb{Z}})\) sending \(P\) to \(Q\). For example, in toric geometry lattice polytopes form one of the key constructions of projective toric varieties, and any classification must somehow address the issue of whether there exists an automorphism of the underlying lattice sending \(P\) to \(Q\).
In general, any isomorphism problem can be solved in one of two ways: on a case-by-case basis by constructing an explicit isomorphism between the two objects, or by determining a normal form for each isomorphism class. Both approaches are supported.
The first approach – dynamically constructing a lattice-preserving isomorphism in \(GL_n({\mathbb{Z}})\) between the two polytopes – has the advantage that it works equally well for rational polytopes and for polytopes of non-zero codimension. The algorithm works by reducing the problem to a graph isomorphism question to which well-developed tools such as Brendan McKay’s Nauty software [McKb, McK81] can then be applied.
The second approach – to compute a normal form \({\rm NF}(P)\) for each isomorphism class – works only for lattice polytopes of codimension zero. The normal form algorithm used by Magma is based on one developed by Kreuzer and Skarke for their Palp software [KS04]. Briefly, row and column permutations are applied to the vertex–facet pairing matrix of \(P\), placing it in a form that is maximal with respect to a certain ordering. This in turn defines an order in which to list the vertices of \(P\); the choice of basis is fixed by taking the Hermite normal form.
Slightly more generally, one may wish to consider polytopes up to change of basis and translation, i.e. up to affine equivalence. Once again Magma offers two solutions. Affine equivalence between two (possibly rational) polytopes can be determined on a case-by-case basis, or an affine normal form can be calculated. All the algorithms are described in detail in [GK13].
- IsIsomorphic(P, Q): TorPol, TorPol -> BoolElt, Map
Returns
trueiff the polytopes \(P\) and \(Q\) are isomorphic, i.e. if there exists an element in \(GL_n({\mathbb{Z}})\) sending \(P\) to \(Q\). If true, also gives an isomorphism from \(P\) to \(Q\). The polytopes may be rational, and need not be of maximum dimension in the ambient lattice.
- Example: Isomorphism Testing for Polytopes (ex-66ee55)
Run in calculator (opens in a new tab)
We begin by creating a random rational \(2\)-dimensional polytope in a \(3\)-dimensional lattice. We shall then apply a random change of basis to \(P\) to generate an isomorphic polytope \(Q\).
> P:=RandomPolytope(3,3,4) / 2; > P; 2-dimensional polytope P with 3 generators: ( 0, -2, 1), ( 0, 1/2, -2), (-1, 3/2, 0) > Q:=P * RandomGLnZ(3,3,3); > Q; 2-dimensional polytope Q with 3 generators: ( -2, -3, -1), (1/2, 5/2, -3/2), (5/2, 3/2, 5/2)
Now we recover the isomorphism between these two polytopes:
> bool,phi:=IsIsomorphic(P,Q); > bool; true > Image(phi,P) eq Q; true
The lattice isomorphism can easily be recovered as a matrix in \(GL_3({\mathbb{Z}})\):
> M:=DefiningMatrix(phi); > M; [-1 0 -1] [ 1 1 1] [ 0 -1 1] > P * M eq Q; true
- IsEquivalent(P, Q): TorPol, TorPol -> BoolElt, Map, TorLatElt
Returns
trueiff the polytopes \(P\) and \(Q\) are equivalent, i.e. if there exists an element in \(GL_n({\mathbb{Z}})\) and lattice translation sending \(P\) to \(Q\). If true, also gives the map as a lattice map \(\varphi\) and translation \(v\) such that \(\varphi(P) + v = Q\).
- NormalForm(P): TorPol -> SeqEnum, GrpPermElt
- PALPNormalForm(P): TorPol -> SeqEnum, GrpPermElt
The Palp normal form of the maximum dimensional lattice polytope \(P\). This is given as a sequence of lattice points equal to the (ordered) vertices of \({\rm NF}(P)\). Also gives the permutation of the vertices of \(P\) used to calculate this normal form.
- Example: Normal Form of a Lattice Polytope (ex-3bf045)
Run in calculator (opens in a new tab)
We start by computing the normal form of a lattice polytope.
> P:=Polytope([[62,23],[-8,-3],[-27,-10]]); > NF:=NormalForm(P); > NF; [ (1, 0), (0, 1), (-2, -1) ]
People familiar with toric geometry will recognise this as the weighted projective space \({\mathbb{P}}(1,1,2)\); we can verify this in one line of code by comparing the normal forms:
> NormalForm(PolytopeOfWPS([1,1,2])) eq NF; true
Now we exhibit one way to recover the change of basis that sends \(P\) to its normal form \({\rm NF}(P)\). We need to capture the permutation of the vertices, so we redo the calculation and this time we save the second return value:
> NF,perm:=NormalForm(P); > perm; (1, 3)
The change of basis in \(GL_2({\mathbb{Z}})\) is now trivial to compute:
> vertsP:=PermuteSequence(Vertices(P),perm); > VP:=Matrix(vertsP); > VQ:=Matrix(NF); > M:=Solution(Transpose(VP),Transpose(VQ)); > M:=Transpose(M); > M; [ -3 10] [ 8 -27] > P * M; 2-dimensional polytope with 3 vertices: (-2, -1), ( 0, 1), ( 1, 0)
- AffineNormalForm(P): TorPol -> SeqEnum, GrpPermElt
The affine normal form of the maximum dimensional lattice polytope \(P\). This is given as a sequence of lattice points equal to the (ordered) vertices of \({\rm AffNF}(P)\). Also gives the permutation of the vertices of \(P\) used to calculate this affine normal form.
- Example: Classifying Polygons by Affine Normal Form (ex-7e87a2)
Run in calculator (opens in a new tab)
We wish to classify all polygons in an \([0,N]\times [0,N]\) box but not contained in a smaller \([0,N-1]\times [0,N-1]\) box, up to change of basis and translation. To do this we make use of the affine normal form. We will perform the classification for \(N\leq 4\).
> procedure classify_polygons_recurse(P,~class,allclass) > for v in Vertices(P) do > Q:=Polytope(Exclude(Points(P),v)); > if Dimension(Q) eq 2 then > AffNF:=AffineNormalForm(Q); > if not AffNF in class and > not &or[AffNF in subclass : subclass in allclass] then > Include(~class,AffNF); > $$(Q,~class,allclass); > end if; > end if; > end for; > end procedure; > > function classify_polygons(N) > allclass:=[]; > for i in [1..N] do > B:=Polytope([[0,0],[i,0],[0,i],[i,i]]); > class:={AffineNormalForm(B)}; > classify_polygons_recurse(B,~class,allclass); > Append(~allclass,class); > end for; > return allclass; > end function; > > classification:=classify_polygons(4); > [#class : class in classification]; [ 2, 15, 131, 1369 ]
Automorphisms of a Polytope
- AutomorphismGroup(P): TorPol -> GrpMat
The subgroup of \(GL(n,\bf{Z})\) (acting on the ambient lattice) which leaves the polyhedron \(P\) unchanged.
- Example: Automorphism Group of a Polytope (ex-49a1bb)
Run in calculator (opens in a new tab)
> P:=CrossPolytope(2); > P; 2-dimensional polytope P with 4 vertices: ( 1, 0), ( 0, 1), (-1, 0), ( 0, -1) > AutomorphismGroup(P); MatrixGroup(2, Integer Ring) Generators: [0 1] [1 0] [ 0 1] [-1 0]