Automatic verification of the paper “All Cyclic Group Facets Inject”

Automatic verification of the paper “All Cyclic Group Facets Inject”.

We check cases (a’) and (b’) of the subadditivity proof in the paper [KoppeZ19] through symbolic computation.

sage: import cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof as proof
sage: from cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof import *
sage: logging.disable(logging.INFO) # Suppress output in automatic tests.

sage: setup_case_aprime1_MMM_type_I()
sage: setup_case_aprime2_MMM_type_II()
sage: setup_case_aprime3_MWW()

sage: setup_case_bprime2_MMM()
sage: setup_case_bprime3_MWW_type_I()
sage: setup_case_bprime3_MWW_type_II()
sage: setup_case_bprime4_WMW()
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramBinWord
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramBurge
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramDomino
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramRSK
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramSylvester
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.GrowthDiagramYoungFibonacci
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.LinearCodeFromVectorSpace
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.construct_phi(pi, signs)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.cython_create_local_so
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.delta_IJK(pi, xy)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.game_theory

Catalog Of Games

TESTS:

sage: 'absolute_import' in dir(game_theory)
False
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.interacts

Interacts included with sage

AUTHORS:

  • Harald Schilly (2011-01-16): initial version (#9623) partially based on work by Lauri Ruotsalainen
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.plot_case(phi, pts)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.plot_fun_IJK(pi, phi)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.self_orthogonal_binary_codes
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case(sign1, sign2, sign3, show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_aprime1_MMM_type_I(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_aprime2_MMM_type_II(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_aprime3_MWW(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_aprime_MMM(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_bprime2_MMM(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_bprime3_MWW(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_bprime3_MWW_type_I(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_bprime3_MWW_type_II(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_case_bprime4_WMW(show_plots=False)
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_pi_case_aprime()
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.setup_pi_case_bprime()
cutgeneratingfunctionology.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.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.igp.procedures.injective_2_slope_fill_in_proof.valuations

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