EVERY GROUP IS A MAXIMAL SUBGROUP OF THE FREE IDEMPOTENT GENERATED SEMIGROUP OVER A BAND IGORDOLINKAANDNIKRUSˇKUC DedicatedtoStuartW.Margolisontheoccasionofhis60thbirthday 3 1 ABSTRACT. GivenanarbitrarygroupGweconstructasemigroupofidempotents 0 (band) B with the propertythat the freeidempotentgenerated semigroupover G 2 B hasamaximalsubgroupisomorphictoG. IfGisfinitelypresentedthenB is G G n finite.Thisanswersseveralquestionsfromrecentpapersinthearea. a J 2 1 1. INTRODUCTION ] LetSbeasemigroup. ThesetE = E(S)ofallidempotentsofScarriesastructure R ofapartialalgebra,calledthebiordered setofS,byretainingtheproductsoftheso- G calledbasicpairs: thesearepairsofidempotents{e, f} suchthat{ef, fe}∩{e, f} 6= . h ∅. It should be noted that if ef ∈ {e, f} then fe is also an idempotent, possi- t a bly different from e, f and ef. Also, if S is an idempotent semigroup (i.e. a band) m then its biordered set is in general different from S itself, since not every pair is [ necessarily basic. The term ‘biordered set’comes from an alternative (but equiva- 2 lent) approach, where one considers E(S) as a relational structure equipped with v twopartialpre-orders;hereweshallnotpursuethisapproach,directinginsteadto 5 [4,5,6,11,16]forfurtherbackground. 2 The class of idempotent generated semigroups is of prime importance in semi- 2 1 group theory, with a host of natural examples, such as the semigroups of singular . (non-bijective)transformationsofafiniteset(Howie[12])orsingularn×nmatrices 1 0 over a field (Erdos [7]). It is not difficult to show that the category of all idempo- 3 tent generatedsemigroupswith a fixed biordered set E has an initial object IG(E), 1 calledthefreeidempotentgeneratedsemigroupoverE(weshallalsosay‘overS’when : v E = E(S)). Thissemigroupisdefinedbythepresentation i X IG(E) = hE | e· f = ef ({e, f} isabasicpair)i. r a Here e· f stands for a word of length 2 in the free semigroup E+, while ef is the elementofEtowhichtheproductequalsinS. Unsurprisingly,IG(E)playsacrucial rule in understandingthe structureof semigroupswith a prescribedbiordered set ofidempotents. Forreasonsthatareintrinsictobasicstructuretheoryofsemigroups[11,13],this in turn dependsupon the knowledgeof maximal subgroups of IG(E). It was con- jectured for a long time that the maximal subgroups of IG(E) are always free; this conjecture was widely circulated back in the1980s, and was explicitly recordedin [15]. Theconjecturewasprovedinanumberofparticularcases,seee.g.[15,17,19]. In2009,Brittenham,MargolisandMeakin[1]disprovedtheconjecturebymeansof 2010MathematicsSubjectClassification. 20M05,20F05. Keywordsandphrases. Freeidempotentgeneratedsemigroup,maximalsubgroup,band. 1 2 I.DOLINKAANDN.RUSˇKUC anexplicit72-elementsemigroupSsuchthatIG(E(S))hasamaximalsubgroupiso- morphictoZ⊕Z,thefreeabeliangroupofrank2. ThiswasfollowedbyGrayand Rusˇkuc[9]whoprovedthatevery grouparisesasamaximal subgroupofIG(E(S)) forasuitablychosensemigroupS;ifthegroupinquestionisfinitelypresentedthen afiniteS will suffice. Furtherensuingworksuchas[10,3,8]investigatesmaximal subgroupsofIG(S) forsomespecificnaturalsemigroupsS,andthefirstauthor[2] initiatesthestudyofIG(B),where Bisaband. Theaimofthepresentnoteistoprovetheresultannouncedinthetitle: Theorem 1. Let G be agroup. Then there exists aband B such that IG(B ) has a max- G G imal subgroup isomorphic to G. Furthermore, if G is finitely presented, then B can be G constructedtobefinite. This single construction provides an alternative, simpler proof of all the main results of [9] (Theorems 1–4), resolves [9, Problem 1] which asks whether every finitely presented group is a maximal subgroup of IG(S) for some finite regular semigroup S, and solves [2, Problem 2] which calls for a characterisation of maxi- malsemigroupsoffreeidempotentgeneratedsemigroupsoverbands. 2. PRESENTATION FOR MAXIMAL SUBGROUPS A general presentation for maximal subgroups of IG(S) in terms of parameters that dependonly on the structure of S has been exhibited in [9, Theorem5]. Since we are interested here only in the case of bands, we utilise the particular form of thistheorem,deducedin[2,Corollary5]. Firstofall,recall[13,Theorem4.4.1]thatanyband Bdecomposesintoasemilat- tice of rectangular bands, which are the D-classes of B. Thus a D-class D of S can beviewedasan I×J ‘table’ofidempotentse (i ∈ I,j ∈ J),where{R : i ∈ I}and ij i {L : j ∈ J} are theR-andL-classesin D respectively. Fori,k ∈ I and j,l ∈ J we j refertothetuple(e ,e ,e ,e )asthe(i,k;j,l) square. ij il kj kl Supposenow wehave an element f ∈ B belongingto a D-class above D. From thebasictheoryofbands(see,forexample,[13,Section4.4])weknowthat f induces idempotentmappings σ : I → I,i 7→ σ(i), and τ : J → J, j 7→ (j)τ, such thatfor alli ∈ I, j ∈ J wehave feij = eσ(i),j, eijf = ei,(j)τ. We say that the square (i,k;j,l) is singular induced by f if one of the following holds: (a) σ(i) = i,σ(k) = kand(j)τ = (l)τ ∈ {j,l}; or (b) σ(i) = σ(k) ∈ {i,k} and(j)τ = j,(l)τ = l. We talk of a left-right or up-down singular square depending on whether (a) or (b) applies. Withtheaboveconventionsthegeneralpresentationweneedisasfollows: Proposition2([9,2]). ThemaximalsubgroupHofIG(B)containinge ∈ Dispresented 11 by hf (i ∈ I, j ∈ J)| f = f = 1 (i ∈ I, j ∈ J), (1) ij i1 1j f−1f = f−1f ((i,k;j,l) asingularsquarein D)i. (2) ij il kj kl FREEIDEMPOTENTGENERATEDSEMIGROUPSOVERBANDS 3 3. CONSTRUCTION OF BG LetG beanygroup. LetuschooseandfixapresentationhA | Ri for G inwhich every relation has the form ab = c for some a,b,c ∈ A. It is clear that G has such a presentation– for instance theCayley table would do. What is less obvious, but nonethelessstilltrue,isthatifGisfinitelypresentedthenithasafinitepresentation ofthisform. Onewayofseeingthisisasfollows: Arelation a ...a = b ...b can 1 k 1 l be replaced by two relations of the form a ...a = c, b ...b = c, at the expense 1 k 1 l of introducing a new generator c. Furthermore, the relation a ...a = c can be 1 k replacedbyk−1relations a a = d , d a = d ,...,d a = d , d a = cof 1 2 2 2 3 3 k−2 k−1 k−1 k−1 k thedesiredform,withnewgeneratorsd ,...,d . 2 k−1 Definesets A = A∪{0}, A′ = {a′ : a ∈ A }, I = A ∪A′, J = A ∪{∞}, 0 0 0 0 0 0 where0, ∞ and a′ (a ∈ A )are symbolsdistinctfromeach otherandthosealready 0 (l) (r) (l) (r) in A. ConsiderthesemigroupT = T ×T ,whereT (respectivelyT )isthe I J I J semigroupofallmappings I → I (resp. J → J)writtenontheleft(resp. right). The semigroupT hasauniqueminimal idealK consistingofall (σ,τ) withbothσ and τ constant. Thisidealisnaturallyisomorphictotherectangularband I×J,andwe willidentifythetwo. WewillvisualiseK asinFigure1. 0 ∞ 0 0′ FIGURE 1. A visual representation of K = I × J, highlighting the partition I = A ∪ A′, as well as the four distinguished rows and 0 0 columns. Wenowdefineaset L ⊆ T . Allelements(σ,τ) ∈ Lwillhave σ2 = σ, τ2 = τ, ker(σ) = {A ,A′}, im(τ) = A . (3) 0 0 0 Recall that ker(σ) is the equivalence on I defined by (i,i′) ∈ ker(σ) if and only if σ(i) = σ(i′), and that it can be identified with the resulting partition of I into equivalence classes. Therefore, each (σ,τ) will be uniquely determined by im(σ) which must be a two-element setthat is a cross-sectionof {A ,A′}, and the value 0 0 (∞)τ ∈ A . Theelementsof L comein fourgroups: Z –theinitial pair; G, G –the 0 elementsarisingfromthegenerators A;R–theelementsarisingfromtherelations R: 4 I.DOLINKAANDN.RUSˇKUC Type Notation Indexing im(σ) (∞)τ Z (σ ,τ ) – {0,0′} 0 0 0 G (σ ,τ ) a ∈ A {0,a′} a a a G (σ ,τ ) a ∈ A {a,a′} 0 a a R (σr,τr) r = (ab,c) ∈ R {b,c′} a TheseelementscanbevisualisedasshowninFigure2. 0 ∞ a ∞ 0 ∞ a ∞ 0 0 b a 0′ a′ a′ c′ Z : (σ0,τ0) G : (σa,τa) G : (σa,τa) R : (σr,τr) FIGURE 2. The elements (σ0,τ0), (σa,τa), (σa,τa) (a ∈ A), (σr,τr) (r = (ab,c) ∈ R) of L. For each (σ,τ) shadedare thetwo rows cor- respondingtoim(σ) andonecolumn correspondingto (∞)τ. They allhaveker(σ) = {A ,A′}andim(τ) = A . 0 0 0 Becauseker(σ) andim(τ)arethesameforall(σ,τ) ∈ Litfollowsthat Lisaleft zero semigroup(i.e. xy = x for all x,y ∈ L). Furthermore,since K is an idealin T (i.e. xy,yx ∈ K for all x ∈ K, y ∈ T ), the set B = K∪L is a subsemigroup of T . G We remark that, strictly speaking, B dependsnot only on G, but crucially on the G chosenpresentationforG. 4. PROOF OF THEOREM 1 WewillnowusethepresentationgiveninProposition2tocomputethemaximal subgroup H of IG(B ) containing the idempotent e = (0,0) ∈ K. Relations (1) in G 0 ourcontextread f = f = 1(i ∈ I, j ∈ J). (4) 0j i0 Theremainingrelations(2)arisefromthesingularsquaresinducedbytheelements of LactingonK. Eachup-downsingularsquareisofoneofthefollowingforms: (a ,a ;c ,c ), (a′,a′,c ,c ) (a ,a ,c ,c ∈ A ). 1 2 1 2 1 2 1 2 1 2 1 2 0 Thesquare(a ,a ;c ,c )yieldstherelation 1 2 1 2 f−1 f = f−1 f (a ,a ,c ,c ∈ A ). (5) a1,c1 a1,c2 a2,c1 a2,c2 1 2 1 2 0 Puttinga = c = 0, a = a, c = candusing(4)yields 1 1 2 2 f = 1(a,c ∈ A ); (6) a,c 0 FREEIDEMPOTENTGENERATEDSEMIGROUPSOVERBANDS 5 clearly,alltheremainingrelations(5)areconsequencesof(6). Similarly,thesquares (a′,a′,c ,c )yieldtherelations 1 2 1 2 fa′,c = f0′,c (a,c ∈ A0). (7) (Notethatwedonotnecessarilyhave f0′,c = 1,andsocannotdeduce fa′,c = 1.) Turningtotheleft-right singular squares,each (σ,τ) ∈ L inducespreciselyone. Below we list respectively the squares introduced by (σ ,τ ) of type Z, (σ ,τ ) of 0 0 a a type G, (σa,τa) of type G, and (σr,τr) of type R, together with the relations they yield: (0,0′;0,∞) : f0−,01f0,∞ = f0−′,10f0′,∞ (8) (0,a′;a,∞) : f0−,a1f0,∞ = fa−′,1afa′,∞ (a ∈ A) (9) (a,a′;0,∞) : fa−,01fa,∞ = fa−′,10fa′,∞ (a ∈ A) (10) (b,c′;a,∞) : fb−,a1fb,∞ = fc−′,1afc′,∞ (r = (ab,c) ∈ R). (11) Usingtherelations(4),(6),(7),wecantransform(8)–(11)into: f0′,∞ = 1 (12) fa′,∞ = f0′,a (a ∈ A) (13) fa,∞ = fa′,∞ = f0′,a (a ∈ A) (14) f0′,b = f0−′,1af0′,c (r = (ab,c) ∈ R). (15) So, the group H is defined by the generators f (i ∈ I, j ∈ J) and relations (4), i,j (6),(7),(12)–(15). Therelations(4),(6),(7),(12)–(14)canbeusedsimplytoeliminate allthegeneratorsexcept f0′,a (a ∈ A). Replacingeachsymbol f0′,a bythesymbol a, theremainingrelations(15)become ab = c(r = (ab,c) ∈ R). ∼ Inotherwords,weobtaintheoriginalpresentationfor G. Thisprovesthat H = G. FinallynotethatifhA | Riisafinitepresentation,thesemigroupB isalsofinite, G with |B | = (2|A|+2)(|A|+2)+1+2|A|+|R|, G andthiscompletestheproofofourtheorem. 5. AN EXAMPLE, TWO REMARKS AND AN OPEN PROBLEM ItmaybeinstructivetofollowinaspecificexamplethesequenceofTietzetrans- formations constituting the brunt of the above proof. Let us take G = Q , the 8 quaterniongroup,withthewellknownFibonacciF(2,3)presentation(see[14,Sec- tion7.3]): ha,b,c | ab = c, bc = a, ca = bi. The dimension of K in this case is 8×5, and Proposition 2 gives a presentationin termsof40generators. Thisis thensimplified byasequenceofgeneratorelimina- tions,usingrelations(1),up-downsingularsquares,andleft-rightsingularsquares induced by the elements of L of types Z, G, G. In the final step further singular squaresarerevealed,givingbacktheoriginalpresentation. If we record the original generators in a natural 8×5 grid, this process may be encapsulatedasshowninFigure3. 6 I.DOLINKAANDN.RUSˇKUC f0,0 f0,a f0,b f0,c f0,∞ 1 1 1 1 1 fa,0 fa,a fa,b fa,c fa,∞ 1 fa,a fa,b fa,c fa,∞ fb,0 fb,a fb,b fb,c fb,∞ 1 fb,a fb,b fb,c fb,∞ fc,0 fc,a fc,b fc,c fc,∞ −(→1) 1 fc,a fc,b fc,c fc,∞ f0′,0 f0′,a f0′,b f0′,c f0′,∞ 1 f0′,a f0′,b f0′,c f0′,∞ fa′,0 fa′,a fa′,b fa′,c fa′,∞ 1 fa′,a fa′,b fa′,c fa′,∞ fb′,0 fb′,a fb′,b fb′,c fb′,∞ 1 fb′,a fb′,b fb′,c fb′,∞ fc′,0 fc′,a fc′,b fc′,c fc′,∞ 1 fc′,a fc′,b fc′,c fc′,∞ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 fa,∞ 1 1 1 1 fa,∞ 1 1 1 1 fa,∞ 1 1 1 1 fb,∞ 1 1 1 1 fb,∞ 1 1 1 1 fb,∞ −U−/→D 1 1 1 1 fc,∞ −L−/R−:→Z 1 1 1 1 fc,∞ −L−/R−:→G 1 1 1 1 fc,∞ 1 a b c f0′,∞ 1 a b c 1 1 a b c 1 1 a b c fa′,∞ 1 a b c fa′,∞ 1 a b c a 1 a b c fb′,∞ 1 a b c fb′,∞ 1 a b c b 1 a b c fc′,∞ 1 a b c fc′,∞ 1 a b c c 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a 1 1 1 1 a 1 1 1 1 b 1 1 1 1 b L/R:G 1 1 1 1 c L/R:R 1 1 1 1 c −−−→ −−−→ 1 a b c 1 1 a b c 1 1 a b c a 1 a b c a 1 a b c b 1 a b c b 1 a b c c 1 a b c c FIGURE 3. The sequence of Tietze transformations constituting the proofofTheorem1. Remark 3. Itis possibletodescribecompletelythestructureofthefreeidempotent generated semigroup IG(B ). By known results (see e.g. [9, (IG1)–(IG4)]) IG(B ) G G has precisely two regular D-classes. The ‘upper’ one is a left zero semigroup L isomorphic to L (as all products in L are basic), while the ‘lower’ one K, the com- pletelysimpleminimalideal,hasaReesmatrixrepresentationwithstructuregroup G and (normalised) sandwich matrix (a−1), where (a ) is the |I|×|J| table that is ji ij theend-productofTietzetransformationsperformedintheproofofTheorem1(in ourexamplethisisthelasttableinFigure3). WeclaimthatinfactIG(B ) = L∪K. G To confirm this, and see that the structure is completely determined, we need to show how to write products ef and fe with e ∈ L, f ∈ K as products of idempo- tentsfromKinIG(B). Fortheproductef notethatthereexistsg ∈ Ksuchthat fRg and ge = g; both pairs {e,g} and {f,g} are critical and we have ef = egf = hf, whereh = eg ∈ K. Theproduct fecanbetreatedsimilarly. Remark 4. Associated to the biorder E of idempotents of a regular semigroup S there is another free idempotent generated object RIG(E), the free regular idempo- tent generated semigroup on E. It is the largest regular semigroup with the biorder ofidempotentsE, anditspresentationcan beobtainedby addingfurtherrelations to the defining presentation for IG(E). For definition and references we refer the FREEIDEMPOTENTGENERATEDSEMIGROUPSOVERBANDS 7 reader to [9]. In particular, from (IG1)–(IG4), (RIG1), (RIG2) in [9] it follows that IG(B ) = RIG(B ). G G OnewayofinterpretingRemarks3,4istosaythatthewordproblemforIG(B ) G is decidable if and only if the word problem for G is decidable. It is the authors’ belief that the next stage in the ongoing exploration of free idempotent generated semigroupsis preciselyan analysis ofthewordproblemfor IG(S). This at present seemsadauntingtask,evenin thecasewhereS isfinite. Nonetheless,wepropose thefollowingproblemwhichmayjustbewithinreachatthisstage: Question 1. Let B be a finite band such that all maximal subgroups of IG(B) have recursivelysolublewordproblems. IsthewordproblemofIG(B)necessarilyrecur- sivelysoluble? Acknowledgement. The research of the first author is supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia throughGrantNo.174019,andbyagrant(Contract114–451–2675/2012) oftheSec- retariat of Science and Technological Development of the Autonomous Province of Vojvodina. Also, the first author gratefully acknowledgesthe hospitality of the School of Mathematics and Statistics of the University of St Andrews, where this researchwascarriedout. REFERENCES [1] M. Brittenham, S. W. Margolis and J. Meakin, Subgroups of free idempotent generated semi- groupsneednotbefree,J.Algebra321(2009),3026–3042. [2] I.Dolinka,Anoteonmaximalsubgroupsoffreeidempotentgeneratedsemigroupsoverbands, PeriodicaMath.Hungar.65(2012),97–105. [3] I.DolinkaandR.Gray,Maximalsubgroupsoffreeidempotentgeneratedsemigroupsoverthe fulllinearmonoid,Trans.Amer.Math.Soc.,toappear.arXiv:1112.0893 [4] D.Easdown,Biorderedsetsofbands,SemigroupForum29(1984),241–246. [5] D.Easdown,Biorderedsetsarebiorderedsubsetsofidempotentsofsemigroups,J.Austral.Math. Soc.Ser.A37(1984),258–268. [6] D.Easdown,Biorderedsetscomefromsemigroups,J.Algebra96(1985),581–591. [7] J.A.Erdos,Onproductsofidempotentmatrices,GlasgowMath.J.8(1967),118–122. [8] V.Gould,D.Yang,Everygroupisthemaximalsubgroupofanaturallyoccurringfreeidempo- tentgeneratedsemigroup,arXiv:1209.1242 [9] R.GrayandN.Rusˇkuc,Onmaximalsubgroupsoffreeidempotentgeneratedsemigroups,Israel J.Math.189(2012),147–176. [10] R.GrayandN.Rusˇkuc,Maximalsubgroupsoffreeidempotentgeneratedsemigroupsoverthe fulltransformationmonoid,Proc.LondonMath.Soc.105(2012),997–1018. [11] P.M.Higgins,TechniquesofSemigroupTheory,OxfordUniversityPress,NewYork,1992. [12] J. M. Howie, The subsemigroup generated by the idempotents of a full transformation semi- group,J.LondonMath.Soc.41(1966),707–716. [13] J.M.Howie,FundamentalsofSemigroupTheory,OxfordUniversityPress,NewYork,1995. [14] D.L.Johnson,PresentationsofGroups,LMSStudentTextsVol.15,CambridgeUniversityPress, Cambridge,1990. [15] B.McElwee,Subgroupsofthe freesemigrouponabiorderedsetinwhichprincipalidealsare singletons,Comm.Algebra30(2002),5513–5519. [16] K.S.S.Nambooripad,Structureofregularsemigroups.I,Mem.Amer.Math.Soc.22(1979), no. 224,vii+119pp. [17] K. S. S. Nambooripad and F. Pastijn, Subgroups of free idempotent generated regular semi- groups,SemigroupForum21(1980),1–7. [18] N.Rusˇkuc,Presentationsforsubgroupsofmonoids,J.Algebra220(1999),365–380. [19] F.Pastijn,Thebiorderonthepartialgroupoidofidempotentsofasemigroup,J.Algebra65(1980), 147–187. 8 I.DOLINKAANDN.RUSˇKUC [20] M.Petrich,IntroductiontoSemigroups,Merrill,Columbus,1973. DEPARTMENTOFMATHEMATICSANDINFORMATICS,UNIVERSITYOFNOVISAD,TRGDOSITEJA OBRADOVIC´A4,21101NOVISAD,SERBIA E-mailaddress:[email protected] SCHOOLOFMATHEMATICSANDSTATISTICS,UNIVERSITYOFSTANDREWS,STANDREWSKY16 9SS,SCOTLAND,UK E-mailaddress:[email protected]