Orbits of primitive 𝑘-homogenous groups on (𝑛-𝑘)-partitions with applications to semigroups

Araújo, João; Bentz, Wolfram; Cameron, Peter

doi:10.1090/tran/7274

Orbits of primitive $k$-homogenous groups on $(n-k)$-partitions with applications to semigroups
HTML articles powered by AMS MathViewer

by João Araújo, Wolfram Bentz and Peter J. Cameron PDF

Trans. Amer. Math. Soc. 371 (2019), 105-136 Request permission

Abstract:

The purpose of this paper is to advance our knowledge of two of the most classic and popular topics in transformation semigroups: automorphisms and the size of minimal generating sets. In order to do this, we examine the $k$-homogeneous permutation groups (those which act transitively on the subsets of size $k$ of their domain $X$) where $|X|=n$ and $k<n/2$. In the process we obtain, for $k$-homogeneous groups, results on the minimum numbers of generators, the numbers of orbits on $k$-partitions, and their normalizers in the symmetric group. As a sample result, we show that every finite $2$-homogeneous group is $2$-generated.

Underlying our investigations on automorphisms of transformation semigroups is the following conjecture:

If a transformation semigroup $S$ contains singular maps and its group of units is a primitive group $G$ of permutations, then its automorphisms are all induced (under conjugation) by the elements in the normalizer of $G$ in the symmetric group.

For the special case that $S$ contains all constant maps, this conjecture was proved correct more than $40$ years ago. In this paper, we prove that the conjecture also holds for the case of semigroups containing a map of rank $3$ or less. The effort in establishing this result suggests that further improvements might be a great challenge. This problem and several additional ones on permutation groups, transformation semigroups, and computational algebra are proposed at the end of the paper.

References

Jorge André, João Araújo, and Peter J. Cameron, The classification of partition homogeneous groups with applications to semigroup theory, J. Algebra 452 (2016), 288–310. MR 3461068, DOI 10.1016/j.jalgebra.2015.12.025
João Araújo, On idempotent generated semigroups, Semigroup Forum 65 (2002), no. 1, 138–140. MR 1903561, DOI 10.1007/s002330010089
João Araújo, Generators for the semigroup of endomorphisms of an independence algebra, Algebra Colloq. 9 (2002), no. 4, 375–382. MR 1933846, DOI 10.1017/S0013091500000729
João Araújo, Wolfram Bentz, and Peter J. Cameron, Groups synchronizing a transformation of non-uniform kernel, Theoret. Comput. Sci. 498 (2013), 1–9. MR 3083510, DOI 10.1016/j.tcs.2013.06.016
João Araújo, Wolfram Bentz, Peter J. Cameron, Gordon Royle, and Artur Schaefer, Primitive groups, graph endomorphisms and synchronization, Proc. Lond. Math. Soc. (3) 113 (2016), no. 6, 829–867. MR 3626847, DOI 10.1112/plms/pdw040
João Araújo, Wolfram Bentz, James D. Mitchell, and Csaba Schneider, The rank of the semigroup of transformations stabilising a partition of a finite set, Math. Proc. Cambridge Philos. Soc. 159 (2015), no. 2, 339–353. MR 3395375, DOI 10.1017/S0305004115000389
J. Araújo, W. Bentz, E. Dobson, J. Konieczny, and J. Morris, Automorphism groups of circulant digraphs with applications to semigroup theory. To appear in Combinatorica.
J. Araújo, P. V. Bünau, J. D. Mitchell, and M. Neunhöffer, Computing automorphisms of semigroups, J. Symbolic Comput. 45 (2010), no. 3, 373–392. MR 2578344, DOI 10.1016/j.jsc.2009.10.001
João Araújo and Peter J. Cameron, Primitive groups synchronize non-uniform maps of extreme ranks, J. Combin. Theory Ser. B 106 (2014), 98–114. MR 3194197, DOI 10.1016/j.jctb.2014.01.006
João Araújo and Peter J. Cameron, Two generalizations of homogeneity in groups with applications to regular semigroups, Trans. Amer. Math. Soc. 368 (2016), no. 2, 1159–1188. MR 3430360, DOI 10.1090/tran/6368
João Araújo, Peter J. Cameron, James D. Mitchell, and Max Neunhöffer, The classification of normalizing groups, J. Algebra 373 (2013), 481–490. MR 2995039, DOI 10.1016/j.jalgebra.2012.08.033
João Araújo, Peter J. Cameron, and Benjamin Steinberg, Between primitive and 2-transitive: synchronization and its friends, EMS Surv. Math. Sci. 4 (2017), no. 2, 101–184. MR 3725240, DOI 10.4171/EMSS/4-2-1
João Araújo, Edward Dobson, and Janusz Konieczny, Automorphisms of endomorphism semigroups of reflexive digraphs, Math. Nachr. 283 (2010), no. 7, 939–964. MR 2677280, DOI 10.1002/mana.200710033
João Araújo, Vítor H. Fernandes, Manuel M. Jesus, Victor Maltcev, and James D. Mitchell, Automorphisms of partial endomorphism semigroups, Publ. Math. Debrecen 79 (2011), no. 1-2, 23–39. MR 2850032, DOI 10.5486/PMD.2011.4703
João Araújo and Michael Kinyon, Inverse semigroups with idempotent-fixing automorphisms, Semigroup Forum 89 (2014), no. 2, 469–474. MR 3258495, DOI 10.1007/s00233-014-9585-0
João Araújo and Janusz Konieczny, Automorphism groups of centralizers of idempotents, J. Algebra 269 (2003), no. 1, 227–239. MR 2015308, DOI 10.1016/S0021-8693(03)00499-X
João Araújo and Janusz Konieczny, Automorphisms of endomorphism monoids of relatively free bands, Proc. Edinb. Math. Soc. (2) 50 (2007), no. 1, 1–21. MR 2294000, DOI 10.1017/S0013091505000672
João Araújo and Janusz Konieczny, A method of finding automorphism groups of endomorphism monoids of relational systems, Discrete Math. 307 (2007), no. 13, 1609–1620. MR 2316670, DOI 10.1016/j.disc.2006.09.029
João Araújo and Janusz Konieczny, Automorphisms of endomorphism monoids of 1-simple free algebras, Comm. Algebra 37 (2009), no. 1, 83–94. MR 2482811, DOI 10.1080/00927870802241204
João Araújo and Janusz Konieczny, General theorems on automorphisms of semigroups and their applications, J. Aust. Math. Soc. 87 (2009), no. 1, 1–17. MR 2538636, DOI 10.1017/S1446788709000019
J. Araújo and J. D. Mitchell, Relative ranks in the monoid of endomorphisms of an independence algebra, Monatsh. Math. 151 (2007), no. 1, 1–10. MR 2317387, DOI 10.1007/s00605-006-0433-5
J. Araújo and J. D. Mitchell, An elementary proof that every singular matrix is a product of idempotent matrices, Amer. Math. Monthly 112 (2005), no. 7, 641–645. MR 2158897, DOI 10.2307/30037549
J. Araújo, J. D. Mitchell, and Csaba Schneider, Groups that together with any transformation generate regular semigroups for idempotent generated semigroups, J. Algebra 343 (2011), 93–106. MR 2824546, DOI 10.1016/j.jalgebra.2011.07.002
J. Araújo, J. D. Mitchell, and N. Silva, On generating countable sets of endomorphisms, Algebra Universalis 50 (2003), no. 1, 61–67. MR 2026827, DOI 10.1007/s00012-003-1809-1
Fredrick Arnold and Benjamin Steinberg, Synchronizing groups and automata, Theoret. Comput. Sci. 359 (2006), no. 1-3, 101–110. MR 2251603, DOI 10.1016/j.tcs.2006.02.003
V. S. Atabekyan, The automorphisms of endomorphism semigroups of free Burnside groups, Internat. J. Algebra Comput. 25 (2015), no. 4, 669–674. MR 3349110, DOI 10.1142/S0218196715500149
George Barnes and Inessa Levi, Ranks of semigroups generated by order-preserving transformations with a fixed partition type, Comm. Algebra 31 (2003), no. 4, 1753–1763. MR 1972890, DOI 10.1081/AGB-120018506
George Barnes and Inessa Levi, On idempotent ranks of semigroups of partial transformations, Semigroup Forum 70 (2005), no. 1, 81–96. MR 2107195, DOI 10.1007/s00233-004-0142-0
R. A. Beaumont and R. P. Peterson, Set-transitive permutation groups, Canadian J. Math. 7 (1955), 35–42. MR 67889, DOI 10.4153/CJM-1955-005-x
A. Belov-Kanel, A. Berzins, and R. Lipyanski, Automorphisms of the endomorphism semigroup of a free associative algebra, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 923–939. MR 2355675, DOI 10.1142/S0218196707003901
A. Belov-Kanel and R. Lipyanski, Automorphisms of the endomorphism semigroup of a polynomial algebra, J. Algebra 333 (2011), 40–54. MR 2785936, DOI 10.1016/j.jalgebra.2011.01.020
A. Berzins, The group of automorphisms of the semigroup of endomorphisms of free commutative and free associative algebras, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 941–949. MR 2355676, DOI 10.1142/S0218196707003949
Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031, DOI 10.1017/CBO9780511623677
P. J. Cameron and W. M. Kantor, $2$-transitive and antiflag transitive collineation groups of finite projective spaces, J. Algebra 60 (1979), no. 2, 384–422. MR 549937, DOI 10.1016/0021-8693(79)90090-5
Peter J. Cameron, Ron Solomon, and Alexandre Turull, Chains of subgroups in symmetric groups, J. Algebra 127 (1989), no. 2, 340–352. MR 1028457, DOI 10.1016/0021-8693(89)90256-1
J. Cichoń, J. D. Mitchell, and M. Morayne, Generating continuous mappings with Lipschitz mappings, Trans. Amer. Math. Soc. 359 (2007), no. 5, 2059–2074. MR 2276612, DOI 10.1090/S0002-9947-06-04026-8
John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812, DOI 10.1007/978-1-4612-0731-3
J. A. Erdos, On products of idempotent matrices, Glasgow Math. J. 8 (1967), 118–122. MR 220751, DOI 10.1017/S0017089500000173
Edward Formanek, A question of B. Plotkin about the semigroup of endomorphisms of a free group, Proc. Amer. Math. Soc. 130 (2002), no. 4, 935–937. MR 1873764, DOI 10.1090/S0002-9939-01-06155-X
G. U. Garba, On the nilpotent ranks of certain semigroups of transformations, Glasgow Math. J. 36 (1994), no. 1, 1–9. MR 1260812, DOI 10.1017/S0017089500030482
L. M. Gluskĭn, Semi-groups of isotone transformations, Uspehi Mat. Nauk 16 (1961), no. 5, 157–162 (Russian). MR 0131486
Gracinda M. S. Gomes and John M. Howie, On the ranks of certain semigroups of order-preserving transformations, Semigroup Forum 45 (1992), no. 3, 272–282. MR 1179851, DOI 10.1007/BF03025769
Olexandr Ganyushkin and Volodymyr Mazorchuk, Classical finite transformation semigroups, Algebra and Applications, vol. 9, Springer-Verlag London, Ltd., London, 2009. An introduction. MR 2460611, DOI 10.1007/978-1-84800-281-4
The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.6.2, 2013, http://www.gap-system.org
Robert M. Guralnick, Attila Maróti, and László Pyber, Normalizers of primitive permutation groups, Adv. Math. 310 (2017), 1017–1063. MR 3620702, DOI 10.1016/j.aim.2017.02.012
P. M. Higgins, J. M. Howie, J. D. Mitchell, and N. Ruškuc, Countable versus uncountable ranks in infinite semigroups of transformations and relations, Proc. Edinb. Math. Soc. (2) 46 (2003), no. 3, 531–544. MR 2013951, DOI 10.1017/S0013091502000974
Peter M. Higgins, John M. Howie, and Nikola Ruškuc, Generators and factorisations of transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A 128 (1998), no. 6, 1355–1369. MR 1663980, DOI 10.1017/S0308210500027360
P. M. Higgins, J. D. Mitchell, M. Morayne, and N. Ruškuc, Rank properties of endomorphisms of infinite partially ordered sets, Bull. London Math. Soc. 38 (2006), no. 2, 177–191. MR 2214470, DOI 10.1112/S0024609305018138
J. M. Howie, The subsemigroup generated by the idempotents of a full transformation semigroup, J. London Math. Soc. 41 (1966), 707–716. MR 219649, DOI 10.1112/jlms/s1-41.1.707
John M. Howie, Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12, The Clarendon Press, Oxford University Press, New York, 1995. Oxford Science Publications. MR 1455373
John M. Howie and Robert B. McFadden, Idempotent rank in finite full transformation semigroups, Proc. Roy. Soc. Edinburgh Sect. A 114 (1990), no. 3-4, 161–167. MR 1055541, DOI 10.1017/S0308210500024355
William M. Kantor, $4$-homogeneous groups, Math. Z. 103 (1968), 67–68. MR 220812, DOI 10.1007/BF01111290
William M. Kantor, $k$-homogeneous groups, Math. Z. 124 (1972), 261–265. MR 306296, DOI 10.1007/BF01113919
William M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), 315–318. MR 377681, DOI 10.1007/BF01113923
William M. Kantor, Line-transitive collineation groups of finite projective spaces, Israel J. Math. 14 (1973), 229–235. MR 326565, DOI 10.1007/BF02764881
Janusz Konieczny, Automorphism groups of endomorphism monoids of free $G$-sets, Asian-Eur. J. Math. 7 (2014), no. 1, 1450015, 15. MR 3189584, DOI 10.1142/S1793557114500156
R. Lipyanski, Automorphisms of the endomorphism semigroups of free linear algebras of homogeneous varieties, Linear Algebra Appl. 429 (2008), no. 1, 156–180. MR 2419147, DOI 10.1016/j.laa.2008.02.020
Inessa Levi, Automorphisms of normal transformation semigroups, Proc. Edinburgh Math. Soc. (2) 28 (1985), no. 2, 185–205. MR 806750, DOI 10.1017/S001309150002263X
Inessa Levi, Automorphisms of normal partial transformation semigroups, Glasgow Math. J. 29 (1987), no. 2, 149–157. MR 901661, DOI 10.1017/S0017089500006790
Inessa Levi, On the inner automorphisms of finite transformation semigroups, Proc. Edinburgh Math. Soc. (2) 39 (1996), no. 1, 27–30. MR 1375662, DOI 10.1017/S0013091500022732
I. Levi, On groups associated with transformation semigroups, Semigroup Forum 59 (1999), no. 3, 342–353. MR 1847649, DOI 10.1007/s002339900054
Inessa Levi, Congruences on normal transformation semigroups, Math. Japon. 52 (2000), no. 2, 247–261. MR 1793274
Inessa Levi, Nilpotent ranks of semigroups of partial transformations, Semigroup Forum 72 (2006), no. 3, 459–476. MR 2228540, DOI 10.1007/s00233-005-0538-5
I. Levi, D. B. McAlister, and R. B. McFadden, Groups associated with finite transformation semigroups, Semigroup Forum 61 (2000), no. 3, 453–467. MR 1832320, DOI 10.1007/PL00006041
I. Levi and R. B. McFadden, $S_n$-normal semigroups, Proc. Edinburgh Math. Soc. (2) 37 (1994), no. 3, 471–476. MR 1297316, DOI 10.1017/S0013091500018927
Inessa Levi and Steve Seif, Combinatorial techniques for determining rank and idempotent rank of certain finite semigroups, Proc. Edinb. Math. Soc. (2) 45 (2002), no. 3, 617–630. MR 1933743, DOI 10.1017/S0013091501000530
A. E. Liber, On symmetric generalized groups, Mat. Sbornik N.S. 33(75) (1953), 531–544 (Russian). MR 0059268
Martin W. Liebeck, The affine permutation groups of rank three, Proc. London Math. Soc. (3) 54 (1987), no. 3, 477–516. MR 879395, DOI 10.1112/plms/s3-54.3.477
Donald Livingstone and Ascher Wagner, Transitivity of finite permutation groups on unordered sets, Math. Z. 90 (1965), 393–403. MR 186725, DOI 10.1007/BF01112361
Andrea Lucchini and Federico Menegazzo, Generators for finite groups with a unique minimal normal subgroup, Rend. Sem. Mat. Univ. Padova 98 (1997), 173–191. MR 1492976
A. Lucchini, F. Menegazzo, and M. Morigi, Asymptotic results for transitive permutation groups, Bull. London Math. Soc. 32 (2000), no. 2, 191–195. MR 1734189, DOI 10.1112/S0024609399006591
A. Lucchini, F. Menegazzo, and M. Morigi, Asymptotic results for primitive permutation groups and irreducible linear groups, J. Algebra 223 (2000), no. 1, 154–170. MR 1738257, DOI 10.1006/jabr.1999.8081
Tomasz Łuczak and László Pyber, On random generation of the symmetric group, Combin. Probab. Comput. 2 (1993), no. 4, 505–512. MR 1264722, DOI 10.1017/S0963548300000869
K. D. Magill Jr., Semigroups of continuous functions, Amer. Math. Monthly 71 (1964), 984–988. MR 192464, DOI 10.2307/2311913
Kenneth D. Magill Jr., Semigroup structures for families of functions. I. Some homomorphism theorems, J. Austral. Math. Soc. 7 (1967), 81–94. MR 0207875
A. I. Mal′cev, Symmetric groupoids, Mat. Sbornik N.S. 31(73) (1952), 136–151 (Russian). MR 0050576
G. Mashevitzky and B. I. Plotkin, On automorphisms of the endomorphism semigroup of a free universal algebra, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 1085–1106. MR 2355687, DOI 10.1142/S0218196707003974
G. Mashevitzky, B. Plotkin, and E. Plotkin, Automorphisms of the category of free Lie algebras, J. Algebra 282 (2004), no. 2, 490–512. MR 2101073, DOI 10.1016/j.jalgebra.2003.09.038
G. Mashevitzky and Boris M. Schein, Automorphisms of the endomorphism semigroup of a free monoid or a free semigroup, Proc. Amer. Math. Soc. 131 (2003), no. 6, 1655–1660. MR 1953569, DOI 10.1090/S0002-9939-03-06923-5
Donald B. McAlister, Semigroups generated by a group and an idempotent, Comm. Algebra 26 (1998), no. 2, 515–547. MR 1604099, DOI 10.1080/00927879808826145
Annabelle McIver and Peter M. Neumann, Enumerating finite groups, Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 152, 473–488. MR 916229, DOI 10.1093/qmath/38.4.473
Peter M. Neumann, Primitive permutation groups and their section-regular partitions, Michigan Math. J. 58 (2009), no. 1, 309–322. MR 2526090, DOI 10.1307/mmj/1242071695
John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937
B. I. Plotkin. Seven Lectures on the Universal Algebraic Geometry. Preprint, Institute of Mathematics, Hebrew University (2000).
B. Plotkin and G. Zhitomirski, Automorphisms of categories of free algebras of some varieties, J. Algebra 306 (2006), no. 2, 344–367. MR 2271339, DOI 10.1016/j.jalgebra.2006.07.028
Boris Plotkin and Grigori Zhitomirski, On automorphisms of categories of universal algebras, Internat. J. Algebra Comput. 17 (2007), no. 5-6, 1115–1132. MR 2355689, DOI 10.1142/S0218196707004098
Maria Isabel Marques Ribeiro, Rank properties in finite inverse semigroups, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 3, 559–568. MR 1878658, DOI 10.1017/S0013091500021192
I. K. Rystsov, Quasioptimal bound for the length of reset words for regular automata, Acta Cybernet. 12 (1995), no. 2, 145–152. MR 1370976
J. Schreier, Über Abbildungen einer abstrakten Menge Auf ihre Teilmengen, Fund. Math. 28 (1936), 261–264.
R. P. Sullivan, Automorphisms of transformation semigroups. part 1, J. Austral. Math. Soc. 20 (1975), no. part 1, 77–84. MR 0372095
È. G. Šutov, Homomorphisms of the semigroup of all partial transformations, Izv. Vysš. Učebn. Zaved. Matematika 1961 (1961), no. 3 (22), 177–184 (Russian). MR 0150223
J. S. V. Symons, Normal transformation semigroups, J. Austral. Math. Soc. Ser. A 22 (1976), no. 4, 385–390. MR 437668, DOI 10.1017/s1446788700016232
Haobo Yang and Xiuliang Yang, Automorphisms of partition order-decreasing transformation monoids, Semigroup Forum 85 (2012), no. 3, 513–524. MR 3001597, DOI 10.1007/s00233-012-9430-2
Helmut Wielandt, Finite permutation groups, Academic Press, New York-London, 1964. Translated from the German by R. Bercov. MR 0183775