Library of commonly used, famous, or interesting polytopes#

This module gathers several constructors of polytopes that can be reached through polytopes.<tab>. For example, here is the hypercube in dimension 5:

sage: polytopes.hypercube(5)
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 32 vertices
>>> from sage.all import *
>>> polytopes.hypercube(Integer(5))
A 5-dimensional polyhedron in ZZ^5 defined as the convex hull of 32 vertices

The following constructions are available

class sage.geometry.polyhedron.library.Polytopes[source]#

Bases: object

A class of constructors for commonly used, famous, or interesting polytopes.

Birkhoff_polytope(n, backend=None)[source]#

Return the Birkhoff polytope with \(n!\) vertices.

The vertices of this polyhedron are the (flattened) \(n\) by \(n\) permutation matrices. So the ambient vector space has dimension \(n^2\) but the dimension of the polyhedron is \((n-1)^2\).

INPUT:

  • n – a positive integer giving the size of the permutation matrices.

  • backend – the backend to use to create the polytope.

See also

sage.matrix.matrix2.Matrix.as_sum_of_permutations() – return the current matrix as a sum of permutation matrices

EXAMPLES:

sage: b3 = polytopes.Birkhoff_polytope(3)
sage: b3.f_vector()
(1, 6, 15, 18, 9, 1)
sage: b3.ambient_dim(), b3.dim()
(9, 4)
sage: b3.is_lattice_polytope()
True
sage: p3 = b3.ehrhart_polynomial()     # optional - latte_int
sage: p3                               # optional - latte_int
1/8*t^4 + 3/4*t^3 + 15/8*t^2 + 9/4*t + 1
sage: [p3(i) for i in [1,2,3,4]]       # optional - latte_int
[6, 21, 55, 120]
sage: [len((i*b3).integral_points()) for i in [1,2,3,4]]
[6, 21, 55, 120]

sage: b4 = polytopes.Birkhoff_polytope(4)
sage: b4.n_vertices(), b4.ambient_dim(), b4.dim()
(24, 16, 9)
>>> from sage.all import *
>>> b3 = polytopes.Birkhoff_polytope(Integer(3))
>>> b3.f_vector()
(1, 6, 15, 18, 9, 1)
>>> b3.ambient_dim(), b3.dim()
(9, 4)
>>> b3.is_lattice_polytope()
True
>>> p3 = b3.ehrhart_polynomial()     # optional - latte_int
>>> p3                               # optional - latte_int
1/8*t^4 + 3/4*t^3 + 15/8*t^2 + 9/4*t + 1
>>> [p3(i) for i in [Integer(1),Integer(2),Integer(3),Integer(4)]]       # optional - latte_int
[6, 21, 55, 120]
>>> [len((i*b3).integral_points()) for i in [Integer(1),Integer(2),Integer(3),Integer(4)]]
[6, 21, 55, 120]

>>> b4 = polytopes.Birkhoff_polytope(Integer(4))
>>> b4.n_vertices(), b4.ambient_dim(), b4.dim()
(24, 16, 9)
Gosset_3_21(backend=None)[source]#

Return the Gosset \(3_{21}\) polytope.

The Gosset \(3_{21}\) polytope is a uniform 7-polytope. It has 56 vertices, and 702 facets: \(126\) \(3_{11}\) and \(576\) \(6\)-simplex. For more information, see the Wikipedia article 3_21_polytope.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: g = polytopes.Gosset_3_21(); g
A 7-dimensional polyhedron in ZZ^8 defined as the convex hull of 56 vertices
sage: g.f_vector() # not tested (~16s)
(1, 56, 756, 4032, 10080, 12096, 6048, 702, 1)
>>> from sage.all import *
>>> g = polytopes.Gosset_3_21(); g
A 7-dimensional polyhedron in ZZ^8 defined as the convex hull of 56 vertices
>>> g.f_vector() # not tested (~16s)
(1, 56, 756, 4032, 10080, 12096, 6048, 702, 1)
Kirkman_icosahedron(backend=None)[source]#

Return the Kirkman icosahedron.

The Kirkman icosahedron is a 3-polytope with integer coordinates: \((\pm 9, \pm 6, \pm 6)\), \((\pm 12, \pm 4, 0)\), \((0, \pm 12, \pm 8)\), \((\pm 6, 0, \pm 12)\). See [Fe2012] for more information.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: ki = polytopes.Kirkman_icosahedron()
sage: ki.f_vector()
(1, 20, 38, 20, 1)

sage: ki.volume()
6528

sage: vertices = ki.vertices()
sage: edges = [[vector(edge[0]),vector(edge[1])] for edge in ki.bounded_edges()]
sage: edge_lengths = [norm(edge[0]-edge[1]) for edge in edges]
sage: sorted(set(edge_lengths))
[7, 8, 9, 11, 12, 14, 16]
>>> from sage.all import *
>>> ki = polytopes.Kirkman_icosahedron()
>>> ki.f_vector()
(1, 20, 38, 20, 1)

>>> ki.volume()
6528

>>> vertices = ki.vertices()
>>> edges = [[vector(edge[Integer(0)]),vector(edge[Integer(1)])] for edge in ki.bounded_edges()]
>>> edge_lengths = [norm(edge[Integer(0)]-edge[Integer(1)]) for edge in edges]
>>> sorted(set(edge_lengths))
[7, 8, 9, 11, 12, 14, 16]
bitruncated_six_hundred_cell(exact=True, backend=None)[source]#

Return the bitruncated 600-cell.

The bitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Bitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcinated_six_hundred_cell(exact=True,              # not tested - very long time
....:                                       backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
>>> from sage.all import *
>>> polytopes.runcinated_six_hundred_cell(exact=True,              # not tested - very long time
...                                       backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
buckyball(exact=True, base_ring=None, backend=None)[source]#

Return the bucky ball.

The bucky ball, also known as the truncated icosahedron is an Archimedean solid. It has 32 faces and 60 vertices.

See also

icosahedron()

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: bb = polytopes.buckyball()    # long time                             # needs sage.groups sage.rings.number_field
sage: bb.f_vector()                 # long time                             # needs sage.groups sage.rings.number_field
(1, 60, 90, 32, 1)
sage: bb.base_ring()                # long time                             # needs sage.groups sage.rings.number_field
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?
>>> from sage.all import *
>>> bb = polytopes.buckyball()    # long time                             # needs sage.groups sage.rings.number_field
>>> bb.f_vector()                 # long time                             # needs sage.groups sage.rings.number_field
(1, 60, 90, 32, 1)
>>> bb.base_ring()                # long time                             # needs sage.groups sage.rings.number_field
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: bb = polytopes.buckyball(exact=False)                                 # needs sage.groups
sage: bb.f_vector()                                                         # needs sage.groups
(1, 60, 90, 32, 1)
sage: bb.base_ring()                                                        # needs sage.groups
Real Double Field
>>> from sage.all import *
>>> bb = polytopes.buckyball(exact=False)                                 # needs sage.groups
>>> bb.f_vector()                                                         # needs sage.groups
(1, 60, 90, 32, 1)
>>> bb.base_ring()                                                        # needs sage.groups
Real Double Field

Its facets are 5 regular pentagons and 6 regular hexagons:

sage: sum(1 for f in bb.facets() if len(f.vertices()) == 5)                 # needs sage.groups
12
sage: sum(1 for f in bb.facets() if len(f.vertices()) == 6)                 # needs sage.groups
20
>>> from sage.all import *
>>> sum(Integer(1) for f in bb.facets() if len(f.vertices()) == Integer(5))                 # needs sage.groups
12
>>> sum(Integer(1) for f in bb.facets() if len(f.vertices()) == Integer(6))                 # needs sage.groups
20
cantellated_one_hundred_twenty_cell(exact=True, backend=None)[source]#

Return the cantellated 120-cell.

The cantellated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Cantellated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantellated_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
>>> from sage.all import *
>>> polytopes.cantellated_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
cantellated_six_hundred_cell(exact=False, backend=None)[source]#

Return the cantellated 600-cell.

The cantellated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 3600 vertices. For more information see Wikipedia article Cantellated 600-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantellated_six_hundred_cell()       # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 3600 vertices
>>> from sage.all import *
>>> polytopes.cantellated_six_hundred_cell()       # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 3600 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.cantellated_six_hundred_cell(exact=True,  # not tested - long time
....:                                        backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
>>> from sage.all import *
>>> polytopes.cantellated_six_hundred_cell(exact=True,  # not tested - long time
...                                        backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 3600 vertices
cantitruncated_one_hundred_twenty_cell(exact=True, backend=None)[source]#

Return the cantitruncated 120-cell.

The cantitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Cantitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantitruncated_one_hundred_twenty_cell(exact=True, backend='normaliz')  # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
>>> from sage.all import *
>>> polytopes.cantitruncated_one_hundred_twenty_cell(exact=True, backend='normaliz')  # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
cantitruncated_six_hundred_cell(exact=True, backend=None)[source]#

Return the cantitruncated 600-cell.

The cantitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Cantitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.cantitruncated_six_hundred_cell(exact=True,          # not tested - very long time
....:                                           backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
>>> from sage.all import *
>>> polytopes.cantitruncated_six_hundred_cell(exact=True,          # not tested - very long time
...                                           backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
cross_polytope(dim, backend=None)[source]#

Return a cross-polytope in dimension dim.

A cross-polytope is a higher dimensional generalization of the octahedron. It is the convex hull of the \(2d\) points \((\pm 1, 0, \ldots, 0)\), \((0, \pm 1, \ldots, 0)\), ldots, \((0, 0, \ldots, \pm 1)\). See the Wikipedia article Cross-polytope for more information.

INPUT:

  • dim – integer. The dimension of the cross-polytope.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: four_cross = polytopes.cross_polytope(4)
sage: four_cross.f_vector()
(1, 8, 24, 32, 16, 1)
sage: four_cross.is_simple()
False
>>> from sage.all import *
>>> four_cross = polytopes.cross_polytope(Integer(4))
>>> four_cross.f_vector()
(1, 8, 24, 32, 16, 1)
>>> four_cross.is_simple()
False
cube(intervals=None, backend=None)[source]#

Return the cube.

The cube is the Platonic solid that is obtained as the convex hull of the eight \(\pm 1\) vectors of length 3 (by default). Alternatively, the cube is the product of three intervals from intervals.

See also

hypercube()

INPUT:

  • intervals – list (default=None). It takes the following possible inputs:

    • If the input is None (the default), returns the convex hull of the eight \(\pm 1\) vectors of length three.

    • 'zero_one' – (string). Return the \(0/1\)-cube.

    • a list of 3 lists of length 2. The cube will be a product of these three intervals.

  • backend – the backend to use to create the polytope.

OUTPUT:

A cube as a polyhedron object.

EXAMPLES:

Return the \(\pm 1\)-cube:

sage: c = polytopes.cube()
sage: c
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
sage: c.f_vector()
(1, 8, 12, 6, 1)
sage: c.volume()
8
sage: c.plot()                                                              # needs sage.plot
Graphics3d Object
>>> from sage.all import *
>>> c = polytopes.cube()
>>> c
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
>>> c.f_vector()
(1, 8, 12, 6, 1)
>>> c.volume()
8
>>> c.plot()                                                              # needs sage.plot
Graphics3d Object

Return the \(0/1\)-cube:

sage: cc = polytopes.cube(intervals ='zero_one')
sage: cc.vertices_list()
[[1, 0, 0],
 [1, 1, 0],
 [1, 1, 1],
 [1, 0, 1],
 [0, 0, 1],
 [0, 0, 0],
 [0, 1, 0],
 [0, 1, 1]]
>>> from sage.all import *
>>> cc = polytopes.cube(intervals ='zero_one')
>>> cc.vertices_list()
[[1, 0, 0],
 [1, 1, 0],
 [1, 1, 1],
 [1, 0, 1],
 [0, 0, 1],
 [0, 0, 0],
 [0, 1, 0],
 [0, 1, 1]]
cuboctahedron(backend=None)[source]#

Return the cuboctahedron.

The cuboctahedron is an Archimedean solid with 12 vertices and 14 faces dual to the rhombic dodecahedron. It can be defined as the convex hull of the twelve vertices \((0, \pm 1, \pm 1)\), \((\pm 1, 0, \pm 1)\) and \((\pm 1, \pm 1, 0)\). For more information, see the Wikipedia article Cuboctahedron.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.cuboctahedron()
sage: co.f_vector()
(1, 12, 24, 14, 1)
>>> from sage.all import *
>>> co = polytopes.cuboctahedron()
>>> co.f_vector()
(1, 12, 24, 14, 1)

Its facets are 8 triangles and 6 squares:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
8
sage: sum(1 for f in co.facets() if len(f.vertices()) == 4)
6
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(3))
8
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(4))
6

Some more computation:

sage: co.volume()
20/3
sage: co.ehrhart_polynomial()      # optional - latte_int
20/3*t^3 + 8*t^2 + 10/3*t + 1
>>> from sage.all import *
>>> co.volume()
20/3
>>> co.ehrhart_polynomial()      # optional - latte_int
20/3*t^3 + 8*t^2 + 10/3*t + 1
cyclic_polytope(dim, n, base_ring=Rational Field, backend=None)[source]#

Return a cyclic polytope.

A cyclic polytope of dimension dim with n vertices is the convex hull of the points (t,t^2,...,t^dim) with \(t \in \{0,1,...,n-1\}\) . For more information, see the Wikipedia article Cyclic_polytope.

INPUT:

  • dim – positive integer. the dimension of the polytope.

  • n – positive integer. the number of vertices.

  • base_ring – either QQ (default) or RDF.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: c = polytopes.cyclic_polytope(4,10)
sage: c.f_vector()
(1, 10, 45, 70, 35, 1)
>>> from sage.all import *
>>> c = polytopes.cyclic_polytope(Integer(4),Integer(10))
>>> c.f_vector()
(1, 10, 45, 70, 35, 1)
dodecahedron(exact=True, base_ring=None, backend=None)[source]#

Return a dodecahedron.

The dodecahedron is the Platonic solid dual to the icosahedron().

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – (optional) the ring in which the coordinates will belong to. Note that this ring must contain \(\sqrt(5)\). If it is not provided and exact=True it will be the number field \(\QQ[\sqrt(5)]\) and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: # needs sage.groups sage.rings.number_field
sage: d12 = polytopes.dodecahedron()
sage: d12.f_vector()
(1, 20, 30, 12, 1)
sage: d12.volume()
-176*sqrt5 + 400
sage: numerical_approx(_)
6.45203596003699

sage: d12 = polytopes.dodecahedron(exact=False)                             # needs sage.groups
sage: d12.base_ring()                                                       # needs sage.groups
Real Double Field
>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> d12 = polytopes.dodecahedron()
>>> d12.f_vector()
(1, 20, 30, 12, 1)
>>> d12.volume()
-176*sqrt5 + 400
>>> numerical_approx(_)
6.45203596003699

>>> d12 = polytopes.dodecahedron(exact=False)                             # needs sage.groups
>>> d12.base_ring()                                                       # needs sage.groups
Real Double Field

Here is an error with a field that does not contain \(\sqrt(5)\):

sage: polytopes.dodecahedron(base_ring=QQ)                                  # needs sage.groups sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational
>>> from sage.all import *
>>> polytopes.dodecahedron(base_ring=QQ)                                  # needs sage.groups sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational
static edge_polytope(backend=None)[source]#

Return the edge polytope of self.

The edge polytope (EP) of a Graph on \(n\) vertices is the polytope in \(\ZZ^{n}\) defined as the convex hull of \(e_i + e_j\) for each edge \((i, j)\). Here \(e_1, \dots, e_n\) denotes the standard basis.

INPUT:

EXAMPLES:

The EP of a \(4\)-cycle is a square:

sage: G = graphs.CycleGraph(4)
sage: P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4))
>>> P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices

The EP of a complete graph on \(4\) vertices is cross polytope:

sage: G = graphs.CompleteGraph(4)
sage: P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cross_polytope(3))          # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> P = G.edge_polytope(); P                                              # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
>>> P.is_combinatorially_isomorphic(polytopes.cross_polytope(Integer(3)))          # needs sage.geometry.polyhedron
True

The EP of a graph is isomorphic to the subdirect sum of its connected components EPs:

sage: n = randint(3, 6)
sage: G1 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: n = randint(3, 6)
sage: G2 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: G = G1.disjoint_union(G2)                                             # needs networkx
sage: P = G.edge_polytope()                                                 # needs networkx sage.geometry.polyhedron
sage: P1 = G1.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
sage: P2 = G2.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
sage: P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))                 # needs networkx sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(3), Integer(6))
>>> G1 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> n = randint(Integer(3), Integer(6))
>>> G2 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> G = G1.disjoint_union(G2)                                             # needs networkx
>>> P = G.edge_polytope()                                                 # needs networkx sage.geometry.polyhedron
>>> P1 = G1.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
>>> P2 = G2.edge_polytope()                                               # needs networkx sage.geometry.polyhedron
>>> P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))                 # needs networkx sage.geometry.polyhedron
True

All trees on \(n\) vertices have isomorphic EPs:

sage: n = randint(4, 10)
sage: G1 = graphs.RandomTree(n)
sage: G2 = graphs.RandomTree(n)
sage: P1 = G1.edge_polytope()                                               # needs sage.geometry.polyhedron
sage: P2 = G2.edge_polytope()                                               # needs sage.geometry.polyhedron
sage: P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(4), Integer(10))
>>> G1 = graphs.RandomTree(n)
>>> G2 = graphs.RandomTree(n)
>>> P1 = G1.edge_polytope()                                               # needs sage.geometry.polyhedron
>>> P2 = G2.edge_polytope()                                               # needs sage.geometry.polyhedron
>>> P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True

However, there are still many different EPs:

sage: len(list(graphs(5)))
34
sage: polys = []
sage: for G in graphs(5):                                                   # needs sage.geometry.polyhedron
....:     P = G.edge_polytope()
....:     for P1 in polys:
....:         if P.is_combinatorially_isomorphic(P1):
....:             break
....:     else:
....:         polys.append(P)
sage: len(polys)                                                            # needs sage.geometry.polyhedron
19
>>> from sage.all import *
>>> len(list(graphs(Integer(5))))
34
>>> polys = []
>>> for G in graphs(Integer(5)):                                                   # needs sage.geometry.polyhedron
...     P = G.edge_polytope()
...     for P1 in polys:
...         if P.is_combinatorially_isomorphic(P1):
...             break
...     else:
...         polys.append(P)
>>> len(polys)                                                            # needs sage.geometry.polyhedron
19
static flow_polytope(edges=None, ends=None, backend=None)[source]#

Return the flow polytope of a digraph.

The flow polytope of a directed graph is the polytope consisting of all nonnegative flows on the graph with a given set \(S\) of sources and a given set \(T\) of sinks.

A flow on a directed graph \(G\) with a given set \(S\) of sources and a given set \(T\) of sinks means an assignment of a nonnegative real to each edge of \(G\) such that the flow is conserved in each vertex outside of \(S\) and \(T\), and there is a unit of flow entering each vertex in \(S\) and a unit of flow leaving each vertex in \(T\). These flows clearly form a polytope in the space of all assignments of reals to the edges of \(G\).

The polytope is empty unless the sets \(S\) and \(T\) are equinumerous.

By default, \(S\) is taken to be the set of all sources (i.e., vertices of indegree \(0\)) of \(G\), and \(T\) is taken to be the set of all sinks (i.e., vertices of outdegree \(0\)) of \(G\). If a different choice of \(S\) and \(T\) is desired, it can be specified using the optional ends parameter.

The polytope is returned as a polytope in \(\RR^m\), where \(m\) is the number of edges of the digraph self. The \(k\)-th coordinate of a point in the polytope is the real assigned to the \(k\)-th edge of self. The order of the edges is the one returned by self.edges(sort=True). If a different order is desired, it can be specified using the optional edges parameter.

The faces and volume of these polytopes are of interest. Examples of these polytopes are the Chan-Robbins-Yuen polytope and the Pitman-Stanley polytope [PS2002].

INPUT:

  • edges – list (default: None); a list of edges of self. If not specified, the list of all edges of self is used with the default ordering of self.edges(sort=True). This determines which coordinate of a point in the polytope will correspond to which edge of self. It is also possible to specify a list which contains not all edges of self; this results in a polytope corresponding to the flows which are \(0\) on all remaining edges. Notice that the edges entered here must be in the precisely same format as outputted by self.edges(); so, if self.edges() outputs an edge in the form (1, 3, None), then (1, 3) will not do!

  • ends – (default: (self.sources(), self.sinks())) a pair \((S, T)\) of an iterable \(S\) and an iterable \(T\).

  • backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

Note

Flow polytopes can also be built through the polytopes.<tab> object:

sage: polytopes.flow_polytope(digraphs.Path(5))                         # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex
>>> from sage.all import *
>>> polytopes.flow_polytope(digraphs.Path(Integer(5)))                         # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex

EXAMPLES:

A commutative square:

sage: G = DiGraph({1: [2, 3], 2: [4], 3: [4]})
sage: fl = G.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))
>>> from sage.all import *
>>> G = DiGraph({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(4)]})
>>> fl = G.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))

Using a different order for the edges of the graph:

sage: ordered_edges = G.edges(sort=True, key=lambda x: x[0] - x[1])
sage: fl = G.flow_polytope(edges=ordered_edges); fl                         # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))
>>> from sage.all import *
>>> ordered_edges = G.edges(sort=True, key=lambda x: x[Integer(0)] - x[Integer(1)])
>>> fl = G.flow_polytope(edges=ordered_edges); fl                         # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))

A tournament on 4 vertices:

sage: H = digraphs.TransitiveTournament(4)
sage: fl = H.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 1),
 A vertex at (1, 0, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 1, 0, 1))
>>> from sage.all import *
>>> H = digraphs.TransitiveTournament(Integer(4))
>>> fl = H.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 1),
 A vertex at (1, 0, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 1, 0, 1))

Restricting to a subset of the edges:

sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),               # needs sage.geometry.polyhedron
....:                             (2, 3, None), (0, 3, None)]); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))
>>> from sage.all import *
>>> fl = H.flow_polytope(edges=[(Integer(0), Integer(1), None), (Integer(1), Integer(2), None),               # needs sage.geometry.polyhedron
...                             (Integer(2), Integer(3), None), (Integer(0), Integer(3), None)]); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))

Using a different choice of sources and sinks:

sage: # needs sage.geometry.polyhedron
sage: fl = H.flow_polytope(ends=([1], [3])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
sage: fl = H.flow_polytope(ends=([0, 1], [3])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([3], [0])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([0, 1], [2, 3])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
 A vertex at (0, 1, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 2, 0, 1),
 A vertex at (1, 0, 0, 1, 1, 0),
 A vertex at (0, 1, 0, 1, 0, 1))
sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 2, None),
....:                             (1, 3, None)],
....:                      ends=([0, 1], [2, 3])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
 A vertex at (1, 2, 1, 0, 0),
 A vertex at (1, 1, 0, 0, 1),
 A vertex at (0, 1, 1, 1, 0))
>>> from sage.all import *
>>> # needs sage.geometry.polyhedron
>>> fl = H.flow_polytope(ends=([Integer(1)], [Integer(3)])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
>>> fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
>>> fl = H.flow_polytope(ends=([Integer(0), Integer(1)], [Integer(3)])); fl
The empty polyhedron in QQ^6
>>> fl = H.flow_polytope(ends=([Integer(3)], [Integer(0)])); fl
The empty polyhedron in QQ^6
>>> fl = H.flow_polytope(ends=([Integer(0), Integer(1)], [Integer(2), Integer(3)])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
>>> fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
 A vertex at (0, 1, 0, 0, 1, 0),
 A vertex at (1, 0, 0, 2, 0, 1),
 A vertex at (1, 0, 0, 1, 1, 0),
 A vertex at (0, 1, 0, 1, 0, 1))
>>> fl = H.flow_polytope(edges=[(Integer(0), Integer(1), None), (Integer(1), Integer(2), None),
...                             (Integer(2), Integer(3), None), (Integer(0), Integer(2), None),
...                             (Integer(1), Integer(3), None)],
...                      ends=([Integer(0), Integer(1)], [Integer(2), Integer(3)])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
>>> fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
 A vertex at (1, 2, 1, 0, 0),
 A vertex at (1, 1, 0, 0, 1),
 A vertex at (0, 1, 1, 1, 0))

A digraph with one source and two sinks:

sage: Y = DiGraph({1: [2], 2: [3, 4]})
sage: Y.flow_polytope()                                                     # needs sage.geometry.polyhedron
The empty polyhedron in QQ^3
>>> from sage.all import *
>>> Y = DiGraph({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)]})
>>> Y.flow_polytope()                                                     # needs sage.geometry.polyhedron
The empty polyhedron in QQ^3

A digraph with one vertex and no edge:

sage: Z = DiGraph({1: []})
sage: Z.flow_polytope()                                                     # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex
>>> from sage.all import *
>>> Z = DiGraph({Integer(1): []})
>>> Z.flow_polytope()                                                     # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex

A digraph with multiple edges (Issue #28837):

sage: G = DiGraph([(0, 1), (0,1)], multiedges=True); G
Multi-digraph on 2 vertices
sage: P = G.flow_polytope(); P                                              # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.vertices()                                                          # needs sage.geometry.polyhedron
(A vertex at (1, 0), A vertex at (0, 1))
sage: P.lines()                                                             # needs sage.geometry.polyhedron
()
>>> from sage.all import *
>>> G = DiGraph([(Integer(0), Integer(1)), (Integer(0),Integer(1))], multiedges=True); G
Multi-digraph on 2 vertices
>>> P = G.flow_polytope(); P                                              # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
>>> P.vertices()                                                          # needs sage.geometry.polyhedron
(A vertex at (1, 0), A vertex at (0, 1))
>>> P.lines()                                                             # needs sage.geometry.polyhedron
()
generalized_permutahedron(coxeter_type, point=None, exact=True, regular=False, backend=None)[source]#

Return the generalized permutahedron of type coxeter_type as the convex hull of the orbit of point in the fundamental cone.

This generalized permutahedron lies in the vector space used in the geometric representation, that is, in the default case, the dimension of generalized permutahedron equals the dimension of the space.

INPUT:

  • coxeter_type – a Coxeter type; given as a pair [type,rank], where type is a letter and rank is the number of generators.

  • point – a list (default: None); a point given by its coordinates in the weight basis. If None is given, the point \((1, 1, 1, \ldots)\) is used.

  • exact – (boolean, default True) if False use floating point approximations instead of exact coordinates

  • regular – boolean (default: False); whether to apply a linear transformation making the vertex figures isometric.

  • backend – backend to use to create the polytope; (default: None)

EXAMPLES:

sage: perm_a3 = polytopes.generalized_permutahedron(['A',3]); perm_a3       # needs sage.combinat
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 24 vertices
>>> from sage.all import *
>>> perm_a3 = polytopes.generalized_permutahedron(['A',Integer(3)]); perm_a3       # needs sage.combinat
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 24 vertices

You can put the starting point along the hyperplane of the first generator:

sage: # needs sage.combinat
sage: perm_a3_011 = polytopes.generalized_permutahedron(['A',3], [0,1,1])
sage: perm_a3_011
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110 = polytopes.generalized_permutahedron(['A',3], [1,1,0])
sage: perm_a3_110
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110.is_combinatorially_isomorphic(perm_a3_011)
True
sage: perm_a3_101 = polytopes.generalized_permutahedron(['A',3], [1,0,1])
sage: perm_a3_101
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
sage: perm_a3_110.is_combinatorially_isomorphic(perm_a3_101)
False
sage: perm_a3_011.f_vector()
(1, 12, 18, 8, 1)
sage: perm_a3_101.f_vector()
(1, 12, 24, 14, 1)
>>> from sage.all import *
>>> # needs sage.combinat
>>> perm_a3_011 = polytopes.generalized_permutahedron(['A',Integer(3)], [Integer(0),Integer(1),Integer(1)])
>>> perm_a3_011
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
>>> perm_a3_110 = polytopes.generalized_permutahedron(['A',Integer(3)], [Integer(1),Integer(1),Integer(0)])
>>> perm_a3_110
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
>>> perm_a3_110.is_combinatorially_isomorphic(perm_a3_011)
True
>>> perm_a3_101 = polytopes.generalized_permutahedron(['A',Integer(3)], [Integer(1),Integer(0),Integer(1)])
>>> perm_a3_101
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices
>>> perm_a3_110.is_combinatorially_isomorphic(perm_a3_101)
False
>>> perm_a3_011.f_vector()
(1, 12, 18, 8, 1)
>>> perm_a3_101.f_vector()
(1, 12, 24, 14, 1)

The usual output does not necessarily give a polyhedron with isometric vertex figures:

sage: perm_a2 = polytopes.generalized_permutahedron(['A',2])                # needs sage.combinat
sage: perm_a2.vertices()                                                    # needs sage.combinat
(A vertex at (-1, -1),
 A vertex at (-1, 0),
 A vertex at (0, -1),
 A vertex at (0, 1),
 A vertex at (1, 0),
 A vertex at (1, 1))
>>> from sage.all import *
>>> perm_a2 = polytopes.generalized_permutahedron(['A',Integer(2)])                # needs sage.combinat
>>> perm_a2.vertices()                                                    # needs sage.combinat
(A vertex at (-1, -1),
 A vertex at (-1, 0),
 A vertex at (0, -1),
 A vertex at (0, 1),
 A vertex at (1, 0),
 A vertex at (1, 1))

It works also with Coxeter types that lead to non-rational coordinates:

sage: perm_b3 = polytopes.generalized_permutahedron(['B',3])        # long time, needs sage.combinat sage.rings.number_field
sage: perm_b3                                                       # long time, needs sage.combinat sage.rings.number_field
A 3-dimensional polyhedron in
 (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3
 defined as the convex hull of 48 vertices
>>> from sage.all import *
>>> perm_b3 = polytopes.generalized_permutahedron(['B',Integer(3)])        # long time, needs sage.combinat sage.rings.number_field
>>> perm_b3                                                       # long time, needs sage.combinat sage.rings.number_field
A 3-dimensional polyhedron in
 (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^3
 defined as the convex hull of 48 vertices

Setting regular=True applies a linear transformation to get isometric vertex figures and the result is inscribed. This cannot be done using rational coordinates. We first do the computations using floating point approximations (RDF):

sage: perm_a2_inexact = polytopes.generalized_permutahedron(                # needs sage.combinat
....:     ['A',2], exact=False)
sage: sorted(perm_a2_inexact.vertices())                                    # needs sage.combinat
[A vertex at (-1.0, -1.0),
 A vertex at (-1.0, 0.0),
 A vertex at (0.0, -1.0),
 A vertex at (0.0, 1.0),
 A vertex at (1.0, 0.0),
 A vertex at (1.0, 1.0)]

sage: perm_a2_inexact_reg = polytopes.generalized_permutahedron(            # needs sage.combinat
....:     ['A',2], exact=False, regular=True)
sage: sorted(perm_a2_inexact_reg.vertices())                                # needs sage.combinat
[A vertex at (-1.0, 0.0),
 A vertex at (-0.5, -0.8660254038),
 A vertex at (-0.5, 0.8660254038),
 A vertex at (0.5, -0.8660254038),
 A vertex at (0.5, 0.8660254038),
 A vertex at (1.0, 0.0)]
>>> from sage.all import *
>>> perm_a2_inexact = polytopes.generalized_permutahedron(                # needs sage.combinat
...     ['A',Integer(2)], exact=False)
>>> sorted(perm_a2_inexact.vertices())                                    # needs sage.combinat
[A vertex at (-1.0, -1.0),
 A vertex at (-1.0, 0.0),
 A vertex at (0.0, -1.0),
 A vertex at (0.0, 1.0),
 A vertex at (1.0, 0.0),
 A vertex at (1.0, 1.0)]

>>> perm_a2_inexact_reg = polytopes.generalized_permutahedron(            # needs sage.combinat
...     ['A',Integer(2)], exact=False, regular=True)
>>> sorted(perm_a2_inexact_reg.vertices())                                # needs sage.combinat
[A vertex at (-1.0, 0.0),
 A vertex at (-0.5, -0.8660254038),
 A vertex at (-0.5, 0.8660254038),
 A vertex at (0.5, -0.8660254038),
 A vertex at (0.5, 0.8660254038),
 A vertex at (1.0, 0.0)]

We can do the same computation using exact arithmetic with the field AA:

sage: perm_a2_reg = polytopes.generalized_permutahedron(                    # needs sage.combinat sage.rings.number_field
....:     ['A',2], regular=True)
sage: V = sorted(perm_a2_reg.vertices()); V  # random                       # needs sage.combinat sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1.000000000000000?, 0.?e-18)]
>>> from sage.all import *
>>> perm_a2_reg = polytopes.generalized_permutahedron(                    # needs sage.combinat sage.rings.number_field
...     ['A',Integer(2)], regular=True)
>>> V = sorted(perm_a2_reg.vertices()); V  # random                       # needs sage.combinat sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1.000000000000000?, 0.?e-18)]

Even though the numbers look like floating point approximations, the computation is actually exact. We can clean up the display a bit using exactify:

sage: for v in V:                                                           # needs sage.combinat sage.rings.number_field
....:     for x in v:
....:         x.exactify()
sage: V                                                                     # needs sage.combinat sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1, 0)]
sage: perm_a2_reg.is_inscribed()                                            # needs sage.combinat sage.rings.number_field
True
>>> from sage.all import *
>>> for v in V:                                                           # needs sage.combinat sage.rings.number_field
...     for x in v:
...         x.exactify()
>>> V                                                                     # needs sage.combinat sage.rings.number_field
[A vertex at (-1, 0),
 A vertex at (-1/2, -0.866025403784439?),
 A vertex at (-1/2, 0.866025403784439?),
 A vertex at (1/2, -0.866025403784439?),
 A vertex at (1/2, 0.866025403784439?),
 A vertex at (1, 0)]
>>> perm_a2_reg.is_inscribed()                                            # needs sage.combinat sage.rings.number_field
True

Larger examples take longer:

sage: # needs sage.combinat sage.rings.number_field
sage: perm_a3_reg = polytopes.generalized_permutahedron(    # long time
....:     ['A',3], regular=True); perm_a3_reg
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg.is_inscribed()    # long time
True
sage: perm_b3_reg = polytopes.generalized_permutahedron(    # long time (12sec on 64 bits), not tested
....:     ['B',3], regular=True); perm_b3_reg
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices
>>> from sage.all import *
>>> # needs sage.combinat sage.rings.number_field
>>> perm_a3_reg = polytopes.generalized_permutahedron(    # long time
...     ['A',Integer(3)], regular=True); perm_a3_reg
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
>>> perm_a3_reg.is_inscribed()    # long time
True
>>> perm_b3_reg = polytopes.generalized_permutahedron(    # long time (12sec on 64 bits), not tested
...     ['B',Integer(3)], regular=True); perm_b3_reg
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

It is faster with the backend 'number_field', which internally uses an embedded number field instead of doing the computations directly with the base ring (AA):

sage: # needs sage.combinat sage.rings.number_field
sage: perm_a3_reg_nf = polytopes.generalized_permutahedron(
....:    ['A',3], regular=True, backend='number_field'); perm_a3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg_nf.is_inscribed()
True
sage: perm_b3_reg_nf = polytopes.generalized_permutahedron(         # long time
....:    ['B',3], regular=True, backend='number_field'); perm_b3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices
>>> from sage.all import *
>>> # needs sage.combinat sage.rings.number_field
>>> perm_a3_reg_nf = polytopes.generalized_permutahedron(
...    ['A',Integer(3)], regular=True, backend='number_field'); perm_a3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
>>> perm_a3_reg_nf.is_inscribed()
True
>>> perm_b3_reg_nf = polytopes.generalized_permutahedron(         # long time
...    ['B',Integer(3)], regular=True, backend='number_field'); perm_b3_reg_nf
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

It is even faster with the backend 'normaliz':

sage: # optional - pynormaliz, needs sage.combinat sage.rings.number_field
sage: perm_a3_reg_norm = polytopes.generalized_permutahedron(
....:    ['A',3], regular=True, backend='normaliz'); perm_a3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
sage: perm_a3_reg_norm.is_inscribed()
True
sage: perm_b3_reg_norm = polytopes.generalized_permutahedron(
....:    ['B',3], regular=True, backend='normaliz'); perm_b3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices
>>> from sage.all import *
>>> # optional - pynormaliz, needs sage.combinat sage.rings.number_field
>>> perm_a3_reg_norm = polytopes.generalized_permutahedron(
...    ['A',Integer(3)], regular=True, backend='normaliz'); perm_a3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 24 vertices
>>> perm_a3_reg_norm.is_inscribed()
True
>>> perm_b3_reg_norm = polytopes.generalized_permutahedron(
...    ['B',Integer(3)], regular=True, backend='normaliz'); perm_b3_reg_norm
A 3-dimensional polyhedron in AA^3 defined as the convex hull of 48 vertices

The speedups from using backend 'normaliz' allow us to go even further:

sage: # optional - pynormaliz, needs sage.combinat sage.rings.number_field
sage: perm_h3 = polytopes.generalized_permutahedron(
....:     ['H',3], backend='normaliz'); perm_h3
A 3-dimensional polyhedron in
 (Number Field in a with defining polynomial x^2 - 5 with a = 2.236067977499790?)^3
 defined as the convex hull of 120 vertices
sage: perm_f4 = polytopes.generalized_permutahedron(        # long time
....:     ['F',4], backend='normaliz'); perm_f4
A 4-dimensional polyhedron
 in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^4
 defined as the convex hull of 1152 vertices
>>> from sage.all import *
>>> # optional - pynormaliz, needs sage.combinat sage.rings.number_field
>>> perm_h3 = polytopes.generalized_permutahedron(
...     ['H',Integer(3)], backend='normaliz'); perm_h3
A 3-dimensional polyhedron in
 (Number Field in a with defining polynomial x^2 - 5 with a = 2.236067977499790?)^3
 defined as the convex hull of 120 vertices
>>> perm_f4 = polytopes.generalized_permutahedron(        # long time
...     ['F',Integer(4)], backend='normaliz'); perm_f4
A 4-dimensional polyhedron
 in (Number Field in a with defining polynomial x^2 - 2 with a = 1.414213562373095?)^4
 defined as the convex hull of 1152 vertices

See also

  • permutahedron()

  • permutahedron()

grand_antiprism(exact=True, backend=None, verbose=False)[source]#

Return the grand antiprism.

The grand antiprism is a 4-dimensional non-Wythoffian uniform polytope. The coordinates were taken from http://eusebeia.dyndns.org/4d/gap. For more information, see the Wikipedia article Grand_antiprism.

Warning

The coordinates are exact by default. The computation with exact coordinates is not as fast as with floating point approximations. If you find this method to be too slow, consider using floating point approximations

INPUT:

  • exact – (boolean, default True) if False use floating point approximations instead of exact coordinates

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: gap = polytopes.grand_antiprism()  # not tested - very long time
sage: gap                                # not tested - very long time
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices
>>> from sage.all import *
>>> gap = polytopes.grand_antiprism()  # not tested - very long time
>>> gap                                # not tested - very long time
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices

Computation with the backend 'normaliz' is instantaneous:

sage: gap_norm = polytopes.grand_antiprism(backend='normaliz')      # optional - pynormaliz, needs sage.rings.number_field
sage: gap_norm                                                      # optional - pynormaliz, needs sage.rings.number_field
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices
>>> from sage.all import *
>>> gap_norm = polytopes.grand_antiprism(backend='normaliz')      # optional - pynormaliz, needs sage.rings.number_field
>>> gap_norm                                                      # optional - pynormaliz, needs sage.rings.number_field
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
the convex hull of 100 vertices

Computation with approximated coordinates is also faster, but inexact:

sage: gap = polytopes.grand_antiprism(exact=False) # random
sage: gap
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 100 vertices
sage: gap.f_vector()
(1, 100, 500, 720, 320, 1)
sage: len(list(gap.bounded_edges()))
500
>>> from sage.all import *
>>> gap = polytopes.grand_antiprism(exact=False) # random
>>> gap
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 100 vertices
>>> gap.f_vector()
(1, 100, 500, 720, 320, 1)
>>> len(list(gap.bounded_edges()))
500
great_rhombicuboctahedron(exact=True, base_ring=None, backend=None)[source]#

Return the great rhombicuboctahedron.

The great rhombicuboctahedron (or truncated cuboctahedron) is an Archimedean solid with 48 vertices and 26 faces. For more information see the Wikipedia article Truncated_cuboctahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: gr = polytopes.great_rhombicuboctahedron()    # long time             # needs sage.rings.number_field
sage: gr.f_vector()                 # long time                             # needs sage.rings.number_field
(1, 48, 72, 26, 1)
>>> from sage.all import *
>>> gr = polytopes.great_rhombicuboctahedron()    # long time             # needs sage.rings.number_field
>>> gr.f_vector()                 # long time                             # needs sage.rings.number_field
(1, 48, 72, 26, 1)

A faster implementation is obtained by setting exact=False:

sage: gr = polytopes.great_rhombicuboctahedron(exact=False)
sage: gr.f_vector()
(1, 48, 72, 26, 1)
>>> from sage.all import *
>>> gr = polytopes.great_rhombicuboctahedron(exact=False)
>>> gr.f_vector()
(1, 48, 72, 26, 1)

Its facets are 4 squares, 8 regular hexagons and 6 regular octagons:

sage: sum(1 for f in gr.facets() if len(f.vertices()) == 4)
12
sage: sum(1 for f in gr.facets() if len(f.vertices()) == 6)
8
sage: sum(1 for f in gr.facets() if len(f.vertices()) == 8)
6
>>> from sage.all import *
>>> sum(Integer(1) for f in gr.facets() if len(f.vertices()) == Integer(4))
12
>>> sum(Integer(1) for f in gr.facets() if len(f.vertices()) == Integer(6))
8
>>> sum(Integer(1) for f in gr.facets() if len(f.vertices()) == Integer(8))
6
hypercube(dim, intervals=None, backend=None)[source]#

Return a hypercube of the given dimension.

The dim-dimensional hypercube is by default the convex hull of the \(2^{\text{dim}}\) \(\pm 1\) vectors of length dim. Alternatively, it is the product of dim line segments given in the intervals. For more information see the wikipedia article Wikipedia article Hypercube.

INPUT:

  • dim – integer. The dimension of the hypercube.

  • intervals – (default = None). It takes the following possible inputs:

    • If None (the default), it returns the \(\pm 1\)-cube of dimension dim.

    • 'zero_one' – (string). Return the \(0/1\)-cube.

    • a list of length dim. Its elements are pairs of numbers \((a,b)\) with \(a < b\). The cube will be the product of these intervals.

  • backend – the backend to use to create the polytope.

EXAMPLES:

Create the \(\pm 1\)-hypercube of dimension 4:

sage: four_cube = polytopes.hypercube(4)
sage: four_cube.is_simple()
True
sage: four_cube.base_ring()
Integer Ring
sage: four_cube.volume()
16
sage: four_cube.ehrhart_polynomial()    # optional - latte_int
16*t^4 + 32*t^3 + 24*t^2 + 8*t + 1
>>> from sage.all import *
>>> four_cube = polytopes.hypercube(Integer(4))
>>> four_cube.is_simple()
True
>>> four_cube.base_ring()
Integer Ring
>>> four_cube.volume()
16
>>> four_cube.ehrhart_polynomial()    # optional - latte_int
16*t^4 + 32*t^3 + 24*t^2 + 8*t + 1

Return the \(0/1\)-hypercube of dimension 4:

sage: z_cube = polytopes.hypercube(4, intervals='zero_one')
sage: z_cube.vertices()[0]
A vertex at (1, 0, 1, 1)
sage: z_cube.is_simple()
True
sage: z_cube.base_ring()
Integer Ring
sage: z_cube.volume()
1
sage: z_cube.ehrhart_polynomial()       # optional - latte_int
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
>>> from sage.all import *
>>> z_cube = polytopes.hypercube(Integer(4), intervals='zero_one')
>>> z_cube.vertices()[Integer(0)]
A vertex at (1, 0, 1, 1)
>>> z_cube.is_simple()
True
>>> z_cube.base_ring()
Integer Ring
>>> z_cube.volume()
1
>>> z_cube.ehrhart_polynomial()       # optional - latte_int
t^4 + 4*t^3 + 6*t^2 + 4*t + 1

Return the 4-dimensional combinatorial cube that is the product of [0,3]^4:

sage: t_cube = polytopes.hypercube(4, intervals=[[0,3]]*4)
>>> from sage.all import *
>>> t_cube = polytopes.hypercube(Integer(4), intervals=[[Integer(0),Integer(3)]]*Integer(4))

Checking that t_cube is three times the previous \(0/1\)-cube:

sage: t_cube == 3 * z_cube
True
>>> from sage.all import *
>>> t_cube == Integer(3) * z_cube
True
hypersimplex(dim, k, project=False, backend=None)[source]#

Return the hypersimplex in dimension dim and parameter k.

The hypersimplex \(\Delta_{d,k}\) is the convex hull of the vertices made of \(k\) ones and \(d-k\) zeros. It lies in the \(d-1\) hyperplane of vectors of sum \(k\). If you want a projected version to \(\RR^{d-1}\) (with floating point coordinates) then set project=True in the options.

See also

simplex()

INPUT:

  • dim – the dimension

  • n – the numbers (1,...,n) are permuted

  • project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This operation turns the coordinates into floating point approximations and corresponds to the projection given by the matrix from zero_sum_projection().

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: # needs sage.combinat
sage: h_4_2 = polytopes.hypersimplex(4, 2)
sage: h_4_2
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
sage: h_4_2.f_vector()
(1, 6, 12, 8, 1)
sage: h_4_2.ehrhart_polynomial()                            # optional - latte_int
2/3*t^3 + 2*t^2 + 7/3*t + 1
sage: TestSuite(h_4_2).run()

sage: # needs sage.combinat
sage: h_7_3 = polytopes.hypersimplex(7, 3, project=True)
sage: h_7_3
A 6-dimensional polyhedron in RDF^6 defined as the convex hull of 35 vertices
sage: h_7_3.f_vector()
(1, 35, 210, 350, 245, 84, 14, 1)
sage: TestSuite(h_7_3).run(skip=["_test_pyramid", "_test_lawrence"])
>>> from sage.all import *
>>> # needs sage.combinat
>>> h_4_2 = polytopes.hypersimplex(Integer(4), Integer(2))
>>> h_4_2
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 6 vertices
>>> h_4_2.f_vector()
(1, 6, 12, 8, 1)
>>> h_4_2.ehrhart_polynomial()                            # optional - latte_int
2/3*t^3 + 2*t^2 + 7/3*t + 1
>>> TestSuite(h_4_2).run()

>>> # needs sage.combinat
>>> h_7_3 = polytopes.hypersimplex(Integer(7), Integer(3), project=True)
>>> h_7_3
A 6-dimensional polyhedron in RDF^6 defined as the convex hull of 35 vertices
>>> h_7_3.f_vector()
(1, 35, 210, 350, 245, 84, 14, 1)
>>> TestSuite(h_7_3).run(skip=["_test_pyramid", "_test_lawrence"])
icosahedron(exact=True, base_ring=None, backend=None)[source]#

Return an icosahedron with edge length 1.

The icosahedron is one of the Platonic solids. It has 20 faces and is dual to the dodecahedron().

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – (optional) the ring in which the coordinates will belong to. Note that this ring must contain \(\sqrt(5)\). If it is not provided and exact=True it will be the number field \(\QQ[\sqrt(5)]\) and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: ico = polytopes.icosahedron()                                         # needs sage.rings.number_field
sage: ico.f_vector()                                                        # needs sage.rings.number_field
(1, 12, 30, 20, 1)
sage: ico.volume()                                                          # needs sage.rings.number_field
5/12*sqrt5 + 5/4
>>> from sage.all import *
>>> ico = polytopes.icosahedron()                                         # needs sage.rings.number_field
>>> ico.f_vector()                                                        # needs sage.rings.number_field
(1, 12, 30, 20, 1)
>>> ico.volume()                                                          # needs sage.rings.number_field
5/12*sqrt5 + 5/4

Its non exact version:

sage: ico = polytopes.icosahedron(exact=False)                              # needs sage.groups
sage: ico.base_ring()                                                       # needs sage.groups
Real Double Field
sage: ico.volume()                  # known bug                             # needs sage.groups
2.181694990...
>>> from sage.all import *
>>> ico = polytopes.icosahedron(exact=False)                              # needs sage.groups
>>> ico.base_ring()                                                       # needs sage.groups
Real Double Field
>>> ico.volume()                  # known bug                             # needs sage.groups
2.181694990...

A version using \(AA <sage.rings.qqbar.AlgebraicRealField>\):

sage: ico = polytopes.icosahedron(base_ring=AA)     # long time             # needs sage.groups sage.rings.number_field
sage: ico.base_ring()                               # long time             # needs sage.groups sage.rings.number_field
Algebraic Real Field
sage: ico.volume()                                  # long time             # needs sage.groups sage.rings.number_field
2.181694990624913?
>>> from sage.all import *
>>> ico = polytopes.icosahedron(base_ring=AA)     # long time             # needs sage.groups sage.rings.number_field
>>> ico.base_ring()                               # long time             # needs sage.groups sage.rings.number_field
Algebraic Real Field
>>> ico.volume()                                  # long time             # needs sage.groups sage.rings.number_field
2.181694990624913?

Note that if base ring is provided it must contain the square root of \(5\). Otherwise you will get an error:

sage: polytopes.icosahedron(base_ring=QQ)                                   # needs sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational
>>> from sage.all import *
>>> polytopes.icosahedron(base_ring=QQ)                                   # needs sage.symbolic
Traceback (most recent call last):
...
TypeError: unable to convert 1/4*sqrt(5) + 1/4 to a rational
icosidodecahedron(exact=True, backend=None)[source]#

Return the icosidodecahedron.

The Icosidodecahedron is a polyhedron with twenty triangular faces and twelve pentagonal faces. For more information see the Wikipedia article Icosidodecahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: id = polytopes.icosidodecahedron()                                    # needs sage.groups sage.rings.number_field
sage: id.f_vector()                                                         # needs sage.groups sage.rings.number_field
(1, 30, 60, 32, 1)
>>> from sage.all import *
>>> id = polytopes.icosidodecahedron()                                    # needs sage.groups sage.rings.number_field
>>> id.f_vector()                                                         # needs sage.groups sage.rings.number_field
(1, 30, 60, 32, 1)
icosidodecahedron_V2(exact=True, base_ring=None, backend=None)[source]#

Return the icosidodecahedron.

The icosidodecahedron is an Archimedean solid. It has 32 faces and 30 vertices. For more information, see the Wikipedia article Icosidodecahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: id = polytopes.icosidodecahedron_V2()   # long time - 6secs
sage: id.f_vector()                           # long time
(1, 30, 60, 32, 1)
sage: id.base_ring()                          # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?
>>> from sage.all import *
>>> id = polytopes.icosidodecahedron_V2()   # long time - 6secs
>>> id.f_vector()                           # long time
(1, 30, 60, 32, 1)
>>> id.base_ring()                          # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: id = polytopes.icosidodecahedron_V2(exact=False)
sage: id.f_vector()
(1, 30, 60, 32, 1)
sage: id.base_ring()
Real Double Field
>>> from sage.all import *
>>> id = polytopes.icosidodecahedron_V2(exact=False)
>>> id.f_vector()
(1, 30, 60, 32, 1)
>>> id.base_ring()
Real Double Field

Its facets are 20 triangles and 12 regular pentagons:

sage: sum(1 for f in id.facets() if len(f.vertices()) == 3)
20
sage: sum(1 for f in id.facets() if len(f.vertices()) == 5)
12
>>> from sage.all import *
>>> sum(Integer(1) for f in id.facets() if len(f.vertices()) == Integer(3))
20
>>> sum(Integer(1) for f in id.facets() if len(f.vertices()) == Integer(5))
12
octahedron(backend=None)[source]#

Return the octahedron.

The octahedron is a Platonic solid with 6 vertices and 8 faces dual to the cube. It can be defined as the convex hull of the six vertices \((0, 0, \pm 1)\), \((\pm 1, 0, 0)\) and \((0, \pm 1, 0)\). For more information, see the Wikipedia article Octahedron.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.octahedron()
sage: co.f_vector()
(1, 6, 12, 8, 1)
>>> from sage.all import *
>>> co = polytopes.octahedron()
>>> co.f_vector()
(1, 6, 12, 8, 1)

Its facets are 8 triangles:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
8
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(3))
8

Some more computation:

sage: co.volume()
4/3
sage: co.ehrhart_polynomial()      # optional - latte_int
4/3*t^3 + 2*t^2 + 8/3*t + 1
>>> from sage.all import *
>>> co.volume()
4/3
>>> co.ehrhart_polynomial()      # optional - latte_int
4/3*t^3 + 2*t^2 + 8/3*t + 1
omnitruncated_one_hundred_twenty_cell(exact=True, backend=None)[source]#

Return the omnitruncated 120-cell.

The omnitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 14400 vertices. For more information see Wikipedia article Omnitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices
>>> from sage.all import *
>>> polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices
omnitruncated_six_hundred_cell(exact=True, backend=None)[source]#

Return the omnitruncated 120-cell.

The omnitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 14400 vertices. For more information see Wikipedia article Omnitruncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices
>>> from sage.all import *
>>> polytopes.omnitruncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - very long time ~10min
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 14400 vertices
one_hundred_twenty_cell(exact=True, backend=None, construction='coxeter')[source]#

Return the 120-cell.

The 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 600 vertices and 120 facets. For more information see Wikipedia article 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

  • construction – the construction to use (string, default ‘coxeter’); the other possibility is ‘as_permutahedron’.

EXAMPLES:

The classical construction given by Coxeter in [Cox1969] is given by:

sage: polytopes.one_hundred_twenty_cell()                    # not tested - long time ~15 sec.
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
 the convex hull of 600 vertices
>>> from sage.all import *
>>> polytopes.one_hundred_twenty_cell()                    # not tested - long time ~15 sec.
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
 the convex hull of 600 vertices

The 'normaliz' is faster:

sage: P = polytopes.one_hundred_twenty_cell(backend='normaliz'); P  # optional - pynormaliz
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
 the convex hull of 600 vertices
>>> from sage.all import *
>>> P = polytopes.one_hundred_twenty_cell(backend='normaliz'); P  # optional - pynormaliz
A 4-dimensional polyhedron in (Number Field in sqrt5 with defining
 polynomial x^2 - 5 with sqrt5 = 2.236067977499790?)^4 defined as
 the convex hull of 600 vertices

It is also possible to realize it using the generalized permutahedron of type \(H_4\):

sage: polytopes.one_hundred_twenty_cell(backend='normaliz',  # not tested - long time
....:                                   construction='as_permutahedron')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 600 vertices
>>> from sage.all import *
>>> polytopes.one_hundred_twenty_cell(backend='normaliz',  # not tested - long time
...                                   construction='as_permutahedron')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 600 vertices
parallelotope(generators, backend=None)[source]#

Return the zonotope, or parallelotope, spanned by the generators.

The parallelotope is the multi-dimensional generalization of a parallelogram (2 generators) and a parallelepiped (3 generators).

INPUT:

  • generators – a list of vectors of same dimension

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.parallelotope([ (1,0), (0,1) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: polytopes.parallelotope([[1,2,3,4], [0,1,0,7], [3,1,0,2], [0,0,1,0]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

sage: K = QuadraticField(2, 'sqrt2')                                        # needs sage.rings.number_field
sage: sqrt2 = K.gen()                                                       # needs sage.rings.number_field
sage: P = polytopes.parallelotope([(1, sqrt2), (1, -1)]); P                 # needs sage.rings.number_field
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices
>>> from sage.all import *
>>> polytopes.parallelotope([ (Integer(1),Integer(0)), (Integer(0),Integer(1)) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> polytopes.parallelotope([[Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(0),Integer(1),Integer(0),Integer(7)], [Integer(3),Integer(1),Integer(0),Integer(2)], [Integer(0),Integer(0),Integer(1),Integer(0)]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

>>> K = QuadraticField(Integer(2), 'sqrt2')                                        # needs sage.rings.number_field
>>> sqrt2 = K.gen()                                                       # needs sage.rings.number_field
>>> P = polytopes.parallelotope([(Integer(1), sqrt2), (Integer(1), -Integer(1))]); P                 # needs sage.rings.number_field
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices
pentakis_dodecahedron(exact=True, base_ring=None, backend=None)[source]#

Return the pentakis dodecahedron.

The pentakis dodecahedron (orkisdodecahedron) is a face-regular, vertex-uniform polytope dual to the truncated icosahedron. It has 60 facets and 32 vertices. See the Wikipedia article Pentakis_dodecahedron for more information.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: pd = polytopes.pentakis_dodecahedron()    # long time - ~10 sec
sage: pd.n_vertices()                           # long time
32
sage: pd.n_inequalities()                       # long time
60
>>> from sage.all import *
>>> pd = polytopes.pentakis_dodecahedron()    # long time - ~10 sec
>>> pd.n_vertices()                           # long time
32
>>> pd.n_inequalities()                       # long time
60

A much faster implementation is obtained when setting exact=False:

sage: pd = polytopes.pentakis_dodecahedron(exact=False)                     # needs sage.groups
sage: pd.n_vertices()                                                       # needs sage.groups
32
sage: pd.n_inequalities()                                                   # needs sage.groups
60
>>> from sage.all import *
>>> pd = polytopes.pentakis_dodecahedron(exact=False)                     # needs sage.groups
>>> pd.n_vertices()                                                       # needs sage.groups
32
>>> pd.n_inequalities()                                                   # needs sage.groups
60

The 60 are triangles:

sage: all(len(f.vertices()) == 3 for f in pd.facets())                      # needs sage.groups
True
>>> from sage.all import *
>>> all(len(f.vertices()) == Integer(3) for f in pd.facets())                      # needs sage.groups
True
permutahedron(n, project=False, backend=None)[source]#

Return the standard permutahedron of (1,…,n).

The permutahedron (or permutohedron) is the convex hull of the permutations of \(\{1,\ldots,n\}\) seen as vectors. The edges between the permutations correspond to multiplication on the right by an elementary transposition in the SymmetricGroup.

If we take the graph in which the vertices correspond to vertices of the polyhedron, and edges to edges, we get the BubbleSortGraph().

INPUT:

  • n – integer

  • project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This operation turns the coordinates into floating point approximations and corresponds to the projection given by the matrix from zero_sum_projection().

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: perm4 = polytopes.permutahedron(4)
sage: perm4
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 24 vertices
sage: perm4.is_lattice_polytope()
True
sage: perm4.ehrhart_polynomial()   # optional - latte_int
16*t^3 + 15*t^2 + 6*t + 1

sage: perm4 = polytopes.permutahedron(4, project=True)
sage: perm4
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: perm4.plot()                                                          # needs sage.plot
Graphics3d Object
sage: perm4.graph().is_isomorphic(graphs.BubbleSortGraph(4))                # needs sage.graphs
True
>>> from sage.all import *
>>> perm4 = polytopes.permutahedron(Integer(4))
>>> perm4
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 24 vertices
>>> perm4.is_lattice_polytope()
True
>>> perm4.ehrhart_polynomial()   # optional - latte_int
16*t^3 + 15*t^2 + 6*t + 1

>>> perm4 = polytopes.permutahedron(Integer(4), project=True)
>>> perm4
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
>>> perm4.plot()                                                          # needs sage.plot
Graphics3d Object
>>> perm4.graph().is_isomorphic(graphs.BubbleSortGraph(Integer(4)))                # needs sage.graphs
True

As both Hrepresentation and Vrepresentation are known, the permutahedron can be set up with both using the backend field. The following takes very very long time to recompute, e.g. with backend ppl:

sage: polytopes.permutahedron(8, backend='field')  # (~1s)
A 7-dimensional polyhedron in QQ^8 defined as the convex hull of 40320 vertices
sage: polytopes.permutahedron(9, backend='field')  # not tested (memory consumption)  # (~5s)
A 8-dimensional polyhedron in QQ^9 defined as the convex hull of 362880 vertices
>>> from sage.all import *
>>> polytopes.permutahedron(Integer(8), backend='field')  # (~1s)
A 7-dimensional polyhedron in QQ^8 defined as the convex hull of 40320 vertices
>>> polytopes.permutahedron(Integer(9), backend='field')  # not tested (memory consumption)  # (~5s)
A 8-dimensional polyhedron in QQ^9 defined as the convex hull of 362880 vertices
rectified_one_hundred_twenty_cell(exact=True, backend=None)[source]#

Return the rectified 120-cell.

The rectified 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 1200 vertices. For more information see Wikipedia article Rectified 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.rectified_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1200 vertices
>>> from sage.all import *
>>> polytopes.rectified_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1200 vertices
rectified_six_hundred_cell(exact=True, backend=None)[source]#

Return the rectified 600-cell.

The rectified 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 720 vertices. For more information see Wikipedia article Rectified 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.rectified_six_hundred_cell(backend='normaliz')  # not tested - long time ~14sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 720 vertices
>>> from sage.all import *
>>> polytopes.rectified_six_hundred_cell(backend='normaliz')  # not tested - long time ~14sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 720 vertices
regular_polygon(n, exact=True, base_ring=None, backend=None)[source]#

Return a regular polygon with \(n\) vertices.

INPUT:

  • n – a positive integer, the number of vertices.

  • exact – (boolean, default True) if False floating point numbers are used for coordinates.

  • base_ring – a ring in which the coordinates will lie. It is None by default. If it is not provided and exact is True then it will be the field of real algebraic number, if exact is False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: octagon = polytopes.regular_polygon(8)
sage: octagon
A 2-dimensional polyhedron in AA^2 defined as the convex hull of 8 vertices
sage: octagon.n_vertices()
8
sage: v = octagon.volume()
sage: v
2.828427124746190?
sage: v == 2*QQbar(2).sqrt()
True
>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> octagon = polytopes.regular_polygon(Integer(8))
>>> octagon
A 2-dimensional polyhedron in AA^2 defined as the convex hull of 8 vertices
>>> octagon.n_vertices()
8
>>> v = octagon.volume()
>>> v
2.828427124746190?
>>> v == Integer(2)*QQbar(Integer(2)).sqrt()
True

Its non exact version:

sage: polytopes.regular_polygon(3, exact=False).vertices()
(A vertex at (0.0, 1.0),
 A vertex at (0.8660254038, -0.5),
 A vertex at (-0.8660254038, -0.5))
sage: polytopes.regular_polygon(25, exact=False).n_vertices()
25
>>> from sage.all import *
>>> polytopes.regular_polygon(Integer(3), exact=False).vertices()
(A vertex at (0.0, 1.0),
 A vertex at (0.8660254038, -0.5),
 A vertex at (-0.8660254038, -0.5))
>>> polytopes.regular_polygon(Integer(25), exact=False).n_vertices()
25
rhombic_dodecahedron(backend=None)[source]#

Return the rhombic dodecahedron.

The rhombic dodecahedron is a polytope dual to the cuboctahedron. It has 14 vertices and 12 faces. For more information see the Wikipedia article Rhombic_dodecahedron.

INPUT:

  • backend – the backend to use to create the polytope.

See also

cuboctahedron()

EXAMPLES:

sage: rd = polytopes.rhombic_dodecahedron()
sage: rd.f_vector()
(1, 14, 24, 12, 1)
>>> from sage.all import *
>>> rd = polytopes.rhombic_dodecahedron()
>>> rd.f_vector()
(1, 14, 24, 12, 1)

Its facets are 12 quadrilaterals (not all identical):

sage: sum(1 for f in rd.facets() if len(f.vertices()) == 4)
12
>>> from sage.all import *
>>> sum(Integer(1) for f in rd.facets() if len(f.vertices()) == Integer(4))
12

Some more computations:

sage: p = rd.ehrhart_polynomial()    # optional - latte_int
sage: p                              # optional - latte_int
16*t^3 + 12*t^2 + 4*t + 1
sage: [p(i) for i in [1,2,3,4]]      # optional - latte_int
[33, 185, 553, 1233]
sage: [len((i*rd).integral_points()) for i in [1,2,3,4]]
[33, 185, 553, 1233]
>>> from sage.all import *
>>> p = rd.ehrhart_polynomial()    # optional - latte_int
>>> p                              # optional - latte_int
16*t^3 + 12*t^2 + 4*t + 1
>>> [p(i) for i in [Integer(1),Integer(2),Integer(3),Integer(4)]]      # optional - latte_int
[33, 185, 553, 1233]
>>> [len((i*rd).integral_points()) for i in [Integer(1),Integer(2),Integer(3),Integer(4)]]
[33, 185, 553, 1233]
rhombicosidodecahedron(exact=True, base_ring=None, backend=None)[source]#

Return the rhombicosidodecahedron.

The rhombicosidodecahedron is an Archimedean solid. It has 62 faces and 60 vertices. For more information, see the Wikipedia article Rhombicosidodecahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: rid = polytopes.rhombicosidodecahedron()   # long time (6secs)
sage: rid.f_vector()                             # long time
(1, 60, 120, 62, 1)
sage: rid.base_ring()                            # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?
>>> from sage.all import *
>>> rid = polytopes.rhombicosidodecahedron()   # long time (6secs)
>>> rid.f_vector()                             # long time
(1, 60, 120, 62, 1)
>>> rid.base_ring()                            # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?

A much faster implementation using floating point approximations:

sage: rid = polytopes.rhombicosidodecahedron(exact=False)
sage: rid.f_vector()
(1, 60, 120, 62, 1)
sage: rid.base_ring()
Real Double Field
>>> from sage.all import *
>>> rid = polytopes.rhombicosidodecahedron(exact=False)
>>> rid.f_vector()
(1, 60, 120, 62, 1)
>>> rid.base_ring()
Real Double Field

Its facets are 20 triangles, 30 squares and 12 pentagons:

sage: sum(1 for f in rid.facets() if len(f.vertices()) == 3)
20
sage: sum(1 for f in rid.facets() if len(f.vertices()) == 4)
30
sage: sum(1 for f in rid.facets() if len(f.vertices()) == 5)
12
>>> from sage.all import *
>>> sum(Integer(1) for f in rid.facets() if len(f.vertices()) == Integer(3))
20
>>> sum(Integer(1) for f in rid.facets() if len(f.vertices()) == Integer(4))
30
>>> sum(Integer(1) for f in rid.facets() if len(f.vertices()) == Integer(5))
12
runcinated_one_hundred_twenty_cell(exact=False, backend=None)[source]#

Return the runcinated 120-cell.

The runcinated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 2400 vertices. For more information see Wikipedia article Runcinated 120-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcinated_one_hundred_twenty_cell(exact=False)  # not tested - very long time
doctest:warning ...  UserWarning: This polyhedron data is
numerically complicated; cdd could not convert between the inexact
V and H representation without loss of data. The resulting object
might show inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 2400 vertices
>>> from sage.all import *
>>> polytopes.runcinated_one_hundred_twenty_cell(exact=False)  # not tested - very long time
doctest:warning ...  UserWarning: This polyhedron data is
numerically complicated; cdd could not convert between the inexact
V and H representation without loss of data. The resulting object
might show inconsistencies.
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 2400 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.runcinated_one_hundred_twenty_cell(exact=True,   # not tested - very long time
....:                                              backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices
>>> from sage.all import *
>>> polytopes.runcinated_one_hundred_twenty_cell(exact=True,   # not tested - very long time
...                                              backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices
runcitruncated_one_hundred_twenty_cell(exact=False, backend=None)[source]#

Return the runcitruncated 120-cell.

The runcitruncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Runcitruncated 120-cell.

Warning

The coordinates are inexact by default. The computation with inexact coordinates (using the backend 'cdd') issues a UserWarning on inconsistencies.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcitruncated_one_hundred_twenty_cell(exact=False)  # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
>>> from sage.all import *
>>> polytopes.runcitruncated_one_hundred_twenty_cell(exact=False)  # not tested - very long time
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.runcitruncated_one_hundred_twenty_cell(exact=True,   # not tested - very long time
....:                                                  backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
>>> from sage.all import *
>>> polytopes.runcitruncated_one_hundred_twenty_cell(exact=True,   # not tested - very long time
...                                                  backend='normaliz')
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 7200 vertices
runcitruncated_six_hundred_cell(exact=True, backend=None)[source]#

Return the runcitruncated 600-cell.

The runcitruncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 7200 vertices. For more information see Wikipedia article Runcitruncated 600-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.runcitruncated_six_hundred_cell(backend='normaliz')  # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of
7200 vertices
>>> from sage.all import *
>>> polytopes.runcitruncated_six_hundred_cell(backend='normaliz')  # not tested - very long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of
7200 vertices
simplex(dim=3, project=False, base_ring=None, backend=None)[source]#

Return the dim dimensional simplex.

The \(d\)-simplex is the convex hull in \(\RR^{d+1}\) of the standard basis \((1,0,\ldots,0)\), \((0,1,\ldots,0)\), ldots, \((0,0,\ldots,1)\). For more information, see the Wikipedia article Simplex.

INPUT:

  • dim – The dimension of the simplex, a positive integer.

  • project – (boolean, default False) if True, the polytope is (isometrically) projected to a vector space of dimension dim-1. This corresponds to the projection given by the matrix from zero_sum_projection(). By default, this operation turns the coordinates into floating point approximations (see base_ring).

  • base_ring – the base ring to use to create the polytope. If project is False, this defaults to \(\ZZ\). Otherwise, it defaults to RDF.

  • backend – the backend to use to create the polytope.

See also

tetrahedron()

EXAMPLES:

sage: s5 = polytopes.simplex(5)
sage: s5
A 5-dimensional polyhedron in ZZ^6 defined as the convex hull of 6 vertices
sage: s5.f_vector()
(1, 6, 15, 20, 15, 6, 1)

sage: s5 = polytopes.simplex(5, project=True)
sage: s5
A 5-dimensional polyhedron in RDF^5 defined as the convex hull of 6 vertices
>>> from sage.all import *
>>> s5 = polytopes.simplex(Integer(5))
>>> s5
A 5-dimensional polyhedron in ZZ^6 defined as the convex hull of 6 vertices
>>> s5.f_vector()
(1, 6, 15, 20, 15, 6, 1)

>>> s5 = polytopes.simplex(Integer(5), project=True)
>>> s5
A 5-dimensional polyhedron in RDF^5 defined as the convex hull of 6 vertices

Its volume is \(\sqrt{d+1} / d!\):

sage: s5 = polytopes.simplex(5, project=True)
sage: s5.volume()      # abs tol 1e-10
0.0204124145231931
sage: sqrt(6.) / factorial(5)
0.0204124145231931

sage: s6 = polytopes.simplex(6, project=True)
sage: s6.volume()      # abs tol 1e-10
0.00367465459870082
sage: sqrt(7.) / factorial(6)
0.00367465459870082
>>> from sage.all import *
>>> s5 = polytopes.simplex(Integer(5), project=True)
>>> s5.volume()      # abs tol 1e-10
0.0204124145231931
>>> sqrt(RealNumber('6.')) / factorial(Integer(5))
0.0204124145231931

>>> s6 = polytopes.simplex(Integer(6), project=True)
>>> s6.volume()      # abs tol 1e-10
0.00367465459870082
>>> sqrt(RealNumber('7.')) / factorial(Integer(6))
0.00367465459870082

Computation in algebraic reals:

sage: s3 = polytopes.simplex(3, project=True, base_ring=AA)                 # needs sage.rings.number_field
sage: s3.volume() == sqrt(3+1) / factorial(3)                               # needs sage.rings.number_field
True
>>> from sage.all import *
>>> s3 = polytopes.simplex(Integer(3), project=True, base_ring=AA)                 # needs sage.rings.number_field
>>> s3.volume() == sqrt(Integer(3)+Integer(1)) / factorial(Integer(3))                               # needs sage.rings.number_field
True
six_hundred_cell(exact=False, backend=None)[source]#

Return the standard 600-cell polytope.

The 600-cell is a 4-dimensional regular polytope. In many ways this is an analogue of the icosahedron.

Warning

The coordinates are not exact by default. The computation with exact coordinates takes a huge amount of time.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: p600 = polytopes.six_hundred_cell(); p600                             # needs sage.groups
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 120 vertices
sage: p600.f_vector()               # long time (~2sec)                     # needs sage.groups
(1, 120, 720, 1200, 600, 1)
>>> from sage.all import *
>>> p600 = polytopes.six_hundred_cell(); p600                             # needs sage.groups
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 120 vertices
>>> p600.f_vector()               # long time (~2sec)                     # needs sage.groups
(1, 120, 720, 1200, 600, 1)

Computation with exact coordinates is currently too long to be useful:

sage: p600 = polytopes.six_hundred_cell(exact=True)         # long time, not tested, needs sage.groups
sage: len(list(p600.bounded_edges()))                       # long time, not tested, needs sage.groups
720
>>> from sage.all import *
>>> p600 = polytopes.six_hundred_cell(exact=True)         # long time, not tested, needs sage.groups
>>> len(list(p600.bounded_edges()))                       # long time, not tested, needs sage.groups
720
small_rhombicuboctahedron(exact=True, base_ring=None, backend=None)[source]#

Return the (small) rhombicuboctahedron.

The rhombicuboctahedron is an Archimedean solid with 24 vertices and 26 faces. See the Wikipedia article Rhombicuboctahedron for more information.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: sr = polytopes.small_rhombicuboctahedron()                            # needs sage.rings.number_field
sage: sr.f_vector()                                                         # needs sage.rings.number_field
(1, 24, 48, 26, 1)
sage: sr.volume()                                                           # needs sage.rings.number_field
80/3*sqrt2 + 32
>>> from sage.all import *
>>> sr = polytopes.small_rhombicuboctahedron()                            # needs sage.rings.number_field
>>> sr.f_vector()                                                         # needs sage.rings.number_field
(1, 24, 48, 26, 1)
>>> sr.volume()                                                           # needs sage.rings.number_field
80/3*sqrt2 + 32

The faces are \(8\) equilateral triangles and \(18\) squares:

sage: sum(1 for f in sr.facets() if len(f.vertices()) == 3)                 # needs sage.rings.number_field
8
sage: sum(1 for f in sr.facets() if len(f.vertices()) == 4)                 # needs sage.rings.number_field
18
>>> from sage.all import *
>>> sum(Integer(1) for f in sr.facets() if len(f.vertices()) == Integer(3))                 # needs sage.rings.number_field
8
>>> sum(Integer(1) for f in sr.facets() if len(f.vertices()) == Integer(4))                 # needs sage.rings.number_field
18

Its non exact version:

sage: sr = polytopes.small_rhombicuboctahedron(False)
sage: sr
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of
24 vertices
sage: sr.f_vector()
(1, 24, 48, 26, 1)
>>> from sage.all import *
>>> sr = polytopes.small_rhombicuboctahedron(False)
>>> sr
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of
24 vertices
>>> sr.f_vector()
(1, 24, 48, 26, 1)
snub_cube(exact=False, base_ring=None, backend=None, verbose=False)[source]#

Return a snub cube.

The snub cube is an Archimedean solid. It has 24 vertices and 38 faces. For more information see the Wikipedia article Snub_cube.

The constant \(z\) used in constructing this polytope is the reciprocal of the tribonacci constant, that is, the solution of the equation \(x^3 + x^2 + x - 1 = 0\). See Wikipedia article Generalizations_of_Fibonacci_numbers#Tribonacci_numbers.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations

  • base_ring – the field to use. If None (the default), construct the exact number field needed (if exact is True) or default to RDF (if exact is True).

  • backend – the backend to use to create the polytope. If None (the default), the backend will be selected automatically.

EXAMPLES:

sage: # needs sage.groups
sage: sc_inexact = polytopes.snub_cube(exact=False); sc_inexact
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
sage: sc_inexact.f_vector()
(1, 24, 60, 38, 1)

sage: # long time, needs sage.groups sage.rings.number_field
sage: sc_exact = polytopes.snub_cube(exact=True)
sage: sc_exact.f_vector()
(1, 24, 60, 38, 1)
sage: sorted(sc_exact.vertices())
[A vertex at (-1, -z, -z^2),
 A vertex at (-1, -z^2, z),
 A vertex at (-1, z^2, -z),
 A vertex at (-1, z, z^2),
 A vertex at (-z, -1, z^2),
 A vertex at (-z, -z^2, -1),
 A vertex at (-z, z^2, 1),
 A vertex at (-z, 1, -z^2),
 A vertex at (-z^2, -1, -z),
 A vertex at (-z^2, -z, 1),
 A vertex at (-z^2, z, -1),
 A vertex at (-z^2, 1, z),
 A vertex at (z^2, -1, z),
 A vertex at (z^2, -z, -1),
 A vertex at (z^2, z, 1),
 A vertex at (z^2, 1, -z),
 A vertex at (z, -1, -z^2),
 A vertex at (z, -z^2, 1),
 A vertex at (z, z^2, -1),
 A vertex at (z, 1, z^2),
 A vertex at (1, -z, z^2),
 A vertex at (1, -z^2, -z),
 A vertex at (1, z^2, z),
 A vertex at (1, z, -z^2)]
sage: sc_exact.is_combinatorially_isomorphic(sc_inexact)
True
>>> from sage.all import *
>>> # needs sage.groups
>>> sc_inexact = polytopes.snub_cube(exact=False); sc_inexact
A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 24 vertices
>>> sc_inexact.f_vector()
(1, 24, 60, 38, 1)

>>> # long time, needs sage.groups sage.rings.number_field
>>> sc_exact = polytopes.snub_cube(exact=True)
>>> sc_exact.f_vector()
(1, 24, 60, 38, 1)
>>> sorted(sc_exact.vertices())
[A vertex at (-1, -z, -z^2),
 A vertex at (-1, -z^2, z),
 A vertex at (-1, z^2, -z),
 A vertex at (-1, z, z^2),
 A vertex at (-z, -1, z^2),
 A vertex at (-z, -z^2, -1),
 A vertex at (-z, z^2, 1),
 A vertex at (-z, 1, -z^2),
 A vertex at (-z^2, -1, -z),
 A vertex at (-z^2, -z, 1),
 A vertex at (-z^2, z, -1),
 A vertex at (-z^2, 1, z),
 A vertex at (z^2, -1, z),
 A vertex at (z^2, -z, -1),
 A vertex at (z^2, z, 1),
 A vertex at (z^2, 1, -z),
 A vertex at (z, -1, -z^2),
 A vertex at (z, -z^2, 1),
 A vertex at (z, z^2, -1),
 A vertex at (z, 1, z^2),
 A vertex at (1, -z, z^2),
 A vertex at (1, -z^2, -z),
 A vertex at (1, z^2, z),
 A vertex at (1, z, -z^2)]
>>> sc_exact.is_combinatorially_isomorphic(sc_inexact)
True
snub_dodecahedron(base_ring=None, backend=None, verbose=False)[source]#

Return the snub dodecahedron.

The snub dodecahedron is an Archimedean solid. It has 92 faces and 60 vertices. For more information, see the Wikipedia article Snub_dodecahedron.

INPUT:

  • base_ring – the ring in which the coordinates will belong to. If it is not provided it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

Only the backend using the optional normaliz package can construct the snub dodecahedron in reasonable time:

sage: sd = polytopes.snub_dodecahedron(base_ring=AA,        # optional - pynormaliz, long time
....:                                  backend='normaliz')
sage: sd.f_vector()                                         # optional - pynormaliz, long time
(1, 60, 150, 92, 1)
sage: sd.base_ring()                                        # optional - pynormaliz, long time
Algebraic Real Field
>>> from sage.all import *
>>> sd = polytopes.snub_dodecahedron(base_ring=AA,        # optional - pynormaliz, long time
...                                  backend='normaliz')
>>> sd.f_vector()                                         # optional - pynormaliz, long time
(1, 60, 150, 92, 1)
>>> sd.base_ring()                                        # optional - pynormaliz, long time
Algebraic Real Field

Its facets are 80 triangles and 12 pentagons:

sage: sum(1 for f in sd.facets()                            # optional - pynormaliz, long time
....:       if len(f.vertices()) == 3)
80
sage: sum(1 for f in sd.facets()                            # optional - pynormaliz, long time
....:       if len(f.vertices()) == 5)
12
>>> from sage.all import *
>>> sum(Integer(1) for f in sd.facets()                            # optional - pynormaliz, long time
...       if len(f.vertices()) == Integer(3))
80
>>> sum(Integer(1) for f in sd.facets()                            # optional - pynormaliz, long time
...       if len(f.vertices()) == Integer(5))
12
static symmetric_edge_polytope(backend=None)[source]#

Return the symmetric edge polytope of self.

The symmetric edge polytope (SEP) of a Graph on \(n\) vertices is the polytope in \(\ZZ^{n}\) defined as the convex hull of \(e_i - e_j\) and \(e_j - e_i\) for each edge \((i, j)\). Here \(e_1, \dots, e_n\) denotes the standard basis.

INPUT:

EXAMPLES:

The SEP of a \(4\)-cycle is a cube:

sage: G = graphs.CycleGraph(4)
sage: P = G.symmetric_edge_polytope(); P                                    # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cube())                     # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4))
>>> P = G.symmetric_edge_polytope(); P                                    # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 8 vertices
>>> P.is_combinatorially_isomorphic(polytopes.cube())                     # needs sage.geometry.polyhedron
True

The SEP of a complete graph on \(4\) vertices is a cuboctahedron:

sage: G = graphs.CompleteGraph(4)
sage: P = G.symmetric_edge_polytope(); P                                    # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 12 vertices
sage: P.is_combinatorially_isomorphic(polytopes.cuboctahedron())            # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(4))
>>> P = G.symmetric_edge_polytope(); P                                    # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 12 vertices
>>> P.is_combinatorially_isomorphic(polytopes.cuboctahedron())            # needs sage.geometry.polyhedron
True

The SEP of a graph with edges on \(n\) vertices has dimension \(n\) minus the number of connected components:

sage: n = randint(5, 12)
sage: G = Graph()
sage: while not G.num_edges():                                              # needs networkx
....:     G = graphs.RandomGNP(n, 0.2)
sage: P = G.symmetric_edge_polytope()                                       # needs networkx sage.geometry.polyhedron
sage: P.ambient_dim() == n                                                  # needs networkx sage.geometry.polyhedron
True
sage: P.dim() == n - G.connected_components_number()                        # needs networkx sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(5), Integer(12))
>>> G = Graph()
>>> while not G.num_edges():                                              # needs networkx
...     G = graphs.RandomGNP(n, RealNumber('0.2'))
>>> P = G.symmetric_edge_polytope()                                       # needs networkx sage.geometry.polyhedron
>>> P.ambient_dim() == n                                                  # needs networkx sage.geometry.polyhedron
True
>>> P.dim() == n - G.connected_components_number()                        # needs networkx sage.geometry.polyhedron
True

The SEP of a graph is isomorphic to the subdirect sum of its connected components SEP’s:

sage: n = randint(3, 6)
sage: G1 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: n = randint(3, 6)
sage: G2 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: G = G1.disjoint_union(G2)                                             # needs networkx
sage: P = G.symmetric_edge_polytope()                                       # needs networkx sage.geometry.polyhedron
sage: P1 = G1.symmetric_edge_polytope()                                     # needs networkx sage.geometry.polyhedron
sage: P2 = G2.symmetric_edge_polytope()                                     # needs networkx sage.geometry.polyhedron
sage: P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))                 # needs networkx sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(3), Integer(6))
>>> G1 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> n = randint(Integer(3), Integer(6))
>>> G2 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> G = G1.disjoint_union(G2)                                             # needs networkx
>>> P = G.symmetric_edge_polytope()                                       # needs networkx sage.geometry.polyhedron
>>> P1 = G1.symmetric_edge_polytope()                                     # needs networkx sage.geometry.polyhedron
>>> P2 = G2.symmetric_edge_polytope()                                     # needs networkx sage.geometry.polyhedron
>>> P.is_combinatorially_isomorphic(P1.subdirect_sum(P2))                 # needs networkx sage.geometry.polyhedron
True

All trees on \(n\) vertices have isomorphic SEPs:

sage: n = randint(4, 10)
sage: G1 = graphs.RandomTree(n)
sage: G2 = graphs.RandomTree(n)
sage: P1 = G1.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
sage: P2 = G2.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
sage: P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(4), Integer(10))
>>> G1 = graphs.RandomTree(n)
>>> G2 = graphs.RandomTree(n)
>>> P1 = G1.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
>>> P2 = G2.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
>>> P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True

However, there are still many different SEPs:

sage: len(list(graphs(5)))
34
sage: polys = []
sage: for G in graphs(5):                                                   # needs sage.geometry.polyhedron
....:     P = G.symmetric_edge_polytope()
....:     for P1 in polys:
....:         if P.is_combinatorially_isomorphic(P1):
....:             break
....:     else:
....:         polys.append(P)
sage: len(polys)                                                            # needs sage.geometry.polyhedron
25
>>> from sage.all import *
>>> len(list(graphs(Integer(5))))
34
>>> polys = []
>>> for G in graphs(Integer(5)):                                                   # needs sage.geometry.polyhedron
...     P = G.symmetric_edge_polytope()
...     for P1 in polys:
...         if P.is_combinatorially_isomorphic(P1):
...             break
...     else:
...         polys.append(P)
>>> len(polys)                                                            # needs sage.geometry.polyhedron
25

A non-trivial example of two graphs with isomorphic SEPs:

sage: G1 = graphs.CycleGraph(4)
sage: G1.add_edges([[0, 5], [5, 2], [1, 6], [6, 2]])
sage: G2 = copy(G1)
sage: G1.add_edges([[2, 7], [7, 3]])
sage: G2.add_edges([[0, 7], [7, 3]])
sage: G1.is_isomorphic(G2)
False
sage: P1 = G1.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
sage: P2 = G2.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
sage: P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True
>>> from sage.all import *
>>> G1 = graphs.CycleGraph(Integer(4))
>>> G1.add_edges([[Integer(0), Integer(5)], [Integer(5), Integer(2)], [Integer(1), Integer(6)], [Integer(6), Integer(2)]])
>>> G2 = copy(G1)
>>> G1.add_edges([[Integer(2), Integer(7)], [Integer(7), Integer(3)]])
>>> G2.add_edges([[Integer(0), Integer(7)], [Integer(7), Integer(3)]])
>>> G1.is_isomorphic(G2)
False
>>> P1 = G1.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
>>> P2 = G2.symmetric_edge_polytope()                                     # needs sage.geometry.polyhedron
>>> P1.is_combinatorially_isomorphic(P2)                                  # needs sage.geometry.polyhedron
True

Apparently, glueing two graphs together on a vertex gives isomorphic SEPs:

sage: n = randint(3, 7)
sage: g1 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: g2 = graphs.RandomGNP(n, 0.2)                                         # needs networkx
sage: G = g1.disjoint_union(g2)                                             # needs networkx
sage: H = copy(G)                                                           # needs networkx
sage: G.merge_vertices(((0, randrange(n)), (1, randrange(n))))              # needs networkx
sage: H.merge_vertices(((0, randrange(n)), (1, randrange(n))))              # needs networkx
sage: PG = G.symmetric_edge_polytope()                                      # needs networkx sage.geometry.polyhedron
sage: PH = H.symmetric_edge_polytope()                                      # needs networkx sage.geometry.polyhedron
sage: PG.is_combinatorially_isomorphic(PH)                                  # needs networkx sage.geometry.polyhedron
True
>>> from sage.all import *
>>> n = randint(Integer(3), Integer(7))
>>> g1 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> g2 = graphs.RandomGNP(n, RealNumber('0.2'))                                         # needs networkx
>>> G = g1.disjoint_union(g2)                                             # needs networkx
>>> H = copy(G)                                                           # needs networkx
>>> G.merge_vertices(((Integer(0), randrange(n)), (Integer(1), randrange(n))))              # needs networkx
>>> H.merge_vertices(((Integer(0), randrange(n)), (Integer(1), randrange(n))))              # needs networkx
>>> PG = G.symmetric_edge_polytope()                                      # needs networkx sage.geometry.polyhedron
>>> PH = H.symmetric_edge_polytope()                                      # needs networkx sage.geometry.polyhedron
>>> PG.is_combinatorially_isomorphic(PH)                                  # needs networkx sage.geometry.polyhedron
True
tetrahedron(backend=None)[source]#

Return the tetrahedron.

The tetrahedron is a Platonic solid with 4 vertices and 4 faces dual to itself. It can be defined as the convex hull of the 4 vertices \((0, 0, 0)\), \((1, 1, 0)\), \((1, 0, 1)\) and \((0, 1, 1)\). For more information, see the Wikipedia article Tetrahedron.

INPUT:

  • backend – the backend to use to create the polytope.

See also

simplex()

EXAMPLES:

sage: co = polytopes.tetrahedron()
sage: co.f_vector()
(1, 4, 6, 4, 1)
>>> from sage.all import *
>>> co = polytopes.tetrahedron()
>>> co.f_vector()
(1, 4, 6, 4, 1)

Its facets are 4 triangles:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
4
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(3))
4

Some more computation:

sage: co.volume()
1/3
sage: co.ehrhart_polynomial()      # optional - latte_int
1/3*t^3 + t^2 + 5/3*t + 1
>>> from sage.all import *
>>> co.volume()
1/3
>>> co.ehrhart_polynomial()      # optional - latte_int
1/3*t^3 + t^2 + 5/3*t + 1
truncated_cube(exact=True, base_ring=None, backend=None)[source]#

Return the truncated cube.

The truncated cube is an Archimedean solid with 24 vertices and 14 faces. It can be defined as the convex hull of the 24 vertices \((\pm x, \pm 1, \pm 1), (\pm 1, \pm x, \pm 1), (\pm 1, \pm 1, \pm x)\) where \(x = \sqrt(2) - 1\). For more information, see the Wikipedia article Truncated_cube.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\sqrt{2}]\) and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_cube()                                       # needs sage.rings.number_field
sage: co.f_vector()                                                         # needs sage.rings.number_field
(1, 24, 36, 14, 1)
>>> from sage.all import *
>>> co = polytopes.truncated_cube()                                       # needs sage.rings.number_field
>>> co.f_vector()                                                         # needs sage.rings.number_field
(1, 24, 36, 14, 1)

Its facets are 8 triangles and 6 octogons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)                 # needs sage.rings.number_field
8
sage: sum(1 for f in co.facets() if len(f.vertices()) == 8)                 # needs sage.rings.number_field
6
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(3))                 # needs sage.rings.number_field
8
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(8))                 # needs sage.rings.number_field
6

Some more computation:

sage: co.volume()                                                           # needs sage.rings.number_field
56/3*sqrt2 - 56/3
>>> from sage.all import *
>>> co.volume()                                                           # needs sage.rings.number_field
56/3*sqrt2 - 56/3
truncated_dodecahedron(exact=True, base_ring=None, backend=None)[source]#

Return the truncated dodecahedron.

The truncated dodecahedron is an Archimedean solid. It has 32 faces and 60 vertices. For more information, see the Wikipedia article Truncated dodecahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: td = polytopes.truncated_dodecahedron()                               # needs sage.rings.number_field
sage: td.f_vector()                                                         # needs sage.rings.number_field
(1, 60, 90, 32, 1)
sage: td.base_ring()                                                        # needs sage.rings.number_field
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?
>>> from sage.all import *
>>> td = polytopes.truncated_dodecahedron()                               # needs sage.rings.number_field
>>> td.f_vector()                                                         # needs sage.rings.number_field
(1, 60, 90, 32, 1)
>>> td.base_ring()                                                        # needs sage.rings.number_field
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?

Its facets are 20 triangles and 12 regular decagons:

sage: sum(1 for f in td.facets() if len(f.vertices()) == 3)                 # needs sage.rings.number_field
20
sage: sum(1 for f in td.facets() if len(f.vertices()) == 10)                # needs sage.rings.number_field
12
>>> from sage.all import *
>>> sum(Integer(1) for f in td.facets() if len(f.vertices()) == Integer(3))                 # needs sage.rings.number_field
20
>>> sum(Integer(1) for f in td.facets() if len(f.vertices()) == Integer(10))                # needs sage.rings.number_field
12

The faster implementation using floating point approximations does not fully work unfortunately, see https://github.com/cddlib/cddlib/pull/7 for a detailed discussion of this case:

sage: td = polytopes.truncated_dodecahedron(exact=False)  # random
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
sage: td.f_vector()
Traceback (most recent call last):
...
ValueError: not all vertices are intersections of facets
sage: td.base_ring()
Real Double Field
>>> from sage.all import *
>>> td = polytopes.truncated_dodecahedron(exact=False)  # random
doctest:warning
...
UserWarning: This polyhedron data is numerically complicated; cdd
could not convert between the inexact V and H representation
without loss of data. The resulting object might show
inconsistencies.
>>> td.f_vector()
Traceback (most recent call last):
...
ValueError: not all vertices are intersections of facets
>>> td.base_ring()
Real Double Field
truncated_icosidodecahedron(exact=True, base_ring=None, backend=None)[source]#

Return the truncated icosidodecahedron.

The truncated icosidodecahedron is an Archimedean solid. It has 62 faces and 120 vertices. For more information, see the Wikipedia article Truncated_icosidodecahedron.

INPUT:

  • exact – (boolean, default True) If False use an approximate ring for the coordinates.

  • base_ring – the ring in which the coordinates will belong to. If it is not provided and exact=True it will be a the number field \(\QQ[\phi]\) where \(\phi\) is the golden ratio and if exact=False it will be the real double field.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: ti = polytopes.truncated_icosidodecahedron()  # long time
sage: ti.f_vector()                                 # long time
(1, 120, 180, 62, 1)
sage: ti.base_ring()                                # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?
>>> from sage.all import *
>>> ti = polytopes.truncated_icosidodecahedron()  # long time
>>> ti.f_vector()                                 # long time
(1, 120, 180, 62, 1)
>>> ti.base_ring()                                # long time
Number Field in sqrt5 with defining polynomial x^2 - 5
 with sqrt5 = 2.236067977499790?

The implementation using floating point approximations is much faster:

sage: ti = polytopes.truncated_icosidodecahedron(exact=False) # random
sage: ti.f_vector()
(1, 120, 180, 62, 1)
sage: ti.base_ring()
Real Double Field
>>> from sage.all import *
>>> ti = polytopes.truncated_icosidodecahedron(exact=False) # random
>>> ti.f_vector()
(1, 120, 180, 62, 1)
>>> ti.base_ring()
Real Double Field

Its facets are 30 squares, 20 hexagons and 12 decagons:

sage: sum(1 for f in ti.facets() if len(f.vertices()) == 4)
30
sage: sum(1 for f in ti.facets() if len(f.vertices()) == 6)
20
sage: sum(1 for f in ti.facets() if len(f.vertices()) == 10)
12
>>> from sage.all import *
>>> sum(Integer(1) for f in ti.facets() if len(f.vertices()) == Integer(4))
30
>>> sum(Integer(1) for f in ti.facets() if len(f.vertices()) == Integer(6))
20
>>> sum(Integer(1) for f in ti.facets() if len(f.vertices()) == Integer(10))
12
truncated_octahedron(backend=None)[source]#

Return the truncated octahedron.

The truncated octahedron is an Archimedean solid with 24 vertices and 14 faces. It can be defined as the convex hull off all the permutations of \((0, \pm 1, \pm 2)\). For more information, see the Wikipedia article Truncated_octahedron.

This is also known as the permutohedron of dimension 3.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_octahedron()
sage: co.f_vector()
(1, 24, 36, 14, 1)
>>> from sage.all import *
>>> co = polytopes.truncated_octahedron()
>>> co.f_vector()
(1, 24, 36, 14, 1)

Its facets are 6 squares and 8 hexagons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 4)
6
sage: sum(1 for f in co.facets() if len(f.vertices()) == 6)
8
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(4))
6
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(6))
8

Some more computation:

sage: co.volume()
32
sage: co.ehrhart_polynomial()       # optional - latte_int                  # needs sage.combinat
32*t^3 + 18*t^2 + 6*t + 1
>>> from sage.all import *
>>> co.volume()
32
>>> co.ehrhart_polynomial()       # optional - latte_int                  # needs sage.combinat
32*t^3 + 18*t^2 + 6*t + 1
truncated_one_hundred_twenty_cell(exact=True, backend=None)[source]#

Return the truncated 120-cell.

The truncated 120-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 2400 vertices. For more information see Wikipedia article Truncated 120-cell.

Warning

The coordinates are exact by default. The computation with inexact coordinates (using the backend 'cdd') returns a numerical inconsistency error, and thus cannot be computed.

INPUT:

  • exact – (boolean, default True) if True use exact coordinates instead of floating point approximations.

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.truncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices
>>> from sage.all import *
>>> polytopes.truncated_one_hundred_twenty_cell(backend='normaliz')  # not tested - long time
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 2400 vertices
truncated_six_hundred_cell(exact=False, backend=None)[source]#

Return the truncated 600-cell.

The truncated 600-cell is a 4-dimensional 4-uniform polytope in the \(H_4\) family. It has 1440 vertices. For more information see Wikipedia article Truncated 600-cell.

Warning

The coordinates are not exact by default. The computation with exact coordinates takes a huge amount of time.

INPUT:

  • exact – (boolean, default False) if True use exact coordinates instead of floating point approximations

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.truncated_six_hundred_cell()  # not tested - long time
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 1440 vertices
>>> from sage.all import *
>>> polytopes.truncated_six_hundred_cell()  # not tested - long time
A 4-dimensional polyhedron in RDF^4 defined as the convex hull of 1440 vertices

It is possible to use the backend 'normaliz' to get an exact representation:

sage: polytopes.truncated_six_hundred_cell(exact=True,backend='normaliz') # not tested - long time ~16sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1440 vertices
>>> from sage.all import *
>>> polytopes.truncated_six_hundred_cell(exact=True,backend='normaliz') # not tested - long time ~16sec
A 4-dimensional polyhedron in AA^4 defined as the convex hull of 1440 vertices
truncated_tetrahedron(backend=None)[source]#

Return the truncated tetrahedron.

The truncated tetrahedron is an Archimedean solid with 12 vertices and 8 faces. It can be defined as the convex hull off all the permutations of \((\pm 1, \pm 1, \pm 3)\) with an even number of minus signs. For more information, see the Wikipedia article Truncated_tetrahedron.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: co = polytopes.truncated_tetrahedron()
sage: co.f_vector()
(1, 12, 18, 8, 1)
>>> from sage.all import *
>>> co = polytopes.truncated_tetrahedron()
>>> co.f_vector()
(1, 12, 18, 8, 1)

Its facets are 4 triangles and 4 hexagons:

sage: sum(1 for f in co.facets() if len(f.vertices()) == 3)
4
sage: sum(1 for f in co.facets() if len(f.vertices()) == 6)
4
>>> from sage.all import *
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(3))
4
>>> sum(Integer(1) for f in co.facets() if len(f.vertices()) == Integer(6))
4

Some more computation:

sage: co.volume()
184/3
sage: co.ehrhart_polynomial()      # optional - latte_int
184/3*t^3 + 28*t^2 + 26/3*t + 1
>>> from sage.all import *
>>> co.volume()
184/3
>>> co.ehrhart_polynomial()      # optional - latte_int
184/3*t^3 + 28*t^2 + 26/3*t + 1
twenty_four_cell(backend=None)[source]#

Return the standard 24-cell polytope.

The 24-cell polyhedron (also called icositetrachoron or octaplex) is a regular polyhedron in 4-dimension. For more information see the Wikipedia article 24-cell.

INPUT:

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: p24 = polytopes.twenty_four_cell()
sage: p24.f_vector()
(1, 24, 96, 96, 24, 1)
sage: v = next(p24.vertex_generator())
sage: for adj in v.neighbors(): print(adj)
A vertex at (-1/2, -1/2, -1/2, 1/2)
A vertex at (-1/2, -1/2, 1/2, -1/2)
A vertex at (-1, 0, 0, 0)
A vertex at (-1/2, 1/2, -1/2, -1/2)
A vertex at (0, -1, 0, 0)
A vertex at (0, 0, -1, 0)
A vertex at (0, 0, 0, -1)
A vertex at (1/2, -1/2, -1/2, -1/2)

sage: p24.volume()
2
>>> from sage.all import *
>>> p24 = polytopes.twenty_four_cell()
>>> p24.f_vector()
(1, 24, 96, 96, 24, 1)
>>> v = next(p24.vertex_generator())
>>> for adj in v.neighbors(): print(adj)
A vertex at (-1/2, -1/2, -1/2, 1/2)
A vertex at (-1/2, -1/2, 1/2, -1/2)
A vertex at (-1, 0, 0, 0)
A vertex at (-1/2, 1/2, -1/2, -1/2)
A vertex at (0, -1, 0, 0)
A vertex at (0, 0, -1, 0)
A vertex at (0, 0, 0, -1)
A vertex at (1/2, -1/2, -1/2, -1/2)

>>> p24.volume()
2
zonotope(generators, backend=None)[source]#

Return the zonotope, or parallelotope, spanned by the generators.

The parallelotope is the multi-dimensional generalization of a parallelogram (2 generators) and a parallelepiped (3 generators).

INPUT:

  • generators – a list of vectors of same dimension

  • backend – the backend to use to create the polytope.

EXAMPLES:

sage: polytopes.parallelotope([ (1,0), (0,1) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: polytopes.parallelotope([[1,2,3,4], [0,1,0,7], [3,1,0,2], [0,0,1,0]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

sage: K = QuadraticField(2, 'sqrt2')                                        # needs sage.rings.number_field
sage: sqrt2 = K.gen()                                                       # needs sage.rings.number_field
sage: P = polytopes.parallelotope([(1, sqrt2), (1, -1)]); P                 # needs sage.rings.number_field
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices
>>> from sage.all import *
>>> polytopes.parallelotope([ (Integer(1),Integer(0)), (Integer(0),Integer(1)) ])
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> polytopes.parallelotope([[Integer(1),Integer(2),Integer(3),Integer(4)], [Integer(0),Integer(1),Integer(0),Integer(7)], [Integer(3),Integer(1),Integer(0),Integer(2)], [Integer(0),Integer(0),Integer(1),Integer(0)]])
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 16 vertices

>>> K = QuadraticField(Integer(2), 'sqrt2')                                        # needs sage.rings.number_field
>>> sqrt2 = K.gen()                                                       # needs sage.rings.number_field
>>> P = polytopes.parallelotope([(Integer(1), sqrt2), (Integer(1), -Integer(1))]); P                 # needs sage.rings.number_field
A 2-dimensional polyhedron in (Number Field in sqrt2 with defining
polynomial x^2 - 2 with sqrt2 = 1.414213562373095?)^2 defined as
the convex hull of 4 vertices
sage.geometry.polyhedron.library.gale_transform_to_polytope(vectors, base_ring=None, backend=None)[source]#

Return the polytope associated to the list of vectors forming a Gale transform.

This function is the inverse of gale_transform() up to projective transformation.

INPUT:

  • vectors – the vectors of the Gale transform

  • base_ring – string (default: \(None\)); the base ring to be used for the construction

  • backend – string (default: \(None\)); the backend to use to create the polytope

Note

The order of the input vectors will not be preserved.

If the center of the (input) vectors is the origin, the function is much faster and might give a nicer representation of the polytope.

If this is not the case, the vectors will be scaled (each by a positive scalar) accordingly to obtain the polytope.

See also

:func`~sage.geometry.polyhedron.library.gale_transform_to_primal`.

EXAMPLES:

sage: from sage.geometry.polyhedron.library import gale_transform_to_polytope
sage: points = polytopes.octahedron().gale_transform()
sage: points
((0, -1), (-1, 0), (1, 1), (1, 1), (-1, 0), (0, -1))
sage: P = gale_transform_to_polytope(points); P
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
sage: P.vertices()
(A vertex at (-1, 0, 0),
 A vertex at (0, -1, 0),
 A vertex at (0, 0, -1),
 A vertex at (0, 0, 1),
 A vertex at (0, 1, 0),
 A vertex at (1, 0, 0))
>>> from sage.all import *
>>> from sage.geometry.polyhedron.library import gale_transform_to_polytope
>>> points = polytopes.octahedron().gale_transform()
>>> points
((0, -1), (-1, 0), (1, 1), (1, 1), (-1, 0), (0, -1))
>>> P = gale_transform_to_polytope(points); P
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices
>>> P.vertices()
(A vertex at (-1, 0, 0),
 A vertex at (0, -1, 0),
 A vertex at (0, 0, -1),
 A vertex at (0, 0, 1),
 A vertex at (0, 1, 0),
 A vertex at (1, 0, 0))

One can specify the base ring:

sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)]).vertices()
(A vertex at (-25, 0, 0),
 A vertex at (-15, 50, -60),
 A vertex at (0, -25, 0),
 A vertex at (0, 0, -25),
 A vertex at (16, -35, 54),
 A vertex at (24, 10, 31))
sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     base_ring=RDF).vertices()
(A vertex at (-0.64, 1.4, -2.16),
 A vertex at (-0.96, -0.4, -1.24),
 A vertex at (0.6, -2.0, 2.4),
 A vertex at (1.0, 0.0, 0.0),
 A vertex at (0.0, 1.0, 0.0),
 A vertex at (0.0, 0.0, 1.0))
>>> from sage.all import *
>>> gale_transform_to_polytope(
...     [(Integer(1),Integer(1)), (-Integer(1),-Integer(1)), (Integer(1),Integer(0)),
...      (-Integer(1),Integer(0)), (Integer(1),-Integer(1)), (-Integer(2),Integer(1))]).vertices()
(A vertex at (-25, 0, 0),
 A vertex at (-15, 50, -60),
 A vertex at (0, -25, 0),
 A vertex at (0, 0, -25),
 A vertex at (16, -35, 54),
 A vertex at (24, 10, 31))
>>> gale_transform_to_polytope(
...     [(Integer(1),Integer(1)), (-Integer(1),-Integer(1)), (Integer(1),Integer(0)),
...      (-Integer(1),Integer(0)), (Integer(1),-Integer(1)), (-Integer(2),Integer(1))],
...     base_ring=RDF).vertices()
(A vertex at (-0.64, 1.4, -2.16),
 A vertex at (-0.96, -0.4, -1.24),
 A vertex at (0.6, -2.0, 2.4),
 A vertex at (1.0, 0.0, 0.0),
 A vertex at (0.0, 1.0, 0.0),
 A vertex at (0.0, 0.0, 1.0))

One can also specify the backend:

sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     backend='field').backend()
'field'
sage: gale_transform_to_polytope(
....:     [(1,1), (-1,-1), (1,0),
....:      (-1,0), (1,-1), (-2,1)],
....:     backend='cdd', base_ring=RDF).backend()
'cdd'
>>> from sage.all import *
>>> gale_transform_to_polytope(
...     [(Integer(1),Integer(1)), (-Integer(1),-Integer(1)), (Integer(1),Integer(0)),
...      (-Integer(1),Integer(0)), (Integer(1),-Integer(1)), (-Integer(2),Integer(1))],
...     backend='field').backend()
'field'
>>> gale_transform_to_polytope(
...     [(Integer(1),Integer(1)), (-Integer(1),-Integer(1)), (Integer(1),Integer(0)),
...      (-Integer(1),Integer(0)), (Integer(1),-Integer(1)), (-Integer(2),Integer(1))],
...     backend='cdd', base_ring=RDF).backend()
'cdd'

A gale transform corresponds to a polytope if and only if every oriented (linear) hyperplane has at least two vectors on each side. See Theorem 6.19 of [Zie2007]. If this is not the case, one of two errors is raised.

If there is such a hyperplane with no vector on one side, the vectors are not totally cyclic:

sage: gale_transform_to_polytope([(0,1), (1,1), (1,0), (-1,0)])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic
>>> from sage.all import *
>>> gale_transform_to_polytope([(Integer(0),Integer(1)), (Integer(1),Integer(1)), (Integer(1),Integer(0)), (-Integer(1),Integer(0))])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

If every hyperplane has at least one vector on each side, then the gale transform corresponds to a point configuration. It corresponds to a polytope if and only if this point configuration is convex and if and only if every hyperplane contains at least two vectors of the gale transform on each side.

If this is not the case, an error is raised:

sage: gale_transform_to_polytope([(0,1), (1,1), (1,0), (-1,-1)])
Traceback (most recent call last):
...
ValueError: the gale transform does not correspond to a polytope
>>> from sage.all import *
>>> gale_transform_to_polytope([(Integer(0),Integer(1)), (Integer(1),Integer(1)), (Integer(1),Integer(0)), (-Integer(1),-Integer(1))])
Traceback (most recent call last):
...
ValueError: the gale transform does not correspond to a polytope
sage.geometry.polyhedron.library.gale_transform_to_primal(vectors, base_ring=None, backend=None)[source]#

Return a point configuration dual to a totally cyclic vector configuration.

This is the dehomogenized vector configuration dual to the input. The dual vector configuration is acyclic and can therefore be dehomogenized as the input is totally cyclic.

INPUT:

  • vectors – the ordered vectors of the Gale transform

  • base_ring – string (default: \(None\)); the base ring to be used for the construction

  • backend – string (default: \(None\)); the backend to be use to construct a polyhedral, used internally in case the center is not the origin, see Polyhedron()

OUTPUT: An ordered point configuration as list of vectors.

Note

If the center of the (input) vectors is the origin, the function is much faster and might give a nicer representation of the point configuration.

If this is not the case, the vectors will be scaled (each by a positive scalar) accordingly.

ALGORITHM:

Step 1: If the center of the (input) vectors is not the origin, we do an appropriate transformation to make it so.

Step 2: We add a row of ones on top of Matrix(vectors). The right kernel of this larger matrix is the dual configuration space, and a basis of this space provides the dual point configuration.

More concretely, the dual vector configuration (inhomogeneous) is obtained by taking a basis of the right kernel of Matrix(vectors). If the center of the (input) vectors is the origin, there exists a basis of the right kernel of the form [[1], [V]], where [1] represents a row of ones. Then, V is a dehomogenization and thus the dual point configuration.

To extend [1] to a basis of Matrix(vectors), we add a row of ones to Matrix(vectors) and calculate a basis of the right kernel of the obtained matrix.

REFERENCES:

For more information, see Section 6.4 of [Zie2007] or Definition 2.5.1 and Definition 4.1.35 of [DLRS2010].

See also

:func`~sage.geometry.polyhedron.library.gale_transform_to_polytope`.

EXAMPLES:

sage: from sage.geometry.polyhedron.library import gale_transform_to_primal
sage: points = ((0, -1), (-1, 0), (1, 1), (1, 1), (-1, 0), (0, -1))
sage: gale_transform_to_primal(points)
[(0, 0, 1), (0, 1, 0), (1, 0, 0), (-1, 0, 0), (0, -1, 0), (0, 0, -1)]
>>> from sage.all import *
>>> from sage.geometry.polyhedron.library import gale_transform_to_primal
>>> points = ((Integer(0), -Integer(1)), (-Integer(1), Integer(0)), (Integer(1), Integer(1)), (Integer(1), Integer(1)), (-Integer(1), Integer(0)), (Integer(0), -Integer(1)))
>>> gale_transform_to_primal(points)
[(0, 0, 1), (0, 1, 0), (1, 0, 0), (-1, 0, 0), (0, -1, 0), (0, 0, -1)]

One can specify the base ring:

sage: p = [(1,1), (-1,-1), (1,0), (-1,0), (1,-1), (-2,1)]
sage: gtpp = gale_transform_to_primal(p); gtpp
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]
sage: (matrix(RDF, gtpp)/25 +
....:  matrix(gale_transform_to_primal(p, base_ring=RDF))).norm() < 1e-15
True
>>> from sage.all import *
>>> p = [(Integer(1),Integer(1)), (-Integer(1),-Integer(1)), (Integer(1),Integer(0)), (-Integer(1),Integer(0)), (Integer(1),-Integer(1)), (-Integer(2),Integer(1))]
>>> gtpp = gale_transform_to_primal(p); gtpp
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]
>>> (matrix(RDF, gtpp)/Integer(25) +
...  matrix(gale_transform_to_primal(p, base_ring=RDF))).norm() < RealNumber('1e-15')
True

One can also specify the backend to be used internally:

sage: gale_transform_to_primal(p, backend='field')
[(48, -71, 88),
 (84, -28, 99),
 (-77, 154, -132),
 (-55, 0, 0),
 (0, -55, 0),
 (0, 0, -55)]
sage: gale_transform_to_primal(p, backend='normaliz')           # optional - pynormaliz
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]
>>> from sage.all import *
>>> gale_transform_to_primal(p, backend='field')
[(48, -71, 88),
 (84, -28, 99),
 (-77, 154, -132),
 (-55, 0, 0),
 (0, -55, 0),
 (0, 0, -55)]
>>> gale_transform_to_primal(p, backend='normaliz')           # optional - pynormaliz
[(16, -35, 54),
 (24, 10, 31),
 (-15, 50, -60),
 (-25, 0, 0),
 (0, -25, 0),
 (0, 0, -25)]

The input vectors should be totally cyclic:

sage: gale_transform_to_primal([(0,1), (1,0), (1,1), (-1,0)])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

sage: gale_transform_to_primal(
....:     [(1,1,0), (-1,-1,0), (1,0,0),
....:      (-1,0,0), (1,-1,0), (-2,1,0)], backend='field')
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic
>>> from sage.all import *
>>> gale_transform_to_primal([(Integer(0),Integer(1)), (Integer(1),Integer(0)), (Integer(1),Integer(1)), (-Integer(1),Integer(0))])
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic

>>> gale_transform_to_primal(
...     [(Integer(1),Integer(1),Integer(0)), (-Integer(1),-Integer(1),Integer(0)), (Integer(1),Integer(0),Integer(0)),
...      (-Integer(1),Integer(0),Integer(0)), (Integer(1),-Integer(1),Integer(0)), (-Integer(2),Integer(1),Integer(0))], backend='field')
Traceback (most recent call last):
...
ValueError: input vectors not totally cyclic
sage.geometry.polyhedron.library.project_points(*points, **kwds)[source]#

Projects a set of points into a vector space of dimension one less.

INPUT:

  • points… – the points to project.

  • base_ring – (defaults to RDF if keyword is None or not provided in kwds) the base ring to use.

The projection is isometric to the orthogonal projection on the hyperplane made of zero sum vector. Hence, if the set of points have all equal sums, then their projection is isometric (as a set of points).

The projection used is the matrix given by zero_sum_projection().

EXAMPLES:

sage: from sage.geometry.polyhedron.library import project_points
sage: project_points([2,-1,3,2])          # abs tol 1e-15
[(2.1213203435596424, -2.041241452319315, -0.577350269189626)]
sage: project_points([1,2,3],[3,3,5])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892), (0.0, -1.6329931618554523)]
>>> from sage.all import *
>>> from sage.geometry.polyhedron.library import project_points
>>> project_points([Integer(2),-Integer(1),Integer(3),Integer(2)])          # abs tol 1e-15
[(2.1213203435596424, -2.041241452319315, -0.577350269189626)]
>>> project_points([Integer(1),Integer(2),Integer(3)],[Integer(3),Integer(3),Integer(5)])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892), (0.0, -1.6329931618554523)]

These projections are compatible with the restriction. More precisely, given a vector \(v\), the projection of \(v\) restricted to the first \(i\) coordinates will be equal to the projection of the first \(i+1\) coordinates of \(v\):

sage: project_points([1,2])    # abs tol 1e-15
[(-0.7071067811865475)]
sage: project_points([1,2,3])  # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892)]
sage: project_points([1,2,3,4])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776)]
sage: project_points([1,2,3,4,0])   # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776, 2.23606797749979)]
>>> from sage.all import *
>>> project_points([Integer(1),Integer(2)])    # abs tol 1e-15
[(-0.7071067811865475)]
>>> project_points([Integer(1),Integer(2),Integer(3)])  # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892)]
>>> project_points([Integer(1),Integer(2),Integer(3),Integer(4)])     # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776)]
>>> project_points([Integer(1),Integer(2),Integer(3),Integer(4),Integer(0)])   # abs tol 1e-15
[(-0.7071067811865475, -1.2247448713915892, -1.7320508075688776, 2.23606797749979)]

Check that it is (almost) an isometry:

sage: V = list(map(vector, IntegerVectors(n=5, length=3)))
sage: P = project_points(*V)
sage: for i in range(21):                                                       # needs sage.combinat
....:     for j in range(21):
....:         assert abs((V[i]-V[j]).norm() - (P[i]-P[j]).norm()) < 0.00001
>>> from sage.all import *
>>> V = list(map(vector, IntegerVectors(n=Integer(5), length=Integer(3))))
>>> P = project_points(*V)
>>> for i in range(Integer(21)):                                                       # needs sage.combinat
...     for j in range(Integer(21)):
...         assert abs((V[i]-V[j]).norm() - (P[i]-P[j]).norm()) < RealNumber('0.00001')

Example with exact computation:

sage: V = [ vector(v) for v in IntegerVectors(n=4, length=2) ]
sage: P = project_points(*V, base_ring=AA)                                      # needs sage.combinat sage.rings.number_field
sage: for i in range(len(V)):                                                   # needs sage.combinat sage.rings.number_field
....:     for j in range(len(V)):
....:         assert (V[i]-V[j]).norm() == (P[i]-P[j]).norm()
>>> from sage.all import *
>>> V = [ vector(v) for v in IntegerVectors(n=Integer(4), length=Integer(2)) ]
>>> P = project_points(*V, base_ring=AA)                                      # needs sage.combinat sage.rings.number_field
>>> for i in range(len(V)):                                                   # needs sage.combinat sage.rings.number_field
...     for j in range(len(V)):
...         assert (V[i]-V[j]).norm() == (P[i]-P[j]).norm()
sage.geometry.polyhedron.library.zero_sum_projection(d, base_ring=None)[source]#

Return a matrix corresponding to the projection on the orthogonal of \((1,1,\ldots,1)\) in dimension \(d\).

The projection maps the orthonormal basis \((1,-1,0,\ldots,0) / \sqrt(2)\), \((1,1,-1,0,\ldots,0) / \sqrt(3)\), ldots, \((1,1,\ldots,1,-1) / \sqrt(d)\) to the canonical basis in \(\RR^{d-1}\).

OUTPUT:

A matrix of dimensions \((d-1)\times d\) defined over base_ring (default: RDF).

EXAMPLES:

sage: from sage.geometry.polyhedron.library import zero_sum_projection
sage: zero_sum_projection(2)
[ 0.7071067811865475 -0.7071067811865475]
sage: zero_sum_projection(3)
[ 0.7071067811865475 -0.7071067811865475                 0.0]
[ 0.4082482904638631  0.4082482904638631 -0.8164965809277261]
>>> from sage.all import *
>>> from sage.geometry.polyhedron.library import zero_sum_projection
>>> zero_sum_projection(Integer(2))
[ 0.7071067811865475 -0.7071067811865475]
>>> zero_sum_projection(Integer(3))
[ 0.7071067811865475 -0.7071067811865475                 0.0]
[ 0.4082482904638631  0.4082482904638631 -0.8164965809277261]

Exact computation in AA:

sage: zero_sum_projection(3, base_ring=AA)                                      # needs sage.rings.number_field
[ 0.7071067811865475? -0.7071067811865475?                    0]
[ 0.4082482904638630?  0.4082482904638630? -0.8164965809277260?]
>>> from sage.all import *
>>> zero_sum_projection(Integer(3), base_ring=AA)                                      # needs sage.rings.number_field
[ 0.7071067811865475? -0.7071067811865475?                    0]
[ 0.4082482904638630?  0.4082482904638630? -0.8164965809277260?]