On the computation of Kronecker coefficients by Vasu Vineet Tewari A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Mathematics) The University Of British Columbia (Vancouver) August 2011 c Vasu Vineet Tewari, 2011 Abstract A major open problem in algebraic combinatorics is to find a combinatorial rule to compute the Kronecker product of two Schur functions. This is the same as decomposing the inner tensor product of two irreducible characters of the symmetric group as a sum of irreducible characters. Given that there is a combinatorial rule, namely the Littlewood-Richardson rule, which describes a way to compute the outer tensor product of two irreducible characters of the symmetric group, one would expect an algorithm which achieves the same purpose in the case of the inner tensor product. Jeffrey Remmel and Tamsen Whitehead first came up with a description of the Kronecker coefficients occurring in the Kronecker product of two Schur functions, both indexed by partitions of length at most 2. Mercedes Rosas later arrived at the same result using a different approach. The solution of the general problem would have implications in Complexity Theory and Quantum Information Theory. Our goal in this thesis is to derive formulae for computing the Kronecker product in certain cases where the Schur functions are indexed by partitions which are nearly rectangular. In particular, we study s(n,n−1,1) ∗ s(n,n) , s(n−1,n−1,1) ∗ s(n,n−1) , s(n−1,n−1,2) ∗ s(n,n) , s(n−1,n−1,1,1) ∗ s(n,n) and s(n,n,1) ∗ s(n,n,1) . Our approach relies ii mainly on the fruitful interplay between manipulation of symmetric functions and the representation theory of the symmetric group. As a consequence of these formulae, we also derive an expression enumerating certain standard Young tableaux of bounded height. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction and Background . . . . . . . . . . . . . . . . . . . . . 1 1.1 1.2 Symmetric functions . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Monomial symmetric functions . . . . . . . . . . . . . . 3 1.1.2 Other symmetric function bases . . . . . . . . . . . . . . 4 Semi-standard Young tableaux . . . . . . . . . . . . . . . . . . . 8 1.2.1 The hook length formula . . . . . . . . . . . . . . . . . . 10 Schur functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1 Combinatorial definition . . . . . . . . . . . . . . . . . . 15 1.4 Basic representation theory of Sn . . . . . . . . . . . . . . . . . . 22 1.5 The Kronecker product of Schur functions . . . . . . . . . . . . . 24 1.6 A brief survey of relevant results . . . . . . . . . . . . . . . . . . 27 1.7 Summary of results present in this thesis . . . . . . . . . . . . . . 32 2 Description of Kronecker Coefficients in Certain Cases . . . . . . . 34 1.3 iv 2.1 s(n,n−1,1) ∗ s(n,n) (n ≥ 2) . . . . . . . . . . . . . . . . . . . . 35 2.1.1 Case I: l(θ ) = 5 . . . . . . . . . . . . . . . . . . . . . . 38 2.1.2 Case II: l(θ ) ≤ 4 . . . . . . . . . . . . . . . . . . . . . . 38 2.1.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2 s(n−1,n−1,1) ∗ s(n,n−1) 2.3 s(n−1,n−1,2) ∗ s(n,n) 2.4 2.5 (n ≥ 2) . . . . . . . . . . . . . . . . . . 39 (n ≥ 3) . . . . . . . . . . . . . . . . . . . 42 2.3.1 Case I: l(θ ) = 6 . . . . . . . . . . . . . . . . . . . . . . 43 2.3.2 Case II: l(θ ) = 5 . . . . . . . . . . . . . . . . . . . . . . 45 2.3.3 Case III: l(θ ) ≤ 4 . . . . . . . . . . . . . . . . . . . . . . 47 2.3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 49 s(n−1,n−1,1,1) ∗ s(n,n) (n ≥ 2) . . . . . . . . . . . . . . . . . . 50 2.4.1 Case I: l(θ ) = 6 . . . . . . . . . . . . . . . . . . . . . . 52 2.4.2 Case II: l(θ ) = 5 . . . . . . . . . . . . . . . . . . . . . . 52 2.4.3 Case III: l(θ ) ≤ 4 . . . . . . . . . . . . . . . . . . . . . . 54 2.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 56 s(n,n,1) ∗ s(n,n,1) (n ≥ 2) . . . . . . . . . . . . . . . . . . . . 57 2.5.1 Relating dθ and dθ − . . . . . . . . . . . . . . . . . . . . 57 2.5.2 Computation . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5.3 Case I: l(θ ) = 6 . . . . . . . . . . . . . . . . . . . . . . 61 2.5.4 Case II: l(θ ) = 5 . . . . . . . . . . . . . . . . . . . . . . 62 2.5.5 Case III: l(θ ) ≤ 4 . . . . . . . . . . . . . . . . . . . . . . 64 2.5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Combinatorial implications . . . . . . . . . . . . . . . . . . . . . 68 3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.6 v 3.1 Further directions . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 vi Acknowledgments I would like to thank all the people whose support and encouragement have been essential to the successful completion of this thesis. It is difficult to overstate my gratitude to my advisor, Professor Stephanie van Willigenburg. With her enthusiasm and inspiration, she helped in making mathematics a lot of fun. Without the constant guidance, insight, sound advice, ideas, suggestions and encouragement of Professor van Willigenburg this work simply could not have been possible. I would also like to express profound gratitude to mathematicians who have nurtured my mathematical interests and helped me in my pursuit of mathematical knowledge, especially Professor Hemalatha Thiagarajan and Professor Udayan Prajapati during my undergraduate years, and Professor Andrew Rechnitzer, Professor Lior Silberman and Professor Richard Anstee at the University of British Columbia. I am indebted to my many student colleagues at University of British Columbia for providing a stimulating and fun environment. Nishant Chandgotia, Gourab Ray, Amir Ghadermarzi, Heidar Taheri, Hesameddin Abbaspour and Vishaal Kapoor made sure I had a life outside of math. Further, I wish to thank my close friends Shreyas Nair, Birottam Dutta, Sandeep Patwa, Krishnendu Bhattacharjee for all the vii camraderie, entertainment, and caring they have provided over the years. Lastly, and most importantly, I wish to thank my parents, Renu and Dinesh Tewari, and my sister, Stuti Sharma. They have supported me, taught me, believed in me and loved me. To them I dedicate this thesis. viii Chapter 1 Introduction and Background Symmetric functions play a central role in algebraic combinatorics because of the wealth of information they carry about permutations and partitions, objects which are at the heart of the field. To add to that, the theory of symmetric functions also interacts with other branches of mathematics, including group theory, representation theory and algebraic geometry. The Schur functions are a basis of the ring of symmetric functions with a variety of applications. They mirror the underlying algebra and combinatorics in a clear fashion. An outstanding open problem in algebraic combinatorics is to arrive at a combinatorial rule to compute the Kronecker product of two Schur functions. Given partitions λ , µ and ν , the Kronecker coefficients, gλµν , occur as the multiplicities of the irreducible representations of the symmetric group in the tensor product of the representations χλ and χµ of the symmetric group. Alternatively, they occur as coefficients in the decomposition of the Kronecker product, sµ ∗ sν , of Schur functions in the Schur basis, as shown in 1 the following equation sµ ∗ sν = ∑ gλµν sλ . (1.1) λ The aim of this thesis is to derive explicit formulae for Kronecker coefficients in certain special cases. But prior to that, we will equip the reader with an overview of symmetric functions and the multitude of operations one can carry out on them, so as to render the computation of the Kronecker coefficients transparent in specific cases. 1.1 Symmetric functions A symmetric function is a formal power series f (x) in the variables x = {x1 , x2 , . . .} with the property that f (xπ (1) , xπ (2) , . . .) = f (x1 , x2 , . . .) for every permutation π of the positive integers N. Corresponding to a finite multiset of positive integers λ = {λ1 , λ2 , . . . , λl } where the λi ’s are ordered in a weakly decreasing sequence, one can define a monomial xλ as follows xλ = xiλ11 xiλ22 · · · xiλl l , (1.2) where the i j for j = 1, . . . , l are distinct positive integers. The degree of the monomial is defined to be ∑li=1 λi . A symmetric function f is said to be homogeneous of degree n if all the monomials occuring in f are of degree n. The set of all homogeneous symmetric functions of a given degree n forms a vector space over the rational numbers, denoted by Λn . Given f ∈ Λn and g ∈ Λm , the product f g (as a formal power series) is an element of Λm+n . Now we define the ring of symmetric 2 functions Λ to be the vector space direct sum of the Λn , i.e. Λn , Λ= (1.3) n≥0 and Λ is considered as a graded algebra. A common theme in the theory of symmetric functions is the description of bases for the vector space Λn and the relationships amongst themselves. There are many different Q-bases for symmetric functions and we will now describe several of these bases. We will also introduce the combinatorial object used to describe the Schur functions. 1.1.1 Monomial symmetric functions The monomial symmetric functions are the functions obtained by symmetrizing a monomial. To elaborate on this concept of symmetrization, we need a notion of a partition. A partition of a positive integer n is a weakly decreasing sequence of non-negative integers λ = (λ1 , λ2 , . . . , λl ) such that the sum ∑li=1 λi equals n. The integers λi are called the parts of λ . We let φ denote the empty partition, i.e. the partition of 0. The notation λ ⊢ n implies that λ is a partition of n. For example, if n = 12, then λ = (5, 3, 3, 1, 0, 0) is a partition of 12 and we write λ ⊢ 12. The length, l(λ ) is the largest index i such that λi > 0. At times, the length of the partition might also be called the height of the partition. Again, if λ = (5, 3, 3, 1, 0, 0), then l(λ ) = 4. We will denote the number of distinct non-zero parts of λ by dλ . Therefore, for the same λ as before, we have dλ = 3. Since the zero parts of a given partition do not really matter for our purposes, we will identify partitions which only differ in 3 the number of trailing zeros. So, for example, the partition λ = (5, 3, 3, 1, 0, 0) is the same as the partition µ = (5, 3, 3, 1). Definition 1.1.1. Let λ = (λ1 , λ2 , . . . , λl ) be a partition of some positive integer n. Then the monomial symmetric function mλ corresponding to λ is mλ (x) = ∑ xiλ11 xiλ22 · · · xiλl l , (1.4) where the sum is over all distinct monomials with exponents λ1 , λ2 , . . . , λl in the variables x = {x1 , x2 , . . .}. For example, mφ = 1, m(1) = ∑ xi , i≥1 m(2) = ∑ xi2 , i≥1 m(1,1) = ∑ xi x j . 1≤i< j Each symmetric function can be written as a sum of monomial symmetric functions with rational coefficients. This implies that the set {mλ : λ ⊢ n} is a basis for Λn . Since the monomial symmetric functions are indexed by partitions, the dimension of this vector space is equal to the number of partitions of n, denoted p(n). 1.1.2 Other symmetric function bases The elementary symmetric functions, eλ can be considered as a product of certain monomial symmetric functions. 4 Definition 1.1.2. e0 = mφ = 1, en = m(1n ) = ∑ xi1 xi2 · · · xin (n ≥ 1), i1 <i2 <...<in eλ = eλ1 eλ2 · · · eλl for λ = (λ1 , λ2 , . . . , λl ). The set {eλ : λ ⊢ n} is a basis for Λn . For any partition λ , eλ can be written as a positive sum of monomial symmetric functions. One defines the homogeneous symmetric functions, hλ by the formulae Definition 1.1.3. h0 = mφ = 1, hn = ∑ mλ = λ ⊢n ∑ xi1 xi2 · · · xin (n ≥ 1), i1 ≤i2 ≤...≤in hλ = hλ1 hλ2 · · · hλl for λ = (λ1 , λ2 , . . . , λl ). The homogeneous symmetric functions can be written as a linear combination of the monomial symmetric functions with positive integer coefficients, and the set {hλ : λ ⊢ n} is also a basis of Λn . A third basis given by the power sum symmetric functions pλ is defined by the formulae 5 Definition 1.1.4. p0 = mφ = 1, pn = m(n) = ∑ xin (n ≥ 1), i≥1 pλ = pλ1 pλ2 · · · pλl for λ = (λ1 , λ2 , . . . , λl ). Example 1.1.5. Some examples of the symmetric functions introduced above are the following: e2 = x1 x2 + x1 x3 + x2 x3 + x1 x4 + . . . = ∑ xi x j = m(1,1) . i< j e(2,1) = e2 e1 = x12 x2 + x1 x22 + x12 x3 + x1 x2 x3 + . . . = m(2,1) + 3m(1,1,1) . h2 = m(2) + m(1,1) = ∑ xi2 + i≥1 ∑ xi x j . 1≤i= j h(2,1) = h2 h1 = x13 + x12 x2 + x12 x3 + · · · + x12 x2 + x1 x22 + x1 x2 x3 + · · · + x12 x3 + x1 x32 + x1 x2 x3 + · · · = 3m(1,1,1) + 2m(2,1) + m(3) . p2 = ∑ xi2 . i≥1 6 p(2,1) = p2 p1 = x13 + x23 + · · · + x12 x2 + x1 x22 + · · · = m(3) + m(2,1) . Both the elementary and the homogeneous symmetric functions can be written in terms of the power sum symmetric functions. Given a partition λ , let mi denote the number of i’s in λ for i ≥ 1. Define zλ = ∏ imi mi ! . (1.5) i≥1 The quantity zλ has a combinatorial interpretation as well. Given a permutation π ∈ Sn , define the cycle type of π to be the partition obtained when the cycle lengths occurring in π ’s cycle decomposition are listed in weakly decreasing order. Then, zλ is the number of permutations in Sn that commute with a fixed permutation of cycle type λ . Example 1.1.6. The permutation π = (135)(26)(48)(7) has cycle type (3, 2, 2, 1) and the number of permutations in S8 that commute with π , z(3,2,2,1) , is 1 × 22 × 2! × 3 = 24. There also exist the following relations hn = en = pλ , z λ ⊢n λ ∑ p ∑ ελ zλλ , (1.6) (1.7) λ ⊢n where ελ = (−1)n−l(λ ) . For an exhaustive discussion on symmetric function bases, the reader should 7 refer to [23]. 1.2 Semi-standard Young tableaux Each partition λ of n is associated to a collection of cells (or squares) called a Ferrers diagram (or a Young diagram), where the i-th row consists of (left justified) λi cells. We will be identifying λ with its Ferrers diagram. Example 1.2.1. The Ferrers diagram of λ = (5, 3, 3, 1) is . The conjugate, λ t , of a partition λ = (λ1 , λ2 , . . . , λl ) is the shape obtained by transposing the Ferrers diagram of λ . Thus, the conjugate of the partition λ = (5, 3, 3, 1) is λ t = (4, 3, 3, 1, 1), shown below, . A filling of a Ferrers diagram λ is a map T : λ → N, i.e., T is a map assigning a positive integer to every square/cell of the Ferrers diagram λ . A semi-standard Young tableau (SSYT) of shape λ is a filling of λ satisfying the condition that T is weakly increasing along each row and strictly increasing along each column in λ . A standard Young tableau (SYT) of shape λ ⊢ n is a certain type of SSYT in which the map T is a bijection from λ to [n] = {1, 2, . . . , n}. The fact that T 8 is a bijection implies that the entries in the rows and columns of λ are strictly increasing. Example 1.2.2. A SSYT of shape λ = (5, 3, 3, 1) is 1 3 3 3 4 2 4 4 5 5 5 6 , while an example of an SYT of the same shape is 1 3 5 7 9 2 4 8 6 1011 12 . The multiset of positive integers that appear in a filling of a shape λ is called the content of T . We can also let content(T) be the tuple α where αi equals the number of times i appears in T . Clearly, the sum of the entries in the tuple α is |λ |, the size of the partition. For example, the content of the SSYT in Example 1.2.2 is (1,1,3,3,3,1) as a tuple. As a multiset, the content is {1, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6}. From this point onwards, we will think of the content as a tuple. Given a partition λ ⊢ n and a tuple µ of non-negative integers summing to n, the Kostka number Kλ ,µ is defined as the number of SSYT of shape λ and content µ . Currently, a simple formula to compute Kλ ,µ is not known. But there is one important case where such a formula is known and the next section covers that particular case. 9 1.2.1 The hook length formula The number of SYTs of shape λ ⊢ n is the Kostka number Kλ ,(1n ) . We will denote this number by fλ , and it can be easily calculated by using the Hook Length Formula of Frame, Robinson and Thrall [11]. Before we can state the formula, we will need the following definitions. Definition 1.2.3. Let c be a cell contained in a Ferrers diagram λ . Its arm length, a(c), equals the number of cells to the right of c in the same row of λ as c. Its leg length, l(c), equals the number of cells below c in the same column of λ as c. Definition 1.2.4. Let c be a cell belonging to a Ferrers diagram λ . The hook length of c, denoted by h(c), is one plus the sum of the arm length and leg length of c, i.e., h(c) = a(c) + l(c) + 1. Example 1.2.5. Let λ = (5, 3, 3, 1). Then the entry in each cell of the Ferrers diagram of λ below gives the respective hook length. 8 6 5 2 1 5 3 2 4 2 1 1 This brings us to the celebrated hook length formula[11]. Theorem 1.2.6. Given a partition λ of n, fλ = n! , ∏c∈λ h(c) where h(c) denotes the hook length of the cell c. 10 On using the hooklength formula for Example 1.2.5 we obtain that the number of SYT of shape (5, 3, 3, 1) is f(5,3,3,1) = 12! (8 · 6 · 5 · 5 · 4 · 3 · 2 · 2 · 2 · 1 · 1 · 1) = 4158. The importance and beauty of this result can be gauged from the fact that it has been proved in a variety of ways, including a probabilistic proof by Greene, Nijenhuis and Wilf [15] and a bijective proof by Novelli, Pak and Stoyanovskii [17]. Some classical results, present in [23], in this context are ∑ fλ2 = n! , λ ⊢n and ∑ fλ = coefficient of λ ⊢n z+z2 zn in e 2 . n! Note that the second of these identities gives us the number of SYTs of a fixed size. Now it is natural to ask how many SYTs are there of fixed size n if one imposes a constraint that the number of parts of λ ⊢ n is bounded above by some fixed positive integer k. This means we are interested in the sum τk (n) = ∑ λ ⊢n l(λ )≤k fλ . This is also a well studied question, as is evident from [3, 4, 13, 19]. In [13], Gessel 11 considered the generating function τk (z) = ∞ ∑ τk (n) n=0 zn , n! and obtained determinantal formulae for τk (z). He also showed [13] that the generating function τk (z) is D-finite. That is to say that they satisfy linear differential equations with polynomial coefficients in z. The expressions for τk (n) are unwieldy when k is large. But for relatively small values of k, these expressions are more succinct than what one would expect from the hooklength formula. Regev [19] worked out the values for τ2 (n) and τ3 (n). In particular, he obtained τ2 (n) = n ⌊ n2 ⌋ 1 n i≥0 i + 1 2i , τ3 (n) = ∑ 2i i . Note that τ3 (n) is actually the Motzkin number Mn which has quite a few interpretations [23]. Gessel [13] and Gouyou-Beauchamps [14] found an expression for τ4 (n) and Gouyou-Beauchamps in the same paper [14] found an expression for τ5 (n). The expressions were: ⌊ 2n ⌋ τ4 (n) = C⌊ n+1 ⌋C⌈ n+1 ⌉ , τ5 (n) = 6 ∑ 2 2 i=0 n (2i + 2)! , Ci (i + 2)!(i + 3)! 2i where Ci = = 1 2i , i+1 i 1 (2i)! , i + 1 (i)!(i)! is the i-th Catalan number. For the sake of ready reference, we will put the above 12 results as a theorem, the way they are presented in Theorem 15 of [13]. Theorem 1.2.7. ([13, Theorem 15]) Let τk (n) be the number of standard tableaux with n entries and at most k rows, and let Cn be the Catalan number τ2 (n) = 1 2n n+1 n . Then n , ⌊ n2 ⌋ 1 n τ3 (n) = ∑ i≥0 i + 1 2i 2i , i τ4 (n) = C⌊ n+1 ⌋C⌈ n+1 ⌉ , 2 ⌊ 2n ⌋ τ5 (n) = 6 ∑ i=0 2 n (2i + 2)! . Ci (i + 2)!(i + 3)! 2i (1.8) For over sixty interpretations of the Catalan numbers, the interested reader is referred to [23]. The one that concerns us is that Cn is equal to the number of SYTs of shape (n, n), i.e., f(n,n) = Cn . (1.9) This can be easily seen to be true by using the hooklength formula. Another byproduct of the hooklength formula is the fact that f(n,n−1) = Cn . (1.10) We will also be needing expressions for f(n,n−1,1) and f(n−1,n−1,1) for our purposes. 13 Proposition 1.2.8. Given n ≥ 2, we have (n − 1)(n + 1) Cn+1 , 2n + 1 n−1 f(n−1,n−1,1) = Cn . 2 f(n,n−1,1) = (1.11) (1.12) Proof. For n = 2 and 3, the proof that follows doesn’t hold, but a manual check can quickly reveal that the identities hold. Henceforth, n ≥ 4. The hooklengths for each of the cells in the first row of the Ferrers diagram of the partition (n, n − 1, 1) from left to right are (n + 2, n, n − 1, . . . , 3, 1). The hooklengths for each of the cells in the second row are (n, n − 2, n − 3, . . . , 2, 1). The third row has just one cell and the associated hooklength is 1. The hooklength formula implies f(n,n−1,1) = = = = = (2n)! (n + 2) · (n) · (n − 1) · · · 3 · 1 · (n) · (n − 2) · · · 2 · 1 · 1 2(n − 1) × (2n)! (n + 2) × n! × n! 2(n − 1)(n + 1)2 (2n + 1) × (2n)! (2n + 1) × (n + 2)! × (n + 1)! (n − 1)(n + 1) × (2n + 2)! (2n + 1) × (n + 2)! × (n + 1)! (n − 1)(n + 1) Cn+1 . (1.13) (2n + 1) We will approach the calculation of f(n−1,n−1,1) similarly. In this case, the hooklengths of the cells in the first row are (n + 1, n − 1, n − 2, . . . , 3, 2) and the hooklengths of the cells in the second row are (n, n − 2, n − 3, . . . , 2, 1). The hook- 14 length formula then gives us f(n−1,n−1,1) = = = = (2n − 1)! (n + 1) · (n − 1) · (n − 2) · · · 3 · 2 · (n) · (n − 2) · · · 2 · 1 · 1 2n(n − 1) × (2n − 1)! 2 × (n + 1)! × n! (n − 1) × (2n)! 2 × (n + 1)! × n! (n − 1) Cn . (1.14) 2 1.3 Schur functions Given that the Schur functions are so protean, it is natural to expect that they can be defined in many ways. We will stick to the approach of defining the Schur functions combinatorially by appealing to semi-standard Young tableaux. This approach, and an alternate formulation that is algebraic and expresses the Schur functions as a quotient of determinants can be found in [23]. 1.3.1 Combinatorial definition Like the other symmetric functions we have encountered, the Schur functions are indexed by partitions. We will proceed to describe how to associate a Schur function sλ given a partition λ . Let SSY T (λ ) be the set of all semi-standard Young tableaux of shape λ . We may associate a monomial xT to every semi-standard Young tableau T ∈ SSY T (λ ) in the following manner. Let α = (α1 , α2 , . . .) be the content of T . Note that we are considering the content here as the tuple α where αi counts the number of times 15 i appears in T (and not as a multiset). Then the monomial weight is associated as follows: xT = x1α1 x2α2 · · · . Example 1.3.1. Let λ = (5, 3, 3, 1) and T ∈ SSY T (λ ) be 1 1 2 3 3 3 4 4 5 5 7 6 . Then content(T ) = (2, 1, 3, 2, 2, 1, 1) and xT = x12 x2 x33 x42 x52 x6 x7 . There is a generalization of SSYT’s of shape λ that fits naturally in the theory of symmetric functions. If λ and µ are partitions such that µ ⊆ λ , i.e., l(µ ) ≤ l(λ ) and µi ≤ λi for all i = 1, 2, . . . , l(µ ), then the skew shape λ /µ is determined by removing the first µi cells from the i-th row of the Ferrers diagram of λ . A semistandard Young tableau of shape λ /µ is a skew shape λ /µ that has cells filled with positive integers so that the rows are weakly increasing and the columns are strictly increasing. The content and the monomial weight associated with a semi-standard Young tableau of skew shape are defined in the same way as before. Example 1.3.2. If λ = (5, 3, 3, 1) and µ = (3, 2, 1), then an SSYT T of skew shape (5, 3, 3, 1)/(3, 2, 1) is 1 1 2 1 3 4 , 16 and xT = x13 x2 x3 x4 . With the definition of a SSYT of skew shape in hand, we are ready to define skew Schur functions. Definition 1.3.3. Given a skew shape λ /µ , the skew Schur function sλ /µ of shape λ /µ is the formal power series sλ /µ (x) = ∑ xT , T where the sum is over all SSYTs T of shape λ /µ . If µ = φ , then λ /µ = λ , and we call sλ the Schur function of shape λ . Though by no means obvious, it turns out that the skew Schur functions are symmetric and the elements of the set {sλ : λ ⊢ n} form a basis for Λn . It is clear that sλ (x) is a formal power series in infinitely many variables {x1 , x2 , . . .}, and one could potentially restrict it to the set of variables {x1 , x2 , . . . , xn } by setting xi = 0 for i > n. This is equivalent to considering only SSYTs with entries in the set [n] = {1, 2, . . . , n} as the weight of any SSYT with an entry greater than n will be 0, and hence its contribution to the above formal power series defining sλ (x) will be 0. In the example given below, we are limiting ourselves to three variables x1 , x2 and x3 . Example 1.3.4. Let λ = (2, 1). Then SSY T (λ ) with maximum entry being 3 is the collection 1 1 2 1 1 3 1 2 2 1 2 3 1 3 2 17 1 3 3 2 2 3 2 3 3 , and therefore s(2,1) (x1 , x2 , x3 ) = x12 x2 + x12 x3 + x1 x22 + 2x1 x2 x3 + x1 x32 + x22 x3 + x2 x32 . The coefficient of a monomial x1α1 x2α2 · · · xnαn in sλ is the Kostka number Kλ ,α where α = (α1 , α2 , . . . , αn ) corresponds to the content and λ is the shape. This equals the number of SSYTs of shape λ and content α . In particular, if λ ⊢ n then the coefficient of x1 x2 · · · xn is the number of standard Young tableaux of shape λ , fλ . More generally, one can define the skew Kostka number Kλ /µ ,α to be the number of SSYTs of shape λ /µ and content α . Now that we are done defining bases for the space of symmetric functions Λn , we will equip this space with an inner product , inner product and is defined by setting sλ , sµ Λn Λn . This is called the Hall = δλ µ and then defining the inner product for any f , g ∈ Λn by linear extension. One can clearly extend this to an inner product on Λ, in which case we will refer to it as , Λ. The Hall inner product has the following properties: pλ , pµ Λn hλ , mµ = δλ µ z λ , Λn = δλ µ , where δ denotes the Kronecker delta. The way we have defined the inner product, we ensure that the Schur functions are an orthonormal basis of Λn . Equipped with the Hall inner product and the definition of skew Schur functions, one can establish a very fundamental property of skew Schur functions. 18 Theorem 1.3.5. For any f ∈ Λ, we have f s µ , , sλ Λ = f , sλ / µ Λ. An alternate description could be as follows. Given a fixed partition µ , one can think of multiplication by sµ as a linear operator on Λ. If one defines the linear ⊥ transformations sµ : Λ → Λ and s⊥ µ : Λ → Λ defined by sµ ( f ) = sµ f and sµ (sλ ) = sλ /µ , then the operators sµ and s⊥ µ are adjoint with respect to the inner product , Λ. In particular, sν s µ , sλ Λ = sν , sλ / µ Λ . For further such details about Schur functions, the reader is referred to [23]. Now we will describe a combinatorial procedure for multiplying two Schur functions. This also corresponds to the outer tensor product of characters of the symmetric group. We will need a few more definitions before we can outline the procedure for multiplication. The skew reading word corresponding to an SSYT of skew shape is the word obtained by reading the entries bottom to top, left to right. Thus, the skew reading word of the tableau in Example 1.3.2 is 413211. Definition 1.3.6. A word w is called a reverse lattice word if wr , that is the word w read backwards, has the property that any prefix of wr contains at least as many instances of a positive integer i as it does of i + 1. For instance, w = 413211 is a reverse lattice word while w = 1233221 is not. The Littlewood-Richardson coefficient, cλµν , is equal to the number of skew 19 tableaux of shape λ /µ and content ν such that the skew reading word of the tableau is a reverse lattice word. This given, the following identity [23] describes the product of two Schur functions sµ (x)sν (x) = ∑ cλµν sλ (x), λ where the sum is over all λ such that µ ⊆ λ and |µ | + |ν | = |λ |. In terms of the inner product on Λ, this identity is equivalent to sµ sν , sλ Λ = cλµν . Thus, we obtain a combinatorial rule to multiply two Schur functions by counting SSYTs of skew shape satisfying certain contraints (commonly called the Littlewood-Richardson rule). Example 1.3.7. Consider the computation of the product s(2,1) s(2,2) . To accomplish this, we are required to list all skew tableaux of shape λ /(2, 1) with content (2, 2) such that the skew reading word is a reverse lattice word. • • 1 • • 1 1 • • 1 • • 1 • 2 • • 1 1 • 2 • 1 2 • 1 1 • 2 2 2 2 2 2 , , , , 2 , • • • 1 1 2 2 . (3,2,2) Thus, for example, we have c(2,1)(2,2) = 1, and s(2,1) s(2,2) = s(4,3) + s(4,2,1) + s(3,3,1) + s(3,2,2) + s(3,2,1,1) + s(2,2,2,1) . We will now look at a special case of the Littlewood-Richardson rule. It describes the multiplication of a Schur functions with a Schur function indexed by a row shape or a column shape. This amounts to multiplying a Schur function 20 sλ (x) with a complete homogeneous symmetric function hn (x) or an elementary symmetric function en (x). It is called the Pieri rule but before we state the rule we need to describe certain skew shapes. A skew shape λ /µ is called a horizontal strip if it does not contain squares in the same column, and is called a vertical strip if it does not contain squares in the same row. Theorem 1.3.8. If µ is a partition, then sµ s(n) = sµ hn = ∑ sν , ∑ sν . ν ⊢|µ |+n ν /µ =horizontal strip of size n and sµ s(1n ) = sµ en = ν ⊢|µ |+n ν /µ =vertical strip of size n For a demonstration of how this rule aids calculations, consider the following example. Example 1.3.9. We will compute s(3,3,1) s(2) using the Pieri rule. This rule implies we should list partitions λ ⊢ 9 such that the skew shape λ /(3, 3, 1) is a horizontal strip of size 2. Thus the possible λ are • • • • • • , • , • • , • 21 , . Thus we obtain s(3,3,1) s(2) = s(4,3,2) + s(4,3,1,1) + s(3,3,3) + s(3,3,2,1) + s(5,3,1) . We can compute s(3,3,1) s(1,1) in a similar fashion. The Pieri rule implies we should list partitions λ ⊢ 9 such that the skew shape λ /(3, 3, 1) is a vertical strip of size 2. Thus, the possible λ are • • • • • , • , • , • • , • . and therefore s(3,3,1) s(1,1) = s(4,4,1) + s(4,3,2) + s(4,3,1,1) + s(3,3,2,1) + s(3,3,1,1,1) . 1.4 Basic representation theory of Sn A representation of a group G is a homomorphism ρ : G → GL(V ) for some finite dimensional vector space V over C. Here GL(V ) denotes the general linear group of V , i.e. the group of all automorphisms of V . After fixing a basis for V , we can think of the representation ρ as a mapping of a group element to an invertible matrix, and we willl call this a matrix representation. We might abuse notation and make no explicit reference to ρ by referring to V as the representation, and letting the [g] denote the matrix ρ (g) for an element g ∈ G. A subrepresentation of a representation V is a subspace W ⊆ V that is invariant 22 under the action of G. A representation V is called irreducible if the only subrepresentations are {0} and V itself. It is well known that every finite dimensional representation of a finite group is isomorphic to the direct sum of a finite number of irreducible representations. Furthermore, the number of these irreducible representations is the number of conjugacy classes of the group. For details, the reader can refer to [22, Chapter 1]. Our only concern here are the representations of the symmetric group Sn . The irreducible representations of Sn are indexed by partitions, and there is a well known construction [18] of the irreducible representation V λ for any λ ⊢ n, called the Specht module corresponding to λ . The character of a representation of a finite group G is a map G → C defined by g → trace([g]). Since the trace of a matrix is conjugation invariant, the trace is a class function i.e. it is constant on conjugacy classes. In the case of the symmetric group, the conjugacy classes are also indexed by the partitions as all permutations with the same cycle type are conjugates. We will denote the character of the irreducible Specht module V λ by χλ . The fact that forms the bedrock of most results in finite group representation theory is the following [22]. Proposition 1.4.1. Every representation of a finite group is determined (upto isomorphism) by its character. Let CF n denote the space of class functions from Sn to Q (we are using Q since the characters of Sn can be realized over Q). CF n has a natural inner product , defined by f,g CF n = 1 f (π )g(π ). n! π∑ ∈Sn 23 CF n Our main tool that reduces character computations to symmetric functions manipulation is a linear transformation ch : CF n → Λn called the characteristic map or the Frobenius map. If f ∈ CF n , then define ch( f ) = = 1 f (π )pπ , n! π∑ ∈Sn 1 ∑ zµ f (µ )pµ , µ ⊢n wherein we have used the fact that f is a class function which basically means that f (π ) is decided completely by π ’s cycle type. The pπ above also refers to the power sum symmetric function indexed by the partition that is the cycle type of π . A very important property of the Frobenius map is the following [22, 23]. Proposition 1.4.2. The linear tranformation ch is an isometry, i.e., f,g CF n = ch( f ), ch(g) Λn . It can be shown that ch(χλ ) = sλ , which in particular implies that sλ , pµ Λn = χλ (µ ) where µ ⊢ |λ |. We have managed to cover those aspects of the representation theory of the symmetric group that concern us most. A detailed account of the same can be found in [23]. 1.5 The Kronecker product of Schur functions We start by describing the Kronecker coefficients at the level of the characters of the symmetric group. Let λ , µ and ν be partitions of n. The Kronecker coefficients 24 gλµν are defined by gλµν = χλ , χµ χν CF n = 1 χλ (π )χµ (π )χν (π ) n! π∑ ∈Sn = ∑ zγ χλ (γ )χµ (γ )χν (γ ) 1 . (1.15) γ ⊢n The fact that the Kronecker coefficients are symmetric in λ , µ and ν is clearly highlighted in the above formulation. The relevance of the Kronecker coefficients comes from the fact that follows. Recall that V µ is the irreducible representation corresponding to the character χµ . Then the pointwise product χµ χν is the character of V µ ⊗ V ν , the representation obtained by taking the tensor product of V µ and V ν . Moreover, gλµν is the multiplicity of V λ in V µ ⊗V ν , i.e., it is the number of times a module isomorphic to V λ occurs in the direct sum decomposition of V µ ⊗V ν into irreducible representations. To obtain an interpretation in terms of symmetric functions, let f , g ∈ Λn . The Kronecker product, f ∗ g, is defined by f ∗ g = ch(uv) , where u and v are class function belonging to CF n such that ch(u) = f , ch(v) = g and uv(π ) = u(π )v(π ). If we set f = sµ , g = sν where both µ , ν are partitions of n 25 then by the property of the Frobenius map we have u = χµ , v = χν . Therefore s µ ∗ sν , sλ Λn = ch(χµ χν ), sλ = ∑ zγ χµ χν (γ )pγ , sλ Λn 1 γ ⊢n = Λn 1 ∑ zγ χµ (γ )χν (γ )pγ , sλ γ ⊢n = Λn 1 ∑ zγ χλ (γ )χµ (γ )χν (γ ) γ ⊢n = gλµν . (1.16) One can also prove easily that pλ pµ p ∗ = δλ µ λ . zλ z µ zλ Notice that the Kronecker product has the following symmetries: s µ ∗ sν = sν ∗ s µ , s µ ∗ sν = sν t ∗ s µ t , where µ t denotes the conjugate of the partition µ . Moreover, if µ , ν ⊢ n then (n) (1n ) gµν = gµν t = δµν . Given that the Kronecker coefficients are positive by the above interpretation as a multiplicity of a character of Sn in a tensor product of two characters, one expects a combinatorial rule for computing these Kronecker coefficients. To date, there is no satisfying positive combinatorial or algebraic formula for the Kronecker product 26 of two Schur functions. Attempts have been made to understand different aspects of these coefficients, for example, special cases [5–7, 20, 21], asymptotics [1, 2], stability [24], the complexity of computing them and conditions which guarantee that the Kronecker coefficients are non-zero [8]. In the next section, we review some of the prior work done on computing Kronecker coefficients by stating the main results that we will be using. 1.6 A brief survey of relevant results The motivation for the results in this thesis has been the recent results on Kronecker product of two Schur functions, both indexed by two row partitions with one of them being rectangular. Although the description of the Kronecker product of two Schur functions indexed by general two row partitions had already been obtained by [20, 21], an alternative characterisation was sought so as to attack the general problem and for the sake of developing computational tools. Before we recall the relevant results, we will establish some notation that we will stick to throughout. Given a non-negative integer n, let Pn = {λ = (λ1 , λ2 , λ3 , λ4 ) : λ ⊢ 2n, λi ≥ 0 and λi all even or all odd)} , Qn = {λ = (λ1 , λ2 , λ3 , λ4 ) : λ ⊢ 2n, λi ≥ 0 and exactly two of λi are odd)} . This given, let Pn , P= n≥0 Qn , Q= n≥0 27 and it is amply clear that P ∪ Q is the set of all partitions of even size and length at most 4. To reiterate a point we made earlier, when we consider partitions in P or Q, we identify partitions which differ only in the number of trailing zeroes. For instance, if λ = (4, 4, 2), then the statement ‘λ belongs to P’ is true even though we have not written λ as a partition with 4 parts. We will also be needing the Knuth bracket for giving truth values to statements. We say ((S)) = 1 if the statement S is true (1.17) 0 otherwise. Given partitions λ and µ , one can define their difference to be the sequence composed of pointwise differences, i.e., the i-th term of the sequence is λi − µi . We let µ P denote the set of partitions λ such that λ − µ ∈ P. For instance, if µ = (2, 1, 1) and λ = (7, 6, 6, 3) then λ − µ = (5, 5, 5, 3) and thus λ ∈ µ P. Now we are in a position to state the results of interest. To start it all, the computation of s(n,n) ∗ s(n,n) in the form given below appeared in [12]. This case was also dealt with in [7]. The results stated the following. Theorem 1.6.1. Given a positive integer n, s(n,n) ∗ s(n,n) = ∑ sλ . (1.18) λ ∈P λ ⊢2n These results were different from earlier characterisations as they explicitly state which partitions have non-zero coefficients and further establish that the coefficients are all either 0 or 1 without giving a combinatorial rule. This computation 28 originally arose out of solving a mathematical physics problem related to resolving the interference of 4 qubits [25]. Example 1.6.2. Consider the computation of s(4,4) ∗ s(4,4) in view of the above theorem. Then, s(4,4) ∗ s(4,4) = s(8) + s(6,2) + s(5,1,1,1) + s(4,4) + s(4,2,2) + s(3,3,1,1) + s(2,2,2,2) . Using the result of [12] as their inspiration, a characterisation of the Kronecker product of s(n,n) ∗ s(n+k,n−k) for k ≥ 0 was obtained in [7]. Their work indicated that the Schur functions expansion of s(n,n) ∗ s(n+k,n−k) has the pattern of a boolean lattice of subsets, in the sense that it can be written as a certain number intersecting sums of Schur functions each with coefficient 1. The main result in [7] stated the following. Theorem 1.6.3. Let λ be a partition of 2n. Then k s(n,n) ∗ s(n+k,n−k) , sλ = ∑ ((λ ∈ (k + i, k, i)P)) i=0 k + ∑ ((λ ∈ (k + i + 1, k + 1, i)P)) . (1.19) i=1 As a demonstration of the result, we will consider an example. Example 1.6.4. Consider the Kronecker product s(4,4) ∗ s(6,2) , i.e., we have n=4 and k=2. Consider λ = (5, 2, 1). Let us see what the above theorem implies for 29 s(4,4) ∗ s(6,2) , sλ . We have 2 s(4,4) ∗ s(6,2) , sλ = ∑ ((λ ∈ (2 + i, 2, i)P)) i=0 2 + ∑ ((λ ∈ (3 + i, 3, i)P)) . i=1 It is clear that (5, 2, 1) can not belong to (3 + i, 3, i)P for i = 1, 2. Also, (5, 2, 1) does not belong to (4, 2, 2)P. Thus, we obtain s(4,4) ∗ s(6,2) , sλ = ((λ ∈ (2, 2, 0)P)) + ((λ ∈ (3, 2, 1)P)) . Now, since (5, 2, 1)−(2, 2, 0) = (3, 0, 1) ∈ / P and (5, 2, 1)−(3, 2, 1) = (2, 0, 0) which does happen to be in P, we obtain s(4,4) ∗ s(6,2) , s(5,2,1) = 1. We have already seen what this theorem implies in the case k = 0. For k = 1, we obtain the following corollary [7]. Corollary 1.6.5. Given a positive integer n, s(n,n) ∗ s(n+1,n−1) = ∑ sλ . (1.20) λ ∈Q λ ⊢2n Example 1.6.6. Let us expand s(4,4) ∗ s(5,3) in the Schur function basis. Then the corollary above tells us that s(4,4) ∗ s(5,3) = s(7,1) + s(6,1,1) + s(5,2,1) + s(5,3) + s(4,3,1) + s(4,2,1,1) + s(3,3,2) +s(3,2,2,1) . A result of Littlewood that we will use a lot, and one that aids the computation 30 of Kronecker coefficients is the following [16]. Theorem 1.6.7. Let α , β and γ be partitions such that |α | + |β | = |γ |. Then, (sα sβ ) ∗ sγ = ∑ ∑ δ ⊢|β | η ⊢|α | γ cη ,δ (sη ∗ sα )(sδ ∗ sβ ) (1.21) γ where cη ,δ are the Littlewood-Richardson coefficients. Using this identity of Littlewood and the characterisation of s(n,n) ∗ s(n,n) , one can prove the following corollary, present in the following form in [7]. Corollary 1.6.8. Given a positive integer n, s(n,n−1) ∗ s(n,n−1) = ∑ λ ⊢2n−1 l(λ )≤4 sλ . (1.22) Now to set ourselves up completely for what follows, we just need one final result that, given partitions µ and ν , describes certain partitions λ for which gλµν = 0. Below, µ ∩ ν denotes the partition obtained by intersecting the corresponding Ferrers diagrams. To illustrate this point, we will give an example. Example 1.6.9. Let ν= , and µ= . 31 Then µ ∩ ν is represented by the following Ferrers diagram . Dvir [10] and Clausen and Meier [9] proved the following theorem. Theorem 1.6.10. Let µ , ν be partitions of n. Then max {λ1 : gλµν = 0 for some λ = (λ1 , λ2 , . . .)} = |µ ∩ ν |, max {m : gλµν = 0 for some λ = (λ1 ≥ λ2 ≥ · · · ≥ λm > 0)} = |µ ∩ ν t |. The import of this theorem can be gauged by the fact that it already implies that if µ and ν are partitions each with at most two rows, then gλµν is 0 for all λ such that l(λ ) ≥ 5. 1.7 Summary of results present in this thesis In this thesis, we provide explicit formulae for the Kronecker coefficients occurring in the expansion of s(n,n−1,1) ∗ s(n,n) , s(n−1,n−1,1) ∗ s(n,n−1) , s(n−1,n−1,2) ∗ s(n,n) , s(n−1,n−1,1,1) ∗ s(n,n) and s(n,n,1) ∗ s(n,n,1) on page 39 in Section 2.1, page 41 in Section 2.2, page 49 in Section 2.3, page 56 in Section 2.4 and page 67 in Section 2.5 respectively. One of the main tools we use is the Pieri rule, which gives an easy way to compute products of the form s(1) sλ , s(2) sλ and s(1,1) sλ and also provides a ⊥ ⊥ succinct description of the skewing operators s⊥ (1) , s(2) and s(1,1) . Another crucial result that we use is an identity of Littlewood, which is Theorem 1.6.7, allowing us 32 to compute the Kronecker coefficients in terms of certain Littlewood-Richardson coefficients and previously obtained characterizations of the Kronecker product of Schur functions indexed by two-rowed partitions. In arriving at Theorem 2.6.3, we use the knowledge of the Kronecker coefficients occurring in s(n,n−1,1) ∗ s(n,n) and s(n,n,1) ∗ s(n+1,n) to obtain an enumeration of standard Young tableaux of height 5 and smallest part equalling 1. This is done by translating the relevant Kronecker product decomposition to the language of characters and equating dimensions. In doing so, note that what we enumerate is actually the number of lattice words of length n which consist of letters 1,2,3,4 or 5 with exactly one occurrence of 5. 33 Chapter 2 Description of Kronecker Coefficients in Certain Cases We start by establishing some notation which the reader has not encountered in the introduction. Let ′ • λ = the partition (λ1 , λ2 , λ3 , λ4 ), given a partition λ . In case, λ has length less than 4, then we supplement it with an appropriate number of zeroes to ′ ′ get λ . Thus, for example, if λ = (5, 3, 3, 2, 1, 1), then λ = (5, 3, 3, 2) and if ′ λ = (5, 3, 2) then λ = (5, 3, 2, 0). ′ • Oλ = the number of odd parts in λ . ′ • Eλ = the number of even non-zero parts in λ . ′ ′ • Oλ = the number of distinct odd parts in λ . ′ ′ • Eλ = the number of distinct even non-zero parts in λ . 34 • Rλ = the number of distinct non-zero parts of λ which occur at least twice. For illustration’s sake, consider the case λ = (6, 5, 3, 3, 3, 2, 2). Then R(λ ) = 2. If the parts in λ are all distinct, then Rλ = 0. • Sλ /µ = the set of partitions θ ⊢ (|λ | − |µ |) such that sθ , sλ /µ = 0, given partitions λ and µ . Equivalently, the Littlewood-Richardson coefficient cλθ ,µ is non-zero. • dλ = the number of distinct non-zero parts in λ . • dλ ,2 = the number of partitions γ such that there exists an index i so that γi + 2 = λi and γ j = λ j for all j = i. Again, if we consider the case where λ = (6, 5, 3, 3, 3, 2, 2). Then dλ ,2 = 2 as the possible γ that satisfy the condition mentioned above are (6, 3, 3, 3, 3, 2, 2) and (6, 5, 3, 3, 3, 2, 0). In the sections that follow, the statement ‘λ ∈ P’ is considered to be equiva′ lent to ‘λ ∈ P’, and an analogous statement holds for a statement like ‘λ ∈ Q’. For example, consider λ = (5, 3, 3, 1, 1). Then, even though λ has 5 parts, we say ′ ((λ ∈ P)) evaluates to 1 because λ = (5, 3, 3, 1) has all 4 parts odd, and thus belongs to P. 2.1 s(n,n−1,1) ∗ s(n,n) (n ≥ 2) We will now give an explicit characterization of the Kronecker product of s(n,n−1,1) and s(n,n) . 35 Observe that the Pieri rule (Theorem 1.3.8) implies s(n,n−1,1) = s(n,n−1) s(1) − s(n,n) − s(n+1,n−1) . (2.1) Since we are looking for the coefficient of sθ , where θ ⊢ 2n, in the expansion of s(n,n−1,1) ∗ s(n,n) as a sum of Schur functions, we should compute s(n,n−1,1) ∗ s(n,n) , sθ . Using (2.1), we obtain = s(n,n−1,1) ∗ s(n,n) , sθ (s(n,n−1) s(1) ) ∗ s(n,n) , sθ − (s(n,n) + s(n+1,n−1) ) ∗ s(n,n) , sθ . (2.2) We will look to evaluate the inner products appearing on the right hand side of (2.2) individually. The use of Theorem 1.6.7 implies (s(n,n−1) s(1) ) ∗ s(n,n) = = ∑ ∑ δ ⊢1 η ⊢2n−1 ∑ (n,n) cη ,δ (sη ∗ s(n,n−1) )(sδ ∗ s(1) ) (n,n) η ⊢2n−1 cη ,(1) (sη ∗ s(n,n−1) )(s(1) ∗ s(1) ). (2.3) (n,n) The Pieri rule yields that cη ,(1) = 0 if and only if η = (n, n − 1), in which case (n,n) c(n,n−1),(1) = 1. Since s(1) ∗ s(1) = s(1) , we conclude that (s(n,n−1) s(1) ) ∗ s(n,n) = s(1) (s(n,n−1) ∗ s(n,n−1) ). 36 (2.4) This reduces (2.2) to s(n,n−1,1) ∗ s(n,n) , sθ = s(1) (s(n,n−1) ∗ s(n,n−1) ), sθ − (s(n,n) + s(n+1,n−1) ) ∗ s(n,n) , sθ = s(n,n−1) ∗ s(n,n−1) , s⊥ (1) sθ − (s(n,n) + s(n+1,n−1) ) ∗ s(n,n) , sθ ∑ = λ ⊢2n−1 l(λ )≤4 sλ , sθ /(1) − ∑ λ ⊢2n l(λ )≤4 sλ , sθ . (2.5) In arriving at the last step in the above sequence (2.5), we’ve made use of ∑ the identities (1.22),(1.20) and (1.18). Notice λ ⊢2n l(λ )≤4 0 otherwise. So we will focus on evaluating ∑ λ ⊢2n−1 l(λ )≤4 sλ , sθ is 1 if l(θ ) ≤ 4 and sλ , sθ /(1) . We appeal to the Pieri rule again to see how sθ /(1) decomposes in the Schur basis. It implies sθ /(1) = ∑ θ − ≺θ sθ − . (2.6) In the equality above, θ − ≺ θ means that θ covers θ − in the Young’s lattice of partitions. Alternatively put, sθ /(1) is the sum of all terms of the form sθ − , where θ − is obtained by removing an inner corner of the partition θ . Note that the number of terms appearing on the right hand side of (2.6) is equal to the number of distinct parts in the partition θ , i.e. dθ . If s(n,n−1,1) ∗ s(n,n) , sθ = 0, then we must have that l(θ ) ≤ 5 by Theorem 1.6.10, as |(n, n − 1, 1) ∩ (n, n)t | ≤ 5. We will carry out the rest of the computa37 tion in cases depending on the length of the partition θ . 2.1.1 Case I: l(θ ) = 5 If l(θ ) = 5, but θ5 ≥ 2, then sθ /(1) is sum of terms of the form sγ with l(γ ) = 5. The right hand side of (2.5) clearly implies that the coefficient of sθ in s(n,n−1,1) ∗ s(n,n) is 0 in this instance. If θ5 = 1, then sθ /(1) = sθ ′ + sum of terms of the form sγ where l(γ ) = 5. This in turn means that ∑ λ ⊢2n−1 l(λ )≤4 s(n,n−1,1) ∗ s(n,n) , sθ = sλ , sθ /(1) = 1. Thus, if l(θ ) = 5, 1 θ5 = 1 0 otherwise. 2.1.2 Case II: l(θ ) ≤ 4 We know that if l(θ ) ≤ 4, then (s(n,n) + s(n+1,n−1) ) ∗ s(n,n) , sθ = 1, as θ either belongs to P or it belongs to Q. The following computation helps us in finishing this case. ∑ λ ⊢2n−1 l(λ )≤4 sλ , sθ /(1) = ∑ λ ⊢2n−1 l(λ )≤4 sλ , ∑ θ − ≺θ = dθ . sθ − (2.7) Therefore s(n,n−1) ∗ s(n,n−1) , s⊥ (1) sθ = dθ . 38 (2.8) Thus for l(θ ) ≤ 4, s(n,n−1,1) ∗ s(n,n) , sθ = dθ − 1. 2.1.3 Summary On collecting the results of the two cases together, we obtain the following description s(n,n−1,1) ∗ s(n,n) , sθ 1 l(θ ) = 5, θ5 = 1 = dθ − 1 l(θ ) ≤ 4 0 otherwise. As a demonstration, we give an example. Example 2.1.1. Consider the computation of s(4,3,1) ∗ s(4,4) . Then s(4,3,1) ∗ s(4,4) = s(2,2,2,1,1) + s(3,2,1,1,1) + 2s(3,2,2,1) + s(3,3,1,1) + s(3,3,2) +s(4,1,1,1,1) + 2s(4,2,1,1) + s(4,2,2) + 2s(4,3,1) + s(5,1,1,1) +2s(5,2,1) + s(5,3) + s(6,1,1) + s(6,2) + s(7,1) . 2.2 s(n−1,n−1,1) ∗ s(n,n−1) (n ≥ 2) In the same vein as the previous case, we can try finding the Kronecker product of s(n−1,n−1,1) and s(n,n−1) . Again, the Pieri rule implies that 39 s(n−1,n−1,1) = s(1) s(n−1,n−1) − s(n,n−1) . (2.9) An application of Theorem 1.6.7 gives (s(1) s(n−1,n−1) ) ∗ s(n,n−1) = = ∑ ∑ δ ⊢1 η ⊢2n−2 ∑ (n,n−1) cη ,δ (sη ∗ s(n−1,n−1) )(sδ ∗ s(1) ) (n,n−1) η ⊢2n−2 cη ,(1) (sη ∗ s(n−1,n−1) )(s(1) ∗ s(1) ). (2.10) (n,n−1) The Pieri rule dictates that the only cases where cη ,(1) (n,n−1) (n, n − 2) or η = (n − 1, n − 1) and in both cases cη ,(1) = 0 are when η = = 1. Thus (s(1) s(n−1,n−1) ) ∗ s(n,n−1) = s(1) (s(n,n−2) ∗ s(n−1,n−1) ) + s(1) (s(n−1,n−1) ∗ s(n−1,n−1) ). If θ ⊢ 2n − 1, (2.9) and (2.11) together bring us to 40 (2.11) s(n−1,n−1,1) ∗ s(n,n−1) , sθ = s(1) ((s(n,n−2) + s(n−1,n−1) ) ∗ s(n−1,n−1) ), sθ − s(n,n−1) ∗ s(n,n−1) , sθ = (s(n,n−2) + s(n−1,n−1) ) ∗ s(n−1,n−1) , s⊥ (1) sθ − s(n,n−1) ∗ s(n,n−1) , sθ = ∑ λ ⊢2n−2 l(λ )≤4 sλ , sθ /(1) − ∑ λ ⊢2n−1 l(λ )≤4 sλ , sθ . (2.12) Now one can easily check that this gives the same characterization as the one obtained from s(n,n−1,1) ∗ s(n,n) and the argument is essentially the same, except that we use (2.12) instead of (2.5). We obtain s(n−1,n−1,1) ∗ s(n,n−1) , sθ 1 l(θ ) = 5, θ5 = 1 = dθ − 1 l(θ ) ≤ 4 0 otherwise. To see the above characterization in practice, we will consider an example. Example 2.2.1. We will compute s(3,3,1) ∗ s(4,3) . s(3,3,1) ∗ s(4,3) = s(2,2,1,1,1) + s(2,2,2,1) + s(3,1,1,1,1) + 2s(3,2,1,1) + s(3,2,2) + s(3,3,1) +s(4,1,1,1) + 2s(4,2,1) + s(4,3) + s(5,1,1) + s(5,2) + s(6,1) . 41 2.3 s(n−1,n−1,2) ∗ s(n,n) (n ≥ 3) In this particular case, an application of the Pieri rule yields s(n−1,n−1,2) = s(2) s(n−1,n−1) − s(n,n−1,1) − s(n+1,n−1) . (2.13) The Kronecker product of s(n−1,n−1,2) and s(n,n) would require the evaluation of (s(2) s(n−1,n−1) ) ∗ s(n,n) . Using Theorem 1.6.7, one can see that (s(2) s(n−1,n−1) ) ∗ s(n,n) = ∑ ∑ (n,n) δ ⊢2 η ⊢2n−2 ∑ = (n,n) η ⊢2n−2 + cη ,δ (sη ∗ s(n−1,n−1) )(sδ ∗ s(2) ) cη ,(1,1) (sη ∗ s(n−1,n−1) )(s(1,1) ∗ s(2) ) ∑ (n,n) η ⊢2n−2 cη ,(2) (sη ∗ s(n−1,n−1) )(s(2) ∗ s(2) ). (2.14) (n,n) (n,n) Notice that for cη ,(2) = 0 to hold, we must have η = (n, n−2) whereas cη ,(1,1) = (n,n) 0 implies that η = (n − 1, n − 1). In both cases, cη ,δ = 1 where δ = (1, 1), η = (n − 1, n − 1) or δ = (2), η = (n, n − 2). This allows us to rewrite (2.14) as (s(2) s(n−1,n−1) ) ∗ s(n,n) = s(1,1) (s(n−1,n−1) ∗ s(n−1,n−1) ) +s(2) (s(n,n−2) ∗ s(n−1,n−1) ). Now, let θ ⊢ 2n. From the equality above, it follows that 42 (2.15) s(n−1,n−1,2) ∗ s(n,n) , sθ = (s(2) s(n−1,n−1) ) ∗ s(n,n) , sθ − s(n,n−1,1) ∗ s(n,n) , sθ − s(n+1,n−1) ∗ s(n,n) , sθ = s(1,1) (s(n−1,n−1) ∗ s(n−1,n−1) ), sθ + s(2) (s(n,n−2) ∗ s(n−1,n−1) ), sθ − s(n,n−1,1) ∗ s(n,n) , sθ − s(n+1,n−1) ∗ s(n,n) , sθ s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = + s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ − s(n+1,n−1) ∗ s(n,n) , sθ − s(n,n−1,1) ∗ s(n,n) , sθ . (2.16) Since we already have a description of the Kronecker products s(n,n−1,1) ∗ s(n,n) and s(n+1,n−1) ∗ s(n,n) , we can focus on evaluating the other two terms on the right hand side of (2.16) individually. But before that, note the fact that if s(n−1,n−1,2) ∗ s(n,n) , sθ = 0, then l(θ ) ≤ 6 necessarily, by an application of Theorem 1.6.10. So we will restrict ourselves to the partitions θ ⊢ 2n satisfying l(θ ) ≤ 6. We will deal with cases based on the length of the partition θ . 2.3.1 Case I: l(θ ) = 6 In this case, we already know that both the terms s(n+1,n−1) ∗s(n,n) , sθ and s(n,n−1,1) ∗ s(n,n) , sθ are 0. 43 ⊥ Now we deal with s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ . To this end, notice that s(2) sθ is a sum of terms of the form sγ where either γ is a partition obtained by subtracting 2 from one of the parts of θ , or γ is a partition obtained by subtracting 1 from 2 distinct parts of the partition θ . This is a consequence of the Pieri rule again. This implies, if l(θ ) = 6 s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ = 0. (2.17) Next, we will look at s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ . As a consequence of the Pieri rule, notice that s⊥ (1,1) sθ is a sum of terms of the form sγ , where γ ⊢ 2n − 2 is a partition obtained by subtracting 1 each from two different (but not necessarily distinct) parts of θ . We know that if s(n−1,n−1) ∗ s(n−1,n−1) , sγ = 0 then l(γ ) ≤ 4. Thus one can expect s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ to be non-zero if the two smallest parts, θ5 and θ6 , are both equal to 1. In other instances, s⊥ (1,1) sθ is a sum of terms of the form sγ where l(γ ) ≥ 5 which, as noted earlier, can not occur in s(n−1,n−1) ∗ s(n−1,n−1) . Thus, one obtains the following s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = 1 θ ′ ∈ P, θ5 = θ6 = 1 0 otherwise. Thus, in the present case, we obtain s(n−1,n−1,2) ∗ s(n,n) , sθ = 1 θ5 = θ6 = 1, θ ∈ P 0 otherwise. 44 (2.18) 2.3.2 Case II: l(θ ) = 5 In this case, we already know that s(n+1,n−1) ∗ s(n,n) , sθ = 0. The characterization of s(n,n−1,1) ∗ s(n,n) we obtained earlier implies s(n,n−1,1) ∗ s(n,n) , sθ = 1 θ5 = 1 0 otherwise. Now, consider the computation of s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ . One can notice that if θ5 ≥ 3, then s⊥ (2) sθ is a sum of terms of the form sγ where l(γ ) = 5. This ⊥ ′ implies s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ = 0. If θ5 = 2, then s(2) sθ = sθ + sum of terms ′ of the form sγ where l(γ ) = 5. Thus, s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ = 1 if θ ∈ Q. The case where θ5 = 1 is slightly intricate, mainly because if θ4 is also 1, then s⊥ (2) sθ will not have a term with both θ4 and θ5 removed. The only terms in s⊥ (2) sθ which might have a non-zero coefficient in s(n,n−2) ∗ s(n−1,n−1) are of the form sγ where γ ∈ Sθ ′ /(1) with the clause that, we neglect γ ∈ Sθ ′ /(1) which satisfy l(γ ) = 3. This ′ takes care of the case where θ4 = θ5 = 1. Notice that θ has exactly 3 odd parts or ′ exactly 3 even parts, as θ ⊢ 2n − 1. Note that s(n,n−2) ∗ s(n−1,n−1) has terms of the ′ form sγ where γ ∈ Q only, by (1.20). If Eθ ′ = 1 (i.e. θ has exactly 3 odd parts), then we can subtract 1 from any of the distinct odd parts to obtain a partition which belongs to Q, and on subtracting 1 from the even part we obtain a partition which ′ belongs to P. On the other hand, if Oθ ′ = 1 (i.e. θ has exactly 3 even parts), then we can subtract 1 from any of the distinct even parts to obtain a partition which belongs to Q, and on subtracting 1 from the odd part we obtain a partition which belongs to P. This line of reasoning allows us to conclude that 45 ′ ′ ((Eθ ′ = 1))[Oθ ′ − ((θ4 = 1))] s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ = ′ +((Oθ ′ = 1))[Eθ ′ ]. (2.19) Put succinctly, one has s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ 0 1 ′ = Oθ ′ − ((θ4 = 1)) ′ Eθ ′ 0 θ5 ≥ 3 ′ θ5 = 2, θ ∈ Q θ5 = 1, Eθ ′ = 1 (2.20) θ5 = 1, Oθ ′ = 1 otherwise. Shifting our focus to computing s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ , observe that if θ5 ≥ 2, then s⊥ (1,1) sθ is a sum of terms of the form sγ with l(γ ) = 5. Thus, these terms do not appear in s(n−1,n−1) ∗ s(n−1,n−1) . This allows us to narrow our consideration to the case θ5 = 1. In this case s⊥ (1,1) sθ is a sum of terms of the form sγ , where either l(γ ) = 5 (i.e. θ5 is not removed), in which case they can not occur in s(n−1,n−1) ∗ s(n−1,n−1) , or l(γ ) ≤ 4 and γ ∈ Sθ ′ /(1) (i.e θ5 is removed and 1 is subtracted from one of θ1 , θ2 , θ3 or θ4 and hence the claim that γ ∈ Sθ ′ /(1) ). Since ′ θ is a partition of 2n − 1, it has either exactly three parts even, or exactly 3 parts odd. In any case, there is exactly one partition in Sθ ′ /(1) which belongs to P. This 46 implies the fact that, if l(θ ) = 5 then s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = 1 θ5 = 1 (2.21) 0 otherwise. Collecting the results of computing individual terms on the right hand side of (2.16) in the case l(θ ) = 5 gives us s(n−1,n−1,2) ∗ s(n,n) , sθ = 1 θ5 = 2, θ ∈ Q O′ − ((θ4 = 1)) Eθ = 1, θ5 = 1 θ ′ Eθ 0 Oθ = 1, θ5 = 1 otherwise. ′ ′ ′ ′ Note that that we have used the fact that, by definition Oθ ′ = Oθ and Eθ ′ = Eθ . 2.3.3 Case III: l(θ ) ≤ 4 We know that, if l(θ ) ≤ 4, then s(n+1,n−1) ∗ s(n,n) , sθ = ((θ ∈ Q)) , and s(n,n−1,1) ∗ s(n,n) , sθ = dθ − 1. To help complete this case, we will compute s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ . Let θ ∈ P. The partition obtained by subtracting 2 from any part of θ is still in P, and there are no terms of the form sγ with γ ∈ P in s(n,n−2) ∗ s(n−1,n−1) . Thus the 47 only contribution is from terms of the form sγ where γ is obtained by subtracting 1 from two distinct parts of θ , as such a partition clearly belongs to Q. All such terms appear in s⊥ (2) sθ with coefficient 1. If θ ∈ Q, then all partitions obtained by subtracting 2 from a part of θ are still in Q. To obtain other partitions γ such that γ is in Q and sγ appears in s⊥ (2) sθ , we subtract 1 from one of the odd parts and a 1 from one of the even parts. This leads us to s(n,n−2) ∗ s(n−1,n−1) , s⊥ (2) sθ = dθ 2 d + O′ E ′ θ ,2 θ θ θ ∈P (2.22) θ ∈ Q. Let us consider s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ now. Assume θ ∈ P. Then s⊥ (1,1) sθ is a sum of terms of the form sγ , where γ ∈ Q as the parity of exactly two of the parts of θ is flipped, allowing us to conclude that, in this case s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = 0. Now θ ∈ Q is the remaining case. There are exactly 2 odd parts in θ . Subtracting 1 from each of these parts will give us a partition of 2n − 2, which lies in P. If there are 2 even non-zero parts in θ , then subtracting 1 from each of these will also give us a partition of 2n − 2 lying in P. Both these partitions appear with a coefficient 1 in s⊥ (1,1) sθ . Thus, if l(θ ) ≤ 4, s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = 0 θ ∈P 1 + ((Eθ = 2)) θ ∈ Q. On collecting the results obtained in the case l(θ ) ≤ 4, we obtain s(n−1,n−1,2) ∗ s(n,n) , sθ d 1 − dθ + θ θ ∈P 2 = 1 − d + d + O′ E ′ + ((E = 2)) θ ∈ Q. θ θ ,2 θ θ θ 48 (2.23) 2.3.4 Summary Just for the sake of convenience, we will collect the results of the three cases together. This gives us the following characterization s(n−1,n−1,2) ∗ s(n,n) , sθ = ((θ ∈ P)) ((θ ∈ Q)) ′ Oθ − ((θ4 = 1)) l(θ ) = 6 and θ5 = θ6 = 1 l(θ ) = 5, θ5 = 2 l(θ ) = 5 and Eθ = 1, θ5 = 1 ′ l(θ ) = 5 and Eθ Oθ = 1, θ5 = 1 1 − dθ + dθ 2 l(θ ) ≤ 4, θ ∈ P ′ ′ 1 − dθ + dθ ,2 + Oθ Eθ + ((Eθ = 2)) l(θ ) ≤ 4, θ ∈ Q 0 otherwise. We will now consider an example. Example 2.3.1. Consider the product s(7,7,2) ∗ s(8,8) , and three partitions α = (5, 5, 3, 1, 1, 1), β = (6, 4, 3, 2, 1) and γ = (7, 5, 2, 2). ′ Note that l(α ) = 6 and α5 = α6 = 1 as well. Since α = (5, 5, 3, 1) belongs to P, we obtain s(7,7,2) ∗ s(8,8) , s(5,5,3,1,1,1) = 1. ′ Consider the case of β now. We have l(β ) = 5 and β5 = 1. Since β has exactly 1 odd part, we have Oβ = 1. Thus, the above characterization allows one to obtain ′ ′ s(7,7,2) ∗s(8,8) , s(6,4,3,2,1) = E(6,4,3,2,1) . Since β has exactly 3 distinct even non-zero parts, we have s(7,7,2) ∗ s(8,8) , s(6,4,3,2,1) = 3. Turning our attention to γ , we see that l(γ ) = 4 and γ ∈ Q. We have dγ = 49 ′ ′ 3, dγ ,2 = 3, Oγ = 2, Eγ = 1 and Eγ = 2. Thus, we get the fact that s(7,7,2) ∗ s(8,8) , s(7,5,2,2) = 4. 2.4 s(n−1,n−1,1,1) ∗ s(n,n) (n ≥ 2) In essence, this is pretty similar to the previous case. On applying Pieri’s rule, we obtain s(n−1,n−1,1,1) = s(1,1) s(n−1,n−1) − s(n,n) − s(n,n−1,1) . (2.24) Using Theorem 1.6.7, we deduce that (s(1,1) s(n−1,n−1) ) ∗ s(n,n) = ∑ ∑ (n,n) δ ⊢2 η ⊢2n−2 ∑ = (n,n) η ⊢2n−2 + cη ,δ (sη ∗ s(n−1,n−1) )(sδ ∗ s(1,1) ) cη ,(1,1) (sη ∗ s(n−1,n−1) )(s(1,1) ∗ s(1,1) ) ∑ (n,n) η ⊢2n−2 cη ,(2) (sη ∗ s(n−1,n−1) )(s(2) ∗ s(1,1) ). (2.25) (n,n) We’ve already worked out which η satifies cη ,δ = 0 for δ ⊢ 2 in the previous section. Since s(1,1) ∗ s(1,1) = s(2) , we obtain (s(1,1) s(n−1,n−1) ) ∗ s(n,n) = s(2) (s(n−1,n−1) ∗ s(n−1,n−1) ) + s(1,1) (s(n,n−2) ∗ s(n−1,n−1) ). Given θ ⊢ 2n, this means 50 (2.26) s(n−1,n−1,1,1) ∗ s(n,n) , sθ = (s(1,1) s(n−1,n−1) ) ∗ s(n,n) , sθ − s(n,n−1,1) ∗ s(n,n) , sθ − s(n,n) ∗ s(n,n) , sθ = s(2) (s(n−1,n−1) ∗ s(n−1,n−1) ), sθ + s(1,1) (s(n,n−2) ∗ s(n−1,n−1) ), sθ − s(n,n−1,1) ∗ s(n,n) , sθ − s(n,n) ∗ s(n,n) , sθ (2.27) Finally, we obtain s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ s(n−1,n−1,1,1) ∗ s(n,n) , sθ = + s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ − s(n,n−1,1) ∗ s(n,n) , sθ − s(n,n) ∗ s(n,n) , sθ . (2.28) As we did in the previous case, we proceed to evaluate individual terms on the right hand side of (2.28). We only need to work on s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ and s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ . 51 2.4.1 Case I: l(θ ) = 6 From existing characterizations, we know that both s(n,n) ∗s(n,n) , sθ and s(n,n−1,1) ∗ s(n,n) , sθ are 0 in the present case. Let us look at s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ . This is clearly 0 if l(θ ) ≥ 6 because in these cases, s⊥ (2) sθ is a sum of terms of the form sγ with l(γ ) ≥ 5. Now consider s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ . If l(θ ) = 6, the only possibility for a non-zero coefficient is when θ5 = θ6 = 1. By (1.20), this readily gives s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = 1 θ5 = θ6 = 1, θ ′ ∈ Q (2.29) 0 otherwise. Thus, in the current case, using (2.28) we obtain s(n−1,n−1,1,1) ∗ s(n,n) , sθ 1 θ5 = θ6 = 1, θ ∈ Q = 0 otherwise. 2.4.2 Case II: l(θ ) = 5 Firstly, recall that, in this particular case we have s(n,n) ∗ s(n,n) , sθ = 0 and s(n,n−1,1) ∗ s(n,n) , sθ = 1 θ5 = 1 (2.30) 0 otherwise. Consider s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ now. If l(θ ) = 5 and θ5 ≥ 3, this is 0 because s⊥ (2) sθ is a sum of terms of the form sγ with l(γ ) = 5. If θ5 = 2, then the only term in s⊥ (2) sθ which is of the form sγ with l(γ ) ≤ 4 is 52 sθ ′ , and this occurs with coefficient 1 in it. Thus, if θ5 = 2, one obtains s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ = 1 θ′ ∈ P (2.31) 0 otherwise. If θ5 = 1, the only terms in s⊥ (2) sθ with length ≤ 4 occur by removing θ5 and ′ subtracting 1 from one of the other parts provided that it is not equal to θ5 . θ has either exactly 3 odd parts or exactly 3 even parts. The expansion of s(n−1,n−1) ∗ s(n−1,n−1) has terms of the form sγ where γ ∈ P. Thus, after removing θ5 , the other 1 should be removed from the single even part if there are 3 odd parts, or from the odd part if there are exactly 3 even parts. Thus s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ = 1 Eθ = 1 1 − ((θ4 = 1)) Oθ = 1. (2.32) The above facts put together, imply s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ = 1 1 ′ θ5 = 2, θ ∈ P θ5 = 1, Eθ = 1 1 − ((θ4 = 1)) θ5 = 1, Oθ = 1 0 otherwise. (2.33) Now we analyse s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ . One sees that if θ5 ≥ 2, the coefficient of s⊥ (1,1) sθ in s(n,n−2) ∗ s(n−1,n−1) is 0. If θ5 = 1, then the only way to get a term of the form sγ with l(γ ) ≤ 4 in s⊥ (1,1) sθ is to remove θ5 and subtract 1 from one of the other parts in θ . We need γ to belong to Q if it is to have a non-zero coefficient. The way to achieve this is to subtract 1 from one of the odd parts if 53 ′ there are exactly 3 odd parts in θ , or subtract 1 from one of the even parts if there are exactly 3 even parts. All things considered, we find that, if l(θ ) = 5, then s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ ′ Eθ ′ ′ = Oθ ′ 0 θ5 = 1, Eθ ′ = 3 θ5 = 1, Oθ ′ = 3 (2.34) otherwise. Using (2.28), if l(θ ) = 5, we obtain the following s(n−1,n−1,1,1) ∗ s(n,n) , sθ 2.4.3 = 1 O′ θ θ5 = 2, θ ∈ P θ5 = 1, Eθ = 1 ′ Eθ − ((θ4 = 1)) θ5 = 1, Oθ = 1 0 otherwise. Case III: l(θ ) ≤ 4 In this case, we have s(n,n) ∗ s(n,n) , sθ = ((θ ∈ P)) , (2.35) s(n,n−1,1) ∗ s(n,n) , sθ = dθ − 1. (2.36) and Consider s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ now. If θ ∈ P, then the only terms in s⊥ (2) sθ which can appear in s(n−1,n−1) ∗s(n−1,n−1) are of the form sγ where γ has been 54 obtained by subtracting 2 from a part of θ . Subtracting 1 from 2 different parts of θ gives a partition which lies in Q. These can’t appear in s(n−1,n−1) s ∗ s(n−1,n−1) . If, on the other hand, θ ∈ Q, then to get a term of the form sγ in s⊥ (2) sθ such that γ lies in P, the only possibility is to either subtract 1 each from two distinct non-zero even parts of θ , or subtract 1 each from two distinct odd parts of θ . These arguments imply s(n−1,n−1) ∗ s(n−1,n−1) , s⊥ (2) sθ = dθ ,2 θ ∈P ((E ′ = 2)) + ((O′ = 2)) θ ∈ Q. θ θ (2.37) Now for s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ . If θ ∈ P, then subtracting 1 each from any two parts in θ will give a partition in Q, if what is obtained after the subtraction is indeed a partition. If θ ∈ Q, then subtracting 1 from one of the even parts and subtracting 1 from one of the odd parts gives a partition in Q. Thus, we conclude that s(n,n−2) ∗ s(n−1,n−1) , s⊥ (1,1) sθ = dθ 2 O′ E ′ θ θ + Rθ θ ∈P (2.38) θ ∈ Q. Now, using (2.28) we collect the different parts together in the case l(θ ) ≤ 4 to obtain 55 s(n−1,n−1,1,1) ∗ s(n,n) , sθ 2.4.4 dθ dθ ,2 − dθ + θ ∈P + Rθ 2 ′ ′ = 1 − dθ + Oθ Eθ ′ ′ +((Eθ = 2)) + ((Oθ = 2)) θ ∈ Q. Summary On gleaning the relevant information from the three cases above, we obtain s(n−1,n−1,1,1) ∗ s(n,n) , sθ ((θ ∈ Q)) 1 ′ Oθ ′ Eθ − ((θ4 = 1)) = dθ ,2 − dθ dθ + Rθ + 2 ′ ′ 1 − dθ + Oθ Eθ ′ ′ +((Eθ = 2)) + ((Oθ = 2)) 0 l(θ ) = 6 and θ5 = θ6 = 1 l(θ ) = 5 and θ5 = 2, θ ∈ P l(θ ) = 5 and Eθ = 1, θ5 = 1 l(θ ) = 5 and Oθ = 1, θ5 = 1 l(θ ) ≤ 4, θ ∈ P l(θ ) ≤ 4, θ ∈ Q otherwise. Let us consider an example now. Example 2.4.1. Consider the Kronecker product s(7,7,1,1) ∗ s(8,8) , and three parti56 tions α = (5, 5, 3, 1, 1, 1), β = (6, 4, 3, 2, 1) and γ = (7, 5, 2, 2). ′ Notice that even though α5 = α6 = 1, the partition α = (5, 5, 3, 1) does not belong to Q. Thus s(7,7,1,1) ∗ s(8,8) , s(5,5,3,1,1,1) = 0. ′ Consider the case of β now. We have l(β ) = 5 and β5 = 1. Since β = (6, 4, 3, 2), we have Oβ = 1. The characterization above gives us s(7,7,1,1) ∗s(8,8) , s(6,4,3,2,1) = ′ ′ E(6,4,3,2,1) − ((β4 = 1)). Since β has exactly 3 distinct even non-zero parts and β4 = 1, we obtain s(7,7,1,1) ∗ s(8,8) , s(6,4,3,2,1) = 3. ′ As far as γ is concerned, we have l(γ ) = 4 and γ ∈ Q. We have dγ = 3, Oγ = 2 ′ and Eγ = 1. Thus s(7,7,1,1) ∗ s(8,8) , s(7,5,2,2) = 1 − 3 + 2 + 1 = 1. 2.5 s(n,n,1) ∗ s(n,n,1) (n ≥ 2) In this section we will answer the question of giving a characterisation of the Kronecker product s(n,n,1) ∗ s(n,n,1) . Before we begin our calculations, we need to introduce certain statistics on partitions, the purpose of which, will become clear soon enough. We need to figure out the relation between the number of distinct parts in a partition θ , and that in the partition θ − obtained by removing an inner corner of θ. 2.5.1 Relating dθ and dθ − Fix an alphabet X = {0, 1, 2}. We will associate a string σ of length l(θ ) + 1 to a partition θ . For 1 ≤ i ≤ l(θ ), define 0 (θi = θi+1 ) σi = 1 (θi − θi+1 = 1) 2 (θi − θi+1 ≥ 2). 57 (2.39) Here we are assuming that when i = l(θ ), then θi+1 = 0. For the sake of convenience, define σ0 = σ1 . Once σ has been found, define the following sets Aθ ,1 = {i : 1 ≤ i ≤ l(θ ), σi = 1 and σi−1 = 0} Aθ ,2 = {i : 1 ≤ i ≤ l(θ ), σi = 2 and σi−1 = 0} Bθ ,1 = {i : 1 ≤ i ≤ l(θ ), σi = 1 and σi−1 = 0} Bθ ,2 = {i : 1 ≤ i ≤ l(θ ), σi = 2 and σi−1 = 0} (2.40) Before we describe the relation between dθ and dθ − , we will consider an example to make the above mentioned notions clear. Example 2.5.1. Consider the partition θ = (8, 7, 5, 4, 3, 3, 2, 2). The Ferrers diagram of θ is • • • • • • , where the bulleted squares represent the inner corner of θ . An inner corner is a square whose removal leaves the Ferrers diagram of a partition. The string σ associated with θ is 112110102. Recall that the indexing of the string starts from zero. Observe that the bulleted squares belong to only those parts θi for which σi = 1 or 2. Note further that, on removing a square from θ2 or θ6 , the 58 resulting partition has the same number of distinct parts as θ itself. On removing a square from θ1 , θ3 or θ4 , the number of distinct parts in the resulting partition is one less that dθ . On the other hand, on removing a square from θ8 gives a partition with number of distinct parts being one more than dθ . Note also that {2, 6} = Aθ ,1 ∪ Bθ ,2 , {1, 3, 4} = Bθ ,1 and {8} = Aθ ,2 . These observations motivate what follows. As observed earlier, to obtain θ − from θ , one can remove a corner only from those parts θi such that σi = 1 or 2. If θ − is obtained by subtracting 1 from θi where i ∈ Aθ ,1 or i ∈ Bθ ,2 , then dθ − = dθ . For i ∈ Aθ ,2 , subtracting 1 from θi results in dθ − being dθ + 1. Finally, for i ∈ Bθ ,1 , subtracting 1 from θi results in dθ − being dθ − 1. We will use aθ ,1 , aθ ,2 , bθ ,1 and bθ ,2 for the cardinalities of the sets Aθ ,1 , Aθ ,2 , Bθ ,1 and Bθ ,2 respectively. 2.5.2 Computation Note that the Pieri rule implies s(1) s(n,n) = s(n,n,1) + s(n+1,n) . (2.41) This means s(n,n,1) ∗ s(n,n,1) = = s(1) s(n,n) − s(n+1,n) ∗ s(n,n,1) s(1) s(n,n) ∗ s(n,n,1) − s(n+1,n) ∗ s(n,n,1) . 59 (2.42) As we have done before, we will use the formula of Littlewood (Theorem 1.6.7) which says s(1) s(n,n) ∗ s(n,n,1) = = ∑∑ δ ⊢1 η ⊢2n ∑ (n,n,1) cη ,δ (n,n,1) η ⊢2n cη ,(1) sη ∗ s(n,n) sη ∗ s(n,n) sδ ∗ s(1) s(1) ∗ s(1) . (2.43) Now we need to figure out which partitions η ⊢ 2n give a non-zero value for (n,n,1) (n,n,1) cη ,(1) . The Pieri rule yields that c(η ,(1) = 0 for all η except η = (n, n) and η = (n,n,1) (n,n,1) (n, n − 1, 1). It also tells us that c(n,n),(1) = c(n,n−1,1),(1) = 1. Using the fact that s(1) ∗ s(1) = s(1) , (2.43) becomes s(1) s(n,n) ∗ s(n,n,1) = s(1) s(n,n) ∗ s(n,n) + s(1) s(n,n) ∗ s(n,n−1,1) , (2.44) and using this in (2.42) gives us s(n,n,1) ∗ s(n,n,1) = s(1) s(n,n) ∗ s(n,n) + s(n,n) ∗ s(n,n−1,1) −s(n+1,n) ∗ s(n,n,1) . (2.45) Since we are looking to compute the coefficient of sθ in s(n,n,1) ∗ s(n,n,1) where θ ⊢ 2n + 1, we must find out what s(n,n,1) ∗ s(n,n,1) , sθ is. To this end, (2.45) gives 60 s(n,n,1) ∗ s(n,n,1) , sθ = s(1) s(n,n) ∗ s(n,n) + s(n,n) ∗ s(n,n−1,1) , sθ − s(n+1,n) ∗ s(n,n,1) , sθ = ⊥ s(n,n) ∗ s(n,n) , s⊥ (1) sθ + s(n,n) ∗ s(n,n−1,1) , s(1) sθ − s(n+1,n) ∗ s(n,n,1) , sθ . (2.46) Notice that we do have characterizations for s(n,n) ∗ s(n,n) , s(n,n) ∗ s(n,n−1,1) , and s(n+1,n) ∗ s(n,n,1) , terms appearing on the right hand side in (2.46) and hence we just have to bring the results together. It is clear via Theorem 1.6.10 that if sθ has a nonzero coefficient in s(n,n,1) ∗ s(n,n,1) , then l(θ ) ≤ 6. We will carry out the computation case by case. 2.5.3 Case I: l(θ ) = 6 Notice that we already obtained a characterization for the Kronecker coefficients appearing in s(n,n,1) ∗ s(n+1,n) in Section 2.2. That tells us s(n+1,n) ∗ s(n,n,1) , sθ = 0. Now, using results in Section 2.1, we know that the Kronecker product s(n,n) ∗ s(n,n−1,1) is a sum of terms of the form sγ and l(γ ) ≤ 5 for each such term. It is also known that if l(γ ) = 5 then sγ appears with coefficient 1 iff γ5 = 1 otherwise the coefficient is 0. This implies that s(n,n) ∗ s(n,n−1,1) , s⊥ (1) sθ = 1 iff θ6 = θ5 = 1, and 0 otherwise. Since s(n,n) ∗ s(n,n) is a sum of terms of the form sγ where l(γ ) ≤ 4, it is clear that s(n,n) ∗ s(n,n) , s⊥ (1) sθ = 0. This gives us the following 61 s(n,n,1) ∗ s(n,n,1) , sθ = 1 (θ6 = θ5 = 1) 0 otherwise. 2.5.4 Case II: l(θ ) = 5 In this case, if we look at s(n+1,n) ∗ s(n,n,1) , sθ , then we know that this is 1 if θ5 = 1 and 0 otherwise, because of the results in Section 2.2. Now we will compute s(n,n−1,1) ∗ s(n,n) , s⊥ (1) sθ . Consider the case where θ5 ≥ 3. Then s⊥ (1) sθ is a sum of terms of the form sγ where γ5 ≥ 2. We know that such terms do not appear in s(n,n) ∗ s(n,n−1,1) . On considering θ5 = 2, we see that s⊥ (1) sθ has terms of the form sγ with γ5 = 2, in which case they do not appear in s(n,n) ∗ s(n,n−1,1) , and a term with γ5 = 1 which will appear in s(n,n) ∗ s(n,n−1,1) with coefficient 1, as we calculated earlier. The one remaining sub-case for this case is θ5 = 1. We know that s⊥ (1) sθ = sθ ′ + ∑ γ ⊢2n,γ5 =1 s⊥ (1) sθ ,sγ =0 and hence 62 sγ , (2.47) s(n,n) ∗ s(n,n−1,1) , s⊥ (1) sθ = s(n,n) ∗ s(n,n−1,1) , sθ ′ + s(n,n) ∗ s(n,n−1,1) , ∑ γ ⊢2n,γ5 =1 s⊥ (1) sθ ,sγ =0 sγ . (2.48) Now we will look at individual terms of the right hand side of (2.48). We know that s(n,n) ∗ s(n,n−1,1) , sθ ′ = dθ ′ − 1. (2.49) Notice that dθ ′ − 1 can be related to the number of distinct parts of θ itself in the following manner dθ ′ − 1 = dθ − 2 (θ4 ≥ 2) dθ − 1 (θ4 = 1). (2.50) Also, observe that every term sγ other than sθ ′ in s⊥ (1) sθ occurs with coefficient 1 and there are dθ − 1 such terms clearly. This gives us s(n,n) ∗ s(n,n−1,1) , ∑ γ ⊢2n,γ5 =1 s⊥ (1) sθ ,sγ =0 63 sγ = dθ − 1. (2.51) Then (2.49), (2.50) and(2.51) together imply s(n,n−1,1) ∗ s(n,n) , s⊥ (1) sθ = 2dθ − 3 (θ5 = 1, θ4 ≥ 2) 2dθ − 2 (θ5 = 1, θ4 = 1). (2.52) Now consider s(n,n) ∗ s(n,n) , s⊥ (1) sθ . Since s(n,n) ∗ s(n,n) only consists of terms sγ where γ ∈ P and l(γ ) ≤ 4, we have that if l(θ ) = 5, then s(n,n) ∗ s(n,n) , s⊥ (1) sθ = 1 (θ5 = 1, θ ∈ P) (2.53) 0 otherwise. Summarising the case l(θ ) = 5 we have s(n,n,1) ∗ s(n,n,1) , sθ = 2dθ − 3 + ((θ ∈ P)) (θ5 = θ4 = 1) 2dθ − 4 + ((θ ∈ P)) (θ4 ≥ 2, θ5 = 1) (θ5 = 2) 1 0 2.5.5 otherwise. Case III: l(θ ) ≤ 4 Firstly, for this case we know from Section 2.2 that s(n+1,n) ∗ s(n,n,1) , sθ = dθ − 1. 64 (2.54) Given a partition γ ⊢ 2n and l(γ ) ≤ 4, from Section 2.1, we also have s(n,n) ∗ s(n,n−1,1) , sγ = dγ − 1. (2.55) ⊥ − Since s⊥ (1) sθ = ∑θ − ≺θ sθ , and we are computing s(n,n) ∗ s(n,n−1,1) , s(1) sθ , cen- tral to our task is the relation between dθ − and dθ when θ − ≺ θ . θ − is obtained by removing a corner from θ , hence we need to figure out when and how does removing a corner change the number of distinct parts of a partition θ . Having accomplished this task in Section 2.5.1, the computation is now routine. We obtain s(n,n) ∗ s(n,n−1,1) , s⊥ (1) sθ = ∑ θ − ≺θ (−1 + dθ − ) = −dθ + ∑ θ − ≺θ dθ − = −dθ + aθ ,2 (dθ + 1) + bθ ,1 (dθ − 1) +aθ ,1 dθ + bθ ,2 dθ . (2.56) Notice that aθ ,1 + aθ ,2 + bθ ,1 + bθ ,2 = dθ . That reduces (2.56) to s(n,n) ∗ s(n,n−1,1) , s⊥ (1) sθ = −dθ + dθ2 − bθ ,1 + aθ ,2 . (2.57) Next we consider the task of computing s(n,n) ∗ s(n,n) , s⊥ (1) sθ . If θ ⊢ 2n + 1 and l(θ ) = 4, then either θ has 3 parts odd and 1 part even, or it has 3 parts even and 1 odd. Since s(n,n) ∗ s(n,n) has terms of the form sγ where γ ∈ P, it is easily seen that if l(θ ) = 4, then s(n,n) ∗ s(n,n) , s⊥ (1) sθ = 1. If l(θ ) = 3, then θ has either 3 65 parts odd, or 2 parts even and 1 odd. In the former case, s⊥ (1) sθ will not have terms of the form sγ with γ ∈ P whereas in the latter, the only term giving a non-zero coefficient is the term sγ with γ obtained by removing a corner from the part with odd length in θ . Arguments on very similar lines yield that for l(θ ) ≤ 2, we have s(n,n) ∗ s(n,n) , s⊥ (1) sθ = 1. To see this, assume l(θ ) = 2. Then θ has one part odd and the other part even. Subtracting one from the odd part gives a partition in P, while subtracting one from the even part gives a partition in Q. If l(θ ) = 1, then the lone part has to be odd, and subtracting one from it gives a partition which is in P. Thus, for l(θ ) ≤ 2, we do get s(n,n) ∗ s(n,n) , s⊥ (1) sθ = 1. Finally we have s(n,n) ∗ s(n,n) , s⊥ (1) sθ 1 (l(θ ) = 4, 2 or 1) = 1 (l(θ ) = 3 and θ has exactly 1 odd part) 0 otherwise. (2.58) Summarising the case l(θ ) ≤ 4, we have s(n,n,1) ∗ s(n,n,1) , sθ = (dθ − 1)2 + 1 − bθ ,1 + aθ ,2 (l(θ ) = 4, 2 or 1) (dθ − 1)2 + 1 − bθ ,1 + aθ ,2 (l(θ ) = 3 and θ (d − 1)2 − b + a θ θ ,1 θ ,2 66 has exactly 1 odd part) otherwise. 2.5.6 Summary After simplifying some of the above relations, we have s(n,n,1) ∗ s(n,n,1) , sθ = 1 l(θ ) = 6, θ6 = θ5 = 1 2dθ − 3 + ((θ ∈ P)) l(θ ) = 5, θ5 = θ4 = 1 2dθ − 4 + ((θ ∈ P)) l(θ ) = 5, θ4 ≥ 2, θ5 = 1 1 l(θ ) = 5, θ5 = 2 (dθ − 1)2 + 1 − bθ ,1 + aθ ,2 l(θ ) = 4 (dθ − 1)2 + 1 − bθ ,1 + aθ ,2 l(θ ) = 3 and θ (dθ − 1)2 − bθ ,1 + aθ ,2 2 − bθ ,1 + aθ ,2 1 0 has exactly 1 odd part l(θ ) = 3 and θ has all parts odd l(θ ) = 2 l(θ ) = 1 otherwise. Let us now consider an example. Example 2.5.2. Consider the computation of s(8,8,1) ∗ s(8,8,1) . Let α = (6, 5, 3, 2, 1), β = (8, 6, 2, 1) and γ = (7, 5, 5) be three partitions. Consider first s(8,8,1) ∗ s(8,8,1) , sα . We can see that l(α ) = dα = 5, α5 = 1 ′ and α4 ≥ 2. Note also that α = (6, 5, 3, 2) does not belong to P. Thus s(8,8,1) ∗ s(8,8,1) , s(6,5,3,2,1) = 2 × 5 − 4 = 6. Next, consider s(8,8,1) ∗ s(8,8,1) , sβ . We have l(β ) = dβ = 4. The string σ associated with (8, 6, 2, 1) is 22211. This immediately yields aβ ,2 = 0 and bβ ,1 = 2. 67 This implies s(8,8,1) ∗ s(8,8,1) , s(8,6,2,1) = (4 − 1)2 + 1 + 0 − 2 = 8. Finally, consider s(8,8,1) ∗ s(8,8,1) , sγ . We can see that l(γ ) = 3, dγ = 2 and the string σ associated with γ = (7, 5, 5) is 2202. Thus, we have aγ ,2 = 1 and bγ ,1 = 0. This gives s(8,8,1) ∗ s(8,8,1) , s(7,5,5) = (2 − 1)2 + 1 − 0 = 2. 2.6 Combinatorial implications We start by recalling relevant notation established prior to this section, and establishing some new notation to be used henceforth. Let • fλ = number of standard Young tableau of shape given by a partition λ . • dλ = number of distinct parts of a partition λ . • τk (n) = the number of standard Young tableau of height ≤ k and size n and if the subscript k is omitted, that means we are just counting all standard Young tableau of size n. • σk (n) = ∑ λ ⊢n l(λ )≤k dλ fλ . • Cn = the n-th Catalan number and equal to 1 2n . n+1 n 1 • Mn = the n-th Motzkin number given by ∑i≥0 i+1 n 2i 2i i . The results obtained above about the Kronecker products s(n,n−1,1) ∗s(n,n) and s(n−1,n−1,1) ∗ s(n,n−1) in Sections 2.5.1 and 2.5.2 imply the following: ∑ (dλ − 1)sλ + λ ⊢2n l(λ )≤4 ∑ λ ⊢2n l(λ )=5 λ5 =1 68 sλ = s(n,n−1,1) ∗ s(n,n) , (2.59) and ∑ (dλ − 1)sλ + λ ⊢2n−1 l(λ )≤4 ∑ λ ⊢2n−1 l(λ )=5 λ5 =1 sλ = s(n−1,n−1,1) ∗ s(n,n−1) . (2.60) Looking at (2.60) and (2.59) in the language of characters of the symmetric group, i.e. looking at the inverse image of the identities above under the Frobenius map, we obtain ∑ ∑ (dλ − 1)χλ + λ ⊢2n l(λ )≤4 λ ⊢2n l(λ )=5 λ5 =1 χλ = χ(n,n−1,1) χ(n,n) , (2.61) and ∑ (dλ − 1)χλ + λ ⊢2n−1 l(λ )≤4 ∑ λ ⊢2n−1 l(λ )=5 λ5 =1 χλ = χ(n−1,n−1,1) χ(n,n−1) . (2.62) If one evaluates (2.61) and (2.62) at the identity element of S2n and S2n−1 respectively, then one obtains the following identity ∑ (dλ − 1) fλ + λ ⊢2n l(λ )≤4 ∑ λ ⊢2n l(λ )=5 λ5 =1 fλ = f(n,n−1,1) f(n,n) , (2.63) and ∑ (dλ − 1) fλ + λ ⊢2n−1 l(λ )≤4 ∑ λ ⊢2n−1 l(λ )=5 λ5 =1 fλ = f(n−1,n−1,1) f(n,n−1) . (2.64) Now, our aim is two-fold. We will find suitable closed form expressions for σ4 (n) and ∑ λ ⊢n l(λ )=5 λ5 =1 fλ . We will start by giving an expression for σk (n). 69 Theorem 2.6.1. Given positive integers m and k, we have σk (m) = τk (m + 1) − τk−1 (m). (2.65) Proof. ∑ τk (m + 1) = λ ⊢m+1 l(λ )≤k fλ . (2.66) Using [22, Lemma 2.8.2], which says fλ = ∑µ ≺λ f µ , we obtain the following sequence of equalities ∑ λ ⊢m+1 l(λ )≤k fλ = ∑ ∑ λ ⊢m+1 µ ≺λ l(λ )≤k = ∑ ∑ fµ µ ⊢m λ ≻µ l(µ )≤k l(λ )≤k = ∑ fµ (dµ + 1) f µ + µ ⊢m l(µ )≤k−1 = ∑ λ ⊢m l(λ )≤k ∑ µ ⊢m l(µ )=k dµ f µ dλ fλ + τk−1 (m) = σk (m) + τk−1 (m). (2.67) Here µ ≺ λ means that the partition λ covers the partition µ in the Young’s lattice. This gives us the following corollary. 70 Corollary 2.6.2. Given a positive integer n, we have σ4 (n) = C⌊ n2 ⌋+1C⌈ 2n ⌉+1 − Mn . (2.68) Proof. Theorem 2.6.1 implies σ4 (n) = τ4 (n + 1) − τ3 (n). (2.69) Theorem 1.2.7 then yields the values for τ4 (n + 1) and τ3 (n), allowing us to prove the corollary. Now we come to our next enumerative result which makes use of (2.63) and (2.64). It relates to a very specific case of counting standard Young tableau with a fixed height. Theorem 2.6.3. Given a positive integer k ≥ 3, we have ∑ λ ⊢k l(λ )=5 λ5 =1 fλ = k+1 ⌊ k+1 2 ⌋(⌈ 2 ⌉ + 1) C⌊ k+1 ⌋C⌈ k+1 ⌉ −C⌊ k ⌋+1C⌈ k ⌉+1 + Mk . 2 2 2 2 k+1 (2.70) Proof. We will treat the cases where k is odd and k is even separately. Firstly assume k = 2n for some integer n ≥ 2. Then (2.63) implies 71 ∑ λ ⊢2n l(λ )=5 λ5 =1 fλ = f(n,n−1,1) f(n,n) − ∑ (dλ − 1) fλ λ ⊢2n l(λ )≤4 f(n,n−1,1) f(n,n) − σ4 (2n) + τ4 (2n). = (2.71) By (1.9), we have f(n,n) = Cn and by Proposition 1.2.8, f(n,n−1,1) = (n + 1)(n − 1) Cn+1 . 2n + 1 (2.72) Using Corollary 2.6.2, we obtain 2 σ4 (2n) = Cn+1 − M2n . (2.73) Theorem 1.2.7 also implies τ4 (2n) = CnCn+1 . (2.74) Therefore ∑ λ ⊢2n l(λ )=5 λ5 =1 fλ = n2 − 1 2 CnCn+1 −Cn+1 + M2n +CnCn+1 2n + 1 = n(n + 2) 2 CnCn+1 −Cn+1 + M2n . 2n + 1 72 (2.75) Now, assume k = 2n − 1 for n ≥ 2. Then (2.64) implies ∑ λ ⊢2n−1 l(λ )=5 λ5 =1 fλ = = f(n−1,n−1,1) f(n,n−1) − ∑ (dλ − 1) fλ λ ⊢2n−1 l(λ )≤4 f(n−1,n−1,1) f(n,n−1) − σ4 (2n − 1) + τ4 (2n − 1). (2.76) Now, by (1.10), we have f(n,n−1) = Cn and by Proposition 1.2.8, we have f(n−1,n−1,1) = n−1 Cn . 2 (2.77) Furthermore, by Corollary 2.6.2, one obtains σ4 (2n − 1) = CnCn+1 − M2n−1 , (2.78) and by Theorem 1.2.7, we get τ4 (2n − 1) = Cn2 . (2.79) Therefore ∑ λ ⊢2n−1 l(λ )=5 λ5 =1 fλ = n−1 Cn2 −CnCn+1 +Cn2 + M2n−1 2 = n+1 Cn2 −CnCn+1 + M2n−1 . 2 73 (2.80) One can check that the claim is just a unified way of rewriting the formulae obtained in the two cases, k = 2n and k = 2n − 1. 74 Chapter 3 Conclusion 3.1 Further directions It is clear from the techniques we have used here that if we know a combinatorial rule for computing the Kronecker product of Schur functions indexed by partitions of height at most k, for some positive integer k, then we can give a description of the Kronecker product of Schur functions indexed by partitions of height k + 1, where the smallest part is 1 or 2. Our concern here was mainly with nearly rectangular partitions. One can go a step further and try to compute s(n+k,n−k−1,1) ∗ s(n,n) for n ≥ k + 2 and k ≥ 1. On performing calculations akin to those described in the previous chapter, one obtains the following relation k s(n+k,n−k−1,1) ∗ s(n,n) , sθ = ∑ (−1)k+ j s(n+ j,n− j) ∗ s(n,n) , s⊥ (1) s(1) sθ j=0 − s(n+k+1,n−k−1) ∗ s(n,n) , sθ − s(n+k,n−k) ∗ s(n,n) , sθ . 75 (3.1) Note that the case where k = 0 has already been dealt with in Section 2.1. Coming back to (3.1), there is a combinatorial rule for computing Kronecker products of the form s(n+ j,n− j) ∗ s(n,n) , as described in [7]. One could use the Pieri rule twice to describe the terms appearing in s⊥ (1) s(1) sθ . Thus, in theory, one could compute s(n+k,n−k−1,1) ∗ s(n,n) , sθ given (3.1). But that is not satisfying since there is an alternating sum in (3.1), and we already know what we are computing is a positive integer. Another area worth looking into is counting standard Young tableaux with added constraints as described below. Given k, i, n ≥ 0, consider the set S(k, i, n) = {λ ⊢ n : λk+1 = i and l(λ ) ≤ k + 1} . Let ρk,i (n) be defined by ∑ ρk,i (n) = λ ∈S(k,i,n) fλ . (3.2) The first thing to note is that ρk,0 (n) = τk (n), and what we have enumerated in Theorem 2.6.3 is ρ4,1 (n). Furthermore, for k ≥ 1, we have n τk (n) = ∑ ρk−1,i (n) . (3.3) i=0 Thus, the numbers ρk,i (n) provide a refinement of the sequence τk (n). To the best of our knowledge, the numbers ρk,i (n) have not been studied, and the question of enumerating them could possibly yield new combinatorial identities. 76 Bibliography [1] C. Ballantine and R. Orellana, On the Kronecker product s(n−p,p) ∗ sλ , Electronic J. Combin. 12 (2005), 1-26. → pages 27 [2] C. Ballantine and R. Orellana, A combinatorial interpretation for the coefficients in the Kronecker product s(n−p,p) ∗ sλ , S´em. Lothar. Combin. 54A (2005/06), Art. B54Af 29pp. → pages 27 [3] F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math. 139 (1995), 463-468. → pages 11 [4] F. Bergeron and F. Gascon, Counting Young tableaux of bounded height, J. Integer Seq. 3 (2000), Article 00.1.7. → pages 11 [5] C. Bessenrodt and C. Behns, On the Durfee size of Kronecker products of characters of the symmetric group and their double covers, J. Algebra 280 (2004), 132-144. → pages 27 [6] C. Bessenrodt and A. Kleshchev, On Kronecker products of complex representations of the symmetric and alternating groups, Pacific J. Math. 190 (1999), 201-223. → pages 77 [7] A. Brown, S. van Willigenburg and M. Zabrocki, Expressions for Catalan Kronecker Products, Pacific J. Math. 248 (2010), 31-48. → pages 27, 28, 29, 30, 31, 76 [8] P. B¨urgisser and C. Ikenmeyer, The complexity of computing Kronecker coefficients, FPSAC 2008 proceedings. → pages 27 [9] M. Clausen and H. Meier, Extreme irreduzible Konstituenten in Tensordarstellungen symmetrischer Gruppen, Bayreuther Math. Schriften 45 (1993), 1-17. → pages 32 [10] Y. Dvir, On the Kronecker product of Sn characters, J. Algebra 154 (1993), 125-140. → pages 32 [11] J.S. Frame, G. de B. Robinson, and R.M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316-324. → pages 10 [12] A. Garsia, N. Wallach, G. Xin and M. Zabrocki, Kronecker Coefficients via symmetric functions and constant term identities, to appear Discrete Math. → pages 28, 29 [13] I. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), 257-285. → pages 11, 12, 13 [14] D. Gouyou-Beauchamps, Standard Young tableaux of height 4 and 5, European J. Combin. 10 (1989), 69-82. → pages 12 [15] C. Greene, A. Nijenhuis and H.S. Wilf, A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. Math. 31 (1979), 104-109. → pages 11 78 [16] D.E. Littlewood, The Kronecker Product of Symmetric Group Representations, J. London Math. Soc. 31 (1) 1956, 89-93. → pages 31 [17] J.-C. Novelli, I. Pak and A. V. Stoyanovskii, A direct bijective proof of the hook-length formula, Discrete Math. Theoret. Computer Science 1 (1997), 53-67. → pages 11 [18] M.H. Peel, Specht modules and symmetric groups,J. Algebra 36 (1975), 8897. → pages 23 [19] A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981), 115-136. → pages 11, 12 [20] J. Remmel and T. Whitehead, On the Kronecker product of Schur functions of two row shapes, Bull. Belg. Math. Soc. 1 (1994), 649-683. → pages 27 [21] M. Rosas, The Kronecker product of Schur functions indexed by two-row shapes or hook shapes, J. Algebraic Combin. 14 (2001), 153-73. → pages 27 [22] B. E. Sagan, The Symmetric Group - Representations, Combinatorial Algorithms, and Symmetric Functions, second Edition, Springer-Verlag, New York, 2001. → pages 23, 24, 70 [23] R.P. Stanley, Enumerative Combinatorics, volume 2, Cambridge University Press, Cambridge, United Kingdom, 1999. → pages 8, 11, 12, 13, 15, 19, 20, 24 [24] E. Vallejo, Stability of Kronecker products of irreducible characters of the symmetric group, Electronic J. Combin. 6 (1999), R39. → pages 27 79 [25] N. Wallach, Hilbert series of measures of entanglement for 4 qubits, Acta Appl. Math. 86 (2005), 203-220. → pages 29 80
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On the computation of Kronecker coefficients
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On the computation of Kronecker coefficients Tewari, Vasu Vineet 2011
pdf
Page Metadata
Item Metadata
Title | On the computation of Kronecker coefficients |
Creator |
Tewari, Vasu Vineet |
Publisher | University of British Columbia |
Date Issued | 2011 |
Description | A major open problem in algebraic combinatorics is to find a combinatorial rule to compute the Kronecker product of two Schur functions. This is the same as decomposing the inner tensor product of two irreducible characters of the symmetric group as a sum of irreducible characters. Given that there is a combinatorial rule, namely the Littlewood-Richardson rule, which describes a way to compute the outer tensor product of two irreducible characters of the symmetric group, one would expect an algorithm which achieves the same purpose in the case of the inner tensor product. Jeffrey Remmel and Tamsen Whitehead first came up with a description of the Kronecker coefficients occurring in the Kronecker product of two Schur functions, both indexed by partitions of length at most 2. Mercedes Rosas later arrived at the same result using a different approach. The solution of the general problem would have implications in Complexity Theory and Quantum Information Theory. Our goal in this thesis is to derive formulae for computing the Kronecker product in certain cases where the Schur functions are indexed by partitions which are nearly rectangular. In particular, we study s{(n,n-1,1)}*s{(n,n)}, s{(n-1,n-1,1)}*s{(n,n-1)}, s{(n-1,n-1,2)}*s{(n,n)}, s{(n-1,n-1,1,1)}*s{(n,n)} and s{(n,n,1)}*s{(n,n,1)}. Our approach relies mainly on the fruitful interplay between manipulation of symmetric functions and the representation theory of the symmetric group. As a consequence of these formulae, we also derive an expression enumerating certain standard Young tableaux of bounded height. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-08-04 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution 3.0 Unported |
DOI | 10.14288/1.0072012 |
URI | http://hdl.handle.net/2429/36483 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2011-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by/3.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2011_fall_tewari_vasu.pdf [ 375.99kB ]
- Metadata
- JSON: 24-1.0072012.json
- JSON-LD: 24-1.0072012-ld.json
- RDF/XML (Pretty): 24-1.0072012-rdf.xml
- RDF/JSON: 24-1.0072012-rdf.json
- Turtle: 24-1.0072012-turtle.txt
- N-Triples: 24-1.0072012-rdf-ntriples.txt
- Original Record: 24-1.0072012-source.json
- Full Text
- 24-1.0072012-fulltext.txt
- Citation
- 24-1.0072012.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0072012/manifest