AN OVERVIEW OF MATHEMATICAL ISSUES ARISING IN THE
GEOMETRIC COMPLEXITY THEORY APPROACH TO VP 6= VNP

arXiv:0907.2850v1 [cs.CC] 16 Jul 2009

PETER BÜRGISSER, 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= N P conjecture. We also describe the precise separationof 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 anapproach to the P v.s. N P 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 matrices 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. 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 tosolve and how it compares to Valiant’s original conjecture, and discuss related issues in geometry that arise from their program. The goal of this paper is to clarify the state of the art, andidentify steps that would further advance the program using recent advances in geometry andrepresentation theory.
The GCT program translates the study of the hypersurfaces22and {detn = 0} ⊂ Cn ,{permm = 0} ⊂ Cm
to a study of the orbit closures2

2

GLn2 · [ℓn−m permm ] ⊂ P(S n Cn ) and GLn2 · [detn ] ⊂ P(S n Cn ),2where S n Cn denotes the space of homogeneous polynomials of degree n in n2 variables. Here ℓ is22
a linear coordinate on C, and one takes any linear inclusion C ⊕ Cm ⊂ Cn to have ℓn−m permm
2
be a homogeneous degree n polynomial on Cn . Mulmuley and Sohoni observe that a variant of
Valiant’s hypothesis would be proved if one could show:
Conjecture 1.1. [43] There does not exist a constant c ≥ 1 such that for sufficiently large m,
GLm2c · [ℓmc −m permm ] ⊂ GLm2c · [detmc ].
Bürgisser supported by DFG-grants BU 1371/2-1 and BU 1371/3-1. Landsberg, Weyman respectively supported by NSF grants DMS-0805782 and DMS-0901185.
1

2

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

It is known that GLn2 · [ℓn−m permm ] ⊂ GLn2 · [detn ] for n = O(m2 2m ), see Remark 9.3.3.
For a closed subvariety X of PV , let X̂ ⊂ V denote the cone over X. Let I(X̂) ⊂ Sym(V ∗ )be the ideal of polynomials vanishing on X̂, and let C[X] = Sym(V ∗ )/I(X̂) denote the homogeneous coordinate ring. For two closed subvarieties X, Y of PV , one has X ⊂ Y iff C[Y ] surjects
onto C[X] by restriction of polynomial functions.
The GCT program sets out to prove:
Conjecture 1.2. [43] For all c ≥ 1 there exists for infinitely many m an irreducible GLm2c module appearing in C[GLm2c · [ℓmc −m permm ]], but not appearing in C[GLm2c · [detmc ]].
Both varieties occuring in Conjecture 1.2 are invariant under GLm2c , so their coordinate
rings are GLm2c -modules. Conjecture 1.1 is a straightforward consequence of Conjecture 1.2 by
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 (called representation theoretic obstructions) should exist.
This is closely related to a separability question [44, Conjecture 12.4] that we will not addressin this paper.
There are several paths one could take to try to find such a sequence of modules. The pathchoosen in [44] is to consider SLn2 ·detn and SLm2 ·permm because 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 irreducible SLn2 -module
appearing in C[SLn2 · detn ] must also appear in the graded SLn2 -module C[GLn2 · [detn ]]δ forsome degree δ. Regarding the permanent, for n > m, SLn2 · ℓn−m permm is not closed, so they
develop machinery to transport information about C[SLm2 · permm ] to C[GLn2 · [ℓn−m permm ]],in particular they introduce a notion of partial stability.
We make a close study of how one can exploit partial stability to determine the GLn2 -module
decomposition of C[GLn2 · ℓn−m permm ] in §5. We also discuss a more elementary approach to
studying which modules in C[GLn2 · ℓn−m permm ] could appear in C[GLn2 · ℓn−m permm ]δ foreach δ. One could get more information from the elementary approach if one could solve theextension problem of determining which functions on the orbit GLn2 · ℓn−m permm extend to theorbit closure GLn2 · ℓn−m permm . In general the extension problem is very difficult, we discuss
it in §7.
We express the restrictions on modules appearing in C[GLn2 · ℓn−m permm ] that we do have , aswell as our information regarding C[GLn2 · detn ], in terms of Kronecker coefficients, culminatingin 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 regardingthese coefficients that we are aware of in §8. Unfortunately, from this information, we are
currently unable to see how one could prove Conjecture 1.2 in the case c = 1 (which is straightforward by other means), let alone for all c. Nevertheless, we have found the GCT program abeautiful 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 closureof another, and [6], where a conjecture of Mulmuley regarding Kronecker coefficients is disprovenand, in an appendix by Mulmuley, a modified conjecture is proposed.
Acknowledgments. It is a pleasure to thank Shrawan Kumar for very useful discussions. This
paper is an outgrowth of the AIM workshop Geometry and representation theory of tensors forcomputer science, statistics and other areas July 21-25, 2008, and authors gratefully thank AIM
and the other participants of the workshop.

GCT APPROACH TO VP 6= VNP

3

2. Overview
We begin, in §3, by establishing notation and reviewing basic facts from representation theory
that we use throughout. In §4 we discuss coordinate rings of orbits and orbit closures. In §5 we
make a detailed study of the cases at hand. While [44] is primarily concerned with SLn2 · detn
and a corresponding closed orbit related to the permanent, we also study the coordinate ringsof the orbits of the general linear group GLn2 . The GLn2 -orbits have the disadvantage of not
being closed in general, so one must deal with the extension problem, which we discuss in §7, butthey have the advantage of having a graded coordinate ring. The orbit SLn2 · ℓn−m permm is not
closed, but the smaller group SLm2 ⊂ SLn2 has the property that SLm2 · ℓn−m permm is closed,
and the modules appearing in GLn2 · ℓn−m permm (ignoring multiplicities) are “inherited” frommodules in the coordinate ring of SLm2 · ℓn−m permm , in a manner described precisely in §4.5,
where we discuss the notion of partial stability.
One goal of [44] is to reduce the conjecture VP 6= VNP (more specifically, VPws 6= VNP– see §9) to a conjecture in representation theory. We explicitly state the conjecture in representation 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 calculationsin [44]), imply Theorem 5.7.1. We also give an overview of their proofs. The consequencesof partial stability can be viewed from the perspective of the collapsing method for computing
coordinate rings (and syzygies), which we discuss in §6.2. In the studies of the coordinate ringsof C[GLn2 · [ℓn−m permm ]] and C[GLn2 · [detn ]], and the resulting conjecture in representation
theory mentioned above, Kronecker coefficients play a central role. We discuss what is known
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 conjecture VP 6= 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 classes VPws 6= VNP.
3. Notation and Preliminaries
Throughout we work over the complex numbers C. Let V be a complex vector space, let
GL(V ) denote the general linear group of V , let v ∈ V and let G ⊆ GL(V ) be a subgroup. We
let G · v ⊂ V denote the orbit of v, G · v ⊂ V its Zariski closure, and G(v) ⊂ G the stabilizer ofv, so G · v ≃ G/G(v). Write C[G · v] (respectively C[G · v]) for the ring of regular functions on
G · v (resp. G · v). By restriction, there is a surjective map Sym(V ∗ ) → C[G · v].
It will be convenient to switch back and forth between vector spaces and projective spaces.
PV denotes the space of lines through the origin in V . If v ∈ V is nonzero, let [v] ∈ PV denotethe corresponding point in projective space, and if x ∈ PV , let x̂ ⊂ V denote the corresponding
line. A linear action of G on V induces an action of G on PV , let G([v]) denote the stabilizer of[v] ∈ PV . If Z ⊂ PV is a subset, let Ẑ ⊂ V denote the corresponding cone in V .
We will be concerned with the space of homogeneous polynomials of degree n in n2 variables,
V = S n (Mat∗n×n ) = S n W . Here Matn×n denotes the space of n × n-matrices, S n W the spaceof homogeneous polynomials of degree n on W ∗ , and G = GL(W ). Our main points of interest
will be x = [detn ] and x = [ℓn−m permm ], where detn ∈ S n (Mat∗n×n ) is the determinant ofan n × n matrix, permm ∈ S m (Mat∗m×m ) is the permanent, we have made a linear inclusion
Matm×m ⊂ Matn×n , and ℓ is a linear form on Matn×n annihilating the image of Matm×m .
For a reductive group G, the set of dominant integral weights Λ+
G indexes the irreducible (finite,Vdimensional) G-modules (see, e.g., [16, 25]), and for λ ∈ Λ+
λ (G) denotes the irreducible GG
module with highest weight λ, and if G is understood, we just write Vλ . If H ⊂ G is a subgroup,
and V a G-module, let V H := {v ∈ V | h·v = v ∀h ∈ H} denote the space of H-invariant vectors.

4

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

For a G-module V , let mult(Vλ (G), V ) denote the multiplicity of the irreducible representation
Vλ (G) in V .
The weight lattice ΛGLM of GLM is ZM and the dominant integral weights Λ+
GLM can be
identified with the M -tuples (π1 , ..., πM ) with π1 ≥ π2 ≥ · · · ≥ πM . For future reference, we
note(3.0.1)V(π1 ,...,πM ) (GLM )∗ = V(−πM ,...,−π1) (GLM ).

The polynomial irreducible representations of GLM are the Schur modules Sπ CM , indexed bypartitions π = (π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 someredundancies since Sπ CM ⊗ (detCM ) ⊗ k = Sπ+(k,...,k)CM . To avoid them, we consider themodules Sπ CM ⊗ (detCM ) ⊗ k with k ∈ Z and π = (π1 , ..., πM −1 , 0). Moreover we write ourpartitions as π = (π1 , ..., πN ) with the convention that π1 ≥ · · · ≥ πN > 0, and we let |π| =π1 + · · · + πN and ℓ(π) = N .
The irreducible SLM -modules are obtained by restricting the irreducible GLM -modules, but
beware that this is insensitive to a twist by the determinant. The weight lattice of ΛSLM of
SLM is ZM −1 and the dominant integral weights Λ+
SLM are the non-negative combinations of
the fundamental weights ω1 , . . . , ωM −1 . A Schur module Sπ CM considered as an SLM -module
has highest weight
λ = λ(π) = (π1 − π2 )ω1 + (π2 − π3 )ω2 + · · · + (πM −1 − πM )ωM −1 .
We write Sπ CM = Vλ(π) (SLM ) or simply Vλ(π) if SLM is clear from the context.
Let π(λ) denote the smallest partition such that the GLM -module Sπ (λ) CM , considered as
PM −1+
an SLM -module, is Vλ . That is, π is a map from Λ+
j=1 λj ωj to
SLM to ΛGLM , mapping λ =M−1Xπ(λ) = (

j=1

λj ,

M
−1
X

λj , ..., λM −1 ).

j=2

4. Stabilizers and coordinate rings of orbits
As mentioned in the introduction, [44] proposes to study the rings of regular functions on
GLn2 · detn and GLn2 · ℓn−m permm by first studying the regular functions on the closed orbits
SLn2 · detn and SLm2 · ℓn−m permm . In this section we review facts about the coordinate ringof a homogeneous space and stability of orbits, record observations in [44] comparing closed
SL(W )-orbits and GL(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, G will denote a reductive group and V a
G-module.
4.1. Coordinate rings of homogeneous spaces. The coordinate ring of a reductive group
G has a left-right decomposition, as a (G − G)-bimodule,M(4.1.1)
C[G] =
Vλ∗ ⊗ Vλ ,λ∈Λ+Gwhere Vλ denotes the irreducible G-module of highest weight λ.

GCT APPROACH TO VP 6= VNP

5Let H ⊂ G be a closed subgroup. The coordinate ring of the homogeneous space G/H isobtained by taking (right) H-invariants in (4.1.1) giving rise to the (left) G-module decomposition
M
M
H(4.1.2)
C[G/H] = C[G]H =Vλ∗ ⊗ VλH =(Vλ∗ ) ⊕ dim Vλ .
λ∈Λ+
G

λ∈Λ+
G

The second equality holds because VλH is a trivial (left) G-module. See [27, Thm. 3, Ch. II, §3],or [48, §7.3] for an exposition of these facts.
4.2. Orbits with reductive stabilizers. Let G be a reductive group, let V be an irreducible
G-module, and let v ∈ V be such that its stabilizer G(v) is reductive. Then G · v = G/G(v) ⊂ V
is an affine variety ([35] Corollary p. 206). This implies that the boundary of G · v is empty or
has pure codimension one in G · v.
4.3. Stability. Following Kempf [23], a non-zero vector v ∈ V is said to be G-stable if the orbit
G · v is closed. We then also say that [v] ∈ PV is G-stable. If V = S d W for dim W > 3, d > 3
and v ∈ V is generic, then by [46] its stabilizer is finite, and by [27, II 4.3.D, Th. 6 p. 142], this
implies that v is stable with respect to the SL(W )-action.
Kempf’s criterion [23, Cor. 5.1] states that if G does not contain a non-trivial central oneparameter subgroup, and the stabilizer G([v]) is not contained in any proper parabolic subgroupof G, then v is G-stable. We will apply Kempf’s criterion to the determinant in §5.2 and to thepermanent in §5.5.
If v is G-stable, then of course C[G · v] = C[G · v]. The former is an intrinsic object withthe above representation-theoretic description, while the latter is the quotient of the space of all
polynomials on V by those vanishing on G · v.
4.4. GL(W ) v.s. SL(W ) orbits. Let V be a GL(W )-module and let v ∈ V be nonzero. Supposethat the homotheties in GL(W ) act non-trivially on v. Then the orbit GL(W ) · v is never stable,
as it contains the origin in its closure.
Assume that v is SL(W )-stable, so C[SL(W ) · v] = C[SL(W ) · v] can be described using(4.1.2). Unfortunately the ring C[SL(W ) · v] is not graded. However GL(W ) · v is a cone over
SL(W ) · v with vertex the origin. The coordinate ring of GL(W ) · v is equipped with a grading
because GL(W ) · v is 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 map Sym(V ∗ ) = C[V ] → C[GL(W ) · v], given by restriction ofpolynomial functions, and this map respects the grading.
Consider the restriction map C[GL(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, because SL(W ) · v is a closed subvariety of GL(W ) · v, restriction of functions
yields a surjective map C[GL(W ) · v] → C[SL(W ) · v]. Both C[GL(W ) · v]δ , C[SL(W ) · v] are
SL(W )-modules (as GL(W ) · v is also an SL(W )-variety), and the map between them is an
SL(W )-module map because the SL(W )-action on functions commutes with restriction.
Summing over all δ yields a surjective SL(W )-module map
M
C[GL(W ) · v]δ → C[SL(W ) · v],
δthat is injective in each degree δ. We have the following consequence observed in [44]:Proposition 4.4.1. Let V be a GL(W )-module and let v ∈ V be SL(W )-stable. An irreducible
SL(W )-module appears in C[SL(W ) · v] iff it appears in C[GL(W ) · v]δ for some δ.

6

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

In contrast to the case of SL(W ), if an irreducible module occurring in C[GL(W ) · v] also
occurs in C[GL(W ) · v] ⊂ Sym(V ∗ ), we can recover the degree it appears in. Consider the case
V = S d W , then a GL(W )-module Sπ W can only occur in C[GL(W ) · v] if |π| = δd for some δand in that case it can only appear in C[GL(W ) · v]δ ⊂ S δ (S d W ∗ ) ⊂ Sym(S d W ∗ ) (see Example
5.1 below).
4.5. Partial stability and an application. Let V be a GL(W )-module. Let v, w ∈ V be
SL(W )-stable points. Equation (4.1.2) and Proposition 4.4.1 imply the following observation:w∈/ GL(W ) · v (equivalently GL(W ) · w 6⊂ GL(W ) · v) if there is an SL(W )-module that contains a SL(W )(w)-invariant that does not contain a SL(W )(v)-invariant. As discussed below,
detn is SL(W )-stable, and while ℓn−m permm is not SL(W )-stable, it is what is called partiallystable in [44], which allows one to attempt to search for such modules as we now describe.
Definition 4.5.1. [44] Let G be a reductive group and let V be a G-module. Let P = KU be
a Levi decomposition of a parabolic subgroup of G. Let R be a reductive subgroup of K. We
say that [v] ∈ PV is (R, P )-stable if it satisfies the two conditions(1) U ⊂ G([v]) ⊂ P .
(2) v is stable under the restricted action of R, that is R · v is closed.
Example 4.5.2. If x ∈ S d W ′ is a generic element and W ′ ( W is a linear inclusion, then x is
not SL(W )-stable, but it is (SL(W ′ ), P ) stable for P the parabolic subgroup of SL(W ) fixing
the subspace W ′ ⊂ W . This follows from §4.3, assuming dim W ′ > 3 and d > 3.
Example 4.5.3. Let W = A ⊕ A′ ⊕ B, A = E ⊗ F ≃ M atm×m , dim A′ = 1, and G = SL(W ).
Let ℓ ∈ A′ such that ℓ 6= 0. It follows from §4.3 that ℓn−m permm ∈ S n M at∗n×n is (R, P )-stablefor R = SL(A) and P the parabolic subgroup of G = GL(W ) preserving A ⊕ A′ , whose Levifactor is K = (GL(A ⊕ A′ ) × GL(B)).
The point of partial stability is that, since the point v is assumed to be R-stable, the problem
of determining the multiplicities of the irreducible modules Vν (R) in C[R. v] is reduced to the
problem of determining the dimension of Vν (R)R(v) . In the case R = K, these are also themultiplicities of the corresponding irreducible representations in the coordinate ring C[G. v].
We will now state a central result of [44] (Theorem 6.1.5 below) in the special case that will
be applied to ℓn−m permm . We first need to recall the classical Pieri formula (see, e.g., [59],Proposition 2.3.1 for a proof):
Proposition 4.5.4. For dim A′ = 1, one has the GL(A) × GL(A′ )-module decomposition
M′
Sπ (A ⊕ A′ ) =Sπ′ A ⊗ S |π|−|π | A′ ,π7→π ′

where the notation π 7→ π ′ means that π1 ≥ π1′ ≥ π2 ≥ π2′ ≥ · · · ≥ 0.
Theorem 4.5.5. Let W = A ⊕ A′ ⊕ B, dim A = a, dim A′ = 1, z ∈ S d−s A, ℓ ∈ A′ \ {0}.
Assume z is SL(A)-stable. Write v = ℓs z. Set R = SL(A), and take P to be the parabolic of
GL(W ) preserving A ⊕ A′ , so K = GL(A ⊕ A′ ) × GL(B), and z is (R, P )-stable.
(1) A module Sν W ∗ occurs in C[GL(W ) · v]δ iff Sν (A ⊕ A′ )∗ occurs in C[GL(A ⊕ A′ ) · v]δ .
There is then a partition ν ′ such that ν 7→ ν ′ and Vλ(ν ′ ) (SL(A)) ⊂ C[SL(A) · [v]]δ .
(2) Conversely, if Vλ (SL(A)) ⊂ C[SL(A) · [v]]δ , then there exist partitions π, π ′ such that
Sπ W ∗ ⊂ C[GL(W ) · [v]]δ , π 7→ π ′ and λ(π ′ ) = λ.
(3) A module Vλ (SL(A)) occurs in C[SL(A) · [v]] iff it occurs in C[SL(A) · v].

GCT APPROACH TO VP 6= VNP

7This is a special case of Theorem 6.1.4. It establishes a connection between C[GL(W ) · v],
which we are primarily interested in but we cannot compute, and C[SL(A)·v], which in principle
can be described using (4.1.2).
We will specialize Theorem 4.5.5 to the case z = permm and study the precise conditions
to have an SL(A)-module in C[SL(A) · permm ] and the corresponding GL(W )-modules inC[GL(W ) · [ℓn−m permm ]]. These conditions are expressed in terms of certain special Kronecker
coefficients, and we discuss those Kronecker coefficients in §8.
5. Examples
We study several examples of orbit closures in spaces of polynomials leading up to the casesof interest, namely GLn2 · detn , GLn2 · ℓn−m permm , SLn2 · detn and SLm2 · ℓn−m permm . We
also study the coordinate rings of the orbits GLn2 · detn and GLn2 · ℓn−m permm . For these to
be useful, one must deal with an extension problem, but the advantage is that their coordinate
rings come equipped with a grading which, when one passes to the closure, indexes the degree.
In §5.7, we state Theorem 5.7.1 which shows that a variant of Valiant’s conjecture would follow
from proving an explicit conjecture in representation theory.
5.1. Example: Let W = Cn and x ∈ S d W generic. We describe the module structure ofC[GL(W ) · x] and C[SL(W ) · x] using (4.1.2). If x ∈ S d W is generic and d, n > 3, thenGL(W )(x) = {λId : λd = 1} ≃ Zd , hence GL(W ) · x ≃ GL(W )/Zd , where Zd acts as multiplication by the d-th roots of unity, see [46]. (Note that if x ∈ S d W is any element, Zd ⊂ GL(W )(x),and thus the calculation here will be useful for other cases.)
We determine the Zd -invariants in GL(W )-modules. Since Sπ W is a submodule of W ⊗|π|,ω ∈ Zd acts on Sπ W ⊗ (detW )−s by the scalar ω |π|−ns. By (4.1.2), we conclude the following
equality of GL(W )-modules:
M
C[GL(W ) · x] =(Sπ W ∗ ) ⊕ dim Sπ W ⊗ (detW ∗ )−s .
(π,s) | d||π|−nsNote that S δ (S d W ∗ ) does not contain any negative powers of the determinant, so when wepass to C[GL(W ) · x] = ⊕ δ S δ (S d W ∗ )/Iδ (GL(W ) · x) we must loose all terms with s > 0, i.e.,
we have the inclusion of GL(W )-modules
M(Sπ W ∗ ) ⊕ dim Sπ W .
C[GL(W ) · x] ⊆π | d||π|Note also that in S δ (S d W ) in general there are far fewer modules and multiplicities than on theright hand side of the same degree, which illustrates the limitation of this information.
Note also that this inclusion respects degree in the graded module C[GL(W ) · x]:
M(Sπ W ∗ ) ⊕ dim Sπ W .
(5.1.1)
C[GL(W ) · x]δ ⊆π | |π|=δdThis property still holds for any x ∈ S d W , proving the assertion in the last paragraph of §4.4.
Regarding SL(W ), note that SL(W )(x) = GL(W )(x) ∩ SL(W ) = Zc , where c = gcd(d, n).
Thus (4.1.2) implies,M(5.1.2)
C[SL(W ) · x] = C[SL(W ) · x] =(Vλ∗ ) ⊕ dim Vλ .
λ∈Λ+| c||π (λ)|
SL(W )

8

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

5.2. First Main Example: GL(W ) · detn ⊂ S n W . Write W = E ⊗ F , with E, F = Cn . Recall that GL(E) × GL(F ) includes into GL(E ⊗ F ) via the inclusion of End(E) × End(F ) =(E ∗ ⊗ E) × (F ∗ ⊗ F ) → (E ⊗ F )∗ ⊗ (E ⊗ F ). Write (e, f ) 7→ e ⊗ f , Note that det(e ⊗ f ) =det(e)det(f ). Let S(GL(E) × GL(F )) ⊂ GL(E ⊗ F ) denote the subgroup of the included
GL(E) × GL(F ) with det(e)det(f ) = 1. Then
(5.2.1)

GL(W )(detn ) = S(GL(E) × GL(F )) ⋊ Z2 ,where on a matrix M , the first factor acts as M 7→ eM f , with e ∈ GL(E), f ∈ GL(F ),det(e)det(f ) = 1, and Z2 acts as M 7→ t M . Note that GL(W )(detn ) ⊂ SL(W ). The computation of the stabilizer dates back to Frobenius [15], for indications of modern proofs, see [18]. As
observed in [43], Theorem 4.1, GL(W )(detn ) does not contain any parabolic subgroup so [detn ]is SL(W )-stable by Kempf’s criterion §4.3.
Proposition 5.2.1. Recall the notation for partitions δn = (δ, ..., δ) (δ appears n times).
M M
C[GL(W ) · detn ] =(Sπ W ∗ ) ⊕ kδn ,δn ,π .
(5.2.2)δ≥0 π | |π|=nδ(5.2.3)

C[GL(W ) · detn ]δ ⊆M

(Sπ W ∗ ) ⊕ kδn ,δn ,π .

π | |π|=nδ(5.2.4)

C[SL(W ) · detn ] = C[SL(W ) · detn ] =M(Vλ∗ ) ⊕ kδn ,δn ,π (λ) , δ = |π(λ)|/n.

λ∈Λ+
SL(W )The Kronecker coefficients kπµν occurring above can be defined by the identity
Sπ (E ⊗ F ) = ⊕ µ,ν (Sµ E ⊗ Sν F ) ⊕ kπµν .
See §8, and in particular §8.3 for remarks on Kronecker coefficients of the form kδn ,δn ,π .
Proof. We apply (4.1.2). We first deduce (Sπ (E ⊗ F ))SL(E)×SL(F ) from the previous formula.
To have a trivial SL(E) × SL(F ) action on Sµ E ⊗ Sν F , we need ν = µ = (δn ). In particular,
n divides |π|. But the GL(W )(detn )-invariants are the same as the SL(E) × SL(F )-invariants(i.e., no negative powers of determinants can appear) because on one hand, if one has a factor(detE)p ⊗ (detF )q , one must have p = q e.g., in order to preserve the Z2 -symmetry, but to beinvariant under S(GL(E) × GL(F )) one needs p = −q.

5.3. Example: Suppose W = A ⊕ B, with x ∈ S d A generic. Here and below let a = dim A
and b = dim B > 0. Assume d, a > 3. The stabilizer GL(W )(x) of x in GL(W ) is of the form



ωId ∗
d
GL(W )(x) =
|ω =1
0
∗
where the upper ∗ is an arbitrary a × b matrix, and the lower ∗ is an arbitrary b × b invertible
matrix. Since there is no control over the lower right hand block matrix in GL(W )(x), an
irreducible GL(W )-module Sπ W ⊗ (detW ) ⊗ k can contain non-trivial invariants only if k = 0,
and then these invariants must be contained in Sπ A ⊂ Sπ W . Since GL(W )(x) acts on Sπ A by
homotheties, we conclude that
M
C[GL(W ) · x] =(Sπ W ∗ ) ⊕ dim Sπ A .
π | d||π|, ℓ(π)≤aW ∗ with d||π| and ℓ(π) ≤ a do occur. The elimination of modules

In particular, all modules Sπ
with more than a parts is due to our variety being contained in a subspace variety (defined in§6.3 below), consistent with Proposition 6.3.2.

GCT APPROACH TO VP 6= VNP

9For comparison with what follows, we record the following immediate consequence for all δ:M(5.3.1)
C[GL(W ) · x]δ ⊆(Sπ W ∗ ) ⊕ dim Sπ A .
π | |π|=dδ, ℓ(π)≤aSince x is not SL(W )-stable, we instead use the (SL(A), Pa )-partial stability of x to obtainfurther information. Namely take R = SL(A), K = GL(A) × GL(B), and Pa the parabolicpreserving A. ¿From (5.1.2) we have a description of C[SL(A) · x] in terms of c = gcd(d, a). By
Theorem 4.5.5, for each dominant integral λ of SL(A) such that c divides |π(λ)|, some π with
λ(π) = λ must occur in C[GL(W ) · x], and by (5.1.1) it occurs in C[GL(W ) · x]|π|/d .
5.4. Example: Suppose W = A ⊕ A′ ⊕ B and x = zℓs ∈ S d W , where z ∈ S d−s A is generic, anddim A′ = 1, ℓ ∈ A′ \ {0}. Assume d − s, a > 3. It is straightforward to show that, with respect
to bases adapted to the splitting W = A ⊕ A′ ⊕ B, ψId 0 ∗η ∗ | η s ψ d−s = 1 .
GL(W )(x) =  0


0
0 ∗

Working as above, we first observe that the GL(W )(x)-invariants in Sπ W must be contained in′
Sπ (A ⊕ A′ ). By the Pieri formula 4.5.4, this is the sum of the Sπ′ A ⊗ S |π|−|π | A′ , for π 7→ π ′ . The′′
action of GL(W )(x) on such a factor is by multiplication with ψ |π | η |π|−|π | , hence the conditions
for invariance that |π ′ | = δ(d − s) and |π| = δd for some δ. We conclude that
M
M
C[GL(W ) · x] =(Sπ W ∗ ) ⊕ dim Sπ′ A ,δ≥0 |π|=δd, |π ′ |=δ(d−s),π7→π ′(5.4.1)

M

C[GL(W ) · x]δ ⊆(Sπ W ∗ ) ⊕ dim Sπ′ A .

|π|=δd, |π ′ |=δ(d−s),π7→π ′The point x is not SL(W )-stable, but is SL(A)-stable, and thus (R, P )-stable for (R, P ) =(SL(A), Pa+1 ). Theorem 4.5.5 applied to this case says that if Sπ W ∗ ⊂ C[GL(W ) · x]δ thenSπ (A ⊕ A′ )∗ ⊂ C[GL(A ⊕ A′ ) · x]δ and there exists π ′ such that π 7→ π ′ and Vλ(π′ ) (SL(A)) ⊂C[SL(A) · x]. Moreover, by (5.1.2) the latter condition is equivalent to the condition thatc = gcd(d − s, a) divides |π ′ |.
5.5. Example: Suppose W = M atm×m and x = permm . We write W = E ⊗ F , with dim E =dim F = m. Then, by [34], for m > 2 the stabilizer of permm ∈ S m (E ⊗ F ) is
(5.5.1)

GL(W )(permm ) = {g ⊗ h | g ∈ NE , h ∈ NF , det(g)det(h) = 1} ⋊ Z2 ,where NE = TE ⋊ WE is the normalizer of the torus TE (diagonal matrices) in GL(E), WE
denotes the Weyl group of permutation matrices in GL(E), and similarly for F . Here Z2 acts
by sending a matrix to its transpose. (We remark that the stabilizer is apparently not to befound in [36]. A shorter proof of 5.5.1 is given in [4].)Note that the stabilizer is contained in SL(W ). To be able to discuss a torus, we have chosena spanning set of m lines in E (resp. F ). Note that the group preserving this choice of data isexactly NE (resp. NF ). [43, Theorem 4.7] remarks that SL(W )(permm ) is not contained in any
proper parabolic subgroup of SL(W ) so permm is SL(W )-stable by Kempf’s criterion 4.3.
Definition 5.5.1. Define Σpermm ⊂ Λ+
GL 2 to be the set of partitions π such that:m(1) |π| = δm some δ ∈ Z+ ,(2) there exist µ, ν with kµνπ 6= 0 such that Sµ Cm ⊂ S m (S δ Cm ) and Sν Cm ⊂ S m (S δ Cm ).

10

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

For π ∈ Σpermm , define
multπ =

Xkµνπ mult(Sµ Cm , S m (S δ Cm ))mult(Sν Cm , S m (S δ Cm )).

µ,νNote that multπ ≥ 1 for π ∈ Σpermm . Finally let ΣSpermm = π −1 (Σpermm ) ⊂ Λ+
SL 2 .
m

Proposition 5.5.2.
(5.5.2)

C[GL(W ) · permm ] =M(Sπ W ∗ ) ⊕ multπ .

M(Sπ W ∗ ) ⊕ multπ .

π∈Σpermm(5.5.3)

C[GL(W ) · permm ]δ ⊆π∈Σpermm ,|π|=δm

(5.5.4)M

C[SL(W ) · permm ] = C[SL(W ) · permm ] =(Vλ∗ ) ⊕ multπ (λ) .

λ∈ΣS
permm

Proof. Argue as in the proof of Proposition 5.2.1 and apply Corollary 8.4.2.



5.6. Second Main Example. Let W = A ⊕ A′ ⊕ B, A = E ⊗ F ≃ M atm×m , dim A′ = 1,
dim W = n2 , and x = ℓn−m permm , ℓ ∈ A′ . With respect to bases adapted to the splitting
W = A ⊕ A′ ⊕ B, ξGL(W )(permm ) 0 ∗0η ∗ | η n−m ξ m = 1 .
(5.6.1)
GL(W )(x) = 


0
0 ∗
Definition 5.6.1. For n ≥ m, define Σnpermm ⊂ Λ+
GL 2 to be the set of partitions π such that:n(1) |π| = δn some δ ∈ Z+ ,(2) there exists π ′ ∈ Σpermm , such that |π ′ | = δm and π 7→ π ′ .
Moreover, for π ∈ Σnpermm we set
Xmultnπ =multπ′ .
π ′ ∈Σpermm , π7→π ′n|π ′ |=m|π|Proposition 5.5.2 and Example 5.4 show:
Proposition 5.6.2.
C[GL(W ) · ℓn−m permm ] =nM(Sπ W ∗ ) ⊕ multπ ,M(Sπ W ∗ ) ⊕ multπ .

π∈Σn
permm

(5.6.2)

C[GL(W ) · ℓn−m permm ]δ ⊆nπ∈Σnpermm ,
|π|=nδ

Since SL(W ) · ℓn−m permm is not stable, we consider R = SL(A) as in §5.4. (We could haveaugmented R by the semi-simple part of the stabilizer of ℓn−m permm but this would not yield
any new information.)¿From Theorem 4.5.5 we deduce the following result.
Proposition 5.6.3. ℓn−m permm is (SL(A), Pm2 +1 )-partially stable. Thus for all λ ∈ ΣSpermm ,there exist partitions π, π ′ such that λ(π ′ ) = λ, π 7→ π ′ , and Sπ W ∗ ⊂ C[GL(W ) · ℓn−m permm ].

GCT APPROACH TO VP 6= VNP

11

Since in Proposition 5.6.3 we have no information about which degree a module appears in, foreach λ there are an infinite number of π’s that could be associated to it. Thus Proposition 5.6.3
may be difficult to utilize in practice.
Proposition 5.6.3 combined with Theorem 4.5.5 gives an explicit description of the Kronecker
problem that results from [44] regarding the permanent.
5.7. The GCT program. As stated in the introduction, to prove a variant of VP 6= VNP it
would be sufficient to prove Conjecture 1.2, that is, for all c > 0, to find m and an irreducible
GLn2 -module appearing in the coordinate ring C[GLn2 · ℓn−m permm ] for n = mc , but do notappearing in C[GLn2 · detn ].
Theorem 4.5.5 and our calculations above applied to the problem at hand yield:
Theorem 5.7.1. Assume there exists λ ∈ ΣSpermm such that for all partitions π ∈ Σnpermm andπ ′ ∈ Σpermm with |π| = nδ, |π ′ | = mδ, π 7→ π ′ and λ(π ′ ) = λ, the Kronecker coefficient kδn ,δn ,πis zero. Then
GLn2 · ℓn−m permm 6⊂ GLn2 · detn .
Unfortunately, because the relevant Kronecker coefficients are rarely zero, we see no way tofind such λ even when n = m, let alone the conjectured n being a polynomial in m.
6. “Inheritance” theorems and desingularizations
In §6.1 we explain the approach to determine the coordinate ring of an orbit closure outlinedin [44]. In §6.2 we review the geometric method for desingularizing G-varieties by collapsing ahomogeneous vector bundle. We then, in §6.3, §6.4 give two examples of auxiliary varieties thatcan be studied with such desingularizations and are useful for the problems at hand. We discuss
how this perspective can be used to recover Theorems 6.1.4 and 6.1.5 from [44] and to obtainfurther information that might be useful.
6.1. Inheritance theorems appearing in [44]. Let R ⊆ K ⊂ G be as in Definition 4.5.1.
We can choose a maximal torus of G in such a way that its intersections with R and K are
maximal tori in these subgroups. This allows one to identify weights accordingly, i.e., it induces++
restriction maps ΛG ≃ ΛK → ΛR , and we impose that Λ+
G → ΛK → ΛR .
+Definition 6.1.1. We say that ν ∈ Λ+
G lies over µ ∈ ΛR at v and degree δ if

(1) Vµ (R)∗ and Vν (K)∗ occur in C[R. [v]]δ and C[K . [v]]δ respectively,(2) Vµ (R)∗ occurs in Vν (K)∗ considered as an R-module.
We say that a dominant weight ν of G lies over a dominant weight µ of R at v if this happens
for some δ > 0.
Example 6.1.2. (Example 4.5.3 cont’d) Let W = A ⊕ A′ ⊕ B, dim A = a, dim A′ = 1, v = ℓs z
with ℓ ∈ A′ , z ∈ S d−s A such that z is SL(A)-stable, so setting R = SL(A), P the parabolic
subgroup of GL(W ) preserving A ⊕ A′ , v is (R, P )-stable. Suppose that a weight in Λ+
GL(W )+
defined by some partition π, lies over λ ∈ ΛSL(A) .
First, that Sπ W ∗ be contained in C[GL(W ) · v] requires that ℓ(π) ≤ a + 1 (which will also be
justified in §6.3 by the fact that GL(W ) · [v] lies in the subspace variety Sa+1 (W )). Second, thecondition that Vλ (SL(A)) be contained in the restriction of Sπ (A ⊕ A′ )∗ requires that π 7→ π ′for some partition π ′ such that ℓ(π ′ ) ≤ a and λ(π ′ ) = λ. Finally we need Vλ (SL(A)) to occur in
C[SL(A) · [v]]δ . Theorem 6.1.4 below describes when this occurs for some δ.
Definition 6.1.3. [44] Let H ⊂ G be a subgroup. We say that a G-module M is H-admissible
if it contains a non-zero H-invariant. We let M H ⊂ M denote the subspace of H-invariants.
Note that an irreducible G-module is H-admissible iff it appears in C[G/H].

12

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

Theorem 6.1.4 ([44], Theorem 8.1). Let [v] ∈ PV be (R, P )-stable. Then the representation
Vλ (G) occurs in the coordinate ring C[G · [v]] only if λ lies over some R(v)-admissible dominant
weight µ of R. Conversely, for every R(v)-admissible dominant weight µ of R, C[G · [v]] contains
Vλ (G) for some dominant weight λ of G lying over µ at v.
Theorem 6.1.4 is a consequence of the following more precise result.
Theorem 6.1.5 ([44], Theorem 8.2). Let [v] ∈ PV be (R, P )-stable. Let P = KU be a Levi
decomposition of P . Then:(1) A K-module Vλ (K)∗ occurs in C[K . [v]] only if λ is also dominant for G, and for all δmult(Vλ (G)∗ , C[G. [v]]δ ) = mult(Vλ (K)∗ , C[K . [v]]δ ).
(2) There are inequalities
mult(Vλ (G)∗ , H 0 (G. [v], OG. [v] (δ))) ≤ mult(Vλ (K)∗ , H 0 (K . [v], OK . [v] (δ))).
+(3) A K-module Vλ (K)∗ can occur in C[K . [v]]δ only if λ ∈ Λ+
G lies over some µ ∈ ΛR at v
and degree δ. Conversely, for each R-module Vµ (R)∗ occurring in C[R. [v]]δ , there exists
a G-dominant weight λ lying over µ at v and degree δ.
(4) An R-module Vµ (R)∗ occurs in C[R. [v]] if and only if it is R(v)-admissible.

Idea of proof. These statements relate the coordinate rings of the projective orbit closures G · [v],K · [v], R · [v], and of the affine (closed) orbit R · v.
In order to prove (1), one observes that the surjection map
C[G · [v]] ։ C[K · [v]]is not only a K-module map, but also a P -module map where the P -module structure on theright-hand side is obtained by extending the action of K by the trivial action of U . (This relieson the assumption that G([v]) contains U .) Any copy of Vλ (G)∗ in some C[G · [v]]δ maps to a
P -module N which is non-zero, because if all polynomials in a G-module vanish on [v], theymust also vanish on G · [v]. Dualizing, since the action of U on N is trivial, one gets an injection
N ∗ → Vλ (G)U . But Vλ (G)U = Vλ (K), in particular it is irreducible and we conclude that
N = Vλ (K)∗ . This implies (1), and its variant (2) is proved in a similar way.
In order to prove (3), one simply observes that the surjection map
C[K · [v]] ։ C[R · [v]]is non-zero on any irreducible component of C[K · [v]]δ , by the same argument as above. So any
such Vλ (K)∗ contributes to C[R · [v]]δ by some Vµ (R)∗ for weights µ over which λ lies. Conversely
any component of C[R · [v]]δ is obtained that way since the restriction map is surjective.
Finally, (4) is a consequence of the fact that R · v is contained in the cone over R · [v]. Since
they are both closed in V , this yields a surjection
C[R · [v]] ։ C[R · v]
and the same argument as for the proof of Proposition 4.4.1 shows that both sides involve thesame irreducible modules.

We emphasize that (4) gives no information of the degree in which a given irreducible module
may occur in C[R. [v]].
In this paper we do not discuss (2), whose failure to be an equality is related with the failureof the cone over K · [v] to be normal, hence to the type of singularity that occurs at the origin.

GCT APPROACH TO VP 6= VNP

13

There is a connection between the notion of (R, P )-stability and the collapsing method that we
discuss in the next subsections. From the latter perspective it is easy to deduce the relationshipbetween C[K · [v]] and C[G · [v]], although the relationship between these and C[R · [v]] is more
subtle. It is possible to write alternative proofs of Theorems 6.1.4, 6.1.5 using the collapsing
set-up.
The desingularization method could be useful for several reasons. First, it allows one tocalculate the multiplicity of an irreducible G-module Vλ (G) in each graded component of thecoordinate ring of an orbit closure. One could detect that one orbit is not in the closure of theother by comparing these multiplicities. Second, it gives information about the multiplicative
structure of the coordinate ring. If an orbit O1 is in the closure of an orbit O2 then thecoordinate ring C[O1 ] is a quotient of C[O2 ] so every polynomial relation in C[O2 ] still holds in
C[O1 ]. Finally, desingularization gives information about the singularities of an orbit closure,which are important geometric invariants.
6.2. The collapsing method and its connection with partial stability. The following
statement can be extracted from [59, Chapter 5]:
Theorem 6.2.1. Let Y ⊂ PV be a projective variety. Suppose there is a projective variety
B and a vector bundle q : E → B that is a subbundle of a trivial bundle V → B with fiber V ,such that the image of the map PE → PV is Y and PE → Y is a desingularization of Y . Writeη = E ∗ and ξ = (V /E)∗ .
If the sheaf cohomology groups H i (B, S δ η) are all zero for i > 0 and δ > 0, and if the linear
maps H 0 (B, S δ η) ⊗ V ∗ → H 0 (B, S δ+1 η) are surjective for all δ ≥ 0, then(1) Ŷ is normal, with rational singularities.
(2) The coordinate ring C[Ŷ ] satisfies C[Ŷ ]δ ≃ H 0 (B, S δ η).
(3) If moreover Y is a G-variety and the desingularization is G-equivariant, then the identifications above are as G-modules.
Notations as above, assume that v ∈ V is (R, P )-stable. Let W = hK · vi be the smallest
K-submodule of V containing v. Since v is stabilized by U , and U is normalized by K, W is a
P -submodule of V with a trivial U -action. Consider the diagramp

EW := G ×P W −−−−→ G/PqyZW ⊂ V.

where EW is a vector bundle over G/P with fiber W , and ZW := q(EW ) = G. W = G. W . The∗ )). In the case when q is a desingularcoordinate ring of ZW is a subring of H 0 (G/P, Sym(EW0∗ization (i.e., when q is birational), H (G/P, Sym(EW )) is the normalization of the coordinate
ring of ZW .
The orbit closure K · v is a K-stable subset of W , and the method of [59] reduces the calculation of the G-module structure of C[G · v] to the calculation of K-module structure of C[K · v].
6.3. The subspace variety. Let W be a vector space and for a < dim W define
Suba (S d W ) = {f ∈ S d W| ∃ W ′ ⊂ W, dim(W ′ ) = a, f ∈ S d W ′ ⊂ S d W }.

Suba (S d W ) is a closed subvariety of S d W which has a natural desingularization given by the
total space of a vector bundle over the Grassmannian Gr(a, W ), namely GL(W )×P S d Ca = S d S,
where S → Gr(a, W ) is the tautological subspace bundle over the Grassmannian. In other words,
the total space of S d S is{(f, W ′ ) ∈ S d W × G(a, W ) | f ∈ S d W ′ }.

14

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

Using Theorem 6.2.1 one may determine the generators of the ideal I(Suba (S d W )) as follows.
For φ ∈ S d W and δ < d, consider the “flattening ” φδ,d−δ : S δ W ∗ → S d−δ W via the inclusion
S d W ⊂ S δ W ⊗ S d−δ W .
Proposition 6.3.1. ([59], §7.2)(1) The ideal I(Suba (S d W )) is the span of all submodules Sπ W ∗ in Sym(S d W ∗ ) for whichℓ(π) > a.
(2) I(Suba (S d W )) is generated by Λa+1 W ∗ ⊗ Λa+1 (S d−1 W ∗ ), which may be considered as
the span of the (a + 1) × (a + 1) minors of φ1,d−1 .
(3) Suba (S d W ) is normal, Cohen-Macaulay and it has rational singularities.
Proposition 6.3.1 implies:
Proposition 6.3.2. Let W ′ ⊂ W be a subspace of dimension b and let f ∈ S d W ′ . Assume thatthe coordinate ring of the orbit closure GL(W ′ ). f ⊂ S d W ′ has the GL(W ′ )-decomposition
M(Sπ W ′∗ ) ⊕ m(π) .
C[GL(W ′ ). f ] =π,ℓ(π)≤b

Then the coordinate ring of the orbit closure GL(W ). f ⊂ S d W has the GL(W )-decomposition
M(Sπ W ∗ ) ⊕ m(π) .
C[GL(W ). f ] =π,ℓ(π)≤b

Proof. We actually prove a more precise statement about the two ideals. First note that
GL(W ) · f ⊂ Subb (S d W ) so for all partitions π with ℓ(π) > b, and Sπ W ∗ ⊂ Sym(S d W ∗ ),Sπ W ∗ ⊂ I(GL(W ) · f ). So henceforth we consider only partitions π with ℓ(π) ≤ b.
We will show that Sπ W ∗ ⊂ I(GL(W ). f ) iff Sπ W ′∗ ⊂ I(GL(W ′ ). f ) for any partition π withℓ(π) ≤ b. Assume |π| = dδ (this must be the case for π to appear in S δ (S d W )) and ℓ(π) ≤ b.
Some highest weight vector of Sπ W ∗ ⊂ S δ (S d W ∗ ) lies in S δ (S d W ′∗ ). That it vanishes on
GL(W ) · f implies it vanishes on GL(W ′ ) · f because if we choose a splitting W = W ′ ⊕ W ′′ andwrite h ∈ S d W as h = h1 + h2 with h1 ∈ S d W ′ , h2 |S d W ′ = 0, given p ∈ S δ (S d W ′ ∗ ), we havep(h) = p(h1 ), and h ∈ GL(W ) · f iff h1 ∈ GL(W ′ ) · f . Finally, an irreducible G-module vanishes
on a G-variety iff any highest weight vector vanishes on the variety.
Remark 6.3.3. The statements above are the special cases of the first part of Theorem 6.1.5 inthe case when W = W ′ ⊕ W ′′ , and G = GL(W ), K = GL(W ′ ) × GL(W ′′ ).
22

Applying Proposition 6.3.2 to x = ℓn−m permm ∈ S n Cm +1 = W ′ ⊂ W = Cn reduces the
problem of determining C[GL(W ) · ℓn−m permm ] to determining C[GL(W ′ ) · ℓn−m permm ].
6.4. Polynomials divisible by a linear form. Another ingredient in the collapsing approach
to Theorem 6.1.4 is investigating a variety of polynomials divisible by a power of a linear form.
Problem 6.4.1. Let W ′ ⊂ W be a subspace of codimension one. Let ℓ ∈ W \ W ′ . Let
g ∈ S d−s W ′ . Take f = ℓs g ∈ S d W . Compare the decompositions of the coordinate rings of theorbit closures GL(W ′ ). g and GL(W ). f .
A solution to Problem 6.4.1 would reduce the investigation of the orbit of ℓn−m permm to theorbit closure of the permanent itself.
Consider the subvariety
Fs (S d W ) = {f ∈ S d W | f = ℓs g for some ℓ ∈ W, g ∈ S d−s W }.
The variety Fs (S d W ) arises naturally in the GCT program because one is interested in thecoordinate ring of GL(W ) · ℓn−m permm which is contained in Fn−m (S n W ). The description of

GCT APPROACH TO VP 6= VNP

15

the normalization of Fs (S d W ) should be useful because the coordinate ring of Fs (S d W ) is asubring in the coordinate ring of its normalization. This normalization is best understood via acollapsing as follows.
The closed subvariety Fs (S d W ) has a desingularization of the form in Theorem 6.2.1 with
G/P = PW , i.e., P is the parabolic subgroup of GLn stabilizing a subspace of dimension one,and the bundle η = S s S ∗ ⊗ S d−s W ∗ , where S = OPW (−1) is the tautological subbundle over
PW . The higher cohomology of Sym(η) vanishes. Theorem 6.2.1 implies that the normalizationof the coordinate ring of Fs (S d W ) has the decomposition
N or(C[Fs (S d W )])e = S es W ∗ ⊗ S e (S d−s W ∗ ).
This decomposition implies that C[Fs (S d W )] is non-normal because C[Fs (S d W )]1 = S d W ∗ andN or(C[Fs (S d W )])1 = S s W ∗ ⊗ S d−s W ∗ , but on the other hand if X is a normal, affine variety
and f : Y → X is a desingularization, then H 0 (Y, OY ) = H 0 (X, OX ). Thus, to determine
C[Fs (S d W )] one would need to deal with the non-normality of Fs (S d W ). However, in thesituation of the proof of Theorem 6.1.4 it is possible to partially avoid such issues.
7. Orbits and their closures
7.1. Comparing GLn2 · detn and gln2 .detn . In this section we compare the orbit closure
GL(W ) · detn with the orbit GL(W ) · detn and the set End(W ) · detn . The reasons for the
first comparison have been discussed already - the second comparison could be useful for helping to understand the first, and it is also important because Valiant’s conjecture is related toEnd(W ) · detn .
Question 7.1.1. Is it true that GL(W ) · detn = End(W ) · detn ?
We expect the answer to be negative.
7.2. Example: A polynomial P with GL(W ) · P 6= End(W ) · P . An easy example of apolynomial P on W = C2 such that GL(W ) · P 6= End(W ) · P is P = xd + y d , for x and y any
two independent coordinates on W . Then GL(W ) · P is the cone over the secant variety to theVeronese variety vd (PW ). It particular it contains the tangential variety to the Veronese variety,hence the polynomial xd−1 y. But for d ≥ 3 this polynomial does not belong to End(W ) · P ,which is just the union of GL(W ) · P with the Veronese variety.
A method to construct polynomials belonging to GL(W ) · detn but not to End(W ) · detn is
proposed in [43, pp. 508-510]. The idea is to start from a weighted graph G with n (ordered)vertices, with n even. Consider its skew-adjacency matrix MG , the skew-symmetric matrix
whose (i, j)-entry with i < j is a variable yij if there is an edge between the vertices i and j,and zero otherwise. More generally, define MG (t) as before but replacing yij by twij yij , wherewij ∈ Z>0 denotes the weight of the edge ij. Thendet(MG (t)) = [Pfaff MG (t)]2 = t2W hG (y) + higher order terms,
where W is the minimal weight of a perfect matching of G, and hG (y) is a sum of monomials
indexed by pairs of minimal perfect matchings. By construction, the polynomial hG (y) is in
GL(W ) · detn . In general G has a unique minimal perfect matching, so hG (y) is just a monomialwhich belongs to End(W ) · detn . It is conjectured in [43, §4.2] that there exist pathologicalweighted graphs G such that hG (y) does not have a small size formula and does not belong toEnd(W ) · detn .

16

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

7.3. Towards understanding GL(W ) · detn ⊂ S n W . In order to better understand the coordinate ring of GL(W ) · detn , it will be important to answer the following question:
Question 7.3.1. What are the irreducible components of the boundary of GL(W ) · detn ? Arethey GL(W )-orbit closures? Is their generic point in End(W ) · detn ?
In principle GL(W ) · detn can be analyzed as follows. The action of GL(W ) or End(W ) on
detn defines a rational map
ψn : P(End(W )) 99K P(S n W ∗ )given by [u] 7→ [detn ◦ u]. Its indeterminacy locus I(ψn ) is, set theoretically, given by the set ofu such that det(u.X) = 0 for all X ∈ W = M atn×n . Thus
I(ψn ) = {u ∈ End(W ) | Im(u) ⊂ Detn },where Detn ⊂ W denotes the hypersurface of non-invertible matrices. Since Im(u) is a vector
space, this relates the problem of understanding ψn to that of linear subspaces in the determinantal hypersurface (detn = 0) ⊂ P(End(W )), which has already received some attention (seee.g. [13].)
By Hironaka’s theorems [20] one can resolve the indeterminacy locus of ψn by a sequence ofsmooth blow-up’s, and GL(W ) · detn can then be obtained as the image of the resolved map.
Completely resolving the indeterminacies will probably be too difficult, but this approach should
help to answer the preceeding questions.
7.4. Remarks on the extension problem. Let G be reductive, let V be an irreducible Gmodule and let v ∈ V . Consider the closure G · v of the G-orbit G · v ≃ G/G(v). Then theboundary G · v\G · v has finitely many components H1 , . . . HN of codimension at least one in
G · v. If G is connected, each of these components is a G-variety.
Example 7.4.1. The most classical example of all for the extension problem is: C∗ ⊂ C:
C[C∗ ] = C[z, z −1 ] and C[C∗ ] = C[C] = C[z]. Here we can take G = C∗ , v = 1.
Consider the case where the singular locus of G · v has codimension at least two. Then thegeneric point of each codimension one Hi is a smooth point of G · v, so that Hi can be definedaround that point by a regular function hi , uniquely defined up to an invertible function. This
allows one to define a valuation νi on C[G · v], giving the order of the pole of a rational function
along Hi : each regular function f on G · v, considered as a rational function of G · v, can beν (f )
uniquely written at the generic point of Hi as f = ghi i , where g is regular and invertible,and νi (f ) ∈ Z. The valuation νi is G-invariant if Hi is. Since a regular function on G · v has nopoles, we haveC[G · v] ⊂ {f ∈ C[G · v] | ∀i νi (f ) ≥ 0}.
If moreover G · v is normal, then we have equality: if f ∈ C[G · v], is such that νi (f ) ≥ 0 for
all i, then f is regular at the generic point of any codimension one boundary component of G · v,
hence outside a subset of codimension at least two – hence everywhere (see, e.g., [12], Corollary11.4). (Earlier, Kostant ([26] , Proposition 9, p 351) showed that if the boundary of G · v has
codimension at least two in G · v, and G · v is normal, then C[G · v] = C[G · v] ).
We expect this normality condition and the codimension two singularities condition to failin our cases (and it is always difficult to check). Nevertheless, the analysis of codimension one
boundary components of the orbit G · v should be a first step towards the determination ofC[G · v].
Another instance of an extension problem was the problem essentially solved by Demazure for
B-orbits in G/B, where G is semi-simple and B ⊂ G a Borel subgroup. Here the orbits, which

GCT APPROACH TO VP 6= VNP

17

are Schubert cells, are just affine spaces (and thus have very simple coordinate rings) and theclosures are Schubert varieties. For a precise, more general statement, and references, see [28,Theorem 8.2.2]. This result relies on the normality of the Schubert varieties, which, as remarked
above, almost certainly fails for the orbit closures of interest here.
8. Kronecker coefficients
We have seen that we need to understand the Kronecker coefficients kδn ,δn ,π in order tounderstand C[GL(W ) · detn ]. Similarly, in order to understand C[GL(W ) · ℓn−m permm ] we needto understand Kronecker coefficients kπµν where Sµ Cm and Sν Cm are contained in some plethysm
S m (S k Cm ). We first give general facts about computing Kronecker coefficients which tell us themultiplicities of certain modules in the coordinate rings we are interested in. Since keeping trackof the multiplicities in the cases at hand appears to be hopeless, one could try to solve the simpler
question of non-vanishing of Kronecker coefficients (i.e., that a certain module appears at all),so we next discuss conditions where one can determine if Kronecker coefficients are non-zero.
Finally in the last two subsections we specialize to the types of Kronecker coefficients arising inthe study of C[detn ] and C[ℓn−m permm ].
8.1. General facts. A general reference for this section is [29, §I.7]. Let π, µ, ν be three partitions of a number n. The Kronecker coefficient kπµν is the dimension of the space of Sn -invariantsin [π] ⊗ [µ] ⊗ [ν], where recall that [π] is the irreducible Sn -module associated to π. In particularkπµν is symmetric with respect to π, µ, ν. Since the irreducible complex representations of Sn
are all defined over Q, kπµν is also the multiplicity of [π] inside the tensor product [µ] ⊗ [ν].
Write π = (n − |π̄|, π̄). Then kπµν only depends on the triple (π̄, µ̄, ν̄) when n is sufficiently
large, cf. [45]. A more precise statement was obtained in [7]. It implies that if kπµν 6= 0, then|π̄| ≤ |µ̄| + |ν̄|. Moreover, in case of equality, the Kronecker coefficient can be identified with a
Littlewood-Richardson coefficient:kπµν = cπ̄µ̄,ν̄ .
Relation with characters. Kronecker coefficients can be computed from the characters of theirreducible representations of Sn . Let χπ denote the character of [π]. Then (see [29, p. 115])1 X
χπ (w)χµ (w)χν (w).
(8.1.1)kπµν =n!
w∈Sn

The characters of Sn can be computed in many ways. Following the Frobenius character formula,they appear as coefficients of the expansion of Newton symmetric functions pµ in terms of Schurfunctions sπ :Xpµ =χµπ sπ .
πHere χµπ denotes the value of the character χπ on any permutation of cycle type µ. Anotherformula for χµπ is given by the Murnaghan-Nakayama rule, which involves a certain type oftableaux T of shape π and weight µ (that is, numbered in such a way that each integer i appearsµi times). Call T a multiribbon tableau if it is numbered non-decreasingly on each row andcolumn, in such a way that for each i, the set of boxes numbered i forms a ribbon (a connected
set containing no two-by-two square). ThenXχµπ =(−1)h(T ) ,T

where the sum is over all multiribbon tableaux T of shape π and weight µ, and h(T ) is the sumof the heights of the ribbons in T (the height of a ribbon being the number of rows it occupies,
minus one). See e.g. [29, I.7, Ex.5].

18

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

Small length cases. The symmetric group Sn has two one dimensional representations, the trivial
representation [n] and the sign representation [1n ]. One has[n] ⊗ [π] = [π]and[1n ] ⊗ [π] = [π ∗ ],where π ∗ denotes the conjugate partition of π. After these two, the simplest representation of
Sn is the vector representation [n − 1, 1] on n-tuples of complex numbers with sum zero. Its
exterior powers ∧p [n − 1, 1] = [n − p, 1p ] are irreducible. Recently Ballantine and Orellana [1]computed the product of [n − p, p] with [π] under the condition that π1 ≥ 2p − 1 (or π1∗ ≥ 2p − 1).
Schur-Weyl duality. There is a close connection between representations of symmetric groups
and representations of general linear groups, called Schur-Weyl duality [21]. Consider the tensor
power U ⊗n of a complex vector space U . The diagonal action of GL(U ) commutes with the
permutation action of Sn . Schur-Weyl duality is the statement that, as a GL(U ) × Sn -module,M
U ⊗n =Sπ U ⊗ [π].
|π|=nA straightforward consequence is the already stated fact that the Kronecker coefficient kπµν canbe defined as the multiplicity of Sµ V ⊗ Sν W inside Sπ (V ⊗ W ) (at least for V and W of large
enough dimension). In particular, since [n] is the trivial representation, this yields the Cauchy
formulaM
S n (V ⊗ W ) =Sπ V ⊗ Sπ W.
|π|=nUsing the Giambelli formula (which expresses any Schur power in terms of symmetric powers) and the Cauchy formula, it is easy to express any Kronecker coefficients in terms ofLittlewood-Richardson coefficients. If π has length ℓ, write cµα1 ,...,αℓ for the multiplicity of Sµ V
in Sα1 V ⊗ · · · ⊗ Sαℓ V . Then
X
X
(8.1.2)kπµν =
sgn(w)
cµα1 ,...,αℓ cνα1 ,...,αℓ .
w∈Sℓ(α1 ,...,αℓ ),|αi |=πi −i+w(i)8.2. Non-vanishing of Kronecker coefficients.
The semi-group property. A rephrasing of the Schur-Weyl duality yields the decompositionM(Sπ U ⊗ Sµ V ⊗ Sν W )⊕kπµν .
(8.2.1)
Sym(U ⊗ V ⊗ W ) =π,µ,ν

Using the fact that the highest weight vectors in this algebra form a finitely generated subalgebra,
one can deduce (see [11]) that:• Triples of partitions with non-zero Kronecker coefficients form a semi-group; that is, if
kπµν 6= 0 for three partitions π, µ, ν of some integer n, and kπ′ µ′ ν ′ 6= 0 for three partitions
π ′ , µ′ , ν ′ of n′ , thenkπ+π′ ,µ+µ′ ,ν+ν ′ 6= 0.
• If one restricts to triples of partitions of length bounded by some integer ℓ, the corresponding semi-group is finitely generated.
• If kπµν 6= 0, the normalized partitions π̃ = nπ , µ̃ = µn , ν̃ = nν verify the entropy relations(8.2.2)H(π̃) ≤ H(µ̃) + H(ν̃).
P

Here H(π̃) = − i π̃i log(π̃i ) denotes the Shannon entropy [51].
Saturation does not hold for Kronecker coefficients, that is, kN π,N µ,N ν 6= 0 for some N ≥ 2does not imply that kπ,µ,ν 6= 0. For counter-examples, see [6], whose appendix by Mulmuley
contains several conjectures regarding the saturation property.

GCT APPROACH TO VP 6= VNP

19

Linear constraints for vanishing. Consider the set KRON of triples (π̃, µ̃, ν̃), where π, µ, ν arethree partitions of n such that kπµν 6= 0 and π̃ etc. are as above. Let KRONℓ denote theanalogous set with the additional condition that the length of the three partitions be bounded
by ℓ. One can deduce from the previous remarks that KRONℓ is a rational convex polytope (seee.g. [14] and [11]).
What are the equations of the facets of this polytope? A geometric method to produce manysuch facets appears in [32], in terms of embeddings
ϕT : F(V ) × F(W ) ֒→ F(V ⊗ W ).
Here F(V ) (resp. F(W )) denotes the variety of full flags in the vector space V (resp. W ), ofdimension m (resp. n). There is no canonical way to define a flag H in V ⊗ W from a flag F in
V and a flag G in W . In order to do that, one needs to prescribe what Klyachko calls a cubicle:
a numbering T of the boxes (i, j) of a rectangle m × n by integers ℓT (i, j) running from 1 to
mn, increasingly on each line and column. Then one lets
X
Hk = ϕT (F, G)k =Fi ⊗ Gj .
ℓT (i,j)≤k

Klyachko [24] goes one step further by applying results of [2]. To state his result, we need adefinition. Consider two non-increasing sequences a and b of real numbers, of lengths m andn, each of sum zero. Suppose that the real numbers ai + bj are all distinct. Ordering them
defines a sequence a + b of length nm, thus a cubicle T and the associated map ϕT . Recall thatthe integral cohomology ring H ∗ (F(V )) has a natural basis given by the Schubert classes σu ,indexed by permutations u ∈ Sm . For any permutation w ∈ Smn , we can therefore decompose
the pull-back by ϕT of the corresponding Schubert class asX
ϕ∗T σw =cw
uv (a, b)σu ⊗ σv .
u∈Sm
v∈Sn

The coefficients cw
uv (a, b) are non-negative integers. Klyachko’s statement is the following:
Theorem 8.2.1. [24] Suppose ℓ ≥ m, n. Then (π̃, µ̃, ν̃) belongs to KRONℓ if and only ifXXXai π̃u(i) +bj µ̃v(j) ≥(a + b)k ν̃w(k)ijkfor all non-increasing sequences a, b and for all u ∈ Sm , v ∈ Sn , w ∈ Smn such that cw
uv (a, b) 6= 0.
There is a formula for the coefficients cw
uv (a, b) in terms of divided differences operators,
which allows one to make explicit computations in low dimensions. For example one can recover
the description of KRON3 given by M. Franz [14] as the convex hull of 11 explicit points.
Unfortunately there is no general rule for deciding whether cw
uv (a, b) is zero or not. Moreoverthe number of inequalities seems to grow extremely fast with ℓ. Redundancy is also an issue.
Klyachko conjectures that it is enough, as for the Horn problem, to consider inequalities forwhich cw
uv (a, b) = 1. Recent advances by N. Ressayre [49] allow one, in principle, to get acomplete and irredundant list of facets for KRONℓ .
8.3. Case of rectangular partitions.
Stanley’s character formula. Formula (8.1.1) shows that, in order to compute a Kronecker coefficient of type kδn ,δn ,π , it would be useful to have a nice formula for the character χδn . Recall that

20

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

δn denotes the partition whose diagram is a rectangle δ × n (i.e., the partition (δ, ..., δ) = (δn )).
Such a formula is given by Stanley in [54]. Suppose that w is a permutation in Sδn . Then
X(−1)δnδκ(u) (−n)κ(v) ,Qn
i=1
j=1 (i + j − 1) uv=w

χδn (w) = Qδwhere u, v ∈ Sδn and κ(u) denotes the number of cycles in u.

Relations with invariants. Let U, V, W be vector spaces of dimensions ℓ, n, n respectively. Taking
SL(V ) × SL(W )-invariants in Formula (8.2.1) yields
M
A := Sym(U ⊗ V ⊗ W )SL(V )×SL(W ) =(Sπ U )⊕kπ,δn ,δn .
δ,πFor ℓ = 2 it is known that A ≃ Sym(S n U ), [52, Theorem 17 p. 369]. Thus for a partition
π = (a, b) of δn in two parts, kπ,δn ,δn is equal to the multiplicity of Sπ U in S δ (S n U ). This isgiven by Sylvester’s formula (see, e.g., [53, Theorem 3.3.4]):(8.3.1)k(δn−b,b),δn ,δn = P (b; δ × n) − P (b − 1; δ × n),

where P (b; δ × n) denotes the number of partitions of size b inside the rectangle δ × n.
This also follows directly from formula (8.1.2), once we observe that a Littlewood-Richardsonncoefficient cδα,β is non-zero only if α and β are complementary partitions in the rectangle δ × n,
and in that case it equals one (this is a straightforward consequence of the Littlewood-Richardson
rule, and a version of Poincaré duality for Grassmannians).
The same argument yields a formula for the length three case as follows. Let π = (a, b, c)with a + b + c = δn. Denote by ST (a, b; δ × n) the number of semistandard lattice permutation
skew-tableaux whose shape is of the form β/α, for β a partition of size δn − b in the rectangle
δ × n, and α a partition of size a (see [29] for the terminology). Thenkπ,δn ,δn

= ST (a, b; δ × n) − ST (a, b + 1; δ × n) + ST (a + 1, b + 1; δ × n)
−ST (a + 1, b − 1; δ × n) + ST (a + 2, b − 1; δ × n) − ST (a + 2, b; δ × n).

For n = 2, and dim U = 4, the algebra of highest weight vectors in A turns out to bepolynomial, with generators of weight (2), (22), (222) and (1111) [31]. Call a partition even(respectively odd) if all its parts are even (respectively odd). We deduce:
Proposition 8.1. A Kronecker coefficient kπ,(δδ),(δδ) is non-zero if and only if:• either π is an even partition of 2δ, of length at most four,• or π is an odd partition of 2δ, of length exactly four.
In both cases kπ,(δδ),(δδ) = 1.
Constraints. Let [π] be a component of [(δn )] ⊗ [(δn )]. The entropy relations (8.2.2) yieldH(π̃) ≤ 2 log(n).
Denote |π|≤a = π1 + · · · + πa (and similarly |π|≥a , etc...). Then [32, Théorème 3.2] give|π|>ab ≤ δ(n − a)+ + δ(n − b)+where x+ = x if x is positive and zero otherwise. For example |π|≤n ≥ δ.

GCT APPROACH TO VP 6= VNP

21

8.4. A variant of Schur-Weyl duality. By Schur-Weyl duality, the decomposition of the
Schur powers Sπ (V1 ⊗ · · · ⊗ Vm ) into irreducible components, for |π| = ℓ, is equivalent to thedecomposition of tensor products of m irreducible representations of Sℓ . What does happen if
we let V1 = · · · = Vm = V and replace the tensor product V1 ⊗ · · · ⊗ Vm by the m-th symmetricpower of V ?
The following remarkable theorem is proved in [17]. Suppose V has dimension n, and fix abasis of V . This defines an action of Sn on V , and on any Schur power Sµ V . In particular thezero-weight space (Sµ V )0 is an Sn -module, non-trivial if and only if µ is of size nδ for some δ.
Here zero-weight must be understood with respect to a maximal torus in SL(V ).
Theorem 8.4.1. [17] Let dim V = n and let µ be a partition of nδ (so that (Sµ V )0 6= 0).
Suppose that the decomposition of (Sµ V )0 into irreducible Sn -modules is
M(Sµ V )0 =[π]⊕sµ,π .
πThen one has the decomposition of GL(V )-modules
M
Sπ (S δ V ) =(Sµ V )⊕sµ,π .
µIn particular, for δ = 1, i.e., |µ| = n, (Sµ V )0 = [µ].
Corollary 8.4.2. Let µ be a partition of size nδ. The dimension of the space of Sn -invariantsin the zero weight space (Sµ Cn )0 equals the multiplicity of Sµ Cn in the plethysm S n (S δ Cn ).
For δ = 2, because of the formula [29, Ex. 6(a), p. 138], this implies that (Sµ V )0 contains
non-trivial Sn -invariants if and only if µ is even. Unfortunately the decomposition of S n (S δ V )is far from being understood for general δ. Conditions for multiplicities not to vanish have beenobtained in [7] and [33].
Nevertheless, observe that for n = dim V = 2, these multiplicities are given by Sylvester’s
formula (8.3.1). This can be generalized as follows. Consider a finite dimensional GL(V )module M , and let mµ (M ) denote the multiplicity of the weight µ in M . Let Nπ (M ) denotethe multiplicity of Sπ V in the decomposition of M into irreducible components. ThenX
sgn(w)mw(π+ρ)−ρ (M ),(8.4.1)Nπ (M ) =w∈Sn

where we let ρ = (n, . . . , 2, 1). Indeed, the Weyl character formula is equivalent to (8.4.1) when
M is irreducible. By linearity, it must hold for any M . In particular, let M = S n (S δ V ). The
multiplicity mµ (M ) is then equal to the number p(µ; n, δ) of ways of writing the monomial xµ
as a product of n monomials of degree δ. The multiplicity of Sπ V inside S n (S δ V ) is thusX
N (π; n, δ) =sgn(w)p(w(π + ρ) − ρ; n, δ),w∈Snwhich generalizes Sylvester’s formula.
9. Complexity classes
In this section we explain the precise complexity problem studied by the GCT program,namely VPws 6= VNP, and place it in the context of Valiant’s algebraic model of NP-completeness[56, 57]. In particular, we compare this to the conjecture VP 6= VNP, and that the permanent is not a p-projection of the determinant, the latter being equivalent to the conjecture
VPws 6= VNP.
All polynomials considered are over C. A general reference for this section is [8].

22PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

9.1. Models of arithmetic circuits and complexity. An arithmetic circuit is a finite acyclic
directed graph with vertices of in-degree 0 or 2 and exactly one vertex of out-degree 0. Vertices
of in-degree 0 are called inputs and labeled by a constant in C or a variable. The other vertices,of in-degree 2, are labeled by × or + and called computation gates. We define the size of a circuitas the number of its vertices. The depth of the circuit is defined as the maximum length of adirected path in the underlying graph. The polynomial computed by a circuit is easily definedby induction.
If the graph underlying the circuit is a directed tree, i.e., all vertices have out-degree at
most 1, then we call the circuit an expression or formula. The notion of weakly-skew circuits isless restrictive: we require that for each multiplication gate α, at least one of the two vertices
pointing to α is computed by a separate subcircuit Cα . Separate means that the edge connecting
Cα to α is the only edge between a vertex of Cα and the remainder to the circuit. In short,
formulas are circuits where previously computed values cannot be reused, while in weakly-skew
circuits we require that at least one of the two operands of a multiplication gate is computed
just for that gate. We note that the degree of the polynomial computed by a weakly-skew circuit
is bounded by its size. The motivation for weakly skew-circuits is that they exactly characterize
the determinant, as we explain below.
We define the complexity L(f ) of a polynomial f over C as the minimum size of an arithmetic
circuit computing f . Restricting to weakly-skew circuits and formulas, respectively, one defines
the corresponding complexity notions Lws (f ) and Le (f ). Clearly, Le (f ) ≥ Lws (f ) ≥ L(f ). The
quantity Le (f ) is called the formula size of f . It is an important fact [5] that log Le (f ) equals,
up to a constant factor, the minimum depth of an arithmetic circuit computing f .
An algorithm due to Berkowitz [3] for computing the determinant implies Lws (detn ) = O(n5 ).
This algorithm also shows the well-known fact that log(Le (detn )) = O(log2 n). The best known
upper bound L(perm ) = O(m2m ) on the complexity of the permanent is exponential [50].
The complexity class VPe is defined as the set of sequences (fn ) of multivariate polynomials
over C such that Le (fn ) is polynomially bounded in n. The set of sequences (fn ) such that
Lws (fn ) is polynomially bounded in n comprises the complexity class VPws . The class VP isdefined as the the set of sequences (fn ) such that L(fn ) and deg fn are polynomially bounded
in n (it is possible to give a syntactic characterization of VP in terms of multiplicatively disjoint
circuits [30]). Note that VPe ⊆ VPws ⊆ VP. Since Lws (detn ) = O(n5 ), we have (detn ) ∈VPws . It is a major open question whether (detn ) is contained in VPe . This is equivalent to
the question whether detn can be computed by arithmetic circuits of depth O(log n). The best
known upper bound is O(log2 n), see [3].

9.2. Completeness. A polynomial f is called a projection of a polynomial g if f can be obtained
from g by substitution of the variables by variables or constants. A sequence (fn ) is called a pprojection of a sequence (gn ) if there exists a polynomially bounded function t : N → N such that
fn is a projection of gt(n) for all n. We note that each of the previously introduced complexity
classes C is closed under p-projection, i.e., if (fn ) is p-projection of (gn ) and (gn ) ∈ C, then(fn ) ∈ C. A sequence (gn ) is called C-complete iff (gn ) ∈ C and any (fn ) ∈ C is a p-projectionof (gn ).
The determinant has the following important universality property [56, 55, 30]: if Lws (f ) ≤ mthen f is a projection of detm+1 . This implies that the sequence (detn ) of determinants is VPws complete [55]. Therefore, VPe = VPws is equivalent to (detn ) ∈ VPe , the major open question
mentioned before. It is not known whether VPws is different from VP.
We remark that when replacing polynomial upper bounds by quasipolynomial upper boundsc2log n in the definitions of the above three complexity classes, then all these classes coincide.

GCT APPROACH TO VP 6= VNP

23

We assign now to any of the above complexity classes VP? a corresponding “nondeterministic”
complexity class VNP? as follows. A sequence (fn ) of polynomialsP
belongs to VNP? if there
exists a polynomial p and a sequence (gn ) ∈ VP? such that fn (x) = e gn (x, e) for all n, where
the sum is over all e ∈ {0, 1}p(n) . It is a nontrivial fact that the resulting classes are the same:
VNPe = VNPws = VNP, for an intuitive proof see [30]. Clearly VP ⊆ VNP.
Valiant [56] proved the major result that (pern ) is VNP-complete. Thus (pern ) 6∈ VP isequivalent to VP 6= VNP, which is sometimes called Valiant’s hypothesis. This can be seen as
an algebraic version of Cook’s famous P 6= NP hypothesis. There is great empirical evidence that
Valiant’s hypothesis is true: if it were false, then most of the complexity classes considered byresearchers today would collapse [9]. Proving this implication relies on the generalized Riemannhypothesis, but we note that the latter can be omitted when dealing with the constant-freeversions of the complexity classes (where only 0, 1 are allowed as constants instead of any complex
numbers).
It is natural to weaken Valiant’s hypothesis to VPws 6= VNP. In view of the completeness ofthe sequences of determinants and permanents in VPws and VNP, respectively, VPws 6= VNP
is logically equivalent to the claim that (pern ) is not a p-projection of (detn ). The latter is apurely mathematical statement, not involving any notions of computation. This is why somepeople (including ourselves) believe that this offers one of the most promising possibilities toattack the P v.s. NP problem.
9.3. Approximate complexity classes. In [10] it was proposed to study the notion of approximate complexity in Valiant’s framework. There is a natural way to put a topology on
the polynomial ring A := C[X1 , X2 , . . .] as a limit of the Euclidean topologies on the finite
dimensional subspaces {f ∈ C[X1 , . . . , Xn ] | deg f ≤ d} whose union over n, d is A.
Definition 9.3.1. The approximate complexity L(f ) of f ∈ A is defined as the minimum r ∈ Nsuch that f is in the closure of {g ∈ A | L(g) ≤ r}. Replacing here L(g) by Lws (g) we obtain
the approximate complexity L ws (f ).
We remark that the same complexity notions are obtained when using the Zariski topology,
since constructible sets have the same closure with respect to Euclidean and Zariski topology.
For more information on approximate complexity we refer to [10].
We define the complexity class VP ws as the set of sequences (fn ) of complex polynomials
such that L ws (fn ) is polynomially bounded in n. Similarly, one defines the classes VP. Clearly,
VP ws ⊆ VP and both classes are closed under p-projections. It is not known whether or not
VP ws is contained in VNP.
We go now back to the GCT approach of [43], which attempts to show Conjecture 1.1.
Proposition 9.3.2. Conjecture 1.1 is equivalent to (perm ) 6∈ VP ws and equivalent to VNP 6⊆
VP ws .
Before giving the proof we note that Conjecture 1.1 would imply that VPws 6= VNP (butnot a priori VP 6= VNP).
Proof. The second equivalence is a consequence of the VNP completeness of (perm ). To show
the first equivalence suppose first that Conjecture 1.1 is false. Then there exist c ≥ 1 and m0csuch that for all m ≥ m0 , [ℓm −m perm ] is contained in the projective orbit closure GLm2c · [detmc ]
c
2c
2c
c
c
in P(S m Cm ). This implies ℓm −m perm ∈ GLm2c · detmc ⊂ S n Cm . Thus for fixed m ≥ m0 ,cthere exists a sequence (σk ) in GLm2c such that fk := σk ·detmc satisfies limk→∞ fk = ℓm −m perm .
There is a weakly-skew arithmetic circuit for detmc of size polynomial in m. Composing thiscircuit with an arithmetic circuit for matrix vector multiplication that computes the linear′
transformation σk yields a weakly-skew arithmetic circuit for fk of size at most mc , where c′

24

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN

denotes a constant (independent of m, k). (In order to preserve the weak-skewness we mayneed several copies of the circuit computing the linear transformation σk .) Let fk′ denote thepolynomial obtained from fk after substituting ℓ by 1 and leaving the variables of perm un′changed. Then Lws (fk′ ) ≤ Lws (fk ) ≤ mc and limk→∞ fk′ = perm . Hence, by definition, we have′
L ws (perm ) ≤ mc for all m ≥ m0 , which implies (perm ) ∈ VP ws .
To show the other direction suppose that (perm ) ∈ VP ws . Hence there exists c ≥ 1 and m0
such that L ws (perm ) < mc for all m ≥ m0 . Fix m ≥ m0 and put n = mc to ease notation. By
definition, there exists a sequence of forms fk such that limk→∞ fk = perm and Lws (fk ) < n
for all k. The universality of the determinant implies that fk is a projection of detn , say
fk (x) = det(Mk ) where Mk is an n by n matrix whose entries are affine linear forms in thevariables xi . We homogenize now with respect to an additional variable ℓ: i.e., we substitute xi
by xi /ℓ and multiply the result by ℓn . This implies1ℓn−m fk (x) = ℓn fk ( x) = det(Mk′ )ℓwith a matrix Mk′ whose entries are linear forms in xi and ℓ. Since GLn2 is dense in Matn×n ,we conclude that the form ℓn−m fk lies in the closure of GLn2 · detn . As limk→∞ fk = perm , this
implies that ℓn−m perm lies in the closure of detn . This holds for all m ≥ m0 with n = mc , so
Conjecture 1.1 would be false.
Remark 9.3.3. Using the known fact Le (perm ) = O(m2 2m ) from [50], the proof of Proposition 9.3.2 implies that GLn2 · [ℓn−m permm ] ⊂ GLn2 · [detn ] for n = O(m2 2m ).
9.4. Order of approximation. We now discuss whether approximation is actually necessary.
Let R = C[[ǫ]] the ring of formal power series in ǫ and K its quotient field. Substituting ǫ by
0 defines the morphism R → C, r 7→ (r)ǫ=0 which extends to S n RN → S n CN . Note that thegroup GLN (K) operates on the scalar extension S n K N in the natural way.
The following result is due to Hilbert [19]. For a proof we refer to Kraft [27, III.2.3, Lemma 1].
Lemma 9.4.1. Suppose that f lies in the GLN (C)-orbit closure of g ∈ S n CN . Then there exists
σ ∈ GLN (K) such that F := σ · g ∈ S n RN satisfies (F )ǫ=0 = f .
Assume we are in the situation of the lemma. By multiplying with a sufficiently high powerof ǫ, we get R-linear forms y1 , . . . , yN such that
(9.4.1)g(y1 , . . . , yN ) = ǫq f + ǫq+1 F̃

with some q ∈ N and F̃ ∈ S n RN . We then say that f can be approximated with order at most q
along a curve in the orbit of detn .
2

Question 9.4.2. Suppose that f lies in orbit closure of detn in S n Cn . Can the order ofapproximation of f along a curve in the orbit of detn be bounded by a polynomial in n?
In [10, Thm. 5.7] an exponential upper bound on the order of approximation is proven in amore general situation.
We show now that if Question 9.4.2 has an affirmative answer, then approximations can beeliminated in the context of the MS-approach.
Proposition 9.4.3. If Question 9.4.2 has an affirmative answer, then VPws = VP ws .
In the present form, this observation is new, although the proof is similar to the arguments
in [10]. We make some preparations for the proof. A skew arithmetic circuit is an arithmetic
circuit such that for each multiplication gate α at least one of the two vertices pointing to α is an
input vertex. Hence the multiplication is either by a variable or a constant. It is clear that skew
circuits are weakly-skew. Astonishingly, skew circuits are no less powerful than weakly-skew

GCT APPROACH TO VP 6= VNP

25

circuits. For each weakly-skew circuit there exists a skew circuit with at most double size thatcomputes the same polynomial, cf. [22].
Let R = C[[ǫ]] and F ∈ R[X1 , . . . , XN ]. We denote by Lws (F ) the smallest size of a weaklyskew arithmetic circuit computing F from the variables Xi and constants in R. Write F =Pii fi ǫ with fi ∈ C[X1 , . . . , XN ].

Lemma 9.4.4. We have Lws (f0 , . . . , fq ) = O(q 2 Lws (F )) for any q ∈ N.

Proof. SupposePwe have a weakly-skew circuit of size s computing F from the variables andconstants c = i ci ǫi ∈ R. By the previous comment we can assume without loss of generalitythat the circuitPis skew. Let g ∈ R[X1 , . . . , XN ] be an intermediate result of the computation
and write g = i gi ǫi with gi ∈ C[X1 , . . . , XN ]. The idea is to construct an arithmetic circuitthat instead of g computes the coefficients g0 , . . . , gq up to degree q from the variables andthe coefficients c0 , . . . , cq of the constants c. This is achieved by replacing each addition of theoriginal circuit by q + 1 additions of the corresponding coefficients. Each multiplication f = g · hPof the original circuit is replaced by O(q 2 ) arithmetic operations following fk = ki=0 gi · hk−i .
This results in a circuit of size O(sq 2 ). Since the original circuit is assumed to be skew, it is clearthat the new circuit can be realized by a skew circuit as well. (We note that it is not obvious
how to preserve weak-skewness.)Proof. (of Proposition 9.4.3) Suppose that (fm ) ∈ VP ws . Then L ws (fm ) < n with n polynomially bounded in m. Hence fm is in the closure of the set of polynomials g satisfying Lws (g) < n.
By the universality of the determinant, those polynomials g are projections of detn , hence contained in GLn2 · detn . It follows that fm ∈ GLn2 · detn . If Question 9.4.2 has an affirmative
answer, then fm can be approximated with order at most q along a curve in the orbit of detn ,where q is polynomially bounded in n and hence in m. Hence we are in the situation (9.4.1) andhave
F := detn (y1 , . . . , yn2 ) = ǫq fm + ǫq+1 F̃
with R-linear forms y1 , . . . , yn2 in the variables xij and some polynomial F̃ over R in xij . ¿From
this we conclude Lws (F ) = mO(1) . Lemma 9.4.4 tells us that Lws (fm ) = O(q 2 Lws (F )). Sinceq was assumed to be polynomially bounded in m, we conclude that Lws (fm ) is polynomiallybounded in m as well. This implies (fm ) ∈ VPws .

References
1. Cristina M. Ballantine and Rosa C. Orellana, A combinatorial interpretation for the coefficients in the
Kronecker product s(n−p,p) ∗ sλ , Sém. Lothar. Combin. 54A (2005/07), Art. B54Af, 29 pp. (electronic).
MR MR2264933 (2008a:05267)
2. Arkady Berenstein and Reyer Sjamaar, Coadjoint orbits, moment polytopes, and the Hilbert-Mumford criterion, J. Amer. Math. Soc. 13 (2000), no. 2, 433–466 (electronic). MR MR1750957 (2001a:53121)
3. S. Berkowitz, On computing the determinant in small parallel time using a small number of processors,
Information Processing Letters 18 (1984), 147–150.
4. Peter Botta, Linear transformations that preserve the permanent, Proc. Amer. Math. Soc. 18 (1967), 566–569.
MR MR0213376 (35 #4240)
5. R.P. Brent, The complexity of multiprecision arithmetic, Proc. Seminar on Compl. of Comp. Problem Solving,
Brisbane, 1975, pp. 126–165.
6. E Briand, R. Orellana, and M. Rosas, Reduced Kronecker coefficients and counter-examples to Mulmuley’ssaturation conjecture SH, preprint arXiv:0810.3163v1 (2008).
7. Michel Brion, Stable properties of plethysm: on two conjectures of Foulkes, Manuscripta Math. 80 (1993),
no. 4, 347–371. MR MR1243152 (95c:20056)
8. P. Bürgisser, Completeness and reduction in algebraic complexity theory, Algorithms and Computation in
Mathematics, vol. 7, Springer Verlag, 2000.
9.
, Cook’s versus Valiant’s hypothesis, Theoretical Computer Science 235 (2000), 71–88.

26

10.

PETER BÜRGISSER, J.M. LANDSBERG, LAURENT MANIVEL AND JERZY WEYMAN, The complexity of factors of multivariate polynomials, Foundations of Computational Mathematics
4 (2004), 369–396.
11. Matthias Christandl, Aram W. Harrow, and Graeme Mitchison, Nonzero Kronecker coefficients and what theytell us about spectra, Comm. Math. Phys. 270 (2007), no. 3, 575–585. MR MR2276458 (2007k:20029)
12. David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York,
1995, With a view toward algebraic geometry. MR MR1322960 (97a:13001)
13. David Eisenbud and Joe Harris, Vector spaces of matrices of low rank, Adv. in Math. 70 (1988), no. 2,
135–155. MR MR954659 (89j:14010)
14. Matthias Franz, Moment polytopes of projective G-varieties and tensor products of symmetric group representations, J. Lie Theory 12 (2002), no. 2, 539–549. MR MR1923785 (2003j:20077)
15. G. Frobenius, Über die Darstellung der endlichen Gruppen durch lineare Substitutionen, Sitzungsber Deutsch.
Akad. Wiss. Berlin (1897), 994–1015.
16. William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, SpringerVerlag, New York, 1991, A first course, Readings in Mathematics. MR MR1153249 (93a:20069)
17. David A. Gay, Characters of the Weyl group of SU (n) on zero weight spaces and centralizers of permutation
representations, Rocky Mountain J. Math. 6 (1976), no. 3, 449–455. MR MR0414794 (54 #2886)
18. A. È. Guterman and A. V. Mikhalëv, General algebra and linear mappings that preserve matrix invariants,
Fundam. Prikl. Mat. 9 (2003), no. 1, 83–101. MR MR2072621 (2005f:15002)
19. D. Hilbert, Über die vollen Invariantensysteme, Math. Ann. 42 (1893), 313–373.
20. Heisuke Hironaka, Resolution of singularities of an algebraic variety over a field of characteristic zero. I, II,
Ann. of Math. (2) 79 (1964), 109–203; ibid. (2) 79 (1964), 205–326. MR MR0199184 (33 #7333)
21. Roger Howe, Perspectives on invariant theory: Schur duality, multiplicity-free actions and beyond, The Schurlectures (1992) (Tel Aviv), Israel Math. Conf. Proc., vol. 8, Bar-Ilan Univ., Ramat Gan, 1995, pp. 1–182.
MR MR1321638 (96e:13006)
22. E. Kaltofen and P. Koiran, Expressing a fraction of two determinants as a determinant, Proc. ISSAC ’08,
ACM, 2008.
23. George R. Kempf, Instability in invariant theory, Ann. of Math. (2) 108 (1978), no. 2, 299–316. MR MR506989(80c:20057)
24. A. Klyachko, Quantum marginal problem and representations of the symmetric group, preprint arXiv:quantph/0409113v1 (2004).
25. Anthony W. Knapp, Lie groups beyond an introduction, second ed., Progress in Mathematics, vol. 140,
Birkhäuser Boston Inc., Boston, MA, 2002. MR MR1920389 (2003c:22001)
26. Bertram Kostant, Lie group representations on polynomial rings, Amer. J. Math. 85 (1963), 327–404.
MR MR0158024 (28 #1252)
27. Hanspeter Kraft, Geometrische Methoden in der Invariantentheorie, Aspects of Mathematics, D1, Friedr.
Vieweg & Sohn, Braunschweig, 1984. MR MR768181 (86j:14006)
28. Shrawan Kumar, Kac-Moody groups, their flag varieties and representation theory, Progress in Mathematics,
vol. 204, Birkhäuser Boston Inc., Boston, MA, 2002. MR MR1923198 (2003k:22022)
29. I. G. Macdonald, Symmetric functions and Hall polynomials, second ed., Oxford Mathematical Monographs,
The Clarendon Press Oxford University Press, New York, 1995, With contributions by A. Zelevinsky, Oxford
Science Publications. MR MR1354144 (96h:05207)
30. G. Malod and N. Portier, Characterizing Valiant’s algebraic complexity classes, Journal of Complexity 24(2008), 16–38.
31. Laurent Manivel, A note on certain Kronecker coefficients, preprint arXiv:0809.3710v1.
32.
, Applications de Gauss et pléthysme, Ann. Inst. Fourier (Grenoble) 47 (1997), no. 3, 715–773.
MR MR1465785 (98h:20078), Gaussian maps and plethysm, Algebraic geometry (Catania, 1993/Barcelona, 1994), Lecture Notes
33.
in Pure and Appl. Math., vol. 200, Dekker, New York, 1998, pp. 91–117. MR MR1651092 (99h:20070)
34. Marvin Marcus and F. C. May, The permanent function, Canad. J. Math. 14 (1962), 177–189. MR MR0137729(25 #1178)
35. Yozô Matsushima, Espaces homogènes de Stein des groupes de Lie complexes, Nagoya Math. J 16 (1960),
205–218. MR MR0109854 (22 #739)
36. Henryk Minc, Permanents, Encyclopedia of Mathematics and its Applications, vol. 9999, Addison-Wesley
Publishing Co., Reading, Mass., 1978, With a foreword by Marvin Marcus, Encyclopedia of Mathematics andits Applications, Vol. 6. MR MR504978 (80d:15009)
37. Ketan D. Mulmuley, Geometric complexity theory: On canonical bases for the nonstandard quantum groups,
preprint.

GCT APPROACH TO VP 6= VNP

38.

27

, Geometric complexity theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry,, Technical Report TR-2007-04, computer science department, The
University of Chicago, May, 2007.
39.
, Geometric complexity theory VII: Nonstandard quantum group for the plethysm problem, preprint.
40. Ketan D. Mulmuley and H. Narayaran, Geometric complexity theory V: On deciding nonvanishing of a generalized Littlewood-Richardson coefficient, Technical Report TR-2007-05, computer science department, The
University of Chicago, May, 2007.
41. Ketan D. Mulmuley and Milind Sohoni, Geometric complexity theory III: on deciding positivity of LittlewoodRichardson coefficients, preprint cs.ArXiv preprint cs.CC/0501076.
, Geometric complexity theory IV: quantum group for the Kronecker problem, preprint available at UC42.
cs dept. homepage.
43.
, Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput.
31 (2001), no. 2, 496–526 (electronic). MR MR1861288 (2003a:68047), Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties,
44.
SIAM J. Comput. 38 (2008), no. 3, 1175–1206. MR MR2421083
45. F. D. Murnaghan, The Analysis of the Kronecker Product of Irreducible Representations of the SymmetricGroup, Amer. J. Math. 60 (1938), no. 3, 761–784. MR MR1507347
46. A. M. Popov, Irreducible simple linear Lie groups with finite standard subgroups in general position,
Funkcional. Anal. i Priložen. 9 (1975), no. 4, 81–82. MR MR0396847 (53 #707)
47. V. Popov, Two orbits: When is one in the closure of the other?, preprint arXiv:0808.2735v7 (2008).
48. Claudio Procesi, Lie groups, Universitext, Springer, New York, 2007, An approach through invariants andrepresentations. MR MR2265844 (2007j:22016)49. N. Ressayre, Theory and generalized eigenvalue problem, preprint arXiv:0704.2127.
50. Herbert John Ryser, Combinatorial mathematics, The Carus Mathematical Monographs, No. 14, Publishedby The Mathematical Association of America, 1963. MR MR0150048 (27 #51)
51. C. E. Shannon, A mathematical theory of communication, Bell System Tech. J. 27 (1948), 379–423, 623–656.
MR MR0026286 (10,133e)
52. A. Skowroński and J. Weyman, The algebras of semi-invariants of quivers, Transform. Groups 5 (2000), no. 4,
361–402. MR MR1800533 (2001m:16017)
53. T. A. Springer, Invariant theory, Lecture Notes in Mathematics, Vol. 585, Springer-Verlag, Berlin, 1977.
MR MR0447428 (56 #5740)
54. Richard P. Stanley, Irreducible symmetric group characters of rectangular shape, Sém. Lothar. Combin. 50(2003/04), Art. B50d, 11 pp. (electronic). MR MR2049555 (2005e:20020)
55. S. Toda, Classes of arithmetic circuits capturing the complexity of computing the determinant, IEICE Trans.
Inf. Syst. E75-D (1992), 116–124.
56. L.G. Valiant, Completeness classes in algebra, Proc. 11th ACM STOC, 1979, pp. 249–261.
57.
, Reducibility by algebraic projections, Logic and Algorithmic: an International Symposium held inhonor of Ernst Specker, vol. 30, Monogr. No. 30 de l’Enseign. Math., 1982, pp. 365–380.
58. Joachim von zur Gathen, Feasible arithmetic computations: Valiant’s hypothesis, J. Symbolic Comput. 4(1987), no. 2, 137–172. MR MR922386 (89f:68021)
59. Jerzy Weyman, Cohomology of vector bundles and syzygies, Cambridge Tracts in Mathematics, vol. 149,
Cambridge University Press, Cambridge, 2003. MR MR1988690 (2004d:13020)
E-mail address: pbuerg@upb.de,jml@math.tamu.edu,Laurent.Manivel@ujf-grenoble.fr,j.weyman@neu.edu