Semigroups¶
-
class
sage.categories.semigroups.
Semigroups
(base_category)¶ Bases:
sage.categories.category_with_axiom.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
TESTS:
sage: TestSuite(C).run()
-
class
Algebras
(category, *args)¶ Bases:
sage.categories.algebra_functor.AlgebrasCategory
TESTS:
sage: TestSuite(Semigroups().Algebras(QQ)).run() sage: TestSuite(Semigroups().Finite().Algebras(QQ)).run()
-
class
ParentMethods
¶ -
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() Finite family {0: B['a'], 1: B['b'], 2: B['c'], 3: B['d']}
-
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) sage: a,b,c,d = A.algebra_generators() sage: a * b + b * d * c * d 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: G = groups.permutation.Dihedral(4) sage: A = G.algebra(QQ) sage: V = A.regular_representation() sage: V == G.regular_representation(QQ) True
-
trivial_representation
(side='twosided')¶ Return the trivial representation of
self
.INPUT:
side
– ignored
EXAMPLES:
sage: G = groups.permutation.Dihedral(4) sage: A = G.algebra(QQ) sage: V = A.trivial_representation() sage: V == G.trivial_representation(QQ) True
-
-
Semigroups.Algebras.
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]
-
class
-
Semigroups.
Aperiodic
¶ alias of
AperiodicSemigroups
-
class
Semigroups.
CartesianProducts
(category, *args)¶ Bases:
sage.categories.cartesian_product.CartesianProductsCategory
TESTS:
sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory sage: class FooBars(CovariantConstructionCategory): ....: _functor_category = "FooBars" ....: _base_category_class = (Category,) sage: Category.FooBars = lambda self: FooBars.category_of(self) sage: C = FooBars(ModulesWithBasis(ZZ)) sage: C Category of foo bars of modules with basis over Integer Ring sage: C.base_category() Category of modules with basis over Integer Ring sage: latex(C) \mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}}) sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module sage: TestSuite(C).run()
-
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
Semigroups.
ElementMethods
¶
-
Semigroups.
Finite
¶ alias of
FiniteSemigroups
-
Semigroups.
FinitelyGeneratedAsMagma
¶ alias of
FinitelyGeneratedSemigroups
-
Semigroups.
HTrivial
¶ alias of
HTrivialSemigroups
-
Semigroups.
JTrivial
¶ alias of
JTrivialSemigroups
-
Semigroups.
LTrivial
¶ alias of
LTrivialSemigroups
-
class
Semigroups.
ParentMethods
¶ -
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 ofself
(default:self.semigroup_generators()
)connecting_set
– alias forgenerators
; deprecatedelements
– a list (or iterable) of elements ofself
OUTPUT:
EXAMPLES:
We start with the (right) Cayley graphs of some classical 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) 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, edge_size2=0.02, vertex_size=0.03) sage: G.show3d(vertex_size=0.03, edge_size=0.01, edge_size2=0.02, vertex_colors={(1,1,1):G.vertices()}, bgcolor=(0,0,0), color_by_label=True, xres=700, yres=700, iterations=200) # long time (less than a minute) sage: G.num_edges() 120 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)
Alternative generators may be specified:
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: 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)
We now illustrate the
side
andsimple
options on a semigroup:sage: S = FiniteSemigroups().example(alphabet=('a','b')) sage: g = S.cayley_graph(simple=True) sage: g.vertices() ['a', 'ab', 'b', 'ba'] sage: g.edges() [('a', 'ab', None), ('b', 'ba', None)]
sage: g = S.cayley_graph(side="left", simple=True) sage: g.vertices() ['a', 'ab', 'b', 'ba'] sage: g.edges() [('a', 'ba', None), ('ab', 'ba', None), ('b', 'ab', None), ('ba', 'ab', None)]
sage: g = S.cayley_graph(side="twosided", simple=True) sage: g.vertices() ['a', 'ab', 'b', 'ba'] sage: g.edges() [('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") sage: g.vertices() ['a', 'ab', 'b', 'ba'] sage: g.edges() [('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(); s.vertices() [()]
TESTS:
sage: SymmetricGroup(2).cayley_graph(side="both") Traceback (most recent call last): ... ValueError: option 'side' must be 'left', 'right' or 'twosided'
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
, andelements
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
insideself
.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
overbase_ring
.side
– (default:"left"
) whether this is the"left"
or"right"
regular representation
EXAMPLES:
sage: G = groups.permutation.Dihedral(4) sage: G.regular_representation() 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 ofself
, or a list, iterable, ... that can be converted into one (seeFamily
).one
– a unit for the subsemigroup, orNone
.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 A subsemigroup of (Ring of integers modulo 15) with 2 generators sage: M.list() [3, 5, 9, 0, 10, 12, 6]
By default, \(M\) is just in the category of subsemigroups:
sage: M in Semigroups().Subobjects() 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)], ....: category=Monoids().Finite().Subobjects() & Groups()); M A submonoid of (Ring of integers modulo 15) with 1 generators sage: M.list() [1, 14] sage: M.one() 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 explictly:
sage: M = R.subsemigroup([R(5)], ....: 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: 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
TESTS:
sage: TestSuite(M).run() Failure in _test_inverse: Traceback (most recent call last): ... The following tests failed: _test_inverse
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
overbase_ring
.INPUT:
base_ring
– (optional) the base ring; the default is \(\ZZ\)side
– ignored
EXAMPLES:
sage: G = groups.permutation.Dihedral(4) sage: G.trivial_representation() Trivial representation of Dihedral group of order 8 as a permutation group over Integer Ring
-
-
class
Semigroups.
Quotients
(category, *args)¶ Bases:
sage.categories.quotients.QuotientsCategory
TESTS:
sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory sage: class FooBars(CovariantConstructionCategory): ....: _functor_category = "FooBars" ....: _base_category_class = (Category,) sage: Category.FooBars = lambda self: FooBars.category_of(self) sage: C = FooBars(ModulesWithBasis(ZZ)) sage: C Category of foo bars of modules with basis over Integer Ring sage: C.base_category() Category of modules with basis over Integer Ring sage: latex(C) \mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}}) sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module sage: TestSuite(C).run()
-
class
ParentMethods
¶ -
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
-
-
Semigroups.Quotients.
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
-
class
-
Semigroups.
RTrivial
¶ alias of
RTrivialSemigroups
-
class
Semigroups.
SubcategoryMethods
¶ -
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
TESTS:
sage: C = Monoids().Aperiodic().Finite() sage: TestSuite(C).run()
See also
TESTS:
sage: TestSuite(C).run() sage: Rings().Aperiodic.__module__ 'sage.categories.semigroups'
-
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
See also
TESTS:
sage: TestSuite(C).run() sage: Rings().HTrivial.__module__ 'sage.categories.semigroups' sage: C # todo: not implemented Category of H-trivial semigroups
-
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
See also
TESTS:
sage: TestSuite(C).run() sage: Rings().JTrivial.__module__ 'sage.categories.semigroups' sage: C # todo: not implemented Category of 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']
See also
TESTS:
sage: TestSuite(C).run() sage: Rings().LTrivial.__module__ 'sage.categories.semigroups' sage: C # todo: not implemented Category of L-trivial semigroups
-
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']
See also
TESTS:
sage: TestSuite(C).run() sage: Rings().RTrivial.__module__ 'sage.categories.semigroups' sage: C # todo: not implemented Category of R-trivial semigroups
-
-
class
Semigroups.
Subquotients
(category, *args)¶ Bases:
sage.categories.subquotients.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
-
-
Semigroups.
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')
-
class