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 defined 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 defined 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.

Background

The descent set of a permutation π = [π 1 , . . . , π n ] in the symmetric group S n on n letters is defined as

Des(π) := {1 ≤ i ≤ n − 1 : π i > π i+1 } ⊆ [n − 1],

where [m] := {1, 2, . . . , m}. For example, Des([2, 1, 4, 5, 3]) = {1, 4}. Its cyclic descent set was defined by Cellini [Cel98] as cDes(π) := {1 ≤ i ≤ n :

π i > π i+1 } ⊆ [n],(1)

with the convention π n+1 := π 1 . For example, cDes([2, 1, 4, 5, 3]) = {1, 4, 5}. 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 S n and on the power set of [n], in which the generator p of Z acts by

[π 1 , π 2 , . . . , π n−1 , π n ] p −→ [π n , π 1 , π 2 , . . . , π n−1 ], {i 1 , . . . , i k } p −→ {i 1 + 1, . . . , i k + 1} mod n.

Then for every permutation π, one has the following three properties:

cDes(π) ∩ [n − 1] = Des(π) (extension) (2) cDes(p(π)) = p(cDes(π)) (equivariance) (3) ∅ cDes(π) [n] (non-Escher)(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 ) := {1 ≤ i ≤ n − 1 : i + 1 appears in a lower row of T than i} ⊆ [n − 1].

For example, the following SYT T of shape λ/µ = (4, 3, 2)/(1, 1) has Des(T ) = {2, 3, 5}:

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 Schützenberger'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.

Cyclic descents: definition and examples

Definition

Let us begin by formalizing the concept of a cyclic extension. Recall the bijection p : 2 The non-Escher axiom is used to prove the (essential) uniqueness of the cyclic extension.

[n] −→ 2 [n] induced by the cyclic shift i → i + 1 (mod n), for all i ∈ [n].

Examples

Cyclic extensions of descent maps have been given previously in several cases:

• For T = S n , 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 λ = (a b ) has rectangular shape, e.g.

λ = (5 3 ) =

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 Schützenberger's jeu-de-taquin promotion operation p provides a cyclic extension (cDes, p). Again, we require a, b ≥ 2 for the non-Escher property.

New examples are given in [AER18].

Theorem 3.2.

1. Let T = SYT(λ) where λ is a hook plus internal corner, namely λ = (n − 2 − k, 2, 1 k ) for 0 ≤ k ≤ n − 4; e.g., λ = (8, 2, 1, 1, 1) =

There is a unique cyclic descent map cDes on T , defined as follows: by the extension property, it suffices to specify when n ∈ cDes(T ), and one decrees this to hold if and only if the entry T 2,2 − 1 lies strictly west of T 2,2 (namely, in the first 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., λ = (8, 3) =

There exists a cyclic extension of Des defined as follows; see [AER18]. Decree that n ∈ 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, T 2,i−1 > T 1,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 α = (α 1 , . . . , α t ) with i α i = n, consider the associated horizontal strip skew shape

α ⊕ := (α 1 ) ⊕ (α 2 ) ⊕ • • • ⊕ (α t )

whose rows, from southwest to northeast, have sizes α 1 , . . . , α t . For T in T = SYT(α ⊕ ), we define cDes(T ) := {1 ≤ i ≤ n : i + 1 is in a lower row than i}, where n + 1 is interpreted as 1, as well as a bijection p : SYT(α ⊕ ) → SYT(α ⊕ ) which first 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 = 3 9 1 5 7 8 2 4 6 p −→ p(T ) = 1 4 2 6 8 9 3 5 7 cDes(T ) = {1, 3, 5, 9} p −→ cDes(p(T )) = {1, 2, 4, 6}

This generalizes the case of (cDes, p) on S n , since for α = (1 n ) = (1, 1, . . . , 1) one has a bijection S n → 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,

w = [5, 3, 1, 4, 2] −→ 1 4 2 5 3

This bijection maps Cellini's cyclic extension (cDes, p) on S n to the one on SYT(α ⊕ ) for α = (1, 1, . . . , 1) defined above 1 .

• Furthermore, for any nonempty partition λ n − 1, the partition λ ⊕ (1), e.g. λ = (4, 3, 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].

Cyclic descents for standard Young tableaux

Our first main result is a necessary and sufficient 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, 1 k ) 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 = {j 1 < . . . < j t } ⊆ [n − 1], the composition (of n) α(J, n) := (j 1 , j 2 − j 1 , j 3 − j 2 , . . . , j t − j t−1 , n − j t ) (5)

defines a connected ribbon having the entries of α(J, n) as row lengths, and thus an associated (skew) ribbon Schur function

s α(J,n) := ∅⊆I⊆J (−1) #(J\I) h α(I,n)(6)

with the following property: for any skew shape λ/µ, the descent map Des : SYT(λ/µ) −→ 2 [n−1] has fiber sizes given by #Des

−1 (J) = s λ/µ , s α(J,n) (∀J ⊆ [n − 1]),(7)

where −, − is the usual inner product on symmetric functions. By analogy, for a subset ∅ = J = {j 1 < j 2 < . . . < j t } ⊆ [n] we define the corresponding cyclic composition of n as

α cyc (J, n) := (j 2 − j 1 , . . . , j t − j t−1 , j 1 + n − j t ),(8)

with α cyc (J, n) := (n) when J = {j 1 }; note that α cyc (∅, n) is not defined. The corresponding affine (or cyclic) ribbon Schur function is then defined as

sα cyc (J,n) := ∅ =I⊆J (−1) #(J\I) h α cyc (I,n) .(9)

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 fiber sizes are given by

#cDes −1 (J) = s λ/µ , sα cyc (J,n) (∀ ∅ J [n]). (10)

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].

5 Cyclic quasisymmetric functions

The ring of cyclic quasisymmetric functions

Recall from [Ges84] the following basic definitions: A quasi-symmetric function is a formal power series f ∈ Z[[x 1 , x 2 , . . .]] of bounded degree such that, for any t ≥ 1, any two increasing sequences i 1 < • • • < i t and i 1 < • • • < i t of positive integers, and any sequence (m 1 , . . . , m t ) of positive integers, the coefficients of

x m1 i1 • • • x mt it and x m1 i 1 • • • x mt i t

in f are equal. Denote by QSym the set of all quasi-symmetric functions, and by QSym n the 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 defined by

F n,J := x i1 • • • x in ,

where the sum extends over all sequences (i 1 , . . . , i n ) of positive integers such that j ∈ J ⇒ i j < i j+1 and j ∈ J ⇒ i j ≤ i j+1 . The set {F n,J : J ⊆ [n − 1]} forms a basis for the additive abelian group QSym n .

The cyclic analogues of these concepts are introduced in [AGRR+18].

Definition 5.1. A cyclic quasi-symmetric function is a formal power series f ∈ Z[[x 1 , x 2 , . . .]] of bounded degree such that, for any t ≥ 1, any two increasing sequences i 1 < • • • < i t and i 1 < • • • < i t of positive integers, any sequence m = (m 1 , . . . , m t ) of positive integers, and any cyclic shift m = (m 1 , . . . , m t ) of m, the coefficients of

x m1 i1 • • • x mt it and x m 1 i 1 • • • x m t i t in f are equal.

Denote by cQSym the set of all cyclic quasi-symmetric functions, and by cQSym n 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 Λ) are graded abelian groups satisfying Sym cQSym QSym (11)

It is not too difficult 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].

Fundamental cyclic quasisymmetric functions

Definition 5.3. For each subset J ⊆ [n] denote by P cyc n,J the set of all pairs (w, k) consisting of a word w = (w 1 , . . . , w n ) ∈ N n and an index k ∈ [n] which satisfy (i) The word w is "cyclically weakly increasing" from index k, namely w k ≤ w k+1 ≤ . . . ≤ w n ≤ w 1 ≤ . . . ≤ w k−1 .

(ii) If j ∈ J then w j = w j+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 ∈ [n] will do. These "constant words" are relevant only for J = ∅, and the definition implies that each of them is counted n times (and not just once) in P cyc n,∅ .

Example 5.5. Let n = 5 and J = {1, 3}. The pairs (12345, 1), (23312, 4) and (23122, 3) are in P cyc 5,{1,3} (see Figure 1), but the pairs (12354, 1), (22312, 4) and (23112, 3) are not. Let D n,J := {i ∈ Z/nZ : J + i ≡ J (mod n)} be the stabilizer of J under the action of Z/nZ by cyclic shifts, and let d n,J := #D n,J .

Definition 5.6. The fundamental cyclic quasisymmetric function corresponding to a subset J ⊆ [n] is defined by

F cyc n,J := d −1 n,J (w,k)∈P cyc n,J x w1 x w2 • • • x wn .

Let 2

[n] 0 be the set of all nonempty subsets of [n], and let c2

[n] 0 be the set of orbits of elements of 2

[n] 0 under cyclic shifts. If J and J are in the same orbit then F cyc n,J = F cyc n,J .

Theorem 5.7. The set {F cyc n,J : J ∈ c2

[n] 0 } is a Z-basis for cQSym n .

Furthermore, letting s λ/µ be the skew Schur function indexed by a non-ribbon shape λ/µ, we have

T ∈SYT(λ/µ) F cyc n,cDes(T ) = s λ/µ . (12)

6 Cyclic Eulerian distributions

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.

Univariate generating functions

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 λ/µ:

T ∈SYT(λ/µ) t des(T ) = (1 − t) n+1 m≥0 s λ/µ (1 m+1 )t m .(13)

Here s λ/µ (1 m ) is the specialization of the skew Schur function s λ/µ (x 1 , x 2 , . . .) given by x 1 = . . . = x m = 1 and x m+1 = . . . = 0. Note that when µ = ∅ this becomes even more explicit, through the hook-content formula [Sta99, Cor. 7.21.4] for the specialization s λ (1 m ). In particular, for the skew shape (1) ⊕n this gives the well-known Carlitz formula for the Eulerian distribution on S n :

S des n (t) := w∈Sn t des(w) = (1 − t) n+1 m≥0 (m + 1) n t m(14)

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,

T ∈SYT(λ/µ) t cdes(T ) = n(1 − t) n m≥1 s λ/µ (1 m ) t m m .(15)

In particular, for the skew shape (1) ⊕n this gives

S cdes n (t) := w∈Sn t cdes(w) = n(1 − t) n m≥1 m n−1 t m = nt S des n−1 (t) (n ≥ 2).(16)

For two-row shapes, [ARR17, Lemma 2.4] is applied in [AER18] to deduce the following.

Theorem 6.2. For any

2 ≤ k ≤ n/2, T ∈SYT((n−k,k)) t cdes(T ) = k d=1 n d k − 1 d − 1 n − k − 1 d − 1 − k − 2 d − 1 n − k d − 1 t d .

Multivariate generating functions

Next we compare the distribution of cDes on SYT(λ) to the distribution of cDes on S n . Recall [Sag01, Theorem 3.1.1 and §5.6 Ex. 22(a)] that the Robinson-Schensted correspondence is a bijection between S n and the set of pairs of standard Young tableaux of the same shape λ (and size n), having the property that if w → (P, Q) then Des(w) = Des(Q). Consequently

w∈Sn t Des(w) = λ n f λ T ∈SYT(λ)

t Des(T ) .

Here t S := i∈S t i for S ⊆ {1, 2, . . .}, 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 T ∈SYT(λ/µ) t cDes(T ) well-defined 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 ( 12), or alternatively by Equation (10), we deduce the following second main result.

Theorem 6.3. For any n ≥ 2

w∈Sn t cDes(w) = non-hook λ n f λ T ∈SYT(λ) t cDes(T ) + n−1 k=1 n − 2 k − 1 T ∈SYT((1 k )⊕(n−k)) t cDes(T ) ,

where cDes is defined on S n 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. Proposition 6.4. 1. For any n ≥ 2

n−1 k=1 T ∈SYT((1 k )⊕(n−k)) t cDes(T ) = n i=1 (1 + t i ) − 1 − t 1 • • • t n . 2. For any n ≥ 4 n−2 k=2 T ∈SYT((n−k,2,1 k−2 )) t cDes(T ) = 1 + t 1 • • • t n + n i=1 (1 + t i ) •   −1 + n j=1 t j (1 + t j−1 )(1 + t j )   .

Cyclic Eulerian distribution on S n

We now focus on λ/µ = (1) ⊕n , where we can take

Z/nZ = c = {e, c, c 2 , • • • , c n−1 } on Z[t 1 , . . . , t n ] by shifting subscripts modulo n, i.e. c(t i ) = t i+1 (mod n) .

Proposition 6.5. For n ≥ 2, one has

S cDes n (t) = n i=1 c i t n S Des n−1 (t)(18)

and also S cDes

n (t) = g(t) + t [n] g(t −1 ),(19)

where

g(t) = g(t 1 , . . . , t n−1 ) := S cDes n (t) tn=0 = n−1 i=1 t i • c i S Des n−1 (t) tn=0 .(20

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 = {j 1 , • • • , j t } ⊆ [n] let −J := {−j 1 , . . . , −j t } (interpreted modulo n).

Corollary 7.3. Let λ/µ be a skew shape of size n which is not a connected ribbon. For any J ⊆ [n] and any cyclic extension cDes of the usual descent map on SYT(λ/µ), the fiber size #cDes −1 (J) = #cDes −1 (−J).

Problem 7.4. For a solution of Problem 7.1, find 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, 1 n−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 refined CSP on SYT of these skew shapes.