| Up: | Monoid Zoo |
|---|
When going from two generators to three, the number of presentations at each length increases, as well as the difficulty of the individual instances. Thus, for three generators, my enumeration only covers sum-of-sides ≤ 8:
⟨a, b, c | u1=v1, u2=v2⟩
After filtering for symmetry, 7873 presentations remain.
To avoid duplicating with the two generators and two relations enumeration up to length 8, in the case of three generators I only consider presentations where each of the three generators appears at least once in the defining relations. Of course, many of the monoids end up being isomorphic to those appearing previously anyway!
First, let's take a look at the "easy" cases:
While ℤ is a both a one-relation monoid and a one-relator group, ℤ ⊕ ℤ is an example of a one-relator group which is not a one-relation monoid, so it does not appear in the one-relation monoid enumeration.
Many, but not all, of the non-Abelian groups appearing in this enumeration are also one-relator groups in disguise, because they have the property that one of the three generators appears only once in one of the two relations. This allows one to express this generator in terms of the other two generators, and thus eliminate one of the two relations.
When there is an obvious isomorphism to a one-relator group, I apply Whitehead's algorithm to the relator to find a minimal representative. This shows that many of these one-relator groups are then isomorphic.
Almost all of the monoids in this enumeration are non-commutative. Other than ℤ and ℤ ⊕ ℤ, there are only three other commutative monoids. All three are cancellative, but not groups:
There are no finite monoids in this enumeration, because it takes at least three relations to present a finite monoid generated by three elements.
Recall that cancellativity can be fully resolved for one-relation monoids, while only heuristic methods work in the two generators, two relations enumeration. With three generators and two relations, the situation is similar to the latter case. The majority of monoids here are non-cancellative, with explicit witnesses for non-cancellativity found by the heuristics described at the previous link:
Establishing that a monoid is definitely cancellative is harder. However, with three generators, there is one new method that can decide cancellativity in certain instances.
This criterion is based on the left (or right) graph of a presentation, defined in The Word Problem for One-Relation Monoids. The vertices in each graph are the letters of the alphabet, and the undirected edges correspond to relations. Two letters are joined by an edge in the left graph if there is a relation where one side starts with the first letter and the other side starts with the other. The right graph instead is defined by looking at the last letter of each side of each relation.
If the left graph is acyclic, we say the presentation is left cycle-free, and analogously for right cycle-free. The key fact is that if a monoid has a cycle-free presentation, it embeds in the group with the same presentation.
Notice how when there is only one relation, this generalizes the criterion for cancellativity of one-relation monoids; the left and right graphs only contain a single edge, and this edge is a cycle if and only if it starts and ends with the same letter. The difference is that with multiple relations, the opposite implication is false; a presentation with left or right cycles might still define a cancellative monoid. (Indeed, when there are only two generators and two relations, this criterion doesn't apply at all; all such presentations have left and right cycles, because there is no way to construct an acyclic undirected graph with two vertices and two edges.)
Here is an example of a cancellative monoid with a cycle-free presentation:
The left graph has two edges (a, b), and (b, c), for each of the two defining relations. It is clearly acyclic. The right graph is acyclic as well.
The group with the same presentation is actually isomorphic to the Braid group B3, so this is yet another submonoid of B3.
All in all, for 333 presentations, cancellativity is definitely known, either because the presentation is a free product of cancellative factors, or because it is cycle-free:
There are 330 presentations remaining where cancellativity is not determined automatically:
In this enumeration, I can find a finite complete rewriting system for all but 44 hard instances.
The first hard instance in this enumeration has length only 6.
This remarkable monoid can be viewed as an extension of the bicyclic monoid, ⟨b, c | cb=1⟩, and it contains the latter as a submonoid, so in particular, it is non-cancellative.
Let's briefly review the bicyclic monoid first. If we write ( instead of c and ) instead of b, the defining relation of the bicyclic monoid allows us to introduce and eliminate pairs of matching parentheses, (). The word ((()())) is equivalent to the identity because all parentheses are balanced, while ())(() is not.
Another way to look at the bicyclic monoid is that it models the composition of stack effect annotations in a stack-based language. See Example 16.29 in Compiling Swift Generics.
A key fact is that in the bicyclic monoid, every element is equivalent to one of the form )m(n. There is also a simple formula for the composition of two such elements, which completely defines the monoid operation. Try deriving it! (Or not; it's written down on the Wikipedia page for the bicyclic monoid.)
Furthermore, there is a homomorphism from the bicyclic monoid into the group of integers, which maps )m(n to their difference, n - m.
Now, let's discuss our larger monoid. We have a third generator a and a second relation ba=ac. Let's denote a by | instead. The defining relation becomes )| = |(. It is also easy to see that:
(|=(|()=()|)=|)
Thus, if | appears in a word, we can shift it left or right, flipping ( to ) and vice versa in the process.
In particular, if we start with an arbitrary element of the bicyclic monoid, and adjoin | on the right, we can then shift the | across the entire word, like so:
)m(n|=|(m)n
However, (m)n always collapses; if m < n, this is equivalent to )n-m, and otherwise, (m-n.
In this way, we can see that any word involving | can be further reduced, by first moving all occurrences of | to one side, and then collapsing the rest into a pure power of ( or ), but never both. Indeed, if x and y are elements of the "bicyclic part" of our monoid, that is, they are words that do not contain |, then |x = |y if and only if x and y map to the same integer under the homomorphism mentioned above.
Thus, our monoid is a disjoint union of the bicyclic monoid, together with the two-sided ideal generated by |. The bicyclic monoid structure collapses inside this ideal.
The above leads to an infinite complete rewriting system for this monoid:
() ⇒ 1)| ⇒ |()| ⇒ |(|)n)( ⇒ |)n for all n ≥ 1The irreducible words are precisely
)m(n,
|m(n, and
|m)n, for reasons described above.