Code for multi-row models

cutgeneratingfunctionology.multirow.GrowthDiagramBinWord
cutgeneratingfunctionology.multirow.GrowthDiagramBurge
cutgeneratingfunctionology.multirow.GrowthDiagramDomino
cutgeneratingfunctionology.multirow.GrowthDiagramRSK
cutgeneratingfunctionology.multirow.GrowthDiagramSylvester
cutgeneratingfunctionology.multirow.GrowthDiagramYoungFibonacci
cutgeneratingfunctionology.multirow.LinearCodeFromVectorSpace
class cutgeneratingfunctionology.multirow.PiecewisePolynomial_polyhedral(polyhedron_function_pairs, periodic_extension=False, is_continuous=None, check_consistency=False)

Bases: sage.structure.sage_object.SageObject

Define a piecewise polynomial function using pairs of (polyhedron, function).

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: square = Polyhedron(vertices = itertools.product([0, 1], repeat=2))
sage: R.<x,y>=PolynomialRing(QQ)
sage: h1 = PiecewisePolynomial_polyhedral([(square, x+y)])
sage: h1
<PiecewisePolynomial_polyhedral with 1 parts, 
 domain: A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices: (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))
 function: x + y>
sage: h1.is_continuous()
True
sage: h2 = PiecewisePolynomial_polyhedral([(square, -x-y)], is_continuous=True)
sage: h1 + h2 == PiecewisePolynomial_polyhedral([(square, R(0))])
True
sage: h1 * h2
<PiecewisePolynomial_polyhedral with 1 parts, 
 domain: A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices: (A vertex at (1, 0), A vertex at (1, 1), A vertex at (0, 1), A vertex at (0, 0))
 function: -x^2 - 2*x*y - y^2>
sage: hmax = PiecewisePolynomial_polyhedral.max(h1, h2)
sage: hmax
<PiecewisePolynomial_polyhedral with 1 parts, 
 domain: A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices: (A vertex at (0, 0), A vertex at (1, 1), A vertex at (0, 1), A vertex at (1, 0))
 function: x + y>
sage: hmax.is_continuous()
True

Set check_consistency=True. Compare h to g = PiecewisePolynomial_polyhedral(pairs, check_consistency=False).plot():

sage: pairs = [(polytopes.hypercube(2), x),(polytopes.hypercube(2), -x),(polytopes.hypercube(2), y),(polytopes.hypercube(2), -y)]

#sage: h = PiecewisePolynomial_polyhedral(pairs, check_consistency=True)
#Traceback (most recent call last):
#...
#ValueError: Cannot define the PiecewisePolynomial_polyhedral due to inconsistent polyhedron function pairs

sage: hxp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), x)], is_continuous = True)
sage: hxn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -x)], is_continuous = True)
sage: hyp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), y)], is_continuous = True)
sage: hyn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -y)], is_continuous = True)
sage: hsublin = PiecewisePolynomial_polyhedral.max(hxp, hxn, hyp, hyn)
sage: hsublin.limiting_slopes([0,0])
[(0, 1), (0, -1), (1, 0), (-1, 0)]
sage: h_restricted = hsublin.restricted_to_domain(polytopes.hypercube(2)/2)
sage: h_restricted.plot() # not tested
sage: len(h_restricted.pairs())
6

sage: hsquare = PiecewisePolynomial_polyhedral(h_restricted.pairs(), periodic_extension=True)
sage: hsquare.plot() # not tested
sage: hsquare.limiting_slopes([5,1])
[(0, 1), (0, -1), (1, 0), (-1, 0)]
sage: hsquare([5,1])
0
sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(5,3/2),(11/2,3/2)]))
y - 1
sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(9/2,1),(9/2,3/2)]))
-x + 5
sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(11/2,1),(11/2,3/2)]))
x - 5
sage: len(hsquare.pairs())
8

sage: hsquare_res = hsquare.restricted_to_domain(polytopes.hypercube(2)/2)
sage: hsquare_res == h_restricted
True
__add__(other)

Add self and another piecewise function. The sum is a function defined on the intersection of the domain of self and the domain of other.

__call__(...) <==> x(...)
__dict__ = dict_proxy({'__module__': 'cutgeneratingfunctionology.multirow', '__repr__': <function __repr__>, '__dict__': <attribute '__dict__' of 'PiecewisePolynomial_polyhedral' objects>, 'is_non_negative': <function is_non_negative>, '__rmul__': <function __mul__>, '__weakref__': <attribute '__weakref__' of 'PiecewisePolynomial_polyhedral' objects>, '__init__': <function __init__>, 'plot': <function plot>, 'functions': <function functions>, 'min': <function min>, 'restricted_to_domain': <function restricted_to_domain>, '__div__': <function __div__>, 'max': <function max>, '__call__': <function __call__>, 'which_function': <function which_function>, '__doc__': '\n Define a piecewise polynomial function using pairs of (polyhedron, function).\n\n EXAMPLES::\n\n sage: from cutgeneratingfunctionology.multirow import *\n sage: square = Polyhedron(vertices = itertools.product([0, 1], repeat=2))\n sage: R.<x,y>=PolynomialRing(QQ)\n sage: h1 = PiecewisePolynomial_polyhedral([(square, x+y)])\n sage: h1\n <PiecewisePolynomial_polyhedral with 1 parts, \n domain: A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices: (A vertex at (0, 0), A vertex at (0, 1), A vertex at (1, 0), A vertex at (1, 1))\n function: x + y>\n sage: h1.is_continuous()\n True\n sage: h2 = PiecewisePolynomial_polyhedral([(square, -x-y)], is_continuous=True)\n sage: h1 + h2 == PiecewisePolynomial_polyhedral([(square, R(0))])\n True\n sage: h1 * h2\n <PiecewisePolynomial_polyhedral with 1 parts, \n domain: A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices: (A vertex at (1, 0), A vertex at (1, 1), A vertex at (0, 1), A vertex at (0, 0))\n function: -x^2 - 2*x*y - y^2>\n sage: hmax = PiecewisePolynomial_polyhedral.max(h1, h2)\n sage: hmax\n <PiecewisePolynomial_polyhedral with 1 parts, \n domain: A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices: (A vertex at (0, 0), A vertex at (1, 1), A vertex at (0, 1), A vertex at (1, 0))\n function: x + y>\n sage: hmax.is_continuous()\n True\n\n Set check_consistency=True. Compare h to g = PiecewisePolynomial_polyhedral(pairs, check_consistency=False).plot()::\n\n sage: pairs = [(polytopes.hypercube(2), x),(polytopes.hypercube(2), -x),(polytopes.hypercube(2), y),(polytopes.hypercube(2), -y)]\n\n #sage: h = PiecewisePolynomial_polyhedral(pairs, check_consistency=True)\n #Traceback (most recent call last):\n #...\n #ValueError: Cannot define the PiecewisePolynomial_polyhedral due to inconsistent polyhedron function pairs\n\n sage: hxp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), x)], is_continuous = True)\n sage: hxn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -x)], is_continuous = True)\n sage: hyp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), y)], is_continuous = True)\n sage: hyn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -y)], is_continuous = True)\n sage: hsublin = PiecewisePolynomial_polyhedral.max(hxp, hxn, hyp, hyn)\n sage: hsublin.limiting_slopes([0,0])\n [(0, 1), (0, -1), (1, 0), (-1, 0)]\n sage: h_restricted = hsublin.restricted_to_domain(polytopes.hypercube(2)/2)\n sage: h_restricted.plot() # not tested\n sage: len(h_restricted.pairs())\n 6\n\n sage: hsquare = PiecewisePolynomial_polyhedral(h_restricted.pairs(), periodic_extension=True)\n sage: hsquare.plot() # not tested\n sage: hsquare.limiting_slopes([5,1])\n [(0, 1), (0, -1), (1, 0), (-1, 0)]\n sage: hsquare([5,1])\n 0\n sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(5,3/2),(11/2,3/2)]))\n y - 1\n sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(9/2,1),(9/2,3/2)]))\n -x + 5\n sage: hsquare.which_function([5,1], Polyhedron(vertices=[(5,1),(11/2,1),(11/2,3/2)]))\n x - 5\n sage: len(hsquare.pairs())\n 8\n\n sage: hsquare_res = hsquare.restricted_to_domain(polytopes.hypercube(2)/2)\n sage: hsquare_res == h_restricted\n True\n ', '__neg__': <function __neg__>, 'from_values_on_group_triangulation': <classmethod object>, 'affine_linear_embedding': <function affine_linear_embedding>, 'polyhedra': <function polyhedra>, 'is_upper_bounded_by': <function is_upper_bounded_by>, 'plot_projection': <function plot_projection>, 'sage_input': <function sage_input>, '__add__': <function __add__>, 'intersection_of_domains': <function intersection_of_domains>, 'translation': <function translation>, '__eq__': <function __eq__>, 'dim': <function dim>, 'pairs': <function pairs>, 'is_lower_bounded_by': <function is_lower_bounded_by>, 'preimage': <function preimage>, 'is_constantly_equal_to': <function is_constantly_equal_to>, 'limit': <function limit>, '__mul__': <function __mul__>, '__hash__': <function __hash__>, '__sub__': <function __sub__>, 'is_continuous': <function is_continuous>, 'limiting_slopes': <function limiting_slopes>})
__div__(other)
__eq__(other)

Assume that self and other have the same domain (=union of the polyhedra). Return True if self == other on the domain.

__hash__()

File: sage/structure/sage_object.pyx (starting at line 326)

Not implemented: mutable objects inherit from this class

EXAMPLES:

sage: hash(SageObject())
Traceback (most recent call last):
...
TypeError: <... 'sage.structure.sage_object.SageObject'> is not hashable
__init__(polyhedron_function_pairs, periodic_extension=False, is_continuous=None, check_consistency=False)

x.__init__(…) initializes x; see help(type(x)) for signature

__module__ = 'cutgeneratingfunctionology.multirow'
__mul__(other)

Multiply self by a scalar or another piecewise function. The product is a function defined on the intersection of the domain of self and the domain of other.

__neg__()
__repr__()

File: sage/structure/sage_object.pyx (starting at line 145)

Default method for string representation.

Note

Do not overwrite this method. Instead, implement a _repr_ (single underscore) method.

EXAMPLES:

By default, the string representation coincides with the output of the single underscore _repr_:

sage: P.<x> = QQ[]
sage: repr(P) == P._repr_()  #indirect doctest
True

Using rename(), the string representation can be customized:

sage: P.rename('A polynomial ring')
sage: repr(P) == P._repr_()
False

The original behaviour is restored with reset_name().:

sage: P.reset_name()
sage: repr(P) == P._repr_()
True

If there is no _repr_ method defined, we fall back to the super class (typically object):

sage: from sage.structure.sage_object import SageObject
sage: S = SageObject()
sage: S
<sage.structure.sage_object.SageObject object at ...>
__rmul__(other)

Multiply self by a scalar or another piecewise function. The product is a function defined on the intersection of the domain of self and the domain of other.

__sub__(other)
__weakref__

list of weak references to the object (if defined)

affine_linear_embedding(A, b=None)

Given full row rank matrix A and vector b (default b = 0). Return the composition PiecewisePolynomial_polyhedral function x -> self(A*x+b).

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = hildebrand_discont_3_slope_1()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: h_vert_strip = h.affine_linear_embedding(matrix([(1,0)]))
sage: h_diag_strip = h.affine_linear_embedding(matrix([(1,1)]))
sage: h_vert_strip.plot(polytopes.hypercube(2)) # not tested
sage: h_diag_strip.plot() # not tested
dim()
classmethod from_values_on_group_triangulation(M)

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: M = matrix([[0,1/4,1/2],[1/4,1/2,3/4],[1/2,3/4,1]])  # q=3
sage: h = PiecewisePolynomial_polyhedral.from_values_on_group_triangulation(M) # grid=(1/qZ)^2

Example from Equivariant III:

sage: M = 1/4 * matrix([[0,2,2,2,2],[2,2,2,3,1],[2,2,4,2,2],[2,2,2,1,2],[2,2,2,2,3]]).transpose() # q=5 sage: h = PiecewisePolynomial_polyhedral.from_values_on_group_triangulation(M) # grid=(1/qZ)^2
functions()
intersection_of_domains(other)

Return a list of (polyhedron, f1, f2) where polyhedorn is the intersection of two polyhedra in the domains of self and of other, and f1 and f2 are the polynomial functions of self and other on the intersection. The polyhedral domains in self and other are ordered according to decreasing dimension.

is_constantly_equal_to(x)

Return True if self == x everywhere.

is_continuous(is_continuous=None)

return if the function is continuous.

is_lower_bounded_by(x)

Return True if self >= x everywhere.

is_non_negative()

Return True if self >= 0 everywhere.

is_upper_bounded_by(x)

Return True if self <= x everywhere.

limit(x, polyhedron=None)

Return the limit of self at x approaching from the relative interior of polyhedron, where the input polyhedron is contained in the domain of some piece of the function. if polyhedron=None, then return the function value at x.

limiting_slopes(x=None)

Return the gradients of the affine functions on the full-dim polyhedron whose closure contains x.

max(other, *arg)

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: R.<x,y>=PolynomialRing(QQ)
sage: hp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), x+y)])
sage: hn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -x-y)])
sage: pairs = PiecewisePolynomial_polyhedral.max(hp, hn).pairs()
sage: list(sorted( (sorted(P.vertices_list()), f) for (P, f) in pairs ))
[([[-1, -1], [-1, 1], [1, -1]], -x - y), ([[-1, 1], [1, -1], [1, 1]], x + y)]
min(other, *arg)

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: R.<x,y>=PolynomialRing(QQ)
sage: hp = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), x+y)])
sage: hn = PiecewisePolynomial_polyhedral([(polytopes.hypercube(2), -x-y)])
sage: pairs = PiecewisePolynomial_polyhedral.min(hp, hn).pairs()
sage: list(sorted( (sorted(P.vertices_list()), f) for (P, f) in pairs ))
[([[-1, -1], [-1, 1], [1, -1]], x + y), ([[-1, 1], [1, -1], [1, 1]], -x - y)]
pairs()
plot(domain=None, alpha=0.500000000000000, projection=False, **kwds)

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = hildebrand_discont_3_slope_1()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: h_diag_strip = h.affine_linear_embedding(matrix([(1,1)]))
sage: g = h_diag_strip.plot()
sage: show(g, viewer='threejs') #not tested
sage: g = plot(h_diag_strip, projection=True, width=1/60)

sage: M = matrix([[0,1/4,1/2],[1/4,1/2,3/4],[1/2,3/4,1]])  # q=3
sage: h = PiecewisePolynomial_polyhedral.from_values_on_group_triangulation(M) # grid=(1/qZ)^2
sage: g = h.plot()
plot_projection(domain=None, group_triangulation=False, show_values_on_vertices=False, **kwds)

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = hildebrand_discont_3_slope_1()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: h_diag_strip = h.affine_linear_embedding(matrix([(1,1)]))
sage: g = h_diag_strip.plot_projection()

sage: M = matrix([[0,1/4,1/2],[1/4,1/2,3/4],[1/2,3/4,1]])  # q=3
sage: h = PiecewisePolynomial_polyhedral.from_values_on_group_triangulation(M) # grid=(1/qZ)^2
sage: g = h.plot_projection(group_triangulation=True)

sage: PR.<x,y>=PolynomialRing(QQ)
sage: pairs = [(polytopes.hypercube(2)-vector([1,0]), 0), (polytopes.hypercube(2)+vector([1,0]), 0), (Polyhedron(vertices=[(0,1),(0,-1)]), x+y+1), (Polyhedron(vertices=[(0,0)]), 0)]
sage: h = PiecewisePolynomial_polyhedral(pairs)
sage: g = h.plot_projection()
sage: g.show(xmin=-0.1, xmax=0.1, ymin=-0.1, ymax=0.1) # not tested

sage: PR.<x,y> = PolynomialRing(QQ)
sage: h = PiecewisePolynomial_polyhedral([(Polyhedron(vertices=[(0, 0), (1, 1), (1, -1)]), x), (Polyhedron(vertices=[(0, 0), (-1, 1), (-1, -1)]), -x), (Polyhedron(vertices=[(0, 0), (1, 1), (-1, 1)]), y), (Polyhedron(vertices=[(0, 0), (1, -1), (-1, -1)]), -y)])
sage: g = h.plot_projection(show_values_on_vertices=True)

sage: pairs = [(Polyhedron(vertices=[(0,0), (0,1), (1,0)]), 0), (Polyhedron(vertices=[(0,0), (0,1)]), 1), (Polyhedron(vertices=[(0,1), (1,0)]), 1), (Polyhedron(vertices=[(0,0), (1,0)]), 1)]
sage: h = PiecewisePolynomial_polyhedral(pairs)
sage: g = h.plot_projection()
polyhedra()
preimage(value)

Return closure of the preimage, as a list of polyhedra, of the given value under the map self.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = gmic()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: delta = subadditivity_slack_delta(h)
sage: preimages = delta.preimage(5/4)
sage: len(preimages)
1
sage: preimages[0].vertices()
(A vertex at (4/5, 4/5), A vertex at (4/5, 1/5), A vertex at (1/5, 4/5))
sage: additive_domain= delta.preimage(0)
sage: len(additive_domain)
6
sage: g = sum(p.plot() for p in additive_domain) # not tested

sage: PR.<x,y>=PolynomialRing(QQ)
sage: pairs = [(polytopes.hypercube(2)-vector([1,0]), 0), (polytopes.hypercube(2)+vector([1,0]), 0), (Polyhedron(vertices=[(0,1),(0,-1)]), x+y+1), (Polyhedron(vertices=[(0,0)]), 0)]
sage: h = PiecewisePolynomial_polyhedral(pairs)
sage: h.preimage(1)
[]

sage: pairs = [(Polyhedron(vertices=[(0,0), (0,1), (1,0)]), 0), (Polyhedron(vertices=[(0,0), (0,1)]), 1), (Polyhedron(vertices=[(0,1), (1,0)]), 1), (Polyhedron(vertices=[(0,0), (1,0)]), 1)]
sage: h = PiecewisePolynomial_polyhedral(pairs)
sage: len(h.preimage(0))
1
restricted_to_domain(domain)

Return a PiecewisePolynomial_polyhedral which is self restricted to domain, where domain is a given polyhedron.

sage_input()
translation(t)

Return the translated PiecewisePolynomial_polyhedral function x -> self(x+t).

which_function(x=None, polyhedron=None)

Return the function of the (first) piece whose domain contains x, if polyhedron=None; return the function of the (first) piece whose domain contains polyhedron, otherwise.

cutgeneratingfunctionology.multirow.addition_names

tuple() -> empty tuple tuple(iterable) -> tuple initialized from iterable’s items

If the argument is a tuple, the return value is the same object.

cutgeneratingfunctionology.multirow.affine_map_for_affine_hull(p)

Return the an affine map x -> A*x+b that maps the affine space of p to the ambient space of p. The affine space of p (in the ambient space) is equal to {A(x) + b for x in the projected space}. This is adapted from sage.geometry.polyhedron.base.affine_hull. Note that the meanings of A, b and v0 are modified. We also handle the unbounded case.

cutgeneratingfunctionology.multirow.channels

Index of channels

Channels in Sage implement the information theoretic notion of transmission of messages.

The channels object may be used to access the codes that Sage can build.

Note

To import these names into the global namespace, use:

sage: from sage.coding.channels_catalog import *
cutgeneratingfunctionology.multirow.codes

Index of code constructions

The codes object may be used to access the codes that Sage can build.

ParityCheckCode() Parity check codes
CyclicCode() Cyclic codes
BCHCode() BCH Codes
GeneralizedReedSolomonCode() Generalized Reed-Solomon codes
ReedSolomonCode() Reed-Solomon codes
BinaryReedMullerCode() Binary Reed-Muller codes
ReedMullerCode() q-ary Reed-Muller codes
HammingCode() Hamming codes
GolayCode() Golay codes
GoppaCode() Goppa codes
DuadicCodeEvenPair() Duadic codes, even pair
DuadicCodeOddPair() Duadic codes, odd pair
QuadraticResidueCode() Quadratic residue codes
ExtendedQuadraticResidueCode() Extended quadratic residue codes
QuadraticResidueCodeEvenPair() Even-like quadratic residue codes
QuadraticResidueCodeOddPair() Odd-like quadratic residue codes
QuasiQuadraticResidueCode() Quasi quadratic residue codes (Requires GAP/Guava)
ToricCode() Toric codes
WalshCode() Walsh codes
from_parity_check_matrix() Construct a code from a parity check matrix
random_linear_code() Construct a random linear code
RandomLinearCodeGuava() Construct a random linear code through Guava (Requires GAP/Guava)
SubfieldSubcode() Subfield subcodes
ExtendedCode() Extended codes
PuncturedCode() Puncturedcodes

Note

To import these names into the global namespace, use:

sage: from sage.coding.codes_catalog import *
cutgeneratingfunctionology.multirow.crystals

Catalog Of Crystals

Let \(I\) be an index set and let \((A,\Pi,\Pi^\vee,P,P^\vee)\) be a Cartan datum associated with generalized Cartan matrix \(A = (a_{ij})_{i,j\in I}\). An abstract crystal associated to this Cartan datum is a set \(B\) together with maps

\[e_i,f_i \colon B \to B \cup \{0\}, \qquad \varepsilon_i,\varphi_i\colon B \to \ZZ \cup \{-\infty\}, \qquad \mathrm{wt}\colon B \to P,\]

subject to the following conditions:

  1. \(\varphi_i(b) = \varepsilon_i(b) + \langle h_i, \mathrm{wt}(b) \rangle\) for all \(b \in B\) and \(i \in I\);
  2. \(\mathrm{wt}(e_ib) = \mathrm{wt}(b) + \alpha_i\) if \(e_ib \in B\);
  3. \(\mathrm{wt}(f_ib) = \mathrm{wt}(b) - \alpha_i\) if \(f_ib \in B\);
  4. \(\varepsilon_i(e_ib) = \varepsilon_i(b) - 1\), \(\varphi_i(e_ib) = \varphi_i(b) + 1\) if \(e_ib \in B\);
  5. \(\varepsilon_i(f_ib) = \varepsilon_i(b) + 1\), \(\varphi_i(f_ib) = \varphi_i(b) - 1\) if \(f_ib \in B\);
  6. \(f_ib = b'\) if and only if \(b = e_ib'\) for \(b,b' \in B\) and \(i\in I\);
  7. if \(\varphi_i(b) = -\infty\) for \(b\in B\), then \(e_ib = f_ib = 0\).

See also

This is a catalog of crystals that are currently implemented in Sage:

Subcatalogs:

Functorial constructions:

TESTS:

sage: 'absolute_import' in dir(crystals)
False
cutgeneratingfunctionology.multirow.cython_create_local_so
cutgeneratingfunctionology.multirow.div_Zk(x)
cutgeneratingfunctionology.multirow.finite_dynamical_systems

Catalog of discrete dynamical systems

This module contains constructors for several specific discrete dynamical systems. These are accessible through sage.dynamics.finite_dynamical_system_catalog. or just through \(finite_dynamical_systems.\) (type either of these in Sage and hit tab for a list).

AUTHORS:

  • Darij Grinberg, Tom Roby (2018): initial version
cutgeneratingfunctionology.multirow.game_theory

Catalog Of Games

TESTS:

sage: 'absolute_import' in dir(game_theory)
False
cutgeneratingfunctionology.multirow.graph_coloring

File: sage/graphs/graph_coloring.pyx (starting at line 1)

Graph coloring

This module gathers all methods related to graph coloring. Here is what it can do :

Proper vertex coloring

all_graph_colorings() Compute all \(n\)-colorings a graph
first_coloring() Return the first vertex coloring found
number_of_n_colorings() Compute the number of \(n\)-colorings of a graph
numbers_of_colorings() Compute the number of colorings of a graph
chromatic_number() Return the chromatic number of the graph
vertex_coloring() Compute vertex colorings and chromatic numbers

Other colorings

grundy_coloring() Compute Grundy numbers and Grundy colorings
b_coloring() Compute b-chromatic numbers and b-colorings
edge_coloring() Compute chromatic index and edge colorings
round_robin() Compute a round-robin coloring of the complete graph on \(n\) vertices
linear_arboricity() Compute the linear arboricity of the given graph
acyclic_edge_coloring() Compute an acyclic edge coloring of the current graph

AUTHORS:

  • Tom Boothby (2008-02-21): Initial version
  • Carlo Hamalainen (2009-03-28): minor change: switch to C++ DLX solver
  • Nathann Cohen (2009-10-24): Coloring methods using linear programming
cutgeneratingfunctionology.multirow.groups

Examples of Groups

The groups object may be used to access examples of various groups. Using tab-completion on this object is an easy way to discover and quickly create the groups that are available (as listed here).

Let <tab> indicate pressing the tab key. So begin by typing groups.<tab> to the see primary divisions, followed by (for example) groups.matrix.<tab> to access various groups implemented as sets of matrices.

cutgeneratingfunctionology.multirow.interacts

Interacts included with sage

AUTHORS:

  • Harald Schilly (2011-01-16): initial version (#9623) partially based on work by Lauri Ruotsalainen
cutgeneratingfunctionology.multirow.is_lattice_free_polyhedron(B)
cutgeneratingfunctionology.multirow.is_maximal_lattice_free_polyhedron(B)
cutgeneratingfunctionology.multirow.is_volume_affine_in_f(B, num_tests=10)
cutgeneratingfunctionology.multirow.lie_algebras

Examples of Lie Algebras

There are the following examples of Lie algebras:

  • A rather comprehensive family of 3-dimensional Lie algebras
  • The Lie algebra of affine transformations of the line
  • All abelian Lie algebras on free modules
  • The Lie algebra of upper triangular matrices
  • The Lie algebra of strictly upper triangular matrices

See also sage.algebras.lie_algebras.virasoro.LieAlgebraRegularVectorFields and sage.algebras.lie_algebras.virasoro.VirasoroAlgebra for other examples.

AUTHORS:

  • Travis Scrimshaw (07-15-2013): Initial implementation
cutgeneratingfunctionology.multirow.lifting_regions(B, f, shifted=False)
cutgeneratingfunctionology.multirow.lifting_regions_tile_box(regions, box=None)
cutgeneratingfunctionology.multirow.matroids

Catalog of matroids

A module containing constructors for several common matroids.

A list of all matroids in this module is available via tab completion. Let <tab> indicate pressing the tab key. So begin by typing matroids.<tab> to see the various constructions available. Many special matroids can be accessed from the submenu matroids.named_matroids.<tab>.

To create a custom matroid using a variety of inputs, see the function Matroid().

cutgeneratingfunctionology.multirow.minimality_test_multirow(fn, f=None)

Test if the input PiecewisePolynomial_polyhedral function \(fn\) is a minimal function for the (multi-row) group relaxation with the given \(f\).

Example:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.WARN)             # Suppress output in automatic tests.
sage: h = gmic(4/5)
sage: fn = piecewise_polynomial_polyhedral_from_fast_piecewise(h)
sage: minimality_test_multirow(fn, f=[4/5])
True
sage: h = ll_strong_fractional()
sage: fn = piecewise_polynomial_polyhedral_from_fast_piecewise(h)
sage: minimality_test_multirow(fn)
True
sage: h_vert_strip = fn.affine_linear_embedding(matrix([(1,0)]))
sage: minimality_test_multirow(h_vert_strip, f=[2/3,2/3])
True
sage: minimality_test_multirow(h_vert_strip, f=[1/3,2/3])
False
sage: h_diag_strip = fn.affine_linear_embedding(matrix([(1,1)]))
sage: minimality_test_multirow(h_diag_strip, f=[1/3,1/3])
True

sage: h = hildebrand_discont_3_slope_1()
sage: fn = piecewise_polynomial_polyhedral_from_fast_piecewise(h)
sage: h_diag_strip = fn.affine_linear_embedding(matrix([(1,1)]))
sage: minimality_test_multirow(h_diag_strip, f=[1/4,1/4]) # known bug  # Heisenbug #long time  #takes 110 seconds
True
sage: M = matrix([[0,1/4,1/2],[1/4,1/2,3/4],[1/2,3/4,1]])  # q=3
sage: fn = PiecewisePolynomial_polyhedral.from_values_on_group_triangulation(M)
sage: minimality_test_multirow(fn) #long time # f = [2/3, 2/3] # takes 132 seconds
True
sage: PR.<x0,x1>=PolynomialRing(QQ)
sage: fn = PiecewisePolynomial_polyhedral([(Polyhedron(vertices=[(0,0),(2/3,0),(2/3,2/3),(0,2/3)]), (x0+x1)*3/4), (Polyhedron(vertices=[(1,1),(2/3,1),(2/3,2/3),(1,2/3)]), (2-x0-x1)*3/2), (Polyhedron(vertices=[(1,0),(2/3,0),(2/3,2/3),(1,2/3)]), -3/2*x0 + 3/4*x1 + 3/2), (Polyhedron(vertices=[(0,1),(2/3,1),(2/3,2/3),(0,2/3)]), 3/4*x0 - 3/2*x1 + 3/2)], periodic_extension=True)
sage: minimality_test_multirow(fn)   # same function as before, minimality test is much faster when it has less pieces.
True

[2012-Basu-Cornuejols-Koeppe] Unique Minimal Liftings for Simplicial Polytopes - Figure 1-b:

sage: slopes = [[0, -2], [-2, 0], [1, 1]]
sage: subadd_function = subadditive_function_from_slopes(slopes)
sage: minimality_test_multirow(subadd_function, f = [1-1/2, 1-1/2]) 
True
sage: #volume_of_additive_domain(subadd_function)
sage: additive_faces = subadd_function._delta.preimage(0)
sage: len(additive_faces)
69
sage: sum(face.volume() for face in additive_faces)
731/15552

[2012-Basu-Cornuejols-Koeppe] Unique Minimal Liftings for Simplicial Polytopes - Figure 1-a. Unique minimal lifiting property is not satisfied. See “lifting_region.sage”, volume_of_lifting_region(polyhedron, pt, True) returns 41/60, which is less than 1:

sage: polyhedron = Polyhedron(vertices=[[-3/13, 21/13], [1 - 4/10, 3], [3/2, 3/4]])
sage: pt = vector((1/2, 2))
sage: sublin_function = sublinear_function_from_polyhedron_and_point(polyhedron, pt)
sage: subadd_function = trivial_fill_in(sublin_function)
sage: f = mod_Zk(-pt)
sage: minimality_test_multirow(subadd_function, f=f)  #long time #3 mins #violate the symmetry condition.
False
sage: delta = subadd_function._delta #long time
sage: delta.is_non_negative()  # long time
True

3-d example:

sage: M1 =Polyhedron(vertices=[[0, 0, 0] ,[2, 0, 0],[0, 3, 0],[0, 0, 6]])
sage: pt = vector((1/4, 1/2, 3))
sage: sublin_function = sublinear_function_from_polyhedron_and_point(M1, pt)
sage: subadd_function = trivial_fill_in(sublin_function) # long time
sage: f = mod_Zk(-pt)
sage: minimality_test_multirow(subadd_function, f=f) # not tested # never terminates, uses a lot of memory
True
cutgeneratingfunctionology.multirow.mod_Zk(x)
cutgeneratingfunctionology.multirow.multiplication_names

tuple() -> empty tuple tuple(iterable) -> tuple initialized from iterable’s items

If the argument is a tuple, the return value is the same object.

cutgeneratingfunctionology.multirow.piecewise_polynomial_polyhedral_from_fast_piecewise(fn)

Convert a FastPiecewise type function fn to a PiecewisePolynomial_polyhedral type one.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = gmic()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
cutgeneratingfunctionology.multirow.plot_polyhedron_and_f(B, f)
cutgeneratingfunctionology.multirow.ppl_point()

Construct a point.

INPUT:

  • expression – a Linear_Expression or something convertible to it (Variable or integer).
  • divisor – an integer.

OUTPUT:

A new Generator representing the point.

Raises a ValueError` if ``divisor==0.

Examples:

>>> from ppl import Generator, Variable
>>> y = Variable(1)
>>> Generator.point(2*y+7, 3)
point(0/3, 2/3)
>>> Generator.point(y+7, 3)
point(0/3, 1/3)
>>> Generator.point(7, 3)
point()
>>> Generator.point(0, 0)
Traceback (most recent call last):
...
ValueError: PPL::point(e, d):
d == 0.
cutgeneratingfunctionology.multirow.random_point_in_polytope(B)
cutgeneratingfunctionology.multirow.self_orthogonal_binary_codes
cutgeneratingfunctionology.multirow.simplicial_complexes

Catalog of simplicial complexes

There are two main types: manifolds and examples related to graph theory.

For manifolds, there are functions defining the \(n\)-sphere for any \(n\), the torus, \(n\)-dimensional real projective space for any \(n\), the complex projective plane, surfaces of arbitrary genus, and some other manifolds, all as simplicial complexes.

Aside from surfaces, this file also provides functions for constructing some other simplicial complexes: the simplicial complex of not-\(i\)-connected graphs on \(n\) vertices, the matching complex on n vertices, the chessboard complex for an \(n\) by \(i\) chessboard, and others. These provide examples of large simplicial complexes; for example, simplicial_complexes.NotIConnectedGraphs(7,2) has over a million simplices.

All of these examples are accessible by typing simplicial_complexes.NAME, where NAME is the name of the example.

  • BarnetteSphere()
  • BrucknerGrunbaumSphere()
  • ChessboardComplex()
  • ComplexProjectivePlane()
  • DunceHat()
  • K3Surface()
  • KleinBottle()
  • MatchingComplex()
  • MooreSpace()
  • NotIConnectedGraphs()
  • PoincareHomologyThreeSphere()
  • PseudoQuaternionicProjectivePlane()
  • RandomComplex()
  • RandomTwoSphere()
  • RealProjectivePlane()
  • RealProjectiveSpace()
  • RudinBall()
  • ShiftedComplex()
  • Simplex()
  • Sphere()
  • SumComplex()
  • SurfaceOfGenus()
  • Torus()
  • ZieglerBall()

You can also get a list by typing simplicial_complexes. and hitting the TAB key.

EXAMPLES:

sage: S = simplicial_complexes.Sphere(2) # the 2-sphere
sage: S.homology()
{0: 0, 1: 0, 2: Z}
sage: simplicial_complexes.SurfaceOfGenus(3)
Triangulation of an orientable surface of genus 3
sage: M4 = simplicial_complexes.MooreSpace(4)
sage: M4.homology()
{0: 0, 1: C4, 2: 0}
sage: simplicial_complexes.MatchingComplex(6).homology()
{0: 0, 1: Z^16, 2: 0}
cutgeneratingfunctionology.multirow.simplicial_sets

Catalog of simplicial sets

This provides pre-built simplicial sets:

  • the \(n\)-sphere and \(n\)-dimensional real projective space, both (in theory) for any positive integer \(n\). In practice, as \(n\) increases, it takes longer to construct these simplicial sets.
  • the \(n\)-simplex and the horns obtained from it. As \(n\) increases, it takes much longer to construct these simplicial sets, because the number of nondegenerate simplices increases exponentially in \(n\). For example, it is feasible to do simplicial_sets.RealProjectiveSpace(100) since it only has 101 nondegenerate simplices, but simplicial_sets.Simplex(20) is probably a bad idea.
  • \(n\)-dimensional complex projective space for \(n \leq 4\)
  • the classifying space of a finite multiplicative group or monoid
  • the torus and the Klein bottle
  • the point
  • the Hopf map: this is a pre-built morphism, from which one can extract its domain, codomain, mapping cone, etc.

All of these examples are accessible by typing simplicial_sets.NAME, where NAME is the name of the example. Type simplicial_sets.[TAB] for a complete list.

EXAMPLES:

sage: RP10 = simplicial_sets.RealProjectiveSpace(8)
sage: RP10.homology()
{0: 0, 1: C2, 2: 0, 3: C2, 4: 0, 5: C2, 6: 0, 7: C2, 8: 0}

sage: eta = simplicial_sets.HopfMap()
sage: S3 = eta.domain()
sage: S2 = eta.codomain()
sage: S3.wedge(S2).homology()
{0: 0, 1: 0, 2: Z, 3: Z}
cutgeneratingfunctionology.multirow.subadditive_function_from_slopes(slopes)

Return a Zk-periodic subadditive PiecewisePolynomial_polyhedral function whose gradients at the orgin are give by the parameter slopes.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: subadd_function = subadditive_function_from_slopes([(0, 1), (0, -1), (1, 0), (-1, 0)])
sage: subadd_function(10,10)
0
cutgeneratingfunctionology.multirow.subadditivity_slack_delta(h)

Return the subadditivity slack function Delta: (x, y) -> h(x) + h(y) - h(x+y) of the given PiecewisePolynomial_polyhedral function h.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = gmic(2/3)
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: delta = subadditivity_slack_delta(h)
sage: g = delta.plot_projection(show_values_on_vertices=True)
sage: delta.plot(domain=polytopes.hypercube(2)) # not tested
sage: delta(1/2,1/2)
3/2
sage: delta(1/5, 1/5)
0
cutgeneratingfunctionology.multirow.sublinear_function_from_polyhedron_and_point(polyhedron, pt)

Construct sublinear function phi given a full-dimensional polyhedron and an interior point f. Notice that the vector f for the group relaxation problem equals to (- pt) mod Z.

EXAMPLES: [2012-Basu-Cornuejols-Koeppe] Unique Minimal Liftings for Simplicial Polytopes - Figure 1-b:

sage: from cutgeneratingfunctionology.multirow import *
sage: polyhedron = Polyhedron(vertices=[(0,0),(0,2),(2,0)])
sage: pt = (1/2, 1/2)
sage: sublin_function = sublinear_function_from_polyhedron_and_point(polyhedron, pt)
sage: sublin_function.plot(polyhedron - vector(pt)) # not tested
sage: sublin_function((1-1/2, 1-1/2))
1
sage: subadd_function = trivial_fill_in(sublin_function)
sage: subadd_function == subadditive_function_from_slopes(subadd_function.limiting_slopes())
True
sage: subadd_function.plot() #not tested
sage: g = subadd_function.plot_projection(show_values_on_vertices=True)

[2012-Basu-Cornuejols-Koeppe] Unique Minimal Liftings for Simplicial Polytopes - Figure 1-a:

sage: polyhedron = Polyhedron(vertices=[[-3/13, 21/13], [1 - 4/10, 3], [3/2, 3/4]])
sage: pt = (1/2, 2)
sage: sublin_function = sublinear_function_from_polyhedron_and_point(polyhedron, pt)
sage: subadd_function = trivial_fill_in(sublin_function)
cutgeneratingfunctionology.multirow.sublinear_function_from_slopes(slopes)

Return a sublinear PiecewisePolynomial_polyhedral function whose gradients at the orgin are given by the parameter slopes.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: sublin_function = sublinear_function_from_slopes([(0, 1), (0, -1), (1, 0), (-1, 0)])
sage: sublin_function(10,10)
10
sage: sublin_function.plot(domain=polytopes.hypercube(2)) # not tested
cutgeneratingfunctionology.multirow.tests

TESTS:

Test the deprecation warnings:

sage: tests.CompleteMatchings
doctest:warning
...
DeprecationWarning:
Importing CompleteMatchings from here is deprecated. If you need to use it, please import it directly from sage.tests.arxiv_0812_2725
See https://trac.sagemath.org/27337 for details.
<function CompleteMatchings at ...>
sage: tests.modsym
doctest:warning
...
DeprecationWarning:
Importing modsym from here is deprecated. If you need to use it, please import it directly from sage.modular.modsym.tests
See https://trac.sagemath.org/27337 for details.
<class ...sage.modular.modsym.tests.Test...>
cutgeneratingfunctionology.multirow.trivial_fill_in(sublin_function)

Trivial fill-in. Return a Zk-periodic PiecewisePolynomial_polyhedral function.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: sublin_function = sublinear_function_from_slopes([(0, 1), (0, -1), (1, 0), (-1, 0)])
sage: subadd_function = trivial_fill_in(sublin_function)
sage: subadd_function(10,10) == subadd_function(0,0)
True
cutgeneratingfunctionology.multirow.valuations

x.__init__(…) initializes x; see help(type(x)) for signature

cutgeneratingfunctionology.multirow.volume_of_additive_domain(h)

Return the volume of \(x * y \in [0,1]^(2d)\) such that \(h(x) + h(y) = h((x+y) mod Z^d)\) For d=1, the result = (merit index of h) / 2.

EXAMPLES:

sage: from cutgeneratingfunctionology.multirow import *
sage: logging.disable(logging.INFO)
sage: fn = gmic()
sage: h = piecewise_polynomial_polyhedral_from_fast_piecewise(fn)
sage: volume_of_additive_domain(h)
17/50
cutgeneratingfunctionology.multirow.volume_of_lifting_region(B, f=None, show_plots=False, return_plots=False)

Examples:

sage: from cutgeneratingfunctionology.multirow import *
sage: M11 = Polyhedron(vertices=[[-1, 0, 0], [0, 0, 2], [0, 2, 0], [1, 0, 0], [1, 2, 2], [2, 0, 2]])
sage: volume_of_lifting_region(M11)
11/12
sage: B = Polyhedron(vertices=[[-3/13, 21/13], [1 - 4/10, 3], [3/2, 3/4]])
sage: f = B.center()
sage: volume_of_lifting_region(B, f)
1763/2600
sage: B = Polyhedron(vertices=[[-3/5, 6/5], [-3, 0], [3, 0]])
sage: f = (-39/25,27/50)
sage: volume_of_lifting_region(B, f) # long time # 12 s
1
cutgeneratingfunctionology.multirow.volume_of_union_of_polytopes(polyhedra)