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 symmet- ric 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 prod- uct 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 for- mulae, 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 Symmetric functions . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Monomial symmetric functions . . . . . . . . . . . . . . 3 1.1.2 Other symmetric function bases . . . . . . . . . . . . . . 4 1.2 Semi-standard Young tableaux . . . . . . . . . . . . . . . . . . . 8 1.2.1 The hook length formula . . . . . . . . . . . . . . . . . . 10 1.3 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 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) (n ≥ 2) . . . . . . . . . . . . . . . . . . 39 2.3 s(n−1,n−1,2) ∗ s(n,n) (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 2.4 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 2.5 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 2.6 Combinatorial implications . . . . . . . . . . . . . . . . . . . . . 68 3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 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 enthusi- asm 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 mathemati- cal knowledge, especially Professor Hemalatha Thiagarajan and Professor Udayan Prajapati during my undergraduate years, and Professor Andrew Rechnitzer, Pro- fessor 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, representa- tion theory and algebraic geometry. The Schur functions are a basis of the ring of symmetric functions with a variety of applications. They mirror the underly- ing algebra and combinatorics in a clear fashion. An outstanding open problem in algebraic combinatorics is to arrive at a combinatorial rule to compute the Kro- necker 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 (xpi(1),xpi(2), . . .) = f (x1,x2, . . .) for every permutation pi 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λ = xλ1i1 x λ2 i2 · · ·x λl il , (1.2) where the i j for j = 1, . . . , l are distinct positive integers. The degree of the mono- mial 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 ho- mogeneous 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≥0 Λn , (1.3) and Λ is considered as a graded algebra. A common theme in the theory of symmet- ric 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) = ∑xλ1i1 xλ2i2 · · ·xλlil , (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) = ∑ i≥1 xi, m(2) = ∑ i≥1 x2i , m(1,1) = ∑ 1≤i< j xix j. Each symmetric function can be written as a sum of monomial symmetric func- tions 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 dimen- sion 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) = ∑ i1 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 1 3 3 2 2 3 2 3 3 , 17 and therefore s(2,1)(x1,x2,x3) = x 2 1x2 + x 2 1x3 + x1x 2 2 +2x1x2x3 + x1x23 + x22x3 + x2x23 . The coefficient of a monomial xα11 x α2 2 · · ·x αn 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 x1x2 · · ·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 〈,〉Λn . This is called the Hall inner product and is defined by setting 〈sλ ,sµ〉Λn = δλ µ 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 = δλ µzλ , 〈hλ ,mµ〉Λ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 prod- uct 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 • 2 2 , • • 1 1 • 2 2 , • • 1 • 1 2 2 , • • 1 • 1 2 2 , • • 1 • 2 1 2 , • • • 1 1 2 2 . Thus, for example, we have c(3,2,2)(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 de- scribes 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 = ∑ ν`|µ|+n ν/µ=horizontal strip of size n sν , and sµs(1n) = sµen = ∑ ν`|µ|+n ν/µ=vertical strip of size n sν . 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 subrep- resentations 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 con- jugacy 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 irre- ducible 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 iso- morphism) by its character. Let CFn denote the space of class functions from Sn to Q (we are using Q since the characters of Sn can be realized over Q). CFn has a natural inner product 〈,〉CFn defined by 〈 f ,g〉CFn = 1 n! ∑pi∈Sn f (pi)g(pi). 23 Our main tool that reduces character computations to symmetric functions manip- ulation is a linear transformation ch : CFn → Λn called the characteristic map or the Frobenius map. If f ∈CFn, then define ch( f ) = 1 n! ∑pi∈Sn f (pi)ppi , = ∑ µ`n 1 zµ f (µ)pµ , wherein we have used the fact that f is a class function which basically means that f (pi) is decided completely by pi’s cycle type. The ppi above also refers to the power sum symmetric function indexed by the partition that is the cycle type of pi . 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〉CFn = 〈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 representa- tion 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λµν = 〈χλ ,χµ χν〉CFn = 1 n! ∑pi∈Sn χλ (pi)χµ(pi)χν(pi) = ∑ γ`n 1 zγ χλ (γ)χµ(γ)χν(γ) . (1.15) 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 char- acter 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 CFn such that ch(u) = f , ch(v) = g and uv(pi) = u(pi)v(pi). 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λ 〉Λn = 〈∑ γ`n 1 zγ χµ χν(γ)pγ ,sλ 〉Λn = 〈∑ γ`n 1 zγ χµ(γ)χν(γ)pγ ,sλ 〉Λn = ∑ γ`n 1 zγ χλ (γ)χµ(γ)χν(γ) = gλµν . (1.16) One can also prove easily that pλ zλ ∗ pµ zµ = δλ µ pλ 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 g(n)µν = g (1n) µν 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 P = ⋃ n≥0 Pn , Q = ⋃ n≥0 Qn , 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 0 otherwise. (1.17) 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) = ∑ λ∈P λ`2n sλ . (1.18) These results were different from earlier characterisations as they explicitly state which partitions have non-zero coefficients and further establish that the co- efficients 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 〈s(n,n) ∗ s(n+k,n−k),sλ 〉= k ∑ i=0 ((λ ∈ (k+ i,k, i)P)) + k ∑ i=1 ((λ ∈ (k+ i+1,k+1, i)P)) . (1.19) 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 〈s(4,4) ∗ s(6,2),sλ 〉= 2 ∑ i=0 ((λ ∈ (2+ i,2, i)P)) + 2 ∑ i=1 ((λ ∈ (3+ i,3, i)P)) . 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) = ∑ λ∈Q λ`2n sλ . (1.20) 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λµν 6= 0 for some λ = (λ1,λ2, . . .)}= |µ ∩ν |, max {m : gλµν 6= 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 occur- ring 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 Sec- tion 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 coeffi- cients 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λ/µ〉 6= 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 6= 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 be- longs 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 c (n,n) η ,δ (sη ∗ s(n,n−1))(sδ ∗ s(1)) = ∑ η`2n−1 c (n,n) η ,(1)(sη ∗ s(n,n−1))(s(1) ∗ s(1)). (2.3) The Pieri rule yields that c(n,n)η ,(1) 6= 0 if and only if η = (n,n−1), in which case c (n,n) (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)). (2.4) 36 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 sλ ,sθ 〉 is 1 if l(θ) ≤ 4 and 0 otherwise. So we will focus on evaluating 〈 ∑ λ`2n−1 l(λ )≤4 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 num- ber 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θ 〉 6= 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 computa- 37 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λ ,sθ/(1)〉= 1. Thus, if l(θ) = 5, 〈s(n,n−1,1) ∗ s(n,n),sθ 〉= 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λ , ∑ θ−≺θ sθ−〉 = dθ . (2.7) Therefore 〈s(n,n−1) ∗ s(n,n−1),s ⊥ (1)sθ 〉= dθ . (2.8) 38 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 descrip- tion 〈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 c (n,n−1) η ,δ (sη ∗ s(n−1,n−1))(sδ ∗ s(1)) = ∑ η`2n−2 c (n,n−1) η ,(1) (sη ∗ s(n−1,n−1))(s(1) ∗ s(1)). (2.10) The Pieri rule dictates that the only cases where c(n,n−1)η ,(1) 6= 0 are when η = (n,n−2) or η = (n−1,n−1) and in both cases c(n,n−1)η ,(1) = 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)). (2.11) If θ ` 2n−1, (2.9) and (2.11) together bring us to 40 〈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) = ∑ δ`2 ∑ η`2n−2 c (n,n) η ,δ (sη ∗ s(n−1,n−1))(sδ ∗ s(2)) = ∑ η`2n−2 c (n,n) η ,(1,1)(sη ∗ s(n−1,n−1))(s(1,1) ∗ s(2)) + ∑ η`2n−2 c (n,n) η ,(2)(sη ∗ s(n−1,n−1))(s(2) ∗ s(2)). (2.14) Notice that for c(n,n)η ,(2) 6= 0 to hold, we must have η =(n,n−2) whereas c (n,n) η ,(1,1) 6= 0 implies that η = (n− 1,n− 1). In both cases, c(n,n)η ,δ = 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)). (2.15) Now, let θ ` 2n. From the equality above, it follows that 42 〈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θ 〉 6= 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γ〉 6= 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. (2.18) 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.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 〈s(n,n−2) ∗ s(n−1,n−1),s ⊥ (2)sθ 〉= ((Eθ ′ = 1))[O ′ θ ′ − ((θ ′ 4 = 1))] +((Oθ ′ = 1))[E ′ θ ′ ]. (2.19) Put succinctly, one has 〈s(n,n−2) ∗ s(n−1,n−1),s ⊥ (2)sθ 〉= 0 θ5 ≥ 3 1 θ5 = 2, θ ′ ∈ Q O′θ ′ − ((θ4 = 1)) θ5 = 1, Eθ ′ = 1 E ′θ ′ θ5 = 1, Oθ ′ = 1 0 otherwise. (2.20) 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 0 otherwise. (2.21) 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 ′θ Oθ = 1, θ5 = 1 0 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 ) θ ∈ P dθ ,2 +O ′ θ E ′ θ θ ∈ Q. (2.22) 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. (2.23) On collecting the results obtained in the case l(θ)≤ 4, we obtain 〈s(n−1,n−1,2) ∗ s(n,n),sθ 〉= 1−dθ + ( dθ 2 ) θ ∈ P 1−dθ +dθ ,2 +O ′ θ E ′ θ +((Eθ = 2)) θ ∈ Q. 48 2.3.4 Summary Just for the sake of convenience, we will collect the results of the three cases to- gether. This gives us the following characterization 〈s(n−1,n−1,2) ∗ s(n,n),sθ 〉= ((θ ∈ P)) l(θ) = 6 and θ5 = θ6 = 1 ((θ ∈ Q)) l(θ) = 5, θ5 = 2 O′θ − ((θ4 = 1)) l(θ) = 5 and Eθ = 1, θ5 = 1 E ′θ l(θ) = 5 and 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) = ∑ δ`2 ∑ η`2n−2 c (n,n) η ,δ (sη ∗ s(n−1,n−1))(sδ ∗ s(1,1)) = ∑ η`2n−2 c (n,n) η ,(1,1)(sη ∗ s(n−1,n−1))(s(1,1) ∗ s(1,1)) + ∑ η`2n−2 c (n,n) η ,(2)(sη ∗ s(n−1,n−1))(s(2) ∗ s(1,1)). (2.25) We’ve already worked out which η satifies c(n,n)η ,δ 6= 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)). (2.26) Given θ ` 2n, this means 50 〈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,1,1) ∗ s(n,n),sθ 〉= 〈s(n−1,n−1) ∗ s(n−1,n−1),s ⊥ (2)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 be- cause 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 0 otherwise. (2.29) 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 0 otherwise. (2.30) 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 0 otherwise. (2.31) 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 θ5 = 2, θ ′ ∈ P 1 θ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 ′θ ′ θ5 = 1, Eθ ′ = 3 O′θ ′ θ5 = 1, Oθ ′ = 3 0 otherwise. (2.34) Using (2.28), if l(θ) = 5, we obtain the following 〈s(n−1,n−1,1,1) ∗ s(n,n),sθ 〉 = 1 θ5 = 2, θ ∈ P O′θ θ5 = 1, Eθ = 1 E ′θ − ((θ4 = 1)) θ5 = 1, Oθ = 1 0 otherwise. 2.4.3 Case III: l(θ)≤ 4 In this case, we have 〈s(n,n) ∗ s(n,n),sθ 〉= ((θ ∈ P)) , (2.35) and 〈s(n,n−1,1) ∗ s(n,n),sθ 〉= dθ −1. (2.36) 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 ) +Rθ θ ∈ P O′θ E ′ θ θ ∈ Q. (2.38) 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θ 〉 = dθ ,2−dθ + ( dθ 2 ) +Rθ θ ∈ P 1−dθ +O ′ θ E ′ θ +((E ′θ = 2))+((O ′ θ = 2)) θ ∈ Q. 2.4.4 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)) l(θ) = 6 and θ5 = θ6 = 1 1 l(θ) = 5 and θ5 = 2, θ ∈ P O′θ l(θ) = 5 and Eθ = 1, θ5 = 1 E ′θ − ((θ4 = 1)) l(θ) = 5 and Oθ = 1, θ5 = 1 dθ ,2−dθ + ( dθ 2 ) +Rθ l(θ)≤ 4, θ ∈ P 1−dθ +O ′ θ E ′ θ +((E ′θ = 2))+((O ′ θ = 2)) l(θ)≤ 4, θ ∈ Q 0 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 parti- 56 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 6= 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 Kro- necker product s(n,n,1) ∗ s(n,n,1). Before we begin our calculations, we need to intro- duce 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 σi = 0 (θi = θi+1) 1 (θi−θi+1 = 1) 2 (θi−θi+1 ≥ 2). (2.39) 57 Here we are assuming that when i = l(θ), then θi+1 = 0. For the sake of conve- nience, 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 6= 0} Bθ ,2 = {i : 1 ≤ i ≤ l(θ), σi = 2 and σi−1 6= 0} (2.40) Before we describe the relation between dθ and dθ− , we will consider an ex- ample to make the above mentioned notions clear. Example 2.5.1. Consider the partition θ = (8,7,5,4,3,3,2,2). The Ferrers dia- gram 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). (2.42) 59 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 c (n,n,1) η ,δ ( sη ∗ s(n,n) )( sδ ∗ s(1) ) = ∑ η`2n c (n,n,1) η ,(1) ( sη ∗ s(n,n) )( s(1) ∗ s(1) ) . (2.43) Now we need to figure out which partitions η ` 2n give a non-zero value for c (n,n,1) η ,(1) . The Pieri rule yields that c (n,n,1) (η ,(1) = 0 for all η except η = (n,n) and η = (n,n− 1,1). It also tells us that c(n,n,1)(n,n),(1) = c (n,n,1) (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 non- zero 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γ 〉6=0 sγ , (2.47) and hence 62 〈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γ 〉6=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γ 〉6=0 sγ〉= dθ −1. (2.51) 63 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) 0 otherwise. (2.53) 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) 1 (θ5 = 2) 0 otherwise. 2.5.5 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. (2.54) 64 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θ ,1dθ +bθ ,2dθ . (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 θ has exactly 1 odd part) (dθ −1)2−bθ ,1 +aθ ,2 otherwise. 66 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 θ has exactly 1 odd part (dθ −1)2−bθ ,1 +aθ ,2 l(θ) = 3 and θ has all parts odd 2−bθ ,1 +aθ ,2 l(θ) = 2 1 l(θ) = 1 0 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 estab- lishing 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 n+1 ( 2n n ) . • Mn = the n-th Motzkin number given by ∑i≥0 1i+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: ∑ λ`2n l(λ )≤4 (dλ −1)sλ + ∑ λ`2n l(λ )=5 λ5=1 sλ = s(n,n−1,1) ∗ s(n,n), (2.59) 68 and ∑ λ`2n−1 l(λ )≤4 (dλ −1)sλ + ∑ λ`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 ∑ λ`2n l(λ )≤4 (dλ −1)χλ + ∑ λ`2n l(λ )=5 λ5=1 χλ = χ(n,n−1,1)χ(n,n), (2.61) and ∑ λ`2n−1 l(λ )≤4 (dλ −1)χλ + ∑ λ`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 re- spectively, then one obtains the following identity ∑ λ`2n l(λ )≤4 (dλ −1) fλ + ∑ λ`2n l(λ )=5 λ5=1 fλ = f(n,n−1,1) f(n,n), (2.63) and ∑ λ`2n−1 l(λ )≤4 (dλ −1) fλ + ∑ λ`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 se- quence of equalities ∑ λ`m+1 l(λ )≤k fλ = ∑ λ`m+1 l(λ )≤k ∑ µ≺λ fµ = ∑ µ`m l(µ)≤k ∑ λµ l(λ )≤k fµ = ∑ µ`m l(µ)≤k−1 (dµ +1) fµ + ∑ µ`m l(µ)=k dµ fµ = ∑ λ`m l(λ )≤k 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) =Cb n2 c+1Cd n2 e+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λ = b k+12 c(d k+1 2 e+1) k+1 Cb k+12 cCd k+12 e−Cb k2 c+1Cd k2 e+1 +Mk. (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)− ∑ λ`2n l(λ )≤4 (dλ −1) fλ = 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) 2n+1 ) Cn+1. (2.72) Using Corollary 2.6.2, we obtain σ4(2n) = C2n+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 2n+1 ) CnCn+1−C2n+1 +M2n +CnCn+1 = ( n(n+2) 2n+1 ) CnCn+1−C2n+1 +M2n. (2.75) 72 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)− ∑ λ`2n−1 l(λ )≤4 (dλ −1) fλ = 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 2 ) Cn. (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) = C2n . (2.79) Therefore ∑ λ`2n−1 l(λ )=5 λ5=1 fλ = ( n−1 2 ) C2n −CnCn+1 +C2n +M2n−1 = ( n+1 2 ) C2n −CnCn+1 +M2n−1. (2.80) 73 One can check that the claim is just a unified way of rewriting the formulae ob- tained 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 〈s(n+k,n−k−1,1) ∗ s(n,n),sθ 〉 = k ∑ j=0 (−1)k+ j〈s(n+ j,n− j) ∗ s(n,n),s⊥(1)s(1)sθ 〉 −〈s(n+k+1,n−k−1) ∗ s(n,n),sθ 〉 −〈s(n+k,n−k) ∗ s(n,n),sθ 〉. (3.1) 75 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 τk(n) = n ∑ i=0 ρk−1,i(n) . (3.3) 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 enu- merating them could possibly yield new combinatorial identities. 76 Bibliography [1] C. Ballantine and R. Orellana, On the Kronecker product s(n−p,p) ∗ sλ , Elec- tronic J. Combin. 12 (2005), 1-26. → pages 27 [2] C. Ballantine and R. Orellana, A combinatorial interpretation for the coef- ficients in the Kronecker product s(n−p,p) ∗ sλ , Sém. 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 rep- resentations 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ürgisser and C. Ikenmeyer, The complexity of computing Kronecker coef- ficients, FPSAC 2008 proceedings. → pages 27 [9] M. Clausen and H. Meier, Extreme irreduzible Konstituenten in Ten- sordarstellungen 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, Euro- pean 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 Representa- tions, 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), 88- 97. → pages 23 [19] A. Regev, Asymptotic values for degrees associated with strips of Young dia- grams, 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 Al- gorithms, 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