Semigroup elements:

Variety ID:

Order: Sequence: Go!

GAP Smallsemi:

Order: Sequence:

Semigroup Variety Cayley to Presentation

GAP Smallgroup:

Order: Sequence:

Group Variety Cayley to Presentation

Presentation:

Filter varieties:

Multiplication table: Semigroup Variety Cayley to Presentation

Set of identities: Identities (or choose example below) Example: Identity basis of variety V(2,3) Example: Identity basis of variety V(4,42) Example: Identity basis of variety V(5,102) Go!

Presentation:

Relations from last run Copy

Additional user relations
Run!

User's choice Run!

Please wait.

Least number of relations

Please wait.

Run!

Documentation

Introduction

Given a finite semigroup S as input (by specifiying the multiplication table, presentation, GAP smallsemi or smallgroup ID), this site returns:

• The representative in the isomorphism class of S, whose vector S is lexicographically the least;
• A basis for the variety var(S), if var(S) = var(B) for some variety whose identification system is available in the variety database.

The variety database (presently, the identification systems available include all 218 varieties generated by semigroups of order up to five) can also accessed by using the following options:

• Input of the variety ID;
• Search for a variety whose identity basis is equivalent to a given set of identities;
• Return the list of all varieties in the database, implying or implied by a set of user identities, and draw a lattice of the resulting varieties.

The site will also display a list of known varieties generated by semigroups of order 6, and conjectures for the varieties not known.

---

Multiplication table

Enter a multiplication table of a semigroup S. Default elements are 1 to N, being N the order of the set, but base 0 instead of 1 or even specific elements can be defined at the option "Define set elements".
Elements can be separated by "," or spaces, and optionally include "[" and "]" to enclose each line and/or the full multiplication table. If the elements are all single-digit, all or part of the separators can be ommited. For instance, all below input strings can used to input the same multiplication table:

Using the GAP syntax option, it's possible to copy a multiplication table from GAP and paste it here. For example, to get the multiplication table of the group with ID=(5,1) at the SmallGroup GAP package:

gap> MultiplicationTable(SmallGroup(5,1));
[ [ 1, 2, 3, 4, 5 ], [ 2, 3, 4, 5, 1 ], [ 3, 4, 5, 1, 2 ], [ 4, 5, 1, 2, 3 ], [ 5, 1, 2, 3, 4 ] ]

To illustrate the flexibility of this input tool: an expression filled with noise such as gap> MultiplicationTable(SmallGroup(5,1));
/ #, ]1,1]]1 [[\[[2]2[2 ,\}, \begin{array} "3,3[3,=,[,,,

will serve to input the semigroup [1,1,1,2,2,2,3,3,3].

The number of multiplication tables values must be exactly order², otherwise and error will be returned. Only semigroups will be accepted, so the associativity property is checked.

---

Semigroup Variety

After entering a multiplication table or selecting a GAP smallsemi ID, by pressing "Semigroup Variety", the site will give a basis for the variety var(S), if var(S) = var(B) for some variety whose identification system is available in the variety database. Semigroups up to order 100 are accepted, but the representative in the isomorphism class of S, whose vector S is lexicographically the least, will only be computed in case the order of S is less or equal to 10.

Each variety is labeled V(n,k), where n is the order of its primitive generator S and the number of primitive semigroups of order n for other varieties that lexicographically precede S is k-1. For example, the variety var{J} is defined by the identities { x²a ≈ xa, xy² ≈ yx² } and is labeled V(3,3), meaning that its primitive generator - which happens to be J - is of order n=3 and there are k-1=2 semigroups of order 3 with vectors preceding v⃗(J) that are primitive generators for 2 other distinct varieties, namely V(3,1) and V(3,2).

---

Group Variety

After selecting a GAP smallgroup ID, by pressing "Group Variety", the site will give known information about the group variety generated by the chosen group. Semigroups up to order 255 are accepted.

---

Presentation to Cayley

Identify a semigroup by entering its presentation in Prover9 syntax, or choose one of the examples provided.


The following subset of the Prover9 systax is available:

• Variables (with names started by “u”, “v”, “w”, “x”, “y” and “z"). No variables will be allowed at the "relations" part;
• Constants (with names started with a "0" to "9", "a" to "t", and "A" to "Z");
• Binary operation character “*”;
• Equal sign “=”;
• Parentheses “(“ and “)”;
• Each identity must end with a ".".

The presentation is divided in two parts: the theory to follow and one more relations (identities) between initial elements of the set.

Examples:

Consider the following example presentations, and how to enter corresponding theory and relations into the site using Prover9 syntax:

The site will create new elements of the set if necessary to close the multiplication table. If more than 20 elements are reached, an error will be returned.

This website provides a presentation for the primitive generator of the given variety. Conversely, the user can introduce a semigroup as a semigroup presentation in any variety or quasivariety. For instance, while investigating some operators in convexity theory, Kiselman^{ref. 2} considered the semigroup

K₃ = < c,l,m | c²=c, l²=l, m²=m, clc=lc, lcl=lc,
cmc=mc, mcm=mc, lml=ml, mlm=ml >.

In less than a second the website shows that K₃ has 17 elements as a semigroup presentation (as shown in Kiselman^{ref. 2}), 7 elements as a band presentation, and 3 elements as a left cancellative semigroup presentation, etc.

Remarks:

• Even though the monoid K₃1 is finitely based^{ref. 1}, it is unknown if the semigroup K₃ is finitely based and so an identity basis for it is presently absent from the website. In general, it is possible for a finite semigroup S to be non-finitely based even if the monoid S¹ is finitely based ^{ref. 4}.
• However, the website will say that the Kiselman band of order 7 generates the variety of semilattices whose primitive generator is the chain of length two.

---

Cayley to Presentation

After entering a multiplication table or selecting a GAP smallsemi ID, by pressing "Cayley to Presentation", the site will produce a presentation from the semigroup's multiplication table.

---

GAP smallsemi ID

Specify a semigroup by entering the ID defined at GAP package "smallsemi". Orders up to 6 are accepted, with the maximum sequence number corresponding to the number of different semigroups of that order (semigroups considered equivalent if isomorphic or anti-isomorphic):

---

GAP smallgroup ID

Specify a semigroup by entering the ID defined at GAP package "smallgroups". Orders up to 255 are accepted.

---

Define set of elements

Define the elements of S to use at "multiplication table" option. The elements specified will also be used on other outputs of the site.

• Default elements are named 1 to N, with N equal to the order of S.
• Another option is start elements with 0 up to N-1.
• Choose "other" to enter other names for elements. Separate elements with commas or spaces. If an insufficient number of elements is provided, the site will use numbers to name the necessary additional elements.

---

Bands and other special cases

The site deals with special cases like bands, groups and order 6 semigroups thar generate non-finitely based varieties. Multiplication tables of some examples are:

• Bands:


• Band 16: [0000000,0100116,2222222,3333333,0103456,0133456,0100666]
• Band 17: [0000000,0101156,2222222,0123356,0124456,0101656,0106656]
• Band 18: [000000,010145,222222,012345,015445,555555]
• Band 19: [000045,011145,012345,033345,004545,055545]
• Band 20: [00000000,01011567,22222222,01033567,01044567,01055567,01715567,77777777]


• Non-finitely based semigroups of order 6:


• B12: [000000, 000112, 012020, 000335, 012345, 035050]
• A12: [000000, 000112, 012122, 000335, 012345, 035355]
• AG2: [000005, 000125, 012125, 000345, 034345, 555550]
• L: [000000, 000001, 000002, 001031, 002042, 011335]

---

Semilattice decomposition

Based on results from Tamura^{ref. 6}, the companion website finds the largest semilattice decomposition of a given semigroup S into semilattice indecomposable semigroups {S_i | i ∈ Y} and provides the variety generated by each S_i. This tool can be used on a relatively large semigroup S, even when we cannot determine an identity basis for the variety var{S}.

---

Variety by ID

Enter the variety ID (order of primitive generator and sequence number). With the current variety database, accepted sequence numbers are:

---

Identities

Enter one or more identities in Prover9 format (see Section Presentation to Cayley for details), and the site will retrieve the variety whose identity basis is equivalent to the set of identities entered.

Example 1:

Enter the identities "y=y*z. x=x*x." (spaces are optional) and press "Go!".
Variety (2,3), whose identity basis is the identity xy=x, will be displayed, as these sets of identities are equivalent.

Example 2:

After acessing a variety, for instance with "Variety ID" option, it's possible to use the "Copy" button to copy the identity basis into the clipboard, in Prover9 format. Try to past these identities into the "Identities" option, and the site will find the corresponding variety.

---

Testing for equivalent identity bases

Recall that two sets of identities ∑₁ and ∑₂ are equivalent if [∑₁] = [∑₂]. Suppose we have a finite set ∑ of identities and would like to find information about the variety [∑], such as the primitive generator for [∑] and the varieties covered by [∑]. If the variety [∑] happens to be in our database, then much of this information is available. The question is how do we identify [∑] with a variety in the database. A tool was developed that will, by specifying one or more identities in Prover9 format, retrieve the variety whose identity basis is equivalent to ∑.

---

Varieties Filter

Suppose we have some property and want to check which varieties in the database satisfy it. This can be done on the website, using these two distinct functionalities:

• Returns the varieties whose identity basis is implied by the user's assumptions. To use it fill assumptions and press "Prover9" on the left side of the screen to search for proofs, or "Mace4" to search for countermodels.
• Returns the varieties whose identity basis implies the user's goals. To use it fill goals and press "Prover9" on the right of the screen to search for proofs, or "Mace4" to search for countermodels.

Use Prover9 syntax to specify the identities defining assumptions and/or goals. Finalize each identity with the character ".".

It’s not necessary to specify the associativity property, it will be included by default.

Prover9, an automatic theorem prover, and its accompanying program, Mace 4, which look for countermodels, will run simultaneously to check the requested implications.

If the filtered set of varieties has less of 80 varieties, it’s possible to obtain a lattice of those varieties by pressing “Lattice”. The lattice graphic can be removed, getting back to the list, by pressing “List”.

Example:

Get only the varieties from the database whose semigroups are bands. These semigroups satisfy the identity x² ≈ x.

Fill the "Goals:" input field with the following string: "x*x=x.", and click "Prover9" in the right option "Varieties whose identity basis implies the user's goals:"

You should get the 15 varieties below:

Press “Lattice” to get the lattice of these varieties.

Add “x*y=y*x.” to the "Goals" field to get “x*x=x. x*y=y*x.”. Press “Prover9” in the right side of the screen. This time only varieties whose semigroups are commutative bands will be obtained (only 3 varieties in the current database).

---

Conjectures

We have a tool that provides a conjecture for the identity basis of a variety generated by a finite semigroup, using an algorithm that gave the correct result on all semigroups of order up to 5. We used it to find the conjectures available on the website. However, given the computational cost of the algorithm, it cannot be included on the website; anyone interested in using it to find a candidate for an identity basis should contact one of the authors. For an illustrative example, consider the semigroup S with vector

v⃗(S) = [111111,111222,123123,111444,111555,123456].

Lee^{ref. 3} has proved that every subvariety of var{S} is finitely based; in particular, an identity basis for var{S} is

∑₁ = { x³ ≈ x², xyx ≈ x²yx, xyx ≈ xyx², xyzx ≈ xyxzx, xyxy ≈ xy²x, xhyxy ≈ xhy²x,
xyhxy ≈ xyhyx, xhytxy ≈ xhytyx}.

Our algorithm produced the following candidate for an identity basis:

∑₂ = { x³ ≈ x², xyx ≈ x²yx, xyx ≈ xyx², xyxy ≈ xy²x }.

It is routinely verified that the identity systems ∑₁ and ∑₂ define the same variety, so that ∑₂ is indeed an identity basis for var{S}.

Remark: It is clear that ∑₂ is much simpler than ∑₁, but, in fairness, we note that the intention of Lee^{ref. 3} was to find a functional identity basis - rather than a minimal one - to assist in establishing other results.

---

References

[1]: D. N. Ashikhmin, M. V. Volkov, W. T. Zhang, The finite basis problem for Kiselman monoids, Demonstr. Math. 48 (2015), no.4, 475-492.

[2]: C. O. Kiselman, A semigroup of operators in convexity theory, Trans. Amer. Math. Soc. 354 (2002), no. 5, 2035-2053.

[3]: E. W. H. Lee, Hereditarily finitely based monoids of extensive transfor- mations, Algebra Universalis 61 (2009), no. 1, 31-58.

[4]: E. W. H. Lee, Finitely based monoids obtained from non-finitely based semigroups, Univ. Iagel. Acta Math. 51 (2013), 45-49.

[5]: E. W. H. Lee, J. Rhodes, and B. Steinberg, Join irreducible semi- groups, Internat. J. Algebra Comput. 29 (2019), no.7, 1249-1310.

[6]: T. Tamura, Remark on the smallest semilattice congruence, Semigroup Forum 5 (1972), no. 1, 277-282.