Identity bases of the semigroups of orders one to six
A census of the 17,282 semigroups of orders one to six, counted up to isomorphism and anti-isomorphism as in GAP Smallsemi: 1,309 of order at most five and 15,973 of order six. All of them except four have a finite identity basis, and every case is proved in Lean: an explicit basis for each of the 17,278 finitely based semigroups, for most of which only the existence of a finite basis was known before, and a proof for the other four that no finite basis exists.
Explore
- Browse all 17,282 semigroups and filter them by order, structure, basis and proof.
- Varieties: the 681 varieties the finitely based semigroups and their transposes generate, as a list or as an interactive graph of their inclusions.
- Names: the rule that names the 685 varieties, fixed once and for all, and the name of the variety of any Cayley table of order at most six.
- No finite basis: L, B₂¹, A₂ᵍ and A₂¹, and why no finite set of identities suffices.
- A random semigroup.
Worth a look
- [6, 3842] C₈, the semigroup C₈ of Lee and Zhang: finitely based, two table entries away from the nonfinitely based L.
- [5, 415] B₂ and [5, 868] A₂: finitely based; adjoining an identity to either gives a semigroup of order six without a finite basis.
- V[5, 540]: the variety V(5,140) of the database of Araújo et al., with a basis in three variables where the certified one uses four.
- [6, 12824]: the largest proof, 333,599 lines of Lean that the proof of no other class uses.
- [6, 2582]: the longest certified basis, 3,513 identities, which reduce to 3.
- V[6, 2771]: the variety whose basis with the fewest identities is longest, with 31 identities.
- V[4, 9]: the variety with the most generators, 4,336 semigroups of order at most six.
How many variables do the bases need?
The 681 finitely based varieties by the number of variables of their basis in the fewest variables: the largest number of distinct variables in one identity, which decides how long it takes to check whether a semigroup lies in the variety. For 590 varieties no basis in fewer variables exists. 73 of the bases in the fewest variables were found by a search for this census, beyond the certified bases and their reductions.
On each page
For each semigroup: the Cayley table and its structure; the basis of its variety in the fewest variables and the basis with the fewest identities, and the basis certified in Lean; the Lean theorem and the size of its proof; the variety it generates and the one its transpose generates, with the varieties directly above and below and the other semigroups that generate it; and the tables that differ from it in one or two entries. About says what is proved in Lean and what is not.