# Semigroup analogue to the classification of finite simple groups?

Is there a semigroup analogue to the classification of finite simple groups?

If so what are some of the major results?

Classification of Finite Simple Groups

One of my semigroup equation sequences in OEIS, g(f(x)) = f(f(f(x)))

• For programmers out there, finite semigroups are a collection of functions on a finite set. Finite groups are collections of permutation functions. Classifying sets of permutation functions took decades, en.wikipedia.org/wiki/Classification_of_finite_simple_groups – Chad Brewbaker Jan 27 '17 at 19:14
• A quick google search came up with this: arsmathematica.net/2012/04/25/… – David Hill Jan 27 '17 at 19:24
• @davidHill I saw that, going to take a deeper look at the underlying paper. I have a bunch of semigroup equations in OEIS. I should see which ones are Moufang. oeis.org/A239750 – Chad Brewbaker Jan 27 '17 at 19:30
• @DavidHill In my group work, decomposition into prime order permutations has been most useful. In Semigroup land you can factor by self composition. Treelike outside with a groupish center and idempotent in the middle. – Chad Brewbaker Jan 27 '17 at 19:39

In group theory, the classification of finite simple groups reduces the classification of all finite groups to the so-called extension problem. Roughly speaking, the extension problem consists in describing a group in terms of a particular normal subgroup and quotient group.

There is no semigroup analogue to this theory, but a weaker classification scheme exists. A semigroup $S$ divides a semigroup $T$ if $S$ is a homomorphic image of a subsemigroup of $T$. The Krohn–Rhodes theorem states that every finite semigroup $S$ divides a wreath product of finite simple groups, each dividing $S$, and copies of the 3-element monoid $\{1, a, b\}$ in which $aa = ba = a$ and $ab = bb = b$.

The best reference on this theory is the (advanced) book

[1] J. Rhodes, B. Steinberg. The $q$-theory of finite semigroups. Springer Verlag (2008). ISBN 978-0-387-09780-0.

• If you set edges from $a$ to $a^{i}$ for all elements of the semigroup, you get a set of connected components surrounding every idempotent. In the middle they have a group-like structure that is all cycles. In the outside you have trees that lead into the center. The 3 element monoid corresponds to the tree-like elements on the outside? – Chad Brewbaker Feb 1 '17 at 15:16
• I am sorry, but I don't understand your sentence "In the outside you have trees that lead into the center". First of all, what does "outside" mean in this context? Anyway, in the 3-element monoid of my answer, all elements are idempotent, and thus your graph consists of three loops $1 \to 1$, $a \to a$ and $b \to b$. – J.-E. Pin Feb 2 '17 at 10:13
• Ah ok. Under iteration, $a^i$ -> $a^{i+1}$, you get forgetful/reluctant functions which then enter a cycle. The paths before the cycle form paths on a tree if you zoom out. – Chad Brewbaker Feb 2 '17 at 21:31

In semigroup theory, the term "simple" has a specialized meaning. If you interpret it to mean that the semigroup has no quotients other than itself and the trivial semigroup, then there is a complete classification. In semigroup theory, these are called "congruence-free semigroups". (In universal algebra, "simple" means no non-trivial quotients.)

There is a complete classification of finite congruence-free semigroups. They are either:

1. a two-element semigroup
2. a finite simple group
3. a completely 0-simple semigroup. Most of these are not congruence-free, but the ones that are have a complete description. They are basically paramatrized by 0-1 matrices.

The proof that a congruence-free semigroup that is not covered by cases 1 or 2 must have a zero is sketched in this Math Overflow answer. (A zero is just an element $0$ such that $0a = a0 = 0$ for all $a$.)

I don't know of a great online source for the third case. This preprint states the theorem, with reference, as Theorem 3.1, but it's not the main subject of the paper.