From: djoyce@black.clarku.edu (Dave Joyce)
Subject: Re: A word problem
Organization: Clark University (Worcester, MA)
Date: 18 Dec 92 21:38:44 GMT

In <1992Dec15.221213.6274@dcs.qmw.ac.uk> arodgers@dcs.qmw.ac.uk (Angus H Rodgers) writes:
>
>I had some amazingly prompt responses to my article, on the day it was
>posted, at the weekend. My thanks go especially to Mark "V." Sapir and
>Nicholas Reingold, whose virtually instantaneous and simultaneous replies
>supplied all the information I needed, and convinced me that sci.math
>has some previously unsuspected oracular qualities. I'll summarise the
>replies when I have time (probably after Christmas ...). Meanwhile, I'll 
>just say that the answer to my question is known, and can be found in:
>
>    Lallement, Gerard
>       Semigroups and combinatorial applications / [by] Gerard Lallement.
>       New York : Wiley, 1979. - xiii,376p : ill ; 24cm. - (Pure and
>       applied mathematics)
>       'A Wiley-Interscience publication'. - Text on lining paper. - Bibl.:
>       p.357-368. - Index. - 0-471-04379-6
>
>(At least, I'm told it can; but a computer error has prevented me from
>borrowing the book and making sure. Aargh! I hate computers!)
>
>I had also better admit, with some embarrassment, that my presentation
>of the problem was confused, in that I used the term "reduced words" to
>refer to strings over the alphabet {a,b,c} which are (in the correct
>terminology) "squarefree", i.e. have no nonempty substrings of the form 
>xx; *but* distinct squarefree strings may nevertheless denote equal elements
>in all idempotent semigroups -- because the reduction rule xx = x can be 
>applied in both directions. (It never even entered my head that the
>backwards application could be needed.) There are, indeed, recipes for
>constructing infinite squarefree strings over a 3-character alphabet, but
>it does not follow from this that infinite 3-generated idempotent
>semigroups exist, and I'm sorry that I gave the misleading impression that
>there was such an implication.

I haven't yet seen the book, but after a bit of work, I found that the free
idempotent semigroup on three generators {a,b,c} has 159 elements.  I was
surprized that it wasn't infinite.  The number 159 may look strange, but it is
divisible by 3.  Every element in the semigroup starts with one of the three
generators (no matter which string is used to represent it), so there are 53
elements starting with any particular generator, say a.  One of those elements
is a itself.  That leaves 52, which is divisible by 2.  26 of those begin with
ab, the other 26 begin with ac.

There are some interesting identities which hold in idempotent semigroups.  My
colleague down the hall, John Kennison, discovered the identity xyz=xyzyxyz.
There are other identities similar to that.  If u and v are any three-letter
permutations of abc, and if x is any string over {a,b,c}, then  uv=uxv.  For
instance, (acb)(cab)=(acb)(abcb)(cab).

I don't know whether the idempotent semigroup on 4 generators is finite.

-- 
David E. Joyce				Dept. Math. & Comp. Sci.
Internet:  djoyce@black.clarku.edu	Clark University
BITnet:    djoyce@clarku		Worcester, MA 01610-1477
Newsgroups: sci.math