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: Toric Cone Boxelements Example (ex-6a5b6c)#
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: Toric Cone Sublattice Example (ex-7976dc)#
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: Toric Cone Quotient Generators Example (ex-badd91)#
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\).
- InfinitePart(P): TorPol -> TorCon#
The tail cone of the polyhedron \(P\).
- IsEmpty(P): TorPol -> BoolElt#
Return
trueif and only if the polyhedron \(P\) is empty.
- Example: Toric Polar Cone Example (ex-a585a6)#
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: Toric Polyhedron Example (ex-d24d32)#
> 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.
- IsSimplex(P): TorPol -> BoolElt#
Return
trueif and only if the polyhedron \(P\) is a simplex.
- IsSimple(P): TorPol -> BoolElt#
Return
trueif and only if the polyhedron \(P\) is simple.
- 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.
- IsFlag(P): TorPol -> BoolElt#
Returns
trueiff the simplicial polytope \(P\) is a flag polytope.
- IsPerfectlyCentered(P): TorPol -> BoolElt#
Returns
trueiff the polyhedron \(P\) is a polytope containing the origin strictly in its interior such that for any non-empty face \(F\) of \(P\), the intersection \({\rm relint}(F)\) with the (outer) normal cone is non-empty.
- IsIntegrallyClosed(P): TorPol -> BoolElt#
Returns
trueiff the polytope \(P\) is integrally closed; i.e. if every lattice point in \(kP\) can be written as the sum of \(k\) lattice points in \(P\), for all \(k\in{\mathbb{Z}}_{\geq 0}\).
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: Toric Width Example (ex-d2ed42)#
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: Toric Pyramid Example (ex-0b2d83)#
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.
- VertexFacetHeightMatrix(P): TorPol -> AlgMatElt#
The vertex–facet height matrix of the polyhedron \(P\), where the \(i,j\)-th entry is equal to the lattice height of the \(i\)-th vertex over the \(j\)-th facet.
- EdgeFacetIncidenceMatrix(P): TorPol -> ModMatRngElt#
The edge–facet incidence matrix of the polyhedron \(P\), where the \(i,j\)-th entry is \(1\) if and only if the \(i\)-th edge 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.