Edit on GitHub

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 — Function
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 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(R,IM)
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(R, L, IM)
Polyhedral fan in ambient dimension 3

julia> lineality_dim(PF)
1
source
polyhedral_fan_from_rays_action — Function
polyhedral_fan_from_rays_action(::Type{T}, Rays::AbstractCollection[RayVector], MC_reps::IncidenceMatrix, perms::AbstractVector{PermGroupElem}) where T<:scalar_types

Construct a polyhedral fan with a group action.

Arguments

  • 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_fan — Method
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_fan — Method
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) == nfacets(C)
true
source

Auxiliary functions

ambient_dim — Method
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(T::TropicalVariety{M, EMB})
ambient_dim(T::TropicalCurve{M, EMB})
ambient_dim(T::TropicalHypersurface{M, EMB})
ambient_dim(T::TropicalLinearSpace{M, EMB})

Return the ambient dimension of T if it is embedded. Otherwise an error is thrown.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is of ambient dimension n

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y+1;

julia> tropicalLine = TropicalHypersurface(f);

julia> ambient_dim(tropicalLine)
2
source
dim — Method
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([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));

julia> dim(PF)
2
source
dim(T::TropicalVariety{M, EMB})
dim(T::TropicalCurve{M, EMB})
dim(T::TropicalHypersurface{M, EMB})
dim(T::TropicalLinearSpace{M, EMB})

Return the dimension of T.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is always of dimension n-1

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y+1;

julia> tropicalLine = TropicalHypersurface(f);

julia> dim(tropicalLine)
1
source
f_vector — Method
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)
Polyhedron 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
f_vector(T::TropicalVariety{M, EMB})
f_vector(T::TropicalCurve{M, EMB})
f_vector(T::TropicalHypersurface{M, EMB})
f_vector(T::TropicalLinearSpace{M, EMB})

Return the f-Vector of T.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y+1;

julia> tropicalLine = TropicalHypersurface(f);

julia> f_vector(tropicalLine)
2-element Vector{Int64}:
 1
 3
source
is_complete — Method
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_pointed — Method
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_regular — Method
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([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));

julia> is_regular(PF)
false
source
is_simplicial — Method
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_simplicial(T::TropicalVariety{M, EMB})
is_simplicial(T::TropicalCurve{M, EMB})
is_simplicial(T::TropicalHypersurface{M, EMB})
is_simplicial(T::TropicalLinearSpace{M, EMB})

Return true if T is a simplicial polyhedral complex, false otherwise.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y+1;

julia> tropicalLine = TropicalHypersurface(f);

julia> is_simplicial(tropicalLine)
true
source
is_smooth — Method
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([0 1; 2 1; 1 0], IncidenceMatrix([[1, 2], [2, 3]]));

julia> is_smooth(PF)
false
source
lineality_dim — Method
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_dim(T::TropicalVariety{M, EMB})
lineality_dim(T::TropicalCurve{M, EMB})
lineality_dim(T::TropicalHypersurface{M, EMB})
lineality_dim(T::TropicalLinearSpace{M, EMB})

Return the dimension of the lineality space of T if it is embedded. Otherwise an error is thrown.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is of lineality dimension n

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y;

julia> tropicalAndAffineLine = TropicalHypersurface(f);

julia> lineality_dim(tropicalAndAffineLine)
1
source
lineality_space — Method
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([1 0; 0 1; -1 0; 0 -1], IncidenceMatrix([[1, 2, 3], [3, 4, 1]]))
Polyhedral fan in ambient dimension 2

julia> lineality_space(PF)
1-element SubObjectIterator{RayVector{QQFieldElem}}:
 [1, 0]
source
lineality_space(T::TropicalVariety{M, EMB})
lineality_space(T::TropicalCurve{M, EMB})
lineality_space(T::TropicalHypersurface{M, EMB})
lineality_space(T::TropicalLinearSpace{M, EMB})

Return the lineality space of T if it is embedded. Otherwise an error is thrown.

Examples

A tropical hypersurface in $\mathbb{R}^n$ is of lineality spaceension n

julia> RR = TropicalSemiring(min);

julia> S,(x,y) = RR["x","y"];

julia> f = x+y;

julia> tropicalAndAffineLine = TropicalHypersurface(f);

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

Return the maximal cones of PF.

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(nrays(c))
       end
4
4
4
4
4
4
source
cones — Method
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
cones — Method
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_cones — Method
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([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]));

julia> n_maximal_cones(PF)
2
source
n_cones — Method
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([1 0; 0 1; -1 -1], IncidenceMatrix([[1, 2], [3]]))
Polyhedral fan in ambient dimension 2

julia> n_cones(PF)
4
source
nrays — Method
nrays(PF::PolyhedralFan)

Return the number of rays of PF.

Examples

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

julia> nrays(face_fan(cube(3)))
8
source
rays — Method
rays(PF::PolyhedralFan)

Return the rays of PF.

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]
source
rays_modulo_lineality — Method
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.

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
primitive_collections — Method
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_subdivision — Method
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 David A. Cox, John B. Little, Henry K. Schenck (2011).

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
[1, 3, 5]
[2, 3, 5]
[1, 2, 5]
[2, 3, 4]
[1, 3, 4]
[1, 2, 4]
source
* — Method
*(PF1::PolyhedralFan, PF2::PolyhedralFan)

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