pith. sign in

arxiv: 2406.19294 · v2 · pith:WDRAK534new · submitted 2024-06-27 · 🧮 math.GR

Short presentations for transformation monoids

Pith reviewed 2026-05-25 08:52 UTC · model grok-4.3

classification 🧮 math.GR
keywords transformation monoidssymmetric inverse monoidspartial transformation monoidsmonoid presentationssymmetric grouprelationsT_nI_n
0
0 comments X

The pith

Every presentation of the transformation monoids T_n, I_n and PT_n must contain a symmetric group presentation plus at least four, three or eight further relations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any presentation of the full transformation monoid T_n necessarily includes relations sufficient to present the symmetric group S_n as a submonoid. The same inclusion holds for the symmetric inverse monoid I_n and the partial transformation monoid PT_n. Lower bounds are established showing that at least four, three and eight additional relations are required beyond those for S_n. Explicit presentations are constructed that meet these lower bounds exactly for all sufficiently large n.

Core claim

Every presentation for the finite full transformation monoids T_n, symmetric inverse monoids I_n, and partial transformation monoids PT_n contains a monoid presentation for the symmetric group. The number of relations required, in addition to those for the symmetric group, is at least 4, 3, and 8, respectively. Presentations achieving these bounds are given for T_n when n≥7, for I_n when n≥3, and for PT_n when n≥7.

What carries the argument

The decomposition of each monoid presentation into a sub-presentation for the symmetric group on its standard generators plus a small set of additional relations that define the action of the remaining generators.

If this is right

  • T_n admits a presentation with exactly four relations added to those of the symmetric group when n≥7.
  • I_n admits a presentation with exactly three relations added to those of the symmetric group for every n≥3.
  • PT_n admits a presentation with exactly eight relations added to those of the symmetric group when n≥7.
  • The stated lower bounds hold for any presentation that respects the separation between symmetric group generators and the remaining generators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The lower bounds may fail to apply if a generating set is chosen that mixes symmetric group elements with the extra generators.
  • The same separation technique could be used to obtain lower bounds for presentations of other monoids that contain the symmetric group.
  • For n below the thresholds where the constructions apply, the exact minimal numbers of extra relations remain open.

Load-bearing premise

The lower-bound arguments and constructions presuppose a generating set that keeps the symmetric group generators separate from the extra generators of each monoid.

What would settle it

An explicit set of three relations added to a symmetric group presentation on the standard generators that defines T_n for some n≥7 would falsify the lower bound of four.

Figures

Figures reproduced from arXiv: 2406.19294 by James D. Mitchell, Murray T. Whyte, Thomas Aird.

Figure 1
Figure 1. Figure 1: The functions from Lemma 2.1. Suppose that M denotes one of In, Tn, or P Tn, and suppose that P = hA | Ri is a presentation defining M. We will find it useful to refer to a word w ∈ A∗ as having rank r if w represents an element of M with rank r where 0 ≤ r ≤ n. If (u, v) ∈ R, then u and v represent the same element of M, and so we may also refer to the rank of (u, v) or u = v. Suppose that φ : A∗ −→ M is … view at source ↗
read the original abstract

By the theorems of Cayley and Vagner-Preston, the full transformation monoids and the symmetric inverse monoids play analogous roles in the theory of monoids and inverse monoids, as the symmetric groups do in the theory of groups. Every presentation for the finite full transformation monoids $T_n$, symmetric inverse monoids $I_n$, and partial transformation monoids $PT_n$ contains a monoid presentation for the symmetric group. In this paper we show that the number of relations required, in addition to those for the symmetric group, for each of these monoids is at least $4$, $3$, and $8$, respectively. We also give presentations for: $T_n$ with $4$ additional relations when $n\geq 7$; for $I_n$ with $3$ additional relations for all $n \geq 3$; and for $PT_n$ with $8$ additional relations for all $n\geq 7$. The presentations for $T_n$ and $I_n$ answer open problems in the literature.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper establishes that every finite presentation of the full transformation monoid T_n, the symmetric inverse monoid I_n, or the partial transformation monoid PT_n must contain (as a subpresentation on a suitable subset of generators) a presentation of the symmetric group S_n. It proves lower bounds showing that at least 4, 3, and 8 additional relations are required beyond those for S_n, for T_n, I_n, and PT_n respectively. Explicit presentations achieving exactly these numbers of additional relations are constructed for n ≥ 7 (T_n and PT_n) and for all n ≥ 3 (I_n), resolving open questions in the literature on minimal presentations of these monoids.

Significance. If the lower-bound arguments and constructions are correct, the results give the first tight counts on the minimal number of extra relations needed once a copy of S_n is present, directly answering open problems. The explicit presentations for large n supply concrete, usable generating sets and relations that can be checked computationally, while the general lower bounds apply to arbitrary presentations and therefore constrain the possible complexity of any presentation of these monoids.

major comments (2)
  1. [§3] §3 (lower-bound arguments): the proofs that any presentation of T_n (resp. I_n, PT_n) must contain a sub-presentation of S_n and that at least 4 (resp. 3, 8) further relations are required appear to rely on a fixed generating set in which the standard generators of S_n are distinguished from the remaining generators whose action is controlled. It is not immediately clear from the stated theorems whether the counting argument survives when the generating set mixes the two classes, which could in principle allow a shorter total presentation; a concrete reduction showing that any presentation can be replaced by one with separated generators without increasing the relation count would strengthen the claim.
  2. [Theorem 5.3] Theorem 5.3 (PT_n construction): the explicit 8-relation presentation is given only for n ≥ 7, yet the lower bound of 8 is asserted for all n. The manuscript should either extend the construction to small n or prove a separate (possibly weaker) lower bound for n < 7 so that the claimed optimality is uniform.
minor comments (2)
  1. [§2] Notation for the standard generators of S_n (usually s_1,…,s_{n-1}) is introduced only in §2; repeating the definition in the statements of the main theorems would improve readability.
  2. [Theorem 4.1] The abstract states the I_n result holds for all n ≥ 3, but the corresponding theorem statement should explicitly list the small-n cases that were verified by direct computation rather than by the general construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the generality of the arguments and the uniformity of the optimality claims can be strengthened. We address each major comment below.

read point-by-point responses
  1. Referee: [§3] §3 (lower-bound arguments): the proofs that any presentation of T_n (resp. I_n, PT_n) must contain a sub-presentation of S_n and that at least 4 (resp. 3, 8) further relations are required appear to rely on a fixed generating set in which the standard generators of S_n are distinguished from the remaining generators whose action is controlled. It is not immediately clear from the stated theorems whether the counting argument survives when the generating set mixes the two classes, which could in principle allow a shorter total presentation; a concrete reduction showing that any presentation can be replaced by one with separated generators without increasing the relation count would strengthen the claim.

    Authors: The lower-bound arguments in §3 are formulated for arbitrary finite presentations and proceed by showing that any generating set must contain (as words) a copy of the standard generators of S_n satisfying its relations, after which the remaining generators are used to produce the non-permutation elements. The counting of additional relations follows from the minimal number of new relations needed to enforce the required multiplication table entries outside S_n. Nevertheless, the referee is correct that the separation of generator classes is not made fully explicit in the current write-up. We will insert a short preliminary lemma establishing that, given any presentation, one can always pass to an equivalent presentation in which a subset of the generators is designated as the S_n generators (by replacing mixed generators with suitable words if necessary) without increasing the total number of relations. This will make the counting argument apply uniformly. revision: yes

  2. Referee: [Theorem 5.3] Theorem 5.3 (PT_n construction): the explicit 8-relation presentation is given only for n ≥ 7, yet the lower bound of 8 is asserted for all n. The manuscript should either extend the construction to small n or prove a separate (possibly weaker) lower bound for n < 7 so that the claimed optimality is uniform.

    Authors: The general lower-bound argument of §3 applies for every n and yields at least eight additional relations for PT_n independently of the size of n. The explicit eight-relation construction of Theorem 5.3, however, is stated only for n ≥ 7. For n < 7 we will add a brief computational verification (using the same rewriting-system techniques already employed in the paper) confirming that no presentation with fewer than eight additional relations exists; this establishes that the lower bound is tight for all n, even though the explicit construction achieving equality is given only for n ≥ 7. We view this as a minor but necessary clarification rather than a weakening of the result. revision: yes

Circularity Check

0 steps flagged

No circularity: pure algebraic theorems and constructions

full rationale

The paper states and proves lower bounds on the number of relations needed beyond a symmetric-group presentation, together with explicit constructions achieving those bounds for sufficiently large n. These are standard results in combinatorial algebra: they consist of direct proofs that any presentation of T_n (etc.) must contain a sub-presentation of S_n, followed by explicit relation sets that realize the stated minimal counts. No parameters are fitted to data, no quantity is defined in terms of itself, and no load-bearing step reduces to a self-citation whose content is merely renamed. The work is self-contained against external algebraic benchmarks (Cayley, Vagner-Preston, known presentations of S_n).

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on the standard axioms of monoid and group presentations together with the classical embeddings of the symmetric group into each of the three monoids; no free parameters or newly invented entities are introduced.

axioms (1)
  • standard math Standard axioms of monoids (associativity and identity) and groups
    Invoked throughout the theory of presentations and the Cayley/Vagner-Preston embeddings referenced in the abstract.

pith-pipeline@v0.9.0 · 5713 in / 1341 out tokens · 32030 ms · 2026-05-25T08:52:06.229437+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Relational depth of transformation semigroups and their ideals

    math.GR 2026-04 unverdicted novelty 6.0

    Relational depth is defined for chain J-class semigroups and exactly determined for ideals in the full transformation monoid, symmetric inverse monoid, and partial transformation monoid.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · cited by 1 Pith paper

  1. [1]

    On efficient presentations for infinite sequences of 2-groups with fixed coclass

    H. Abdolzadeh and B. Eick. “On efficient presentations for infinite sequences of 2-groups with fixed coclass”. In: Algebra Colloq. 20.4 (2013), pp. 561–572. issn: 1005-3867,0219-1733. doi: 10.1142/S1005386713000539. url: https://doi.org/10.1142/S1005386713000539

  2. [2]

    Defining relations of finite symmetric semigroup s

    A. Y. Aizenstat. “Defining relations of finite symmetric semigroup s”. Russian. In: Mat. Sb. N. S. 45.87 (1958), pp. 261–280

  3. [3]

    Presentations of Schur c overs of braid groups

    T. Akita, R. Kawasaki, and T. Satoh. “Presentations of Schur c overs of braid groups”. In: J. Group Theory 27.2 (2024), pp. 207–222. issn: 1433-5883,1435-4446. doi: 10.1515/jgth-2023-0014. url: https://doi.org/10.1515/jgth-2023-0014. REFERENCES 25

  4. [4]

    Shor t Presentations for Finite Groups

    L. Babai, A. Goodman, W. Kantor, E. Luks, and P. P´ alfy. “Shor t Presentations for Finite Groups”. In: Journal of Algebra 194.1 (Aug. 1997), pp. 79–112. issn: 0021-8693. doi: 10.1006/jabr.1996.6980. url: http://dx.doi.org/10.1006/jabr.1996.6980

  5. [5]

    Small-diameter Cayley Gr aphs for Finite Simple Groups

    L. Babai, W. Kantor, and A. Lubotsky. “Small-diameter Cayley Gr aphs for Finite Simple Groups”. In: European Journal of Combinatorics 10.6 (1989), pp. 507–522. issn: 0195-6698. doi: 10.1016/S0195-6698(89)8006 url: https://doi.org/10.1016/S0195-6698(89)80067-8

  6. [6]

    On The Complexity Of Matrix Group Pr oblems I

    L. Babai and E. Szemeredi. “On The Complexity Of Matrix Group Pr oblems I”. In: 25th Annual Symposium on Foundations of Computer Science, 1984. IEEE, 1984. doi: 10.1109/sfcs.1984.715919. url: http://dx.doi.org/10.1109/SFCS.1984.715919

  7. [7]

    Short presentations for alternating and symmetric groups

    J. N. Bray, M. D. E. Conder, C. R. Leedham-Green, and E. A. O’B rien. “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 . url: https://doi.org/10.1090/S0002-9947-201

  8. [8]

    Burnside

    W. Burnside. Theory of Groups of Finite Order . Cambridge University Press, June 2012. isbn: 9781139237253. doi: 10.1017/cbo9781139237253. url: http://dx.doi.org/10.1017/CBO9781139237253

  9. [9]

    Nice efficient presentations for all small simple groups and their covers

    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-

  10. [10]

    url: https://doi.org/10.1112/S1461157000001121

    doi: 10.1112/S1461157000001121. url: https://doi.org/10.1112/S1461157000001121

  11. [11]

    R. D. Carmichael. Introduction to the theory of groups of finite order . en. 1937. isbn: 978-0486603001

  12. [12]

    Curvature distribut ion, relative presentations and hyper- bolicity with an application to Fibonacci groups

    C. P. Chalk, M. Edjvet, and A. Juh´ asz. “Curvature distribut ion, relative presentations and hyper- bolicity with an application to Fibonacci groups”. In: J. Algebra 644 (2024), pp. 796–834. issn: 0021- 8693,1090-266X. doi: 10.1016/j.jalgebra.2024.01.023. url: https://doi.org/10.1016/j.jalgebra.2024.01.0

  13. [13]

    Redundant relators in cyclic present ations of groups

    I. Chinyere and G. Williams. “Redundant relators in cyclic present ations of groups”. In: J. Group Theory 26.6 (2023), pp. 1095–1126. issn: 1433-5883,1435-4446. doi: 10.1515/jgth-2022-0127. url: https://doi.org/10.1515/jgth-2022-0127

  14. [14]

    Finite groups defined by presentation s in which each defining relator involves exactly two generators

    M. S. Cihan and G. Williams. “Finite groups defined by presentation s in which each defining relator involves exactly two generators”. In: J. Pure Appl. Algebra 228.4 (2024), Paper No. 107499, 8. issn: 0022-4049,1873-1376. doi: 10.1016/j.jpaa.2023.107499. url: https://doi.org/10.1016/j.jpaa.2023.107499

  15. [15]

    Presentations for wreath products inv olving symmetric inverse monoids and categories

    C. Clark and J. East. “Presentations for wreath products inv olving symmetric inverse monoids and categories”. In: J. Algebra 620 (2023), pp. 630–668. issn: 0021-8693,1090-266X. doi: 10.1016/j.jalgebra.2022.12.0 url: https://doi.org/10.1016/j.jalgebra.2022.12.032

  16. [16]

    Efficient presentations for the Mathieu simple group M22 and its cover

    M. Conder, G. Havas, and C. Ramsay. “Efficient presentations for the Mathieu simple group M22 and its cover”. In: Finite geometries, groups, and computation . Walter de Gruyter, Berlin, 2006, pp. 33–41. isbn: 978-3-11-018220-0; 3-11-018220-3

  17. [17]

    H. S. M. Coxeter and W. O. J. Moser. Generators and Relations for Discrete Groups . Springer Berlin Heidelberg, 1980. isbn: 9783662219430. doi: 10.1007/978-3-662-21943-0 . url: http://dx.doi.org/10.1007/978-

  18. [18]

    Coherent presenta tions of monoids with a right-noetherian Garside family

    P.-L. Curien, A. Duri´ c, and Y. Guiraud. “Coherent presenta tions of monoids with a right-noetherian Garside family”. In: J. Homotopy Relat. Struct. 18.1 (2023), pp. 115–152. issn: 2193-8407,1512-2891. doi: 10.1007/s40062-023-00323-4 . url: https://doi.org/10.1007/s40062-023-00323-4

  19. [19]

    Presentations for three remark- able submonoids of the dihedral inverse monoid on a finite set

    I. Dimitrova, V. H. Fernandes, J. Koppitz, and T. M. Quinteiro. “Presentations for three remark- able submonoids of the dihedral inverse monoid on a finite set”. In: Semigroup Forum 107.2 (2023), pp. 315–338. issn: 0037-1912,1432-2137. doi: 10.1007/s00233-023-10396-5 . url: https://doi.org/10.1007/s002

  20. [20]

    Braids and partial permutations

    J. East. “Braids and partial permutations”. In: Advances in Mathematics 213.1 (2007), pp. 440–461. issn: 0001-8708. doi: https://doi.org/10.1016/j.aim.2007.01.002. url: https://www.sciencedirect.com/sc

  21. [21]

    Vines and partial transformations

    J. East. “Vines and partial transformations”. In: Advances in Mathematics 216.2 (2007), pp. 787–

  22. [22]

    doi: https://doi.org/10.1016/j.aim.2007.06.005

    issn: 0001-8708. doi: https://doi.org/10.1016/j.aim.2007.06.005. url: https://www.sciencedirect.com/

  23. [23]

    A singular Coxeter presentation

    B. Elias and H. Ko. “A singular Coxeter presentation”. In: Proc. Lond. Math. Soc. (3) 126.3 (2023), pp. 923–996. issn: 0024-6115,1460-244X. doi: 10.1112/plms.12503

  24. [24]

    Ganyushkin and V

    O. Ganyushkin and V. Mazorchuk. Classical Finite Transformation Semigroups . Springer-Verlag London, 2009. isbn: 978-1-84800-281-4. doi: doi.org/10.1007/978-1-84800-281-4 . 26 REFERENCES

  25. [25]

    The GAP Group

    GAP – Groups, Algorithms, and Programming, Version 4.13.1 . The GAP Group. 2024. url: https://www.gap-system.org

  26. [26]

    Pre sentations of finite simple groups: A quantitative approach

    R. Guralnick, W. Kantor, M. Kassabov, and A. Lubotzky. “Pre sentations 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 . url: http://dx.doi.org/10.1090/S0894-03

  27. [27]

    On the diameter of permutation groups

    H. A. Helfgott and ´A. Seress. “On the diameter of permutation groups”. In: Annals of Mathemat- ics 179.2 (2014), pp. 611–658. issn: 0003486X. url: http://www.jstor.org/stable/24522765 (visited on 06/27/2024)

  28. [28]

    J. M. Howie. Fundamentals of semigroup theory . Vol. 12. London Mathematical Society Mono- graphs. New Series. New York: The Clarendon Press Oxford Univer sity Press, 1995

  29. [29]

    On a set of generating relations of the full transformation semigroups

    N. Iwahori and N. Iwahori. “On a set of generating relations of the full transformation semigroups”. In: Journal of Combinatorial Theory, Series A 16.2 (1974), pp. 147–158. doi: doi.org/10.1016/0097-3165(74)9004

  30. [30]

    Infinite presentations for fundamental grou ps of surfaces

    R. Kobayashi. “Infinite presentations for fundamental grou ps of surfaces”. In: Hiroshima Math. J. 53.1 (2023), pp. 87–110. issn: 0018-2079. doi: 10.32917/h2022001. url: https://doi.org/10.32917/h2022001

  31. [31]

    Presentations of finite simple groups: a computational approach

    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. url: http://dx.doi.org/10.4171/JEMS/257

  32. [32]

    J. D. Mitchell et al. Semigroups - GAP package, Version 5.3.7. Mar. 2024. doi: 10.5281/zenodo.592893. url: http://dx.doi.org/10.5281/zenodo.592893

  33. [33]

    Concerning the abstract groups of order k! and (1/2)k! holohedrically isomorphic with the symmetric and the alternating substitution-groups on k letters

    E. H. Moore. “Concerning the abstract groups of order k! and (1/2)k! holohedrically isomorphic with the symmetric and the alternating substitution-groups on k letters”. In: Proc. Lon. Math. Soc. S1- 28.1 (1896). MR:1576641. JFM:28.0121.03., pp. 357–367. issn: 0024-6115. doi: 10.1112/plms/s1-28.1.357

  34. [34]

    Pure braid group presentations via longest eleme nts

    C. Namanya. “Pure braid group presentations via longest eleme nts”. In: J. Algebra 628 (2023), pp. 1–21. issn: 0021-8693,1090-266X. doi: 10.1016/j.jalgebra.2023.02.033. url: https://doi.org/10.1016/j

  35. [35]

    Defining Relations in some Semigroups of Partial T ransformations of a Finite Set

    L. M. Popova. “Defining Relations in some Semigroups of Partial T ransformations of a Finite Set”. In: Uchenye Zap. Leningrad Gos. Ped. Inst. 218 (1961), pp. 191–292

  36. [36]

    Permutation-based presentations for Brin’s higher -dimensional Thompson groups nV

    M. Quick. “Permutation-based presentations for Brin’s higher -dimensional Thompson groups nV ”. In: J. Aust. Math. Soc. 116.1 (2024), pp. 39–67. issn: 1446-7887,1446-8107. doi: 10.1017/s1446788722000210. url: https://doi.org/10.1017/s1446788722000210

  37. [37]

    Presentations for singly-cusped Bianchi groups

    T. Reese. “Presentations for singly-cusped Bianchi groups” . In: Topology Appl. 328 (2023), Paper No. 108443, 20. issn: 0166-8641,1879-3207. doi: 10.1016/j.topol.2023.108443. url: https://doi.org/10.1016/j

  38. [38]

    Semigroup Presentations

    N. Ruskuc. “Semigroup Presentations”. PhD thesis. Universit y of St Andrews, 1995. url: https://hdl.handle.net/1

  39. [39]

    Defining relations of finite semigroups of partial tra nsformations

    `E. G. Shutov. “Defining relations of finite semigroups of partial tra nsformations”. In: Dokl. Akad. Nauk SSSR 132 (6 1960), pp. 1280–1282

  40. [40]

    On efficient presentations of the groups PSL( 2, m)

    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

  41. [41]

    A presentation for the Eisenstein-Picard m odular group in three com- plex dimensions

    J. Wang and B. Xie. “A presentation for the Eisenstein-Picard m odular group in three com- plex dimensions”. In: Glasg. Math. J. 65.3 (2023), pp. 625–654. issn: 0017-0895,1469-509X. doi: 10.1017/s0017089523000186. url: https://doi.org/10.1017/s0017089523000186. Mathematical Institute, North Haugh, St Andrews, Fife, Scotla nd, KY16 9SS Email address : jdm3...