Monoids with two generators and one relation

Contents

• The enumeration
• A tour
• Hard instances
• One-off results
• The Baumslag-Gersten group
• Classical results
• Related work

The enumeration

It is easy to produce a list of all two generator, one relation monoids with sum-of-sides ≤ 11:

⟨a, b | u=v⟩

To cut down on the work, I use the fact that a large number of monoid presentations in this list are isomorphic or anti-isomorphic to each other, by some combination of the following:

1. Swapping the two sides of the defining relation, so u=v becomes v=u.
2. Replacing a with b, and vice versa, within both words in the defining relation.
3. Reversing both sides of the relation.

If one instance in such an equivalence class has a finite complete presentation, they all do, so it suffices to only keep one instance from each such equivalence class.

I also skip presentations where the defining relation is the tautology u=u, or of the form u=v with both |u| ≤ 1 and |v| ≤ 1. All such presentations define the free monoid on one or two generators.

After this filtering has taken place, 5944 presentations remain.

A tour

One way to classify the monoids in the enumeration is to split them up into three kinds: groups, cancellative monoids that are not groups, and non-cancellative monoids. Let's do that for the first few presentations in the enumeration.

The first three presentations are of special monoids, meaning the defining relation has the form w=1.

• ⟨a, b | aa=1⟩ is the very first presentation in the enumeration. This is the free product of the two-element group with the natural numbers: ℤ₂ ∗ ℕ. This is not a group, because while a is invertible, b is not. However, it is cancellative, because it is the free product of two cancellative monoids.
• ⟨a, b | ab=1⟩ is the bicyclic monoid. Notice that the element ba is a non-trivial idempotent, meaning that (ba)² = ba. This is the first non-cancellative monoid in the enumeration; if you click the link, you will see a short "proof" in the form of three elements x, y, and z that exhibit a counterexample.
• ⟨a, b | aaa=1⟩ is the free product ℤ₃ ∗ ℕ. It is cancellative.
• ⟨a, b | aab=1⟩ is a non-cancellative special monoid.

We just saw a couple of special monoids that are cancellative but not groups, and a couple that are not cancellative. It doesn't take long for the first groups to appear:

• ⟨a, b | aba=1⟩ is the Abelian group of integers under addition. (Can you see why ba=ab, and what the integer values of a and b must be?)
• ⟨a, b | abaaba=1⟩ is isomorphic to the free product ℤ₂ ∗ ℤ. This group contains ⟨a, b | aa=1⟩ from above as a submonoid.
• ⟨a, b | abaabaaba=1⟩ is isomorphic to the free product ℤ₃ ∗ ℤ. Similar to the previous, but this group now contains ⟨a, b | aaa=1⟩ as a submonoid.

Up to length 11, every special monoid that is not a group has an FCRS over the original alphabet {a, b}. However, among the special monoids that present groups, finding a finite complete rewriting system requires the use of morphocompletion to introduce new auxiliary generators in almost all instances. In fact, the only groups in the one-relation enumeration where completion converges over the original alphabet are the three listed above!

The first group we encounter that requires expanding the generating set has a presentation of length 4:

• ⟨a, b | abba=1⟩ is the fundamental group of the Klein bottle.
• ⟨a, b | aabba=1⟩ is the Trefoil knot group, also known as the Braid group on three strands, B₃.
• ⟨a, b | ababba=1⟩ is isomorphic to the Jantzen monoid, also known as the Baumslag-Solitar group BS(1, -2). A finite complete rewriting system for this group was first constructed in Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group, by adding generators.

To determine if a special one-relation monoid is cancellative, we can look at all cyclic conjugates of the relator w:

• If for some u and v, we have w = uv = 1 but vu ≠ 1, then vu must be a non-trivial idempotent, because (vu)² = v(uv)u = vu. In particular, this means the monoid is not cancellative on either side.
• On the other hand, if every cyclic conjugate of w is equal to the identity, then every generator that appears in the relator is invertible. The monoid is cancellative, because it splits up into a free product of a group and a free monoid, the latter generated by those letters not appearing in w, if any.
• If every generator appears in w, and every generator is also invertible, there is no free monoid factor, and we have a group.

Now, let's move on to non-special monoids. A classic result is that if we're given a one-relation monoid with non-empty relation sides, we can read off cancellativity by looking at the initial and final letters of each side of the defining relation:

• The monoid is left-cancellative if and only if the two sides of the defining relation have different initial letters.
• The monoid is right-cancellative if and only if the two sides of the defining relation have different final letters.

Among those monoids that are not special, the first examples of cancellative and non-cancellative monoids, respectively, are the following:

• ⟨a, b | aa=a⟩ is the first monoid that is not cancellative, and not special.
• ⟨a, b | aa=b⟩ is the first monoid that is cancellative, and not special. This monoid is isomorphic to ℕ.
• ⟨a, b | aba=b⟩ is the first monoid that is cancellative, not special, and not commutative. This is a submonoid of the group ⟨a, b | abba=1⟩.

A number of cancellative one-relation monoids in the enumeration turn out to be submonoids of ⟨a, b | aabba=1⟩, the Braid group B₃ mentioned earlier:

• ⟨a, b | bab=aba⟩ is the submonoid of positive words in B₃, which represent braids obtained by crossings in one direction only. This monoid was discussed in A finite Thue system with decidable word problem and without equivalent finite canonical system, where it was noted that an FCRS can only be obtained by introducing an additional letter.
• ⟨a, b | abba=bab⟩ is another submonoid of the same group with a similar-looking presentation. Here, we must extend the alphabet by introducing two auxiliary generators.
• ⟨a, b | abbba=bab⟩ requires three auxiliary generators.
• ⟨a, b | abbbba=bab⟩ requires four auxiliary generators.
• ⟨a, b | abbbbba=bab⟩ requires five auxiliary generators.
• ⟨a, b | abbbbbba=bab⟩ requires six auxiliary generators.

Other than ℕ and ℤ, only one other one commutative monoid appears in this enumeration:

• ⟨a, b | ba=ab⟩ is isomorphic to ℕ ⊕ ℕ.

There are no finite monoids in this enumeration. If you want to meet monoids that are either finite or commutative, visit the land of two generators, two relations!

Hard instances

I can find a finite complete rewriting system for all presentations in the enumeration except for 4 hard instances. The first one is ⟨a, b | abbaab=ba⟩, with length 8. Unlike with the two generators, two relations enumeration, I have not resolved the status of any of the one-relation hard instances. I only have three basic observations I can share:

1. All four are cancellative, so each one embeds in the group with the same presentation. (See Classical results below.)
2. The first two, ⟨a, b | abbaab=ba⟩ and ⟨a, b | ababaaab=ba⟩, are both submonoids of the same group, and furthermore the first is a submonoid of the second.
3. The fourth hard instance, ⟨a, b | abababa=baab⟩, is a submonoid of B₃.

Note that the first point implies we can still solve the word problem in all four by using Magnus's algorithm, and since I have a finite complete rewriting system for the remaining monoids in the enumeration, I can conclude that every two generator, one relation monoid with sum-of-sides ≤ 11 has a known decidable word problem.

One-off results

I've found finite complete rewriting systems for a handful of one relation monoids that have stumped others, which is perhaps mildly interesting.

(1) The below monoid, due to Victor Maltcev, appears as Exercise 4.10:8 (ii) in An invitation to General Algebra and Universal Constructions by George M. Bergman:

(ii) (Victor Maltcev) Does there exist a normal form or other useful description for the monoid presented by generators a, b and the relation abbab = baabb ? (I do not know the answer.)

The monoid ⟨a, b | abbab=baabb⟩ is anti-isomorphic to ⟨a, b | abaab=aabba⟩, which is FCRS.

(2) The next example is from a talk titled Off with the head! Termination provers and the word problem for 1-relation monoids by Reinis Cirpons:

The 1-relation Thue systems for which the decidability of the word problem is unknown to us: {baabbbaba ↔ a} {baaabaaa ↔ aba}.

The first one is anti-isomorphic to ⟨a, b | ababbbaab=a⟩. The second one is anti-isomorphic to ⟨a, b | aaabaaab=aba⟩. Both are FCRS.

(3) The next example is from The Word Problem for One-Relation Monoids:

We note in passing that the smallest monadic one-relation monoid to which no result in the literature appears to be available to solve the word problem for is ⟨a, b | bababbbabba=a⟩. The author has not found a finite complete rewriting system for this monoid, but has solved the word problem for this monoid by other means.

The monoid presented by ⟨a, b | bababbbabba=a⟩ is FCRS.

(4) In the paper On the Dehn functions of a class of monadic one-relation monoids by the same author as the one-relation monoid survey, he defines this family of monoids:

Π_N := ⟨a,b | baa(ba)^N=a⟩

At one point he asks:

Does Π_N admit a finite complete rewriting system for all N ≥ 2?

While I do not have a rigorous proof of this fact, it appears that one way to construct an FCRS for these monoids is by first adding two letters c=ab and d=ba and then using a specific recursive path order. For example, here are the first few up to N ≤ 7:

• ⟨a, b | baababa=a⟩
• ⟨a, b | baabababa=a⟩
• ⟨a, b | baababababa=a⟩
• ⟨a, b | baabababababa=a⟩
• ⟨a, b | baababababababa=a⟩
• ⟨a, b | baabababababababa=a⟩

Related work: Monoid enthusiast laserbat was able to prove that each monoid in this family is FCRS by a different approach: The Nyberg-Brodda Monoid Family is FCRS.

The Baumslag-Gersten group

The Baumslag-Gersten group is a one-relation group with presentation ⟨a, b | b^-1a^-1bab^-1ab=aa⟩, not a one-relation monoid. (One possible monoid presentation is shown below.)

Every one-relator group has a decidable word problem (see Classical results below). A group's Dehn function in a sense measures the complexity of applying Magnus's algorithm, and the Dehn function of the Baumslag-Gersten group is an iterated tower of exponentials. However, the word problem in the Baumslag-Gersten group can actually be solved in polynomial time, as shown in The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.

This quote appears in the paper titled HNN extensions and stackable groups:

Although it is an open question whether Baumslag’s nonmetabelian group, or any other group with nonelementary Dehn function, can have a finite complete rewriting system, [...]

I claim that the Baumslag-Gersten group is FCRS. The below page shows how to obtain one if we start from this monoid presentation:

• ⟨a, b, c, d | dcbadab=aa, ac=1, ca=1, bd=1, db=1⟩

I do not know the exact time complexity of word reduction in this FCRS. It uses a recursive path order to establish termination, so it is possible that it is something equally bad as the Dehn function.

Here is an input file for kbmag which also reproduces the result:

_RWS := rec (
  isRWS := true,
  ordering := "wreathprod",
  generatorOrder := [e,f,a,c,g,b,d],
  level := [1,1,1,1,2,3,4],
  equations := [
    # group inverses
    [a*c, IdWord],
    [c*a, IdWord],
    [b*d, IdWord],
    [d*b, IdWord],

    # the original relation
    [d*c*b*a*d*a*b, a*a],

    # auxiliary generators
    [e, d*c*b],
    [f, c*e],
    [g, d*a*b]
  ]
);

Classical results

One-relation monoids have a rich theory, which does not extend to the general case of multiple relations. For an in-depth survey, see The Word Problem for One-Relation Monoids by C.F. Brodda. Here is a brief summary of some of the known results:

• A fundamental fact is that the word problem is decidable for all one-relator groups via Magnus's algorithm.
• A one-relation monoid presentation is called special if it has the form ⟨A | w=1⟩, where A is some alphabet.
  • Not every special one-relation monoid is a one-relator group, but the word problem in a special monoid that is not a group can be solved by reducing to the one-relator group case, by constructing the group of units (invertible elements) in the special monoid.
• If both sides of the defining relation are non-empty, we can check cancellativity by looking at the initial and final letter of each side of the defining relation, as described above:
• If the monoid is cancellative on both sides, it embeds in the group with the same presentation. In this case, the word problem again reduces to that for one-relator groups.
• If the monoid is neither left nor right cancellative, a technique known as compression reduces the word problem to that in a shorter one relation monoid presentation.

In the remaining case, where the monoid is cancellative on one side but not the other, the word problem has only been solved for a handful of specific families of one-relation monoids.

It is an open question whether the word problem is decidable for all one-relation monoids. It is also an open question if every one-relation monoid can be presented by a finite complete rewriting system. The latter would of course imply the former, but another theoretical possibility is that every one-relation monoid has a decidable word problem, just not via FCRS.

Related work

A team led by James D. Mitchell at University of St Andrews has been looking at solving the word problem in one relation monoids using a variety of techniques, not just FCRS, with a larger enumeration than mine---they're enumerating all ⟨a, b | u=v⟩ where |u| ≤ 10 and |v| ≤ 10, not just |u|+|v| ≤ 11. Check out their publications:

• Off with the head: termination provers and the word problem for 1-relation monoids
• Certifying the decidability of the word problem in monoids at large