SemiBase

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.

What is not proved in Lean

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.

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.

ProofOrder 6Orders 1–5Idea
transfer from order ≤ 59,6850S has order at most five and is a subsemigroup of this one (the final sweep of these transfers, and earlier waves)
embedding transfer1,7400S is a subsemigroup of this one
divisor transfer2,7280S is a quotient of a subsemigroup of this one
direct-power transfer5890S is a subsemigroup of a direct power of this one
subdirect product1950this semigroup is a subdirect product of two factors; the proof combines their bases
inflation5825this semigroup is an inflation of a smaller one; the proof adapts the basis of that one
nilpotent certificate260all products of a fixed number of elements are equal to the zero; a generated certificate lists the identities between short words
heavy generated transfer630transfers of the final sweep that needed much heavier generated proofs
other generated proof3650generated adapters and wrappers of transfers found by the campaign's search
individual proof130proofs written for one semigroup or a few, among them C₈
family proof482166one basis, proved once to derive every identity of every semigroup of a family; on each table only the identities of the basis are checked
wrapper250thin wrappers that restate proofs made earlier
no finite basis40the four proofs that no finite basis exists
transfer01,042S, another semigroup of order at most five, lies in the variety of this one and the basis of S holds here
direct proof076a 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

Built 2026-10-30 from commit 8f33104fb79f of the website and commit 5804539aee8e20acc0fa8efc01510a3806a0daa8 of the Lean repository.