Catalog of common polyhedral convex cones

This module provides shortcut functions, grouped under the globally-available cones prefix, to create some common cones:

• The nonnegative orthant,

• The rearrangement cone of order p,

• The Schur cone,

• The trivial cone.

At the moment, only convex rational polyhedral cones are supported—specifically, those cones that can be built using the Cone() constructor. As a result, each shortcut method can be passed either an ambient dimension ambient_dim, or a toric lattice (from which the dimension can be inferred) to determine the ambient space.

Here are some typical usage examples:

sage: cones.nonnegative_orthant(2).rays()
N(1, 0),
N(0, 1)
in 2-d lattice N

sage: cones.rearrangement(2,2).rays()
N( 1,  0),
N( 1, -1),
N(-1,  1)
in 2-d lattice N

sage: cones.schur(3).rays()
N(1, -1,  0),
N(0,  1, -1)
in 3-d lattice N

sage: cones.trivial(3).rays()
Empty collection
in 3-d lattice N

To specify some other lattice, pass it as an argument to the function:

sage: K = cones.nonnegative_orthant(3)
sage: cones.schur(lattice=K.dual().lattice())
2-d cone in 3-d lattice M

For more information about these cones, see the documentation for the individual functions and the references therein.

sage.geometry.cone_catalog.nonnegative_orthant(ambient_dim=None, lattice=None)

The nonnegative orthant in ambient_dim dimensions, or living in lattice.

The nonnegative orthant consists of all componentwise-nonnegative vectors. It is the convex-conic hull of the standard basis.

INPUT:

• ambient_dim – a nonnegative integer (default: None); the dimension of the ambient space

• lattice – a toric lattice (default: None); the lattice in which the cone will live

If ambient_dim is omitted, then it will be inferred from the rank of lattice. If the lattice is omitted, then the default lattice of rank ambient_dim will be used.

A ValueError is raised if neither ambient_dim nor lattice are specified. It is also a ValueError to specify both ambient_dim and lattice unless the rank of lattice is equal to ambient_dim.

OUTPUT:

A ConvexRationalPolyhedralCone living in lattice and having ambient_dim standard basis vectors as its generators. Each generating ray has the integer ring as its base ring.

A ValueError can be raised if the inputs are incompatible or insufficient. See the INPUT documentation for details.

REFERENCES:

• Chapter 2 in [BV2009] (Examples 2.4, 2.14, and 2.23 in particular)

EXAMPLES:

sage: cones.nonnegative_orthant(3).rays()
N(1, 0, 0),
N(0, 1, 0),
N(0, 0, 1)
in 3-d lattice N

sage.geometry.cone_catalog.rearrangement(p, ambient_dim=None, lattice=None)

The rearrangement cone of order p in ambient_dim dimensions, or living in lattice.

The rearrangement cone of order p in ambient_dim dimensions consists of all vectors of length ambient_dim whose smallest p components sum to a nonnegative number.

For example, the rearrangement cone of order one has its single smallest component nonnegative. This implies that all components are nonnegative, and that therefore the rearrangement cone of order one is the nonnegative orthant in its ambient space.

When p and ambient_dim are equal, all components of the cone’s elements must sum to a nonnegative number. In other words, the rearrangement cone of order ambient_dim is a half-space.

INPUT:

• p – a nonnegative integer; the number of components to “rearrange”, between 1 and ambient_dim inclusive

• ambient_dim – a nonnegative integer (default: None); the dimension of the ambient space

• lattice – a toric lattice (default: None); the lattice in which the cone will live

If ambient_dim is omitted, then it will be inferred from the rank of lattice. If the lattice is omitted, then the default lattice of rank ambient_dim will be used.

A ValueError is raised if neither ambient_dim nor lattice are specified. It is also a ValueError to specify both ambient_dim and lattice unless the rank of lattice is equal to ambient_dim.

It is also a ValueError to specify a non-integer p.

OUTPUT:

A ConvexRationalPolyhedralCone representing the rearrangement cone of order p living in lattice, with ambient dimension ambient_dim. Each generating ray has the integer ring as its base ring.

A ValueError can be raised if the inputs are incompatible or insufficient. See the INPUT documentation for details.

ALGORITHM:

Suppose that the ambient space is of dimension \(n\). The extreme directions of the rearrangement cone for \(1 \le p \le n-1\) are given by [Jeong2017] Theorem 5.2.3. When \(2 \le p \le n-2\) (that is, if we ignore \(p = 1\) and \(p = n-1\)), they consist of

• the standard basis \(\left\{e_{1},e_{2},\ldots,e_{n}\right\}\) for the ambient space, and

• the \(n\) vectors \(\left(1,1,\ldots,1\right)^{T} - pe_{i}\) for \(i = 1,2,\ldots,n\).

Special cases are then given for \(p = 1\) and \(p = n-1\) in the theorem. However in SageMath we don’t need conically-independent extreme directions. We only need a generating set, because the Cone() function will eliminate any redundant generators. And one can easily verify that the special-case extreme directions for \(p = 1\) and \(p = n-1\) are contained in the conic hull of the \(2n\) generators just described. The half space resulting from \(p = n\) is also covered by this set of generators, so for all valid \(p\) we simply take the conic hull of those \(2n\) vectors.

REFERENCES:

• [GJ2016], Section 4

• [HS2010], Example 2.21

• [Jeong2017], Section 5.2

EXAMPLES:

The rearrangement cones of order one are nonnegative orthants:

sage: orthant = cones.nonnegative_orthant(6)
sage: cones.rearrangement(1,6).is_equivalent(orthant)
True

When p and ambient_dim are equal, the rearrangement cone is a half-space, so we expect its lineality to be one less than ambient_dim because it will contain a hyperplane but is not the entire space:

sage: cones.rearrangement(5,5).lineality()
4

Jeong’s Proposition 5.2.1 [Jeong2017] states that all rearrangement cones are proper when p is less than ambient_dim:

sage: all( cones.rearrangement(p, ambient_dim).is_proper()
....:              for ambient_dim in range(10)
....:              for p in range(1, ambient_dim) )
True

Jeong’s Corollary 5.2.4 [Jeong2017] states that if \(p = n-1\) in an \(n\)-dimensional ambient space, then the Lyapunov rank of the rearrangement cone is \(n\), and that for all other \(p > 1\) its Lyapunov rank is one:

sage: all( cones.rearrangement(p, ambient_dim).lyapunov_rank()
....:      ==
....:      ambient_dim
....:              for ambient_dim in range(2, 10)
....:              for p in [ ambient_dim-1 ] )
True
sage: all( cones.rearrangement(p, ambient_dim).lyapunov_rank() == 1
....:              for ambient_dim in range(3, 10)
....:              for p in range(2, ambient_dim-1) )
True

sage.geometry.cone_catalog.schur(ambient_dim=None, lattice=None)

The Schur cone in ambient_dim dimensions, or living in lattice.

The Schur cone in \(n\) dimensions induces the majorization ordering on the ambient space. If \(\left\{e_{1}, e_{2}, \ldots, e_{n}\right\}\) is the standard basis for the space, then its generators are \(\left\{e_{i} - e_{i+1}\ |\ 1 \le i \le n-1\right\}\). Its dual is the downward monotonic cone.

INPUT:

• ambient_dim – a nonnegative integer (default: None); the dimension of the ambient space

• lattice – a toric lattice (default: None); the lattice in which the cone will live

If ambient_dim is omitted, then it will be inferred from the rank of lattice. If the lattice is omitted, then the default lattice of rank ambient_dim will be used.

A ValueError is raised if neither ambient_dim nor lattice are specified. It is also a ValueError to specify both ambient_dim and lattice unless the rank of lattice is equal to ambient_dim.

OUTPUT:

A ConvexRationalPolyhedralCone representing the Schur cone living in lattice, with ambient dimension ambient_dim. Each generating ray has the integer ring as its base ring.

A ValueError can be raised if the inputs are incompatible or insufficient. See the INPUT documentation for details.

REFERENCES:

• [GS2010], Section 3.1

• [IS2005], Example 7.3

• [SS2016], Example 7.4

EXAMPLES:

Verify the claim [SS2016] that the maximal angle between any two generators of the Schur cone and the nonnegative orthant in dimension five is \(\left(3/4\right)\pi\):

sage: P = cones.schur(5)
sage: Q = cones.nonnegative_orthant(5)
sage: G = ( g.change_ring(QQbar).normalized() for g in P )
sage: H = ( h.change_ring(QQbar).normalized() for h in Q )
sage: actual = max(arccos(u.inner_product(v)) for u in G for v in H)
sage: expected = 3*pi/4
sage: abs(actual - expected).n() < 1e-12
True

The dual of the Schur cone is the “downward monotonic cone” [GS2010], whose elements’ entries are in non-increasing order:

sage: ambient_dim = ZZ.random_element(10)
sage: K = cones.schur(ambient_dim).dual()
sage: x = K.random_element()
sage: all( x[i] >= x[i+1] for i in range(ambient_dim-1) )
True

sage.geometry.cone_catalog.trivial(ambient_dim=None, lattice=None)

The trivial cone with no nonzero generators in ambient_dim dimensions, or living in lattice.

INPUT:

• ambient_dim – a nonnegative integer (default: None); the dimension of the ambient space

• lattice – a toric lattice (default: None); the lattice in which the cone will live

If ambient_dim is omitted, then it will be inferred from the rank of lattice. If the lattice is omitted, then the default lattice of rank ambient_dim will be used.

A ValueError is raised if neither ambient_dim nor lattice are specified. It is also a ValueError to specify both ambient_dim and lattice unless the rank of lattice is equal to ambient_dim.

OUTPUT:

A ConvexRationalPolyhedralCone representing the trivial cone with no nonzero generators living in lattice, with ambient dimension ambient_dim.

A ValueError can be raised if the inputs are incompatible or insufficient. See the INPUT documentation for details.

EXAMPLES:

Construct the trivial cone, containing only the origin, in three dimensions:

sage: cones.trivial(3)
0-d cone in 3-d lattice N

If a lattice is given, the trivial cone will live in that lattice:

sage: L = ToricLattice(3, 'M')
sage: cones.trivial(3, lattice=L)
0-d cone in 3-d lattice M