Realization of permutations of even degree by products of three fixed-point-free involutions

F. M. Malyshev

Sbornik. Mathematics, Tome 215 (2024) no. 12, pp. 1720-1754

Résumé

We consider representations of a permutation $\pi$ of degree $2n$, $n\geqslant3$, by a product of three so-called pairwise-cycle permutations, all of whose cycles have length $2$. This is a valid question for even permutations if $n$ is even and for odd permutations if $n$ is odd. We prove constructively that for $n\geqslant4$, $n\neq8$, such a representation holds for all permutations $\pi$ of the same parity as $n$, apart from four exceptional conjugacy classes. For $n=8$ there are five exceptional conjugacy classes, and for $n=3$ there is one such class. Bibliography: 32 titles.

Détail

Keywords: cyclic structure, products of involutions, cubic graphs.
Mots-clés : permutations, involutions

Bibliographie

[1] N. Bourbaki, Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: Systèmes de racines, Actualites Sci. Indust., 1337, Hermann, Paris, 1968, 288 pp. | MR | Zbl

[2] E. Artin, Geometric algebra, Interscience Publishers, Inc., New York–London, 1957, x+214 pp. | MR | Zbl

[3] P. R. Halmos and S. Kakutani, “Products of symmetries”, Bull. Amer. Math. Soc., 64 (1958), 77–78 | DOI | MR | Zbl

[4] H. Radjavi, “Products of Hermitian matrices and symmetries”, Proc. Amer. Math. Soc., 21 (1969), 369–372 | DOI | MR | Zbl

[5] A. R. Sampson, “A note on a new matrix decomposition”, Linear Algebra Appl., 8:5 (1974), 459–463 | DOI | MR | Zbl

[6] W. C. Waterhouse, “Factoring unimodular matrices”, in “Solutions of advanced problems: 5876”, Amer. Math. Monthly, 81:9 (1974), 1035 | DOI | MR

[7] W. H. Gustafson, P. R. Halmos and H. Radjavi, “Products of involutions”, Linear Algebra Appl., 13:1–2 (1976), 157–162 | DOI | MR | Zbl

[8] G. Moran, “Permutations as products of $k$ conjugate involutions”, J. Combin. Theory Ser. A, 19:2 (1975), 240–242 | DOI | MR | Zbl

[9] R. W. Carter, “Simple groups and simple Lie algebras”, J. London Math. Soc., 40 (1965), 193–240 | DOI | MR | Zbl

[10] Seminar on algebraic groups and related finite groups (Inst. Adv. Study, Princeton, NJ 1968/69), Lecture Notes in Math., 131, Springer, Berlin, 1970, viii+321 pp. | DOI | MR | Zbl

[11] N. T. Petrov, “On the length of simple groups”, Soviet Math. Dokl., 14 (1973), 127–131 | MR | Zbl

[12] J. Dénes, “The representation of a permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 4 (1959), 63–71 | MR | Zbl

[13] S. Piccard, “Sur les bases du groupe symétrique et du groupe alternant”, Comment. Math. Helv., 11:1 (1938), 1–8 | Zbl

[14] V. G. Bardakov, “Expansion of even permutations into two factors of given cyclic structure”, Discrete Math. Appl., 3:4 (1993), 385–406 | DOI | MR | Zbl

[15] V. G. Bardakov, “Even permutations not representable in the form of a product of two permutations of given order”, Math. Notes, 62:2 (1997), 141–147 | DOI | MR | Zbl

[16] V. L. Kompel'maher and V. A. Liskovets, “Successive generation of permutations by means of a transposition basis”, Kibernetika (Kiev), 1975, no. 3, 17–21 (Russian) | MR | Zbl

[17] V. I. Sushchanskij and R. A. Voskanyan, “On systems of generators of symmetric and alternating groups containing only cycles of the same length”, Questions in group theory and homological algebra, Yaroslavl' State University, Yaroslavl', 1985, 43–49 (Russian) | MR | Zbl

[18] A. Yu. Zubov, “On the representation of substitutions as products of a transposition and a full cycle”, J. Math. Sci. (N.Y.), 166:6 (2010), 710–724 | DOI | MR | Zbl

[19] M. T. Lugo, Profiles of large combinatorial structures, PhD Thesis, Univ. Pennsylvania, 2010, 263 pp. | MR

[20] A. Yu. Zubov, “Circular inversions of permutations and their use in sorting problems”, Prikl. Diskretn. Mat., 2016, no. 1(31), 13–31 (Russian) | DOI | MR | Zbl

[21] V. G. Mikhailov, “The number of decompositions of a random permutation in a composition of two involutions with a given cycle in one of the factors”, Mat. Vopr. Kriptografii, 8:1 (2017), 80–94 (Russian) | DOI | MR | Zbl

[22] L. Bugay, “Some involutions which generate the finite symmetric group”, Math. Sci. Appl. E-Notes, 8:1 (2020), 25–28 | DOI

[23] J. L. Brenner, “Covering theorems for FINANSIGS VIII – almost all conjugacy classes in $A_n$ have exponent $\leqslant\!4$”, J. Austral. Math. Soc. Ser. A, 25:2 (1978), 210–214 | DOI | MR | Zbl

[24] F. M. Malyshev, “Realization of even permutations of even degree by products of four involutions without fixed points”, Discrete Math. Appl., 34:5 (2024), 263–276 | DOI

[25] R. Ree, “A theorem on permutations”, J. Combin. Theory Ser. A, 10:2 (1971), 174–175 | DOI | MR | Zbl

[26] W. Feit, R. Lyndon and L. Scott, “A remark about permutations”, J. Combin. Theory Ser. A, 18:2 (1975), 234–235 | DOI | MR | Zbl

[27] Y. Dvir, “Covering properties of permutation groups”, Products of conjugacy classes in groups, Lecture Notes in Math., 1112, Springer-Verlag, Berlin, 1985, 197–221 | DOI | MR | Zbl

[28] G. Moran, “Products of involution classes in infinite symmetric groups”, Trans. Amer. Math. Soc., 307:2 (1988), 745–762 | DOI | MR | Zbl

[29] M. È. Tuzhilin, “Generation of the alternating group by semiregular involutions”, Prikl. Diskr. Mat., 2009, Suppl. 3 (2010), 14–15 (Russian) | Zbl

[30] C. P. Bonnington and C. H. C. Little, The foundations of topological graph theory, Springer-Verlag, New York, 1995, x+178 pp. | DOI | MR | Zbl

[31] G. Ringel, Map color theorem, Grundlehren Math. Wiss., 209, Springer-Verlag, New York–Heidelberg, 1974, xii+191 pp. | DOI | MR | Zbl

[32] L. S. Pontryagin, Foundations of combinatorial topology, 2nd ed., Nauka, Moscow, 1976, 136 pp. ; English transl. of 1st ed. Graylock Press, Rochester, NY, 1952, xii+99 pp. | MR | Zbl | MR | Zbl