ON MONOIDS WITH A SINGLE DEFINING RELATOR

G. C. Smith

Abstract. This paper concerns single-relator monoid presentations, and discusses the circumstances in which the resulting monoid is or is not a group.

This paper is dedicated to my parents Eileen and Roy Smith on the occasion of their Golden Wedding Anniversary.

Introduction

This note is in response to questions of D. L. Johnson and R. M. Thomas [1]. Johnson asked whether or not the monoid presented as ⟨x, y | x^{2}y^{3}xy = 1⟩ is a group. In fact this is not by each of Theorems 1, 2 and 3 below.

According to Johnson, Thomas has asked whether a single relator monoid on three letters can be a group. Now, a palindromic relator involving all letters must obviously define a group, but the question becomes interesting if we insist that the relator not be a palindrome. M. J. Tomkinson (personal communication) has pointed out that one may stretch the meaning of palindrome here so that, for example xxyx is a palindrome – an x syllable followed by a y syllable followed by an x syllable. Even with this liberal interpretation of the term palindrome, we will be able to prove, in Theorem 5, that any finite number of letters (but at least two), there is a non-palindromic single monoid relator on those letters which defines a group.

Typeset by AMS-TEX 2 G. C. SMITH

Results

The first result shows that Johnson’s monoid is not a group. First recall that a syllable in a word is a non-empty subword of maximal extent subject to involving a single letter.

As Johnson observed [1], a monoid on two letters with a relator having an odd number of syllables must be a group providing it at least three syllables. Theorem 1. Let M = mon⟨x, y | r = 1⟩ where r involves an even number of syllables. If the strictly highest power of x or y occurring in this product is an end syllable, then M is not a group.

Our second result subsumes Theorem 1. Theorem 2. Let X be a set of size at least two. If M = mon⟨X | r = 1⟩ and no proper initial segment of r co-incides with a proper terminal segment of r then M is not a group.

Our third result concerns single relator monoids on two letters. If there are two syllables, the monoid is not a group [1]. If there are four syllables then we can say exactly when the monoid is a group. Theorem 3. Let M = mon⟨x, y | r = 1⟩ where r = x^{a}y^{b}x^{c}y^{d} and a, b, c, d > 0. The monoid M is a group if and only if d ≤ b, a ≤ c and at least one of these equalities is strict.

If the length of the relator is six syllables, then the situation becomes more complicated. Theorem 4. Let M = mon⟨x, y | r = 1⟩ where r = x^{a}y^{b}x^{c}y^{d}x^{e}y^{f} and the expo-

ON MONOIDS WITH A SINGLE DEFINING RELATOR 3

nents are all positive. The monoid M is a group if and only if one of the following conditions holds.

(a) b = d, c = e, a ≤ c, f ≤ d and at least one of the inequalities is strict.

(b) a ≤ e, f ≤ b and at least one of the inequalities is strict.

(c) a = e, b = f, c ≤ a, b ≤ d and at least one of the inequalities is strict.

(d) a = e, b = f, a ≤ c, d ≤ b and at least one of the inequalities is strict.

A sufficiently diligent reader might wish to explore the situation where the relator has a larger even number of syllables. Our final result answers the question attributed to Thomas [1].

Theorem 5. Let n ≥ 2 be a natural number. There is a single relator monoid M_{n} on n letters with the relator not a palindrome but M_{n} a group.

Proofs

Since Theorem 2 subsumes Theorem 1, the inclusion of the latter result in this note needs explanation. The point is that the method of proof of Theorem 1 given below may be applicable in other contexts.

The idea of this proof of Theorem 1 is to proceed as if we are performing Todd-Coxeter coset enumeration [3,4] in an attempt to construct functions x, y : ℕ ⟶ ℕ which satisfy the relator. There will be a variation to the usual Todd-Coxeter procedure in order to avoid getting bijections.

There is no hope of replacing the natural numbers by a finite set since injections and surjections would then co-incide, and functions satisfying the relator would be bijections.

4 G. C. SMITH

Make a Todd-Coxeter table headed by the relator, and successively fill in rows according the the recipe we now describe. Row n should begin and end with n. The first row is as shown, given that we are studying Johnson’s monoid.

\begin{aligned}& x & & x & & y & & y & & y & & x & & y \\ 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 1 \end{aligned}

The function which will correspond to x sends 1 to 2, 2 to 3 and 6 to 7. The function which will correspond to y sends 3 to 4, 4 to 5, 5 to 6 and 7 to 1. From now on identify x and y with their corresponding functions. Fill in successive rows from left to right according to the rule that when an entry is not forced (by a previous entry) then the smallest natural number hitherto unmentioned is inserted in the table. The first few rows of the table are as follows.

x  x  y  y  y  x  y
1  2  3  4  5  6  7  1
2  3  8  9  10  11  12  2
3  8  13  14  15  16  17  3
4  18  19  20  21  22  23  4
5  24  25  26  27  28  29  5
6  7  30  31  32  33  34  6
7  30  35  36  37  38  39  7
8  13  40  41  42  43  44  8
9  45  46  47  48  49  50  9
10  51  52  53  54  55  56  10

Provided that this process may be continued indefinitely, we are done. The functions corresponding to x and y are defined by the inductive completion of the table. If a natural number m does not occur as an argument for y in the table, then define (m)y = 42. Now (1)y = (41)y so y is not bijective and Johnson’s monoid is not a group.

Now, the only obstruction to this procedure is that there might be a row n which must be filled in according to definitions previously made, and that the final entry

ON MONOIDS WITH A SINGLE DEFINING RELATOR 5

of row n might be forced to be not n.

In fact this cannot happen, since in every row the only entries which are determined by previous definitions occur to the left of the column before the first y. This is a special case of the general argument.

Proof of Theorem 1.

Use the procedure outlined above to fill in a Todd-Coxeter table. We assume, without loss of generality, that the relator begins with an x.

Let P_{n} be the proposition that at the moment the definition of row n commences, the entries in each column immediately preceding each y-syllable of row n do not yet have their value under x assigned. Of course P_{1} holds. Assume P_{r} holds, and imagine we are about to study row r +1. If (r +1)x is undefined then P_{r+1} holds. If (r + 1)x is already defined then r + 1 is an entry in a row earlier than row r + 1 and after column 1. This record of the value of (r +1)x and those available immediately to the right run out when we reach the column immediately preceding a y-syllable or the last column. The condition on the length of the initial x-syllable ensures that in row r + 1 the entry in the penultimate column before first y-syllable does not yet have its x-value assigned. When it is assigned (to an unused number), that entry will not have its x-value assigned at the end of the study of row n + 1, and nor will any other entries in columns immediately preceding y−syllables.

Notice that (1)y is not assigned by this procedure, though every natural number (including 42) is assigned as a y-value. Thus putting (1)y = 42 ensures that y is not injective, and the monoid is not a group.

It is instructive to see this process failing when applied to the monoid ⟨x, y |

6 G. C. SMITH

xy^{2}xy = 1⟩ which is in fact a group. The table begins

x  y  y  x  y
1  2  3  4  5  1
2  6  7  8  9  2
3  10  11  12  13  3
4  5  1  14  15  4
5  16  17  18  19  5
6  20  21  22  23  6
7  24  25  26  27  7
8  9  2  3  10  11

but the final entry should also be 8.

Proof of Theorem 2. If r is the empty word, the result is clear. Suppose, without loss of generality, that r begins with x. Put a short-lex ordering on words on X : in other words order the letters of X arbitrarily, and order words according to their length, and discriminate between words of the same length using lexicographic order. Now subject the relator r to the Knuth-Bendix completion procedure [2]. This starts by looking for critical pairs obtained by r overlapping with r. There are no such overlaps, so the Knuth-Bendix procedure terminates immediately, and r ⟶ 1 is a complete rewriting system for M. Thus successive applications of the rewrite rule (until no rewrites are possible) will put words representing the same element of the monoid into the same normal form. Conversely, words representing different elements of the monoid will be put into distinct normal forms.

Given our rewrite rule, it follows that y ∈ X − {x} has no right inverse and we are done.

Proof of Theorem 3. When initiating a Knuth-Bendix completion procedure, no self-overlaps will occur (and M will not be a group) unless both d ≤ b, a ≤ c. In the event that a = c and b = d then the unique critical pair requires no resolution

ON MONOIDS WITH A SINGLE DEFINING RELATOR 7

and x^{a}y^{b}x^{a}y^{b} ⟶ 1 is a complete rewriting system for M, and so y has no right inverse.

Finally we suppose that d ≤ b, a ≤ c and at least one of these inequalities is strict. Initiate the Knuth-Bendix procedure to discover that x^{a}y^{b}x^{c}y^{d}y^{b−d}x^{c}y^{d} is both y^{b−d}x^{c}y^{d} and x^{a}y^{b}x^{c−a}. Now 1 = x^{a}y^{b}x^{c}y^{d} = y^{b−d}x^{c}y^{d}x^{a}y^{d} = x^{a}y^{d}x^{a}y^{b}x^{c−a}. Thus either x or y has a two sided inverse. Conjugation now forces both to have two sided inverses and M to be a group.

We say an overlap of words is syllabic if the overlapping segment consists of a collection of syllables of each word. Notice that, in Theorem 3, the only way a group arises is when the relator overlaps itself in way which is non-syllabic. Any hope that this might generalise is quashed by the observation that mon⟨x, y | x^{2}yxyx^{2}y = 1⟩ is a group. To see this, the non-trivial overlap yields that x^{2}y commutes with xy. Thus our monoid is an epimorphic image of mon⟨x, y | xyx^{2}yx^{2}y = 1⟩ which is a group by an argument analogous to the proof of Theorem 3, or by appeal to Theorem 4.

Proof of Theorem 4. Suppose the relator overlaps itself with the overlap involving four syllables. If the overlap is non-syllabic, M will be a group for the usual reason. This is condition (a). If the overlap is syllabic, the relator is (x^{a}y^{b})^{3} = 1. The usual Knuth-Bendix argument shows that M is not a group.

Thus we may assume that any overlap involves only two syllables, Condition (b) describes the situation when the overlap is non-syllabic. If the overlap is syllabic, the relator is x^{a}y^{b}x^{c}y^{d}x^{a}y^{b} = 1 and the upshot of the overlap is that x^{a}y^{b}x^{c}y^{d} = x^{c}y^{d}x^{a}y^{b}. Now observe that (x^{a}y^{b})^{2}x^{c}y^{d} = x^{c}y^{d}(x^{a}y^{b})^{2} = 1 so if either condition

8 G. C. SMITH

(c) or (d) holds then M is a group by the usual non-syllabic argument. Finally, if conditions (c) and (d) both fail to hold then x^{a}y^{b} and x^{c}y^{d} do not overlap in a relevant way. This enables us to use Knuth-Bendix to obtain a complete set of rewrite rules for M. The rules are (x^{a}y^{b})^{2}x^{c}y^{d} ⟶ 1 and x^{c}y^{d}x^{a}y^{b} ⟶ x^{a}y^{b}x^{c}y^{d}. Thus y has no right inverse and M is not a monoid. Proof of Theorem 5. If there are less than three letters the result is clear since, as J. M. Howie has observed [1], mon⟨x, y | xy^{2}xy = 1⟩ is a group. Suppose the letters are x, y, a_{1}, a_{2}, … a_{n}. Let w be the palindrome a_{1}a_{2} … a_{n−3}a_{n−2}a_{n−3} … a_{2}a_{1}. Consider the non-palindromic relator r = xwy^{2}x^{2}wy defining the monoid M_{n} = mon⟨x, y | r = 1⟩. Now in M_{n} we have

xwy^{2}x = xwy^{2}x·1 = xwy^{2}x·xwy^{2}x^{2}wy = xwy^{2}x^{2}wy ·yx^{2}wy = 1·yx^{2}wy = yx^{2}wy

so 1 = r = (yx^{2}wy)xwy = xwy(xwy^{2}x) and both x and y are invertible. Conjugation of r by suitable powers of x and y and their inverses yields that w has a two sided inverse. However, w is a palindrome so its letters must themselves be invertible and we are done.

References

1. D. L. Johnson, Monoid Presentations of Groups, Proceedings of the Royal Irish Academy 97A (1997), 1-4.

2. D. E. Knuth and P. B. Bendix, Simple Word Problems in Universal Algebras (J. Leech, ed.), Computational Problems in Abstract Algebra, Pergammon Press, Oxford, New York, 1970, pp. 263-297.

3. J. A. Todd and H. S. M. Coxeter, A practical method for enumerating cosets in an abstract finite group, Proc. Edinburgh Math. Soc. 5 (1936), 25-36.

ON MONOIDS WITH A SINGLE DEFINING RELATOR 9

4. D. L. Johnson, Presentations of Groups, (2nd edition) C.U.P., Cambridge, 1997.

Department of Mathematical Sciences, University of Bath.