Base class for polyhedra over \(\QQ\)

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

Bases: Polyhedron_base

Base class for Polyhedra over \(\QQ\).

Hstar_function(acting_group=None, output=None)[source]

Return \(H^*\) as a rational function in \(t\) with coefficients in the ring of class functions of the acting_group of this polytope.

Here, \(H^*(t) = \sum_{m} \chi_{m\text{self}}t^m \det(Id-\rho(t))\). The irreducible characters of acting_group form an orthonormal basis for the ring of class functions with values in \(\CC\). The coefficients of \(H^*(t)\) are expressed in this basis.

INPUT:

  • acting_group – (default=None) a permgroup object. A subgroup of the polytope’s restricted_automorphism_group. If None, it is set to the full restricted_automorphism_group of the polytope. The acting group should always use output='permutation'.

  • output – string. an output option. The allowed values are:

    • None (default): returns the rational function \(H^*(t)\). \(H^*\) is a rational function in \(t\) with coefficients in the ring of class functions.

    • 'e_series_list': Returns a list of the ehrhart_series for the fixed_subpolytopes of each conjugacy class representative.

    • 'determinant_vec': Returns a list of the determinants of \(Id-\rho*t\) for each conjugacy class representative.

    • 'Hstar_as_lin_comb': Returns a vector of the coefficients of the irreducible representations in the expression of \(H^*\).

    • 'prod_det_es': Returns a vector of the product of determinants and the Ehrhart series.

    • 'complete': Returns a list with Hstar, Hstar_as_lin_comb, character table of the acting group, and whether Hstar is effective.

OUTPUT:

The default output is the rational function \(H^*\). \(H^*\) is a rational function in \(t\) with coefficients in the ring of class functions. There are several output options to see the intermediary outputs of the function.

EXAMPLES:

The \(H^*\)-polynomial of the standard (\(d-1\))-dimensional simplex \(S = conv(e_1, \dots, e_d)\) under its restricted_automorphism_group() is equal to 1 = \(\chi_{trivial}\) (Prop 6.1 [Stap2011]). Here is the computation for the 3-dimensional standard simplex:

sage: # optional - pynormaliz
sage: S = polytopes.simplex(3, backend='normaliz'); S
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
sage: G = S.restricted_automorphism_group(
....:         output='permutation')
sage: G.is_isomorphic(SymmetricGroup(4))
True
sage: Hstar = S._Hstar_function_normaliz(G); Hstar
chi_4
sage: G.character_table()
[ 1 -1  1  1 -1]
[ 3 -1  0 -1  1]
[ 2  0 -1  2  0]
[ 3  1  0 -1 -1]
[ 1  1  1  1  1]

>>> from sage.all import *
>>> # optional - pynormaliz
>>> S = polytopes.simplex(Integer(3), backend='normaliz'); S
A 3-dimensional polyhedron in ZZ^4 defined as the convex hull of 4 vertices
>>> G = S.restricted_automorphism_group(
...         output='permutation')
>>> G.is_isomorphic(SymmetricGroup(Integer(4)))
True
>>> Hstar = S._Hstar_function_normaliz(G); Hstar
chi_4
>>> G.character_table()
[ 1 -1  1  1 -1]
[ 3 -1  0 -1  1]
[ 2  0 -1  2  0]
[ 3  1  0 -1 -1]
[ 1  1  1  1  1]

# optional - pynormaliz
S = polytopes.simplex(3, backend='normaliz'); S
G = S.restricted_automorphism_group(
        output='permutation')
G.is_isomorphic(SymmetricGroup(4))
Hstar = S._Hstar_function_normaliz(G); Hstar
G.character_table()

The next example is Example 7.6 in [Stap2011], and shows that \(H^*\) is not always a polynomial. Let P be the polytope with vertices \(\pm(0,0,1),\pm(1,0,1), \pm(0,1,1), \pm(1,1,1)\) and let G = \(\Zmod{2}\) act on P as follows:

sage: # optional - pynormaliz
sage: P = Polyhedron(vertices=[[0,0,1], [0,0,-1], [1,0,1],
....:                          [-1,0,-1], [0,1,1],
....:                          [0,-1,-1], [1,1,1], [-1,-1,-1]],
....:                backend='normaliz')
sage: K = P.restricted_automorphism_group(
....:         output='permutation')
sage: G = K.subgroup(gens=[K([(0,2),(1,3),(4,6),(5,7)])])
sage: conj_reps = G.conjugacy_classes_representatives()
sage: Dict = P.permutations_to_matrices(conj_reps,
....:                                   acting_group=G)
sage: list(Dict.keys())[0]
(0,2)(1,3)(4,6)(5,7)
sage: list(Dict.values())[0]
[-1  0  1  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0  1]
sage: len(G)
2
sage: G.character_table()
[ 1  1]
[ 1 -1]

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(1)], [Integer(0),Integer(0),-Integer(1)], [Integer(1),Integer(0),Integer(1)],
...                          [-Integer(1),Integer(0),-Integer(1)], [Integer(0),Integer(1),Integer(1)],
...                          [Integer(0),-Integer(1),-Integer(1)], [Integer(1),Integer(1),Integer(1)], [-Integer(1),-Integer(1),-Integer(1)]],
...                backend='normaliz')
>>> K = P.restricted_automorphism_group(
...         output='permutation')
>>> G = K.subgroup(gens=[K([(Integer(0),Integer(2)),(Integer(1),Integer(3)),(Integer(4),Integer(6)),(Integer(5),Integer(7))])])
>>> conj_reps = G.conjugacy_classes_representatives()
>>> Dict = P.permutations_to_matrices(conj_reps,
...                                   acting_group=G)
>>> list(Dict.keys())[Integer(0)]
(0,2)(1,3)(4,6)(5,7)
>>> list(Dict.values())[Integer(0)]
[-1  0  1  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0  1]
>>> len(G)
2
>>> G.character_table()
[ 1  1]
[ 1 -1]

# optional - pynormaliz
P = Polyhedron(vertices=[[0,0,1], [0,0,-1], [1,0,1],
                         [-1,0,-1], [0,1,1],
                         [0,-1,-1], [1,1,1], [-1,-1,-1]],
               backend='normaliz')
K = P.restricted_automorphism_group(
        output='permutation')
G = K.subgroup(gens=[K([(0,2),(1,3),(4,6),(5,7)])])
conj_reps = G.conjugacy_classes_representatives()
Dict = P.permutations_to_matrices(conj_reps,
                                  acting_group=G)
list(Dict.keys())[0]
list(Dict.values())[0]
len(G)
G.character_table()

Then we calculate the rational function \(H^*(t)\):

sage: Hst = P._Hstar_function_normaliz(G); Hst              # optional - pynormaliz
(chi_0*t^4 + (3*chi_0 + 3*chi_1)*t^3
  + (8*chi_0 + 2*chi_1)*t^2 + (3*chi_0 + 3*chi_1)*t + chi_0)/(t + 1)

>>> from sage.all import *
>>> Hst = P._Hstar_function_normaliz(G); Hst              # optional - pynormaliz
(chi_0*t^4 + (3*chi_0 + 3*chi_1)*t^3
  + (8*chi_0 + 2*chi_1)*t^2 + (3*chi_0 + 3*chi_1)*t + chi_0)/(t + 1)

Hst = P._Hstar_function_normaliz(G); Hst              # optional - pynormaliz

To see the exact as written in [Stap2011], we can format it as 'Hstar_as_lin_comb'. The first coordinate is the coefficient of the trivial character; the second is the coefficient of the sign character:

sage: lin = P._Hstar_function_normaliz(                     # optional - pynormaliz
....:           G, output='Hstar_as_lin_comb'); lin
((t^4 + 3*t^3 + 8*t^2 + 3*t + 1)/(t + 1),
 (3*t^3 + 2*t^2 + 3*t)/(t + 1))

>>> from sage.all import *
>>> lin = P._Hstar_function_normaliz(                     # optional - pynormaliz
...           G, output='Hstar_as_lin_comb'); lin
((t^4 + 3*t^3 + 8*t^2 + 3*t + 1)/(t + 1),
 (3*t^3 + 2*t^2 + 3*t)/(t + 1))

lin = P._Hstar_function_normaliz(                     # optional - pynormaliz
          G, output='Hstar_as_lin_comb'); lin
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)[source]

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())
6
sage: poly(2)                                               # optional - latte_int
36
sage: len((2*simplex).integral_points())
36

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

simplex = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
simplex = simplex.change_ring(QQ)
poly = simplex.ehrhart_polynomial(engine='latte')     # optional - latte_int
poly                                                  # optional - latte_int
poly(1)                                               # optional - latte_int
len(simplex.integral_points())
poly(2)                                               # optional - latte_int
len((2*simplex).integral_points())

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

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

# optional - pynormaliz
simplex = Polyhedron(vertices=[(0,0,0), (3,3,3),
                               (-3,2,1), (1,-1,-2)],
                     backend='normaliz')
simplex = simplex.change_ring(QQ)
poly = simplex.ehrhart_polynomial(engine='normaliz')
poly

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')
Traceback (most recent call last):
...
TypeError: The backend of the polyhedron should be 'normaliz'

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

simplex = Polyhedron(vertices=[(0,0,0), (3,3,3),
                               (-3,2,1), (1,-1,-2)])
simplex = simplex.change_ring(QQ)
simplex.ehrhart_polynomial(engine='normaliz')

The polyhedron should be compact:

sage: C = Polyhedron(rays=[[1,2], [2,1]],                   # optional - pynormaliz
....:                backend='normaliz')
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

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

C = Polyhedron(rays=[[1,2], [2,1]],                   # optional - pynormaliz
               backend='normaliz')
C = C.change_ring(QQ)                                 # optional - pynormaliz
C.ehrhart_polynomial()                                # optional - pynormaliz

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'

>>> from sage.all import *
>>> L = Polyhedron(vertices=[[Integer(0)], [Integer(1)/Integer(2)]])
>>> L.ehrhart_polynomial()
Traceback (most recent call last):
...
TypeError: the polytope has nonintegral vertices, use ehrhart_quasipolynomial with backend 'normaliz'

L = Polyhedron(vertices=[[0], [1/2]])
L.ehrhart_polynomial()
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)[source]

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

    • 'latte'; use LattE Integrale program (requires optional package ‘latte_int’)

    • 'normaliz'; use the Normaliz program (requires 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]],          # optional - pynormaliz
....:                       backend='normaliz'); line_seg
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)

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

line_seg = Polyhedron(vertices=[[0], [1/2]],          # optional - pynormaliz
                      backend='normaliz'); line_seg
line_seg.ehrhart_quasipolynomial()                    # optional - pynormaliz

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,                  # optional - pynormaliz
....:                      backend='normaliz')
sage: eq = subpoly.ehrhart_quasipolynomial(); eq            # optional - pynormaliz
(4*t^2 + 3*t + 1, 4*t^2 + 2*t)
sage: eq = subpoly.ehrhart_quasipolynomial(); 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

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

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]]
subpoly = Polyhedron(vertices=verts,                  # optional - pynormaliz
                     backend='normaliz')
eq = subpoly.ehrhart_quasipolynomial(); eq            # optional - pynormaliz
eq = subpoly.ehrhart_quasipolynomial(); eq            # optional - pynormaliz
even_ep = eq[0]                                       # optional - pynormaliz
odd_ep  = eq[1]                                       # optional - pynormaliz
even_ep(2)                                            # optional - pynormaliz
ts = 2*subpoly                                        # optional - pynormaliz
ts.integral_points_count()                            # optional - pynormaliz latte_int
odd_ep(1)                                             # optional - pynormaliz
subpoly.integral_points_count()                       # optional - pynormaliz latte_int

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'

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

line_seg = Polyhedron(vertices=[[0], [1/2]])
line_seg.ehrhart_quasipolynomial()

The polyhedron should be compact:

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

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

C = Polyhedron(rays=[[1/2,2], [2,1]],                 # optional - pynormaliz
               backend='normaliz')
C.ehrhart_quasipolynomial()                           # optional - pynormaliz

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

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

>>> from sage.all import *
>>> # optional - pynormaliz
>>> simplex = Polyhedron(vertices=[(Integer(0),Integer(0),Integer(0)), (Integer(3),Integer(3),Integer(3)),
...                                (-Integer(3),Integer(2),Integer(1)), (Integer(1),-Integer(1),-Integer(2))],
...                      backend='normaliz')
>>> simplex = simplex.change_ring(QQ)
>>> poly = simplex.ehrhart_quasipolynomial(
...     engine='normaliz'); poly
7/2*t^3 + 2*t^2 - 1/2*t + 1
>>> simplex.ehrhart_polynomial()                          # optional - latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1

# optional - pynormaliz
simplex = Polyhedron(vertices=[(0,0,0), (3,3,3),
                               (-3,2,1), (1,-1,-2)],
                     backend='normaliz')
simplex = simplex.change_ring(QQ)
poly = simplex.ehrhart_quasipolynomial(
    engine='normaliz'); poly
simplex.ehrhart_polynomial()                          # optional - latte_int
fixed_subpolytope(vertex_permutation)[source]

Return the fixed subpolytope of this polytope by the cyclic action of vertex_permutation.

The fixed subpolytope of this polytope under the vertex_permutation is the subset of this polytope that is fixed pointwise.

INPUT:

  • vertex_permutation – permutation; a permutation of the vertices of self

OUTPUT: a subpolytope of self

Note

The vertex_permutation is obtained as a permutation of the vertices represented as a permutation. For example, vertex_permutation = self.restricted_automorphism_group(output=’permutation’).

Requiring a lattice polytope as opposed to a rational polytope as input is purely conventional.

EXAMPLES:

The fixed subpolytopes of the cube can be obtained as follows:

sage: Cube = polytopes.cube(backend = 'normaliz')           # optional - pynormaliz
sage: AG = Cube.restricted_automorphism_group(              # optional - pynormaliz
....:          output='permutation')
sage: reprs = AG.conjugacy_classes_representatives()        # optional - pynormaliz

>>> from sage.all import *
>>> Cube = polytopes.cube(backend = 'normaliz')           # optional - pynormaliz
>>> AG = Cube.restricted_automorphism_group(              # optional - pynormaliz
...          output='permutation')
>>> reprs = AG.conjugacy_classes_representatives()        # optional - pynormaliz

Cube = polytopes.cube(backend = 'normaliz')           # optional - pynormaliz
AG = Cube.restricted_automorphism_group(              # optional - pynormaliz
         output='permutation')
reprs = AG.conjugacy_classes_representatives()        # optional - pynormaliz

The fixed subpolytope of the identity element of the group is the entire cube:

sage: reprs[0]                                              # optional - pynormaliz
()
sage: Cube.fixed_subpolytope(vertex_permutation=reprs[0])   # optional - pynormaliz
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8
vertices
sage: _.vertices()                                          # optional - pynormaliz
(A vertex at (-1, -1, -1),
 A vertex at (-1, -1, 1),
 A vertex at (-1, 1, -1),
 A vertex at (-1, 1, 1),
 A vertex at (1, -1, -1),
 A vertex at (1, -1, 1),
 A vertex at (1, 1, -1),
 A vertex at (1, 1, 1))

>>> from sage.all import *
>>> reprs[Integer(0)]                                              # optional - pynormaliz
()
>>> Cube.fixed_subpolytope(vertex_permutation=reprs[Integer(0)])   # optional - pynormaliz
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8
vertices
>>> _.vertices()                                          # optional - pynormaliz
(A vertex at (-1, -1, -1),
 A vertex at (-1, -1, 1),
 A vertex at (-1, 1, -1),
 A vertex at (-1, 1, 1),
 A vertex at (1, -1, -1),
 A vertex at (1, -1, 1),
 A vertex at (1, 1, -1),
 A vertex at (1, 1, 1))

reprs[0]                                              # optional - pynormaliz
Cube.fixed_subpolytope(vertex_permutation=reprs[0])   # optional - pynormaliz
_.vertices()                                          # optional - pynormaliz

You can obtain non-trivial examples:

sage: G = AG([(0,1),(2,3),(4,5),(6,7)])                     # optional - pynormaliz
sage: fsp = Cube.fixed_subpolytope(G); fsp                  # optional - pynormaliz
A 2-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
sage: fsp.vertices()                                        # optional - pynormaliz
(A vertex at (-1, -1, 0),
 A vertex at (-1, 1, 0),
 A vertex at (1, -1, 0),
 A vertex at (1, 1, 0))

>>> from sage.all import *
>>> G = AG([(Integer(0),Integer(1)),(Integer(2),Integer(3)),(Integer(4),Integer(5)),(Integer(6),Integer(7))])                     # optional - pynormaliz
>>> fsp = Cube.fixed_subpolytope(G); fsp                  # optional - pynormaliz
A 2-dimensional polyhedron in QQ^3 defined as the convex hull of 4 vertices
>>> fsp.vertices()                                        # optional - pynormaliz
(A vertex at (-1, -1, 0),
 A vertex at (-1, 1, 0),
 A vertex at (1, -1, 0),
 A vertex at (1, 1, 0))

G = AG([(0,1),(2,3),(4,5),(6,7)])                     # optional - pynormaliz
fsp = Cube.fixed_subpolytope(G); fsp                  # optional - pynormaliz
fsp.vertices()                                        # optional - pynormaliz

The next example shows that fixed_subpolytope() works for rational polytopes:

sage: # optional - pynormaliz
sage: P = Polyhedron(vertices=[[0], [1/2]],
....:                backend='normaliz')
sage: P.vertices()
(A vertex at (0), A vertex at (1/2))
sage: G = P.restricted_automorphism_group(
....:         output='permutation'); G
Permutation Group with generators [(0,1)]
sage: len(G)
2
sage: fixed_set = P.fixed_subpolytope(G.gens()[0])
sage: fixed_set
A 0-dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex
sage: fixed_set.vertices_list()
[[1/4]]

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P = Polyhedron(vertices=[[Integer(0)], [Integer(1)/Integer(2)]],
...                backend='normaliz')
>>> P.vertices()
(A vertex at (0), A vertex at (1/2))
>>> G = P.restricted_automorphism_group(
...         output='permutation'); G
Permutation Group with generators [(0,1)]
>>> len(G)
2
>>> fixed_set = P.fixed_subpolytope(G.gens()[Integer(0)])
>>> fixed_set
A 0-dimensional polyhedron in QQ^1 defined as the convex hull of 1 vertex
>>> fixed_set.vertices_list()
[[1/4]]

# optional - pynormaliz
P = Polyhedron(vertices=[[0], [1/2]],
               backend='normaliz')
P.vertices()
G = P.restricted_automorphism_group(
        output='permutation'); G
len(G)
fixed_set = P.fixed_subpolytope(G.gens()[0])
fixed_set
fixed_set.vertices_list()
fixed_subpolytopes(conj_class_reps)[source]

Return the fixed subpolytopes of this polytope under the actions of the given conjugacy class representatives.

The conj_class_reps are representatives of the conjugacy classes of a subgroup of the automorphism group of this polytope. For an element of the automorphism group, the fixed subpolytope is the subset of this polytope that is fixed pointwise.

INPUT:

  • conj_class_reps – list of representatives of the conjugacy classes of the subgroup of the restricted_automorphism_group() of the polytope. Each element is written as a permutation of the vertices of the polytope.

OUTPUT:

A dictionary where the elements of conj_class_reps are keys and the fixed subpolytopes are values.

Note

Two elements in the same conjugacy class fix lattice-isomorphic subpolytopes.

EXAMPLES:

Here is an example for the square:

sage: # optional - pynormaliz, needs sage.groups
sage: p = polytopes.hypercube(2, backend='normaliz'); p
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: aut_p = p.restricted_automorphism_group(
....:             output='permutation')
sage: aut_p.order()
8
sage: conj_list = aut_p.conjugacy_classes_representatives()
sage: fixedpolytopes_dict = p.fixed_subpolytopes(conj_list)
sage: fixedpolytopes_dict[aut_p([(0,3),(1,2)])]
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex

>>> from sage.all import *
>>> # optional - pynormaliz, needs sage.groups
>>> p = polytopes.hypercube(Integer(2), backend='normaliz'); p
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
>>> aut_p = p.restricted_automorphism_group(
...             output='permutation')
>>> aut_p.order()
8
>>> conj_list = aut_p.conjugacy_classes_representatives()
>>> fixedpolytopes_dict = p.fixed_subpolytopes(conj_list)
>>> fixedpolytopes_dict[aut_p([(Integer(0),Integer(3)),(Integer(1),Integer(2))])]
A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex

# optional - pynormaliz, needs sage.groups
p = polytopes.hypercube(2, backend='normaliz'); p
aut_p = p.restricted_automorphism_group(
            output='permutation')
aut_p.order()
conj_list = aut_p.conjugacy_classes_representatives()
fixedpolytopes_dict = p.fixed_subpolytopes(conj_list)
fixedpolytopes_dict[aut_p([(0,3),(1,2)])]
integral_points_count(verbose=False, use_Hrepresentation=False, explicit_enumeration_threshold=1000, preprocess=True, **kwds)[source]

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 (default: False); whether to display verbose output

  • use_Hrepresentation – boolean (default: False); whether to send the H or V representation to LattE

  • preprocess – boolean (default: True); 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

>>> from sage.all import *
>>> P = polytopes.cube()
>>> P.integral_points_count()
27
>>> P.integral_points_count(explicit_enumeration_threshold=Integer(0))  # optional - latte_int
27

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

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

>>> from sage.all import *
>>> (Integer(1000000000)*P).integral_points_count(verbose=True)         # optional - latte_int
This is LattE integrale...
...
Total time:...
8000000012000000006000000001

(1000000000*P).integral_points_count(verbose=True)         # optional - latte_int

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

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

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

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

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

“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           # needs sage.combinat
33

>>> from sage.all import *
>>> 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+Integer(3))*x[i] for i in range(d)) <= b)
...     return lp.polyhedron(backend=backend)
>>> fibonacci_knapsack(Integer(20), Integer(12)).integral_points_count()  # does not finish with preprocess=False           # needs sage.combinat
33

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)
fibonacci_knapsack(20, 12).integral_points_count()  # does not finish with preprocess=False           # needs sage.combinat
is_effective(Hstar, Hstar_as_lin_comb)[source]

Test for the effectiveness of the Hstar series of this polytope.

The Hstar series of the polytope is determined by the action of a subgroup of the polytope’s restricted_automorphism_group(). The Hstar series is effective if it is a polynomial in \(t\) and the coefficient of each \(t^i\) is an effective character in the ring of class functions of the acting group. A character \(\rho\) is effective if the coefficients of the irreducible representations in the expression of \(\rho\) are nonnegative integers.

INPUT:

  • Hstar – a rational function in \(t\) with coefficients in the ring of class functions

  • Hstar_as_lin_comb – vector. The coefficients of the irreducible representations of the acting group in the expression of Hstar as a linear combination of irreducible representations with coefficients in the field of rational functions in \(t\).

OUTPUT: boolean; whether the Hstar series is effective

See also

Hstar_function()

EXAMPLES:

The \(H^*\) series of the two-dimensional permutahedron under the action of the symmetric group is effective:

sage: # optional - pynormaliz
sage: p3 = polytopes.permutahedron(3, backend='normaliz')
sage: G = p3.restricted_automorphism_group(
....:         output='permutation')
sage: reflection12 = G([(0,2),(1,4),(3,5)])
sage: reflection23 = G([(0,1),(2,3),(4,5)])
sage: S3 = G.subgroup(gens=[reflection12, reflection23])
sage: S3.is_isomorphic(SymmetricGroup(3))
True
sage: Hstar = p3.Hstar_function(S3)
sage: Hlin  = p3.Hstar_function(S3,
....:                           output='Hstar_as_lin_comb')
sage: p3.is_effective(Hstar, Hlin)
True

>>> from sage.all import *
>>> # optional - pynormaliz
>>> p3 = polytopes.permutahedron(Integer(3), backend='normaliz')
>>> G = p3.restricted_automorphism_group(
...         output='permutation')
>>> reflection12 = G([(Integer(0),Integer(2)),(Integer(1),Integer(4)),(Integer(3),Integer(5))])
>>> reflection23 = G([(Integer(0),Integer(1)),(Integer(2),Integer(3)),(Integer(4),Integer(5))])
>>> S3 = G.subgroup(gens=[reflection12, reflection23])
>>> S3.is_isomorphic(SymmetricGroup(Integer(3)))
True
>>> Hstar = p3.Hstar_function(S3)
>>> Hlin  = p3.Hstar_function(S3,
...                           output='Hstar_as_lin_comb')
>>> p3.is_effective(Hstar, Hlin)
True

# optional - pynormaliz
p3 = polytopes.permutahedron(3, backend='normaliz')
G = p3.restricted_automorphism_group(
        output='permutation')
reflection12 = G([(0,2),(1,4),(3,5)])
reflection23 = G([(0,1),(2,3),(4,5)])
S3 = G.subgroup(gens=[reflection12, reflection23])
S3.is_isomorphic(SymmetricGroup(3))
Hstar = p3.Hstar_function(S3)
Hlin  = p3.Hstar_function(S3,
                          output='Hstar_as_lin_comb')
p3.is_effective(Hstar, Hlin)

If the \(H^*\)-series is not polynomial, then it is not effective:

sage: # optional - pynormaliz
sage: P = Polyhedron(vertices=[[0,0,1], [0,0,-1], [1,0,1],
....:                          [-1,0,-1], [0,1,1],
....:                          [0,-1,-1], [1,1,1], [-1,-1,-1]],
....:                backend='normaliz')
sage: G = P.restricted_automorphism_group(
....:         output='permutation')
sage: H = G.subgroup(gens=[G([(0,2),(1,3),(4,6),(5,7)])])
sage: Hstar = P.Hstar_function(H); Hstar
(chi_0*t^4 + (3*chi_0 + 3*chi_1)*t^3
  + (8*chi_0 + 2*chi_1)*t^2 + (3*chi_0 + 3*chi_1)*t + chi_0)/(t + 1)
sage: Hstar_lin = P.Hstar_function(H,
....:                              output='Hstar_as_lin_comb')
sage: P.is_effective(Hstar, Hstar_lin)
False

>>> from sage.all import *
>>> # optional - pynormaliz
>>> P = Polyhedron(vertices=[[Integer(0),Integer(0),Integer(1)], [Integer(0),Integer(0),-Integer(1)], [Integer(1),Integer(0),Integer(1)],
...                          [-Integer(1),Integer(0),-Integer(1)], [Integer(0),Integer(1),Integer(1)],
...                          [Integer(0),-Integer(1),-Integer(1)], [Integer(1),Integer(1),Integer(1)], [-Integer(1),-Integer(1),-Integer(1)]],
...                backend='normaliz')
>>> G = P.restricted_automorphism_group(
...         output='permutation')
>>> H = G.subgroup(gens=[G([(Integer(0),Integer(2)),(Integer(1),Integer(3)),(Integer(4),Integer(6)),(Integer(5),Integer(7))])])
>>> Hstar = P.Hstar_function(H); Hstar
(chi_0*t^4 + (3*chi_0 + 3*chi_1)*t^3
  + (8*chi_0 + 2*chi_1)*t^2 + (3*chi_0 + 3*chi_1)*t + chi_0)/(t + 1)
>>> Hstar_lin = P.Hstar_function(H,
...                              output='Hstar_as_lin_comb')
>>> P.is_effective(Hstar, Hstar_lin)
False

# optional - pynormaliz
P = Polyhedron(vertices=[[0,0,1], [0,0,-1], [1,0,1],
                         [-1,0,-1], [0,1,1],
                         [0,-1,-1], [1,1,1], [-1,-1,-1]],
               backend='normaliz')
G = P.restricted_automorphism_group(
        output='permutation')
H = G.subgroup(gens=[G([(0,2),(1,3),(4,6),(5,7)])])
Hstar = P.Hstar_function(H); Hstar
Hstar_lin = P.Hstar_function(H,
                             output='Hstar_as_lin_comb')
P.is_effective(Hstar, Hstar_lin)