Fast Lattice Polytopes using PPL.

The LatticePolytope_PPL() class is a thin wrapper around PPL polyhedra. Its main purpose is to be fast to construct, at the cost of being much less full-featured than the usual polyhedra. This makes it possible to iterate with it over the list of all 473800776 reflexive polytopes in 4 dimensions.

Note

For general lattice polyhedra you should use Polyhedron() with base_ring=ZZ.

The class derives from the PPL ppl.polyhedron.C_Polyhedron class, so you can work with the underlying generator and constraint objects. However, integral points are generally represented by \(\ZZ\)-vectors. In the following, we always use generator to refer the PPL generator objects and vertex (or integral point) for the corresponding \(\ZZ\)-vector.

EXAMPLES:

sage: vertices = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (-9, -6, -1, -1)]
sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: P = LatticePolytope_PPL(vertices);  P
A 4-dimensional lattice polytope in ZZ^4 with 5 vertices
sage: P.integral_points()
((-9, -6, -1, -1), (-3, -2, 0, 0), (-2, -1, 0, 0), (-1, -1, 0, 0),
 (-1, 0, 0, 0), (0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0))
sage: P.integral_points_not_interior_to_facets()
((-9, -6, -1, -1), (-3, -2, 0, 0), (0, 0, 0, 0), (1, 0, 0, 0),
 (0, 1, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0))

Fibrations of the lattice polytopes are defined as lattice sub-polytopes and give rise to fibrations of toric varieties for suitable fan refinements. We can compute them using fibration_generator()

sage: F = next(P.fibration_generator(2))
sage: F.vertices()
((1, 0, 0, 0), (0, 1, 0, 0), (-3, -2, 0, 0))

Finally, we can compute automorphisms and identify fibrations that only differ by a lattice automorphism:

sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
sage: fibers = [ f.vertices() for f in square.fibration_generator(1) ];  fibers
[((1, 0), (-1, 0)), ((0, 1), (0, -1)), ((-1, -1), (1, 1)), ((-1, 1), (1, -1))]
sage: square.pointsets_mod_automorphism(fibers)
(frozenset({(-1, -1), (1, 1)}), frozenset({(-1, 0), (1, 0)}))

AUTHORS:

• Volker Braun: initial version, 2012

sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL(*args)

Construct a new instance of the PPL-based lattice polytope class.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1,0),(0,1))
A 2-dimensional lattice polytope in ZZ^2 with 3 vertices

sage: from ppl import point, Generator_System, C_Polyhedron, Linear_Expression, Variable
sage: p = point(Linear_Expression([2,3],0));  p
point(2/1, 3/1)
sage: LatticePolytope_PPL(p)
A 0-dimensional lattice polytope in ZZ^2 with 1 vertex

sage: P = C_Polyhedron(Generator_System(p));  P
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point
sage: LatticePolytope_PPL(P)
A 0-dimensional lattice polytope in ZZ^2 with 1 vertex

A TypeError is raised if the arguments do not specify a lattice polytope:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1/2,1))
Traceback (most recent call last):
...
TypeError: unable to convert rational 1/2 to an integer

sage: from ppl import point, Generator_System, C_Polyhedron, Linear_Expression, Variable
sage: p = point(Linear_Expression([2,3],0), 5);  p
point(2/5, 3/5)
sage: LatticePolytope_PPL(p)
Traceback (most recent call last):
 ...
TypeError: generator is not a lattice polytope generator

sage: P = C_Polyhedron(Generator_System(p));  P
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point
sage: LatticePolytope_PPL(P)
Traceback (most recent call last):
...
TypeError: polyhedron has non-integral generators

class sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class

Bases: ppl.polyhedron.C_Polyhedron

The lattice polytope class.

You should use LatticePolytope_PPL() to construct instances.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1,0),(0,1))
A 2-dimensional lattice polytope in ZZ^2 with 3 vertices

affine_lattice_polytope()

Return the lattice polytope restricted to affine_space().

OUTPUT:

A new, full-dimensional lattice polytope.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: poly_4d = LatticePolytope_PPL((-9,-6,0,0),(0,1,0,0),(1,0,0,0));  poly_4d
A 2-dimensional lattice polytope in ZZ^4 with 3 vertices
sage: poly_4d.space_dimension()
4
sage: poly_2d = poly_4d.affine_lattice_polytope();  poly_2d
A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
sage: poly_2d.space_dimension()
2

affine_space()

Return the affine space spanned by the polytope.

OUTPUT:

The free module \(\ZZ^n\), where \(n\) is the dimension of the affine space spanned by the points of the polytope.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: point = LatticePolytope_PPL((1,2,3))
sage: point.affine_space()
Free module of degree 3 and rank 0 over Integer Ring
Echelon basis matrix:
[]
sage: line = LatticePolytope_PPL((1,1,1), (1,2,3))
sage: line.affine_space()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[0 1 2]

ambient_space()

Return the ambient space.

OUTPUT:

The free module \(\ZZ^d\), where \(d\) is the ambient space dimension.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: point = LatticePolytope_PPL((1,2,3))
sage: point.ambient_space()
Ambient free module of rank 3 over the principal ideal domain Integer Ring

base_projection(fiber)

The projection that maps the sub-polytope fiber to a single point.

OUTPUT:

The quotient module of the ambient space modulo the affine_space() spanned by the fiber.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
sage: fiber = next(poly.fibration_generator(2))
sage: poly.base_projection(fiber)
Finitely generated module V/W over Integer Ring with invariants (0, 0)

base_projection_matrix(fiber)

The projection that maps the sub-polytope fiber to a single point.

OUTPUT:

An integer matrix that represents the projection to the base.

See also

The base_projection() yields equivalent information, and is easier to use. However, just returning the matrix has lower overhead.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
sage: fiber = next(poly.fibration_generator(2))
sage: poly.base_projection_matrix(fiber)
[0 0 1 0]
[0 0 0 1]

Note that the basis choice in base_projection() for the quotient is usually different:

sage: proj = poly.base_projection(fiber)
sage: proj_matrix = poly.base_projection_matrix(fiber)
sage: [ proj(p) for p in poly.integral_points() ]
[(-1, -1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 1), (1, 0)]
sage: [ proj_matrix*p for p in poly.integral_points() ]
[(-1, -1), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 1), (1, 0)]

base_rays(fiber, points)

Return the primitive lattice vectors that generate the direction given by the base projection of points.

INPUT:

• fiber – a sub-lattice polytope defining the base_projection().

• points – the points to project to the base.

OUTPUT:

A tuple of primitive \(\ZZ\)-vectors.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: poly = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
sage: fiber = next(poly.fibration_generator(2))
sage: poly.base_rays(fiber, poly.integral_points_not_interior_to_facets())
((-1, -1), (0, 1), (1, 0))

sage: p = LatticePolytope_PPL((1,0),(1,2),(-1,0))
sage: f = LatticePolytope_PPL((1,0),(-1,0))
sage: p.base_rays(f, p.integral_points())
((1),)

bounding_box()

Return the coordinates of a rectangular box containing the non-empty polytope.

OUTPUT:

A pair of tuples (box_min, box_max) where box_min are the coordinates of a point bounding the coordinates of the polytope from below and box_max bounds the coordinates from above.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).bounding_box()
((0, 0), (1, 1))

contains(point_coordinates)

Test whether point is contained in the polytope.

INPUT:

• point_coordinates – a list/tuple/iterable of rational numbers. The coordinates of the point.

OUTPUT:

Boolean.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: line = LatticePolytope_PPL((1,2,3), (-1,-2,-3))
sage: line.contains([0,0,0])
True
sage: line.contains([1,0,0])
False

contains_origin()

Test whether the polytope contains the origin

OUTPUT:

Boolean.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((1,2,3), (-1,-2,-3)).contains_origin()
True
sage: LatticePolytope_PPL((1,2,5), (-1,-2,-3)).contains_origin()
False

embed_in_reflexive_polytope(output='hom')

Find an embedding as a sub-polytope of a maximal reflexive polytope.

INPUT:

• hom – string. One of 'hom' (default), 'polytope', or points. How the embedding is returned. See the output section for details.

OUTPUT:

An embedding into a reflexive polytope. Depending on the output option slightly different data is returned.

• If output='hom', a map from a reflexive polytope onto self is returned.

• If output='polytope', a reflexive polytope that contains self (up to a lattice linear transformation) is returned. That is, the domain of the output='hom' map is returned. If the affine span of self is less or equal 2-dimensional, the output is one of the following three possibilities:

  polar_P2_polytope(), polar_P1xP1_polytope(), or polar_P2_112_polytope().

• If output='points', a dictionary containing the integral points of self as keys and the corresponding integral point of the reflexive polytope as value.

If there is no such embedding, a LatticePolytopeNoEmbeddingError is raised. Even if it exists, the ambient reflexive polytope is usually not uniquely determined and a random but fixed choice will be returned.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: polygon = LatticePolytope_PPL((0,0,2,1),(0,1,2,0),(2,3,0,0),(2,0,0,3))
sage: polygon.embed_in_reflexive_polytope()
The map A*x+b with A=
[ 1  1]
[ 0  1]
[-1 -1]
[ 1  0]
b =
(-1, 0, 3, 0)
sage: polygon.embed_in_reflexive_polytope('polytope')
A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
sage: polygon.embed_in_reflexive_polytope('points')
{(0, 0, 2, 1): (1, 0),
 (0, 1, 2, 0): (0, 1),
 (1, 0, 1, 2): (2, 0),
 (1, 1, 1, 1): (1, 1),
 (1, 2, 1, 0): (0, 2),
 (2, 0, 0, 3): (3, 0),
 (2, 1, 0, 2): (2, 1),
 (2, 2, 0, 1): (1, 2),
 (2, 3, 0, 0): (0, 3)}

sage: LatticePolytope_PPL((0,0), (4,0), (0,4)).embed_in_reflexive_polytope()
Traceback (most recent call last):
...
LatticePolytopeNoEmbeddingError: not a sub-polytope of a reflexive polygon

fibration_generator(dim)

Generate the lattice polytope fibrations.

For the purposes of this function, a lattice polytope fiber is a sub-lattice polytope. Projecting the plane spanned by the subpolytope to a point yields another lattice polytope, the base of the fibration.

INPUT:

• dim – integer. The dimension of the lattice polytope fiber.

OUTPUT:

A generator yielding the distinct lattice polytope fibers of given dimension.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: p = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
sage: list( p.fibration_generator(2) )
[A 2-dimensional lattice polytope in ZZ^4 with 3 vertices]

has_IP_property()

Whether the lattice polytope has the IP property.

That is, the polytope is full-dimensional and the origin is a interior point not on the boundary.

OUTPUT:

Boolean.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((-1,-1),(0,1),(1,0)).has_IP_property()
True
sage: LatticePolytope_PPL((-1,-1),(1,1)).has_IP_property()
False

integral_points()

Return the integral points in the polyhedron.

Uses the naive algorithm (iterate over a rectangular bounding box).

OUTPUT:

The list of integral points in the polyhedron. If the polyhedron is not compact, a ValueError is raised.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((-1,-1),(1,0),(1,1),(0,1)).integral_points()
((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))

sage: simplex = LatticePolytope_PPL((1,2,3), (2,3,7), (-2,-3,-11))
sage: simplex.integral_points()
((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))

The polyhedron need not be full-dimensional:

sage: simplex = LatticePolytope_PPL((1,2,3,5), (2,3,7,5), (-2,-3,-11,5))
sage: simplex.integral_points()
((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5))

sage: point = LatticePolytope_PPL((2,3,7))
sage: point.integral_points()
((2, 3, 7),)

sage: empty = LatticePolytope_PPL()
sage: empty.integral_points()
()

Here is a simplex where the naive algorithm of running over all points in a rectangular bounding box no longer works fast enough:

sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
sage: simplex = LatticePolytope_PPL(v); simplex
A 4-dimensional lattice polytope in ZZ^4 with 5 vertices
sage: len(simplex.integral_points())
49

Finally, the 3-d reflexive polytope number 4078:

sage: v = [(1,0,0), (0,1,0), (0,0,1), (0,0,-1), (0,-2,1),
....:      (-1,2,-1), (-1,2,-2), (-1,1,-2), (-1,-1,2), (-1,-3,2)]
sage: P = LatticePolytope_PPL(*v)
sage: pts1 = P.integral_points()                     # Sage's own code
sage: pts2 = LatticePolytope(v).points()                            # optional - palp
sage: for p in pts1: p.set_immutable()
sage: set(pts1) == set(pts2)                                        # optional - palp
True

sage: len(Polyhedron(v).integral_points())  # takes about 1 ms
23
sage: len(LatticePolytope(v).points())  # takes about 13 ms         # optional - palp
23
sage: len(LatticePolytope_PPL(*v).integral_points())  # takes about 0.5 ms
23

integral_points_not_interior_to_facets()

Return the integral points not interior to facets

OUTPUT:

A tuple whose entries are the coordinate vectors of integral points not interior to facets (codimension one faces) of the lattice polytope.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
sage: square.n_integral_points()
9
sage: square.integral_points_not_interior_to_facets()
((-1, -1), (-1, 1), (0, 0), (1, -1), (1, 1))

is_bounded()

Return whether the lattice polytope is compact.

OUTPUT:

Always True, since polytopes are by definition compact.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).is_bounded()
True

is_full_dimensional()

Return whether the lattice polytope is full dimensional.

OUTPUT:

Boolean. Whether the affine_dimension() equals the ambient space dimension.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: p = LatticePolytope_PPL((0,0),(0,1))
sage: p.is_full_dimensional()
False
sage: q = LatticePolytope_PPL((0,0),(0,1),(1,0))
sage: q.is_full_dimensional()
True

is_simplex()

Return whether the polyhedron is a simplex.

OUTPUT:

Boolean, whether the polyhedron is a simplex (possibly of strictly smaller dimension than the ambient space).

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).is_simplex()
True

lattice_automorphism_group(points=None, point_labels=None)

The integral subgroup of the restricted automorphism group.

INPUT:

• points – A tuple of coordinate vectors or None (default). If specified, the points must form complete orbits under the lattice automorphism group. If None all vertices are used.

• point_labels – A tuple of labels for the points or None (default). These will be used as labels for the do permutation group. If None the points will be used themselves.

OUTPUT:

The integral subgroup of the restricted automorphism group acting on the given points, or all vertices if not specified.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3))
sage: Z3square.lattice_automorphism_group()                                     # optional - sage.groups  # optional - sage.graphs
Permutation Group with generators [(), ((1,2),(2,1)),
((0,0),(3,3)), ((0,0),(3,3))((1,2),(2,1))]

sage: G1 = Z3square.lattice_automorphism_group(point_labels=(1,2,3,4));  G1     # optional - sage.groups  # optional - sage.graphs
Permutation Group with generators [(), (2,3), (1,4), (1,4)(2,3)]
sage: G1.cardinality()                                                          # optional - sage.groups  # optional - sage.graphs
4

sage: G2 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4))      # optional - sage.groups  # optional - sage.graphs
sage: G2 == PermutationGroup([[(2,3)], [(1,2),(3,4)], [(1,4)]])                 # optional - sage.groups  # optional - sage.graphs
True
sage: G2.cardinality()                                                          # optional - sage.groups  # optional - sage.graphs
8

sage: points = Z3square.integral_points();  points
((0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3))
sage: Z3square.lattice_automorphism_group(points, point_labels=(1,2,3,4,5,6))   # optional - sage.groups  # optional - sage.graphs
Permutation Group with generators [(), (3,4), (1,6)(2,5), (1,6)(2,5)(3,4)]

Point labels also work for lattice polytopes that are not full-dimensional, see trac ticket #16669:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: lp = LatticePolytope_PPL((1,0,0),(0,1,0),(-1,-1,0))
sage: lp.lattice_automorphism_group(point_labels=(0,1,2))                       # optional - sage.groups  # optional - sage.graphs
Permutation Group with generators [(), (1,2), (0,1), (0,1,2), (0,2,1), (0,2)]

n_integral_points()

Return the number of integral points.

OUTPUT:

Integer. The number of integral points contained in the lattice polytope.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0),(1,0),(0,1)).n_integral_points()
3

n_vertices()

Return the number of vertices.

OUTPUT:

An integer, the number of vertices.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).n_vertices()
3

pointsets_mod_automorphism(pointsets)

Return pointsets modulo the automorphisms of self.

INPUT:

• polytopes a tuple/list/iterable of subsets of the integral points of self.

OUTPUT:

Representatives of the point sets modulo the lattice_automorphism_group() of self.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: square = LatticePolytope_PPL((-1,-1),(-1,1),(1,-1),(1,1))
sage: fibers = [ f.vertices() for f in square.fibration_generator(1) ]
sage: square.pointsets_mod_automorphism(fibers)                                                 # optional - sage.groups  # optional - sage.graphs
(frozenset({(-1, -1), (1, 1)}), frozenset({(-1, 0), (1, 0)}))

sage: cell24 = LatticePolytope_PPL(
....: (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,-1,-1,1),(0,0,-1,1),
....: (0,-1,0,1),(-1,0,0,1),(1,0,0,-1),(0,1,0,-1),(0,0,1,-1),(-1,1,1,-1),
....: (1,-1,-1,0),(0,0,-1,0),(0,-1,0,0),(-1,0,0,0),(1,-1,0,0),(1,0,-1,0),
....: (0,1,1,-1),(-1,1,1,0),(-1,1,0,0),(-1,0,1,0),(0,-1,-1,1),(0,0,0,-1))
sage: fibers = [f.vertices() for f in cell24.fibration_generator(2)]
sage: cell24.pointsets_mod_automorphism(fibers)   # long time                                   # optional - sage.groups  # optional - sage.graphs
(frozenset({(-1, 0, 0, 0),
            (-1, 0, 0, 1),
            (0, 0, 0, -1),
            (0, 0, 0, 1),
            (1, 0, 0, -1),
            (1, 0, 0, 0)}),
 frozenset({(-1, 0, 0, 0), (-1, 1, 1, 0), (1, -1, -1, 0), (1, 0, 0, 0)}))

restricted_automorphism_group(vertex_labels=None)

Return the restricted automorphism group.

First, let the linear automorphism group be the subgroup of the Euclidean group \(E(d) = GL(d,\RR) \ltimes \RR^d\) preserving the \(d\)-dimensional polyhedron. The Euclidean group acts in the usual way \(\vec{x}\mapsto A\vec{x}+b\) on the ambient space. The restricted automorphism group is the subgroup of the linear automorphism group generated by permutations of vertices. If the polytope is full-dimensional, it is equal to the full (unrestricted) automorphism group.

INPUT:

• vertex_labels – a tuple or None (default). The labels of the vertices that will be used in the output permutation group. By default, the vertices are used themselves.

OUTPUT:

A PermutationGroup acting on the vertices (or the vertex_labels, if specified).

REFERENCES:

[BSS2009]

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3))
sage: G1234 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4))                   # optional - sage.groups  # optional - sage.graphs
sage: G1234 == PermutationGroup([[(2,3)],[(1,2),(3,4)]])                                        # optional - sage.groups  # optional - sage.graphs
True
sage: G = Z3square.restricted_automorphism_group()                                              # optional - sage.groups  # optional - sage.graphs
sage: G == PermutationGroup([[((1,2),(2,1))],[((0,0),(1,2)),((2,1),(3,3))],[((0,0),(3,3))]])    # optional - sage.groups  # optional - sage.graphs
True
sage: set(G.domain()) == set(Z3square.vertices())                                               # optional - sage.groups  # optional - sage.graphs
True
sage: set(map(tuple,G.orbit(Z3square.vertices()[0]))) == set([(0, 0), (1, 2), (3, 3), (2, 1)])  # optional - sage.groups  # optional - sage.graphs
True
sage: cell24 = LatticePolytope_PPL(
....: (1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,-1,-1,1),(0,0,-1,1),
....: (0,-1,0,1),(-1,0,0,1),(1,0,0,-1),(0,1,0,-1),(0,0,1,-1),(-1,1,1,-1),
....: (1,-1,-1,0),(0,0,-1,0),(0,-1,0,0),(-1,0,0,0),(1,-1,0,0),(1,0,-1,0),
....: (0,1,1,-1),(-1,1,1,0),(-1,1,0,0),(-1,0,1,0),(0,-1,-1,1),(0,0,0,-1))
sage: cell24.restricted_automorphism_group().cardinality()                                      # optional - sage.groups  # optional - sage.graphs
1152

sub_polytope_generator()

Generate the maximal lattice sub-polytopes.

OUTPUT:

A generator yielding the maximal (with respect to inclusion) lattice sub polytopes. That is, each can be gotten as the convex hull of the integral points of self with one vertex removed.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: P = LatticePolytope_PPL((1,0,0), (0,1,0), (0,0,1), (-1,-1,-1))
sage: for p in P.sub_polytope_generator():
....:     print(p.vertices())
((0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0))
((-1, -1, -1), (0, 0, 0), (0, 1, 0), (1, 0, 0))
((-1, -1, -1), (0, 0, 0), (0, 0, 1), (1, 0, 0))
((-1, -1, -1), (0, 0, 0), (0, 0, 1), (0, 1, 0))

vertices()

Return the vertices as a tuple of \(\ZZ\)-vectors.

OUTPUT:

A tuple of \(\ZZ\)-vectors. Each entry is the coordinate vector of an integral points of the lattice polytope.

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: p = LatticePolytope_PPL((-9,-6,-1,-1),(0,0,0,1),(0,0,1,0),(0,1,0,0),(1,0,0,0))
sage: p.vertices()
((-9, -6, -1, -1), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0))
sage: p.minimized_generators()
Generator_System {point(-9/1, -6/1, -1/1, -1/1), point(0/1, 0/1, 0/1, 1/1),
point(0/1, 0/1, 1/1, 0/1), point(0/1, 1/1, 0/1, 0/1), point(1/1, 0/1, 0/1, 0/1)}

vertices_saturating(constraint)

Return the vertices saturating the constraint

INPUT:

• constraint – a constraint (inequality or equation) of the polytope.

OUTPUT:

The tuple of vertices saturating the constraint. The vertices are returned as \(\ZZ\)-vectors, as in vertices().

EXAMPLES:

sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
sage: p = LatticePolytope_PPL((0,0),(0,1),(1,0))
sage: ieq = next(iter(p.constraints()));  ieq
x0>=0
sage: p.vertices_saturating(ieq)
((0, 0), (0, 1))

sage.geometry.polyhedron.ppl_lattice_polytope.line(cls, expression)

Generator.line(type cls, expression)

Construct a line.

INPUT:

• expression – a Linear_Expression or something convertible to it (Variable or integer).

OUTPUT:

A new Generator representing the line.

Raises a ValueError` if the homogeneous part of ``expression represents the origin of the vector space.

Examples:

>>> from ppl import Generator, Variable
>>> y = Variable(1)
>>> Generator.line(2*y)
line(0, 1)
>>> Generator.line(y)
line(0, 1)
>>> Generator.line(1)
Traceback (most recent call last):
...
ValueError: PPL::line(e):
e == 0, but the origin cannot be a line.

sage.geometry.polyhedron.ppl_lattice_polytope.point(cls, expression=0, divisor=1)

Generator.point(type cls, expression=0, divisor=1)

Construct a point.

INPUT:

• expression – a Linear_Expression or something convertible to it (Variable or integer).

• divisor – an integer.

OUTPUT:

A new Generator representing the point.

Raises a ValueError` if ``divisor==0.

Examples:

>>> from ppl import Generator, Variable
>>> y = Variable(1)
>>> Generator.point(2*y+7, 3)
point(0/3, 2/3)
>>> Generator.point(y+7, 3)
point(0/3, 1/3)
>>> Generator.point(7, 3)
point()
>>> Generator.point(0, 0)
Traceback (most recent call last):
...
ValueError: PPL::point(e, d):
d == 0.