Monoids with two generators and two relations

Contents

• The enumeration
• Finite monoids
  • Finite monoids of length 10
  • Finite monoids of length 11
• Commutative monoids
• Cancellativity
• Hard instances
  • ⟨a, b | aaa=a, abba=bb⟩
  • ⟨a, b | aba=aa, baa=aab⟩

The enumeration

Similar to the one-relation case, it is easy to generate an exhaustive list of all monoid presentations with two generators, two relations, and sum-of-sides ≤ 11:

⟨a, b | u₁=v₁, u₂=v₂⟩

In addition to the symmetries described in the one-relation case, there is one more way to fold together trivially-isomorphic presentations:

1. Swapping the two defining relations, so ⟨a, b | u₁=v₁, u₂=v₂⟩ becomes ⟨a, b | u₂=v₂, u₁=v₁⟩.

After filtering for symmetry, 28,551 presentations remain.

Finite monoids

A notable change from one relations to two is the appearance of finite monoids.

Of the 28,551 presentations in this enumeration, 18,868 present finite monoids. I've classified them up to (anti-)isomorphism, and I believe exactly 556 unique finite monoids appear. Some are quite small:

• ⟨a, b | aa=a, ab=1⟩ is the first presentation of the trivial group with one element, but there are 2030 more.
• ⟨a, b | aa=1, ab=1⟩ is the first presentation of the group with two elements, but there are 1990 more.
• ⟨a, b | aa=a, aaa=b⟩ is the other possible monoid structure with two elements; not nearly as popular, with only 46 other duplicates in the enumeration.
• ⟨a, b | ab=a, ba=b⟩ is the smallest non-commutative monoid in the enumeration, with three elements.

Some nice and short presentations of various classic finite groups then appear:

• ⟨a, b | abba=b, baba=1⟩ is a presentation of the symmetric group of degree 3, with 6 elements. (An interesting fact is that while this is the only non-Abelian group of order 6 up to isomorphism, there are many more monoids that are not groups, for example the slightly ridiculous ⟨a, b | ab=a, bbbb=ba⟩.)
• ⟨a, b | aba=b, aabb=1⟩ is a presentation of the Quaternion group with 8 elements. Can you see which elements can work as i, j, k, and -1? (There are multiple possible assignments, of course.)
• ⟨a, b | bab=aa, bbb=1⟩ is a finite monoid with 27 elements, but the group with the same presentation is SL(2, 3). (The monoid has three more elements, the powers of b.)

Finite monoids of length 10

Here is a "Busy Beaver"-esque problem: what is the largest finite monoid you can present with two generators, two relations, and length N? (The Busy Beaver problem asks, given a Turing machine with m states and n symbols, what is the longest possible running time among all such machines that halt?)

The length 10 maximum is 1083 elements, achieved by ⟨a, b | aaa=1, abbbba=b⟩. The rewriting system consists of 11 rules, and there is an even simpler explicit description of this monoid:

• All of the large finite monoids in the enumeration are closely related to the group with the same presentation, and have a few more elements than the group.
• The group with the same presentation as the 1083 element monoid has 1080 elements, and it's isomorphic to the direct product ℤ₉ ⨯ SL(2, 5).
• One possible isomorphism maps the generators a and b to the following elements, a := (3, A),    b := (1, B) where: A :=

  0	1
  4	4

  ,    B :=

  0	2
  2	3

  
  
• In the group, b⁹⁰ = 1, so every element can be expressed as a word involving b, but in the monoid, we have b⁹¹ = b instead.
• Thus, the monoid with this presentation has three more elements than the group: 1, a, and a². This is actually an inverse monoid.
• It follows that every element of this monoid can be represented as a triple, consisting of an integer, a 2x2 integer matrix, and a boolean flag that is set for pure powers of a.
• The monoid operation is defined to perform the group operation on the first two components of each triple, and "Boolean and" on the third component.
• Here is an explicit realization of the monoid operation in the form of a short Swift program, to verify that the two generators satisfy the defining relations and generate a monoid of the correct size.

Finite monoids of length 11

The length 11 maximum (so far, see below) is 2,361,964 elements, achieved by ⟨a, b | aaba=bab, bbbb=1⟩. The rewriting system consists of 112,169 rules.

• Knuth-Bendix completion struggles with this presentation due to an explosion in the number of intermediate rules, so I solve it with Todd-Coxeter congruence enumeration instead. (For this reason, this is the only monoid in the enumeration whose rewriting system does not have a certificate. However, I have checked the cardinality of the monoid with other Todd-Coxeter implementations.)
• Congruence enumeration constructs the Cayley graph for a finite monoid. The "standardization" algorithm described in Computation with Finitely Presented Groups by Charles C. Sims can then very quickly produce a finite complete rewriting system.
• I have yet to come up with an explicit description of this monoid, if one even exists.
• The monoid has 4 more elements, the pure powers of b, than the group with the same presentation.

Another difficult presentation is ⟨a, b | aaa=1, ababbb=ba⟩. This is a finite monoid with only 336 elements.

• Here, the situation is reversed. I have not been able to get Todd-Coxeter to finish with this presentation, only Knuth-Bendix.
• The certificate shown on the linked page requires over 70,000 "lemmas" to show that each rule in the rewriting system of 216 rules is a consequence of the defining relations.
• The group with the same presentation is similarly difficult to resolve. This group has 333 elements, and it is actually just the semidirect product ℤ₃₇ ⋊ ℤ₉. The difficulty here is with the specific presentation of the group. This group presentation was previously discussed in a MathOverflow question.
• Monoid enthusiast laserbat discovered an interesting connection between this group and a family of groups studied previously: The Gilbert-Howie group H(9,7) has 37 elements.

The finiteness of one of the hard instances is still an open question:

⟨a, b | aaa=1, babbb=aba⟩

This monoid has 3 more elements than the group with the same presentation, because b⁸ is a central idempotent in the monoid. The possibility remains that the above presents a finite monoid with more than 2,361,964 elements.

The group with the same presentation was coincidentally the subject of another MathOverflow question. At the time of writing, that question is unsolved. Resolving it would also resolve the status of the monoid.

It is undecidable if a monoid presentation defines a finite monoid, and it appears that with two generators and two relations, the difficulty of establishing finiteness increases rapidly with length.

Commutative monoids

Another distinct feature of this enumeration is that it contains a large number of commutative monoids. A monoid with two generators being commutative is another way to say that ba=ab. In some instances that present commutative monoids, this identity appears directly as one of the two defining relations, while in others, it is a consequence of the defining relations.

If you add the condition that a finitely-generated commutative monoid is also a group, you get a finitely-generated Abelian group, and its structure is completely described by the Fundamental Theorem of Finitely Generated Abelian Groups. Those finitely-generated commutative monoids that are not groups are more intricate in comparison, but they are still somewhat "easier" than arbitrary finitely-presented monoids.

Namely, in the commutative case, being finitely presented is the same as being finitely generated (Redei's Theorem), and furthermore, all finitely generated commutative monoids have a decidable word problem.

There are several approaches to solving the word problem in a commutative monoid; the direct equivalent of the Knuth-Bendix completion algorithm is called Buchberger's algorithm. Unlike Knuth-Bendix completion, Buchberger's algorithm always terminates. Buchberger's algorithm outputs a Gröbner basis, which is entirely analogous to a finite complete rewriting system.

In a commutative monoid, two words are always equivalent if one can be obtained from the other by permuting the letters, so instead of arbitrary words, we can think of elements as being represented by monomials in the generators. For example if a and b are arbitrary generators in some commutative monoid, then aabbb, bbbaa, and babab are all equivalent to a²b³. Given a monomial, we repeatedly apply reduction rules from our Gröbner basis to reduce it to a normal form. Two monomials then represent the same element if they have identical normal forms.

If you click on a link to the page for a commutative monoid, you will see a "Commutative structure" section, which shows a Gröbner basis for the monoid, along with various invariants computed from this basis. Each monoid's page also shows a so-called Staircase diagram for the monoid, which I will reproduce for a series of examples below.

⟨a, b | ba=ab, aba=aab⟩

The simplest possible staircase diagram belongs to the following monoid:

• ⟨a, b | ba=ab, aba=aab⟩ is a two-relation presentation of the free commutative monoid on two generators, ℕ ⊕ ℕ.

Notice how the second relation is redundant, being a consequence of the first. The Gröbner basis for this monoid has no relations at all, because ba=ab is implied. For this reason, the staircase diagram is trivial, so the name "staircase" won't make sense yet.

Every element in this monoid is equivalent to a^mbⁿ, for some unique m, n. Imagine we place the elements on a grid. Multiplying by a moves one position to the right, while multiplying by b moves one position up. The grid extends infinitely along both axes, but there are no elements with negative co-ordinates, so the identity element is at the bottom-left corner.

The staircase diagram also assigns a unique color to each Archimedean component. The Archimedean component of the identity element is exactly the set of invertible elements ("units") in a commutative monoid. Since ℕ ⊕ ℕ has no units other than the identity, the point at the origin has a distinct color of its own. This monoid has 4 Archimedean components total, which is the maximum you can achieve with two generators.

⟨a, b | aa=1, aaa=1⟩

Let's look at the following monoid next:

• ⟨a, b | aa=1, aaa=1⟩ is a two-relation presentation of the natural numbers under addition, ℕ.

Taking the two defining relations together, we get the consequence a = a(aa) = 1. The Gröbner basis has one rule, ⟨a, b | a=1⟩. This means you can still "travel" as far as you want up the b axis, but as soon as you take a single step on the a axis, you jump back. Let's draw a rectangle with bottom-left corner at a, the left-hand side of our relation, together with an arrow pointing towards 1, the right-hand side of our relation:

The box covers up all points with a co-ordinate strictly greater than zero; these are the points that can be reduced using our rule. There are now two Archimedean components, with the identity element again in a component of its own, because it is the only unit.

⟨a, b | ab=1, ba=1⟩

Now, consider this presentation:

• ⟨a, b | ab=1, ba=1⟩ is the group of integers, ℤ.

Since ab=1, our box has been shifted up by one position. We now get not one but two infinite rays of uncovered points, and something very interesting has happened; the Archimedean component structure has collapsed entirely, and every element in our monoid is now a unit.

⟨a, b | ba=ab, aaa=1⟩

Here is a commutative monoid with non-trivial units, which is not a group:

• ⟨a, b | ba=ab, aaa=1⟩ is isomorphic to the direct sum ℤ₃ ⊕ ℕ.

The b axis goes on forever as before, but you now can take up to three steps on the a axis before wrapping around. The Archimedean component of the identity element has three elements, which means this monoid has a non-trivial group of units. Indeed, both a and aa are invertible, with a ⋅ aa = 1. The group of units is isomorphic to ℤ₃. The elements with b co-ordinate greater than zero are not invertible, and they form a second Archimedean component.

⟨a, b | ba=ab, aaabbb=1⟩

Let's repeat the same trick to get a group:

• ⟨a, b | ba=ab, aaabbb=1⟩ is the direct sum ℤ₃ ⊕ ℤ.

Once again, the Archimedean component structure collapses:

⟨a, b | ba=ab, aaa=bb⟩

While ℕ is just the free monoid on one generator, its submonoid structure is quite elaborate. A submonoid of ℕ is called a Numerical semigroup. A numerical semigroup is finitely generated, so it consists of those natural numbers which can be written as a linear combination of the generators.

Here is an interesting presentation:

• ⟨a, b | ba=ab, aaa=bb⟩ is isomorphic to the numerical semigroup generated by 2 and 3.

Here is the staircase diagram. This monoid has two Archimedean components, and no units, but otherwise the staircase diagram doesn't reveal much:

So which natural numbers can be written as a linear combination of 2 and 3? Every even number can, and so can every odd number greater than or equal to 3, so 1 is the only natural number not present in this submonoid.

Two more numerical semigroups appear in the enumeration:

• ⟨a, b | ba=ab, aaaaa=bb⟩ is the numerical semigroup generated by 2 and 5.
• ⟨a, b | ba=ab, aaaa=bbb⟩ is the numerical semigroup generated by 3 and 4.

⟨a, b | ba=ab, bb=aa⟩

A cancellative monoid is one with the property that for any three elements x, y, z, such that xz = yz, then it is already true that x = y. (That is, we can "cancel" the z on both sides to solve the equation, like in "ordinary" algebra). Every cancellative commutative monoid is a submonoid of an Abelian group, known as the monoid's Grothendieck group, or group of fractions.

For example, here is a submonoid of ℤ₂ ⊕ ℤ (in fact, a submonoid of ℤ₂ ⊕ ℕ):

• ⟨a, b | ba=ab, bb=aa⟩ is isomorphic to the submonoid of ℤ₂ ⊕ ℕ generated by (1, 1) and (0, 1).

Like a number of other questions relating to Abelian groups, the generating set for this embedding can be found by computing the Smith normal form of a certain matrix constructed from the monoid presentation.

As in the previous example, the staircase diagram is not very revealing:

It is decidable if a commutative monoid is cancellative. This follows from the correspondence between commutative monoid presentations and ideals in polynomial rings. From a Gröbner basis, it is possible to compute the saturation of the corresponding binomial ideal. The presented monoid is cancellative if and only if each defining relation of the saturation ideal holds in the original monoid. If any such relation does not hold, the monoid is not cancellative, and we get an explicit counterexample demonstrating non-cancellativity.

All of the commutative monoids we've seen so far have been cancellative. The cancellative commutative monoids in the enumeration can all be described in a simple way, and it appears that they are classified up to isomorphism:

• Infinite cancellative commutative monoids

However, most of the commutative monoids in the enumeration are not cancellative, and most of those don't admit such a simple description, except for a few free products:

• Infinite non-cancellative commutative monoids

I don't know if any of the remaining non-cancellative commutative monoids are isomorphic to each other, and all I can say is they are only unique up to Gröbner basis. While the isomorphism problem is decidable for commutative monoids, I have not tried to implement the general algorithm.

⟨a, b | ba=ab, aaa=bb⟩

Here is a non-cancellative monoid:

• ⟨a, b | ab=a, ba=a⟩ is not cancellative, because ab = a, but b ≠ 1.

You can travel infinitely far along the a or b axis, but the relationship between them is more complicated. This is not a submonoid of any Abelian group; in an Abelian group, ab=a would imply that b=1, but this does not hold in this monoid.

⟨a, b | aab=b, aaaa=abb⟩

In all examples so far, the Gröbner basis consisted of only one rule. Any staircase diagram consisting of a single box must leave an infinite subset of points uncovered, no matter how we position the box. So to get a finite commutative monoid, we need a Gröbner basis with more than one rule. This is a nice intuitive argument (maybe not quite rigorous enough to be a proof) showing that a commutative monoid with two generators and one relation necessarily has to be infinite. (Which immediately implies the same fact about non-commutative monoids as well, if you consider the quotient by ba=ab!)

So to get a finite monoid, we need at least two boxes, or rules in our Gröbner basis, and we have to position them in just the right way to cover up both "ends". For example:

• ⟨a, b | aab=b, aaaa=abb⟩ is a finite commutative monoid with 8 elements. The Gröbner has three rules.

If you count the remaining uncovered points, you can see there are exactly 8:

We finally have a "real" staircase diagram!

⟨a, b | ab=a, baa=a⟩

Of course you can still get an infinite monoid whose Gröbner basis has more than one rule, for example:

• ⟨a, b | ab=a, baa=a⟩ is not cancellative, because ab = a, but b ≠ 1.

In this monoid, the powers of b are in bijective correspondence to the natural numbers, but there is one more "weird" element a adjoined, living in its own Archimedean component:

Since abⁿ = a for all n, this element a behaves like an "infinitely large" element. So this monoid is isomorphic to ℕ ∪ {∞}, with the "obvious" operation of addition extended in this way.

If you want to learn more about commutative monoids, I recommend reading Commutative Semigroups by P.A. Gillet, and Finitely Generated Commutative Monoids by J.C. Rosales and P.A. Garcia-Sanchez.

Cancellativity

Whether a monoid is cancellative can be read off directly from the presentation in the case of a one relation monoid, but in the world of multiple relations, the situation is more subtle:

1. As mentioned above, cancellativity is decidable for commutative monoids.
2. If a monoid is known to be finite, the question is also very easy; a finite monoid is cancellative if and only if it is a group.
3. One more simple case is when our monoid can be expressed as a free product; then the monoid is cancellative if and only if each factor is cancellative.
4. In the general case of an infinite, non-commutative monoid, cancellativity is undecidable, even if the monoid has a finite complete presentation; see Cancellativity in Finitely Presented Semigroups.

Regarding (3) above, there are three such cancellative monoids which are not groups in the enumeration. These are the only infinite non-commutative monoids with two relations where I can automatically prove cancellativity:

• Infinite cancellative non-commutative monoids

To prove left (or right) cancellativity, one must show that multiplication by every generator on the left (or right) is always one-to-one. On the other hand, to show that a monoid is not left (or right) cancellative, it suffices to exhibit a single counterexample, in the form of three elements x, y, z such that x≠y and zx=zy (or xz=yz).

So while the general problem is undecidable, it is sometimes possible to find "obvious" non-cancellativity witnesses among the rewriting rules of a finite complete presentation:

1. If there is a rule where both sides start with the same letter, the monoid is not left-cancellative.
2. If there is a rule where both sides end with the same letter, the monoid is not right-cancellative.
3. If there is a rule of the form w ⇒ 1, we check each cyclic conjugate 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.

Of course, when none of the rules in the FCRS match any of the above heuristics, we cannot conclude anything; the monoid might be cancellative or non-cancellative.

In the two relation enumeration, the majority of the infinite non-commutative monoids turn out to be non-cancellative, and the above heuristics successfully find a witness to the failure of cancellativity on at least one side:

• Infinite non-cancellative non-commutative monoids

Some examples where the w ⇒ 1 heuristic can find a non-cancellativity witness:

• ⟨a, b | ab=1, aabb=1⟩ is a two-relation presentation of the bicyclic monoid.
• ⟨a, b | aabb=1, abab=1⟩ is a slightly more interesting two-relation special monoid. Taking the first relator aabb=1 for example, you can see for yourself that baab does not reduce to 1, by typing it into the "normal form widget" on the linked page. Thus, baabbaab reduces to baab (try it!) and so multiplication by b is not injective, and this monoid is not cancellative.

There are only 105 presentations remaining where cancellativity is unknown:

• Infinite non-commutative monoids

Some of them are cancellative, and some are probably not, but at this time I have no automatic way to decide one way or another.

Note: There is one more simple criterion for cancellativity, which generalizes the one relation monoid criterion. If a presentation is cycle free, then the presented monoid is cancellative. However, there are no cycle-free presentations in the two generator, two relation enumeration. Some appear in the three generator, two relation enumeration, though.

Hard instances

In this enumeration, I can find a finite complete rewriting system for all but 17 hard instances. The first one has length 10, while the remaining 16 have length 11.

⟨a, b | aaa=a, abba=bb⟩

I claim that ⟨a, b | aaa=a, abba=bb⟩ cannot be presented by a finite complete rewriting system over any alphabet (this monoid is "not FCRS"). Since everything else is solved up to length 10, it is the unique such monoid of minimum length. In fact, just like Squier's S₁, this monoid does not have finite derivation type.

• A two-relation monoid does not have finite derivation type

The second half of this article describes my earlier enumeration of two-relation monoids up to length 10; at the time, this monoid was one of three hard instances. Since then, I've solved the other two; they're FCRS and isomorphic to each other:

• ⟨a, b | bab=aaa, bbbb=1⟩

⟨a, b | aba=aa, baa=aab⟩

I also have an earlier result that one of the length 11 hard instances is not FCRS. The main proof fits in two pages, and it is (relatively speaking) quite straightforward, relying only on nothing more than the preliminary definitions and the pumping lemma for regular languages. I would be very happy if this was incorporated as an example in someone's textbook on string rewriting or Knuth-Bendix completion!

• The monoid ⟨a, b | aba=aa, baa=aab⟩ has no finite complete presentation