Finite monoids¶

class sage.categories.finite_monoids.FiniteMonoids(base_category)[source]¶

Bases: CategoryWithAxiom_singleton

The category of finite (multiplicative) monoids.

A finite monoid is a finite sets endowed with an associative unital binary operation $*$ .

EXAMPLES:

Sage

sage: FiniteMonoids()
Category of finite monoids
sage: FiniteMonoids().super_categories()
[Category of monoids, Category of finite semigroups]

Python

>>> from sage.all import *
>>> FiniteMonoids()
Category of finite monoids
>>> FiniteMonoids().super_categories()
[Category of monoids, Category of finite semigroups]

Sage Live

FiniteMonoids()
FiniteMonoids().super_categories()

class ElementMethods[source]¶

Bases: object

pseudo_order()[source]¶

Return the pair $[k, j]$ with $k$ minimal and $0 \leq j < k$ such that self^k == self^j.

Note that $j$ is uniquely determined.

EXAMPLES:

Sage

sage: M = FiniteMonoids().example(); M
An example of a finite multiplicative monoid: the integers modulo 12

sage: x = M(2)
sage: [ x^i for i in range(7) ]
[1, 2, 4, 8, 4, 8, 4]
sage: x.pseudo_order()
[4, 2]

sage: x = M(3)
sage: [ x^i for i in range(7) ]
[1, 3, 9, 3, 9, 3, 9]
sage: x.pseudo_order()
[3, 1]

sage: x = M(4)
sage: [ x^i for i in range(7) ]
[1, 4, 4, 4, 4, 4, 4]
sage: x.pseudo_order()
[2, 1]

sage: x = M(5)
sage: [ x^i for i in range(7) ]
[1, 5, 1, 5, 1, 5, 1]
sage: x.pseudo_order()
[2, 0]

Python

>>> from sage.all import *
>>> M = FiniteMonoids().example(); M
An example of a finite multiplicative monoid: the integers modulo 12

>>> x = M(Integer(2))
>>> [ x**i for i in range(Integer(7)) ]
[1, 2, 4, 8, 4, 8, 4]
>>> x.pseudo_order()
[4, 2]

>>> x = M(Integer(3))
>>> [ x**i for i in range(Integer(7)) ]
[1, 3, 9, 3, 9, 3, 9]
>>> x.pseudo_order()
[3, 1]

>>> x = M(Integer(4))
>>> [ x**i for i in range(Integer(7)) ]
[1, 4, 4, 4, 4, 4, 4]
>>> x.pseudo_order()
[2, 1]

>>> x = M(Integer(5))
>>> [ x**i for i in range(Integer(7)) ]
[1, 5, 1, 5, 1, 5, 1]
>>> x.pseudo_order()
[2, 0]

Sage Live

M = FiniteMonoids().example(); M
x = M(2)
[ x^i for i in range(7) ]
x.pseudo_order()
x = M(3)
[ x^i for i in range(7) ]
x.pseudo_order()
x = M(4)
[ x^i for i in range(7) ]
x.pseudo_order()
x = M(5)
[ x^i for i in range(7) ]
x.pseudo_order()

Todo

more appropriate name? see, for example, Jean-Eric Pin’s lecture notes on semigroups.

class ParentMethods[source]¶

Bases: object

nerve()[source]¶

The nerve (classifying space) of this monoid.

OUTPUT:

the nerve $B G$ (if $G$ denotes this monoid), as a simplicial set. The $k$ -dimensional simplices of this object are indexed by products of $k$ elements in the monoid:

a_{1} * a_{2} * \dots * a_{k}

The $0$ -th face of this is obtained by deleting $a_{1}$ , and the $k$ -th face is obtained by deleting $a_{k}$ . The other faces are obtained by multiplying elements: the 1st face is

(a 1 * a_{2}) * \dots * a_{k}

and so on. See Wikipedia article Nerve_(category_theory), which describes the construction of the nerve as a simplicial set.

A simplex in this simplicial set will be degenerate if in the corresponding product of $k$ elements, one of those elements is the identity. So we only need to keep track of the products of non-identity elements. Similarly, if a product $a_{i - 1} a_{i}$ is the identity element, then the corresponding face of the simplex will be a degenerate simplex.

EXAMPLES:

The nerve (classifying space) of the cyclic group of order 2 is infinite-dimensional real projective space.

Sage

sage: Sigma2 = groups.permutation.Cyclic(2)                             # needs sage.groups
sage: BSigma2 = Sigma2.nerve()                                          # needs sage.graphs sage.groups
sage: BSigma2.cohomology(4, base_ring=GF(2))                            # needs sage.graphs sage.groups sage.modules
Vector space of dimension 1 over Finite Field of size 2

Python

>>> from sage.all import *
>>> Sigma2 = groups.permutation.Cyclic(Integer(2))                             # needs sage.groups
>>> BSigma2 = Sigma2.nerve()                                          # needs sage.graphs sage.groups
>>> BSigma2.cohomology(Integer(4), base_ring=GF(Integer(2)))                            # needs sage.graphs sage.groups sage.modules
Vector space of dimension 1 over Finite Field of size 2

Sage Live

Sigma2 = groups.permutation.Cyclic(2)                             # needs sage.groups
BSigma2 = Sigma2.nerve()                                          # needs sage.graphs sage.groups
BSigma2.cohomology(4, base_ring=GF(2))                            # needs sage.graphs sage.groups sage.modules

The $k$ -simplices of the nerve are named after the chains of $k$ non-unit elements to be multiplied. The group $Σ_{2}$ has two elements, written () (the identity element) and (1,2) in Sage. So the 1-cells and 2-cells in $B Σ_{2}$ are:

Sage

sage: BSigma2.n_cells(1)                                                # needs sage.graphs sage.groups
[(1,2)]
sage: BSigma2.n_cells(2)                                                # needs sage.graphs sage.groups
[(1,2) * (1,2)]

Python

>>> from sage.all import *
>>> BSigma2.n_cells(Integer(1))                                                # needs sage.graphs sage.groups
[(1,2)]
>>> BSigma2.n_cells(Integer(2))                                                # needs sage.graphs sage.groups
[(1,2) * (1,2)]

Sage Live

BSigma2.n_cells(1)                                                # needs sage.graphs sage.groups
BSigma2.n_cells(2)                                                # needs sage.graphs sage.groups

Another construction of the group, with different names for its elements:

Sage

sage: # needs sage.groups sage.rings.number_field
sage: C2 = groups.misc.MultiplicativeAbelian([2])
sage: BC2 = C2.nerve()
sage: BC2.n_cells(0)
[1]
sage: BC2.n_cells(1)
[f]
sage: BC2.n_cells(2)
[f * f]

Python

>>> from sage.all import *
>>> # needs sage.groups sage.rings.number_field
>>> C2 = groups.misc.MultiplicativeAbelian([Integer(2)])
>>> BC2 = C2.nerve()
>>> BC2.n_cells(Integer(0))
[1]
>>> BC2.n_cells(Integer(1))
[f]
>>> BC2.n_cells(Integer(2))
[f * f]

Sage Live

# needs sage.groups sage.rings.number_field
C2 = groups.misc.MultiplicativeAbelian([2])
BC2 = C2.nerve()
BC2.n_cells(0)
BC2.n_cells(1)
BC2.n_cells(2)

With mod $p$ coefficients, $B Σ_{p}$ should have its first nonvanishing homology group in dimension $p$ :

Sage

sage: Sigma3 = groups.permutation.Symmetric(3)                          # needs sage.groups
sage: BSigma3 = Sigma3.nerve()                                          # needs sage.graphs sage.groups
sage: BSigma3.homology(range(4), base_ring=GF(3))                       # needs sage.graphs sage.groups
{0: Vector space of dimension 0 over Finite Field of size 3,
 1: Vector space of dimension 0 over Finite Field of size 3,
 2: Vector space of dimension 0 over Finite Field of size 3,
 3: Vector space of dimension 1 over Finite Field of size 3}

Python

>>> from sage.all import *
>>> Sigma3 = groups.permutation.Symmetric(Integer(3))                          # needs sage.groups
>>> BSigma3 = Sigma3.nerve()                                          # needs sage.graphs sage.groups
>>> BSigma3.homology(range(Integer(4)), base_ring=GF(Integer(3)))                       # needs sage.graphs sage.groups
{0: Vector space of dimension 0 over Finite Field of size 3,
 1: Vector space of dimension 0 over Finite Field of size 3,
 2: Vector space of dimension 0 over Finite Field of size 3,
 3: Vector space of dimension 1 over Finite Field of size 3}

Sage Live

Sigma3 = groups.permutation.Symmetric(3)                          # needs sage.groups
BSigma3 = Sigma3.nerve()                                          # needs sage.graphs sage.groups
BSigma3.homology(range(4), base_ring=GF(3))                       # needs sage.graphs sage.groups

Note that we can construct the $n$ -skeleton for $B Σ_{2}$ for relatively large values of $n$ , while for $B Σ_{3}$ , the complexes get large pretty quickly:

Sage

sage: # needs sage.graphs sage.groups
sage: Sigma2.nerve().n_skeleton(14)
Simplicial set with 15 non-degenerate simplices
sage: BSigma3 = Sigma3.nerve()
sage: BSigma3.n_skeleton(3)
Simplicial set with 156 non-degenerate simplices
sage: BSigma3.n_skeleton(4)
Simplicial set with 781 non-degenerate simplices

Python

>>> from sage.all import *
>>> # needs sage.graphs sage.groups
>>> Sigma2.nerve().n_skeleton(Integer(14))
Simplicial set with 15 non-degenerate simplices
>>> BSigma3 = Sigma3.nerve()
>>> BSigma3.n_skeleton(Integer(3))
Simplicial set with 156 non-degenerate simplices
>>> BSigma3.n_skeleton(Integer(4))
Simplicial set with 781 non-degenerate simplices

Sage Live

# needs sage.graphs sage.groups
Sigma2.nerve().n_skeleton(14)
BSigma3 = Sigma3.nerve()
BSigma3.n_skeleton(3)
BSigma3.n_skeleton(4)

Finally, note that the classifying space of the order $p$ cyclic group is smaller than that of the symmetric group on $p$ letters, and its first homology group appears earlier:

Sage

sage: # needs sage.graphs sage.groups sage.rings.number_field
sage: C3 = groups.misc.MultiplicativeAbelian([3])
sage: list(C3)
[1, f, f^2]
sage: BC3 = C3.nerve()
sage: BC3.n_cells(1)
[f, f^2]
sage: BC3.n_cells(2)
[f * f, f * f^2, f^2 * f, f^2 * f^2]
sage: len(BSigma3.n_cells(2))
25
sage: len(BC3.n_cells(3))
8
sage: len(BSigma3.n_cells(3))
125
sage: BC3.homology(range(4), base_ring=GF(3))
{0: Vector space of dimension 0 over Finite Field of size 3,
 1: Vector space of dimension 1 over Finite Field of size 3,
 2: Vector space of dimension 1 over Finite Field of size 3,
 3: Vector space of dimension 1 over Finite Field of size 3}
sage: BC5 = groups.permutation.Cyclic(5).nerve()
sage: BC5.homology(range(4), base_ring=GF(5))
{0: Vector space of dimension 0 over Finite Field of size 5,
 1: Vector space of dimension 1 over Finite Field of size 5,
 2: Vector space of dimension 1 over Finite Field of size 5,
 3: Vector space of dimension 1 over Finite Field of size 5}

Python

>>> from sage.all import *
>>> # needs sage.graphs sage.groups sage.rings.number_field
>>> C3 = groups.misc.MultiplicativeAbelian([Integer(3)])
>>> list(C3)
[1, f, f^2]
>>> BC3 = C3.nerve()
>>> BC3.n_cells(Integer(1))
[f, f^2]
>>> BC3.n_cells(Integer(2))
[f * f, f * f^2, f^2 * f, f^2 * f^2]
>>> len(BSigma3.n_cells(Integer(2)))
25
>>> len(BC3.n_cells(Integer(3)))
8
>>> len(BSigma3.n_cells(Integer(3)))
125
>>> BC3.homology(range(Integer(4)), base_ring=GF(Integer(3)))
{0: Vector space of dimension 0 over Finite Field of size 3,
 1: Vector space of dimension 1 over Finite Field of size 3,
 2: Vector space of dimension 1 over Finite Field of size 3,
 3: Vector space of dimension 1 over Finite Field of size 3}
>>> BC5 = groups.permutation.Cyclic(Integer(5)).nerve()
>>> BC5.homology(range(Integer(4)), base_ring=GF(Integer(5)))
{0: Vector space of dimension 0 over Finite Field of size 5,
 1: Vector space of dimension 1 over Finite Field of size 5,
 2: Vector space of dimension 1 over Finite Field of size 5,
 3: Vector space of dimension 1 over Finite Field of size 5}

Sage Live

# needs sage.graphs sage.groups sage.rings.number_field
C3 = groups.misc.MultiplicativeAbelian([3])
list(C3)
BC3 = C3.nerve()
BC3.n_cells(1)
BC3.n_cells(2)
len(BSigma3.n_cells(2))
len(BC3.n_cells(3))
len(BSigma3.n_cells(3))
BC3.homology(range(4), base_ring=GF(3))
BC5 = groups.permutation.Cyclic(5).nerve()
BC5.homology(range(4), base_ring=GF(5))

rhodes_radical_congruence(base_ring=None)[source]¶

Return the Rhodes radical congruence of the semigroup.

The Rhodes radical congruence is the congruence induced on S by the map $S \to k S \to k S / r a d k S$ with k a field.

INPUT:

base_ring – (default: $Q$ ) a field

OUTPUT:

A list of couples (m, n) with $m \neq n$ in the lexicographic order for the enumeration of the monoid self.

EXAMPLES:

Sage

sage: M = Monoids().Finite().example()
sage: M.rhodes_radical_congruence()                                     # needs sage.modules
[(0, 6), (2, 8), (4, 10)]

sage: # needs sage.combinat sage.groups sage.modules
sage: from sage.monoids.hecke_monoid import HeckeMonoid
sage: H3 = HeckeMonoid(SymmetricGroup(3))
sage: H3.repr_element_method(style='reduced')
sage: H3.rhodes_radical_congruence()
[([1, 2], [2, 1]), ([1, 2], [1, 2, 1]), ([2, 1], [1, 2, 1])]

Python

>>> from sage.all import *
>>> M = Monoids().Finite().example()
>>> M.rhodes_radical_congruence()                                     # needs sage.modules
[(0, 6), (2, 8), (4, 10)]

>>> # needs sage.combinat sage.groups sage.modules
>>> from sage.monoids.hecke_monoid import HeckeMonoid
>>> H3 = HeckeMonoid(SymmetricGroup(Integer(3)))
>>> H3.repr_element_method(style='reduced')
>>> H3.rhodes_radical_congruence()
[([1, 2], [2, 1]), ([1, 2], [1, 2, 1]), ([2, 1], [1, 2, 1])]

Sage Live

M = Monoids().Finite().example()
M.rhodes_radical_congruence()                                     # needs sage.modules
# needs sage.combinat sage.groups sage.modules
from sage.monoids.hecke_monoid import HeckeMonoid
H3 = HeckeMonoid(SymmetricGroup(3))
H3.repr_element_method(style='reduced')
H3.rhodes_radical_congruence()

By Maschke’s theorem, every group algebra over $Q$ is semisimple hence the Rhodes radical of a group must be trivial:

Sage

sage: SymmetricGroup(3).rhodes_radical_congruence()                     # needs sage.combinat sage.groups sage.modules
[]
sage: DihedralGroup(10).rhodes_radical_congruence()                     # needs sage.groups sage.modules
[]

Python

>>> from sage.all import *
>>> SymmetricGroup(Integer(3)).rhodes_radical_congruence()                     # needs sage.combinat sage.groups sage.modules
[]
>>> DihedralGroup(Integer(10)).rhodes_radical_congruence()                     # needs sage.groups sage.modules
[]

Sage Live

SymmetricGroup(3).rhodes_radical_congruence()                     # needs sage.combinat sage.groups sage.modules
DihedralGroup(10).rhodes_radical_congruence()                     # needs sage.groups sage.modules

REFERENCES:

[Rho69]