Contents Menu Expand Light mode Dark mode Auto light/dark, in light mode Auto light/dark, in dark mode Skip to content
Combinatorial and Discrete Geometry
Light Logo Dark Logo
Version 10.6 Reference Manual
  • Home - Combinatorial and Discrete Geometry
  • Hyperplane Arrangements
  • Ordered Hyperplane Arrangements
  • Library of Hyperplane Arrangements
  • Hyperplanes
  • Affine Subspaces of a Vector Space
  • Plotting of Hyperplane Arrangements
  • Library of commonly used, famous, or interesting polytopes
  • Polyhedra
  • Parents for Polyhedra
  • H(yperplane) and V(ertex) representation objects for polyhedra
  • Functions for plotting polyhedra
  • A class to keep information about faces of a polyhedron
  • Generate cdd .ext / .ine file format
  • Formal modules generated by polyhedra
  • Lattice and reflexive polytopes
  • Lattice Euclidean Group Elements
  • Access the PALP database(s) of reflexive lattice polytopes
  • Fast Lattice Polygons using PPL
  • Fast Lattice Polytopes using PPL.
  • Generating Function of Polyhedron’s Integral Points
  • Combinatorial polyhedron
  • Combinatorial face of a polyhedron
  • PolyhedronFaceLattice
  • Face iterator for polyhedra
  • List of faces
  • Conversions
  • Finite polyhedral complexes
  • Toric lattices
  • Convex rational polyhedral cones
  • Catalog of common polyhedral convex cones
  • Find maximal angles between polyhedral convex cones
  • Rational polyhedral fans
  • Morphisms between toric lattices compatible with fans
  • Point collections
  • Toric plotter
  • Groebner Fans
  • Base class for polyhedra: Initialization and access to Vrepresentation and Hrepresentation
  • Base class for polyhedra: Implementation of the ConvexSet_base API
  • Base class for polyhedra: Methods related to lattice points
  • Base class for polyhedra: Methods regarding the combinatorics of a polyhedron
  • Base class for polyhedra: Graph-theoretic methods
  • Base class for polyhedra: Methods for constructing new polyhedra
  • Base class for polyhedra: Methods for plotting and affine hull projection
  • Base class for polyhedra: Methods for triangulation and volume computation
  • Base class for polyhedra: Miscellaneous methods
  • Base class for polyhedra over \(\QQ\)
  • Base class for polyhedra over \(\ZZ\)
  • Base class for polyhedra over RDF
  • The cdd backend for polyhedral computations
  • The cdd backend for polyhedral computations, floating point version
  • The Python backend
  • The Python backend, using number fields internally
  • The Normaliz backend for polyhedral computations
  • The polymake backend for polyhedral computations
  • The PPL (Parma Polyhedra Library) backend for polyhedral computations
  • Double Description Algorithm for Cones
  • Double Description for Arbitrary Polyhedra
  • Triangulations of a point configuration
  • Base classes for triangulations
  • A triangulation
  • Abstract base classes for classes in geometry
  • Convex Sets
  • Linear Expressions
  • Newton Polygons
  • Relative Interiors of Polyhedra and Cones
  • Ribbon Graphs
  • Pseudolines
  • Voronoi diagram
  • Find isomorphisms between fans
  • Construction of finite atomic and coatomic lattices from incidences
  • Cython helper methods to compute integral points in polyhedra
  • Helper Functions For Freeness Of Hyperplane Arrangements
Back to top
View this page
Edit this page

Base class for polyhedra: Methods related to lattice points¶

class sage.geometry.polyhedron.base2.Polyhedron_base2(parent, Vrep, Hrep, Vrep_minimal=None, Hrep_minimal=None, pref_rep=None, mutable=False, **kwds)[source]¶

Bases: Polyhedron_base1

Methods related to lattice points.

See sage.geometry.polyhedron.base.Polyhedron_base.

generating_function_of_integral_points(**kwds)[source]¶

Return the multivariate generating function of the integral points of this polyhedron.

To be precise, this returns

\[\sum_{(r_0,\dots,r_{d-1}) \in \mathit{polyhedron}\cap \ZZ^d} y_0^{r_0} \dots y_{d-1}^{r_{d-1}}.\]

This calls generating_function_of_integral_points(), so have a look at the documentation and examples there.

INPUT:

The following keyword arguments are passed to generating_function_of_integral_points():

  • split – boolean (default: False) or list

    • split=False computes the generating function directly, without any splitting.

    • When split is a list of disjoint polyhedra, then for each of these polyhedra, this polyhedron is intersected with it, its generating function computed and all these generating functions are summed up.

    • split=True splits into \(d!\) disjoint polyhedra.

  • result_as_tuple – (default: None) a boolean or None

    This specifies whether the output is a (partial) factorization (result_as_tuple=False) or a sum of such (partial) factorizations (result_as_tuple=True). By default (result_as_tuple=None), this is automatically determined. If the output is a sum, it is represented as a tuple whose entries are the summands.

  • indices – (default: None) a list or tuple

    If this is None, this is automatically determined.

  • name – (default: 'y') a string

    The variable names of the Laurent polynomial ring of the output are this string followed by an integer.

  • names – list or tuple of names (strings), or a comma separated string

    name is extracted from names, therefore names has to contain exactly one variable name, and name and``names`` cannot be specified both at the same time.

  • Factorization_sort (default: False) and Factorization_simplify (default: True) – booleans

    These are passed on to sage.structure.factorization.Factorization when creating the result.

  • sort_factors – boolean (default: False)

    If set, then the factors of the output are sorted such that the numerator is first and only then all factors of the denominator. It is ensured that the sorting is always the same; use this for doctesting.

OUTPUT:

The generating function as a (partial) Factorization of the result whose factors are Laurent polynomials

The result might be a tuple of such factorizations (depending on the parameter result_as_tuple) as well.

Note

At the moment, only polyhedra with nonnegative coordinates (i.e. a polyhedron in the nonnegative orthant) are handled.

EXAMPLES:

sage: # needs sage.combinat
sage: P2 = (Polyhedron(ieqs=[(0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, -1)]),
....:       Polyhedron(ieqs=[(0, -1, 0, 1), (0, 1, 0, 0), (0, 0, 1, 0)]))
sage: P2[0].generating_function_of_integral_points(sort_factors=True)
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1
sage: P2[1].generating_function_of_integral_points(sort_factors=True)
1 * (-y1 + 1)^-1 * (-y2 + 1)^-1 * (-y0*y2 + 1)^-1
sage: (P2[0] & P2[1]).Hrepresentation()
(An equation (1, 0, -1) x + 0 == 0,
 An inequality (1, 0, 0) x + 0 >= 0,
 An inequality (0, 1, 0) x + 0 >= 0)
sage: (P2[0] & P2[1]).generating_function_of_integral_points(sort_factors=True)
1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1
>>> from sage.all import *
>>> # needs sage.combinat
>>> P2 = (Polyhedron(ieqs=[(Integer(0), Integer(0), Integer(0), Integer(1)), (Integer(0), Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(1), Integer(0), -Integer(1))]),
...       Polyhedron(ieqs=[(Integer(0), -Integer(1), Integer(0), Integer(1)), (Integer(0), Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(0), Integer(1), Integer(0))]))
>>> P2[Integer(0)].generating_function_of_integral_points(sort_factors=True)
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1
>>> P2[Integer(1)].generating_function_of_integral_points(sort_factors=True)
1 * (-y1 + 1)^-1 * (-y2 + 1)^-1 * (-y0*y2 + 1)^-1
>>> (P2[Integer(0)] & P2[Integer(1)]).Hrepresentation()
(An equation (1, 0, -1) x + 0 == 0,
 An inequality (1, 0, 0) x + 0 >= 0,
 An inequality (0, 1, 0) x + 0 >= 0)
>>> (P2[Integer(0)] & P2[Integer(1)]).generating_function_of_integral_points(sort_factors=True)
1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1

The number of integer partitions \(1 \leq r_0 \leq r_1 \leq r_2 \leq r_3 \leq r_4\):

sage: # needs sage.combinat
sage: P = Polyhedron(ieqs=[(-1, 1, 0, 0, 0, 0), (0, -1, 1, 0, 0, 0),
....:                      (0, 0, -1, 1, 0, 0), (0, 0, 0, -1, 1, 0),
....:                      (0, 0, 0, 0, -1, 1)])
sage: f = P.generating_function_of_integral_points(sort_factors=True); f
y0*y1*y2*y3*y4 * (-y4 + 1)^-1 * (-y3*y4 + 1)^-1 * (-y2*y3*y4 + 1)^-1 *
(-y1*y2*y3*y4 + 1)^-1 * (-y0*y1*y2*y3*y4 + 1)^-1
sage: f = f.value()
sage: P.<z> = PowerSeriesRing(ZZ)
sage: c = f.subs({y: z for y in f.parent().gens()}); c
z^5 + z^6 + 2*z^7 + 3*z^8 + 5*z^9 + 7*z^10 + 10*z^11 + 13*z^12 + 18*z^13 +
23*z^14 + 30*z^15 + 37*z^16 + 47*z^17 + 57*z^18 + 70*z^19 + 84*z^20 +
101*z^21 + 119*z^22 + 141*z^23 + 164*z^24 + O(z^25)
sage: ([Partitions(k, length=5).cardinality() for k in range(5,20)] ==
....:     c.truncate().coefficients(sparse=False)[5:20])
True
>>> from sage.all import *
>>> # needs sage.combinat
>>> P = Polyhedron(ieqs=[(-Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)), (Integer(0), -Integer(1), Integer(1), Integer(0), Integer(0), Integer(0)),
...                      (Integer(0), Integer(0), -Integer(1), Integer(1), Integer(0), Integer(0)), (Integer(0), Integer(0), Integer(0), -Integer(1), Integer(1), Integer(0)),
...                      (Integer(0), Integer(0), Integer(0), Integer(0), -Integer(1), Integer(1))])
>>> f = P.generating_function_of_integral_points(sort_factors=True); f
y0*y1*y2*y3*y4 * (-y4 + 1)^-1 * (-y3*y4 + 1)^-1 * (-y2*y3*y4 + 1)^-1 *
(-y1*y2*y3*y4 + 1)^-1 * (-y0*y1*y2*y3*y4 + 1)^-1
>>> f = f.value()
>>> P = PowerSeriesRing(ZZ, names=('z',)); (z,) = P._first_ngens(1)
>>> c = f.subs({y: z for y in f.parent().gens()}); c
z^5 + z^6 + 2*z^7 + 3*z^8 + 5*z^9 + 7*z^10 + 10*z^11 + 13*z^12 + 18*z^13 +
23*z^14 + 30*z^15 + 37*z^16 + 47*z^17 + 57*z^18 + 70*z^19 + 84*z^20 +
101*z^21 + 119*z^22 + 141*z^23 + 164*z^24 + O(z^25)
>>> ([Partitions(k, length=Integer(5)).cardinality() for k in range(Integer(5),Integer(20))] ==
...     c.truncate().coefficients(sparse=False)[Integer(5):Integer(20)])
True

See also

More examples can be found at generating_function_of_integral_points().

get_integral_point(index, **kwds)[source]¶

Return the index-th integral point in this polyhedron.

This is equivalent to sorted(self.integral_points())[index]. However, so long as integral_points_count() does not need to enumerate all integral points, neither does this method. Hence it can be significantly faster. If the polyhedron is not compact, a ValueError is raised.

INPUT:

  • index – integer; the index of the integral point to be found. If this is not in [0, self.integral_point_count()), an IndexError is raised.

  • **kwds – optional keyword parameters that are passed to integral_points_count()

ALGORITHM:

The function computes each of the components of the requested point in turn. To compute x_i, the \(i\)-th component, it bisects the upper and lower bounds on x_i given by the bounding box. At each bisection, it uses integral_points_count() to determine on which side of the bisecting hyperplane the requested point lies.

See also

integral_points_count().

EXAMPLES:

sage: P = Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)])
sage: P.get_integral_point(1)
(0, 0)
sage: P.get_integral_point(4)
(1, 1)
sage: sorted(P.integral_points())
[(-1, -1), (0, 0), (0, 1), (1, 0), (1, 1)]
sage: P.get_integral_point(5)
Traceback (most recent call last):
...
IndexError: ...

sage: Q = Polyhedron([(1,3), (2, 7), (9, 77)])
sage: [Q.get_integral_point(i) for i in range(Q.integral_points_count())] == sorted(Q.integral_points())
True
sage: Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib')  # optional - latte_int
(1, 3)
sage: Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib', foo=True)  # optional - latte_int
Traceback (most recent call last):
...
RuntimeError: ...

sage: R = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]])
sage: R.get_integral_point(0)
Traceback (most recent call last):
...
ValueError: ...
>>> from sage.all import *
>>> P = Polyhedron(vertices=[(-Integer(1),-Integer(1)),(Integer(1),Integer(0)),(Integer(1),Integer(1)),(Integer(0),Integer(1))])
>>> P.get_integral_point(Integer(1))
(0, 0)
>>> P.get_integral_point(Integer(4))
(1, 1)
>>> sorted(P.integral_points())
[(-1, -1), (0, 0), (0, 1), (1, 0), (1, 1)]
>>> P.get_integral_point(Integer(5))
Traceback (most recent call last):
...
IndexError: ...

>>> Q = Polyhedron([(Integer(1),Integer(3)), (Integer(2), Integer(7)), (Integer(9), Integer(77))])
>>> [Q.get_integral_point(i) for i in range(Q.integral_points_count())] == sorted(Q.integral_points())
True
>>> Q.get_integral_point(Integer(0), explicit_enumeration_threshold=Integer(0), triangulation='cddlib')  # optional - latte_int
(1, 3)
>>> Q.get_integral_point(Integer(0), explicit_enumeration_threshold=Integer(0), triangulation='cddlib', foo=True)  # optional - latte_int
Traceback (most recent call last):
...
RuntimeError: ...

>>> R = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(1)/Integer(3)]], rays=[[Integer(1), Integer(1)]])
>>> R.get_integral_point(Integer(0))
Traceback (most recent call last):
...
ValueError: ...
h_star_vector()[source]¶

Return the \(h^*\)-vector of the lattice polytope.

The \(h^*\)-vector records the coefficients of the polynomial in the numerator of the Ehrhart series of a lattice polytope.

INPUT:

  • self – a lattice polytope

OUTPUT:

A list whose entries give the \(h^*\)-vector.

Note

The backend of self should be 'normaliz'. This function depends on Normaliz (i.e. the 'pynormaliz' optional package). See the Normaliz documentation for further details.

EXAMPLES:

The \(h^*\)-vector of a unimodular simplex S (a simplex with volume = \(\frac{1}{dim(S)!}\)) is always 1. Here we test this on simplices up to dimension 3:

sage: # optional - pynormaliz
sage: s1 = polytopes.simplex(1,backend='normaliz')
sage: s2 = polytopes.simplex(2,backend='normaliz')
sage: s3 = polytopes.simplex(3,backend='normaliz')
sage: [s1.h_star_vector(), s2.h_star_vector(), s3.h_star_vector()]
[[1], [1], [1]]
>>> from sage.all import *
>>> # optional - pynormaliz
>>> s1 = polytopes.simplex(Integer(1),backend='normaliz')
>>> s2 = polytopes.simplex(Integer(2),backend='normaliz')
>>> s3 = polytopes.simplex(Integer(3),backend='normaliz')
>>> [s1.h_star_vector(), s2.h_star_vector(), s3.h_star_vector()]
[[1], [1], [1]]

For a less trivial example, we compute the \(h^*\)-vector of the \(0/1\)-cube, which has the Eulerian numbers \((3,i)\) for \(i \in [0,2]\) as an \(h^*\)-vector:

sage: cube = polytopes.cube(intervals='zero_one', backend='normaliz')   # optional - pynormaliz
sage: cube.h_star_vector()                                              # optional - pynormaliz
[1, 4, 1]
sage: from sage.combinat.combinat import eulerian_number
sage: [eulerian_number(3,i) for i in range(3)]
[1, 4, 1]
>>> from sage.all import *
>>> cube = polytopes.cube(intervals='zero_one', backend='normaliz')   # optional - pynormaliz
>>> cube.h_star_vector()                                              # optional - pynormaliz
[1, 4, 1]
>>> from sage.combinat.combinat import eulerian_number
>>> [eulerian_number(Integer(3),i) for i in range(Integer(3))]
[1, 4, 1]
integral_points(threshold=100000)[source]¶

Return the integral points in the polyhedron.

Uses either the naive algorithm (iterate over a rectangular bounding box) or triangulation + Smith form.

INPUT:

  • threshold – integer (default: 100000); use the naive algorithm as long as the bounding box is smaller than this

OUTPUT:

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

EXAMPLES:

sage: Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)]).integral_points()
((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))

sage: simplex = Polyhedron([(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 *
>>> Polyhedron(vertices=[(-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 = Polyhedron([(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))

The polyhedron need not be full-dimensional:

sage: simplex = Polyhedron([(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 = Polyhedron([(2,3,7)])
sage: point.integral_points()
((2, 3, 7),)

sage: empty = Polyhedron()
sage: empty.integral_points()
()
>>> from sage.all import *
>>> simplex = Polyhedron([(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 = Polyhedron([(Integer(2),Integer(3),Integer(7))])
>>> point.integral_points()
((2, 3, 7),)

>>> empty = Polyhedron()
>>> 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 = Polyhedron(v); simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 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 = Polyhedron(v); simplex
A 4-dimensional polyhedron in ZZ^4 defined as the convex hull of 5 vertices
>>> len(simplex.integral_points())
49

A case where rounding in the right direction goes a long way:

sage: P = 1/10*polytopes.hypercube(14, backend='field')
sage: P.integral_points()
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)
>>> from sage.all import *
>>> P = Integer(1)/Integer(10)*polytopes.hypercube(Integer(14), backend='field')
>>> P.integral_points()
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),)

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 = Polyhedron(v)
sage: pts1 = P.integral_points()                     # Sage's own code
sage: all(P.contains(p) for p in pts1)
True
sage: pts2 = LatticePolytope(v).points()                                    # needs palp
sage: for p in pts1: p.set_immutable()
sage: set(pts1) == set(pts2)                                                # needs palp
True

sage: timeit('Polyhedron(v).integral_points()')   # not tested - random
625 loops, best of 3: 1.41 ms per loop
sage: timeit('LatticePolytope(v).points()')       # not tested - random
25 loops, best of 3: 17.2 ms per loop
>>> 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 = Polyhedron(v)
>>> pts1 = P.integral_points()                     # Sage's own code
>>> all(P.contains(p) for p in pts1)
True
>>> pts2 = LatticePolytope(v).points()                                    # needs palp
>>> for p in pts1: p.set_immutable()
>>> set(pts1) == set(pts2)                                                # needs palp
True

>>> timeit('Polyhedron(v).integral_points()')   # not tested - random
625 loops, best of 3: 1.41 ms per loop
>>> timeit('LatticePolytope(v).points()')       # not tested - random
25 loops, best of 3: 17.2 ms per loop
integral_points_count(**kwds)[source]¶

Return the number of integral points in the polyhedron.

This generic version of this method simply calls integral_points().

EXAMPLES:

sage: P = polytopes.cube()
sage: P.integral_points_count()
27
>>> from sage.all import *
>>> P = polytopes.cube()
>>> P.integral_points_count()
27

We shrink the polyhedron a little bit:

sage: Q = P*(8/9)
sage: Q.integral_points_count()
1
>>> from sage.all import *
>>> Q = P*(Integer(8)/Integer(9))
>>> Q.integral_points_count()
1

Same for a polyhedron whose coordinates are not rationals. Note that the answer is an integer even though there are no guarantees for exactness:

sage: Q = P*RDF(8/9)
sage: Q.integral_points_count()
1
>>> from sage.all import *
>>> Q = P*RDF(Integer(8)/Integer(9))
>>> Q.integral_points_count()
1

Unbounded polyhedra (with or without lattice points) are not supported:

sage: P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]])
sage: P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...
sage: P = Polyhedron(vertices=[[1, 1]], rays=[[1, 1]])
sage: P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...
>>> from sage.all import *
>>> P = Polyhedron(vertices=[[Integer(1)/Integer(2), Integer(1)/Integer(3)]], rays=[[Integer(1), Integer(1)]])
>>> P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...
>>> P = Polyhedron(vertices=[[Integer(1), Integer(1)]], rays=[[Integer(1), Integer(1)]])
>>> P.integral_points_count()
Traceback (most recent call last):
...
NotImplementedError: ...
is_lattice_polytope()[source]¶

Return whether the polyhedron is a lattice polytope.

OUTPUT:

True if the polyhedron is compact and has only integral vertices, False otherwise.

EXAMPLES:

sage: polytopes.cross_polytope(3).is_lattice_polytope()
True
sage: polytopes.regular_polygon(5).is_lattice_polytope()                    # needs sage.rings.number_field
False
>>> from sage.all import *
>>> polytopes.cross_polytope(Integer(3)).is_lattice_polytope()
True
>>> polytopes.regular_polygon(Integer(5)).is_lattice_polytope()                    # needs sage.rings.number_field
False
lattice_polytope(envelope=False)[source]¶

Return an encompassing lattice polytope.

INPUT:

  • envelope – boolean (default: False); if the polyhedron has non-integral vertices, this option decides whether to return a strictly larger lattice polytope or raise a ValueError. This option has no effect if the polyhedron has already integral vertices.

OUTPUT:

A LatticePolytope. If the polyhedron is compact and has integral vertices, the lattice polytope equals the polyhedron. If the polyhedron is compact but has at least one non-integral vertex, a strictly larger lattice polytope is returned.

If the polyhedron is not compact, a NotImplementedError is raised.

If the polyhedron is not integral and envelope=False, a ValueError is raised.

ALGORITHM:

For each non-integral vertex, a bounding box of integral points is added and the convex hull of these integral points is returned.

EXAMPLES:

First, a polyhedron with integral vertices:

sage: P = Polyhedron(vertices=[(1, 0), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope(); lp
2-d reflexive polytope... in 2-d lattice M
sage: lp                                                            # optional - polytopes_db, needs palp
2-d reflexive polytope #3 in 2-d lattice M
sage: lp.vertices()
M(-1,  0),
M( 0, -1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M
>>> from sage.all import *
>>> P = Polyhedron(vertices=[(Integer(1), Integer(0)), (Integer(0), Integer(1)), (-Integer(1), Integer(0)), (Integer(0), -Integer(1))])
>>> lp = P.lattice_polytope(); lp
2-d reflexive polytope... in 2-d lattice M
>>> lp                                                            # optional - polytopes_db, needs palp
2-d reflexive polytope #3 in 2-d lattice M
>>> lp.vertices()
M(-1,  0),
M( 0, -1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M

Here is a polyhedron with non-integral vertices:

sage: P = Polyhedron( vertices = [(1/2, 1/2), (0, 1), (-1, 0), (0, -1)])
sage: lp = P.lattice_polytope()
Traceback (most recent call last):
...
ValueError: Some vertices are not integral. You probably want
to add the argument "envelope=True" to compute an enveloping
lattice polytope.
sage: lp = P.lattice_polytope(True)
sage: lp                                                            # optional - polytopes_db, needs palp
2-d reflexive polytope #5 in 2-d lattice M
sage: lp.vertices()
M(-1,  0),
M( 0, -1),
M( 1,  1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M
>>> from sage.all import *
>>> P = Polyhedron( vertices = [(Integer(1)/Integer(2), Integer(1)/Integer(2)), (Integer(0), Integer(1)), (-Integer(1), Integer(0)), (Integer(0), -Integer(1))])
>>> lp = P.lattice_polytope()
Traceback (most recent call last):
...
ValueError: Some vertices are not integral. You probably want
to add the argument "envelope=True" to compute an enveloping
lattice polytope.
>>> lp = P.lattice_polytope(True)
>>> lp                                                            # optional - polytopes_db, needs palp
2-d reflexive polytope #5 in 2-d lattice M
>>> lp.vertices()
M(-1,  0),
M( 0, -1),
M( 1,  1),
M( 0,  1),
M( 1,  0)
in 2-d lattice M
random_integral_point(**kwds)[source]¶

Return an integral point in this polyhedron chosen uniformly at random.

INPUT:

  • **kwds – optional keyword parameters that are passed to get_integral_point()

OUTPUT:

The integral point in the polyhedron chosen uniformly at random. If the polyhedron is not compact, a ValueError is raised. If the polyhedron does not contain any integral points, an EmptySetError is raised.

See also

get_integral_point().

EXAMPLES:

sage: P = Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)])
sage: P.random_integral_point()                                     # random
(0, 0)
sage: P.random_integral_point() in P.integral_points()
True
sage: P.random_integral_point(explicit_enumeration_threshold=0,     # random, optional - latte_int
....:                         triangulation='cddlib')
(1, 1)
sage: P.random_integral_point(explicit_enumeration_threshold=0,     # optional - latte_int
....:                         triangulation='cddlib', foo=7)
Traceback (most recent call last):
...
RuntimeError: ...

sage: Q = Polyhedron(vertices=[(2, 1/3)], rays=[(1, 2)])
sage: Q.random_integral_point()
Traceback (most recent call last):
...
ValueError: ...

sage: R = Polyhedron(vertices=[(1/2, 0), (1, 1/2), (0, 1/2)])
sage: R.random_integral_point()
Traceback (most recent call last):
...
EmptySetError: ...
>>> from sage.all import *
>>> P = Polyhedron(vertices=[(-Integer(1),-Integer(1)),(Integer(1),Integer(0)),(Integer(1),Integer(1)),(Integer(0),Integer(1))])
>>> P.random_integral_point()                                     # random
(0, 0)
>>> P.random_integral_point() in P.integral_points()
True
>>> P.random_integral_point(explicit_enumeration_threshold=Integer(0),     # random, optional - latte_int
...                         triangulation='cddlib')
(1, 1)
>>> P.random_integral_point(explicit_enumeration_threshold=Integer(0),     # optional - latte_int
...                         triangulation='cddlib', foo=Integer(7))
Traceback (most recent call last):
...
RuntimeError: ...

>>> Q = Polyhedron(vertices=[(Integer(2), Integer(1)/Integer(3))], rays=[(Integer(1), Integer(2))])
>>> Q.random_integral_point()
Traceback (most recent call last):
...
ValueError: ...

>>> R = Polyhedron(vertices=[(Integer(1)/Integer(2), Integer(0)), (Integer(1), Integer(1)/Integer(2)), (Integer(0), Integer(1)/Integer(2))])
>>> R.random_integral_point()
Traceback (most recent call last):
...
EmptySetError: ...
Next
Base class for polyhedra: Methods regarding the combinatorics of a polyhedron
Previous
Base class for polyhedra: Implementation of the ConvexSet_base API
Copyright © 2005--2025, The Sage Development Team
Made with Sphinx and @pradyunsg's Furo
On this page
  • Base class for polyhedra: Methods related to lattice points
    • Polyhedron_base2
      • generating_function_of_integral_points()
      • get_integral_point()
      • h_star_vector()
      • integral_points()
      • integral_points_count()
      • is_lattice_polytope()
      • lattice_polytope()
      • random_integral_point()