Semigroups#

class sage.categories.semigroups.Semigroups(base_category)#

Bases: CategoryWithAxiom_singleton

The category of (multiplicative) semigroups.

A semigroup is an associative magma, that is a set endowed with a multiplicative binary operation \(*\) which is associative (see Wikipedia article Semigroup).

The operation \(*\) is not required to have a neutral element. A semigroup for which such an element exists is a monoid.

EXAMPLES:

sage: C = Semigroups(); C
Category of semigroups
sage: C.super_categories()
[Category of magmas]
sage: C.all_super_categories()
[Category of semigroups, Category of magmas,
 Category of sets, Category of sets with partial maps, Category of objects]
sage: C.axioms()
frozenset({'Associative'})
sage: C.example()
An example of a semigroup: the left zero semigroup
class Algebras(category, *args)#

Bases: AlgebrasCategory

class ParentMethods#

Bases: object

algebra_generators()#

The generators of this algebra, as per MagmaticAlgebras.ParentMethods.algebra_generators().

They correspond to the generators of the semigroup.

EXAMPLES:

sage: M = FiniteSemigroups().example(); M
An example of a finite semigroup:
the left regular band generated by ('a', 'b', 'c', 'd')
sage: M.semigroup_generators()
Family ('a', 'b', 'c', 'd')
sage: M.algebra(ZZ).algebra_generators()                            # needs sage.modules
Family (B['a'], B['b'], B['c'], B['d'])
gen(i=0)#

Return the i-th generator of self.

EXAMPLES:

sage: A = GL(3, GF(7)).algebra(ZZ)                                  # needs sage.modules
sage: A.gen(0)                                                      # needs sage.groups sage.libs.pari sage.modules
[3 0 0]
[0 1 0]
[0 0 1]
gens()#

Return the generators of self.

EXAMPLES:

sage: a, b = SL2Z.algebra(ZZ).gens(); a, b                          # needs sage.groups sage.modules
([ 0 -1]
 [ 1  0],
 [1 1]
 [0 1])
sage: 2*a + b                                                       # needs sage.groups sage.modules
2*[ 0 -1]
  [ 1  0]
+
[1 1]
[0 1]
ngens()#

Return the number of generators of self.

EXAMPLES:

sage: SL2Z.algebra(ZZ).ngens()                                      # needs sage.groups sage.modules
2
sage: DihedralGroup(4).algebra(RR).ngens()                          # needs sage.groups sage.modules
2
product_on_basis(g1, g2)#

Product, on basis elements, as per MagmaticAlgebras.WithBasis.ParentMethods.product_on_basis().

The product of two basis elements is induced by the product of the corresponding elements of the group.

EXAMPLES:

sage: S = FiniteSemigroups().example(); S
An example of a finite semigroup:
 the left regular band generated by ('a', 'b', 'c', 'd')
sage: A = S.algebra(QQ)                                             # needs sage.modules
sage: a, b, c, d = A.algebra_generators()                           # needs sage.modules
sage: a * b + b * d * c * d                                         # needs sage.modules
B['ab'] + B['bdc']
regular_representation(side='left')#

Return the regular representation of self.

INPUT:

  • side – (default: "left") whether this is the "left" or "right" regular representation

EXAMPLES:

sage: # needs sage.groups
sage: G = groups.permutation.Dihedral(4)
sage: A = G.algebra(QQ)                                             # needs sage.modules
sage: V = A.regular_representation()                                # needs sage.modules
sage: V == G.regular_representation(QQ)                             # needs sage.modules
True
trivial_representation(side='twosided')#

Return the trivial representation of self.

INPUT:

  • side – ignored

EXAMPLES:

sage: # needs sage.groups
sage: G = groups.permutation.Dihedral(4)
sage: A = G.algebra(QQ)                                             # needs sage.modules
sage: V = A.trivial_representation()                                # needs sage.modules
sage: V == G.trivial_representation(QQ)                             # needs sage.modules
True
extra_super_categories()#

Implement the fact that the algebra of a semigroup is indeed a (not necessarily unital) algebra.

EXAMPLES:

sage: Semigroups().Algebras(QQ).extra_super_categories()
[Category of semigroups]
sage: Semigroups().Algebras(QQ).super_categories()
[Category of associative algebras over Rational Field,
 Category of magma algebras over Rational Field]
Aperiodic#

alias of AperiodicSemigroups

class CartesianProducts(category, *args)#

Bases: CartesianProductsCategory

extra_super_categories()#

Implement the fact that a Cartesian product of semigroups is a semigroup.

EXAMPLES:

sage: Semigroups().CartesianProducts().extra_super_categories()
[Category of semigroups]
sage: Semigroups().CartesianProducts().super_categories()
[Category of semigroups, Category of Cartesian products of magmas]
class ElementMethods#

Bases: object

Finite#

alias of FiniteSemigroups

FinitelyGeneratedAsMagma#

alias of FinitelyGeneratedSemigroups

HTrivial#

alias of HTrivialSemigroups

JTrivial#

alias of JTrivialSemigroups

LTrivial#

alias of LTrivialSemigroups

class ParentMethods#

Bases: object

cayley_graph(side='right', simple=False, elements=None, generators=None, connecting_set=None)#

Return the Cayley graph for this finite semigroup.

INPUT:

  • side – “left”, “right”, or “twosided”: the side on which the generators act (default:”right”)

  • simple – boolean (default:False): if True, returns a simple graph (no loops, no labels, no multiple edges)

  • generators – a list, tuple, or family of elements of self (default: self.semigroup_generators())

  • connecting_set – alias for generators; deprecated

  • elements – a list (or iterable) of elements of self

OUTPUT:

EXAMPLES:

We start with the (right) Cayley graphs of some classical groups:

sage: # needs sage.graphs sage.groups
sage: D4 = DihedralGroup(4); D4
Dihedral group of order 8 as a permutation group
sage: G = D4.cayley_graph()
sage: show(G, color_by_label=True, edge_labels=True)                    # needs sage.plot
sage: A5 = AlternatingGroup(5); A5
Alternating group of order 5!/2 as a permutation group
sage: G = A5.cayley_graph()
sage: G.show3d(color_by_label=True, edge_size=0.01,                     # needs sage.plot
....:          edge_size2=0.02, vertex_size=0.03)
sage: G.show3d(vertex_size=0.03,        # long time (less than a minute), needs sage.plot
....:          edge_size=0.01, edge_size2=0.02,
....:          vertex_colors={(1,1,1): G.vertices(sort=True)},
....:          bgcolor=(0,0,0), color_by_label=True,
....:          xres=700, yres=700, iterations=200)
sage: G.num_edges()
120

sage: # needs sage.combinat sage.graphs sage.groups
sage: w = WeylGroup(['A', 3])
sage: d = w.cayley_graph(); d
Digraph on 24 vertices
sage: d.show3d(color_by_label=True, edge_size=0.01, vertex_size=0.03)   # needs sage.plot

Alternative generators may be specified:

sage: # needs sage.graphs sage.groups
sage: G = A5.cayley_graph(generators=[A5.gens()[0]])
sage: G.num_edges()
60
sage: g = PermutationGroup([(i + 1, j + 1)
....:                       for i in range(5)
....:                       for j in range(5) if j != i])
sage: g.cayley_graph(generators=[(1,2), (2,3)])
Digraph on 120 vertices

If elements is specified, then only the subgraph induced and those elements is returned. Here we use it to display the Cayley graph of the free monoid truncated on the elements of length at most 3:

sage: # needs sage.combinat sage.graphs
sage: M = Monoids().example(); M
An example of a monoid:
 the free monoid generated by ('a', 'b', 'c', 'd')
sage: elements = [M.prod(w)
....:             for w in sum((list(Words(M.semigroup_generators(), k))
....:                           for k in range(4)), [])]
sage: G = M.cayley_graph(elements=elements)
sage: G.num_verts(), G.num_edges()
(85, 84)
sage: G.show3d(color_by_label=True, edge_size=0.001, vertex_size=0.01)  # needs sage.plot

We now illustrate the side and simple options on a semigroup:

sage: S = FiniteSemigroups().example(alphabet=('a', 'b'))
sage: g = S.cayley_graph(simple=True)                                   # needs sage.graphs
sage: g.vertices(sort=True)                                             # needs sage.graphs
['a', 'ab', 'b', 'ba']
sage: g.edges(sort=True)                                                # needs sage.graphs
[('a', 'ab', None), ('b', 'ba', None)]
sage: g = S.cayley_graph(side="left", simple=True)                      # needs sage.graphs
sage: g.vertices(sort=True)                                             # needs sage.graphs
['a', 'ab', 'b', 'ba']
sage: g.edges(sort=True)                                                # needs sage.graphs
[('a', 'ba', None), ('ab', 'ba', None), ('b', 'ab', None),
('ba', 'ab', None)]
sage: g = S.cayley_graph(side="twosided", simple=True)                  # needs sage.graphs
sage: g.vertices(sort=True)                                             # needs sage.graphs
['a', 'ab', 'b', 'ba']
sage: g.edges(sort=True)                                                # needs sage.graphs
[('a', 'ab', None), ('a', 'ba', None), ('ab', 'ba', None),
('b', 'ab', None), ('b', 'ba', None), ('ba', 'ab', None)]
sage: g = S.cayley_graph(side="twosided")                               # needs sage.graphs
sage: g.vertices(sort=True)                                             # needs sage.graphs
['a', 'ab', 'b', 'ba']
sage: g.edges(sort=True)                                                # needs sage.graphs
[('a', 'a', (0, 'left')), ('a', 'a', (0, 'right')), ('a', 'ab', (1, 'right')), ('a', 'ba', (1, 'left')), ('ab', 'ab', (0, 'left')), ('ab', 'ab', (0, 'right')), ('ab', 'ab', (1, 'right')), ('ab', 'ba', (1, 'left')), ('b', 'ab', (0, 'left')), ('b', 'b', (1, 'left')), ('b', 'b', (1, 'right')), ('b', 'ba', (0, 'right')), ('ba', 'ab', (0, 'left')), ('ba', 'ba', (0, 'right')), ('ba', 'ba', (1, 'left')), ('ba', 'ba', (1, 'right'))]
sage: s1 = SymmetricGroup(1); s = s1.cayley_graph()                     # needs sage.graphs sage.groups
sage: s.vertices(sort=False)                                            # needs sage.graphs sage.groups
[()]

Todo

  • Add more options for constructing subgraphs of the Cayley graph, handling the standard use cases when exploring large/infinite semigroups (a predicate, generators of an ideal, a maximal length in term of the generators)

  • Specify good default layout/plot/latex options in the graph

  • Generalize to combinatorial modules with module generators / operators

AUTHORS:

  • Bobby Moretti (2007-08-10)

  • Robert Miller (2008-05-01): editing

  • Nicolas M. Thiery (2008-12): extension to semigroups, side, simple, and elements options, …

magma_generators()#

An alias for semigroup_generators().

EXAMPLES:

sage: S = Semigroups().example("free"); S
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')
sage: S.magma_generators()
Family ('a', 'b', 'c', 'd')
sage: S.semigroup_generators()
Family ('a', 'b', 'c', 'd')
prod(args)#

Return the product of the list of elements args inside self.

EXAMPLES:

sage: S = Semigroups().example("free")
sage: S.prod([S('a'), S('b'), S('c')])
'abc'
sage: S.prod([])
Traceback (most recent call last):
...
AssertionError: Cannot compute an empty product in a semigroup
regular_representation(base_ring=None, side='left')#

Return the regular representation of self over base_ring.

  • side – (default: "left") whether this is the "left" or "right" regular representation

EXAMPLES:

sage: G = groups.permutation.Dihedral(4)                                # needs sage.groups
sage: G.regular_representation()                                        # needs sage.groups
Left Regular Representation of Dihedral group of order 8
 as a permutation group over Integer Ring
semigroup_generators()#

Return distinguished semigroup generators for self.

OUTPUT: a family

This method is optional.

EXAMPLES:

sage: S = Semigroups().example("free"); S
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')
sage: S.semigroup_generators()
Family ('a', 'b', 'c', 'd')
subsemigroup(generators, one=None, category=None)#

Return the multiplicative subsemigroup generated by generators.

INPUT:

  • generators – a finite family of elements of self, or a list, iterable, … that can be converted into one (see Family).

  • one – a unit for the subsemigroup, or None.

  • category – a category

This implementation lazily constructs all the elements of the semigroup, and the right Cayley graph relations between them, and uses the latter as an automaton.

See AutomaticSemigroup for details.

EXAMPLES:

sage: R = IntegerModRing(15)
sage: M = R.subsemigroup([R(3), R(5)]); M                               # needs sage.combinat
A subsemigroup of (Ring of integers modulo 15) with 2 generators
sage: M.list()                                                          # needs sage.combinat
[3, 5, 9, 0, 10, 12, 6]

By default, \(M\) is just in the category of subsemigroups:

sage: M in Semigroups().Subobjects()                                    # needs sage.combinat
True

In the following example, we specify that \(M\) is a submonoid of the finite monoid \(R\) (it shares the same unit), and a group by itself:

sage: M = R.subsemigroup([R(-1)],                                       # needs sage.combinat
....:     category=Monoids().Finite().Subobjects() & Groups()); M
A submonoid of (Ring of integers modulo 15) with 1 generators
sage: M.list()                                                          # needs sage.combinat
[1, 14]
sage: M.one()                                                           # needs sage.combinat
1

In the following example, \(M\) is a group; however, its unit does not coincide with that of \(R\), so \(M\) is only a subsemigroup, and we need to specify its unit explicitly:

sage: M = R.subsemigroup([R(5)],                                        # needs sage.combinat
....:     category=Semigroups().Finite().Subobjects() & Groups()); M
Traceback (most recent call last):
...
ValueError: For a monoid which is just a subsemigroup,
the unit should be specified

sage: # needs sage.groups
sage: M = R.subsemigroup([R(5)], one=R(10),
....:     category=Semigroups().Finite().Subobjects() & Groups()); M
A subsemigroup of (Ring of integers modulo 15) with 1 generators
sage: M in Groups()
True
sage: M.list()
[10, 5]
sage: M.one()
10

Todo

  • Fix the failure in TESTS by providing a default implementation of __invert__ for finite groups (or even finite monoids).

  • Provide a default implementation of one for a finite monoid, so that we would not need to specify it explicitly?

trivial_representation(base_ring=None, side='twosided')#

Return the trivial representation of self over base_ring.

INPUT:

  • base_ring – (optional) the base ring; the default is \(\ZZ\)

  • side – ignored

EXAMPLES:

sage: G = groups.permutation.Dihedral(4)                                # needs sage.groups
sage: G.trivial_representation()                                        # needs sage.groups
Trivial representation of Dihedral group of order 8
 as a permutation group over Integer Ring
class Quotients(category, *args)#

Bases: QuotientsCategory

class ParentMethods#

Bases: object

semigroup_generators()#

Return semigroup generators for self by retracting the semigroup generators of the ambient semigroup.

EXAMPLES:

sage: S = FiniteSemigroups().Quotients().example().semigroup_generators() # todo: not implemented
example()#

Return an example of quotient of a semigroup, as per Category.example().

EXAMPLES:

sage: Semigroups().Quotients().example()
An example of a (sub)quotient semigroup: a quotient of the left zero semigroup
RTrivial#

alias of RTrivialSemigroups

class SubcategoryMethods#

Bases: object

Aperiodic()#

Return the full subcategory of the aperiodic objects of self.

A (multiplicative) semigroup \(S\) is aperiodic if for any element \(s\in S\), the sequence \(s,s^2,s^3,...\) eventually stabilizes.

In terms of variety, this can be described by the equation \(s^\omega s = s\).

EXAMPLES:

sage: Semigroups().Aperiodic()
Category of aperiodic semigroups

An aperiodic semigroup is \(H\)-trivial:

sage: Semigroups().Aperiodic().axioms()
frozenset({'Aperiodic', 'Associative', 'HTrivial'})

In the finite case, the two notions coincide:

sage: Semigroups().Aperiodic().Finite() is Semigroups().HTrivial().Finite()
True
HTrivial()#

Return the full subcategory of the \(H\)-trivial objects of self.

Let \(S\) be (multiplicative) semigroup. Two elements of \(S\) are in the same \(H\)-class if they are in the same \(L\)-class and in the same \(R\)-class.

The semigroup \(S\) is \(H\)-trivial if all its \(H\)-classes are trivial (that is of cardinality \(1\)).

EXAMPLES:

sage: C = Semigroups().HTrivial(); C
Category of h trivial semigroups
sage: Semigroups().HTrivial().Finite().example()
NotImplemented
JTrivial()#

Return the full subcategory of the \(J\)-trivial objects of self.

Let \(S\) be (multiplicative) semigroup. The \(J\)-preorder \(\leq_J\) on \(S\) is defined by:

\[x\leq_J y \qquad \Longleftrightarrow \qquad x \in SyS\]

The \(J\)-classes are the equivalence classes for the associated equivalence relation. The semigroup \(S\) is \(J\)-trivial if all its \(J\)-classes are trivial (that is of cardinality \(1\)), or equivalently if the \(J\)-preorder is in fact a partial order.

EXAMPLES:

sage: C = Semigroups().JTrivial(); C
Category of j trivial semigroups

A semigroup is \(J\)-trivial if and only if it is \(L\)-trivial and \(R\)-trivial:

sage: sorted(C.axioms())
['Associative', 'HTrivial', 'JTrivial', 'LTrivial', 'RTrivial']
sage: Semigroups().LTrivial().RTrivial()
Category of j trivial semigroups

For a commutative semigroup, all three axioms are equivalent:

sage: Semigroups().Commutative().LTrivial()
Category of commutative j trivial semigroups
sage: Semigroups().Commutative().RTrivial()
Category of commutative j trivial semigroups
LTrivial()#

Return the full subcategory of the \(L\)-trivial objects of self.

Let \(S\) be (multiplicative) semigroup. The \(L\)-preorder \(\leq_L\) on \(S\) is defined by:

\[x\leq_L y \qquad \Longleftrightarrow \qquad x \in Sy\]

The \(L\)-classes are the equivalence classes for the associated equivalence relation. The semigroup \(S\) is \(L\)-trivial if all its \(L\)-classes are trivial (that is of cardinality \(1\)), or equivalently if the \(L\)-preorder is in fact a partial order.

EXAMPLES:

sage: C = Semigroups().LTrivial(); C
Category of l trivial semigroups

A \(L\)-trivial semigroup is \(H\)-trivial:

sage: sorted(C.axioms())
['Associative', 'HTrivial', 'LTrivial']
RTrivial()#

Return the full subcategory of the \(R\)-trivial objects of self.

Let \(S\) be (multiplicative) semigroup. The \(R\)-preorder \(\leq_R\) on \(S\) is defined by:

\[x\leq_R y \qquad \Longleftrightarrow \qquad x \in yS\]

The \(R\)-classes are the equivalence classes for the associated equivalence relation. The semigroup \(S\) is \(R\)-trivial if all its \(R\)-classes are trivial (that is of cardinality \(1\)), or equivalently if the \(R\)-preorder is in fact a partial order.

EXAMPLES:

sage: C = Semigroups().RTrivial(); C
Category of r trivial semigroups

An \(R\)-trivial semigroup is \(H\)-trivial:

sage: sorted(C.axioms())
['Associative', 'HTrivial', 'RTrivial']
class Subquotients(category, *args)#

Bases: SubquotientsCategory

The category of subquotient semi-groups.

EXAMPLES:

sage: Semigroups().Subquotients().all_super_categories()
[Category of subquotients of semigroups,
 Category of semigroups,
 Category of subquotients of magmas,
 Category of magmas,
 Category of subquotients of sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

[Category of subquotients of semigroups,
 Category of semigroups,
 Category of subquotients of magmas,
 Category of magmas,
 Category of subquotients of sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]
example()#

Returns an example of subquotient of a semigroup, as per Category.example().

EXAMPLES:

sage: Semigroups().Subquotients().example()
An example of a (sub)quotient semigroup: a quotient of the left zero semigroup
Unital#

alias of Monoids

example(choice='leftzero', **kwds)#

Returns an example of a semigroup, as per Category.example().

INPUT:

  • choice – str (default: ‘leftzero’). Can be either ‘leftzero’ for the left zero semigroup, or ‘free’ for the free semigroup.

  • **kwds – keyword arguments passed onto the constructor for the chosen semigroup.

EXAMPLES:

sage: Semigroups().example(choice='leftzero')
An example of a semigroup: the left zero semigroup
sage: Semigroups().example(choice='free')
An example of a semigroup: the free semigroup generated by ('a', 'b', 'c', 'd')
sage: Semigroups().example(choice='free', alphabet=('a','b'))
An example of a semigroup: the free semigroup generated by ('a', 'b')