Users.math.cas.cz

Geometric Complexity Theory III: on deciding positivity of Littlewood-Richardson coefficients The University of Chicago and I.I.T., Mumbai∗ We point out that the remarkable Knutson and Tao Saturation Theorem and polynomial time algorithms for linear programminghave together an important, immediate consequence in geomet-ric complexity theory : The problem of deciding positivity ofLittlewood-Richardson coefficients belongs to P ; cf..
Specifically, for GLn(C), positivity of a Littlewood-Richardson co- efficient cα,β,γ can be decided in time that is polynomial in n and thebit lengths of the specifications of the partitions α, β and γ. Further- more, the algorithm is strongly polynomial in the sense of .
The main goal of this article is to explain the significance of this result in the context of geometric complexity theory. Furthermore, itis also conjectured that an analogous result holds for arbitrary sym-metrizable Kac-Moody algebras.
The fundamental Littlewood-Richardson rule in the representation the- ory of GLn(C) states that the tensor product of two irreducible repre-sentations (Weyl modules) Vα and Vβ of GLn(C) decomposes as follows: where cα,β,γ are Littlewood-Richardson coefficients. Here α, β are partitions(Young diagrams) with at most n rows. The sum is over all Young diagramsγ of height at most n, and size equal to the sum of the sizes of α and β.
This rule has been studied intensively in representation theory; cf. Ful- ton . But the problem of deciding positivity of cα,β,γ efficiently didnot receive much attention, perhaps because there was really no motiva-tion for studying it. The problem arises naturally in geometric complexitytheory , which is an approach to the fundamental problems incomplexity theory (GCT), such as P vs. N P , through algebraic geometryand representation theory. The basic philosophy of this approach is the flipfrom hard nonexistence to easy existence. Specifically, the approach firstreduces the hard nonexistence problems in complexity theory, such as Pvs. N P , in characteristic zero, to showing existence of certain obstructions,which are certain gadgets with algebro-geometric and representation the-oretic properties. The central geometric invariant theoretic results ofGCT pave the road for proving easiness of this and related existenceproblems in geometric invariant theory, once certain existence problems inrepresentation theory are shown to be easy. The transition from nonexis-tence to existence was proposed in . The stronger transition from hardnonexistence to easy existence was proposed in , which is an extendedabstract of .
By divine justice, as was to be expected for the P vs. N P problem, show- ing that these representation theoretic existence problems are easy turnedout to be extremely hard. Because they are intimately related to the cen-tury old, fundamental unsolved problems of representation theory, such asthe plethysm problem . As such, when the flip philosophy was first pro-posed in , it went against the common belief among mathematicians.
Deciding positivity of a Littlewood-Richardson coefficient cγ –i.e. deciding if the the Weyl module Vγ occurs (exists) within Vα ⊗ Vβ–is the simplestinstance of a general existence problem, called the subgroup restriction prob-lem in described below. Its membership in P (Theorem provides thefirst concrete evidence in support of the flip philosophy of GCT.
It is a direct consequence of the Saturation Theorem of Knutson and Tao and polynomial time algorithms for linear programming . Aftera preliminary version of this note was written, it was communicated to us byProf. Tao that actually they had thought briefly about the polynomial timealgorithm question for positivity in the different context of the Honeycombmodel , and asked Peter Shor about it. He basically gave the sameresponse that is in this note. See page 180-181 of ; though there is a slight error in that paper, in asserting that the simplex method takespolynomial time. Nevertheless, as we point out, for the LP that arises hereeven a strongly polynomial time algorithm exists.
The Saturation Theorem itself was proved in an entirely different con- text: as a step in the proof of Horn’s conjecture , which arose fromthe work of H. Weyl in 1912 and I. M. Gelfand in 1940’s. After several at-tempts, finally Klyachko proved some remarkable results in the study ofstability criterion for toric vector bundles on the projective plane. Zelevin-sky observed that Horn’s conjecture would follow from these results ifthe Saturation Conjecture were proved; as happened soon after in . Forthe sake of a computer scientist not familiar with these developments, wegive a self-contained proof of Theorem here, assuming only the statementof the Saturation Theorem.
Theorem was stated in as known, implicitly assuming integrality of the polytope P defined below. We recently realized that P need not beintegral, in view of , which disproved a conjecture of Berenstein andKirillov that Gelfand-Tsetlin polytopes are integral. Fortunately, theSaturation Theorem, which had come to our attention just then, provideda sufficient relaxation of integrality.
Let λ = (λ1, · · · , λk), where λ1 ≥ λ2 ≥ · · · λk > 0, be a partition (Young diagram). By its bit length, we mean the bit length of its specification,which is i). Observe that the dimension of the Weyl module Vλ can be exponential in n, k and the bit lengths of λi’s. Because the dimensionof Vλ is the total number of semistandard tableau of shape λ with entries in[1, n] .
Theorem 1 Given partitions α, β and γ, deciding if Vγ exists within Vα ⊗Vβ–i.e. if cα,β,γ is positive–can be done in polynomial time; i.e., in timethat is polynomial in n and the bit lengths of α, β, and γ1 Furthermore, thealgorithm is strongly polynomial in the sense of .
This is remarkable, since the dimensions of Vα, Vβ, Vγ can be exponen- tial in n and the bit lengths of αi, βj and γk’s. What the result says isthat whether an exponential dimensional object Vγ can be embedded in an-other exponential dimensional object Vα ⊗ Vβ can be decided in time thatis polynomial in n and the bit lengths of just their labels α, β and γ.
1If we assume that a partition λ is specified as (λ1, · · · , λn), with λ1 ≥ · · · ≥ λn, where λi = 0 for i higher than the height of λ, then the term n can be subsumed in the bitlength of the input.
Strong polynomiality stated in the theorem means that : (1) The number of arithmetic steps in the algorithm is polynomial in n. It does notdepend on the bit lengths of αi, βj, and γk’s. (3) The bit length of everyintermediate operand that arises in the algorithm is polynomial in the totalbit length of α, β and γ.
The fundamental problems and conjectures in representation theory thatarise in geometric complexity theory are instances of the following subgrouprestriction problem. Suppose G is a reductive group over C . In com-plexity theory, we shall only be interested in nice reductive groups such as:SLn(C), the classical simple groups, the group C∗ of nonzero complex num-bers, finite simple groups, and the groups obtained from these by standardgroups theoretic constructions such as products, wreath products etc. Sup-pose H ⊆ G is a nicely embedded, nice subgroup of G. Two importantexamples of nice embeddings are: 1. H → G = H × H (diagonal map). In this case, the subgroup restric- tion problem will reduce to decomposing the tensor product of tworepresentations of H, together with the associated decision problem.
2. GL(Cn) × GL(Cn) → GL(Cn ⊗ Cn).
restriction problem will become equivalent to finding a positive de-composition of the tensor product of two irreducible representations(Specht modules) of the symmetric group –a fundamental, cen-tury old unsolved problem in the representation theory of the sym-metric groups–together with the associated decision problem.
3. U is a representation of H, G = GL(U ), and H → G is the represen- tation homomorphism. In this case, the subgroup restriction problemwill reduce to the (generalized) plethysm problem –a fundamen-tal, century old unsolved problem in the representation theory of thegeneral linear group–together with the associated decision problem.
Let V = Vα be a representation of G, where α is a label that completelyspecifies V . For example, if G = GLn(C), and Vα is its irreducible represen-tation (Weyl module) then the label α is the Young diagram. If V = Vβ ⊗Vγ,where Vβ and Vγ are irreducible, then the label α is the composite β ⊗ γ,and so on.
Since H is a subgroup of G, V is also a representation of H. The classical result of H. Weyl says that V has an essentially unique decomposition as anH-module: where β is the label ranging over irreducible representations of H, Wβ is thecorresponding irreducible representation, and m(β) is its multiplicity.
The subgroup restriction problem is find an explicit efficient positive de- composition rule for akin to the Littlewood-Richardson rule for . Theassociated existence problem is: given labels α and β of H and G respec-tively, does Wβ occur within Vα? That is, is m(β) positive? The goal is toshow that this problem belongs to the complexity class P . Here by poly-nomial, we mean polynomial in the numeric parameters associated with Gand H and the bit lengths of the labels α, β. For example, the numericparameter associated with GLn(C) is n, with the symmetric group Sn is n,and if G is built using products etc. then they are the numeric parametersof the building blocks.
When H = GLn(C) → GLn(C) × GLn(C), the decomposition coin- cides with the tensor product decomposition , and the decision problemis simply deciding positivity of a Littlewood-Richardson coefficient. Thoughthe general problem is far harder than the latter, it is qualitatively similar.
Hence, Theorem supports the conjecture that the general problem alsobelongs to P .
Once this representation theoretic existence problem is shown to be in P , and a sufficiently concrete form of the decomposition is found,the central algebro-geometric results of GCT in give a lead on the(harder) geometric invariant theoretic existence problems in GCT. The roadahead is undoubtedly long and arduous, but, at least, the journey has begun.
The proof of Theorem follows easily from the following three results: 1. Littlewood-Richardson rule: specifically, a polyhedral interpretation of the Littlewood-Richardson coefficients. The polytope we use hereis more elementary than Berenstein-Zelevinsky polytope and theHive polytope –the latter two have some stronger properties notused here.
3. Polynomial time algorithm for linear programming: e.g. the ellipsoid or the interior point method, and the related strongly polynomial timealgorithm for combinatorial linear programming due to Tardos .
Let us begin with a polyhedral interpretation; this should be well known.
Recall that the Littlewood-Richardson coefficient cγ Let us say that a word w = w1 · · · wr is a reverse lattice word if, when read backwards from the end to any letter ws, s < r, the sequence wr · · · wscontains at least as many 1’s as 2’s, at least as many 2’s as 3’s, and so onfor all positive integers. The row word w(T ) of a skew tableau T is definedto be the word obtained by reading its entries from bottom to top, and leftto right. A skew-tableau T of shape γ/α is called a Littlewood-Richardsonskew tableau if its row word w(T ) is a reverse lattice word.
is the number of Littlewood-Richardson skew tableaux of Let ri(T ), i ≤ n, j ≤ n, denote the number of j’s in the i-th row of T .
These are integers satisfying the constraints: 4. Tableau constraints: No k ≤ j occurs in the row i + 1 of T below a j 5. Reverse lattice word constraints: ri = 0 for i < j, and for i ≤ n, Let r denote the vector with the entries ri (T ). These constraints can be where the entries of A are 0, 1 or −1, and the entries of b are homogeneous,integral, linear forms in αi, βj, and γk’s. Thus cγ points in the polytope P determined by these constraints.
Claim 1 The polytope P contains an integer point iff it is nonempty.
Suppose P is nonempty. Since b is homogeneous in α, β and γ, it follows the scaled polytope qP . All vertices of P have rational coefficients. Hence,for some positive integer q, the scaled polytope qP has an integer point. Itfollows that, for this q, cqγ is positive. Saturation Theorem says that, is positive. Hence, P contains an integer point. Q.E.D.
Whether P is nonempty can be determined in polynomial time using either the ellipsoid or the interior point algorithm for linear programming.
Since the linear program is combinatorial , this can also be done instrongly polynomial time using Tardos’ algorithm . This proves Theo-rem It is of interest to know if there is a purely combinatorial algorithm for this problem that does not use linear programming; i.e., one similar tothe max-flow or weighted matching problems in combinatorial optimization.
The polytopes that arise in these combinatorial optimization problems areunimodular and integral–i.e., their vertices are integral . In contrast, Pneed not be integral. This is known for the Gelfand-Tsetlin polytope thatarises in the study of Kostka numbers, and also for the Hive polytope. Unlike the hive polytope , P need not even have an integral vertex.
It is reasonable to conjecture that there is a polynomial time algorithm thatprovides an integral proof of positivity of cγ , in the form of an integral point in P . The above algorithm, as also the one in , only provides arational proof; i.e., a rational point in P .
There is a generalization of the Littlewood-Richardson rule for arbitrary classical Lie algebras, and also for symmetrizable Kac-Moody algebras . It was erroneously stated in as known that the problem of decidingpositivity of generalized Littlewood-Richardson coefficients also belongs toP . But now we conjecture that this is so.
Specifically, let G be a symmetrizable generalized Kac-Moody algebra , with rank r, which is the dimension of the corresponding symmetriz-able generalized Cartan matrix. Let Vα, Vβ be two irreducible integrablerepresentations of G with highest weights α and β. Then it is known that are generalized Littlewood-Richardson coefficients, as defined in Conjecture 2 Given fixed α, β, γ, positivity of cγ nomial time; i.e. in time that is polynomial in the rank r and the bit lengthsof the specifications of α, β, γ. Furthermore, there exists a strongly polyno-mial time algorithm for the same.
The proof here does not generalize, since the saturation conjecture is known to be false for the type B, C, D . Hari Narayanan pointedout to us that J. De Loera and T. McAllister have recently made someconjectures for the hive polytopes for types B, C, D. These may provide astep towards the proof of Conjecture for types B, C, D.
Given the fundamental importance of the P vs. N P question, we hope this note will bring to a computer scientist’s attention, similar, but far moreformidable conjectures of geometric complexity theory . The first few in-stances of these conjectures say that the decision versions of the well knownrepresentation theoretic positivity problems , such as the plethysm prob-lem, have (strongly) polynomial time algorithms. It also makes sense tomake similar conjectures for other positivity problems in not consideredin , such as the ones concerning Kazdan-Lusztig polynomials.
[1] A. Berenstein and A. Kirillov: Groups generated by involutions, Gelfand-Tsetlin patterns, and combinatorics of Young tableaux,Algebra i Analiz 7 (1995), no. 1, 92-152 (Russian). Translation inSt. Petersburg Math. J. 7 (1996), no. 1, 77-127.
[2] A. Berenstein, A. Zelevinsky: Triple multiplicities for sl(r + 1) and the spectrum of the exterior algebra of the adjoint representation.
J. Algebraic Combin. 1 (1992) no. 1, 7-22.
Elashvili: Invariant algebras, pp. 57-64 in Lie groups, their dis- crete subgroups and invariant theory, edited by E. Vinberg, Ad-vances in Soviet Math. 8, Amer. Math. Soc., Providence, RI, 1992.
[4] W. Fulton, J. Harris: Representation theory, Springer Verlag, 1991.
[5] W. Fulton: Eigenvalues of sums of Hermitian matrices (after A Klyachko), pp. 255-269 in S´eminaire Bourbaki 1997/98 (expos´es835-849), Ast´erisque 252, Soc. math. France, Paris, 1999.
[6] W. Fulton: Young tableaux, London Mathematical Society, 1997.
[7] M. Kashiwara: Crystallizing the q-analogoue of universal envelop- ing algebra, Commun. Math. Phys. 133 (1990) 249-260.
Richardson polynomials and Kostka coefficients, in CRM Proceed-ings and Lecture Notes, Vol 34, 2003.
[9] A. Knutson, T. Tao: The honeycomb model of GLn(C) tensor products I: proof of the saturation conjecture, J. Amer. Math. Soc.
12 (1999) 1055-1090.
[10] A. Knutson, T. Tao: Honeycombs and sums of Hermitian matrices, Notices Amer. Math. Soc. 48 (2001) No. 2, 175-186.
[11] P. Littelmann: A Littlewood-Richardson rule for symmetrizable Kac-Moody Lie algebras, Invent. math. 116 (1994), 329-346.
[12] J. De Loera, T. McAllister: Vertices of Gelfand-Tsetlin polytopes, [13] T. Nakashima: Crystal base and a generalization of Littlewood- Richardson rule for the classical Lie algebras, Commun. Math.
Phys. 154 (1993), 215-243.
[14] M. Grotschel, L. Lovasz, A. Schrijver: Geometric algorithms and combinatorial optimization, Springer Verlag, 1993.
[15] K. Mulmuley, M. Sohoni: Geometric complexity theory: An ap- proach to the P vs. NP and related problems, SIAM J. comput.
vol. 31, no. 2, pp 496-526, (2001) [16] K. Mulmuley, M. Sohoni: Geometric complexity theory, P vs. NP and explicit obstructions, in “Advances in Algebra and Geometry”,Edited by C. Musili, the proceedings of the International Confer-ence on Algebra and Geometry, Hyderabad 2001.
[17] K. Mulmuley, M. Sohoni: Geometric complexity theory II: explicit obstructions, preprint, 2001. Its extended abstract appears in above.
[18] D. Mumford, J. Fogarty, F. Kirwan: Geometric invariant theory, [19] R. Stanley: Positivity problems and conjectures in algebraic com- binatorics, In mathematics: frontiers and perspectives, 295-319,Amer. Math. Soc. Providence, RI (2000).
[20] A. Zelevinsky: Littlewood-Richardson semigroups, New perspec- tives in Geometric Combinatorics, MSRI publications, vol. 38,1999.

Source: http://users.math.cas.cz/~pudlak/alg-geom/mulmuleygct3.pdf