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

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

Python

>>> 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

Sage Live

# needs sage.combinat
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)]))
P2[0].generating_function_of_integral_points(sort_factors=True)
P2[1].generating_function_of_integral_points(sort_factors=True)
(P2[0] & P2[1]).Hrepresentation()
(P2[0] & P2[1]).generating_function_of_integral_points(sort_factors=True)

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

Sage

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

Python

>>> 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

Sage Live

# needs sage.combinat
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)])
f = P.generating_function_of_integral_points(sort_factors=True); f
f = f.value()
P.<z> = PowerSeriesRing(ZZ)
c = f.subs({y: z for y in f.parent().gens()}); c
([Partitions(k, length=5).cardinality() for k in range(5,20)] ==
    c.truncate().coefficients(sparse=False)[5:20])

See also

integral_points_count().

EXAMPLES:

Sage

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: ...

Python

>>> 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: ...

Sage Live

P = Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)])
P.get_integral_point(1)
P.get_integral_point(4)
sorted(P.integral_points())
P.get_integral_point(5)
Q = Polyhedron([(1,3), (2, 7), (9, 77)])
[Q.get_integral_point(i) for i in range(Q.integral_points_count())] == sorted(Q.integral_points())
Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib')  # optional - latte_int
Q.get_integral_point(0, explicit_enumeration_threshold=0, triangulation='cddlib', foo=True)  # optional - latte_int
R = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]])
R.get_integral_point(0)

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

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]]

Python

>>> 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]]

Sage Live

# optional - pynormaliz
s1 = polytopes.simplex(1,backend='normaliz')
s2 = polytopes.simplex(2,backend='normaliz')
s3 = polytopes.simplex(3,backend='normaliz')
[s1.h_star_vector(), s2.h_star_vector(), s3.h_star_vector()]

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

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]

Python

>>> 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]

Sage Live

cube = polytopes.cube(intervals='zero_one', backend='normaliz')   # optional - pynormaliz
cube.h_star_vector()                                              # optional - pynormaliz
from sage.combinat.combinat import eulerian_number
[eulerian_number(3,i) for i in range(3)]

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

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))

Python

>>> 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))

Sage Live

Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)]).integral_points()
simplex = Polyhedron([(1,2,3), (2,3,7), (-2,-3,-11)])
simplex.integral_points()

The polyhedron need not be full-dimensional:

Sage

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()
()

Python

>>> 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()
()

Sage Live

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

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

Python

>>> 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

Sage Live

v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
simplex = Polyhedron(v); simplex
len(simplex.integral_points())

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

Sage

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),)

Python

>>> 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),)

Sage Live

P = 1/10*polytopes.hypercube(14, backend='field')
P.integral_points()

Finally, the 3-d reflexive polytope number 4078:

Sage

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

Python

>>> 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

Sage Live

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

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

sage: P = polytopes.cube()
sage: P.integral_points_count()
27

Python

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

Sage Live

P = polytopes.cube()
P.integral_points_count()

We shrink the polyhedron a little bit:

Sage

sage: Q = P*(8/9)
sage: Q.integral_points_count()
1

Python

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

Sage Live

Q = P*(8/9)
Q.integral_points_count()

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

sage: Q = P*RDF(8/9)
sage: Q.integral_points_count()
1

Python

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

Sage Live

Q = P*RDF(8/9)
Q.integral_points_count()

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

Sage

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: ...

Python

>>> 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: ...

Sage Live

P = Polyhedron(vertices=[[1/2, 1/3]], rays=[[1, 1]])
P.integral_points_count()
P = Polyhedron(vertices=[[1, 1]], rays=[[1, 1]])
P.integral_points_count()

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

sage: polytopes.cross_polytope(3).is_lattice_polytope()
True
sage: polytopes.regular_polygon(5).is_lattice_polytope()                    # needs sage.rings.number_field
False

Python

>>> 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

Sage Live

polytopes.cross_polytope(3).is_lattice_polytope()
polytopes.regular_polygon(5).is_lattice_polytope()                    # needs sage.rings.number_field

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

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

Python

>>> 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

Sage Live

P = Polyhedron(vertices=[(1, 0), (0, 1), (-1, 0), (0, -1)])
lp = P.lattice_polytope(); lp
lp                                                            # optional - polytopes_db, needs palp
lp.vertices()

Here is a polyhedron with non-integral vertices:

Sage

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

Python

>>> 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

Sage Live

P = Polyhedron( vertices = [(1/2, 1/2), (0, 1), (-1, 0), (0, -1)])
lp = P.lattice_polytope()
lp = P.lattice_polytope(True)
lp                                                            # optional - polytopes_db, needs palp
lp.vertices()

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.