The notion of descent set is classical both for permutations and for standard Young tableaux (SYT). Cellini introduced a natural notion of cyclic descent set for permutations, and Rhoades introduced such a notion for SYT, but only of rectangular shapes. In this paper, we describe cyclic descents for SYT of various other shapes. Motivated by these ndings, we de ne cyclic extensions of descent sets in a general context, and we show that they exist for SYT of almost all shapes. Finally, we introduce the ring of cyclic quasisymmetric functions and apply it to analyze the distributions of cyclic descents over permutations and SYT.
Introduction The notion of descent set, for permutations as well as for standard Young tableaux (SYT), is classical. Cellini introduced a natural notion of cyclic descent set for permutations, and Rhoades introduced such a notion for SYT | but only for rectangular shapes.
In [ER17a] and [AER18] we de ned cyclic descent set maps for SYT of various shapes; see Theorem 3.2 below and the remark following it. Motivated by these results, cyclic extensions of descent sets have been de ned in a general context and shown to exist for SYT of almost all shapes [ARR17]; see Theorem 4.1 below. The proof applies nonnegativity properties of Postnikov's toric Schur polynomials, providing a new interpretation of certain Gromov-Witten invariants. Finally, the ring of cyclic quasisymmetric functions has been introduced and studied in [AGRR+18], and further applied to analyze the resulting cyclic Eulerian distributions.
= [ 1; : : : ; n] in the symmetric group Sn on n letters is de ned as n i Des( ) := f1 i 1 : i > i+1g [n where [m] := f1; 2; : : : ; mg. For example, Des([2; 1; 4; 5; 3]) = f1; 4g. Its cyclic descent set was de ned by Cellini [Cel98] as cDes( ) := f1 n : i > i+1g [n]; with the convention n+1 := 1. For example, cDes([2; 1; 4; 5; 3]) = f1; 4; 5g. This cyclic descent set was further studied by Dilks, Petersen, Stembridge [DPS09] and others. It has the following important properties. Consider the two actions of the cyclic group Z, on Sn and on the power set of [n], in which the generator p of Z acts by Then for every permutation , one has the following three properties:
p [ 1; 2; : : : ; n 1; n] 7 !
p fi1; : : : ; ikg 7 ! [ n; 1; 2; : : : ; n 1]; fi1 + 1; : : : ; ik + 1g mod n: cDes( ) \ [n cDes(p( )) = p(cDes( ))
1] = Des( ) ? ( cDes( ) ( [n] (extension) (equivariance) (non-Escher) (1) (2) (3) (4) The term non-Escher refers to M. C. Escher's drawing \Ascending and Descending", which paradoxically depicts the impossible cases cDes( ) = ? and cDes( ) = [n].
There is also an established notion of descent set for a standard (Young) tableau (SYT) T of a skew shape = :
Des(T ) := f1 i n 1 : i + 1 appears in a lower row of T than ig [n For example, the following SYT T of shape = = (4; 3; 2)=(1; 1) has Des(T ) = f2; 3; 5g: 1 2 7 3 5 4 6 For the special case of an SYT T of rectangular shape, Rhoades [Rho10, Lemma 3.3] introduced a notion of cyclic descent set cDes(T ), possessing the above properties (2), (3) and (4) with respect to the Z-action in which the generator p acts on tableaux via Schutzenberger's jeu-de-taquin promotion operator. A similar concept of cDes(T ) and accompanying action p was introduced for two-row shapes and certain other skew shapes (see Subsection 3.2 for the list) in [AER18, ER17a], and used there to answer Schur positivity questions. 3 3.1
Cyclic descents: de nition and examples Let us begin by formalizing the concept of a cyclic extension. Recall the bijection p : 2[n] the cyclic shift i 7! i + 1 (mod n), for all i 2 [n]. ! 2[n] induced by De nition 3.1. Let T be a nite set. A descent map is any map Des : T ! 2[n 1]. A cyclic extension of Des is a pair (cDes; p), where cDes : T ! 2[n] is a map and p : T ! T is a bijection, satisfying the following axioms: for all T in T ,
(extension) cDes(T ) \ [n 1] = Des(T ); (equivariance) cDes(p(T )) = p(cDes(T ));
(non-Escher) ? ( cDes(T ) ( [n]: The non-Escher axiom is used to prove the (essential) uniqueness of the cyclic extension. 3.2 Cyclic extensions of descent maps have been given previously in several cases:
For T = Sn, the descent set Des( ) of a permutation was described in Section 2, as was Cellini's original cyclic extension (cDes; p). Note that n 2 is required for the non-Escher property.
Let T = SYT( ) where
= (ab) has rectangular shape, e.g.
Consider the usual notion of descent set Des(T ) on standard tableaux, as in Section 2. As mentioned earlier, Rhoades [Rho10, Lemma 3.3] showed that Schutzenberger's jeu-de-taquin promotion operation p provides a cyclic extension (cDes; p). Again, we require a; b 2 for the non-Escher property.
Theorem 3.2.
1. Let T = SYT( ) where e.g., There is a unique cyclic descent map cDes on T , de ned as follows: by the extension property, it su ces to specify when n 2 cDes(T ), and one decrees this to hold if and only if the entry T2;2 1 lies strictly west of T2;2 (namely, in the rst column of T ); see [AER18] for more details. Note that for most shapes in this family there are several possible shifting bijections p, so that the cyclic extension (cDes; p) is not unique. 2. Let T = SYT( ) with of two-row shape, namely = (n k; k) for 2 k n=2; e.g., There exists a cyclic extension of Des de ned as follows; see [AER18]. Decree that n 2 cDes(T ) if and only if both the last two entries in the second row of T are consecutive, and for every 1 < i < k, T2;i 1 > T1;i.
Other examples involve direct sums of shapes. Given t (skew) shapes 1; : : : ; t, the direct sum 1 2 t is the skew shape consisting of t diagrams of shapes 1; : : : ; t, for each i the diagram of i+1 is strictly northeast of the diagram of i, with no rows or columns in common.
Given any (strict) composition of n, that is, an ordered sequence of positive integers Pi i = n, consider the associated horizontal strip skew shape = ( 1; : : : ; t) with := ( 1) ( 2) ( t) whose rows, from southwest to northeast, have sizes 1; : : : ; t. For T in T = SYT( ), we de ne cDes(T ) := f1 i
n : i + 1 is in a lower row than ig; where n + 1 is interpreted as 1, as well as a bijection p : SYT( ) ! SYT( ) which rst replaces each entry j of T by j + 1 (mod n) and then re-orders each row to make it left-to-right increasing. One can check that this (cDes; p) is a cyclic extension of Des, with t 2 required for the non-Escher property. For example, when = (3; 4; 2) (and n = 9), one has the following standard tableaux T of shape : T = This generalizes the case of (cDes; p) on Sn, since for = (1n) = (1; 1; : : : ; 1) one has a bijection Sn ! SYT( ) which sends a permutation w to the tableau whose entries are w 1(1); : : : ; w 1(n) read from southwest to northeast; e.g., for n = 5, This bijection maps Cellini's cyclic extension (cDes; p) on Sn to the one on SYT( de ned above1.
Furthermore, for any nonempty partition 1, the partition
(1), e.g. ` n ) for
= (1; 1; : : : ; 1) has an explicit cyclic extension of Des described in [ER17a]. This case was, in fact, our original motivation, and the question of existence of a cyclic extension of Des on SYT( = ) appears there as [ER17a, Problem 5.5]. 4
Cyclic descents for standard Young tableaux Our rst main result is a necessary and su cient condition for the existence of a cyclic extension cDes of the descent map Des on the set SYT( = ) of standard Young tableaux of shape = , with an accompanying Z-action on SYT( = ) via an operator p, satisfying properties (2), (3) and (4). In this story, a special role is played by the skew shapes known as ribbons (connected skew shapes containing no 2 2 rectangle), and in particular hooks (straight ribbon shapes, namely = (n k; 1k) for k = 0; 1; : : : ; n 1). Early versions of [AER18] and [ER17a] conjectured the following result.
Theorem 4.1. [ARR17, Theorem 1.1] Let = be a skew shape. The descent map Des on SYT( = ) has a cyclic extension (cDes; p) if and only if = is not a connected ribbon. Furthermore, for all J [n], all such cyclic extensions share the same cardinalities #cDes 1(J ).
Our strategy for proving Theorem 4.1 is inspired by a result of Gessel [Ges84, Theorem 7] that we recall here. For a subset J = fj1 < : : : < jtg [n 1], the composition (of n) (J; n) := (j1; j2 j1; j3 j2; : : : ; jt jt 1; n jt) de nes a connected ribbon having the entries of (J; n) as row lengths, and thus an associated (skew) ribbon Schur function (5) (6) 1This cyclic descent map can be further generalized to strips, which are the disconnected shapes each of whose connected components consists of either one row or one column; see [AER18].
s (J;n) :=
X ( 1)#(JnI)h (I;n) ? I J with the following property: for any skew shape = , the descent map Des : SYT( = ) given by ! 2[n 1] has ber sizes #Des 1(J ) = hs = ; s (J;n)i (8J [n where h ; i is the usual inner product on symmetric functions.
By analogy, for a subset ? 6= J = fj1 < j2 < : : : < jtg [n] we de ne the corresponding cyclic composition of n as cyc(J; n) := (j2 j1; : : : ; jt jt 1; j1 + n jt); with cyc(J; n) := (n) when J = fj1g; note that cyc(?; n) is not de ned. The corresponding a ne (or cyclic) ribbon Schur function is then de ned as s~ cyc(J;n) :=
X ( 1)#(JnI)h cyc(I;n): ?6=I J We then collect enough properties of this function to show that there must exist a map cDes : SYT( = ) ! 2[n] and a Z-action p on SYT( = ), as in Theorem 4.1, such that ber sizes are given by #cDes 1(J ) = hs = ; s~ cyc(J;n)i (8 ? ( J ( [n]): The nonnegativity of this inner product when = is not a connected ribbon ultimately relies on relating s~ cyc(J;n) to a special case of Postnikov's toric Schur polynomials, with their interpretation in terms of Gromov-Witten invariants for Grassmannians [Pos05]. (7) (8) (9) (10) 5 5.1
Cyclic quasisymmetric functions
Recall from [Ges84] the following basic de nitions: A quasi-symmetric function is a formal power series f 2 Z[[x1; x2; : : :]] of bounded degree such that, for any t 1, any two increasing sequences i1 < < it and i01 < m1< i0txoim0f tpoinsitfivaerienteeqguearls., aDnednaontey bseyquQeSnycme(tmh1e; s:e:t: ;omf ta)llofqpuaossii-tsivyemimnteetgreicrs,futnhcetcioones, caienndtsboyf QximS1y1 mn xtimht et and xi01 t set of all quasi-symmetric functions which are homogeneous of degree n.
The fundamental quasi-symmetric function corresponding to a subset J [n
1] is de ned by Fn;J :=
X xi1 xin ; where the sum extends over all sequences (i1; : : : ; in) of positive integers such that j 2 J ) ij < ij+1 and j 62 J ) ij ij+1. The set fFn;J : J [n 1]g forms a basis for the additive abelian group QSymn.
The cyclic analogues of these concepts are introduced in [AGRR+18].
De nition 5.1. A cyclic quasi-symmetric function is a formal power series f 2 Z[[x1; x2; : : :]] of bounded degree such that, for any t 1, any two increasing sequences i1 < < it and i01 < < i0t of positive integers, any sequence m = (m1; : : : ; mt) of positive integers, and any cyclic shift m0 = (m01; : : : ; m0t) of m, the coe cients of xim1 1 ximt t and xim01 01 xim0t 0t in f are equal.
Denote by cQSym the set of all cyclic quasi-symmetric functions, and by cQSymn the set of all cyclic quasisymmetric functions which are homogeneous of degree n.
Observation 5.2. QSym, cQSym and the set Sym of symmetric functions (sometimes denoted abelian groups satisfying
It is not too di cult to check that they are also rings, that is, closed under the multiplication operation on power series. For Sym; QSym this is well-known; the proof for cQSym is given in [AGRR+18]. ) are graded
(11) 5.2
De nition 5.3. For each subset J [n] denote by Pnc;yJc the set of all pairs (w; k) consisting of a word w = (w1; : : : ; wn) 2 Nn and an index k 2 [n] which satisfy (i) The word w is \cyclically weakly increasing" from index k, namely wk wk 1. wk+1 : : : wn w1 : : : (ii) If j 2 J then wj 6= wj+1, where indices are computed modulo n. (This condition is vacuous for J = ?.) Remark 5.4. The index k is uniquely determined by the word w, unless all the letters of w are equal; in which case, any index k 2 [n] will do. These \constant words" are relevant only for J = ?, and the de nition implies that each of them is counted n times (and not just once) in Pnc;y?c .
Example 5.5. Let n = 5 and J = f1; 3g. The pairs (12345; 1), (23312; 4) and (23122; 3) are in P5c;yfc1;3g (see Figure 1), but the pairs (12354; 1), (22312; 4) and (23112; 3) are not.
2 3 3 5 ^ 4 1 3 2 ^ 1
J (mod n)g be the stabilizer of J under the action of Z=nZ by cyclic shifts, De nition 5.6. The fundamental cyclic quasisymmetric function corresponding to a subset J by [n] is de ned Fnc;yJc := dn;1J
X (w;k)2Pncy;Jc xw1 xw2 xwn : Let 2[n] be the set of all nonempty subsets of [n], and let c2[n] be the set of orbits of elements of 2[0n] under 0 0 cyclic shifts. If J and J 0 are in the same orbit then Fncy;Jc = Fnc;yJc0 .
Theorem 5.7. The set fFnc;yJc : J 2 c2[0n]g is a Z-basis for cQSymn.
Furthermore, letting s = be the skew Schur function indexed by a non-ribbon shape = , we have
X The distribution of descents on sets of permutations and other combinatorial objects, known as the Eulerian distribution, has been studied extensively; see, e.g., [BBS09], [Pet15, p. 91] and references therein. In this section we study the distribution of cyclic descents over SYT and compare it to its distribution over permutations. 6.1
The descent number is the size of the descent set. For any skew shape = of size n there is a known expression [Sta99, equation (7.96)] for the generating function of the descent number, des, on standard Young tableaux of shape = :
X tdes(T ) = (1 t)n+1 X s = (1m+1)tm: Here s = (1m) is the specialization of the skew Schur function s = (x1; x2; : : :) given by x1 = : : : = xm = 1 and xm+1 = : : : = 0. Note that when = ? this becomes even more explicit, through the hook-content formula [Sta99, Cor. 7.21.4] for the specialization s (1m). In particular, for the skew shape (1) n this gives the well-known Carlitz formula for the Eulerian distribution on Sn:
An analogous expression for the cyclic descent number cdes is proved in [ARR17].
Corollary 6.1. For any skew shape = of size n which is not a connected ribbon,
Sdnes(t) :=
X tdes(w) = (1 t)n+1 X (m + 1)ntm
X In particular, for the skew shape (1) n this gives
Scndes(t) :=
X tcdes(w) = n(1 t)n X mn 1tm = nt Sdnes1(t) (n 2): w2Sn Next we compare the distribution of cDes on SYT( ) to the distribution of cDes on Sn. Recall [Sag01, Theorem 3.1.1 and x5.6 Ex. 22(a)] that the Robinson-Schensted correspondence is a bijection between Sn and the set of pairs of standard Young tableaux of the same shape (and size n), having the property that if w 7! (P; Q) then Des(w) = Des(Q). Consequently
X tDes(w) = X f
X
tDes(T ): w2Sn `n
T 2SYT( ) Here tS := Qi2S ti for S f1; 2; : : :g, while ` n means is a partition of n, and f := #SYT( ). Note that Theorem 4.1 implies that any non-hook shape , as well as any disconnected skew shape = , will have PT 2SYT( = ) tcDes(T ) well-de ned and independent of the choice of cyclic extension (cDes; p) for Des on SYT( = ). Recall from Section 3 the notation for direct sum of shapes.
By Equation (
2 X tcDes(w) =
X f w2Sn non-hook `n
X T 2SYT( ) tcDes(T ) + k=1 nX1 n 2 k 1
X T 2SYT((1k) (n k)) tcDes(T ); where cDes is de ned on Sn by Cellini's formula (1) and on standard Young tableaux (of the relevant shapes) as in Theorem 4.1.
The explicit description of the unique cyclic descent map on near-hook SYT given in [AER18], is applied there to deduce the following.
1. For any n
2
We now focus on = = (1) n, where we can take T = Sn and use the extra symmetry to get more re ned
results. Consider the multivariate generating functions
(
ScnDes(t) tn=0 =
ci SnDes1(t) tn=0 :
n 1
X ti
i=1
Remark 6.6. Formulas (
SnDes(t) = SnDes(t1; : : : ; tn 1) := ScnDes(t) = ScnDes(t1; : : : ; tn 1; tn) :=
Note that SnDes(t) and ScnDes(t) are, respectively, the ag h-polynomials for the type An 1 Coxeter complex and for the reduced Steinberg torus considered by Dilks, Petersen, and Stembridge [DPS09]. The two are related by an obvious specialization
ScnDes(t) tn=1 = SnDes(t): c(ti) = ti+1 (mod n).
2, one has On the other hand, ScnDes(t) and SnDes1(t) are also related in a slightly less obvious way. De ne an action of the cyclic group Z=nZ = hci = fe; c; c2; ; cn 1g on Z[t1; : : : ; tn] by shifting subscripts modulo n, i.e.
ScnDes(t) = n X ci tn SnDes1(t) i=1
ScnDes(t) = g(t) + t[n]g(t 1); SnDes(t) = " n
X ti ciSnDes1(t)
# i=1 tn=1
: Scndes(t; u) :=
w2Sn
One can specialize ScnDes(t) to a bivariate generating function by setting t1 = t2 = and Petersen [Pet05].
= tn 1 := t and tn := u. The following result generalizes an observation of Fulman [Ful00]
2 one has Scndes(t; u) = nt + (u t) d dt t
(21) Remark 6.8. The coe cients of f (t) = ddt tSdnes1(t) appear as OEIS entry A065826.
The preceding calculations lead to an exponential generating function for Scndes(u; t), generalizing work of Petersen [Pet15, Proposition 14.4]. For more details see [ARR17, x6]. 7
Final remarks and open problems Detailed proofs of Theorems 4.1 and 6.3 may be found in the full version paper [ARR17]. Our proof of the existence of (cDes; p) in Theorem 4.1, whose strategy was sketched above, is indirect and involves arbitrary choices.
Problem 7.1. Find a natural, explicit map cDes and cyclic action p on SYT( = ) as in Theorem 4.1. Problem 7.2. Find a Robinson-Schensted-style bijective proof of Theorem 6.3.
For J = fj1; ; jtg
Corollary 7.3. Let = be a skew shape of size n which is not a connected ribbon. For any J cyclic extension cDes of the usual descent map on SYT( = ), the ber size Problem 7.4. For a solution of Problem 7.1, nd an involution on SYT( = ) which sends the cyclic descent set to its negative.
Problem 7.5. For non-ribbon shapes = , can one choose the operator p in Theorem 4.1 and a polynomial X(q) to obtain a cyclic sieving phenomenon (CSP) ?
This problem was solved by Rhoades [Rho10] for rectangular shapes and by Pechenik [Pec14] for shapes (k; k; 1n 2k). Recalling from [ER17a] the cyclic descent extension for SYT( (1)), Equation (10) in the current paper has been applied in [ARS+18] to obtain a re ned CSP on SYT of these skew shapes.
Thanks to the anonymous referees for their useful comments, which led to an improved presentation. [AGRR+18] R. M. Adin, I. Gessel, V. Reiner and Y. Roichman. Cyclic quasisymmetric functions. In preparation.
Discrete Mathematics and Theoretical Computer Science, 11:95-115, 2009. [Bjo84] A. Bjorner. Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings.
Advances in Mathematics, 52:173{212, 1984. [Bon12] M. Bona. Combinatorics of Permutations, 2nd edition. Discrete Mathematics and its Applications, CRC Press, Boca Raton, 2012. interpretation of positroid classes.
At [Pec14] O. Pechenik. Cyclic sieving of increasing tableaux and small Schrder paths. Journal of Combinatorial
Theory Series A, 125:357-378, 2014. [Pet05] T. K. Petersen. Cyclic descents and P -partitions. Journal of Algebraic Combinatorics, 22:343-375, 2005. [Pet15] T. K. Petersen. Eulerian numbers. Birkhauser Advanced Texts, Birkhauser/Springer, New York, 2015. [Pos05] A. Postnikov. A ne approach to quantum Schubert calculus. Duke Mathematical Journal, 128:473{509, 2005. [Rho10] B. Rhoades. Cyclic sieving, promotion, and representation theory. Journal of Combinatorial Theory
Series A, 117:38{76, 2010. [Sag01] B. E. Sagan. The symmetric group: Representations, combinatorial algorithms, and symmetric functions, 2nd edition. Graduate Texts in Mathematics 203. Springer-Verlag, New York, 2001.