# 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'$. ```magma > 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$: ```magma > d:=Dimension(C); > heights:=[&+c : c in pts]; > delta:=[#[i : i in heights | i eq h] : h in [0..d - 1]]; > R:=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:=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` ```magma 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 `level` restricts 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. ```magma > 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$. ```magma > C1 := C @@ f; ``` In the smaller lattice, this cone is nonsingular. ```magma > 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. ```magma > 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$. ```magma > 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)$. ```magma > 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 `true` if 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. ```magma > 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$. ```magma > 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. ```magma > HasIntegralPoint(D); true ``` Computing the span of all the integral points of $D$ is possible. ```magma > 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. ```magma > 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. ```magma > IsPolytope(cD); true > IsPolytope(D); false ``` ### `Example: Toric Polyhedron Example (ex-d24d32)` ```magma > 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) ``` ```magma > 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. ```magma > 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 `true` if and only if the cone $C$ or polyhedron $P$ has dimension equal to that of its ambient lattice. ### `IsStrictlyConvex(C): TorCon -> BoolElt` Return `true` if 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 `true` if and only if the cone $C$ or the polyhedron $P$ is a linear space. ### `IsSimplicial(C): TorCon -> BoolElt` ### `IsSimplicial(P): TorPol -> BoolElt` Return `true` if and only if the cone $C$ or the polyhedron $P$ is simplicial. ### `IsSimplex(P): TorPol -> BoolElt` Return `true` if and only if the polyhedron $P$ is a simplex. ### `IsSimple(P): TorPol -> BoolElt` Return `true` if and only if the polyhedron $P$ is simple. ### `IsAffineLinear(P): TorPol -> BoolElt` Return `true` if and only if the polyhedron $P$ is an affine linear space. ### `IsZero(C): TorCon -> BoolElt` Return `true` if and only if the cone $C$ is supported at the origin of its ambient toric lattice. ### `ContainsZero(P): TorPol -> BoolElt` Return `true` if and only if the polyhedron $P$ contains the origin strictly in its interior. ### `IsPointed(P): TorPol -> BoolElt` Returns `true` iff the polyhedron $P$ is pointed, i.e. if it is empty of has a vertex. ### `IsFlag(P): TorPol -> BoolElt` Returns `true` iff the simplicial polytope $P$ is a flag polytope. ### `IsPerfectlyCentered(P): TorPol -> BoolElt` Returns `true` iff 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 `true` iff 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 `true` if 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. ```magma > 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: ```magma > NumberOfInteriorPoints(P); 0 ``` We calculate a change of basis to make the fact that $P$ is of width one immediately apparent. ```magma > 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 `true` iff 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: ```magma > 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$. ```magma > 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$: ```magma > 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$. ```magma > 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: ```magma > 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.