Polyhedral Fans

Introduction

Let $\mathbb{F}$ be an ordered field; the default is that $\mathbb{F}=\mathbb{Q}$ is the field of rational numbers and other fields are not yet supported everywhere in the implementation.

A nonempty finite collection $\mathcal{F}$ of (polyhedral) cones in $\mathbb{F}^n$, for $n$ fixed, is a (polyhedral) fan if

  • the set $\mathcal{F}$ is closed with respect to taking faces and
  • if $C,D\in\mathcal{F}$ then $C\cap D$ is a face of both, $C$ and $D$.

Construction

To construct a polyhedral fan, you must pass the rays of each cone in the fan, along with an IncidenceMatrix encoding which rays generate which cones.

polyhedral_fanFunction
polyhedral_fan(T, Rays::AbstractCollection[RayVector], LS::Union{AbstractCollection[RayVector], Nothing}, Incidence::IncidenceMatrix) where T<:scalar_types

Assemble a polyhedral fan from ray generators, lineality generators, and an IncidenceMatrix indicating which rays form a cone.

Arguments

  • T: Type or parent Field of scalar to use, defaults to QQFieldElem.
  • Rays::AbstractCollection[RayVector]: Rays generating the cones of the fan; encoded row-wise as representative vectors.
  • LS::AbstractCollection[RayVector]: Contains row-wise generators of the lineality space of the fan. (optional argument)
  • Cones::IncidenceMatrix: An incidence matrix; there is a 1 at position (i,j) if cone i has ray j as extremal ray, and 0 otherwise.

Examples

To obtain the upper half-space of the plane:

julia> R = [1 0; 1 1; 0 1; -1 0; 0 -1];

julia> IM=IncidenceMatrix([[1,2],[2,3],[3,4],[4,5],[1,5]]);

julia> PF=polyhedral_fan(IM, R)
Polyhedral fan in ambient dimension 2

Polyhedral fan with lineality space:

julia> R = [1 0 0; 0 0 1];

julia> L = [0 1 0];

julia> IM = IncidenceMatrix([[1],[2]]);

julia> PF=polyhedral_fan(IM, R, L)
Polyhedral fan in ambient dimension 3

julia> lineality_dim(PF)
1
source
polyhedral_fan(cones::AbstractVector{Cone{T}}) where T<:scalar_types

Assemble a polyhedral fan from a non-empty list of cones.

source
polyhedral_fan(v::NormalToricVarietyType)

Return the fan of an abstract normal toric variety v.

Examples

julia> p2 = projective_space(NormalToricVariety, 2)
Normal toric variety

julia> polyhedral_fan(p2)
Polyhedral fan in ambient dimension 2
source
polyhedral_fan_from_rays_actionFunction
polyhedral_fan_from_rays_action([::Union{Type{T}, Field} = QQFieldElem,] Rays::AbstractCollection[RayVector], MC_reps::IncidenceMatrix, perms::AbstractVector{PermGroupElem}) where T<:scalar_types

Construct a polyhedral fan with a group action.

Arguments

  • The first argument either specifies the Type of its coefficients or their

parent Field.

  • Rays: The rays of the fan
  • MC_reps: IncidenceMatrix whose rows give the indices of the rays forming representatives of the maximal cones under the group action.
  • perms: A vector of permutations PermGroupElem that form generators of the group acting on the rays of the fan.
source
normal_fanMethod
normal_fan(P::Polyhedron)

Return the normal fan of P. The maximal cones of the normal fan of P are dual to the edge cones at the vertices of P.

Examples

The rays of a normal fan of a cube point in every positive and negative unit direction.

julia> C = cube(3);

julia> NF = normal_fan(C)
Polyhedral fan in ambient dimension 3

julia> rays(NF)
6-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0, 0]
 [-1, 0, 0]
 [0, 1, 0]
 [0, -1, 0]
 [0, 0, 1]
 [0, 0, -1]
source
face_fanMethod
face_fan(P::Polyhedron)

Return the face fan of P. The polytope P has to contain the origin, then the maximal cones of the face fan of P are the cones over the facets of P.

Examples

By definition, this bounded polyhedron's number of facets equals the amount of maximal cones of its face fan.

julia> C = cross_polytope(3);

julia> FF = face_fan(C)
Polyhedral fan in ambient dimension 3

julia> n_maximal_cones(FF) == n_facets(C)
true
source

Auxiliary functions

ambient_dimMethod
ambient_dim(PF::PolyhedralFan)

Return the ambient dimension PF, which is the dimension of the embedding space.

This is equal to the dimension of the fan if and only if the fan is full-dimensional.

Examples

The normal fan of the 4-cube is embedded in the same ambient space.

julia> ambient_dim(normal_fan(cube(4)))
4
source
ambient_dim(TropV::TropicalVariety)

See ambient_dim(::PolyhedralComplex).

source
arrangement_polynomialFunction
arrangement_polynomial([ring::MPolyRing{<: FieldElem},] A::MatElem{<: FieldElem})

Given some $A\in\mathbb{F}^{n\times d},$ return the product of the linear forms corresponding to the rows.

Let $A$ be a $n\times d$ matrix with entries from a field $\mathbb{F}$. The rows of $A$ are the normal vectors for a hyperplane arrangement $\mathcal{A} = \{H_{1},\dots,H_{n}:H_{i}\subset \mathbb{F}^{d}\}.$ We have $H_{i} = V(\alpha_{i})$, where $\alpha_{i}\in\mathbb{F}[x_{1},\dots,x_{d}]$ is a linear form whose coefficients are the entries of the $i$th row.

Then we have $\cup_{H_{i}\in\mathcal{A}}H_{i} = V(\Pi^{n}_{i=1}\alpha_{i}).$

Optionally one can select to use columns instead of rows in the following way:

arrangement_polynomial(...  ; hyperplanes=:in_cols)

Example using standard ring and then custom ring.

julia> A = matrix(QQ,[1 2 5//2; 0 0 1; 2 3 2; 1//2 3 5; 3 1 2; 7 8 1])
[   1   2   5//2]
[   0   0      1]
[   2   3      2]
[1//2   3      5]
[   3   1      2]
[   7   8      1]

julia> factor(arrangement_polynomial(A))
(1//4) * (2*x1 + 3*x2 + 2*x3) * (7*x1 + 8*x2 + x3) * (x1 + 6*x2 + 10*x3) * (2*x1 + 4*x2 + 5*x3) * x3 * (3*x1 + x2 + 2*x3)

julia> R,_ = polynomial_ring(QQ, [:x, :y, :z])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])

julia> factor(arrangement_polynomial(R, A))
(1//4) * (2*x + 3*y + 2*z) * (7*x + 8*y + z) * (x + 6*y + 10*z) * (2*x + 4*y + 5*z) * z * (3*x + y + 2*z)

To use the columns instead, proceed in the following way:

julia> A = matrix(QQ,[1 0 2 1//2 3 7;2 0 3 3 1 8;5//2 1 2 5 2 1]);

julia> factor(arrangement_polynomial(A; hyperplanes=:in_cols))
(1//4) * (2*x1 + 3*x2 + 2*x3) * (7*x1 + 8*x2 + x3) * (x1 + 6*x2 + 10*x3) * (2*x1 + 4*x2 + 5*x3) * x3 * (3*x1 + x2 + 2*x3)
source
dimMethod
dim(PF::PolyhedralFan)

Return the dimension of PF.

Examples

This fan in the plane contains a 2-dimensional cone and is thus 2-dimensional itself.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> dim(PF)
2
source
f_vectorMethod
f_vector(PF::PolyhedralFan)

Compute the vector $(f₁,f₂,...,f_{dim(PF)-1})$ where $f_i$ is the number of faces of $PF$ of dimension $i$.

Examples

The f-vector of the normal fan of a polytope is the reverse of the f-vector of the polytope.

julia> c = cube(3)
Polytope in ambient dimension 3

julia> f_vector(c)
3-element Vector{ZZRingElem}:
 8
 12
 6


julia> nfc = normal_fan(c)
Polyhedral fan in ambient dimension 3

julia> f_vector(nfc)
3-element Vector{ZZRingElem}:
 6
 12
 8
source
is_completeMethod
is_complete(PF::PolyhedralFan)

Determine whether PF is complete, i.e. its support, the set-theoretic union of its cones, covers the whole space.

Examples

Normal fans of polytopes are complete.

julia> is_complete(normal_fan(cube(3)))
true
source
is_pointedMethod
is_pointed(PF::PolyhedralFan)

Determine whether PF is pointed, i.e. all its cones are pointed.

Examples

The normal fan of a non-fulldimensional polytope is not pointed.

julia> C = convex_hull([0 0; 1 0])
Polyhedron in ambient dimension 2

julia> is_fulldimensional(C)
false

julia> nf = normal_fan(C)
Polyhedral fan in ambient dimension 2

julia> is_pointed(nf)
false

julia> lineality_dim(nf)
1
source
is_regularMethod
is_regular(PF::PolyhedralFan)

Determine whether PF is regular, i.e. the normal fan of a polytope.

Examples

This fan is not complete and thus not regular.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> is_regular(PF)
false
source
is_simplicialMethod
is_simplicial(PF::PolyhedralFan)

Determine whether PF is simplicial, i.e. every cone should be generated by a basis of the ambient space.

Examples

The normal_fan of the cube is simplicial, while the face_fan is not.

julia> is_simplicial(normal_fan(cube(3)))
true

julia> is_simplicial(face_fan(cube(3)))
false
source
is_smoothMethod
is_smooth(PF::PolyhedralFan{QQFieldElem})

Determine whether PF is smooth.

Examples

Even though the cones of this fan cover the positive orthant together, one of these und thus the whole fan is not smooth.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2], [2, 3]]), [0 1; 2 1; 1 0]);

julia> is_smooth(PF)
false
source
lineality_dimMethod
lineality_dim(PF::PolyhedralFan)

Return the dimension of the lineality space of the polyhedral fan PF, i.e. the dimension of the largest linear subspace.

Examples

The dimension of the lineality space is zero if and only if the fan is pointed.

julia> C = convex_hull([0 0; 1 0])
Polyhedron in ambient dimension 2

julia> is_fulldimensional(C)
false

julia> nf = normal_fan(C)
Polyhedral fan in ambient dimension 2

julia> is_pointed(nf)
false

julia> lineality_dim(nf)
1
source
lineality_spaceMethod
lineality_space(PF::PolyhedralFan)

Return a non-redundant matrix whose rows are generators of the lineality space of PF.

Examples

This fan consists of two cones, one containing all the points with $y ≤ 0$ and one containing all the points with $y ≥ 0$. The fan's lineality is the common lineality of these two cones, i.e. in $x$-direction.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2, 3], [3, 4, 1]]), [1 0; 0 1; -1 0; 0 -1])
Polyhedral fan in ambient dimension 2

julia> lineality_space(PF)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0]
source
maximal_conesMethod
maximal_cones(PF::PolyhedralFan)

Return the maximal cones of PF.

Optionally IncidenceMatrix can be passed as a first argument to return the incidence matrix specifying the maximal cones of PF. In that case, the indices refer to the output of rays_modulo_lineality(Cone).

Examples

Here we ask for the the number of rays for each maximal cone of the face fan of the 3-cube and use that maximal_cones returns an iterator.

julia> PF = face_fan(cube(3));

julia> for c in maximal_cones(PF)
         println(n_rays(c))
       end
4
4
4
4
4
4

julia> maximal_cones(IncidenceMatrix, PF)
6×8 IncidenceMatrix
[1, 3, 5, 7]
[2, 4, 6, 8]
[1, 2, 5, 6]
[3, 4, 7, 8]
[1, 2, 3, 4]
[5, 6, 7, 8]
source
conesMethod
cones(PF::PolyhedralFan, cone_dim::Int)

Return an iterator over the cones of PF of dimension cone_dim.

Examples

The 12 edges of the 3-cube correspond to the 2-dimensional cones of its face fan:

julia> PF = face_fan(cube(3));

julia> cones(PF, 2)
12-element SubObjectIterator{Cone{QQFieldElem}}:
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
 Polyhedral cone in ambient dimension 3
source
conesMethod
cones(PF::PolyhedralFan)

Return the ray indices of all non-zero-dimensional cones in a polyhedral fan.

Examples

julia> PF = face_fan(cube(2))
Polyhedral fan in ambient dimension 2

julia> cones(PF)
8×4 IncidenceMatrix
[1, 3]
[2, 4]
[1, 2]
[3, 4]
[1]
[3]
[2]
[4]
source
n_maximal_conesMethod
n_maximal_cones(PF::PolyhedralFan)

Return the number of maximal cones of PF.

Examples

The cones given in this construction are non-redundant. Thus there are two maximal cones.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> n_maximal_cones(PF)
2
source
n_conesMethod
n_cones(PF::PolyhedralFan)

Return the number of cones of PF.

Examples

The cones given in this construction are non-redundant. There are six cones in this fan.

julia> PF = polyhedral_fan(IncidenceMatrix([[1, 2], [3]]), [1 0; 0 1; -1 -1])
Polyhedral fan in ambient dimension 2

julia> n_cones(PF)
4
source
n_raysMethod
n_rays(PF::PolyhedralFan)

Return the number of rays of PF.

Examples

The 3-cube has 8 vertices. Accordingly, its face fan has 8 rays.

julia> n_rays(face_fan(cube(3)))
8
source
raysMethod
rays([as::Type{T} = RayVector,] PF::PolyhedralFan)

Return the rays of PF. The rays are defined to be the one-dimensional faces of its cones, so if PF has lineality, there are no rays.

See also rays_modulo_lineality.

Optional arguments for as include

  • RayVector.

Examples

The rays of a normal fan of a cube point in every positive and negative unit direction.

julia> C = cube(3);

julia> NF = normal_fan(C);

julia> rays(NF)
6-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0, 0]
 [-1, 0, 0]
 [0, 1, 0]
 [0, -1, 0]
 [0, 0, 1]
 [0, 0, -1]

As for the Cone, the rays may be converted to a matrix using the matrix(ring, ...) function.

julia> C = cube(3);

julia> NF = normal_fan(C);

julia> matrix(QQ, rays(NF))
[ 1    0    0]
[-1    0    0]
[ 0    1    0]
[ 0   -1    0]
[ 0    0    1]
[ 0    0   -1]

The following fan has no rays:

julia> IM = IncidenceMatrix([[1,2],[2,3]]);

julia> R = [1 0 0; 0 1 0; -1 0 0];

julia> L = [0 0 1];

julia> PF = polyhedral_fan(IM, R, L)
Polyhedral fan in ambient dimension 3

julia> rays(PF)
0-element SubObjectIterator{RayVector{QQFieldElem}}
source
rays(TropV::TropicalVariety)

See rays(::PolyhedralComplex).

source
rays_modulo_linealityMethod
rays_modulo_lineality(as, F::PolyhedralFan)

Return the rays of the polyhedral fan F up to lineality as a NamedTuple with two iterators. If F has lineality L, then the iterator rays_modulo_lineality iterates over representatives of the rays of F/L. The iterator lineality_basis gives a basis of the lineality space L.

See also rays and lineality_space.

Examples

julia> P = convex_hull(QQFieldElem, [0 0; 1 0])
Polyhedron in ambient dimension 2

julia> NF = normal_fan(P)
Polyhedral fan in ambient dimension 2

julia> rmlF = rays_modulo_lineality(NF)
(rays_modulo_lineality = RayVector{QQFieldElem}[[1, 0], [-1, 0]], lineality_basis = RayVector{QQFieldElem}[[0, 1]])

julia> rmlF.rays_modulo_lineality
2-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0]
 [-1, 0]

julia> rmlF.lineality_basis
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [0, 1]

julia> rays(NF)
0-element SubObjectIterator{RayVector{QQFieldElem}}
source
rays_modulo_lineality(TropV::TropicalVariety)

See rays_modulo_lineality(::PolyhedralComplex).

source
primitive_collectionsMethod
primitive_collections(PF::PolyhedralFan)

Return the primitive collections of a polyhedral fan.

Examples

julia> primitive_collections(normal_fan(simplex(3)))
1-element Vector{Set{Int64}}:
 Set([4, 2, 3, 1])
source
star_subdivisionMethod
star_subdivision(PF::PolyhedralFan, n::Int)

Return the star subdivision of a polyhedral fan at its n-th torus orbit. Note that this torus orbit need not be maximal. We follow definition 3.3.17 of [CLS11].

Examples

julia> star = star_subdivision(normal_fan(simplex(3)), 1)
Polyhedral fan in ambient dimension 3

julia> rays(star)
5-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]
 [-1, -1, -1]
 [1, 1, 1]

julia> ray_indices(maximal_cones(star))
6×5 IncidenceMatrix
[2, 3, 5]
[1, 3, 5]
[1, 2, 5]
[2, 3, 4]
[1, 3, 4]
[1, 2, 4]
source
star_subdivisionMethod
star_subdivision(PF::PolyhedralFan, new_ray::AbstractVector{<:IntegerUnion})

Return the star subdivision of a polyhedral fan by a primitive element of the underlying lattice. We follow the definition at the top of page 515 in [CLS11].

Examples

julia> fan = normal_fan(simplex(3))
Polyhedral fan in ambient dimension 3

julia> new_ray = [1, 1, 1];

julia> star = star_subdivision(fan, new_ray)
Polyhedral fan in ambient dimension 3

julia> rays(star)
5-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0, 0]
 [0, 1, 0]
 [0, 0, 1]
 [-1, -1, -1]
 [1, 1, 1]

julia> ray_indices(maximal_cones(star))
6×5 IncidenceMatrix
[2, 3, 5]
[1, 3, 5]
[1, 2, 5]
[2, 3, 4]
[1, 3, 4]
[1, 2, 4]
source
*Method
*(PF1::PolyhedralFan{QQFieldElem}, PF2::PolyhedralFan{QQFieldElem})

Return the Cartesian/direct product of two polyhedral fans.

Examples

julia> normal_fan(simplex(2))*normal_fan(simplex(3))
Polyhedral fan in ambient dimension 5
source