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

Bases: Polyhedron_base1

Methods related to lattice points.

See sage.geometry.polyhedron.base.Polyhedron_base.

generating_function_of_integral_points(**kwds)#

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 – (default: False) a boolean 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 – a 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 – (default: False) a boolean

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

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

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

h_star_vector()#

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.

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

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]

integral_points(threshold=100000)#

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

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

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

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

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

integral_points_count(**kwds)#

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

We shrink the polyhedron a little bit:

sage: Q = P*(8/9)
sage: 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

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

is_lattice_polytope()#

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

lattice_polytope(envelope=False)#

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

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

random_integral_point(**kwds)#

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.