Cones and Polyhedra
Generators of Cones
- BoxElements(C): TorCon -> SetEnum
Given a simplicial cone \(C\), returns the coefficients of the points in the fundamental domain generated by the rays of \(C\), with respect to the rays.
- Example: Box Elements of a Simplicial Cone (ex-6a5b6c)
Run in calculator (opens in a new tab)
Let \(C\subset L\) be a simplicial cone and consider the sublattice \(L'\subset L\) generated by the rays of \(C\). We shall construct a representative set of points of \(L\) contained in the fundamental domain of \(L'\).
> C:=Cone([[1,-1,-3],[1,1,0],[1,0,1]]); > rays:=Rays(C); > Index(rays); 5 > pts:=BoxElements(C); > pts; { [ 0, 0, 0 ], [ 3/5, 3/5, 4/5 ], [ 2/5, 2/5, 1/5 ], [ 1/5, 1/5, 3/5 ], [ 4/5, 4/5, 2/5 ] } > {&+[rays[i] * c[i] : i in [1..3]] : c in pts}; { (2, 0, -2), (2, 0, -1), (1, 0, -1), (0, 0, 0), (1, 0, 0) }
Using these points we can construct the rational Ehrhart generating function counting the number of points as successive heights in \(C\):
> d:=Dimension(C); > heights:=[&+c : c in pts]; > delta:=[#[i : i in heights | i eq h] : h in [0..d - 1]]; > R<x>:=RationalFunctionField(Rationals()); > f:=&+[delta[i] * x^(i - 1) : i in [1..d]] / (1 - x)^d; > f; (-2*x^2 - 2*x - 1)/(x^3 - 3*x^2 + 3*x - 1) > K<t>:=PowerSeriesRing(Rationals(),10); > K ! f; 1 + 5*t + 14*t^2 + 28*t^3 + 47*t^4 + 71*t^5 + 100*t^6 + 134*t^7 + \\ 173*t^8 + 217*t^9 + O(t^10) > w:=Dual(Ambient(C)) ! [1,0,0]; > [NumberOfPoints(Polyhedron(C,w,i)) : i in [0..9]]; [ 1, 5, 14, 28, 47, 71, 100, 134, 173, 217 ]
- HilbertBasis(C): TorCon -> SeqEnum
- ZGenerators(C): TorCon -> SeqEnum
level: RngIntElt Default: Infinity()
If \(C\) lies in a toric lattice \(L\), then return a finite sequence of elements of \(L\) that generate \(C\) as a monoid. If specified, the parameter
levelrestricts the search for generators to that given level; this assumes that \(C\) is graded.
- RGenerators(C): TorCon -> SeqEnum
- MinimalRGenerators(C): TorCon -> SeqEnum
If \(C\) lies in a toric lattice \(L\), then return a finite sequence of elements of \(L\) that generate \(C\) over \({\mathbb{Q}}_+\). The list is forced to be minimal for
MinimalRGenerators, but might not be otherwise.
- Points(C, H, h): TorCon, TorLatElt, FldRatElt -> SetEnum
The set of integral lattice points in the cone \(C\) contained in the hyperplane given by the section determined by the dual lattice element \(H\) at height given by the rational number \(h\). The intersection of \(H\) with \(C\) is required to be compact.
- Example: Cone Generators in a Sublattice (ex-7976dc)
Run in calculator (opens in a new tab)
Here we find the generators of a cone in the sublattice spanned by its defining lattice points. First build some points in a toric lattice and make the cone they generate.
> L := ToricLattice(4); > B := [ L | [1,2,3,-3], [-1,0,1,0], [1,2,1,-2], [2,0,0,-1], [0,0,2,-1] ]; > L1,f := Sublattice(B); > Dimension(L1); 3 > C := Cone(B); > Points(Polytope(B)); { (1, 2, 1, -2), (2, 0, 0, -1), (-1, 0, 1, 0), (1, 2, 3, -3), (1, 0, 1, -1), (0, 0, 2, -1), (0, 1, 1, -1), (1, 1, 2, -2) } > ZGenerators(C); [ (-1, 0, 1, 0), (0, 1, 1, -1), (1, 2, 1, -2), (2, 0, 0, -1) ]
Using the embedding map \(f\), pull the cone back to the lattice span of \(C\).
> C1 := C @@ f;
In the smaller lattice, this cone is nonsingular.
> IsNonsingular(C1); true
We can find out which points generate the cone in the smaller lattice and compare them with the generators of the original cone.
> B1 := ZGenerators(C1); > B1; [ (-1, 0, 1), (1, 1, 0), (2, 0, -1) ] > [ Index(B,Image(f,b)) : b in B1 ]; [ 2, 3, 4 ]
- QuotientGenerators(C): TorCon -> SetEnum
Let \(C\subset L\) be a simplicial cone of maximum dimension in the lattice \(L\). Let \(L'\subset L\) be the sublattice generated by the rays of \(C\). This intrinsic returns a sequence of generators for the torsion of \(L / L'\); the generators are expressed in terms of the basis given by the rays of \(C\).
- Example: Cone of a Cyclic Quotient Singularity (ex-badd91)
Run in calculator (opens in a new tab)
Consider the cyclic quotient singularity \(1/3(1,1,2)\). We will begin by constructing the corresponding cone \(C\).
> L:=ToricLattice(3); > v:=L ! [1/3,1/3,2/3]; > N,emb:=AddVectorToLattice(v); > C:=Image(emb,PositiveQuadrant(L)); > C; Cone C with 3 generators: (1, 0, 0), (0, 1, 0), (1, 1, 3) > IsIsolated(C); true > IsQFactorial(C); true > IsTerminal(C); true
Now we reverse this operation: we take the cone \(C\) and recognise that it corresponds to \(1/3(1,1,2)\).
> QuotientGenerators(C); { [ 2/3, 2/3, 1/3 ] }
Of course, the generators are defined only up to multiplication by units in \(\mu_3\).
Properties of Polyhedra
- CompactPart(P): TorPol -> TorPol
The polytope defined by taking the convex hull of the vertices of the polyhedron \(P\). This is the smallest polytope which can occur as a factor in an expression of \(P\) as the Minkowski sum of a polytope and a cone.
- IntegralPart(P): TorPol -> TorPol
The polyhedron defined by taking the convex hull of the integral points contained in the polyhedron \(P\).
- Example: Polar Polyhedron of a Polytope (ex-a585a6)
Run in calculator (opens in a new tab)
One can build a polytope as the convex hull of a finite sequence of points—these may be elements of a toric lattice or simply sequences of integer or rational coefficients.
> P := Polytope([[-4,2,1],[0,3,4],[3,1,-3],[3,0,0],[2,-1,1]]);
The polar polyhedron comprises dual vectors that evaluate to at least \(-1\) on \(P\). It is compact if and only if the origin lies in the interior of \(P\).
> D := Polar(P); > D; 3-dimensional polyhedron D with 3-dimensional finite part with 5 vertices: ( 1/2, 1, -1), (-1/3, 1/2, 1/6), (-1/3, 1/21, -2/7), (-1/3, -3/13, -1/13), (1/67, -37/67, 11/67) and 3-dimensional infinite part given by a cone with 3 minimal generators: ( 1, 2, 0), ( 2, 9, 5), ( 7, 9, 10)
Since \(D\) is infinite, there is no intrinsic to list its integral points, but one can determine whether it contains integral points at all.
> HasIntegralPoint(D); true
Computing the span of all the integral points of \(D\) is possible.
> IntegralPart(D); 3-dimensional polyhedron with 3-dimensional finite part with 6 vertices: (0, 0, 0), (0, 1, 0), (0, 2, 1), (1, 1, 1), (1, 2, -1), (2, 2, 3) and 3-dimensional infinite part given by a cone with 3 minimal generators: (1, 2, 0), (2, 9, 5), (7, 9, 10)
The compact and infinite parts of \(D\) can be recovered.
> cD := CompactPart(D); > cD; 3-dimensional polytope cD with 5 vertices: ( 1/2, 1, -1), (-1/3, 1/2, 1/6), (-1/3, 1/21, -2/7), (-1/3, -3/13, -1/13), (1/67, -37/67, 11/67)
Polytopes are special cases of polyhedra (those whose infinite tail cone is the zero cone, or equivalently those that are compact), and the distinction can be determined.
> IsPolytope(cD); true > IsPolytope(D); false
- Example: Polyhedron from a Cone (ex-d24d32)
Run in calculator (opens in a new tab)
> C:=Cone([[0,1,0],[0,1,1],[1,1,2],[1,1,4]]); > P:=Polyhedron(C); > P; 2-dimensional polyhedron P with 1-dimensional finite part with 2 vertices: (1, 2), (1, 4) and 2-dimensional infinite part given by a cone with 2 minimal generators: (1, 0), (1, 1)
> CC:=Cone([[1,0],[1,1]]); > QQ:=Polytope([[1,2],[1,4]]); > PP:=CC + QQ; > PP; 2-dimensional polyhedron PP with 1-dimensional finite part with 2 vertices: (1, 2), (1, 4) and 2-dimensional infinite part given by a cone with 2 minimal generators: (1, 0), (1, 1)
But there’s a potential catch.
> PP eq P; false > Ambient(PP); 2-dimensional toric lattice Z^2 > Ambient(P); 2-dimensional toric lattice ker <1, 0, 0> > P:=ChangeAmbient(P,Ambient(PP)); > PP eq P; true
The ambients are different simply because of the method of construction of the two polyhedra, but they can be forced into the same space.
- IsMaximumDimensional(C): TorCon -> BoolElt
- IsMaximumDimensional(P): TorPol -> BoolElt
Return
trueif and only if the cone \(C\) or polyhedron \(P\) has dimension equal to that of its ambient lattice.
- IsStrictlyConvex(C): TorCon -> BoolElt
Return
trueif and only if the cone \(C\) is strictly convex; that is, if there exists a hyperplane \(H\) such that \(C\) is contained on one side of \(H\) and \(C\) meets \(H\) in single point \(0\).
- IsLinearSpace(C): TorCon -> BoolElt
- IsLinearSpace(P): TorPol -> BoolElt
Return
trueif and only if the cone \(C\) or the polyhedron \(P\) is a linear space.
- IsSimplicial(C): TorCon -> BoolElt
- IsSimplicial(P): TorPol -> BoolElt
Return
trueif and only if the cone \(C\) or the polyhedron \(P\) is simplicial.
- IsAffineLinear(P): TorPol -> BoolElt
Return
trueif and only if the polyhedron \(P\) is an affine linear space.
- IsZero(C): TorCon -> BoolElt
Return
trueif and only if the cone \(C\) is supported at the origin of its ambient toric lattice.
- ContainsZero(P): TorPol -> BoolElt
Return
trueif and only if the polyhedron \(P\) contains the origin strictly in its interior.
- IsPointed(P): TorPol -> BoolElt
Returns
trueiff the polyhedron \(P\) is pointed, i.e. if it is empty of has a vertex.
Attributes of Polyhedra
- IsPolytope(P): TorPol -> BoolElt
Returns
trueif and only if the polyhedron \(P\) is a polytope; that is, if and only if \(P\) is compact.
- Dimension(C): TorCon -> RngIntElt
- Dimension(P): TorPol -> RngIntElt
The dimension of the toric cone \(C\) or polyhedron \(P\).
- Degree(P): TorPol -> RngIntElt
- Codegree(P): TorPol -> RngIntElt
The degree and codegree of the integral polytope \(P\). The codegree is equal to the smallest dilation \(k\in{\mathbb{Z}}_{>0}\) such that \(kP\) contains an interior lattice point.
- Index(C): TorCon -> RngIntElt
The index of the sublattice generated by the minimal \({\bf R}\)-generators of the cone \(C\) in its linear span.
- Width(P): TorPol -> FldRatElt, SetEnum
- Width(P, u): TorPol, TorLatElt -> FldRatElt
The width of a polytope \(P\) in a lattice \(L\) with respect to an element \(u\in L^\vee\) in the dual lattice is the different \(\max\{u(v) : v\in P\} - \min\{u(v) : v\in P\}\). More generally, the width of \(P\) is defined to be the smallest possible width ranging over all non-zero \(u\).
- Example: Lattice Width of a Polytope (ex-d2ed42)
Run in calculator (opens in a new tab)
We calculate the (minimum) width of a polytope \(P\), along with all forms realising this width.
> P:=Polytope([[1,-2,3],[2,-4,-1],[5,-4,1],[-3,-3,-3]]); > width,us:=Width(P); > width; 1 > us; { (1, 3, -1), (-1, -3, 1) } > u:=Representative(us); > [u * v : v in Vertices(P)]; [ -8, -9, -8, -9 ]
In particular, the fact that \(P\) is of width one implies that \(P\) contains no (strict) interior lattice points:
> NumberOfInteriorPoints(P); 0
We calculate a change of basis to make the fact that \(P\) is of width one immediately apparent.
> phi:=ChangeBasis(u); > DefiningMatrix(phi); [ 1 0 1] [ 0 1 3] [ 0 0 -1] > Image(phi,P); 3-dimensional polytope with 4 vertices: ( 1, -2, -8), ( 2, -4, -9), ( 5, -4, -8), (-3, -3, -9)
- IsPyramid(P): TorPol -> BoolElt, TorLatElt, TorPol, Map, TorLatElt
Returns
trueiff the polytope \(P\) is a pyramid, i.e. if there exists a facet \(F\) and an integral vertex \(u\in P\) such that \(P = {\rm conv}(F \cup \{u\})\), where \(u\) is at height one relative to \(F\). If \(P\) is a pyramid, then a choice of apex \(u\), base facet \(F\), an element \(\varphi\) in \(GL_n({\mathbb{Z}})\), and a lattice translation \(v\) are also returned. These are chosen such that \(\varphi(P) + v\) sends \(u\) to \((1,0,\ldots,0)\) and embeds \(F\) in the \((n-1)\)-dimensional sublattice generated by \((0,1,\ldots,0),\ldots,(0,0,\ldots,1)\).
- Pyramid(P): TorPol -> TorPol, Map, Map, Map, Map
The pyramid given by embedding the polyhedron \(P\) in the lattice \({\mathbb{Z}}\times L\) (where \(L\) is the ambient lattice containing \(P\)) and adding the point \((1,0,\ldots,0)\) to the convex hull. Also gives the two embedding maps and the two projection maps of the underlying lattices.
- Example: Recognising a Pyramid (ex-0b2d83)
Run in calculator (opens in a new tab)
We begin with a \(3\)-dimensional polytope \(P\) living in a \(4\)-dimensional lattice:
> P:=Polytope([ > [ -3, -2, -1, 3 ], > [ 2, 2, 0, -3 ], > [ 3, 0, -2, 0 ], > [ 4, 1, 61, -121 ] > ]); > Dimension(P); 3
Next we see that \(P\) is a pyramid \(P={\rm conv}(F\cup\{u\})\). We recover the \(2\)-dimensional polytope \(F\) and the corresponding apex \(u\).
> bool,u,F,phi,v:=IsPyramid(P); > bool; true > F; 2-dimensional polytope F with 3 vertices: ( 2, 2, 0, -3), ( 3, 0, -2, 0), ( 4, 1, 61, -121) > u; (-3, -2, -1, 3)
We make this pyramid construction explicit by calculating \(\varphi(P)+v\):
> Image(phi,P) + v; 3-dimensional polytope with 4 vertices: (1, 0, 0, 0), (0, 0, 0, 0), (0, 1, -2, -1), (0, 2, -1, -1)
Let us consider \(F\) as a simplex in a \(2\)-dimensional lattice; we see that it is equivalent to the standard empty triangle \(S\).
> F:=PolyhedronInSublattice(F); > F; 2-dimensional polytope F with 3 vertices: (2, 0), (3, -1), (4, -1) > NumberOfInteriorPoints(F); 0 > S:=Polytope([ > [ 0, 0 ], > [ 1, 0 ], > [ 0, 1 ] > ]); > bool:=IsEquivalent(F,S); > bool; true
Since \(P\) is equivalent to a pyramid over \(S\), we have that the Ehrhart \(\delta\)-vector (also known as the \(h^*\)-vector) of \(P\) must be equal to \((1,0,0,0)\). We verify this fact:
> EhrhartDeltaVector(P); [ 1, 0, 0, 0 ]
- VertexEdgeIncidenceMatrix(P): TorPol -> ModMatRngElt
The vertex–edge incidence matrix of the polyhedron \(P\), where the \(i,j\)-th entry is \(1\) if and only if the \(i\)-th vertex is contained in the \(j\)-th edge.
- VertexFacetIncidenceMatrix(P): TorPol -> ModMatRngElt
The vertex–facet incidence matrix of the polyhedron \(P\), where the \(i,j\)-th entry is \(1\) if and only if the \(i\)-th vertex is contained in the \(j\)-th facet.
Combinatorics of Polyhedral Complexes
- Ambient(C): TorCon -> TorLat
- Ambient(P): TorPol -> TorLat
The ambient toric lattice of the toric cone \(C\) or polyhedron \(P\).
- ChangeAmbient(C, L): TorCon, TorLat -> TorCon
- ChangeAmbient(P, L): TorPol, TorLat -> TorPol
Make a cone or polyhedron identical to the toric cone \(C\) or polyhedron \(P\) but lying in the toric lattice \(L\); the identification of the existing ambient toric lattice with \(L\) is simply by identification of the two standard bases and it requires the dimensions of the two spaces to be equal.