Generating Function of Polyhedron’s Integral Points#

This module provides generating_function_of_integral_points() which computes the generating function of the integral points of a polyhedron.

The main function is accessible via sage.geometry.polyhedron.base.Polyhedron_base.generating_function_of_integral_points() as well.

Various#

AUTHORS:

Daniel Krenn (2016, 2021)

ACKNOWLEDGEMENT:

Daniel Krenn is supported by the Austrian Science Fund (FWF): P 24644-N26 and by the Austrian Science Fund (FWF): P 28466-N35.

Functions#

sage.geometry.polyhedron.generating_function.generating_function_of_integral_points(polyhedron, split=False, result_as_tuple=None, name=None, names=None, **kwds)#

Return the multivariate generating function of the integral points of the 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}}.\]

INPUT:

polyhedron – an instance of Polyhedron_base (see also sage.geometry.polyhedron.constructor)
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, 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: from sage.geometry.polyhedron.generating_function import generating_function_of_integral_points

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: generating_function_of_integral_points(P2[0], sort_factors=True)
1 * (-y0 + 1)^-1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1
sage: generating_function_of_integral_points(P2[1], 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: generating_function_of_integral_points(P2[0] & P2[1], sort_factors=True)
1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1

sage: P3 = (
....:   Polyhedron(
....:     ieqs=[(0, 0, 0, 0, 1), (0, 0, 0, 1, 0),
....:           (0, 0, 1, 0, -1), (-1, 1, 0, -1, -1)]),
....:   Polyhedron(
....:     ieqs=[(0, 0, -1, 0, 1), (0, 1, 0, 0, -1),
....:           (0, 0, 0, 1, 0), (0, 0, 1, 0, 0), (-1, 1, -1, -1, 0)]),
....:   Polyhedron(
....:     ieqs=[(1, -1, 0, 1, 1), (1, -1, 1, 1, 0),
....:           (0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 1, 0, 0),
....:           (1, 0, 1, 1, -1), (0, 1, 0, 0, 0), (1, 1, 1, 0, -1)]),
....:   Polyhedron(
....:     ieqs=[(0, 1, 0, -1, 0), (0, -1, 0, 0, 1),
....:           (-1, 0, -1, -1, 1), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0)]),
....:   Polyhedron(
....:     ieqs=[(0, 1, 0, 0, 0), (0, 0, 1, 0, 0),
....:           (-1, -1, -1, 0, 1), (0, -1, 0, 1, 0)]))
sage: def intersect(I):
....:     I = iter(I)
....:     result = next(I)
....:     for i in I:
....:         result &= i
....:     return result
sage: for J in subsets(range(len(P3))):
....:     if not J:
....:         continue
....:     P = intersect([P3[j] for j in J])
....:     print('{}: {}'.format(J, P.Hrepresentation()))
....:     print(generating_function_of_integral_points(P, sort_factors=True))
[0]: (An inequality (0, 0, 0, 1) x + 0 >= 0,
      An inequality (0, 0, 1, 0) x + 0 >= 0,
      An inequality (0, 1, 0, -1) x + 0 >= 0,
      An inequality (1, 0, -1, -1) x - 1 >= 0)
y0 * (-y0 + 1)^-1 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1 * (-y0*y1*y3 + 1)^-1
[1]: (An inequality (0, -1, 0, 1) x + 0 >= 0,
      An inequality (0, 0, 1, 0) x + 0 >= 0,
      An inequality (0, 1, 0, 0) x + 0 >= 0,
      An inequality (1, -1, -1, 0) x - 1 >= 0,
      An inequality (1, 0, 0, -1) x + 0 >= 0)
(-y0^2*y2*y3 - y0^2*y3 + y0*y3 + y0) *
(-y0 + 1)^-1 * (-y0*y2 + 1)^-1 * (-y0*y3 + 1)^-1 *
(-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 1]: (An equation (0, 1, 0, -1) x + 0 == 0,
         An inequality (1, -1, -1, 0) x - 1 >= 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0,
         An inequality (0, 0, 1, 0) x + 0 >= 0)
y0 * (-y0 + 1)^-1 * (-y0*y2 + 1)^-1 * (-y0*y1*y3 + 1)^-1
[2]: (An inequality (-1, 0, 1, 1) x + 1 >= 0,
     An inequality (-1, 1, 1, 0) x + 1 >= 0,
      An inequality (0, 0, 0, 1) x + 0 >= 0,
      An inequality (0, 0, 1, 0) x + 0 >= 0,
      An inequality (0, 1, 0, 0) x + 0 >= 0,
      An inequality (0, 1, 1, -1) x + 1 >= 0,
      An inequality (1, 0, 0, 0) x + 0 >= 0,
      An inequality (1, 1, 0, -1) x + 1 >= 0)
(y0^2*y1*y2*y3^2 + y0^2*y2^2*y3 + y0*y1^2*y3^2 - y0^2*y2*y3 +
 y0*y1*y2*y3 - y0*y1*y3^2 - 2*y0*y1*y3 - 2*y0*y2*y3 - y0*y2 +
 y0*y3 - y1*y3 + y0 + y3 + 1) *
(-y1 + 1)^-1 * (-y2 + 1)^-1 * (-y0*y2 + 1)^-1 *
(-y1*y3 + 1)^-1 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 2]: (An equation (1, 0, -1, -1) x - 1 == 0,
         An inequality (-1, 1, 1, 0) x + 1 >= 0,
         An inequality (1, 0, -1, 0) x - 1 >= 0,
         An inequality (0, 0, 1, 0) x + 0 >= 0)
y0 * (-y1 + 1)^-1 * (-y0*y2 + 1)^-1 * (-y0*y1*y3 + 1)^-1
[1, 2]: (An equation (1, -1, -1, 0) x - 1 == 0,
         An inequality (0, -1, 0, 1) x + 0 >= 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0,
         An inequality (1, 0, 0, -1) x + 0 >= 0,
         An inequality (1, -1, 0, 0) x - 1 >= 0)
(-y0^2*y2*y3 + y0*y3 + y0) *
(-y0*y2 + 1)^-1 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 1, 2]: (An equation (0, 1, 0, -1) x + 0 == 0,
            An equation (1, -1, -1, 0) x - 1 == 0,
            An inequality (0, 1, 0, 0) x + 0 >= 0,
            An inequality (1, -1, 0, 0) x - 1 >= 0)
y0 * (-y0*y2 + 1)^-1 * (-y0*y1*y3 + 1)^-1
[3]: (An inequality (-1, 0, 0, 1) x + 0 >= 0,
      An inequality (0, -1, -1, 1) x - 1 >= 0,
      An inequality (0, 0, 1, 0) x + 0 >= 0,
      An inequality (0, 1, 0, 0) x + 0 >= 0,
      An inequality (1, 0, -1, 0) x + 0 >= 0)
(-y0*y1*y3^2 - y0*y3^2 + y0*y3 + y3) *
(-y3 + 1)^-1 * (-y0*y3 + 1)^-1 *
(-y1*y3 + 1)^-1 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 3]: (An equation -1 == 0,)
0
[1, 3]: (An equation (1, 0, 0, -1) x + 0 == 0,
         An inequality (1, -1, -1, 0) x - 1 >= 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0,
         An inequality (0, 0, 1, 0) x + 0 >= 0)
y0*y3 * (-y0*y3 + 1)^-1 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 1, 3]: (An equation -1 == 0,)
0
[2, 3]: (An equation (0, 1, 1, -1) x + 1 == 0,
         An inequality (1, 0, -1, 0) x + 0 >= 0,
         An inequality (-1, 1, 1, 0) x + 1 >= 0,
         An inequality (0, 0, 1, 0) x + 0 >= 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0)
(-y0*y1*y3^2 + y0*y3 + y3) *
(-y1*y3 + 1)^-1 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 2, 3]: (An equation -1 == 0,)
0
[1, 2, 3]: (An equation (1, 0, 0, -1) x + 0 == 0,
            An equation (1, -1, -1, 0) x - 1 == 0,
            An inequality (0, 1, 0, 0) x + 0 >= 0,
            An inequality (1, -1, 0, 0) x - 1 >= 0)
y0*y3 * (-y0*y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 1, 2, 3]: (An equation -1 == 0,)
0
[4]: (An inequality (-1, -1, 0, 1) x - 1 >= 0,
      An inequality (-1, 0, 1, 0) x + 0 >= 0,
      An inequality (0, 1, 0, 0) x + 0 >= 0,
      An inequality (1, 0, 0, 0) x + 0 >= 0)
y3 * (-y2 + 1)^-1 * (-y3 + 1)^-1 * (-y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 4]: (An equation -1 == 0,)
0
[1, 4]: (An equation -1 == 0,)
0
[0, 1, 4]: (An equation -1 == 0,)
0
[2, 4]: (An equation (1, 1, 0, -1) x + 1 == 0,
         An inequality (-1, 0, 1, 0) x + 0 >= 0,
         An inequality (1, 0, 0, 0) x + 0 >= 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0)
y3 * (-y2 + 1)^-1 * (-y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 2, 4]: (An equation -1 == 0,)
0
[1, 2, 4]: (An equation -1 == 0,)
0
[0, 1, 2, 4]: (An equation -1 == 0,)
0
[3, 4]: (An equation (1, 0, -1, 0) x + 0 == 0,
         An inequality (0, 1, 0, 0) x + 0 >= 0,
         An inequality (-1, -1, 0, 1) x - 1 >= 0,
         An inequality (1, 0, 0, 0) x + 0 >= 0)
y3 * (-y3 + 1)^-1 * (-y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 3, 4]: (An equation -1 == 0,)
0
[1, 3, 4]: (An equation -1 == 0,)
0
[0, 1, 3, 4]: (An equation -1 == 0,)
0
[2, 3, 4]: (An equation (1, 1, 0, -1) x + 1 == 0,
            An equation (1, 0, -1, 0) x + 0 == 0,
            An inequality (0, 1, 0, 0) x + 0 >= 0,
            An inequality (1, 0, 0, 0) x + 0 >= 0)
y3 * (-y1*y3 + 1)^-1 * (-y0*y2*y3 + 1)^-1
[0, 2, 3, 4]: (An equation -1 == 0,)
0
[1, 2, 3, 4]: (An equation -1 == 0,)
0
[0, 1, 2, 3, 4]: (An equation -1 == 0,)
0

sage: P = Polyhedron(vertices=[[1], [5]])
sage: P.generating_function_of_integral_points()
y0^5 + y0^4 + y0^3 + y0^2 + y0