AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP VNP
27
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
27
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur, Master, Bac+5
ar X iv :0 90 7. 28 50 v1 [ cs .C C] 1 6 J ul 20 09 AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP 6= VNP PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN Abstract. We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant's algebraic analog of the P 6= NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. 1. Introduction In a series of papers [43, 44, 41, 42, 40, 38, 39, 37], K. Mulmuley and M. Sohoni outline an approach to the P v.s. NP problem, that they call the Geometric Complexity Theory (GCT) program. The starting point is Valiant's conjecture VP 6= VNP [56] (see also [58, 8]) which essentially says that the permanent hypersurface in m2 variables (i.e., the set of m?m matri- ces X with permm(X) = 0) cannot be realized as an affine linear section of the determinant hypersurface in n(m)2 variables with n(m) a polynomial function of m.
Voir
ar X iv :0 90 7. 28 50 v1 [ cs .C C] 1 6 J ul 20 09 AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP 6= VNP PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN Abstract. We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant's algebraic analog of the P 6= NP conjecture. We also describe the precise separation of complexity classes that their program proposes to demonstrate. 1. Introduction In a series of papers [43, 44, 41, 42, 40, 38, 39, 37], K. Mulmuley and M. Sohoni outline an approach to the P v.s. NP problem, that they call the Geometric Complexity Theory (GCT) program. The starting point is Valiant's conjecture VP 6= VNP [56] (see also [58, 8]) which essentially says that the permanent hypersurface in m2 variables (i.e., the set of m?m matri- ces X with permm(X) = 0) cannot be realized as an affine linear section of the determinant hypersurface in n(m)2 variables with n(m) a polynomial function of m.
- group slm2 ?
- polynomial vanishing
- group
- sπcm
- representation theory
- detn
- valiant's
- gln2 ·
- ring can
Publié par
Langue
English
AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE GEOMETRIC COMPLEXITY THEORY APPROACH TO VP6=VNP
¨ PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN
Abstract.We discuss the geometry of orbit closures and the asymptotic behavior of Kronecker coefficients in the context of the Geometric Complexity Theory program to prove a variant of Valiant’s algebraic analog of theP6=N P also describe the precise separationconjecture. We of complexity classes that their program proposes to demonstrate.
1.oductionIntr
In a series of papers [43, 44, 41, 42, 40, 38, 39, 37], K. Mulmuley and M. Sohoni outline an approach to thePv.s.N Pproblem, that they call theGeometric Complexity Theory (GCT) program. The starting point is Valiant’s conjectureVP6=VNP[56] (see also [58, 8]) which essentially says that the permanent hypersurface inm2variables (i.e., the set ofm×mmatri-cesXwith permm(X) = 0) cannot be realized as an affine linear section of the determinant hypersurface inn(m)2variables withn(m) a polynomial function ofm. Their program (at least up to [44]) translates the problem of proving Valiant’s conjecture to proving a conjecture in representation theory. In this paper we give an exposition of the program outlined in [43, 44], present the representation-theoretic conjecture in detail, and present a framework for reducing their representation theory questions to easier questions by taking more geometric information into account. We also precisely identify the complexity problem the GCT approach proposes to solve and how it compares to Valiant’s original conjecture, and discuss related issues in geome-try that arise from their program. The goal of this paper is to clarify the state of the art, and identify steps that would further advance the program using recent advances in geometry and representation theory.
The GCT program translates the study of the hypersurfaces {permm= 0} ⊂Cm2and{detn0} ⊂Cn2 = , to a study of the orbit closures GLn2[ℓn−mpermm]⊂P(SnCn2) andGLn2[detn]⊂P(SnCn2), whereSnCn2denotes the space of homogeneous polynomials of degreeninn2variables. Hereℓis a linear coordinate onCand one takes any linear inclusion, C⊕Cm2⊂Cn2to haveℓn−mpermm be a homogeneous degreenpolynomial onCn2 and Sohoni observe that a variant of. Mulmuley Valiant’s hypothesis would be proved if one could show:
Conjecture 1.1.[43]There does not exist a constantc≥1such that for sufficiently largem, GLm2c[ℓmc−mpermm]⊂GLm2c[detmc]
Bu¨rgissersupportedbyDFG-grantsBU1371/2-1andBU1371/3-1.Landsberg,Weymanrespectivelysup-ported by NSF grants DMS-0805782 and DMS-0901185. 1
¨ 2 PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN It is known thatGLn2[ℓn−mpermm]⊂GLn2[detn] forn=O(m22m), see Remark 9.3.3. ˆ ˆ For a closed subvarietyXofPV, letX⊂Vdenote the cone overX. LetI(X)⊂Sym(V∗) ˆ ˆ be the ideal of polynomials vanishing onX, and letC[X] =Sym(V∗)I(X) denote the homoge-neous coordinate ring. For two closed subvarietiesX, YofPV, one hasX⊂YiffC[Y] surjects ontoC[X] by restriction of polynomial functions. The GCT program sets out to prove:
Conjecture 1.2.[43]For allc≥1there exists for infinitely manyman irreducibleGLm2c-module appearing inCGLm2c[ℓmc−mpermm]], but not appearing inCGLm2c[detmc]]. Both varieties occuring in Conjecture 1.2 are invariant underGLm2c, so their coordinate rings areGLm2c 1.1 is a straightforward consequence of Conjecture 1.2 by-modules. Conjecture Schur’s lemma. A program to prove Conjecture 1.2 is outlined in [44]. This paper also contains a discussion why the desired irreducible modules (calledrepresentation theoretic obstructions) should exist. This is closely related to a separability question [44, Conjecture 12.4] that we will not address in this paper. There are several paths one could take to try to find such a sequence of modules. The path choosen in [44] is to considerSLn2detnandSLm2permmbecause on one hand, their coordinate rings can be determined in principle using representation theory, and on the other hand, they are closed affine varieties. Mulmuley and Sohoni observe that any irreducibleSL2-module appearing inC[SLn2detn] must also appear in the gradedSLn2-moduleCGLn2[detn]]δfor some degreeδ the permanent, for. Regardingn > m,SLn2ℓn−mpermmis not closed, so they develop machinery to transport information aboutC[SLm2permm] toCGLn2[ℓn−mpermm]], in particular they introduce a notion ofpartial stability. We make a close study of how one can exploit partial stability to determine theGLn2-module decomposition ofCGLn2ℓn−mpermm] in§ also discuss a more elementary approach to5. We studying which modules inC[GLn2ℓn−mpermm] could appear inCGLn2ℓn−mpermm]δfor eachδ could get more information from the elementary approach if one could solve the. One extension problemof determining which functions on the orbitGLn2ℓn−mpermmextend to the orbit closureGLn2ℓn−mpermm. In general the extension problem is very difficult, we discuss it in§7. We express the restrictions on modules appearing inCGLn2ℓn−mpermm] that we do have , as well as our information regardingCGLn2detn], in terms ofKronecker coefficients, culminating in Theorem 5.7.1. Kronecker coefficients are defined as the multiplicities occurring in tensor products of representations of symmetric groups. We review all relevant information regarding these coefficients that we are aware of in§ from this information, we are8. Unfortunately, currently unable to see how one could prove Conjecture 1.2 in the casec= 1 (which is straight-forward by other means), let alone for allc we have found the GCT program a. Nevertheless, beautiful source of inspiration for future work.
This program is beginning to gain the attention of the mathematical community, for example the recent preprints [47], where an algorithm is given for determining if one orbit is in the closure of another, and [6], where a conjecture of Mulmuley regarding Kronecker coefficients is disproven and, in an appendix by Mulmuley, a modified conjecture is proposed.
Acknowledgments. ThisIt is a pleasure to thank Shrawan Kumar for very useful discussions. paper is an outgrowth of the AIM workshopGeometry and representation theory of tensors for computer science, statistics and other areasJuly 21-25, 2008, and authors gratefully thank AIM and the other participants of the workshop.
GCT APPROACH TOVP6=VNP
2.Overview
3
We begin, in§3, by establishing notation and reviewing basic facts from representation theory that we use throughout. In§ In4 we discuss coordinate rings of orbits and orbit closures.§5 we make a detailed study of the cases at hand. While [44] is primarily concerned withSLn2detn and a corresponding closed orbit related to the permanent, we also study the coordinate rings of the orbits of the general linear groupGLn2. TheGLn2-orbits have the disadvantage of not being closed in general, so one must deal with the extension problem, which we discuss in§7, but they have the advantage of having a graded coordinate ring. The orbitSLn2ℓn−mpermmis not closed, but the smaller groupSL2⊂SL2has the property thatSLm2ℓn−mpermmis closed, and the modules appearing inGLn2ℓn−mpermm(ignoring multiplicities) are “inherited” from modules in the coordinate ring ofSLm2ℓn−mpermm, in a manner described precisely in§4.5, where we discuss the notion ofpartial stability. One goal of [44] is to reduce the conjectureVP6=VNP(more specifically,VPws6=VNP – see§ explicitly state the conjecture in repre- We9) to a conjecture in representation theory. sentation theory that follows from the work in [44] in Theorem 5.7.1. We then, in§6.1, state the theorems in [44] that, together with our computations in§5 (which build on calculations in [44]), imply Theorem 5.7.1. We also give an overview of their proofs. The consequences of partial stability can be viewed from the perspective of thecollapsing methodfor computing coordinate rings (and syzygies), which we discuss in§6.2. In the studies of the coordinate rings ofCGLn2[ℓn−mpermm]] andCGLn2[detn]], and the resulting conjecture in representation theory mentioned above,Kronecker coefficients We discuss what is knownplay a central role. about the relevant Kronecker coefficients in§8. In§9, we give a brief outline of the relevant algebraic complexity theory involved here. We explain Valiant’s conjectureVP6=VNP, how this precisely relates to the conjecture regarding projecting the determinant to the permanent, and we formulate Conjecture 1.1 as the separation of complexity classesVPws6=VNP.
3.Notation and Preliminaries
Throughout we work over the complex numbersC. LetVbe a complex vector space, let GL(V) denote the general linear group ofV, letv∈Vand letG⊆GL(V We) be a subgroup. letGv⊂Vdenote the orbit ofv,Gv⊂Vits Zariski closure, andG(v)⊂Gthe stabilizer of v, soGv≃GG(v). WriteC[Gv] (respectivelyCGv]) for the ring of regular functions on Gv(resp.Gv restriction, there is a surjective map). BySym(V∗)→CGv]. It will be convenient to switch back and forth between vector spaces and projective spaces. PVdenotes the space of lines through the origin inV. Ifv∈Vis nonzero, let [v]∈PVdenote the corresponding point in projective space, and ifx∈PV, letxˆ⊂Vdenote the corresponding line. A linear action ofGonVinduces an action ofGonPV, letG([v]) denote the stabilizer of ˆ [v]∈PV. IfZ⊂PVis a subset, letZ⊂Vdenote the corresponding cone inV. We will be concerned with the space of homogeneous polynomials of degreeninn2variables, V=Sn(Mat∗n×n) =SnW. Here Matn×ndenotes the space ofn×n,secirtam-SnWthe space of homogeneous polynomials of degreenonW∗, andG=GL(W main points of interest). Our will bex= [detn] andx= [ℓn−mpermm], where detn∈Sn(Matn∗×n) is the determinant of ann×nmatrix, permm∈Sm(Mat∗m×mthe permanent, we have made a linear inclusion) is Matm×m⊂Matn×n, andℓis a linear form on Matn×nannihilating the image of Matm×m. For a reductive groupG, the set of dominant integral weights ΛG+indexes the irreducible (finite dimensional)G-modules (see, e.g., [16, 25]), and forλ∈Λ+G,Vλ(G) denotes the irreducibleG-module with highest weightλ, and ifGis understood, we just writeVλ. IfH⊂Gis a subgroup, andVaG-module, letVH:={v∈V|hv=v∀h∈H}denote the space ofH-invariant vectors.
4
¨ PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN
For aG-moduleV, let mult(Vλ(G), V) denote the multiplicity of the irreducible representation Vλ(G) inV. The weight lattice ΛGLMofGLMisZMand the dominant integral weights ΛG+LMcan be identified with theM-tuples (π1, , πM) withπ1≥π2 ≥≥ πM future reference, we. For note
(3.0.1)V(π1πM)(GLM)∗=V(−πM−π1)(GLM) The polynomial irreducible representations ofGLMare the Schur modulesSπCM, indexed by partitionsπ= (π1, , πM) withπ1≥π2 ≥≥ πM≥0. To get all the rational irreducible representations we need to twist by negative powers of the determinant. This introduces some redundancies sinceSπCM⊗(detCM)⊗k=Sπ+(kk)CM avoid them, we consider the. To modulesSπCM⊗(detCM)⊗kwithk∈Zandπ= (π1, , πM−1, we write our0). Moreover partitions asπ= (π1, , πN) with the convention thatπ1≥ ≥ πN>0, and we let|π|= π1+ +πNandℓ(π) =N. The irreducibleSLM-modules are obtained by restricting the irreducibleGLM-modules, but beware that this is insensitive to a twist by the determinant. The weight lattice of ΛSLMof SLMisZM−1and the dominant integral weights ΛS+LMare the non-negative combinations of the fundamental weightsω1, , ωM−1. A Schur moduleSπCMconsidered as anSLM-module has highest weight
λ=λ(π) = (π1−π2)ω1+ (π2−π3)ω2+ + (πM−1−πM)ωM−1 We writeSπCM=Vλ(π)(SLM) or simplyVλ(π)ifSLMis clear from the context. Letπ(λ) denote the smallest partition such that theGLM-moduleSπ(λ)CM, considered as anSLM-module, isVλ. That is,πis a map from ΛS+LMto ΛG+LM, mappingλ=PMj=−11λjωjto M−1M−1 π(λ) = (Xλj,Xλj, , λM−1) j=1j=2
4.Stabilizers and coordinate rings of orbits
As mentioned in the introduction, [44] proposes to study the rings of regular functions on GLn2detnandGLn2ℓn−mpermmby first studying the regular functions on the closed orbits SLn2detnandSLm2ℓn−mpermm. In this section we review facts about the coordinate ring of a homogeneous space and stability of orbits, record observations in [44] comparing closed SL(W)-orbits andGL(W)-orbit closures, state their definition of partial stability and record Theorem 4.5.5 which illustrates a potential utility of partial stability. Throughout this section, unless otherwise specified,Gwill denote a reductive group andVa G-module.
4.1.Coordinate rings of homogeneous spaces.The coordinate ring of a reductive group Ghas a left-right decomposition, as a (G−G)-bimodule, (4.1.1)C[G] =MVλ∗⊗Vλ, + λ∈ΛG
whereVλdenotes the irreducibleG-module of highest weightλ.
GCT APPROACH TOVP6=VNP
5
LetH⊂G coordinate ring of the homogeneous space Thebe a closed subgroup.GHis obtained by taking (right)H-invariants in (4.1.1) giving rise to the (left)G-module decomposi-tion H (4.1.2)C[GH] =C[G]H=MVλ∗⊗VλHM(Vλ∗)⊕d =imVλ λ∈Λ+Gλ∈Λ+G The second equality holds becauseVλHis a trivial (left)G [27, Thm.-module. See II, Ch. 3,§3], or [48,§7.3] for an exposition of these facts.
4.2.Orbits with reductive stabilizers.LetGbe a reductive group, letVbe an irreducible G-module, and letv∈Vbe such that its stabilizerG(v Then) is reductive.Gv=GG(v)⊂V is an affine variety ([35] Corollary p. 206). This implies that the boundary ofGvis empty or has pure codimension one inGv. 4.3.Stability.Following Kempf [23], a non-zero vectorv∈Vis said to beG-stableif the orbit Gvis closed. then also say that [ Wev]∈PVisG-stable. IfV=SdWfor dimW >3,d >3 andv∈Vis generic, then by [46] its stabilizer is finite, and by [27, II 4.3.D, Th. 6 p. 142], this implies thatvis stable with respect to theSL(W)-action. Kempf ’s criterion [23, Cor. 5.1] states that ifGdoes not contain a non-trivial central one-parameter subgroup, and the stabilizerG([v]) is not contained in any proper parabolic subgroup ofG, thenvisG-stable. We will apply Kempf ’s criterion to the determinant in§5.2 and to the permanent in§5.5. IfvisG-stable, then of courseC[Gv] =CGv]. The former is an intrinsic object with the above representation-theoretic description, while the latter is the quotient of the space of all polynomials onVby those vanishing onGv.
4.4.GL(W)v.s.SL(W)orbits.LetVbe aGL(W)-module and letv∈Vbe nonzero. Suppose that the homotheties inGL(W) act non-trivially onv the orbit. ThenGL(W)vis never stable, as it contains the origin in its closure. Assume thatvisSL(W)-stable, soC[SL(W)v] =CSL(W)v] can be described using (4.1.2). Unfortunately the ringC[SL(W)v However] is not graded.GL(W)vis a cone over SL(W)v coordinate ring ofwith vertex the origin. TheGL(W)vis equipped with a grading becauseGL(W)vis invariant under rescaling, so any polynomial vanishing on it must also have each of its homogeneous components vanishing on it separately. In fact this coordinate ring is the image of a surjective mapSym(V∗) =C[V]→CGL(W)v], given by restriction of polynomial functions, and this map respects the grading. Consider the restriction mapCGL(W)v]δ→C[SL(W)v]. It is injective for allδbecause a homogeneous polynomial vanishing on an affine variety vanishes on the cone over it. On the other hand, becauseSL(W)vis a closed subvariety ofGL(W)v, restriction of functions yields a surjective mapCGL(W)v]→C[SL(W)v]. BothCGL(W)v]δ,C[SL(W)v] are SL(W)-modules (asGL(W)vis also anSL(W)-variety), and the map between them is an SL(W)-module map because theSL(W)-action on functions commutes with restriction. Summing over allδyields a surjectiveSL(W)-module map MCGL(W)v]δ→C[SL(W)v], δ that is injective in each degreeδ have the following consequence observed in [44]:. We
Proposition 4.4.1.LetVbe aGL(W)-module and letv∈VbeSL(W)-stable. An irreducible SL(W)-module appears inC[SL(W)v]iff it appears inCGL(W)v]δfor someδ.
6
¨ PETER BURGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN
In contrast to the case ofSL(W), if an irreducible module occurring inC[GL(W)v] also occurs inCGL(W)v]⊂Sym(V∗ Consider the case), we can recover the degree it appears in. V=SdW, then aGL(W)-moduleSπWcan only occur inCGL(W)v] if|π|=δdfor someδ and in that case it can only appear inCGL(W)v]δ⊂Sδ(SdW∗)⊂Sym(SdW∗) (see Example 5.1 below).
4.5.Partial stability and an application.LetVbe aGL(W)-module. Letv, w∈Vbe SL(W Equation (4.1.2) and Proposition 4.4.1 imply the following observation:)-stable points. w ∈GL(W)v(equivalentlyGL(W)w6⊂GL(W)v) if there is anSL(W)-module that con-tains aSL(W)(w)-invariant that does not contain aSL(W)(v discussed below,)-invariant. As detnisSL(W)-stable, and whileℓn−mpermmis notSL(W)-stable, it is what is calledpartially stablein [44], which allows one to attempt to search for such modules as we now describe.
Definition 4.5.1.[44] LetGbe a reductive group and letVbe aG-module. LetP=KUbe a Levi decomposition of a parabolic subgroup ofG. LetRbe a reductive subgroup ofK. We say that [v]∈PVis (R, P)-stableif it satisfies the two conditions (1)U⊂G([v])⊂P. (2)vis stable under the restricted action ofR, that isRvis closed. Example 4.5.2.Ifx∈SdW′is a generic element andW′(Wis a linear inclusion, thenxis notSL(W)-stable, but it is (SL(W′), P) stable forPthe parabolic subgroup ofSL(W) fixing the subspaceW′⊂W follows from. This§4.3, assuming dimW′>3 andd >3. Example 4.5.3.LetW=A⊕A′⊕B,A=E⊗F≃M atm×m, dimA′= 1, andG=SL(W). Letℓ∈A′such thatℓ6= 0. It follows from§4.3 thatℓn−mpermm∈SnM at∗n×nis (R, P)-stable forR=SL(A) andPthe parabolic subgroup ofG=GL(W) preservingA⊕A′, whose Levi factor isK= (GL(A⊕A′)×GL(B)).
The point of partial stability is that, since the pointvis assumed to beR-stable, the problem of determining the multiplicities of the irreducible modulesVν(R) inCRv] is reduced to the problem of determining the dimension ofVν(R)R(v) the case. InR=K, these are also the multiplicities of the corresponding irreducible representations in the coordinate ringCGv]. We will now state a central result of [44] (Theorem 6.1.5 below) in the special case that will be applied toℓn−mpermm. We first need to recall the classical Pieri formula (see, e.g., [59], Proposition 2.3.1 for a proof ): Proposition 4.5.4.FordimA′= 1, one has theGL(A)×GL(A′)-module decomposition Sπ(A⊕A′) =MSπ′A⊗S|π|−|π′|A′, π7→π′ where the notationπ7→π′means thatπ1≥π′1≥π2≥π′2≥ ≥ 0 Theorem 4.5.5.LetW=A⊕A′⊕B,dimA=a,dimA′= 1,z∈Sd−sA,ℓ∈A′\ {0}. AssumezisSL(A)-stable. Writev=ℓsz. SetR=SL(A), and takePto be the parabolic of GL(W)preservingA⊕A′, soK=GL(A⊕A′)×GL(B), andzis(R, P)-stable. (1)A moduleSνW∗occurs inCGL(W)v]δiffSν(A⊕A′)∗occurs inCGL(A⊕A′)v]δ. There is then a partitionν′such thatν7→ν′andVλ(ν′)(SL(A))⊂CSL(A)[v]]δ. (2)Conversely, ifVλ(SL(A))⊂CSL(A)[v]]δ, then there exist partitionsπ, π′such that SπW∗⊂CGL(W)[v]]δ,π7→π′andλ(π′) =λ. (3)A moduleVλ(SL(A))occurs inCSL(A)[v]]iff it occurs inC[SL(A)v].
