Applications of the Brauer complex: card shuffling, permutation statistics, and dynamical systems. (English) Zbl 1012.20042
Summary: By algebraic group theory, there is a map from the semisimple conjugacy classes of a finite group of Lie type to the conjugacy classes of the Weyl group. Picking a semisimple class uniformly at random yields a probability measure on conjugacy classes of the Weyl group. Using the Brauer complex, it is proved that this measure agrees with a second measure on conjugacy classes of the Weyl group induced by a construction of Cellini using the affine Weyl group. Formulas for Cellini’s measure in type \(A\) are found. This leads to new models of card shuffling and has interesting combinatorial and number-theoretic consequences. An analysis of type \(C\) gives another solution to a problem of Rogers in dynamical systems: the enumeration of unimodal permutations by cycle structure. The proof uses the factorization theory of palindromic polynomials over finite fields. Contact is made with symmetric function theory.
MSC:
| 20G40 | Linear algebraic groups over finite fields |
| 05A15 | Exact enumeration problems, generating functions |
| 20B30 | Symmetric groups |
| 20P05 | Probabilistic methods in group theory |
| 20E45 | Conjugacy classes for groups |
Keywords:
finite groups of Lie type; conjugacy classes; Brauer complex; probability measures; symmetric functions; dynamical systems; card shufflingReferences:
| [1] | Aldous, A., Random Walk on Finite Groups and Rapidly Mixing Markov Chains. Random Walk on Finite Groups and Rapidly Mixing Markov Chains, Lecture Notes in Mathematics, 986 (1983), Springer: Springer New York, p. 243-297 · Zbl 0514.60067 |
| [2] | Bayer, D.; Diaconis, P., Trailing the dovetail shuffle to its lair, Ann. Appl. Probab., 2, 294-313 (1992) · Zbl 0757.60003 |
| [3] | Bergeron, N., A hyperoctahedral analog of the free Lie algebra, J. Combin. Theory Ser. A, 58, 256-278 (1991) · Zbl 0759.17003 |
| [4] | Bergeron, F.; Bergeron, N., Orthogonal idempotents in the descent algebra of \(B_n\) and applications, J. Pure Appl. Algebra, 79, 109-129 (1992) · Zbl 0793.20004 |
| [5] | Bergeron, F.; Bergeron, N.; Garsia, A. M., Idempotents for the free Lie algebra and \(q\)-enumeration, Invariant Theory and Tableaux. Invariant Theory and Tableaux, IMA Vol. Math. Appl., 19 (1990), Springer: Springer New York · Zbl 0721.17006 |
| [6] | Bergeron, F.; Bergeron, N.; Howlett, R. B.; Taylor, D. E., A decomposition of the descent algebra of a finite Coxeter group, J. Algebraic Combin., 1, 23-44 (1992) · Zbl 0798.20031 |
| [7] | Bergeron, N.; Wolfgang, L., The decomposition of Hochschild cohomology and the Gerstenhaber operations, J. Pure Appl. Algebra, 104, 243-265 (1995) · Zbl 0851.16004 |
| [8] | Bidigare, P.; Hanlon, P.; Rockmore, D., A combinatorial description of the spectrum of the Tsetlin library and its generalization to hyperplane arrangements, Duke Math J., 99, 135-174 (1999) · Zbl 0955.60043 |
| [9] | Brown, K.; Diaconis, P., Random walks and hyperplane arrangements, Ann. Probab., 26, 1813-1854 (1998) · Zbl 0938.60064 |
| [10] | Carter, R., Finite Groups of Lie Type (1985), Wiley: Wiley New York · Zbl 0567.20023 |
| [11] | Cellini, P., A general commutative descent algebra, J. Algebra, 175, 990-1014 (1995) · Zbl 0832.20060 |
| [12] | Cellini, P., A general commutative descent algebra II. The Case \(C_n\), J. Algebra, 175, 1015-1026 (1995) · Zbl 0832.20061 |
| [13] | Diaconis, P., Group Representations in Probability and Statistics. Group Representations in Probability and Statistics, Lecture Notes Monograph Series, 11 (1988), Institute of Mathematical Statistics: Institute of Mathematical Statistics Hayward · Zbl 0695.60012 |
| [14] | Diaconis, P.; McGrath, M.; Pitman, J., Riffle shuffles, cycles, and descents, Combinatorica, 15, 11-20 (1995) · Zbl 0828.05003 |
| [15] | Elashvili, A.; Jibladze, M.; Pataraia, D., Combinatorics of necklaces and “Hermite reciprocity”, J. Algebraic Combin., 10, 173-188 (1999) · Zbl 0940.13003 |
| [16] | Fulman, J., The combinatorics of biased riffle shuffles, Combinatorica, 18, 173-184 (1998) · Zbl 0932.60007 |
| [17] | Fulman, J., Descent algebras, hyperplane arrangements, and shuffling cards, Proc. Amer. Math. Soc., 129, 965-973 (2001) · Zbl 0999.20030 |
| [18] | Fulman, J., Semisimple orbits of Lie algebras and card shuffling measures on Coxeter groups, J. Algebra, 224, 151-165 (2000) · Zbl 0971.60048 |
| [19] | Fulman, J., Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting, J. Algebra, 231, 614-639 (2000) · Zbl 0965.60029 |
| [20] | J. Fulman, Cellini’s descent algebra and semisimple conjugacy classes of finite groups of Lie type, preprint math.nt/9909121 at, xxx.lanl.gov.; J. Fulman, Cellini’s descent algebra and semisimple conjugacy classes of finite groups of Lie type, preprint math.nt/9909121 at, xxx.lanl.gov. |
| [21] | J. Fulman, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, parts I and II. Preprints math.co/0102176 and math.co/0104003 at, xxx.lanl.gov.; J. Fulman, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, parts I and II. Preprints math.co/0102176 and math.co/0104003 at, xxx.lanl.gov. · Zbl 1012.05154 |
| [22] | J. Fulman, P. M. Neumann, and, C. E. Praeger, A generating function approach to the enumeration of cyclic, separable, and semisimple matrices in the classical groups over finite fields, preprint.; J. Fulman, P. M. Neumann, and, C. E. Praeger, A generating function approach to the enumeration of cyclic, separable, and semisimple matrices in the classical groups over finite fields, preprint. · Zbl 1082.05097 |
| [23] | T. Gannon, The cyclic structure of unimodal permutations, preprint, math.DS/9906207 at, xxx.lanl.gov.; T. Gannon, The cyclic structure of unimodal permutations, preprint, math.DS/9906207 at, xxx.lanl.gov. · Zbl 0983.05005 |
| [24] | Garsia, A., Combinatorics of the free Lie algebra and the symmetric group, Analysis, et cetera (1990), Academic Press: Academic Press Boston, p. 309-382 · Zbl 0709.17003 |
| [25] | Gerstenhaber, M.; Schack, S. D., A Hodge type decomposition for commutative algebra cohomology, J. Pure. Appl. Algebra, 38, 229-247 (1987) · Zbl 0671.13007 |
| [26] | I. Gessel, Counting permutations by descents, greater index, and cycle structure, unpublished manuscript.; I. Gessel, Counting permutations by descents, greater index, and cycle structure, unpublished manuscript. |
| [27] | Gessel, I.; Reutenauer, C., Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, 64, 189-215 (1993) · Zbl 0793.05004 |
| [28] | Golomb, S., Irreducible polynomials, synchronization codes, primitive necklaces, and the cyclotomic algebra, Combinatorial Mathematics and its Applications (1969), Univ. North Carolina Press: Univ. North Carolina Press Durham, p. 358-370 · Zbl 0221.94008 |
| [29] | Hanlon, P., The action of \(S_n\) on the components of the Hodge decomposition of Hochschild homology, Michigan Math. J., 37, 105-124 (1990) · Zbl 0701.16010 |
| [30] | Hardy, G.; Wright, E., An Introduction to the Theory of Numbers (1979), Clarendon Press: Clarendon Press Oxford · Zbl 0423.10001 |
| [31] | Humphreys, J., Conjugacy Classes in Semisimple Algebraic Groups. Conjugacy Classes in Semisimple Algebraic Groups, Mathematical Surveys and Monographs, 43 (1995), American Mathematical Society: American Mathematical Society Providence · Zbl 0834.20048 |
| [32] | Humphreys, J., Reflection Groups and Coxeter Groups. Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, 29 (1990), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0725.20028 |
| [33] | Lalley, S., Cycle structure of riffle shuffles, Ann. Prob., 24, 49-73 (1996) · Zbl 0854.05007 |
| [34] | Lalley, S., Riffle shuffles and their associated dynamical systems, J. Theoret. Probab., 12, 903-932 (1999) · Zbl 0965.60022 |
| [35] | Macdonald, I., Symmetric Functions and Hall Polynomials (1995), Clarendon Press: Clarendon Press Oxford · Zbl 0824.05059 |
| [36] | Ramanathan, K. G., Some applications of Ramanujan’s trigonometrical sum \(C_m}(n)\), Indian Acad. Sci. Sect. A., 20, 62-70 (1944) · Zbl 0063.06402 |
| [37] | Reiner, V., Signed permutation statistics and cycle type, European J. Combin., 14, 569-579 (1993) · Zbl 0793.05006 |
| [38] | Reiner, V., Quotients of Coxeter complexes and \(P\)-partitions, Mem. Amer. Math. Soc., 95, vi (1992) · Zbl 0751.06002 |
| [39] | Rogers, T., Chaos in systems in population biology, Prog. Theoret. Biol., 6, 91-146 (1981) |
| [40] | Rogers, T.; Weiss, A., The number of orientation reversing cycles in the quadratic map, CMS Conf. Proc., 8, 703-711 (1986) · Zbl 0652.58035 |
| [41] | Shnider, S.; Sternberg, S., Quantum Groups. Quantum Groups, Graduate Texts in Mathematical Physics, II (1993), International Press: International Press Cambridge · Zbl 0845.17015 |
| [42] | R. Stanley, Generalized riffle shuffles and quasisymmetric functions, preprint math. CO/9912025 at, xxx.lanl.gov.; R. Stanley, Generalized riffle shuffles and quasisymmetric functions, preprint math. CO/9912025 at, xxx.lanl.gov. · Zbl 1010.05078 |
| [43] | J. Y. Thibon, The cycle enumerator of unimodal permutations, preprint, math. CO/0102051 at, xxx.lanl.gov.; J. Y. Thibon, The cycle enumerator of unimodal permutations, preprint, math. CO/0102051 at, xxx.lanl.gov. · Zbl 0988.05092 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
