Base class for polyhedra over \(\ZZ\)

class sage.geometry.polyhedron.base_ZZ.Polyhedron_ZZ(parent, Vrep, Hrep, **kwds)

Bases: sage.geometry.polyhedron.base_QQ.Polyhedron_QQ

Base class for Polyhedra over \(\ZZ\)

Minkowski_decompositions(*args, **kwds)

Deprecated: Use minkowski_decompositions() instead. See trac ticket #23685 for details.

ehrhart_polynomial(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.

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.

INPUT:

  • verbose - (boolean, default to False) if True, print the whole output of the LattE command.

The following options are passed to the LattE command, for details you should 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

Note

Any additional argument is forwarded to LattE’s executable count. All occurrences of ‘_’ will be replaced with a ‘-‘.

ALGORITHM:

This method calls the program count from LattE integrale, a program for lattice point enumeration (see https://www.math.ucdavis.edu/~latte/).

See also

latte the interface to LattE integrale

EXAMPLES:

sage: P = Polyhedron(vertices=[(0,0,0),(3,3,3),(-3,2,1),(1,-1,-2)])
sage: p = P.ehrhart_polynomial()    # optional - latte_int
sage: p                             # optional - latte_int
7/2*t^3 + 2*t^2 - 1/2*t + 1
sage: p(1)                          # optional - latte_int
6
sage: len(P.integral_points())
6
sage: p(2)                          # optional - latte_int
36
sage: len((2*P).integral_points())
36

The unit hypercubes:

sage: from itertools import product
sage: def hypercube(d):
....:     return Polyhedron(vertices=list(product([0,1],repeat=d)))
sage: hypercube(3).ehrhart_polynomial()   # optional - latte_int
t^3 + 3*t^2 + 3*t + 1
sage: hypercube(4).ehrhart_polynomial()   # optional - latte_int
t^4 + 4*t^3 + 6*t^2 + 4*t + 1
sage: hypercube(5).ehrhart_polynomial()   # optional - latte_int
t^5 + 5*t^4 + 10*t^3 + 10*t^2 + 5*t + 1
sage: hypercube(6).ehrhart_polynomial()   # optional - latte_int
t^6 + 6*t^5 + 15*t^4 + 20*t^3 + 15*t^2 + 6*t + 1

An empty polyhedron:

sage: P = Polyhedron(ambient_dim=3, vertices=[])
sage: P.ehrhart_polynomial()    # optional - latte_int
0
sage: parent(_)                 # optional - latte_int
Univariate Polynomial Ring in t over Rational Field
fibration_generator(dim)

Generate the lattice polytope fibrations.

For the purposes of this function, a lattice polytope fiber is a sub-lattice polytope. Projecting the plane spanned by the subpolytope to a point yields another lattice polytope, the base of the fibration.

INPUT:

  • dim – integer. The dimension of the lattice polytope fiber.

OUTPUT:

A generator yielding the distinct lattice polytope fibers of given dimension.

EXAMPLES:

sage: P = Polyhedron(toric_varieties.P4_11169().fan().rays(), base_ring=ZZ)
sage: list( P.fibration_generator(2) )
[A 2-dimensional polyhedron in ZZ^4 defined as the convex hull of 3 vertices]
find_translation(translated_polyhedron)

Return the translation vector to translated_polyhedron.

INPUT:

  • translated_polyhedron – a polyhedron.

OUTPUT:

A \(\ZZ\)-vector that translates self to translated_polyhedron. A ValueError is raised if translated_polyhedron is not a translation of self, this can be used to check that two polyhedra are not translates of each other.

EXAMPLES:

sage: X = polytopes.cube()
sage: X.find_translation(X + vector([2,3,5]))
(2, 3, 5)
sage: X.find_translation(2*X)
Traceback (most recent call last):
...
ValueError: polyhedron is not a translation of self
has_IP_property()

Test whether the polyhedron has the IP property.

The IP (interior point) property means that

  • self is compact (a polytope).
  • self contains the origin as an interior point.

This implies that

  • self is full-dimensional.
  • The dual polyhedron is again a polytope (that is, a compact polyhedron), though not necessarily a lattice polytope.

EXAMPLES:

sage: Polyhedron([(1,1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
False
sage: Polyhedron([(0,0),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
False
sage: Polyhedron([(-1,-1),(1,0),(0,1)], base_ring=ZZ).has_IP_property()
True

REFERENCES:

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

EXAMPLES:

sage: p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
sage: p.is_reflexive()
True
minkowski_decompositions()

Return all Minkowski sums that add up to the polyhedron.

OUTPUT:

A tuple consisting of pairs \((X,Y)\) of \(\ZZ\)-polyhedra that add up to self. All pairs up to exchange of the summands are returned, that is, \((Y,X)\) is not included if \((X,Y)\) already is.

EXAMPLES:

sage: square = Polyhedron(vertices=[(0,0),(1,0),(0,1),(1,1)])
sage: square.minkowski_decompositions()
((A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
  A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
 (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
  A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices))

Example from http://cgi.di.uoa.gr/~amantzaf/geo/

 sage: Q = Polyhedron(vertices=[(4,0), (6,0), (0,3), (4,3)])
 sage: R = Polyhedron(vertices=[(0,0), (5,0), (8,4), (3,2)])
 sage: (Q+R).minkowski_decompositions()
 ((A 0-dimensional polyhedron in ZZ^2 defined as the convex hull of 1 vertex,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 5 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 5 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 3 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 7 vertices),
  (A 1-dimensional polyhedron in ZZ^2 defined as the convex hull of 2 vertices,
   A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 6 vertices))

sage: [ len(square.dilation(i).minkowski_decompositions())
....:   for i in range(6) ]
[1, 2, 5, 8, 13, 18]
sage: [ ceil((i^2+2*i-1)/2)+1 for i in range(10) ]
[1, 2, 5, 8, 13, 18, 25, 32, 41, 50]
polar()

Return the polar (dual) polytope.

The polytope must have the IP-property (see has_IP_property()), that is, the origin must be an interior point. In particular, it must be full-dimensional.

OUTPUT:

The polytope whose vertices are the coefficient vectors of the inequalities of self with inhomogeneous term normalized to unity.

EXAMPLES:

sage: p = Polyhedron(vertices=[(1,0,0),(0,1,0),(0,0,1),(-1,-1,-1)], base_ring=ZZ)
sage: p.polar()
A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 4 vertices
sage: type(_)
<class 'sage.geometry.polyhedron.parent.Polyhedra_ZZ_ppl_with_category.element_class'>
sage: p.polar().base_ring()
Integer Ring