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_fan
— Functionpolyhedral_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 parentField
of scalar to use, defaults toQQFieldElem
.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
polyhedral_fan(cones::AbstractVector{Cone{T}}) where T<:scalar_types
Assemble a polyhedral fan from a non-empty list of cones.
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
polyhedral_fan_from_rays_action
— Functionpolyhedral_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 fanMC_reps
:IncidenceMatrix
whose rows give the indices of the rays forming representatives of the maximal cones under the group action.perms
: A vector of permutationsPermGroupElem
that form generators of the group acting on the rays of the fan.
normal_fan
— Methodnormal_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]
face_fan
— Methodface_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
Auxiliary functions
ambient_dim
— Methodambient_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
ambient_dim(TropV::TropicalVariety)
arrangement_polynomial
— Functionarrangement_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)
dim
— Methoddim(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
f_vector
— Methodf_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
is_complete
— Methodis_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
is_pointed
— Methodis_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
is_regular
— Methodis_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
is_simplicial
— Methodis_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
is_smooth
— Methodis_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
lineality_dim
— Methodlineality_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
lineality_space
— Methodlineality_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]
maximal_cones
— Methodmaximal_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]
cones
— Methodcones(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
cones
— Methodcones(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]
n_maximal_cones
— Methodn_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
n_cones
— Methodn_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
n_rays
— Methodn_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
rays
— Methodrays([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}}
rays(TropV::TropicalVariety)
rays_modulo_lineality
— Methodrays_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}}
rays_modulo_lineality(TropV::TropicalVariety)
primitive_collections
— Methodprimitive_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])
star_subdivision
— Methodstar_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]
star_subdivision
— Methodstar_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]
*
— 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