About the census
What is proved in Lean
For each of the 17,282 semigroups of orders one to six in GAP Smallsemi 0.7.2, a theorem: either a finite list of identities is a basis, that is, the identities hold and every identity of the semigroup follows from them by equational logic, or no finite basis exists. The Lean kernel checks every proof, and the proofs use no axioms beyond propositional extensionality, quotient soundness and choice.
- Order six: one theorem collects the 15,973 cases, SemiBase.order6_classification. Sources, build instructions and the checks of the tables: nasqret/semibase-order6, archived on Zenodo as doi:10.5281/zenodo.23109225.
- Orders one to five: a theorem for each of the 1,309 semigroups, from the same campaign, audited in both orientations with the Lean kernel; for order five a second replay read the bases back from Lean. 1,064 of these theorems are in the public repository, which builds them as part of the proofs of order six (1,048 in the very revision the audit checked); the semigroup pages link them. The other 245 are in the repository of the campaign, which is not public.
What is not proved in Lean
- The bases with the fewest identities come from the certified ones by removing identities that follow from the others, with the prover Vampire, and the bases in the fewest variables partly from a search for this census, also checked with Vampire (see below). Their equivalence with the certified bases rests on Vampire's proofs.
- That Smallsemi lists every semigroup of order at most six once, up to isomorphism and anti-isomorphism, is taken from GAP and the literature.
The inclusions between the varieties need no prover: a variety V(S) lies in a variety W exactly when S satisfies a basis of W, and evaluating the certified basis of W in the table of S decides it. So every inclusion among the 681 varieties is decided, and two semigroups generate the same variety exactly when each satisfies the basis of the other.
Duals and smaller generators
Smallsemi counts a semigroup and its opposite, with the transposed table, once. Their varieties are dual: an identity holds in one exactly when it holds read backwards in the other. The census lists both. V[n, k] is the variety generated by [n, k] and V[n, k]ᵒᵖ the variety generated by its transpose, and each variety is named after its generator of least order, then least number, a table before its transpose. So the 681 finitely based varieties come in 141 self-dual ones and 270 dual pairs V[n, k] and V[n, k]ᵒᵖ, and the name of a variety tells the least order of a single semigroup that generates it. The lists of generators and of members of a variety include the transposes, marked ᵒᵖ. Names fixes these names once and for all, with the four varieties without a finite basis, and finds the name of the variety of any table of order at most six.
The 220 varieties generated by a semigroup of order at most five are exactly the varieties of the database of Araújo, Araújo, Cameron, Lee and Raminhos, which also counts duals separately; each variety page gives the name it has there, such as V(5,140). The bases of the database hold in exactly the same tables of order at most six, and their transposes, as the bases of this census (checked by prep/prepare_lower.py).
Bases in few variables
To decide whether a semigroup of order n satisfies an identity in k variables takes about nk evaluations, so for testing membership in a variety a basis in few variables is better than a basis of few identities. Each variety page shows a basis in the fewest variables known, counting the largest number of distinct variables in one identity, and a basis with the fewest identities when it is a different one.
- Lower bounds: if a semigroup T lies outside a variety V but satisfies every identity of V in k variables, then no basis of V uses only k variables. Among the tables of order at most six, T qualifies when every subsemigroup of T generated by k elements lies in V. Beyond them, the finite model builder of Vampire found 138 larger semigroups that satisfy the rules of a complete rewriting system of the free object of V on k generators, and so every identity of V in k variables, without lying in V. The variety pages show the witness of each bound, and check_data.py checks every one by evaluation.
- Upper bounds: the identities of V in k variables are those of the free object of V on k generators, the functions that words define on the generator of V. A complete rewriting system of that free object gives finitely many of them; when Vampire derives a certified basis from some of them, those are a basis, and the redundant ones are removed, again with Vampire.
For 590 of the 681 varieties the two bounds meet, so the basis shown uses as few variables as possible. 73 of the bases in the fewest variables were found by the search, among them the basis x⁴yz ≈ xyz, x³ ≈ y³, xy ≈ yx of V(5,140) in three variables, where the certified basis x³yzt ≈ yzt, xy ≈ yx uses four.
What was known
That every semigroup of order at most five is finitely based was shown by Trahtman (1983), without listing the bases. That exactly four semigroups of order six are not finitely based was shown by Lee, Li and Zhang (2012), and Lee and Zhang (2015) treat the semigroups of order six in detail. For most of the finitely based ones, 14,534 of the 14,600 semigroups of order six without an identity element, finite basability follows there from sufficient conditions, which show that a finite basis exists without writing one down. The census gives an explicit basis for every one of them. Araújo, Araújo, Cameron, Lee and Raminhos (2023) survey the varieties generated by the semigroups of order at most five, with bases.
How the proofs work
Most proofs are transfers. If a semigroup S with a certified basis lies in the variety of a semigroup T, and T satisfies the basis of S, then every identity of T holds in S and so follows from the basis: the basis of S is a basis of T. The transfers differ in how S lies in the variety of T. Each semigroup page names the method of its proof.
| Proof | Order 6 | Orders 1–5 | Idea |
|---|---|---|---|
| transfer from order ≤ 5 | 9,685 | 0 | S has order at most five and is a subsemigroup of this one (the final sweep of these transfers, and earlier waves) |
| embedding transfer | 1,740 | 0 | S is a subsemigroup of this one |
| divisor transfer | 2,728 | 0 | S is a quotient of a subsemigroup of this one |
| direct-power transfer | 589 | 0 | S is a subsemigroup of a direct power of this one |
| subdirect product | 195 | 0 | this semigroup is a subdirect product of two factors; the proof combines their bases |
| inflation | 58 | 25 | this semigroup is an inflation of a smaller one; the proof adapts the basis of that one |
| nilpotent certificate | 26 | 0 | all products of a fixed number of elements are equal to the zero; a generated certificate lists the identities between short words |
| heavy generated transfer | 63 | 0 | transfers of the final sweep that needed much heavier generated proofs |
| other generated proof | 365 | 0 | generated adapters and wrappers of transfers found by the campaign's search |
| individual proof | 13 | 0 | proofs written for one semigroup or a few, among them C₈ |
| family proof | 482 | 166 | one basis, proved once to derive every identity of every semigroup of a family; on each table only the identities of the basis are checked |
| wrapper | 25 | 0 | thin wrappers that restate proofs made earlier |
| no finite basis | 4 | 0 | the four proofs that no finite basis exists |
| transfer | 0 | 1,042 | S, another semigroup of order at most five, lies in the variety of this one and the basis of S holds here |
| direct proof | 0 | 76 | a proof for this semigroup alone, or generated for it |
Conventions
Elements are numbered from 1 as in Smallsemi (from 0 in Lean), and a table gives the product of the row element and the column element. An identity u ≈ v is written with the variables x, y, z, t, … in order of first occurrence and with powers for repeated letters, so x²yx stands for xxyx. [n, k] is the semigroup number k of order n in Smallsemi. A class that is not self-dual stands for two semigroups, a table and its transpose; a basis read backwards is a basis of the transpose, a lemma in Lean (BasisFor.oppositeReversed). The links to Lean point to commit 5804539 of the repository. The variety pages of the first release, named after generators of order six, lead to the new names.
Credits
Created and curated by @nasqret. The Lean proofs were written by language-model agents in a campaign from June to September 2026, described in Proving at Scale for Universal Algebra, MATH-AI workshop, NeurIPS 2026. The reduced bases of order six were computed with Vampire by the bases-min tools of Mikoláš Janota, which also supplied the satisfaction rows over all tables of order at most six. The tables come from GAP Smallsemi by A. Distler and J. D. Mitchell. Thanks to E. W. H. Lee for comments on the bases and on duality. The source of this website is nasqret/semibase-site; the same build is also served at bnaskrecki.faculty.wmi.amu.edu.pl/semigroups6.
References
- J. Araújo, J. P. Araújo, P. J. Cameron, E. W. H. Lee and J. Raminhos, A survey on varieties generated by small semigroups and a companion website, J. Algebra 635 (2023) 698–735; database sgv.dm.fct.unl.pt.
- A. Distler and J. D. Mitchell, Smallsemi, a library of small semigroups, GAP package, version 0.7.2.
- E. W. H. Lee, J. R. Li and W. T. Zhang, Minimal non-finitely based semigroups, Semigroup Forum 85 (2012) 577–580.
- E. W. H. Lee and W. T. Zhang, Finite basis problem for semigroups of order six, LMS J. Comput. Math. 18 (2015) 1–129.
- P. Perkins, Bases for equational theories of semigroups, J. Algebra 11 (1969) 298–314.
- M. V. Sapir, Problems of Burnside type and the finite basis property in varieties of semigroups, Math. USSR-Izv. 30 (1988) 295–314.
- A. N. Trahtman, The finite basis question for semigroups of order less than six, Semigroup Forum 27 (1983) 387–389.
- A. N. Trahtman, Some finite infinitely basable semigroups, Ural. Gos. Univ. Mat. Zap. 14 (1987) 128–131.
- M. V. Volkov, The finite basis problem for finite semigroups, Sci. Math. Jpn. 53 (2001) 171–199.
- W. T. Zhang and Y. F. Luo, A new example of a minimal nonfinitely based semigroup, Bull. Aust. Math. Soc. 84 (2011) 484–491.
Built 2026-10-30 from commit 8f33104fb79f of the website and commit 5804539aee8e20acc0fa8efc01510a3806a0daa8 of the Lean repository.