THE MURNAGHAN–NAKAYAMA RULE FOR k-SCHUR FUNCTIONS JASON BANDLOW,ANNESCHILLING,ANDMIKE ZABROCKI 1 Abstract. We prove the Murnaghan–Nakayama rule for k-Schur functions of Lapointe 1 andMorse,thatis,wegiveanexplicitformulafortheexpansionoftheproductofapower 0 sum symmetric function and a k-Schur function in terms of k-Schur functions. This is 2 proved using the noncommutative k-Schur functions in terms of the nilCoxeter algebra n introduced by Lam and the affine analogue of noncommutative symmetric functions of a Fomin and Greene. J 0 2 1. Introduction ] O TheMurnaghan–Nakayama rule[10,13,14]isacombinatorial formulaforthecharacters C χ (µ) of the symmetric group in terms of ribbontableaux. Under the Frobenius character- . λ h istic map, there exists an analogous statement on the level of symmetric functions, which t a follows directly from the formula m (1.1) p s = (−1)ht(µ/λ)s . [ r λ µ Xµ 2 Here p is the r-th power sum symmetric function, s is the Schur function labeled by v r λ 6 partition λ, and the sum is over all partitions λ ⊆µ for which µ/λ is a border strip of size 8 r. Recall that a border strip is a connected skew shape without any 2×2 squares. The 8 height ht(µ/λ) of a border strip µ/λ is one less than the number of rows. 4 . In [3], Fomin and Greene develop the theory of Schur functions in noncommuting vari- 4 ables. In particular, they derive a noncommutative version of the Murnaghan–Nakayama 0 0 rule[3,Theorem1.3]forthenilCoxeter algebra(ormoregenerallythelocalplacticalgebra) 1 : (1.2) p s = (−1)asc(w)ws , v r λ λ Xi Xw where w is a hook word of length r. Here p and s are the noncommutative analogues r λ r a of the power sum symmetric function and the Schur function (introduced in Section 2). Consider w as a word in a totally ordered alphabet that consists of the indices of the generators of the algebra. The word w is a hook word if w =b b ...b a a ...a where l l−1 1 1 2 m (1.3) b > b > ··· >b > a ≤ a ≤ ··· ≤ a l l−1 1 1 2 m and asc(w) = m−1 is the number of ascents in w. Actually, by [3, Theorem 5.1] it can further be assumed that the support of w is an interval. Date: April 2010. Partially supported bythe NSFgrants DMS–0652641 and DMS–0652652. 1 2 JASONBANDLOW,ANNESCHILLING, ANDMIKEZABROCKI In this paper, we derive a (noncommutative) Murnaghan–Nakayama rule for the k- Schur functions of Lapointe and Morse [9]. k-Schur functions form a basis for the ring Λ = Z[h ,...,h ] spanned by the first k complete homogeneous symmetric functions h , (k) 1 k r which is a subring of the ring of symmetric functions Λ. Lapointe and Morse [9] gave a formula for a homogeneous symmetric function h times a k-Schur function (at t = 1) as r (1.4) h s(k) = s(k), r λ µ µ∈XP(k) wherethesumisoverallk-boundedpartitionsµ ∈ P(k) suchthatµ/λisahorizontalr-strip and µ(k)/λ(k) is a vertical r-strip. Here λ(k) denotes the k-conjugate of λ. Equation (1.4) is a simple analogue of the Pieri rule for usual Schur functions, called the k-Pieri rule. This formulacan infactbetaken asthedefinitionof k-Schurfunctionsfromwhichmany oftheir properties can be derived. Conjecturally, the k-Pieri definition of the k-Schur functions is equivalent tothe original definition by Lapointe, Lascoux, andMorse [5]in terms of atoms. Lam [4] defined a noncommutative version of the k-Schur functions in the affine nilCox- eter algebra as the dual of the affine Stanley symmetric functions (1.5) F (X) = hh (u)h (u)···h (u)·1,wi xa1···xat, w at at−1 a1 1 t a=(aX1,...,at) where the sum is over all compositions of len(w) satisfying a ∈ [0,k]. Here i h (u) = udec r A A X aretheanaloguesofhomogeneoussymmetricfunctionsinnoncommutativevariables,where thesumisover allr-subsetsAof[0,k]andudec istheproductofthegenerators oftheaffine A nilCoxeter algebra in cyclically decreasing order with indices appearing in A. We denote the noncommutative analogue of Λ by Λ as the subalgebra of the affine nilCoxeter (k) (k) algebragenerated bytheseanalogues ofhomogeneous symmetricfunctions. SeeSection 2.3 for further details. (k) Denote bys thenoncommutative k-Schurfunctionlabeled bythek-boundedpartition λ λ and p the noncommutative power sum symmetric function in the affine nilCoxeter r algebra. There is a natural bijection from k-bounded partitions λ to (k+1)-cores, denoted core (λ) (see Section 2.1). We define a vertical domino in a skew-partition to be a pair k+1 of cells in the diagram, with one sitting directly above the other. For the skew of two k-bounded partitions λ ⊆ µ we define the height as (1.6) ht(µ/λ) = number of vertical dominos in µ/λ . For ribbons, that is skew shapes without any 2×2 squares, the definition of height can be restated as the number of occupied rows minus the number of connected components. Notice that this is compatible with the usual definition of the height of a border strip. Definition 1.1. The skew of two k-bounded partitions, µ/λ, is called a k-ribbon of size r if µ and λ satisfy the following properties: (0) (containment condition) λ ⊆ µ and λ(k) ⊆ µ(k); THE MURNAGHAN–NAKAYAMA RULE FOR k-SCHUR FUNCTIONS 3 (1) (size condition) |µ/λ| = r; (2) (ribbon condition) core (µ)/core (λ) is a ribbon; k+1 k+1 (3) (connectednesscondition)core (µ)/core (λ)isk-connected(seeDefinition2.3); k+1 k+1 (4) (height statistics condition) ht(µ/λ)+ht(µ(k)/λ(k)) = r−1. Our main result is the following theorem. Theorem 1.2. For 1≤ r ≤ k and λ a k-bounded partition, we have p s(k) = (−1)ht(µ/λ)s(k), r λ µ µ X where the sum is over all k-bounded partitions µ such that µ/λ is a k-ribbon of size r. If k is sufficiently large, then µ/λ satisfies Definition 1.1 is equivalent to µ/λ is a connected ribbon of size r (as a skew partition). Hence for k sufficiently large, Theorem 1.2 implies Equation (1.1). Let λ,ν be k-bounded partitions of the same size and ℓ the length of ν. A k-ribbon tableau of shape λ and type ν is a filling, T, of the cells of λ with the labels {1,2,...,ℓ} which satisfies the following conditions for all 1≤ i ≤ ℓ: (i) the shape of the restriction of T to the cells labeled 1,...,i is a partition, and (ii) the skew shape r , which is the restriction of T to the cells labeled i, is a k-ribbon i of size ν . i We also define ℓ χ(k) = (−1)ht(ri) , λ,ν ! T i=1 X Y where the sum is over all k-ribbon tableaux T of shape λ and type ν. Iterating Theorem 1.2 gives the following corollary. We remark that this formula may also be considered as a definition of the k-Schur functions. Corollary 1.3. For ν a k-bounded partition, we have (k) (k) p = χ s . ν λ,ν λ λ∈XP(k) All notation and definitions regarding our main Theorem 1.2 are given in Section 2. In Section 2 we also see that there is a ring isomorphism ι: Λ → Λ (k) (k) sendingthenoncommutative symmetricfunctionstotheirsymmetricfunctioncounterpart. This leads us to the following corollary. Corollary 1.4. Theorem 1.2 and Corollary 1.3 also hold when replacing p by the power r (k) (k) sum symmetric function p , and s by the k-Schur function s . r λ λ 4 JASONBANDLOW,ANNESCHILLING, ANDMIKEZABROCKI Dual k-Schur functions S(k) indexed by k-bounded partitions λ form a basis of the λ quotient space Λ(k) = Λ/hp | r > ki = Λ/hm | λ > ki (they correspond to the affine r λ 1 Stanley symmetric functions indexed by Grassmannian elements). The Hall inner product h·,·i : Λ × Λ → Q defined by hh ,m i = hs ,s i = δ , can be restricted to h·,·i : λ µ λ µ λ,µ Λ ×Λ(k) → Q, so that s(k) and S(k) form dual bases hs(k),S(k)i = δ . Let z be the (k) λ µ λ µ λ,µ λ size of the centralizer of any permutation of cycle type λ. Then hp ,p i= z δ . λ µ λ λ,µ Corollary 1.5. For ν a k-bounded partition, we have 1 S(k) = χ(k) p . ν z ν,λ λ λ λ∈XP(k) Proof. Denote by b(k) the coefficient of p in S(k), that is, S(k) = b(k)p . Then, using ν,λ λ ν ν λ ν,λ λ Corollary 1.3 we have P z b(k) = hp ,S(k)i = h χ(k)s(k),S(k)i = χ(k). (cid:3) λ ν,λ λ ν µ,λ µ ν ν,λ µ X Since the product of two k-bounded power symmetric functions is again a k-bounded power symmetric function, the expansion of the dual k-Schur functions in terms of p of λ Corollary 1.5 is better suited for multiplication than the expansion in terms of monomial symmetric functions. The product of two k-bounded monomial symmetric functions is a sum of monomial symmetric functions which are not necessarily k-bounded. The classical Murnaghan-Nakayama rule (corresponding to sufficiently large k) has implications for representation theory. Thewell-known Frobenius mapsendsa representation V of the symmetric group S to the symmetric function n χ (µ) V p , µ z µ µ X where χ (µ) is the character of V evaluated on the conjugacy class of type µ. This map V sends the irreducible representation V to the Schur function s . Therefore, whenever a λ λ Schur-positive symmetric function is expanded in terms of the power-sum basis, the coeffi- cients can be interpreted as the character of some corresponding representation. However, this does not apply to Corollary 1.5, since the functions S(k) are not Schur positive. The λ possibility of a different form of a k-Murnaghan-Nakayama rule that would have representation theoretical implications is discussed in Section 5. Thepaperis organized as follows. In Section 2 we introduceall notation and definitions. In particular, we define the various noncommutative symmetric functions. In Section 3 we prove Theorem 3.1, which is the analogue of Theorem 1.2 formulated in terms of the nilCoxeter algebra. In Section 4 it is shown that Theorems 1.2 and 3.1 are equivalent. We conclude in Section 5 with some related open questions. In Appendices A and B we list (k) (k) some tables for χ and its dual version χ˜ . λ,µ λ,µ THE MURNAGHAN–NAKAYAMA RULE FOR k-SCHUR FUNCTIONS 5 Acknowledgments We thank Drexel University and the American Institute for Mathematics (AIM) for hosting two focused research workshops in March and May 2009, where this work be- gan. Special thanks to Sara Billey, Luc Lapointe, Jennifer Morse, Thomas Lam, Mark Shimozono, and Nicolas Thiéry for many stimulating discussions. This work benefited greatly from calculations run in the open source computer algebra system sage [15] and sage-combinat [16]. 2. Notation In this section we give all necessary definitions. 2.1. Partitions and cores. A sequence λ = (λ ,λ ,...,λ ) is a partition if λ ≥ λ ≥ 1 2 ℓ 1 2 ··· ≥ λ >0. We say that ℓ is the length of λ and |λ| = λ +···+λ is its size. A partition ℓ 1 ℓ λ is k-bounded if λ ≤k. We denote by P(k) the set of all k-bounded partitions. 1 One may represent a partition λ by its partition diagram, which contains λ boxes in i row i. The conjugate λt corresponds to the diagram with rows and columns interchanged. We use French convention and label rows in decreasing order from bottom to top. For example and correspond to the partition (3,1) and its conjugate (2,1,1), respectively. For two partitions λ and µ whose diagrams are contained, that is λ ⊆ µ, we denote by µ/λ the skew partition consisting of the boxes in µ not contained in λ. A ribbon is a skew shape which does not contain any 2×2 squares. An r-border strip is a connected ribbon with r boxes. Apartition λ is an r-core if nor-borderstrip can beremoved from λ such that theresult is again a partition. For example (2.1) is a 4-core. We denote the set of all r-cores by C . r For a cell c = (i,j) ∈ λ in row iand columnj we defineits hook length to bethenumber of cells in row i of λ to the right of c plus the number of cells in column j of λ weakly above c (including c). An alternative definition of an r-core is a partition without any cells of hook length equal to a multiple of r [12, Ch. 1, Ex. 8]. The content of cell c = (i,j) is given by j−i (mod r). There exists a bijection [8] (2.2) core :P(k) → C k+1 k+1 from k-bounded partitions to (k+1)-cores defined as follows. Let λ ∈ P(k) considered as a set of cells. Starting from the smallest row, check whether there are any cells of hook length greater than k. If so, slide the row and all those in the rows below to the right by 6 JASONBANDLOW,ANNESCHILLING, ANDMIKEZABROCKI the minimal amount so that none of cells in that row have a hook length greater than k. Then continue the procedure with the rows below. The positions of the cells define a skew partition and the outer partition is a (k+1)-core. The inverse map core−1 : C → P(k) is slightly easier to compute. The partition k+1 k+1 core−1 (κ) is of the same length as the (k+1)-core κ and the ith entry of the partition is k+1 the number of cells in the the ith row of κ which have a hook smaller or equal to k. Let λ ∈ P(k). Then the k-conjugate λ(k) of λ is defined as core−1 (core (λ)t). k+1 k+1 Example 2.1. For k = 3, take λ = (3,2,1,1) ∈P(k) so that core : 7→ 4 which is the 4-core in (2.1) (where we have drawn the original boxes of λ in bold). To obtain the k-conjugate λ(3) of λ we calculate core−1 : 7→ . 4 2.2. Affine nilCoxeter algebra. The affine nilCoxeter algebra A is the algebra over Z k generated by u ,u ,...,u satisfying 0 1 k u2 = 0 for i ∈ [0,k], i (2.3) u u u = u u u for i ∈ [0,k], i i+1 i i+1 i i+1 u u = u u for i,j ∈ [0,k] such that |i−j| ≥ 2, i j j i whereall indices are taken modulok+1. We view theindices i ∈ [0,k] as living on a circle, with nodeibeingadjacent tonodesi−1 andi+1 (modulok+1). As withCoxeter groups, we have a notion of reduced words of elements u ∈ A as the shortest expressions in the k generators. If u= u ···u is a reduced expression, we call {i ,...,i } the support of u i1 im 1 m denoted supp(u) (which is independent of the reduced word and only depends on u itself). Also, i ...i is the corresponding reduced word and len(u) =m is the length of u. 1 m A word w in the letters [0,k] is cyclically decreasing (resp. increasing) if the length of w is at most k, every letter appears at most once, and if i,i − 1 ∈ w then i occurs before (resp. after) i−1. Note that since u and u commute if i is not adjacent to j, i j all cyclically decreasing (resp. increasing) words w with the same support give rise to the same affine nilCoxeter group element u . For a proper subset A ( [0,k] we define i∈w i udec ∈ A (resp. uinc ∈ A ) to be the element corresponding to cyclically decreasing (resp. A k A k Q increasing) words with support A. Example 2.2. Take k = 6 and A = {0,2,3,4,6}. Then udec = (u u )(u u u ) = A 0 6 4 3 2 (u u u )(u u ) and uinc = (u u )(u u u ) =(u u u )(u u ). 4 3 2 0 6 A 6 0 2 3 4 2 3 4 6 0 THE MURNAGHAN–NAKAYAMA RULE FOR k-SCHUR FUNCTIONS 7 If u∈ A is supportedon a propersubset S of [0,k], then we specify a canonical interval k I which contains the subset S. Identify the smallest element a (from the numbers 0 S through k with the integer order) which does not appear in S. Then the canonical cyclic interval which we choose orders the elements a+1< a+2< ··· < k < 0 < 1< ··· < a−1, (where we identify k and −1 when necessary). Definition 2.3. An element u ∈ A (resp. word w) is k-connected if its support S is an k interval in I . S Example 2.4. For k = 6, the word w = 0605 is k-connected, whereas w = 06052 is not. Suppose u ∈ A has support S ( [0,k]. We say that u corresponds to a hook word if it k has a reduced word w of the form of Equation (1.3) with respect to the canonical order I . S In this case we denote by asc(u) or asc(w) the number of ascents asc (w) in the canonical IS order. Example 2.5. Take u = u u u u u ∈ A . In this case S = {0,2,3,4,6} and I is given 3 2 6 0 4 6 S by 2 < 3 < 4< 5 < 6 < 0. The word w = (3)(2460) is a hook word with respect to I and S asc(u) = 3. The generators u in the nilCoxeter algebra A act on a (k+1)-core ν ∈ C by i k k+1 ν with all corner cells of content i added if they exist, (2.4) u ·ν = i (0 otherwise. This action is extended to the rest of the algebra A and can be shown to be consistent k with the relations of the generators. Under the bijection core−1 to k-bounded partitions k+1 onlythetopmostboxaddedtodiagramsurvives. Theactionofu onak-boundedpartition i λ under core is denoted u ·λ. k+1 i Example 2.6. Taking ν = core (λ) from Example 2.1 we obtain 4 u ·ν = and core−1(u ·ν)= 2 4 2 where the boxes added by u of content 2 are indicated in bold. 2 2.3. Noncommutative symmetric functions. We now give the definition of the non- (k) commutative symmetric functions er, hr, s(r−i,1i), pr, and sλ in terms of the affine nil- Coxeter algebra. Following Lam [4], for r = 1,...,k, we define the noncommutative homogeneous symmetric functions h = udec , r A A∈X[0,k] (cid:16) r (cid:17) 8 JASONBANDLOW,ANNESCHILLING, ANDMIKEZABROCKI where udec is a cyclically decreasing element with support A as defined in Section 2.2. We A take as a defining relation for the elements e the equation r (−1)ie h = 0. It can r i=0 r−i i be shown [4, Proposition 16] that then P e = uinc , r A A∈X[0,k] (cid:16) r (cid:17) where uinc is a cyclically increasing element with support A. More generally, the hook A Schur functions for r ≤ k are given by s(r−i,1i) = hr−iei −hr−i+1ei−1+···+(−1)ihr andwewilldemonstrateinCorollary3.5(below)thattheseelementsmayalsobeexpressed as a sum over certain words. The noncommutative power sum symmetric functions for 1 ≤ r ≤ k are defined through the analogue of a classical identity with ribbon Schur functions r−1 pr = (−1)is(r−i,1i). i=0 X Lam [4, Proposition 8] proved that, even though the variables u do not commute, the i elements h for 1 ≤ r ≤ k commute and consequently, so do the other elements e , p , r r r s(r−i,1i) we have defined in terms of the hr. We define Λ(k) = Z[h1,...,hk] to be the noncommutative analogue of Λ = Z[h ,...,h ]. (k) 1 k (k) We define the noncommutative k-Schur functions s by the noncommutative analogue λ (k) of the k-Pieri rule (1.4). Let us denote by H the set of all pairs (µ,λ) of k-bounded r partitions µ,λ such that µ/λ is a horizontal r-strip and µ(k)/λ(k) is a vertical r-strip (which describes the summation in the k-Pieri rule). Then for a k-bounded partition λ we require that (2.5) h s(k) = s(k). r λ µ µ:(µ,Xλ)∈H(rk) (k) This definition can be used to expand the h elements in terms of the elements s . The µ λ transition matrix is described by the number of k-tableaux of given shape and weight (see [8]). Since this matrix is unitriangular, this system of relations can be inverted over the integers and hence {s(k) |λ ∈ P(k)} forms a basis of Λ . λ (k) (k) As shown in [8, 6], for 1 ≤ r ≤ k, we have if (µ,λ) ∈ H , then there is a cyclically r decreasing element u∈ A of length r such that µ = u·λ. Moreover, if u∈ A is cyclically k k (k) decreasing and µ = u·λ 6= 0, then (µ,λ) ∈ H . r THE MURNAGHAN–NAKAYAMA RULE FOR k-SCHUR FUNCTIONS 9 Example 2.7. Take λ = (3,3,1,1) ∈ P(3) and u= u u . Then 0 3 core (λ) = and u·core (λ) = 4 4 (3) so that ((3,3,2,1,1),(3,3,1,1)) ∈ H . 2 Hence, we may rewrite (2.5) as h s(k) = s(k) = s(k) , r λ µ udAec·λ µ:(µ,Xλ)∈H(rk) A∈X(cid:16)[0r,k](cid:17) where we assume s(k) = 0 if udec ·λ = 0. The elements h = udec generate udAec·λ A r A∈(cid:16)[0r,k](cid:17) A Λ(k), and therefore more generally for any element f = ucuu ∈PΛ(k) with u ∈ Ak and c ∈Z u P (k) (k) (2.6) f s = c s . λ u u·λ u X Sinceallofthenoncommutativesymmetricfunctionsinthissection commuteandsatisfy the same defining relations as their commutative counterparts, there is a ring isomorphism ι: Λ → Λ (k) (k) sending h 7→ h , e 7→ e , p 7→ p , s(k) 7→ s(k). r r r r r r λ λ 3. Main result: Murnaghan–Nakayama rule in terms of words We now restate Theorem 1.2 in terms of the action of words. This result is proved in the remainder of this section. Theorem 3.1. For 1≤ r ≤ k and λ a k-bounded partition, we have (3.1) p s(k) = (−1)asc(w)s(k), r λ µ (w,µ) X where the sum is over all pairs (w,µ) of reduced words w in the affine nilCoxeter algebra A and k-bounded partitions µ satisfying k (1′) (size condition) len(w) = r; (2′) (ribbon condition) w is a hook word; (3′) (connectedness condition) w is k-connected; (4′) (weak order condition) µ = w·λ. In Section 4 we will show the equivalence of Theorem 1.2 and Theorem 3.1. The proof of Theorem 3.1 essentially amounts to computing an expression for p in r terms of words. Since all words involved will be of length ≤ k, there will be a canonical order on the support as introduced in Section 2.2. The statistic asc(w), and the property of being a hook word, will always be in terms of this canonical ordering. 10 JASONBANDLOW,ANNESCHILLING, ANDMIKEZABROCKI Lemma 3.2. For 0≤ i ≤ r ≤k, (3.2) h e = w , r−i i w X where the sum is over all words w satisfying (1′), (2′) with respect to the canonical order, and asc(w) ∈ {i−1,i}. Proof. h is the sum over all cyclically decreasing nilCoxeter group elements of length r−i r−i and e is the sum over all cyclically increasing nilCoxeter group elements of length i. i Hence h e = uv. r−i i (u,v) X ucycl. dec.,|u|=r−i v cycl. inc.,|v|=i Rearrange each u and v so that they together form a hook with respect to the canonical order associated to the set supp(u)∪supp(v). Either the last letter of u is smaller than the first letter of v, in which case the total ascent is i, or the last letter of u is bigger than the first letter in v, in which case the total number of ascents is i−1. This yields a bijection between hook words in the canonical order and pairs appearing in this sum with the number of ascents in {i,i−1}. In the corner case i = 0 (resp. i = r) the number of ascents can only be 0 (resp. r−1 due to the fact that the words are of length r). (cid:3) Example 3.3. Take k = 8, u = (u u u )(u u ) and v = (u u )(u ), so that i = 3 and 1 0 8 5 4 2 3 0 r = 8. In this case the canonical order is 7 < 8 < 0 < 1 < 2 < 3 < 4 < 5 and we would write uv as uv = [(u u )(u u u )][(u )(u u )], giving rise to the word w = (5410)(8023) 5 4 1 0 8 0 2 3 with i = 3 ascents. If on the other hand u = (u u )(u u ) and v = (u u )(u u ), so that 1 0 5 4 2 3 8 0 i = 4 and r = 8, then we would write uv = [(u u )(u u )][(u u )(u u )], giving rise to the 5 4 1 0 8 0 2 3 word w = (5410)(8023) with i−1= 3 ascents. Remark 3.4. Note that there may be multiplicities in (3.2) with respect to affine nilCox- eter group elements because there may be several hook words with the same number of ascents thatareequivalent tothesameaffinenilCoxeter element. For example, (4)(20) and (0)(24) are two different hook words with exactly one ascent with respect to the interval I = {2 < 4 < 0}. Of course, they both correspond to the same affine nilCoxeter {0,2,4} element since all letters in the word commute. The element with u = u and v = u u 2 4 0 would give rise to the hook word w = (240) with 2 ascents. We can use this lemma to get an expression for hook Schur functions. Corollary 3.5. For 0 ≤ i ≤ r ≤ k, the hook Schur function is s(r−i,1i) = w , w X where the sum is over all words w satisfying (1′),(2′) with respect to the canoncial order, and asc(w) = i.

The Murnaghan-Nakayama rule for k-Schur functions

Similar The Murnaghan-Nakayama rule for k-Schur functions