The computation of Kostka numbers and Littlewood-Richardson coefficients is #P-complete 5 0 0 2 Hariharan Narayanan n University of chicago a J email:[email protected] 2 1 February 1, 2008 ] O C . h Abstract t a m KostkanumbersandLittlewood-Richardson coefficients playanessential roleinthe [ representation theory of the symmetric groups and the special linear groups. There has been a significant amount of interest in their computation ([1], [10], [11], [2], [3]). 1 v The issue of their computational complexity has been a question of folklore, but was 6 asked explicitly byE.Rassart[10]. We provethatthecomputation ofeither quantity is 7 #P-complete. The reduction to computing Kostka numbers, is from the #P-complete 1 1 problem [4] of counting the number of 2×k contingency tables having given row and 0 column sums. The main ingredient in this reduction is a correspondence discovered by 5 D. E. Knuth [6]. The reduction to the problem of computing Littlewood-Richardson 0 / coefficients is from that of computing Kostka numbers. h t a m 1 Introduction : v i X r Let N = {1,2,...} be the set of positive integers and Z = N∪{0}. Let λ = (λ ,...,λ ) ∈ a ≥0 1 s Ns, λ ≥ λ ≥ ··· ≥ λ ≥ 1, µ = (µ ,...,µ ) ∈ Zt , ν = (ν ,...,ν ) ∈ Zu and 1 2 s 1 t ≥0 1 u ≥0 α = (α ,...,α ) ∈ Nv, α ≥ ··· ≥ α ≥ 1. The Kostka number K and the Littlewood- 1 v 1 v λµ Richardson coefficient cν playanessential roleintherepresentation theoryof thesymmetric λα groups and the special linear groups. Their combinatorial definitions can be found in Sec- tion2. The issue oftheir computational complexity hasbeen aquestion offolklore. Recently, in [10], E. Rassart asked whether there exist fast (polynomial time) algorithms to compute Kostka numbers and Littlewood Richardson coefficients (Question 1, page 99). We prove that these two quantities are #P-complete (see Theorems 1, 2), and thus answer his question in the negative under the hypothesis that a #P-complete quantity cannot be computed in polynomial time. 1 In [1], Barvinok and Fomin show how the set of all non-zero K for a given µ can be λµ produced in time that is polynomial in the total size of the input and output. They also give a probabilistic algorithm running in time, polynomial in the total size of input and output, thatcomputestheset ofallnon-zeroLittlewood-Richardsoncoefficients cν givenλandµ. In λµ [3], methods for the explicit computation of the Kostka numbers and Littlewood-Richardson coefficients using vector partition functions are discussed. Combinatorially, the Kostka number K is the number of Young tableaux that have shape λµ λ and content µ ([5], page 25). The Littlewood-Richardson coefficient cν is the number of λα LR skew tableaux on the shape λ∗α with content ν (this follows from Corollary 2, (v), page 62 and Lemma 1, page 65 of [5]). Representation theoretically, K is the multiplicity of λµ the weight µ in the representation V of the lie algebra sl (C) of the special linear group λ r+1 having highest weight λ and cνλα is the multiplicity of Vν in the tensor product Vλ ⊗C Vα. They also appear in the representation theory of the symmetric groups (see chapter 7, [5]). While there are formulae for K and cν due to Kostant and Steinberg respectively ([3], λµ λα [2]), the number of terms is, in general, exponential in the bit-length of the input. These numbers have interesting properties such as, for fixed λ, µ, α, ν, K and cNν ([11]) are NλNµ NλNα polynomials inN. Whether K > 0canbeanswered inpolynomialtime (seeproposition2), λµ and so can the question of whether cν > 0, though the latter is a highly non-trivial fact λα estabilished by Ketan Mulmuley and Milind Sohoni [8], and uses the proof of the Saturation Conjecture by Knutson and Tao [7]. This fact plays an important role in the approach to the P vs NP question [9] due to Ketan Mulmuley and Milind Sohoni. Let a = (a ,a ) ∈ Z ,a ≥ a and b = (b ,...b ) ∈ Zk . We reduce the #P-complete 1 2 ≥0 1 2 1 k ≥0 problem ([4]) of finding the number |I(a,b)| of 2×k contingency tables that have row sums a := (a ,a ) and column sums b := (b ,...,b ), to that of finding some K . We reduce 1 2 1 k λµ this in turn to finding some cν , where λ,µ,α and ν can be computed in time polynomial λα in the size of (a,b). The main tool used in the reduction to finding Kostka numbers is a correspondence found by Donald E. Knuth ([6]) between the set I(a,b) of contingency tables and pairs of tableaux having contents a and b respectively. 2 Preliminaries and Notation A Young diagram ([5], page 1) is a collection of boxes, arranged in left justified rows, such that from top to bottom, the number of boxes in a row is monotonically (weakly) decreasing. The first two shapes in Figure1 are Young diagrams. Afilling is a numbering of the boxes of a Young diagram with positive integers, that are not necessarily distinct. A Young tableau or simply tableau is a filling such that the entries are 1. weakly increasing from left to right across each row, and 2. strictly increasing from top to bottom, down each column. 2 * = Figure 1: Left to right, the shapes λ,α and the skew shape λ∗α. P and Q, in Figure 2, are Young tableau. A skew diagram is the diagram obtained from removing a smaller Young diagram out of a larger one. The third shape in Figure 1 is a skew shape. A skew tableau is a filling of the boxes of a skew diagram with positive integers, non-decreasing in rows, and strictly increasing in columns (see Figure 5). If the number of boxes in the ith row of a tableau, for 1 ≤ i ≤ s is λ and λ := (λ ,...,λ ), it is said to have i 1 s shape λ. If the tableau houses µ copies of j for j ≤ t and µ := (µ ,...,µ ), it is said to j 1 t have content µ. Thus, in figure 2, P and Q have the same shape (5,2), but contents (3,2,2) and (4,3) respectively. We represent a Young diagram having s rows and λ boxes in the ith row by λ = (λ ,...,λ ). i 1 s Given two shapes λ and α, λ∗α is defined to be the skew-shape obtained by attaching the lower left corner of α to the upper right corner of λ as in figure 1 (see [5], page 60). size(λ,µ) denotes the number of bits used in the description of this tuple of vectors. For λ := (λ ,...,λ ), let |λ| = s λ . For vectors λ, µ, we say that λ D µ if |λ| = |µ| and 1 s Pi=1 i ∀i, λ ≥ µ . In addition, if λ 6= µ, we say λ ⊲ µ. This ordering is called the Pj≤i j Pj≤i j dominance ordering. We call a tableau Littlewood-Richardson or LR, if, when its entries are read right to left, top to bottom, at any moment, the number of copies of i encountered is greater than or equal to the number of copies of i+1 encountered ([5], page 63). We denote the set of all (possibly skew) tableaux of shape λ and content µ by T(λ,µ), and its subset consisting of all LR (possibly skew) tableaux by LRT(λ,µ). The Kostka number K is the number of λµ tableauxof shapeλandcontent µ, i.e|T(λ,µ)|([5], page25). The Littlewood-Richardson coefficient cν is the number of LR skew tableaux of shape λ∗α of content ν, i.e |LRT(λ∗ λα α,ν)| (this follows from Corollary 2, (v), page 62 and Lemma 1, page 65 of [5]). 3 The problems are in #P Valiant defined the counting class #P in his seminal paper [12], and proved that the com- putation of the permanent is #P-complete. The class #P is the class of functions f : 3 ∪n∈N{0,1}n → Z≥0, for which there exists a polynomial time turing machine M and a poly- nomialpsuch that(∀n ∈ N),(∀x ∈ {0,1}n),f(x) = |{y|y ∈ {0,1}p(n) and M accepts (x,y)}. The tableau shapes λ,α and contents µ,ν are described by vectors with integer coefficients. Therefore the number of boxes in a tableau might be exponential in the size of the input. Thus it needs to be estabilished that even though an object in T(λ,µ) or LRT(λ∗α,ν) may be exponentially large, it has a polynomial length description, and its membership (given this short description) can be verified in polynomial time. Proposition 1 The problem of determining K is in #P. λµ Proof: Let λ,µ be defined as in the Introduction. A tableau of shape λ is fully specified given the number µ of copies of i, that are present in the jth row, for all i ≤ s and j ≤ t. Thus its ij description is of length polynomial in size(λ,µ), in fact it has length O(size(λ,µ)2). Given the set {µ } , this corresponds to the tableau obtained, by writing, in the ith row, from ij i≤s,j≤t left to right, µ copies of 1, µ copies of 2 and so on for each i ≤ s. To verify whether i1 i2 this filling has the content µ, we need to verify, that µ = µ for each j, which takes Pi ij j O(size(λ,µ)2) time. To verify whether this filling has the shape λ, we need to verify, that µ = λ for each i, which again takes O(size(λ,µ)2) time. To verify whether this filling is Pj ij i a tableau, we need to check that the entries in a column of this filling are strictly increasing from top to bottom. In other words, that, for each row i ≤ s−1 and each k ≤ t−1 Xµij ≥ X µi+1,j. j≤k j≤k+1 This can be done in time O(size(λ,µ)2) if we maintained cumulative sums and calculated the next sum incrementally. Therefore the task of computing K is in #P. λµ (cid:3) Proposition 2 Given λ and µ, whether or not K > 0 can be answered in polynomial time. λµ Proof: Let λ and µ be as in proposition 1. For any permutation σ of the set {1,...,t}, let σ(µ) be the vector (µ ,...,µ ). It is a known fact that K = K (see [5], page 26). Let σ σ(1) σ(t) λµ λσ(µ) be a permutation such that ∀i ≤ t − 1, µ ≥ µ . For any µˇ, whose components are σ(i) σ(i+1) arranged in non-increasing order, it is known that K > 0 if and only if λDµˇ (see [5], page λµˇ 26). Whether λDσ(µ) can be checked in time that is O(size(λ,µ)). Thus, whether or not K > 0 can be answered in time O(size(λ,µ)ln(size(λ,µ)), which is the time it takes to λµ find a permutation σ that arranges the components of µ in non-increasing order. (cid:3) Proposition 3 The problem of computing cν is in #P. λα 4 Proof: Let λ,α and ν be defined as in the Introduction. Given S ∈ LRT(λ∗α,ν), we shall describe it as follows. Let the number of occurrences of j in the ith row of S be ν . S is described ij by (λ,α) and {ν } . Conversely, given (λ,α) and {ν } , we verify that it has ij i≤s+v,j≤u ij i≤s+v,j≤u shape λ∗α and content µ, by checking that 1. ∀i ≤ v, ν = α , Pj ij i 2. ∀i ≥ v +1, ν = λ , and Pj ij i−v 3. ∀j, ν = ν . Pi ij j This takes time O(size(λ,α,ν)2). The description corresponds to the skew filling obtained, by writing in the shape λ∗α, left to right, in the ith row, ν copies of 1, ν copies of 2 and i1 i2 so on. Such a skew filling would be a skew tableau if and only if the entries of each column strictly increased from the top to the bottom. In other words, Xνij ≥ X νi+1,j, j≤k j≤k+1 for each row i ≤ s + v − 1 other than s and each k ≤ u − 1. Thus, to verify from its description, that a given filling is an element of T(λ∗α,ν) takes polynomial time. To verify that a specified filling is LR, we need to check, that, while scanning the entries of the tableau from left to right, top to bottom, at any instant, the number of copies of j encountered is ≥ the number of copies of j +1 encountered. In other words, that the following inequality holds for every row k ≤ v+s and every j ≤ u−1, Xνij ≥ X νi,j+1. i≤k i≤k+1 Thus, to verify that a skew tableau is LR only takes time polynomial in the bit-length of its description. Thus, the problem of determining cν is in #P. λα (cid:3) 4 Hardness Results Lemma 1 Given a = (a ,a ) ∈ Z2 , a ≥ a , and b = (b ,...,b ) ∈ Zk , let λ = (|a|,a ) 1 2 ≥0 1 2 1 k ≥0 2 and µ = (b ,...,b ,a ). Then, |I(a,b)| = K . 1 k 2 λµ Proof: 5 P Q 2 1 1 1 1 1 2 3 1 1 1 1 2 R−S−K 1 1 1 2 3 2 2 Figure 2: An instance of the correspondence between I(a,b) and ∪ T(λˇ,a) × T(λˇ,b) for λˇ a = (4,3), b = (3,2,2). P Q P 1 1 1 2 3 1 1 1 1 2 Discard Q 1 1 1 2 3 Construct Q 2 3 2 2 2 3 Figure 3: An instance of the correspondence between ∪ T(λˇ,a)×T(λˇ,b) and ∪ T(λˇ,b) λˇ λˇDa for a = (4,3) and b = (3,2,2). The R-S-K (Robinson-Schensted-Knuth) correspondence ([6], or [5] pages 40-41) gives a bijectionbetweenI(a,b),thesetof2×k contingencytableswithrowsumsaandcolumnsums b, and pairs of tableaux (T ,T ) having a common shape but contents a and b respectively. 1 2 In other words, we have a bijection between I(a,b) and ∪ T(λˇ,a) × T(λˇ,b). A sample λˇ correspondence is shown in figure 2. Claim 1 For every shape λˇ = (λˇ,λˇ), such that that λˇ D a, there is exactly one tableau 1 2 having shape λˇ and content a. For any other shape λˇ there is no tableau having shape λˇ and content a. Any tableau with content a = (a ,a ) can have at most two rows, since the entries in a 1 2 single column are all distinct. Further, 1 may be present only in the 1st row, because top to bottom, each column has strictly increasing entries. Therefore for a tableau to have content a, it is necessary that |λ| = |a| and there be atleast a boxes in the 1st row. In other words, 1 T(λ,a) 6= φ =⇒ λˇ Da. Conversely, this condition together with a ≥ a , implies that a ≥ λˇ. Therefore the filling 1 2 1 2 in which the first a boxes of the top row contain 1 and all others contain 2 is a tableau (see 1 Q in Figure 3). Since all the copies of 1 must be in the first row and must be in a contiguous stretch including the leftmost box, this is the only tableau in T(λ,a). Hence the claim is proved. Thus there is a bijection between ∪ T(λˇ,a) × T(λˇ,b) and the set of tableaux of λˇ content b having some shape λˇ D a. i.e, there is a bijection between ∪ T(λˇ,a) × T(λˇ,b) λˇ and ∪ T(λˇ,b). An example of this is provided in figure 3. Let us now consider the set λˇDa ∪ T(λˇ,b). λˇDa 6 Truncate 1 1 1 2 3 P 1 1 1 2 3 4 4 2 3 Extend 2 3 4 Figure 4: An instance of the correspondence between ∪ T(λˇ,b) and T(λ,µ), where a = λˇDa (4,3),b = (3,2,2),λ = (7,3) and µ = (3,2,2,3). Claim 2 Any tableau in ∪ T(λˇ,b) can be extended to a tableau of the shape λ = (a + λˇDa 1 a ,a ) by filling the boxes that are in λ but not λˇ, with k +1. This extension is a bijection 2 2 between ∪ T(λˇ,b) and T(λ,µ). λˇDa If there is a tableau of shape λˇ and content a, λˇ ≤ |a| = a +a , and λˇ ≤ a . λˇ Da =⇒ 1 1 2 2 2 λˇ ≥ a = λ . Therefore no two of the boxes in λ which are not in λˇ belong to the same 1 2 2 column. Those of these boxes, that are present in a given row, occupy a contiguous stretch that includes the rightmost box. Therefore by filling them with k + 1 we get a tableau in T(λ,µ). Conversely, given a tableau T in T(λ,µ), deleting all boxes of T filled with k + 1 gives a tableau in ∪ T(λˇ,b). These two maps are inverses of each other and hence provide λˇDa a bijection between ∪ T(λˇ,b) and T(λ,µ). Hence the claim is proved. λˇDa An example of this correspondence has been illustrated in figure 4. Therefore, |I(a,b)| = |∪ T(λˇ,a)×T(λˇ,b)| = |∪ T(λˇ,b)| = |T(λ,µ)| = K . λˇ λˇDa λµ (cid:3) Theorem 1 The problem of computing K , even when λ has only 2 rows, is #P-complete. λµ Proof: Computing K is in #P by proposition 1. Now the result follows from Lemma 1 because λµ the computation of |I(a,b)| is known to be #P-complete ([4]). (cid:3) Lemma 2 Given λ = (λ ,λ ) ∈ Z2 , λ ≥ λ , and µ = (µ ,...,µ ) ∈ Zℓ , let α = 1 2 ≥0 1 2 1 ℓ ≥0 (α ,...,α ) where (∀i)α = µ , and ν = (ν ,...,ν ), where ∀i ≤ ℓ−1,ν = α +µ , 1 ℓ−1 i Pj>i i 1 ℓ i i i and ν = µ . Then K = cν . ℓ ℓ λµ λα Proof: cν is, by definition, |LRT(λ∗α,ν)|, which is the number of LR tableaux on the skew shape λα λ ∗ α that have content ν. The skew shape λ ∗ α consists of a copy of λ and a copy of α, as in figures 1 and 5. For any skew tableau S of shape λ ∗ α, we shall denote by S| , the α restriction of S to the copy of α and by S| , the restriction of S to the copy of λ. Thus, S| λ α is a tableau of shape α and S| is a tableau of shape λ. λ 7 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 1 1 1 2 3 4 4 1 1 1 2 3 4 4 2 3 4 2 3 4 Figure 5: An instance of the correspondence between T(λ,µ) and LRT(λ∗α,ν) for λ = (7,3) and µ = (3,2,2,3), α = (7,5,3) and ν = (10,7,5,3). Claim 3 Let S ∈ LRT(λ∗α,ν). For i ≤ ℓ−1, the ith row of S| must consist entirely of α copies of i. We proceed to show this by induction. Let i = 1. The rightmost entry of the 1st row of S| , is 1, by the LR condition. The entries of each row are non-decreasing, left to right. α Therefore each entry of the 1st row must be 1. Now assume for some r, 1 ≤ r ≤ ℓ−1, that the claim is true for all i ≤ r. If r = ℓ − 1, we are done, so let r < ℓ − 1. The entries of columns of S| are strictly increasing, top to bottom. By the induction hypothesis, the entry α directly above a square in the (r+1)th row is r. Therefore, any element in the (r+1)th row must be ≥ r +1. But the rightmost entry of the (r +1)th row cannot be anything > r +1, because this would violate the LR condition. The entries of each row are non-decreasing, left to right. Therefore each entry of the (r +1)th row must be r +1. Hence, by induction, the claim is proved. Consequently, S| must have content ν −α = µ. In other words, S| ∈ T(λ,µ). Conversely, λ λ given any tableau T ∈ T(λ,µ), let S(T) be the skew tableau of shape λ ∗ α in which S(T)| = T and the ith row of S(T)| consists entirely of copies of i. While scanning S(T) λ α right to left, top to bottom, the LR condition could not possibly be violated while on a square of S(T)| . By the time we begin scanning the rightmost box of the first row of α S(T)| , for any i ≤ ℓ−1, the number of copies of i encountered is already µ more than λ i+1 the number of copies of i+ 1 encountered. Therefore the LR condition could not possibly be violated on any square of S(T)| either. Therefore S(T) ∈ LRT(λ ∗ α,ν). S(T)| = T, λ λ thus we have a bijection between LRT(λ∗α,ν), the set of LR skew tableaux of shape λ∗α having content ν and T(λ,µ), the set of tableaux of shape λ having content µ. Hence K = |T(λ,µ)| = |LRT(λ∗α,ν)| = cν as claimed. λµ λα (cid:3) Theorem 2 The problem of computing cν , even when λ has only 2 rows is #P-complete. λα Proof: By Proposition 3, computing cν is in #P. We have already proved in Theorem 1, that the λα 8 computation of K is #P complete. The result now follows from Lemma 2. λµ (cid:3) 5 Conclusion We proved that the computation of Kostka numbers and Littlewood-Richardson coefficients is #P complete. The reduction to computing Kostka numbers was from the #P complete problem [4] of computing the number of contingency tables having given row and column sums. The problem of computing Kostka numbers was then reduced to that of computing Littlewood-Richardson coefficients. It is not known whether there exist Fully Polynomial Randomized Approximation Schemes (FPRAS) to compute any of these quantities. It would be of interest to find FPRAS to compute Kostka Numbers and Littlewood-Richardson coef- ficients. These are conjectured to exist by K. Mulmuley and M. Sohoni, [8] in their approach to the P vs NP question. 6 Acknowledgements I wish express my gratitude to Ketan Mulmuley for suggesting the topic of this paper and for many valuable discussions. Many thanks are due to Ravi Kannan for informing me about [4]. I also sincerely thank Etienne Rassart, Rahul Santhanam, and L´aszl´o Babai for helpful comments. References [1] A. Barvinok and S.V. Fomin, Sparse interpolation of symmetric polynomials, Advances in Applied Mathematics , 18 (1997), 271-285, MR 98i:05164. [2] S. Billey, V. Guillemin, E. Rassart, A vector partition function for the multiplicities of sl (C), Journal of Algebra, 278 (2004) no. 1, 251-293. k [3] C. Cochet, Kostka Numbers and Littlewood-Richardson Coefficients, preprint (2003). [4] M. Dyer, R. Kannan and J. Mount, Sampling Contingency tables, Random Structures and Algorithms, (1979) 10 487-506. [5] W. Fulton, Young Tableaux, London Mathematical Society Student Texts 35 (1997). [6] D. E. Knuth, Permutations, matrices, and generalized Young tableaux, Pacific Journal of Mathematics, vol. 34, (1970), pp. 709–727. 9 [7] A. Knutson, T. Tao, The honeycomb model of tensor products I: Proof of the saturation conjecture, J. Amer. Math. Soc. 12 (1999), 1055-1090. [8] K. Mulmuley, personal communication, (2004). [9] K. Mulmuley and M. Sohoni, Geometric complexity theory, P vs. NP, and explicit ob- structions., Proceedings, International Conference on Algebra and Geometry, Hyder- abad, (2001). [10] E. Rassart, Geometric approaches to computing Kostka numbers and Littlewood- Richardson coefficients, Thesis for the Ph.D. degree in Mathematics, Massachusetts Institute of Technology (MIT), 2004. [11] E. Rassart, A polynomiality property for Littlewood-Richardson coefficients, Journal of Combinatorial Theory, Series A 107 (2004), no. 2, 161–179. [12] L.G. Valiant, The complexity of computing the permanent, Theoret. Comp. Sci., (1979), 8:189-201. 10