A New Interpretation of the Cocharge Statistic Kendra Ann Nelsen A THESIS in Mathematics Presented to the Faculties of the University of Pennsylvania in Partial Fulfillment of the Requirements for the Degree of Master of Arts 2005 Supervisor of Thesis Graduate Group Chairman Contents 1 Preliminaries 1 1.1 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Statistics on Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Plethystic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Macdonald Polynomials and Haglund’s Combinatorial Formula 14 2.1 Haglund’s Combinatorial Formula . . . . . . . . . . . . . . . . . . . . 14 2.2 The Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Macdonald polynomials and Cocharge 24 3.1 Defining Charge and Cocharge . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Relating Macdonald Polynomials and Cocharge . . . . . . . . . . . . 28 4 Beyond Partitions 33 4.1 Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 A New Look at Cocharge . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.1 An Alternative Description of Cocharge . . . . . . . . . . . . . 36 4.2.2 Cocharge and Compositions . . . . . . . . . . . . . . . . . . . 39 4.2.3 A Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5 Kostka-Foulkes Polynomials 50 ii 5.1 Introductory Information . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.2 Words and Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.3 Kostka-Foulkes and Charge . . . . . . . . . . . . . . . . . . . . . . . 54 iii Abstract A New Interpretation of the Cocharge Statistic Kendra Ann Nelsen Advisor: James Haglund In this thesis we will start by introducing the combinatorial formula for the Macdonald polynomial. We then show how cocharge arises naturally from this formula. Expanding these methods to compositions, we see how an alterna- tive description of cocharge arises naturally from the combinatorial statistics used in the formula for the Macdonald polynomial. The final chapter of the thesis outlines the proof of Lascoux and Schu¨tzenberger’s famous theorem that expands the Kostka-Foulkes polynomial in terms of charge. iv 1 1 Preliminaries 1.1 Tableaux A partition µ = (µ ,...,µ ) of n is a tuple of weakly decreasing, nonzero parts such 1 k that µ +···+µ = n. The length of the partition ‘(µ) = k is equal to the number 1 ‘ of parts of µ, and the size of the partition |µ| = n is the sum of the parts. Identify a partition µ with the tableau that has µ boxes in the ith row. For the partition i µ = (5,4,2) we identify µ with the following tableau ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ . (1.1) Equivalently, the diagram of µ is dg(µ) = {(i,j) ∈ Z × Z |i <= ‘(µ),j <= µ }. + + i Abusing notation, we refer to dg(µ) as µ. We partially order partitions µ and ν of n by saying µ ≤ ν if µ +···+µ ≤ ν +···ν for all k. 1 k 1 k Let µ0 = (µ0,...,µ0) where µ0 is equal to the number of boxes in the ith column 1 j i of µ. In the above example, when µ = (5,4,2) we have µ0 = (3,3,2,2,1). A filling of a partition µ is a map σ : µ → Z that assigns a positive integer to each of the boxes + in the partition µ. A super filling of a partition µ is a map σ : µ → Z SZ that + − assigns a non-zero integer to each of the boxes in the partition µ. Denote negative numbers with a bar overtop, i.e. negative 4 is written 4. For example, a filling and a super filling of the partition µ = (5,4,2) are: 2 ..........................................................................................................................................................................................121..................................................................................................................................................................................................................................................................................334..................................................................................................................................................................................................................................................................24....................................................................................................................................................................................................31....................................................................................................................................................................................6......................................................................................, ..........................................................................................................................................................................................132..................................................................................................................................................................................................................................................................................226..................................................................................................................................................................................................................................................................24....................................................................................................................................................................................................51....................................................................................................................................................................................3....................................................................................... The reading word of a tableau is found by reading the entries of the tableau left to right, top to bottom. Denoted w(σ), the reading word of the above filling is 14234113236. If u = (1,5) is the box in the first row, fifth column of the above partition µ, then µ(u) = 6 is the filling of the box u. Define the weight of a filling as a tuple λ where λ is the number of i’s that appear in the filling. Denote the weight i as wt(µ) = (λ ,··· ,λ ) so that in the above filling, we have wt(µ) = (3,2,3,2,0,1). 1 k Similarly, define the weight of a super filling as a pair of tuples (λ,ρ) where λ is the i number of i’s and ρ is the number of i’s appearing in the super filling. The above i super filling has weight wt(σ) = (λ,ρ) where λ = (1,1,2,1,1) and ρ = (1,3,0,0,0,1). We can standardize filling σ(µ) of weight λ = (λ ,··· ,λ ) in the following way: 1 k 1. In reading order (from left to right, top to bottom) replace the first entry containing a 1 with a 1, the second entry containing a 1 with a 2, ···, the λth 1 entry containing a 1 with a λ . 1 2. In reading order replace the first entry containing a 2 with a λ +1, the second 1 entry containing a 2 with a λ + 2, ···, the λth entry containing a 2 with a 1 2 λ +λ . 1 2 3 3. Repeat the same process for entries containing 3 through λ k Standardization produces a new filling σ˜(µ) with weight wt(σ˜) = 1|µ| (i.e. a filling with entries consisting of one 1, one 2, ..., one |µ|). Below we illustrate standardizing a filling: σ(µ) σ˜(µ) ..........................................................................................................................................................................................121..................................................................................................................................................................................................................................................................................334..................................................................................................................................................................................................................................................................24....................................................................................................................................................................................................31....................................................................................................................................................................................6......................................................................................, ..........................................................................................................................................................................................341..................................................................................................................................................................................................................................................................................769..........................................................................................................................................................................................................................................1........................5.....................0...............................................................................................................................................................................82....................................................................................................................................................................1..............................1......................................................................... A super filling σ(µ) can be standardized using a similar algorithm. First, one must fix a complete order on the super alphabet Z SZ . Two orderings that we will use + − later are: (a) 1 < 1 < 2 < 2 < 3 < 3··· , (b) 1 < 2 < 3 < ... < 3 < 2 < 1. For the purposes of explaining how to standardize a super filling, we will use ordering (a). Let σ(µ) be a super filling with wt(σ) = (λ,ρ). 1. In reading order (from left to right, top to bottom) replace the first entry containing a 1 with a 1, the second entry containing a 1 with a 2, ···, the λth 1 entry containing a 1 with a λ . 1 4 2. In backwards reading order (from right to left, bottom to top) replace the first entry containing a 1 with a λ +1, the second entry containing a 1 with a λ +2, 1 1 ···, the ρth entry containing a 1 with a λ +ρ . 1 1 1 3. Repeat the same process for entries containing 2,2,3,3,.... Below we illustrate standardizing a super filling: σ(µ) σ˜(µ) ..........................................................................................................................................................................................132..................................................................................................................................................................................................................................................................................226..................................................................................................................................................................................................................................................................24....................................................................................................................................................................................................51....................................................................................................................................................................................3......................................................................................, ..........................................................................................................................................................................................173..................................................................................................................................................................................................................................................1................................56............................1......................................................................................................................................................................................................................................49............................................................................................................................................................................1........................2.....................0...............................................................................................................................................................8....................................................................................... To standardize using an alternate ordering, go from the smallest letter in the ordering to the largest letter in the ordering replacing positive letters in reading order and negative letters in backwards reading order. Let µ = (µ ,...,µ ) and λ = (λ ,··· ,λ ) be partitions. A semi-standard tableau 1 ‘ 1 k of shape µ and weight λ is a filling of the boxes of µ with λ 1’s, ···, λ m’s such 1 m that: 1. the values in the columns decrease strictly from top to bottom, 2. the values in the rows increase weakly from left to right. Let µ = (5,4,2) and λ = (3,2,3,2,0,1). A possible semi-standard tableau T of shape µ (denoted shp(T) = µ) is: 5 ..........................................................................................................................................................................................123..................................................................................................................................................................................................................................................................................124..................................................................................................................................................................................................................................................................13....................................................................................................................................................................................................34....................................................................................................................................................................................6...................................................................................... We will use the following notation: SSYT(λ) = {semi-standard tableau T with shp(T) = λ and weight not specified}, SSYT(λ,µ) = {semi-standard tableau T with shp(T) = λ and wt(T) = µ}. 1.2 Statistics on Tableaux The goal of this section is to define two combinatorial statistics, inv(σ) and maj(σ) of a filling σ, that are used in Haglund’s combinatorial formula for the Macdonald Polynomial [4]. A descent of a filling σ is a pair of entries (µ(u),µ(v)), with µ(u) > µ(v), where u is the box directly above v in the Ferris diagram of µ. Define Des(σ) = {u ∈ µ| (µ(u),µ(v)) is a descent pair }. For example, with respect to the ordering 1 < 1 < 2 < 2 < ···, the filling below has three descents which correspond to the boxes denoted with a subscript d on the entry: 6 ..................................................................................................................................................................2........................11................................d..........................................................................................................................................................................................................................4........................33................................d................................................................................................................................................................................................................4..................2........................d............................................................................................................................................................................31....................................................................................................................................................................................6...................................................................................... Equivalently, Des(σ) = {(2,1),(2,3),(3,2)}. Observe that for all semi-standard tableau, entries not in the first row are descents by definition. We can expand the definition of the descent set to include super fillings. First, fix a complete ordering on Z SZ , and let u be the box directly above v in µ. A descent of a super filling σ is + − a pair of entries (µ(u),µ(v)), with µ(u) > µ(v), or µ(u) = µ(v) ∈ Z . For example, − the super filling below has four descents which correspond to the boxes denoted with a subscript d on the entry: ..................................................................................................................................................................3........................12................................d..........................................................................................................................................................................................................................26........................2................................dd................................................................................................................................................................................................................4..................2........................d............................................................................................................................................................................15....................................................................................................................................................................................3...................................................................................... Equivalently, Des(σ) = {(1,2),(2,2),(2,3),(3,2)}. It is important to observe that if σ is a filling or super filling, and σ˜ is its standardization, Des(σ) = Des(σ˜). The leg (arm) of a box u ∈ µ is the number of boxes strictly above (to the right of) u and in the same column (row) as u. If u = (1,2) in the partition µ = (5,4,2) below, then leg(u) = 2 and arm(u) = 3 as denoted in the following diagram: