From: arodgers@dcs.qmw.ac.uk (Angus H Rodgers)
Newsgroups: sci.math
Subject: Re: A word problem
Date: 15 Dec 92 22:12:13 GMT
Organization: Computer Science Dept, QMW, University of London

In <djoyce.724444576@black.clarku.edu>
djoyce@black.clarku.edu (Dave Joyce) writes:

>In <1992Dec12.162349.29729@dcs.qmw.ac.uk>
>arodgers@dcs.qmw.ac.uk (Angus H Rodgers) writes:

>>Are there any finitely generated infinite semigroups in which
>>the idempotent law holds?
>>
>>The "free idempotent semigroup" (if that's the name for it) on
>>2 generators has 6 elements. I don't know if the f.i.s. on 3
>>generators is infinite, but it's certainly quite big.
>>
>[Description and comments for problem with an alphabet {a,b,c} deleted]
>>
>>Is there, nevertheless, a recipe or existence proof for arbitarily
>>long reduced words?

>This is a very interesting problem, but I haven't made any progress on it yet.
>[....]
>Sometimes the source of a problem helps in solving the problem.  I'd like to
>know more about it.

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.

>Does anyone know examples of idempotent semigroups (or idempotent monoids)
>besides the commutative ones?  (Commutative ones are semilattices and don't
>help with this problem.)

When I dallied with this problem last year (somebody mentioned 
semilattices, and somebody else wondered what would happen if you
dropped the commutativity condition, but none of us had worked in
this area), I thought of some examples, and I think I reduced them all
to this one construction (which, I now learn, is called a "rectangular
band"): take any two sets A, B (nonempty, and not both singletons, if
you want to avoid commutativity), and on the Cartesian product AxB
define an associative, idempotent binary operation * by putting
(a,b) * (a',b') := (a,b').
--
Gus Rodgers,  Dept. of Computer Science, | 
Queen Mary & Westfield College, Mile End | 
Road, London, England.   +44 71 975 5241 | 
E-mail (JANET):   arodgers@dcs.qmw.ac.uk | Post in haste, repent at leisure.
Newsgroups: sci.math.num-analysis