Short presentations for transformation monoids
Pith reviewed 2026-05-25 08:52 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- [§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.
- [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)
- [§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.
- [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
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
-
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
-
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
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
axioms (1)
- standard math Standard axioms of monoids (associativity and identity) and groups
Forward citations
Cited by 1 Pith paper
-
Relational depth of transformation semigroups and their ideals
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
-
[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]
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
work page 1958
-
[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]
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]
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]
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]
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]
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]
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-
work page 2004
-
[10]
url: https://doi.org/10.1112/S1461157000001121
doi: 10.1112/S1461157000001121. url: https://doi.org/10.1112/S1461157000001121
-
[11]
R. D. Carmichael. Introduction to the theory of groups of finite order . en. 1937. isbn: 978-0486603001
work page 1937
-
[12]
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]
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]
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]
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]
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
work page 2006
-
[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]
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]
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]
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]
Vines and partial transformations
J. East. “Vines and partial transformations”. In: Advances in Mathematics 216.2 (2007), pp. 787–
work page 2007
-
[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]
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]
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]
GAP – Groups, Algorithms, and Programming, Version 4.13.1 . The GAP Group. 2024. url: https://www.gap-system.org
work page 2024
-
[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]
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]
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
work page 1995
-
[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]
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]
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]
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]
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]
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]
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
work page 1961
-
[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]
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]
N. Ruskuc. “Semigroup Presentations”. PhD thesis. Universit y of St Andrews, 1995. url: https://hdl.handle.net/1
work page 1995
-
[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
work page 1960
-
[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]
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...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.