Aperiodic semigroups contain no nontrivial subgroups

An aperiodic semigroup is a semigroup \(S\) such that for every element \(x \in S\) there exists some \(n \in \mathbb{N}\) such that \(x^n = x^{n+1}\). They are distinguished among semigroups by being the most un-grouplike of all: they contain no non-trivial subgroups! Conversely, if a finite semigroup contains no non-trivial subgroups then it must be aperiodic.

One direction is slightly easier than the other: if a semigroup is aperiodic then any non-trivial subgroup would contain some nontrivial element \(g\), but then \(g\) would satisfy \(g^n = g^{n+1}\) for some \(n \in \mathbb{N}\), whence \(g = 1\) in the subgroup since \(g\) is invertible in the subgroup. But then the subgroup must have been trivial after all.

For the other direction, observe that if there is no \(n \in \mathbb{N}\) such that \(x^n = x^{n+1}\) for some fixed \(x\) then the powers of \(x\) do not “stabilize”, and instead form a cycle \(x^l, \ldots, x^{k-1}\) where \(x^k = x^l\). Now if \(k-l \geq l\) then we are already done since then \(x^{k-l}\) appears on our cycle and \(x^{k-l}x^{l+y} = x^{k+y} = x^{l+y}\) for any \(y \in \mathbb{N}\) so that \(x^{k-l}\) is the group identity and the cyclic group is generated by \(x^{k-l+1}\).

Otherwise, \(k-l < l\) so \(2l > k\) and therefore there exists some \(p\) such that \(l \leq p < k\) and \(x^{2l} = x^p\). But then \(p < 2p < 2k\) so one can consider the element \(x^{2k-p}\) and \(2k-p > k\) so again there exists some \(q\) satisfying \(l \leq q < k\) such that \(x^{2k-p} = x^q\). Finally, considering

\(\qquad x^{l+y}x^q = x^{l+y}x^{2k-p} = x^{l+y}x^{k-p}x^k = x^{2l}x^{k-p}x^y = x^kx^y = x^{l+y}\)

one sees that \(x^q\) is an element on our cycle which is an identity, and the subgroup is generated by \(x^{q+1}\). This does the trick. :-)

There exist infinite semigroups that contain no non-trivial subgroups but are not aperiodic: the obvious first example already works: \((\mathbb{N}, +)\).

Why might we care about this? Well, semigroups have lot to say about the possible behaviors of state machines. State transitions are sometimes irreversible so standard groupoid theory does not apply, but there is still a lot of interesting behavior here. For example, the Maybe monoid corresponds to a little state machine with start state \(s\), end state \(t\), a single arrow \(x: s \to t\), and a loop \(x: t \to t\). One can “enter” the state \(t\) via \(x\), but one cannot escape \(t\) once entered. Most modern public-key cryptography is based on cyclic groups, but are there interesting possibilities for using monogenic semigroups instead? Looking at Diffie-Hellman, the answer seems to be yes.