The cyclic sieving phenomenon. (English) Zbl 1052.05068
Let \(X\) be a finite set with an action of a cyclic group \(C\) of order \(n\). Let \(X(q)\) be a polynomial in \(q\) having nonnegative integer coefficients, with the property that \(X(1)=| X| \). Fix an isomorphism \(\omega\) of \(C\) with the complex \(n\)th roots of unity.
Proposition. For a triple \((X,X(q),C)\) the following are equivalent: (i) For every \(c\in C\), \([X(q)]_{q=\omega(c)}=| \{x\in X\;| \;c(x)=x\}| \). (ii) The coefficients \(a_l\) defined uniquely by the expansion \[ X(q)\equiv \sum_{l=0}^{n-1}a_lq^l\pmod{q^n-1} \] have the following interpretation: \(a_l\) counts the number of \(C\)-orbits on \(X\) for which the stabilizer order divides \(l\).
When either of these two conditions holds, we say that \((X,X(q),C)\) exhibits the cyclic sieving phenomenon. If \(| C| =2\), then condition (i) above is Stembridge’s \(q=-1\) phenomenon. In this paper it is shown that the cyclic sieving phenomenon appears in various situations, involving \(q\)-binomial coefficients, finite reflection groups, and some finite field \(q\)-analogues.
Theorem 1.6. Let \((W,S)\) be a finite Coxeter system and \(J\subseteq S\). Let \(C\) be a cyclic subgroup generated by a regular element. Let \(X\) be a set of cosets \(W/W_J\), and \(X(q)=W^J(q)\). Then \((X,X(q),C)\) exhibits the cyclic sieving phenomenon.
Proposition. For a triple \((X,X(q),C)\) the following are equivalent: (i) For every \(c\in C\), \([X(q)]_{q=\omega(c)}=| \{x\in X\;| \;c(x)=x\}| \). (ii) The coefficients \(a_l\) defined uniquely by the expansion \[ X(q)\equiv \sum_{l=0}^{n-1}a_lq^l\pmod{q^n-1} \] have the following interpretation: \(a_l\) counts the number of \(C\)-orbits on \(X\) for which the stabilizer order divides \(l\).
When either of these two conditions holds, we say that \((X,X(q),C)\) exhibits the cyclic sieving phenomenon. If \(| C| =2\), then condition (i) above is Stembridge’s \(q=-1\) phenomenon. In this paper it is shown that the cyclic sieving phenomenon appears in various situations, involving \(q\)-binomial coefficients, finite reflection groups, and some finite field \(q\)-analogues.
Theorem 1.6. Let \((W,S)\) be a finite Coxeter system and \(J\subseteq S\). Let \(C\) be a cyclic subgroup generated by a regular element. Let \(X\) be a set of cosets \(W/W_J\), and \(X(q)=W^J(q)\). Then \((X,X(q),C)\) exhibits the cyclic sieving phenomenon.
Reviewer: Alexandre A. Makhnev (Ekaterinburg)
MSC:
| 05E05 | Symmetric functions and generalizations |
| 20C30 | Representations of finite symmetric groups |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 05A30 | \(q\)-calculus and related topics |
| 05E10 | Combinatorial aspects of representation theory |
References:
| [1] | Andrews, G., The Friedman-Joichi-Stanton monotonicity conjecture at primes, Amer. Math. Soc. DIMACS Book Series, 64, 9-16 (2004) · Zbl 1079.11055 |
| [2] | C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group \(D_n\); C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group \(D_n\) |
| [3] | Barcelo, H.; Maule, R.; Sundaram, S., On counting permutations by pairs of congruence classes of major index, Electron. J. Combin, 9, R21 (2002) · Zbl 1007.05005 |
| [4] | M. Beck, A. Feingold, M. Weiner, Arithmetic partition sums and orbits of \(Z_n^{k\) |
| [5] | P. Brändén, \(qhJ\textbf{2}\textbf{n}χ\); P. Brändén, \(qhJ\textbf{2}\textbf{n}χ\) |
| [6] | F. Chapoton,; F. Chapoton, |
| [7] | Coxeter, H. S.M., Regular Complex Polytopes (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0732.51002 |
| [8] | N.G. de Bruijn, Generalization of Pólya’s fundamental theorem in enumerative combinatorial analysis, Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 (1959) 59-69.; N.G. de Bruijn, Generalization of Pólya’s fundamental theorem in enumerative combinatorial analysis, Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 (1959) 59-69. · Zbl 0085.00901 |
| [9] | Désarménien, J., Étude modulo \(n\) des statistiques Mahoniennes, Sém. Loth. Combin, 22, 27-35 (1990) |
| [10] | Drudge, K., On the orbits of Singer groups and their subgroups, Electron. J. Combin, 9, R15 (2002), (electronic) · Zbl 0998.20003 |
| [11] | Elashvili, A.; Jibladze, M.; Pataraia, D., Combinatorics of necklaces and “Hermite reciprocity”, J. Algebr. Combin, 10, 173-186 (1999) · Zbl 0940.13003 |
| [12] | Eng, O. D., Quotients of Poincaré polynomials evaluated at −1, J. Algebr. Combin, 13, 29-40 (2001) · Zbl 1021.20031 |
| [13] | Fulman, J., Applications of the Brauer complexcard shuffling, permutation statistics and dynamical systems, J. Algebra, 243, 96-122 (2001) · Zbl 1012.20042 |
| [14] | Fürlinger, J.; Hofbauer, J., \(q\)-Catalan numbers, J. Combin. Theory Ser. A, 40, 248-264 (1985) · Zbl 0581.05006 |
| [15] | G. Gasper, M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics and its Applications, Vol. 35, Cambridge University Press, Cambridge, 1990.; G. Gasper, M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics and its Applications, Vol. 35, Cambridge University Press, Cambridge, 1990. · Zbl 0695.33001 |
| [16] | Haiman, M., Conjectures on the quotient ring by diagonal invariants, J. Algebr. Combin, 3, 17-76 (1994) · Zbl 0803.13010 |
| [17] | Hardy, G.; Wright, E., An Introduction to the Theory of Numbers (1979), Oxford: Oxford New York · Zbl 0423.10001 |
| [18] | Hewett, T. J., Modular invariant theory of parabolic subgroups of \(GL_n(F_{q\) · Zbl 0866.55021 |
| [19] | H. Hiller, Geometry of Coxeter groups, Research Notes in Mathematics, Vol. 54, Pitman (Advanced Publishing Program), London, 1982.; H. Hiller, Geometry of Coxeter groups, Research Notes in Mathematics, Vol. 54, Pitman (Advanced Publishing Program), London, 1982. · Zbl 0483.57002 |
| [20] | Kraśkiewicz, W.; Weyman, J., Algebra of coinvariants and the action of a Coxeter element, Bayreuth Math. Schr, 63, 265-284 (2001) · Zbl 1037.20012 |
| [21] | Lascoux, A.; Leclerc, B.; Thibon, J.-Y., Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras and unipotent varieties, J. Math. Phys, 38, 1041-1068 (1997) · Zbl 0869.05068 |
| [22] | Littlewood, D., The Theory of Group Characters (1940), Oxford: Oxford New York · JFM 66.0093.02 |
| [23] | Macdonald, I. G., Symmetric Functions and Hall Polynomials (1995), Oxford University Press: Oxford University Press Oxford · Zbl 0487.20007 |
| [24] | Ramanathan, K., Some applications of Ramanujan’s trigonometrical sum \(C_m(n)\), Indian Acad. Sci. Sect. A, 20, 62-70 (1944) · Zbl 0063.06402 |
| [25] | Read, R. C., On the number of self-complementary graphs and digraphs, J. London Math. Soc, 38, 99-104 (1963) · Zbl 0116.15001 |
| [26] | Reiner, V., Non-crossing partitions for classical reflection groups, Discrete Math, 177, 195-222 (1997) · Zbl 0892.06001 |
| [27] | Reiner, V., Note on a theorem of Eng, Ann. Combin, 6, 117-118 (2002) · Zbl 1022.20017 |
| [28] | Reiner, V., Equivariant fiber polytopes, Doc. Math, 7, 113-132 (2002), (electronic) · Zbl 1141.52309 |
| [29] | V. Reiner, D. Stanton, P. Webb, Springer’s theorem for modular coinvariants of \(GLnFq\); V. Reiner, D. Stanton, P. Webb, Springer’s theorem for modular coinvariants of \(GLnFq\) |
| [30] | V. Reiner, D. Stanton, P. Webb, Springer’s regular elements over arbitrary fields, Manuscript, 2004 (at; V. Reiner, D. Stanton, P. Webb, Springer’s regular elements over arbitrary fields, Manuscript, 2004 (at · Zbl 1155.13005 |
| [31] | Shephard, G. C.; Todd, J. A., Finite unitary reflection groups, Canad. J. Math, 6, 274-304 (1954) · Zbl 0055.14305 |
| [32] | Simion, R., Noncrossing partitions, Formal power series and algebraic combinatorics (Vienna, 1997), Discrete Math, 217, 367-409 (2000) · Zbl 0959.05009 |
| [33] | Simion, R., A type-\(B\) associahedron, Adv. in Appl. Math, 30, 2-25 (2003) · Zbl 1047.52006 |
| [34] | Springer, T. A., Regular elements of finite reflection groups, Invent. Math, 25, 159-198 (1974) · Zbl 0287.20043 |
| [35] | Stanley, R. P., Weyl groups, the hard Lefschetz theorem and the Sperner property, SIAM J. Algebraic Discrete Methods, 1, 168-184 (1980) · Zbl 0502.05004 |
| [36] | Stanley, R. P., Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A, 76, 175-177 (1996) · Zbl 0859.05075 |
| [37] | R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge, 1997.; R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge, 1997. · Zbl 0889.05001 |
| [38] | R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62. Cambridge University Press, Cambridge, 1999.; R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62. Cambridge University Press, Cambridge, 1999. · Zbl 0928.05001 |
| [39] | Stanton, D.; White, D., A Schensted algorithm for rim hook tableaux, J. Combin. Theory Ser. A, 40, 211-247 (1985) · Zbl 0577.05001 |
| [40] | Stanton, D.; White, D., Constructive Combinatorics, Undergraduate Texts in Mathematics (1986), Springer: Springer New York · Zbl 0595.05002 |
| [41] | Stembridge, J. R., Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A, 68, 372-409 (1994) · Zbl 0809.05007 |
| [42] | Stembridge, J. R., On minuscule representations, plane partitions and involutions in complex Lie groups, Duke Math. J, 73, 469-490 (1994) · Zbl 0805.22006 |
| [43] | Stembridge, J. R., Canonical bases and self-evacuating tableaux, Duke Math. J, 82, 585-606 (1996) · Zbl 0869.17011 |
| [44] | von Sterneck, R. D., Ein Analogon zur additiven Zahlentheorie, Wien. Ber, 111, 1567-1601 (1902) · JFM 33.0196.01 |
| [45] | Wagon, S.; Wilf, H., When are subset sums equidistributed modulo m?, Electron J. Combin, 1, R3 (1994), (electronic) · Zbl 0816.11012 |
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.
