Cycle type factorizations in GL n 𝔽 q
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1427-1459.

Recent work by Huang, Lewis, Morales, Reiner, and Stanton suggests that the regular elliptic elements of GL n 𝔽 q are somehow analogous to the n-cycles of the symmetric group. In 1981, Stanley enumerated the factorizations of permutations into products of n-cycles. We study the analogous problem in GL n 𝔽 q of enumerating factorizations into products of regular elliptic elements. More precisely, we define a notion of cycle type for GL n 𝔽 q and seek to enumerate the tuples of a fixed number of regular elliptic elements whose product has a given cycle type. In some cases, we provide explicit formulas. Our main tool is a standard character-theoretic technique due to Frobenius, which we make use of by finding simplified formulas for the necessary character values. For every case in which we are not able to compute an explicit formula, we at least determine the asymptotic behavior. We conclude with some results about the polynomiality of our enumerative formulas and some open problems.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.259
Classification: 05A15, 20C15, 11T06
Keywords: factorization enumeration, cycle type, $q$-analogues
Gordon, Graham 1

1 University of Washington Seattle, WA 98195
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{ALCO_2022__5_6_1427_0,
     author = {Gordon, Graham},
     title = {Cycle type factorizations in $\protect \mathrm{GL}_n \protect \mathbb{F}_q\protect $},
     journal = {Algebraic Combinatorics},
     pages = {1427--1459},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.259},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.259/}
}
TY  - JOUR
AU  - Gordon, Graham
TI  - Cycle type factorizations in $\protect \mathrm{GL}_n \protect \mathbb{F}_q\protect $
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1427
EP  - 1459
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.259/
DO  - 10.5802/alco.259
LA  - en
ID  - ALCO_2022__5_6_1427_0
ER  - 
%0 Journal Article
%A Gordon, Graham
%T Cycle type factorizations in $\protect \mathrm{GL}_n \protect \mathbb{F}_q\protect $
%J Algebraic Combinatorics
%D 2022
%P 1427-1459
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.259/
%R 10.5802/alco.259
%G en
%F ALCO_2022__5_6_1427_0
Gordon, Graham. Cycle type factorizations in $\protect \mathrm{GL}_n \protect \mathbb{F}_q\protect $. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1427-1459. doi : 10.5802/alco.259. https://alco.centre-mersenne.org/articles/10.5802/alco.259/

[1] Bertram, E. A.; Wei, V. K. Decomposing a permutation into two large cycles: an enumeration, SIAM J. Algebraic Discrete Methods, Volume 1 (1980) no. 4, pp. 450-461 | DOI | MR

[2] Boccara, G. Nombre de représentations d’une permutation comme produit de deux cycles de longueurs données, Discrete Math., Volume 29 (1980) no. 2, pp. 105-134 | DOI | MR

[3] Bóna, M.; Pittel, B. On the cycle structure of the product of random maximal cycles, Sém. Lothar. Combin., Volume 80 ([2019–2021]), Paper no. Art. B30b, 37 pages | MR

[4] Brickman, L.; Fillmore, P. A. The invariant subspace lattice of a linear transformation, Canad. J. Math., Volume 19 (1967), pp. 810-822 | MR

[5] Chapuy, G.; Stump, C. Counting factorizations of Coxeter elements into products of reflections, J. Lond. Math. Soc. (2), Volume 90 (2014) no. 3, pp. 919-939 | DOI | MR

[6] Dénes, J. 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., Volume 4 (1959), pp. 63-71 | MR

[7] Dummit, D. S.; Foote, R. M. Abstract algebra, John Wiley & Sons, Inc., Hoboken, NJ, 2004, xii+932 pages | MR

[8] Ekedahl, R.; Lando, S.; Shapiro, M.; Vainshtein, A. Hurwitz numbers and intersections on moduli spaces of curves, Invent. Math., Volume 146 (2001) no. 2, pp. 297-327 | DOI | MR

[9] Frobenius, F. G. Gesammelte Abhandlungen. Bände I, II, III, Herausgegeben von J.-P. Serre, Springer-Verlag, Berlin-New York, 1968, Vol. I: vii+650 pp. (1 plate); Vol. II: ii+733 pp.; Vol. III: iv+740 pages | MR

[10] Fulman, J. Cycle indices for the finite classical groups, J. Group Theory, Volume 2 (1999) no. 3, pp. 251-289 | DOI | MR

[11] Fulton, W. Young tableaux, London Mathematical Society Student Texts, 35, Cambridge University Press, Cambridge, 1997, x+260 pages | MR

[12] Fulton, W.; Harris, J. Representation theory, Graduate Texts in Mathematics, 129, Springer-Verlag, New York, 1991, xvi+551 pages | MR

[13] Gauss, C. F. Disquisitiones arithmeticae, Yale University Press, New Haven, Conn.-London, 1966, xx+472 pages (Translated into English by Arthur A. Clarke, S. J) | MR

[14] Goulden, I. P.; Jackson, D. M. The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, European J. Combin., Volume 13 (1992) no. 5, pp. 357-365 | DOI | MR

[15] Green, J. A. The characters of the finite general linear groups, Trans. Amer. Math. Soc., Volume 80 (1955), pp. 402-447 | DOI | MR

[16] Huang, J.; Lewis, J. B.; Reiner, V. Absolute order in general linear groups, J. Lond. Math. Soc. (2), Volume 95 (2017) no. 1, pp. 223-247 | MR

[17] Jackson, D. M. Counting cycles in permutations by group characters, with an application to a topological problem, Trans. Amer. Math. Soc., Volume 299 (1987) no. 2, pp. 785-801 | DOI | MR

[18] Kung, J. P. S. The cycle structure of a linear transformation over a finite field, Linear Algebra Appl., Volume 36 (1981), pp. 141-155 | DOI | MR

[19] Lando, S. K.; Zvonkin, A. K. Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, 141, Springer-Verlag, Berlin, 2004, xvi+455 pages (With an appendix by Don B. Zagier) | DOI | MR

[20] Lehrer, G. I. The cohomology of the regular semisimple variety, J. Algebra, Volume 199 (1998) no. 2, pp. 666-689 | MR

[21] Lewis, J. B.; Morales, A. H. GL n (𝔽 q )-analogues of factorization problems in the symmetric group, European J. Combin., Volume 58 (2016), pp. 75-95 | DOI | MR

[22] Lewis, J. B.; Reiner, V.; Stanton, D. Reflection factorizations of Singer cycles, J. Algebraic Combin., Volume 40 (2014) no. 3, pp. 663-691 | DOI | MR

[23] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995

[24] Murnaghan, F. D. On the Representations of the Symmetric Group, Amer. J. Math., Volume 59 (1937) no. 3, pp. 437-488 | DOI | MR

[25] Nakayama, T. On some modular properties of irreducible representations of a symmetric group. I, Jpn. J. Math., Volume 18 (1941), pp. 89-108 | MR

[26] Sagan, B. E. The symmetric group, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages | MR

[27] Serre, J.-P. Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977, x+170 pages (Graduate Texts in Mathematics, Vol. 42) | MR

[28] Stanley, R. P. Factorization of permutations into n-cycles, Discrete Math., Volume 37 (1981) no. 2-3, pp. 255-262 | DOI | MR

[29] Stanley, R. P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages (With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin) | DOI | MR

[30] Stanley, R. P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR

[31] Steinberg, R. A geometric approach to the representations of the full linear group over a Galois field, Trans. Amer. Math. Soc., Volume 71 (1951), pp. 274-282 | DOI | MR

[32] Stong, R. Some asymptotic results on finite vector spaces, Adv. in Appl. Math., Volume 9 (1988) no. 2, pp. 167-199 | DOI | MR

[33] Vakil, R. Genus 0 and 1 Hurwitz numbers: recursions, formulas, and graph-theoretic interpretations, Trans. Amer. Math. Soc., Volume 353 (2001) no. 10, pp. 4025-4038 | DOI | MR

[34] Walkup, D. W. How many ways can a permutation be factored into two n-cycles?, Discrete Math., Volume 28 (1979) no. 3, pp. 315-319 | DOI | MR

Cited by Sources: