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$.

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(TropV::TropicalVariety)

See ambient_dim(::PolyhedralComplex).

source

arrangement_polynomial — Function

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

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(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> dim(PF)
2

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)
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_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(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

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_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(incidence_matrix([[1, 2], [2, 3]]), [0 1; 2 1; 1 0]);

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_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(incidence_matrix([[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_cones — Method

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

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; trivial=true)

Return the ray indices of all cones in a polyhedral fan. If trivial is set to false, the trivial cone, i.e., the Minkowski sum of the origin with the lineality space of the fan, will be omitted.

Examples

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

julia> cones(PF)
9×4 IncidenceMatrix
 [1, 3]
 [2, 4]
 [1, 2]
 [3, 4]
 [1]
 [3]
 [2]
 [4]
 []

source

minimal_supercone_coordinates — Method

minimal_supercone_coordinates(PF::PolyhedralFan, v::AbstractVector{<:RationalUnion})
-> Vector{QQFieldElem}

Let $PF$ be a pointed polyhedral fan and let $u_1, \ldots, u_n$ be the minimal generators of the rays of $PF$. Let $\sigma$ be the unique cone in $PF$ such that $v$ is in the relative interior of $v$. Note that if $v$ is a zero vector, then $v$ is in the relative interior of the zero cone. This function returns a vector $(p_1, \ldots, p_n)$ of nonnegative rational numbers such that both of the following hold:

the vector $v$ is equal to $p_1 u_1 + \ldots + p_n u_n$, and
if $u_i$ is not in $\sigma$, then $p_i = 0$.

If $PF$ is simplicial, then $(p_1, \ldots, p_n)$ is unique.

Examples

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

julia> v = [1, 1, 0]
3-element Vector{Int64}:
 1
 1
 0

julia> minimal_supercone_indices(PF, v)
Set{Int64} with 2 elements:
  2
  1

source

minimal_supercone_indices — Method

minimal_supercone_indices(PF::PolyhedralFan, v::AbstractVector{<:RationalUnion})
-> Set{Int64}

Given an point $v$ inside the support of the polyhedral fan $PF$, return the ray indices of the unique cone $σ$ in $PF$ such that $v$ is in the relative interior of $σ$. Note that if $v$ is a zero vector, then $v$ is in the relative interior of the zero cone.

The cone $σ$ can be constructed by

RPF = matrix(coefficient_field(PF), rays(PF))
isempty(result) && (sigma = positive_hull([], lineality_space(PF)))
!isempty(result) && (sigma = positive_hull(RPF[[result...], :], lineality_space(PF)))

where result is the output of this function.

Examples

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

julia> v = [1, 1, 0]
3-element Vector{Int64}:
 1
 1
 0

julia> minimal_supercone_indices(PF, v)
Set{Int64} with 2 elements:
  2
  1

source

is_minimal_supercone_coordinate_vector — Method

is_minimal_supercone_coordinate_vector(PF::PolyhedralFan, v::AbstractVector{<:RationalUnion})
-> Bool

Given a pointed polyhedral fan PF and a vector v of length equal to the number of rays of PF, this function checks that both of the following are true:

all of the entries of v are nonnegative,
there exists a cone $\sigma$ in PF such that for every $i$, if the $i$-th entry of $v$ is positive, then the $i$-th ray of PF belongs to $\sigma$.

Examples

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

julia> is_minimal_supercone_coordinate_vector(PF, [1, 1, 1, 0])
true

julia> is_minimal_supercone_coordinate_vector(PF, [1, 1, 1, 1])
false

source

standard_coordinates — Method

standard_coordinates(PF::PolyhedralFan, v::AbstractVector{<:RationalUnion})
-> Vector{QQFieldElem}

If is_minimal_supercone_coordinate_vector(PF, v) is true, then return the dot product of v and the vector of primitive generators of the rays of PF.

Examples

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

julia> standard_coordinates(PF, [1, 1, 0, 1])
3-element Vector{QQFieldElem}:
 0
 0
 -1

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(incidence_matrix([[1, 2], [3]]), [1 0; 0 1; -1 -1]);

julia> n_maximal_cones(PF)
2

source

n_cones — Method

n_cones(PF::PolyhedralFan; trivial=true)

Return the number of cones of PF. If trivial is set to false, the trivial cone, i.e., the Minkowski sum of the origin with the lineality space of the fan, will be omitted.

Examples

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

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

julia> n_cones(PF)
5

source

n_rays — Method

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

rays — Method

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.

Polyhedral Fans

Introduction

Construction

Auxiliary functions