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))
>>> from sage.all import *
>>> vertices = [(Integer(1), Integer(0), Integer(0), Integer(0)), (Integer(0), Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(0), Integer(0), Integer(1)), (-Integer(9), -Integer(6), -Integer(1), -Integer(1))]
>>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL
>>> P = LatticePolytope_PPL(vertices); P
A 4-dimensional lattice polytope in ZZ^4 with 5 vertices
>>> 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))
>>> 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))
vertices = [(1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (-9, -6, -1, -1)] from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL P = LatticePolytope_PPL(vertices); P P.integral_points() P.integral_points_not_interior_to_facets()
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))
>>> from sage.all import *
>>> F = next(P.fibration_generator(Integer(2)))
>>> F.vertices()
((1, 0, 0, 0), (0, 1, 0, 0), (-3, -2, 0, 0))
F = next(P.fibration_generator(2)) F.vertices()
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) # needs sage.groups
(frozenset({(-1, -1), (1, 1)}), frozenset({(-1, 0), (1, 0)}))
>>> from sage.all import *
>>> square = LatticePolytope_PPL((-Integer(1),-Integer(1)), (-Integer(1),Integer(1)), (Integer(1),-Integer(1)), (Integer(1),Integer(1)))
>>> fibers = [ f.vertices() for f in square.fibration_generator(Integer(1)) ]; fibers
[((1, 0), (-1, 0)), ((0, 1), (0, -1)), ((-1, -1), (1, 1)), ((-1, 1), (1, -1))]
>>> square.pointsets_mod_automorphism(fibers) # needs sage.groups
(frozenset({(-1, -1), (1, 1)}), frozenset({(-1, 0), (1, 0)}))
square = LatticePolytope_PPL((-1,-1), (-1,1), (1,-1), (1,1)) fibers = [ f.vertices() for f in square.fibration_generator(1) ]; fibers square.pointsets_mod_automorphism(fibers) # needs sage.groups
AUTHORS:
Volker Braun: initial version, 2012
- sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL(*args)[source]¶
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 # needs pplpy sage: p = point(Linear_Expression([2,3],0)); p # needs pplpy point(2/1, 3/1) sage: LatticePolytope_PPL(p) # needs pplpy A 0-dimensional lattice polytope in ZZ^2 with 1 vertex sage: P = C_Polyhedron(Generator_System(p)); P # needs pplpy A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point sage: LatticePolytope_PPL(P) # needs pplpy A 0-dimensional lattice polytope in ZZ^2 with 1 vertex
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))) A 2-dimensional lattice polytope in ZZ^2 with 3 vertices >>> from ppl import point, Generator_System, C_Polyhedron, Linear_Expression # needs pplpy >>> p = point(Linear_Expression([Integer(2),Integer(3)],Integer(0))); p # needs pplpy point(2/1, 3/1) >>> LatticePolytope_PPL(p) # needs pplpy A 0-dimensional lattice polytope in ZZ^2 with 1 vertex >>> P = C_Polyhedron(Generator_System(p)); P # needs pplpy A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point >>> LatticePolytope_PPL(P) # needs pplpy A 0-dimensional lattice polytope in ZZ^2 with 1 vertex
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1,0), (0,1)) from ppl import point, Generator_System, C_Polyhedron, Linear_Expression # needs pplpy p = point(Linear_Expression([2,3],0)); p # needs pplpy LatticePolytope_PPL(p) # needs pplpy P = C_Polyhedron(Generator_System(p)); P # needs pplpy LatticePolytope_PPL(P) # needs pplpy
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)) # needs pplpy 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 # needs pplpy sage: p = point(Linear_Expression([2,3],0), 5); p # needs pplpy point(2/5, 3/5) sage: LatticePolytope_PPL(p) # needs pplpy Traceback (most recent call last): ... TypeError: generator is not a lattice polytope generator sage: P = C_Polyhedron(Generator_System(p)); P # needs pplpy A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point sage: LatticePolytope_PPL(P) # needs pplpy Traceback (most recent call last): ... TypeError: polyhedron has non-integral generators
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1)/Integer(2),Integer(1))) # needs pplpy Traceback (most recent call last): ... TypeError: unable to convert rational 1/2 to an integer >>> from ppl import point, Generator_System, C_Polyhedron, Linear_Expression # needs pplpy >>> p = point(Linear_Expression([Integer(2),Integer(3)],Integer(0)), Integer(5)); p # needs pplpy point(2/5, 3/5) >>> LatticePolytope_PPL(p) # needs pplpy Traceback (most recent call last): ... TypeError: generator is not a lattice polytope generator >>> P = C_Polyhedron(Generator_System(p)); P # needs pplpy A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point >>> LatticePolytope_PPL(P) # needs pplpy Traceback (most recent call last): ... TypeError: polyhedron has non-integral generators
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1/2,1)) # needs pplpy from ppl import point, Generator_System, C_Polyhedron, Linear_Expression # needs pplpy p = point(Linear_Expression([2,3],0), 5); p # needs pplpy LatticePolytope_PPL(p) # needs pplpy P = C_Polyhedron(Generator_System(p)); P # needs pplpy LatticePolytope_PPL(P) # needs pplpy
- class sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class[source]¶
Bases:
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))) A 2-dimensional lattice polytope in ZZ^2 with 3 vertices
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1,0), (0,1))
- affine_lattice_polytope()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> poly_4d = LatticePolytope_PPL((-Integer(9),-Integer(6),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))); poly_4d A 2-dimensional lattice polytope in ZZ^4 with 3 vertices >>> poly_4d.space_dimension() 4 >>> poly_2d = poly_4d.affine_lattice_polytope(); poly_2d A 2-dimensional lattice polytope in ZZ^2 with 3 vertices >>> poly_2d.space_dimension() 2
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL poly_4d = LatticePolytope_PPL((-9,-6,0,0), (0,1,0,0), (1,0,0,0)); poly_4d poly_4d.space_dimension() poly_2d = poly_4d.affine_lattice_polytope(); poly_2d poly_2d.space_dimension()
- affine_space()[source]¶
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]
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> point = LatticePolytope_PPL((Integer(1),Integer(2),Integer(3))) >>> point.affine_space() Free module of degree 3 and rank 0 over Integer Ring Echelon basis matrix: [] >>> line = LatticePolytope_PPL((Integer(1),Integer(1),Integer(1)), (Integer(1),Integer(2),Integer(3))) >>> line.affine_space() Free module of degree 3 and rank 1 over Integer Ring Echelon basis matrix: [0 1 2]
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL point = LatticePolytope_PPL((1,2,3)) point.affine_space() line = LatticePolytope_PPL((1,1,1), (1,2,3)) line.affine_space()
- ambient_space()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> point = LatticePolytope_PPL((Integer(1),Integer(2),Integer(3))) >>> point.ambient_space() Ambient free module of rank 3 over the principal ideal domain Integer Ring
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL point = LatticePolytope_PPL((1,2,3)) point.ambient_space()
- base_projection(fiber)[source]¶
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)
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> poly = LatticePolytope_PPL((-Integer(9),-Integer(6),-Integer(1),-Integer(1)), ... (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))) >>> fiber = next(poly.fibration_generator(Integer(2))) >>> poly.base_projection(fiber) Finitely generated module V/W over Integer Ring with invariants (0, 0)
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL poly = LatticePolytope_PPL((-9,-6,-1,-1), (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)) fiber = next(poly.fibration_generator(2)) poly.base_projection(fiber)
- base_projection_matrix(fiber)[source]¶
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]
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> poly = LatticePolytope_PPL((-Integer(9),-Integer(6),-Integer(1),-Integer(1)), ... (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))) >>> fiber = next(poly.fibration_generator(Integer(2))) >>> poly.base_projection_matrix(fiber) [ 0 0 -1 0] [ 0 0 0 -1]
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL poly = LatticePolytope_PPL((-9,-6,-1,-1), (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)) fiber = next(poly.fibration_generator(2)) poly.base_projection_matrix(fiber)
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)]
>>> from sage.all import * >>> proj = poly.base_projection(fiber) >>> proj_matrix = poly.base_projection_matrix(fiber) >>> [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)] >>> [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)]
proj = poly.base_projection(fiber) proj_matrix = poly.base_projection_matrix(fiber) [proj(p) for p in poly.integral_points()] [proj_matrix*p for p in poly.integral_points()]
- base_rays(fiber, points)[source]¶
Return the primitive lattice vectors that generate the direction given by the base projection of points.
INPUT:
fiber
– a sub-lattice polytope defining thebase_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),)
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> poly = LatticePolytope_PPL((-Integer(9),-Integer(6),-Integer(1),-Integer(1)), ... (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))) >>> fiber = next(poly.fibration_generator(Integer(2))) >>> poly.base_rays(fiber, poly.integral_points_not_interior_to_facets()) ((-1, -1), (0, 1), (1, 0)) >>> p = LatticePolytope_PPL((Integer(1),Integer(0)), (Integer(1),Integer(2)), (-Integer(1),Integer(0))) >>> f = LatticePolytope_PPL((Integer(1),Integer(0)), (-Integer(1),Integer(0))) >>> p.base_rays(f, p.integral_points()) ((1),)
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL poly = LatticePolytope_PPL((-9,-6,-1,-1), (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)) fiber = next(poly.fibration_generator(2)) poly.base_rays(fiber, poly.integral_points_not_interior_to_facets()) p = LatticePolytope_PPL((1,0), (1,2), (-1,0)) f = LatticePolytope_PPL((1,0), (-1,0)) p.base_rays(f, p.integral_points())
- bounding_box()[source]¶
Return the coordinates of a rectangular box containing the non-empty polytope.
OUTPUT:
A pair of tuples
(box_min, box_max)
wherebox_min
are the coordinates of a point bounding the coordinates of the polytope from below andbox_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))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))).bounding_box() ((0, 0), (1, 1))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1,0), (0,1)).bounding_box()
- contains(point_coordinates)[source]¶
Test whether point is contained in the polytope.
INPUT:
point_coordinates
– 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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> line = LatticePolytope_PPL((Integer(1),Integer(2),Integer(3)), (-Integer(1),-Integer(2),-Integer(3))) >>> line.contains([Integer(0),Integer(0),Integer(0)]) True >>> line.contains([Integer(1),Integer(0),Integer(0)]) False
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL line = LatticePolytope_PPL((1,2,3), (-1,-2,-3)) line.contains([0,0,0]) line.contains([1,0,0])
- contains_origin()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(1),Integer(2),Integer(3)), (-Integer(1),-Integer(2),-Integer(3))).contains_origin() True >>> LatticePolytope_PPL((Integer(1),Integer(2),Integer(5)), (-Integer(1),-Integer(2),-Integer(3))).contains_origin() False
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((1,2,3), (-1,-2,-3)).contains_origin() LatticePolytope_PPL((1,2,5), (-1,-2,-3)).contains_origin()
- embed_in_reflexive_polytope(output='hom')[source]¶
Find an embedding as a sub-polytope of a maximal reflexive polytope.
INPUT:
hom
– string. One of'hom'
(default),'polytope'
, orpoints
. 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 ontoself
is returned.If
output='polytope'
, a reflexive polytope that containsself
(up to a lattice linear transformation) is returned. That is, the domain of theoutput='hom'
map is returned. If the affine span ofself
is less or equal 2-dimensional, the output is one of the following three possibilities:polar_P2_polytope()
,polar_P1xP1_polytope()
, orpolar_P2_112_polytope()
.If
output='points'
, a dictionary containing the integral points ofself
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> polygon = LatticePolytope_PPL((Integer(0),Integer(0),Integer(2),Integer(1)), (Integer(0),Integer(1),Integer(2),Integer(0)), (Integer(2),Integer(3),Integer(0),Integer(0)), (Integer(2),Integer(0),Integer(0),Integer(3))) >>> 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) >>> polygon.embed_in_reflexive_polytope('polytope') A 2-dimensional lattice polytope in ZZ^2 with 3 vertices >>> 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)} >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(4),Integer(0)), (Integer(0),Integer(4))).embed_in_reflexive_polytope() Traceback (most recent call last): ... LatticePolytopeNoEmbeddingError: not a sub-polytope of a reflexive polygon
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL polygon = LatticePolytope_PPL((0,0,2,1), (0,1,2,0), (2,3,0,0), (2,0,0,3)) polygon.embed_in_reflexive_polytope() polygon.embed_in_reflexive_polytope('polytope') polygon.embed_in_reflexive_polytope('points') LatticePolytope_PPL((0,0), (4,0), (0,4)).embed_in_reflexive_polytope()
- fibration_generator(dim)[source]¶
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]
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> p = LatticePolytope_PPL((-Integer(9),-Integer(6),-Integer(1),-Integer(1)), ... (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))) >>> list(p.fibration_generator(Integer(2))) [A 2-dimensional lattice polytope in ZZ^4 with 3 vertices]
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL p = LatticePolytope_PPL((-9,-6,-1,-1), (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)) list(p.fibration_generator(2))
- has_IP_property()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((-Integer(1),-Integer(1)), (Integer(0),Integer(1)), (Integer(1),Integer(0))).has_IP_property() True >>> LatticePolytope_PPL((-Integer(1),-Integer(1)), (Integer(1),Integer(1))).has_IP_property() False
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((-1,-1), (0,1), (1,0)).has_IP_property() LatticePolytope_PPL((-1,-1), (1,1)).has_IP_property()
- integral_points()[source]¶
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))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((-Integer(1),-Integer(1)), (Integer(1),Integer(0)), (Integer(1),Integer(1)), (Integer(0),Integer(1))).integral_points() ((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1)) >>> simplex = LatticePolytope_PPL((Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(3),Integer(7)), (-Integer(2),-Integer(3),-Integer(11))) >>> simplex.integral_points() ((-2, -3, -11), (0, 0, -2), (1, 2, 3), (2, 3, 7))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((-1,-1), (1,0), (1,1), (0,1)).integral_points() simplex = LatticePolytope_PPL((1,2,3), (2,3,7), (-2,-3,-11)) simplex.integral_points()
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() ()
>>> from sage.all import * >>> simplex = LatticePolytope_PPL((Integer(1),Integer(2),Integer(3),Integer(5)), (Integer(2),Integer(3),Integer(7),Integer(5)), (-Integer(2),-Integer(3),-Integer(11),Integer(5))) >>> simplex.integral_points() ((-2, -3, -11, 5), (0, 0, -2, 5), (1, 2, 3, 5), (2, 3, 7, 5)) >>> point = LatticePolytope_PPL((Integer(2),Integer(3),Integer(7))) >>> point.integral_points() ((2, 3, 7),) >>> empty = LatticePolytope_PPL() >>> empty.integral_points() ()
simplex = LatticePolytope_PPL((1,2,3,5), (2,3,7,5), (-2,-3,-11,5)) simplex.integral_points() point = LatticePolytope_PPL((2,3,7)) point.integral_points() empty = LatticePolytope_PPL() 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
>>> from sage.all import * >>> v = [(Integer(1),Integer(0),Integer(7),-Integer(1)), (-Integer(2),-Integer(2),Integer(4),-Integer(3)), (-Integer(1),-Integer(1),-Integer(1),Integer(4)), (Integer(2),Integer(9),Integer(0),-Integer(5)), (-Integer(2),-Integer(1),Integer(5),Integer(1))] >>> simplex = LatticePolytope_PPL(v); simplex A 4-dimensional lattice polytope in ZZ^4 with 5 vertices >>> len(simplex.integral_points()) 49
v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)] simplex = LatticePolytope_PPL(v); simplex len(simplex.integral_points())
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() # needs palp sage: for p in pts1: p.set_immutable() sage: set(pts1) == set(pts2) # needs palp True sage: len(Polyhedron(v).integral_points()) # takes about 1 ms 23 sage: len(LatticePolytope(v).points()) # takes about 13 ms # needs palp 23 sage: len(LatticePolytope_PPL(*v).integral_points()) # takes about 0.5 ms 23
>>> from sage.all import * >>> v = [(Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),-Integer(1)), (Integer(0),-Integer(2),Integer(1)), ... (-Integer(1),Integer(2),-Integer(1)), (-Integer(1),Integer(2),-Integer(2)), (-Integer(1),Integer(1),-Integer(2)), (-Integer(1),-Integer(1),Integer(2)), (-Integer(1),-Integer(3),Integer(2))] >>> P = LatticePolytope_PPL(*v) >>> pts1 = P.integral_points() # Sage's own code >>> pts2 = LatticePolytope(v).points() # needs palp >>> for p in pts1: p.set_immutable() >>> set(pts1) == set(pts2) # needs palp True >>> len(Polyhedron(v).integral_points()) # takes about 1 ms 23 >>> len(LatticePolytope(v).points()) # takes about 13 ms # needs palp 23 >>> len(LatticePolytope_PPL(*v).integral_points()) # takes about 0.5 ms 23
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)] P = LatticePolytope_PPL(*v) pts1 = P.integral_points() # Sage's own code pts2 = LatticePolytope(v).points() # needs palp for p in pts1: p.set_immutable() set(pts1) == set(pts2) # needs palp len(Polyhedron(v).integral_points()) # takes about 1 ms len(LatticePolytope(v).points()) # takes about 13 ms # needs palp len(LatticePolytope_PPL(*v).integral_points()) # takes about 0.5 ms
- integral_points_not_interior_to_facets()[source]¶
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))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> square = LatticePolytope_PPL((-Integer(1),-Integer(1)), (-Integer(1),Integer(1)), (Integer(1),-Integer(1)), (Integer(1),Integer(1))) >>> square.n_integral_points() 9 >>> square.integral_points_not_interior_to_facets() ((-1, -1), (-1, 1), (0, 0), (1, -1), (1, 1))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL square = LatticePolytope_PPL((-1,-1), (-1,1), (1,-1), (1,1)) square.n_integral_points() square.integral_points_not_interior_to_facets()
- is_bounded()[source]¶
Return whether the lattice polytope is compact.
OUTPUT: always
True
, since polytopes are by definition compactEXAMPLES:
sage: from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL sage: LatticePolytope_PPL((0,0), (1,0), (0,1)).is_bounded() True
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))).is_bounded() True
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1,0), (0,1)).is_bounded()
- is_full_dimensional()[source]¶
Return whether the lattice polytope is full dimensional.
OUTPUT: boolean; whether the
affine_dimension()
equals the ambient space dimensionEXAMPLES:
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> p = LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(0),Integer(1))) >>> p.is_full_dimensional() False >>> q = LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(1),Integer(0))) >>> q.is_full_dimensional() True
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL p = LatticePolytope_PPL((0,0), (0,1)) p.is_full_dimensional() q = LatticePolytope_PPL((0,0), (0,1), (1,0)) q.is_full_dimensional()
- is_simplex()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))).is_simplex() True
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).is_simplex()
- lattice_automorphism_group(points=None, point_labels=None)[source]¶
The integral subgroup of the restricted automorphism group.
INPUT:
points
– tuple of coordinate vectors orNone
(default). If specified, the points must form complete orbits under the lattice automorphism group. IfNone
all vertices are used.point_labels
– tuple of labels for thepoints
orNone
(default). These will be used as labels for the do permutation group. IfNone
, thepoints
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() # needs sage.graphs sage.groups 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)) # needs sage.graphs sage.groups sage: G1 # needs sage.graphs sage.groups Permutation Group with generators [(), (2,3), (1,4), (1,4)(2,3)] sage: G1.cardinality() # needs sage.graphs sage.groups 4 sage: G2 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4)) # needs sage.graphs sage.groups sage: G2 == PermutationGroup([[(2,3)], [(1,2),(3,4)], [(1,4)]]) # needs sage.graphs sage.groups True sage: G2.cardinality() # needs sage.graphs sage.groups 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, # needs sage.graphs sage.groups ....: point_labels=(1,2,3,4,5,6)) Permutation Group with generators [(), (3,4), (1,6)(2,5), (1,6)(2,5)(3,4)]
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> Z3square = LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(2)), (Integer(2),Integer(1)), (Integer(3),Integer(3))) >>> Z3square.lattice_automorphism_group() # needs sage.graphs sage.groups Permutation Group with generators [(), ((1,2),(2,1)), ((0,0),(3,3)), ((0,0),(3,3))((1,2),(2,1))] >>> G1 = Z3square.lattice_automorphism_group(point_labels=(Integer(1),Integer(2),Integer(3),Integer(4))) # needs sage.graphs sage.groups >>> G1 # needs sage.graphs sage.groups Permutation Group with generators [(), (2,3), (1,4), (1,4)(2,3)] >>> G1.cardinality() # needs sage.graphs sage.groups 4 >>> G2 = Z3square.restricted_automorphism_group(vertex_labels=(Integer(1),Integer(2),Integer(3),Integer(4))) # needs sage.graphs sage.groups >>> G2 == PermutationGroup([[(Integer(2),Integer(3))], [(Integer(1),Integer(2)),(Integer(3),Integer(4))], [(Integer(1),Integer(4))]]) # needs sage.graphs sage.groups True >>> G2.cardinality() # needs sage.graphs sage.groups 8 >>> points = Z3square.integral_points(); points ((0, 0), (1, 1), (1, 2), (2, 1), (2, 2), (3, 3)) >>> Z3square.lattice_automorphism_group(points, # needs sage.graphs sage.groups ... point_labels=(Integer(1),Integer(2),Integer(3),Integer(4),Integer(5),Integer(6))) Permutation Group with generators [(), (3,4), (1,6)(2,5), (1,6)(2,5)(3,4)]
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3)) Z3square.lattice_automorphism_group() # needs sage.graphs sage.groups G1 = Z3square.lattice_automorphism_group(point_labels=(1,2,3,4)) # needs sage.graphs sage.groups G1 # needs sage.graphs sage.groups G1.cardinality() # needs sage.graphs sage.groups G2 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4)) # needs sage.graphs sage.groups G2 == PermutationGroup([[(2,3)], [(1,2),(3,4)], [(1,4)]]) # needs sage.graphs sage.groups G2.cardinality() # needs sage.graphs sage.groups points = Z3square.integral_points(); points Z3square.lattice_automorphism_group(points, # needs sage.graphs sage.groups point_labels=(1,2,3,4,5,6))
Point labels also work for lattice polytopes that are not full-dimensional, see Issue #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)) # needs sage.graphs sage.groups Permutation Group with generators [(), (1,2), (0,1), (0,1,2), (0,2,1), (0,2)]
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> lp = LatticePolytope_PPL((Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (-Integer(1),-Integer(1),Integer(0))) >>> lp.lattice_automorphism_group(point_labels=(Integer(0),Integer(1),Integer(2))) # needs sage.graphs sage.groups Permutation Group with generators [(), (1,2), (0,1), (0,1,2), (0,2,1), (0,2)]
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL lp = LatticePolytope_PPL((1,0,0), (0,1,0), (-1,-1,0)) lp.lattice_automorphism_group(point_labels=(0,1,2)) # needs sage.graphs sage.groups
- n_integral_points()[source]¶
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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(0)), (Integer(0),Integer(1))).n_integral_points() 3
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0), (1,0), (0,1)).n_integral_points()
- n_vertices()[source]¶
Return the number of vertices.
OUTPUT: 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
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> LatticePolytope_PPL((Integer(0),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0))).n_vertices() 3
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL LatticePolytope_PPL((0,0,0), (1,0,0), (0,1,0)).n_vertices()
- pointsets_mod_automorphism(pointsets)[source]¶
Return
pointsets
modulo the automorphisms ofself
.INPUT:
polytopes
– tuple/list/iterable of subsets of the integral points ofself
OUTPUT:
Representatives of the point sets modulo the
lattice_automorphism_group()
ofself
.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) # needs sage.graphs sage.groups (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 # needs sage.graphs sage.groups (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)}))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> square = LatticePolytope_PPL((-Integer(1),-Integer(1)), (-Integer(1),Integer(1)), (Integer(1),-Integer(1)), (Integer(1),Integer(1))) >>> fibers = [f.vertices() for f in square.fibration_generator(Integer(1))] >>> square.pointsets_mod_automorphism(fibers) # needs sage.graphs sage.groups (frozenset({(-1, -1), (1, 1)}), frozenset({(-1, 0), (1, 0)})) >>> cell24 = LatticePolytope_PPL( ... (Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(1),-Integer(1),-Integer(1),Integer(1)), (Integer(0),Integer(0),-Integer(1),Integer(1)), ... (Integer(0),-Integer(1),Integer(0),Integer(1)), (-Integer(1),Integer(0),Integer(0),Integer(1)), (Integer(1),Integer(0),Integer(0),-Integer(1)), (Integer(0),Integer(1),Integer(0),-Integer(1)), (Integer(0),Integer(0),Integer(1),-Integer(1)), (-Integer(1),Integer(1),Integer(1),-Integer(1)), ... (Integer(1),-Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(0),-Integer(1),Integer(0)), (Integer(0),-Integer(1),Integer(0),Integer(0)), (-Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(1),-Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),-Integer(1),Integer(0)), ... (Integer(0),Integer(1),Integer(1),-Integer(1)), (-Integer(1),Integer(1),Integer(1),Integer(0)), (-Integer(1),Integer(1),Integer(0),Integer(0)), (-Integer(1),Integer(0),Integer(1),Integer(0)), (Integer(0),-Integer(1),-Integer(1),Integer(1)), (Integer(0),Integer(0),Integer(0),-Integer(1))) >>> fibers = [f.vertices() for f in cell24.fibration_generator(Integer(2))] >>> cell24.pointsets_mod_automorphism(fibers) # long time # needs sage.graphs sage.groups (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)}))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL square = LatticePolytope_PPL((-1,-1), (-1,1), (1,-1), (1,1)) fibers = [f.vertices() for f in square.fibration_generator(1)] square.pointsets_mod_automorphism(fibers) # needs sage.graphs sage.groups 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)) fibers = [f.vertices() for f in cell24.fibration_generator(2)] cell24.pointsets_mod_automorphism(fibers) # long time # needs sage.graphs sage.groups
- restricted_automorphism_group(vertex_labels=None)[source]¶
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
– tuple orNone
(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 thevertex_labels
, if specified).REFERENCES:
EXAMPLES:
sage: # needs sage.graphs sage.groups 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)) sage: G1234 == PermutationGroup([[(2,3)], [(1,2),(3,4)]]) True sage: G = Z3square.restricted_automorphism_group() sage: G == PermutationGroup([[((1,2),(2,1))], [((0,0),(1,2)), ....: ((2,1),(3,3))], [((0,0),(3,3))]]) True sage: set(G.domain()) == set(Z3square.vertices()) True sage: (set(tuple(x) for x in G.orbit(Z3square.vertices()[0])) ....: == set([(0, 0), (1, 2), (3, 3), (2, 1)])) 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() 1152
>>> from sage.all import * >>> # needs sage.graphs sage.groups >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> Z3square = LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(1),Integer(2)), (Integer(2),Integer(1)), (Integer(3),Integer(3))) >>> G1234 = Z3square.restricted_automorphism_group( ... vertex_labels=(Integer(1),Integer(2),Integer(3),Integer(4))) >>> G1234 == PermutationGroup([[(Integer(2),Integer(3))], [(Integer(1),Integer(2)),(Integer(3),Integer(4))]]) True >>> G = Z3square.restricted_automorphism_group() >>> G == PermutationGroup([[((Integer(1),Integer(2)),(Integer(2),Integer(1)))], [((Integer(0),Integer(0)),(Integer(1),Integer(2))), ... ((Integer(2),Integer(1)),(Integer(3),Integer(3)))], [((Integer(0),Integer(0)),(Integer(3),Integer(3)))]]) True >>> set(G.domain()) == set(Z3square.vertices()) True >>> (set(tuple(x) for x in G.orbit(Z3square.vertices()[Integer(0)])) ... == set([(Integer(0), Integer(0)), (Integer(1), Integer(2)), (Integer(3), Integer(3)), (Integer(2), Integer(1))])) True >>> cell24 = LatticePolytope_PPL( ... (Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(1),-Integer(1),-Integer(1),Integer(1)), (Integer(0),Integer(0),-Integer(1),Integer(1)), ... (Integer(0),-Integer(1),Integer(0),Integer(1)), (-Integer(1),Integer(0),Integer(0),Integer(1)), (Integer(1),Integer(0),Integer(0),-Integer(1)), (Integer(0),Integer(1),Integer(0),-Integer(1)), (Integer(0),Integer(0),Integer(1),-Integer(1)), (-Integer(1),Integer(1),Integer(1),-Integer(1)), ... (Integer(1),-Integer(1),-Integer(1),Integer(0)), (Integer(0),Integer(0),-Integer(1),Integer(0)), (Integer(0),-Integer(1),Integer(0),Integer(0)), (-Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(1),-Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),-Integer(1),Integer(0)), ... (Integer(0),Integer(1),Integer(1),-Integer(1)), (-Integer(1),Integer(1),Integer(1),Integer(0)), (-Integer(1),Integer(1),Integer(0),Integer(0)), (-Integer(1),Integer(0),Integer(1),Integer(0)), (Integer(0),-Integer(1),-Integer(1),Integer(1)), (Integer(0),Integer(0),Integer(0),-Integer(1))) >>> cell24.restricted_automorphism_group().cardinality() 1152
# needs sage.graphs sage.groups from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL Z3square = LatticePolytope_PPL((0,0), (1,2), (2,1), (3,3)) G1234 = Z3square.restricted_automorphism_group( vertex_labels=(1,2,3,4)) G1234 == PermutationGroup([[(2,3)], [(1,2),(3,4)]]) G = Z3square.restricted_automorphism_group() G == PermutationGroup([[((1,2),(2,1))], [((0,0),(1,2)), ((2,1),(3,3))], [((0,0),(3,3))]]) set(G.domain()) == set(Z3square.vertices()) (set(tuple(x) for x in G.orbit(Z3square.vertices()[0])) == set([(0, 0), (1, 2), (3, 3), (2, 1)])) 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)) cell24.restricted_automorphism_group().cardinality()
- sub_polytope_generator()[source]¶
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))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> P = LatticePolytope_PPL((Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(0),Integer(1)), (-Integer(1),-Integer(1),-Integer(1))) >>> 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))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL P = LatticePolytope_PPL((1,0,0), (0,1,0), (0,0,1), (-1,-1,-1)) for p in P.sub_polytope_generator(): print(p.vertices())
- vertices()[source]¶
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)}
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> p = LatticePolytope_PPL((-Integer(9),-Integer(6),-Integer(1),-Integer(1)), ... (Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(0),Integer(0))) >>> p.vertices() ((-9, -6, -1, -1), (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0)) >>> 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)}
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL p = LatticePolytope_PPL((-9,-6,-1,-1), (0,0,0,1), (0,0,1,0), (0,1,0,0), (1,0,0,0)) p.vertices() p.minimized_generators()
- vertices_saturating(constraint)[source]¶
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))
>>> from sage.all import * >>> from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL >>> p = LatticePolytope_PPL((Integer(0),Integer(0)), (Integer(0),Integer(1)), (Integer(1),Integer(0))) >>> ieq = next(iter(p.constraints())); ieq x0>=0 >>> p.vertices_saturating(ieq) ((0, 0), (0, 1))
from sage.geometry.polyhedron.ppl_lattice_polytope import LatticePolytope_PPL p = LatticePolytope_PPL((0,0), (0,1), (1,0)) ieq = next(iter(p.constraints())); ieq p.vertices_saturating(ieq)