home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17187 < prev    next >
Encoding:
Text File  |  1992-12-21  |  3.4 KB  |  65 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!noc.near.net!black.clarku.edu!black.clarku.edu!djoyce
  3. From: djoyce@black.clarku.edu (Dave Joyce)
  4. Subject: Re: A word problem
  5. Message-ID: <djoyce.724714724@black.clarku.edu>
  6. Organization: Clark University (Worcester, MA)
  7. References: <1992Dec12.162349.29729@dcs.qmw.ac.uk> <djoyce.724444576@black.clarku.edu> <1992Dec15.221213.6274@dcs.qmw.ac.uk>
  8. Date: 18 Dec 92 21:38:44 GMT
  9. Lines: 54
  10.  
  11. In <1992Dec15.221213.6274@dcs.qmw.ac.uk> arodgers@dcs.qmw.ac.uk (Angus H Rodgers) writes:
  12. >
  13. >I had some amazingly prompt responses to my article, on the day it was
  14. >posted, at the weekend. My thanks go especially to Mark "V." Sapir and
  15. >Nicholas Reingold, whose virtually instantaneous and simultaneous replies
  16. >supplied all the information I needed, and convinced me that sci.math
  17. >has some previously unsuspected oracular qualities. I'll summarise the
  18. >replies when I have time (probably after Christmas ...). Meanwhile, I'll 
  19. >just say that the answer to my question is known, and can be found in:
  20. >
  21. >    Lallement, Gerard
  22. >       Semigroups and combinatorial applications / [by] Gerard Lallement.
  23. >       New York : Wiley, 1979. - xiii,376p : ill ; 24cm. - (Pure and
  24. >       applied mathematics)
  25. >       'A Wiley-Interscience publication'. - Text on lining paper. - Bibl.:
  26. >       p.357-368. - Index. - 0-471-04379-6
  27. >
  28. >(At least, I'm told it can; but a computer error has prevented me from
  29. >borrowing the book and making sure. Aargh! I hate computers!)
  30. >
  31. >I had also better admit, with some embarrassment, that my presentation
  32. >of the problem was confused, in that I used the term "reduced words" to
  33. >refer to strings over the alphabet {a,b,c} which are (in the correct
  34. >terminology) "squarefree", i.e. have no nonempty substrings of the form 
  35. >xx; *but* distinct squarefree strings may nevertheless denote equal elements
  36. >in all idempotent semigroups -- because the reduction rule xx = x can be 
  37. >applied in both directions. (It never even entered my head that the
  38. >backwards application could be needed.) There are, indeed, recipes for
  39. >constructing infinite squarefree strings over a 3-character alphabet, but
  40. >it does not follow from this that infinite 3-generated idempotent
  41. >semigroups exist, and I'm sorry that I gave the misleading impression that
  42. >there was such an implication.
  43.  
  44. I haven't yet seen the book, but after a bit of work, I found that the free
  45. idempotent semigroup on three generators {a,b,c} has 159 elements.  I was
  46. surprized that it wasn't infinite.  The number 159 may look strange, but it is
  47. divisible by 3.  Every element in the semigroup starts with one of the three
  48. generators (no matter which string is used to represent it), so there are 53
  49. elements starting with any particular generator, say a.  One of those elements
  50. is a itself.  That leaves 52, which is divisible by 2.  26 of those begin with
  51. ab, the other 26 begin with ac.
  52.  
  53. There are some interesting identities which hold in idempotent semigroups.  My
  54. colleague down the hall, John Kennison, discovered the identity xyz=xyzyxyz.
  55. There are other identities similar to that.  If u and v are any three-letter
  56. permutations of abc, and if x is any string over {a,b,c}, then  uv=uxv.  For
  57. instance, (acb)(cab)=(acb)(abcb)(cab).
  58.  
  59. I don't know whether the idempotent semigroup on 4 generators is finite.
  60.  
  61. -- 
  62. David E. Joyce                Dept. Math. & Comp. Sci.
  63. Internet:  djoyce@black.clarku.edu    Clark University
  64. BITnet:    djoyce@clarku        Worcester, MA 01610-1477
  65.