Base class for polyhedra over \(\QQ\)

class sage.geometry.polyhedron.base_QQ.Polyhedron_QQ(parent, Vrep, Hrep, **kwds)

Bases: sage.geometry.polyhedron.base.Polyhedron_base

Base class for Polyhedra over \(\QQ\)

ehrhart_polynomial(engine=None, variable='t', verbose=False, dual=None, irrational_primal=None, irrational_all_primal=None, maxdet=None, no_decomposition=None, compute_vertex_cones=None, smith_form=None, dualization=None, triangulation=None, triangulation_max_height=None, **kwds)

Return the Ehrhart polynomial of this polyhedron.

The polyhedron must be a lattice polytope. Let \(P\) be a lattice polytope in \(\RR^d\) and define \(L(P,t) = \# (tP\cap \ZZ^d)\). Then E. Ehrhart proved in 1962 that \(L\) coincides with a rational polynomial of degree \(d\) for integer \(t\). \(L\) is called the Ehrhart polynomial of \(P\). For more information see the Wikipedia article Ehrhart_polynomial. The Ehrhart polynomial may be computed using either LattE Integrale or Normaliz by setting engine to ‘latte’ or ‘normaliz’ respectively.

INPUT:

  • engine – string; The backend to use. Allowed values are:

    • None (default); When no input is given the Ehrhart polynomial is computed using LattE Integrale (optional)
    • 'latte'; use LattE integrale program (optional)
    • 'normaliz'; use Normaliz program (optional package pynormaliz). The backend of self must be set to ‘normaliz’.
  • variable – string (default: ‘t’); The variable in which the Ehrhart polynomial should be expressed.

  • When the engine is ‘latte’, the additional input values are:

    • verbose - boolean (default: False); If True, print the whole output of the LattE command.

    The following options are passed to the LattE command, for details consult the LattE documentation:

    • dual - boolean; triangulate and signed-decompose in the dual space
    • irrational_primal - boolean; triangulate in the dual space, signed-decompose in the primal space using irrationalization.
    • irrational_all_primal - boolean; triangulate and signed-decompose in the primal space using irrationalization.
    • maxdet – integer; decompose down to an index (determinant) of maxdet instead of index 1 (unimodular cones).
    • no_decomposition – boolean; do not signed-decompose simplicial cones.
    • compute_vertex_cones – string; either ‘cdd’ or ‘lrs’ or ‘4ti2’
    • smith_form – string; either ‘ilio’ or ‘lidia’
    • dualization – string; either ‘cdd’ or ‘4ti2’
    • triangulation - string; ‘cddlib’, ‘4ti2’ or ‘topcom’
    • triangulation_max_height - integer; use a uniform distribution of height from 1 to this number

OUTPUT:

A univariate polynomial in variable over a rational field.

See also

latte the interface to LattE Integrale PyNormaliz

EXAMPLES:

To start, we find the Ehrhart polynomial of a three-dimensional simplex, first using engine='latte'. Leaving the engine unspecified sets the engine to ‘latte’ by default:

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
sage: simplex = simplex.change_ring(QQ)
sage: poly = simplex.ehrhart_polynomial(engine='latte')  # optional - latte_int
sage: poly                                               # optional - latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1
sage: poly(1)                                            # optional - latte_int
6
sage: len(simplex.integral_points())                     # optional - latte_int
6
sage: poly(2)                                            # optional - latte_int
36
sage: len((2*simplex).integral_points())                 # optional - latte_int
36

Now we find the same Ehrhart polynomial, this time using engine='normaliz'. To use the Normaliz engine, the simplex must be defined with backend='normaliz':

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)], backend='normaliz') # optional - pynormaliz
sage: simplex = simplex.change_ring(QQ)                                                       # optional - pynormaliz
sage: poly = simplex.ehrhart_polynomial(engine = 'normaliz')                                  # optional - pynormaliz
sage: poly                                                                                    # optional - pynormaliz
7/2*t^3 + 2*t^2 - 1/2*t + 1

If the engine='normaliz', the backend should be 'normaliz', otherwise it returns an error:

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
sage: simplex = simplex.change_ring(QQ)
sage: simplex.ehrhart_polynomial(engine='normaliz')  # optional - pynormaliz
Traceback (most recent call last):
...
TypeError: The backend of the polyhedron should be 'normaliz'

The polyhedron should be compact:

sage: C = Polyhedron(backend='normaliz',rays=[[1,2],[2,1]])  # optional - pynormaliz
sage: C = C.change_ring(QQ)                                  # optional - pynormaliz
sage: C.ehrhart_polynomial()                                 # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: Ehrhart polynomial only defined for compact polyhedra

The polyhedron should have integral vertices:

sage: L = Polyhedron(vertices = [[0],[1/2]])
sage: L.ehrhart_polynomial()
Traceback (most recent call last):
...
TypeError: the polytope has nonintegral vertices, use ehrhart_quasipolynomial with backend 'normaliz'
ehrhart_quasipolynomial(variable='t', engine=None, verbose=False, dual=None, irrational_primal=None, irrational_all_primal=None, maxdet=None, no_decomposition=None, compute_vertex_cones=None, smith_form=None, dualization=None, triangulation=None, triangulation_max_height=None, **kwds)

Compute the Ehrhart quasipolynomial of this polyhedron with rational vertices.

If the polyhedron is a lattice polytope, returns the Ehrhart polynomial, a univariate polynomial in variable over a rational field. If the polyhedron has rational, nonintegral vertices, returns a tuple of polynomials in variable over a rational field. The Ehrhart counting function of a polytope \(P\) with rational vertices is given by a quasipolynomial. That is, there exists a positive integer \(l\) and \(l\) polynomials \(ehr_{P,i} \text{ for } i \in \{1,\dots,l \}\) such that if \(t\) is equivalent to \(i\) mod \(l\) then \(tP \cap \mathbb Z^d = ehr_{P,i}(t)\).

INPUT:

  • variable – string (default: ‘t’); The variable in which the Ehrhart polynomial should be expressed.

  • engine – string; The backend to use. Allowed values are:

    • None (default); When no input is given the Ehrhart polynomial is computed using LattE Integrale (optional)
    • 'latte'; use LattE integrale program (optional)
    • 'normaliz'; use Normaliz program (optional package pynormaliz). The backend of self must be set to ‘normaliz’.
  • When the engine is ‘latte’, the additional input values are:

    • verbose - boolean (default: False); If True, print the whole output of the LattE command.

    The following options are passed to the LattE command, for details consult the LattE documentation:

    • dual - boolean; triangulate and signed-decompose in the dual space
    • irrational_primal - boolean; triangulate in the dual space, signed-decompose in the primal space using irrationalization.
    • irrational_all_primal - boolean; triangulate and signed-decompose in the primal space using irrationalization.
    • maxdet – integer; decompose down to an index (determinant) of maxdet instead of index 1 (unimodular cones).
    • no_decomposition – boolean; do not signed-decompose simplicial cones.
    • compute_vertex_cones – string; either ‘cdd’ or ‘lrs’ or ‘4ti2’
    • smith_form – string; either ‘ilio’ or ‘lidia’
    • dualization – string; either ‘cdd’ or ‘4ti2’
    • triangulation - string; ‘cddlib’, ‘4ti2’ or ‘topcom’
    • triangulation_max_height - integer; use a uniform distribution of height from 1 to this number

OUTPUT:

A univariate polynomial over a rational field or a tuple of such polynomials.

See also

latte the interface to LattE Integrale PyNormaliz

Warning

If the polytope has rational, non integral vertices, it must have backend='normaliz'.

EXAMPLES:

As a first example, consider the line segment [0,1/2]. If we dilate this line segment by an even integral factor \(k\), then the dilated line segment will contain \(k/2 +1\) lattice points. If \(k\) is odd then there will be \(k/2+1/2\) lattice points in the dilated line segment. Note that it is necessary to set the backend of the polytope to ‘normaliz’:

sage: line_seg = Polyhedron(vertices=[[0],[1/2]],backend='normaliz') # optional - pynormaliz
sage: line_seg                                                       # optional - pynormaliz
A 1-dimensional polyhedron in QQ^1 defined as the convex hull of 2 vertices
sage: line_seg.ehrhart_quasipolynomial()                             # optional - pynormaliz
(1/2*t + 1, 1/2*t + 1/2)

For a more exciting example, let us look at the subpolytope of the 3 dimensional permutahedron fixed by the reflection across the hyperplane \(x_1 = x_4\):

sage: verts = [[3/2, 3, 4, 3/2],
....:  [3/2, 4, 3, 3/2],
....:  [5/2, 1, 4, 5/2],
....:  [5/2, 4, 1, 5/2],
....:  [7/2, 1, 2, 7/2],
....:  [7/2, 2, 1, 7/2]]
sage: subpoly = Polyhedron(vertices=verts, backend='normaliz') # optional - pynormaliz
sage: eq = subpoly.ehrhart_quasipolynomial()    # optional - pynormaliz
sage: eq                                        # optional - pynormaliz
(4*t^2 + 3*t + 1, 4*t^2 + 2*t)
sage: eq = subpoly.ehrhart_quasipolynomial()    # optional - pynormaliz
sage: eq                                        # optional - pynormaliz
(4*t^2 + 3*t + 1, 4*t^2 + 2*t)
sage: even_ep = eq[0]                           # optional - pynormaliz
sage: odd_ep  = eq[1]                           # optional - pynormaliz
sage: even_ep(2)                                # optional - pynormaliz
23
sage: ts = 2*subpoly                            # optional - pynormaliz
sage: ts.integral_points_count()                # optional - pynormaliz latte_int
23
sage: odd_ep(1)                                 # optional - pynormaliz
6
sage: subpoly.integral_points_count()           # optional - pynormaliz latte_int
6

A polytope with rational nonintegral vertices must have backend='normaliz':

sage: line_seg = Polyhedron(vertices=[[0],[1/2]])
sage: line_seg.ehrhart_quasipolynomial()
Traceback (most recent call last):
...
TypeError: The backend of the polyhedron should be 'normaliz'

The polyhedron should be compact:

sage: C = Polyhedron(backend='normaliz',rays=[[1/2,2],[2,1]])  # optional - pynormaliz
sage: C.ehrhart_quasipolynomial()                              # optional - pynormaliz
Traceback (most recent call last):
...
ValueError: Ehrhart quasipolynomial only defined for compact polyhedra

If the polytope happens to be a lattice polytope, the Ehrhart polynomial is returned:

sage: simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)], backend='normaliz') # optional - pynormaliz
sage: simplex = simplex.change_ring(QQ)                                                       # optional - pynormaliz
sage: poly = simplex.ehrhart_quasipolynomial(engine='normaliz')                               # optional - pynormaliz
sage: poly                                                                                    # optional - pynormaliz
7/2*t^3 + 2*t^2 - 1/2*t + 1
sage: simplex.ehrhart_polynomial()                                                            # optional - pynormaliz latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1
integral_points_count(verbose=False, use_Hrepresentation=False, explicit_enumeration_threshold=1000, preprocess=True, **kwds)

Return the number of integral points in the polyhedron.

This method uses the optional package latte_int if an estimate for lattice points based on bounding boxes exceeds explicit_enumeration_threshold.

INPUT:

  • verbose (boolean; False by default) – whether to display verbose output.
  • use_Hrepresentation - (boolean; False by default) – whether to send the H or V representation to LattE
  • preprocess - (boolean; True by default) – whether, if the integral hull is known to lie in a coordinate hyperplane, to tighten bounds to reduce dimension

See also

latte the interface to LattE interfaces

EXAMPLES:

sage: P = polytopes.cube()
sage: P.integral_points_count()
27
sage: P.integral_points_count(explicit_enumeration_threshold=0) # optional - latte_int
27

We enlarge the polyhedron to force the use of the generating function methods implemented in LattE integrale, rather than explicit enumeration.

sage: (1000000000*P).integral_points_count(verbose=True) # optional - latte_int This is LattE integrale… … Total time:… 8000000012000000006000000001

We shrink the polyhedron a little bit:

sage: Q = P*(8/9)
sage: Q.integral_points_count()
1
sage: Q.integral_points_count(explicit_enumeration_threshold=0) # optional - latte_int
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: ...

“Fibonacci” knapsacks (preprocessing helps a lot):

sage: def fibonacci_knapsack(d, b, backend=None):
....:     lp = MixedIntegerLinearProgram(base_ring=QQ)
....:     x = lp.new_variable(nonnegative=True)
....:     lp.add_constraint(lp.sum(fibonacci(i+3)*x[i] for i in range(d)) <= b)
....:     return lp.polyhedron(backend=backend)
sage: fibonacci_knapsack(20, 12).integral_points_count() # does not finish with preprocess=False
33