Séminaire Lotharingien de Combinatoire 75 (2016), Article B75a

PERMANENT VERSUS DETERMINANT, OBSTRUCTIONS, AND KRONECKER COEFFICIENTS^{∗}

PETER BÜRGISSER†

Abstract. We give an introduction to some of the recent ideas that go under the name “geometric complexity theory”. We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.

1. Motivation

The determinant polynomial is defined as

det_{n} := det(X) := ∑_{π∈S_{n}} sgn(π) ∏_{i=1}^{n} x_{iπ(i)},

where x_{ij} are variables over a field K. The determinant derives its importance from the fact that it defines a group homomorphism det: GL_{n}(K) → K^{×} due to

det(X · Y) = det(X) det(Y).

It is highly relevant for computational mathematics that the determinant has an efficient computation. For instance, by using Gaussian elimination, it can be computed with O(n^{3}) arithmetic operations.

The definition of the permanent polynomial looks similarly as for that of the determinant:

per_{n} := per(X) := ∑_{π∈S_{n}} ∏_{i=1}^{n} x_{iπ(i)},

but without the sign changes. The permanent has less symmetries: per(X · Y) = per(X) per(Y) holds if X is a product of a permutation and a diagonal matrix, or if Y is so; but in general, the multiplicativity property is violated. Also, for the permanent, there is no known efficient computation. We do not know whether there is a polynomial time algorithm for computing it. The permanent often shows up in algebraic combinatorics and statistical physics as a generating function in enumeration problems.

2000 Mathematics Subject Classification. 68Q17, 20C30, 05E10, 14L24. Key words and phrases. Permanent versus determinant, geometric complexity theory, orbit closures,

representations, plethysms, Kronecker coefficients, Young tableaux, highest weight vectors.

∗ This is an elaboration of a series of three lectures at the 75th Séminaire Lotharingien de Combinatoire and XX Incontro Italiano di Combinatorica Algebrica in Bertinoro, Italy, September 6–9, 2015.

† Institute of Mathematics, Technische Universität Berlin, pbuerg@math.tu-berlin.de. Partially supported by DFG grant BU 1371/3-2.

In computer science, the permanent is known as a universal (or complete) problem in a class of weighted enumeration problems. One says that the family (per_{n}) of permanents is VNP-complete. This theory was created in 1979 by L. Valiant [59]. See [6, 41] for more information.

Proving that computing per_{n} requires superpolynomially many arithmetic operations in n is considered the holy grail of algebraic complexity theory. This essentially amounts to proving the separation VP ≠ VNP of complexity classes. This separation is an “easier” variant of the famous P ≠ NP problem.

2. Determinantal complexity

Note that per [\begin{matrix}a & b \\ c & d \end{matrix}] = det [\begin{matrix}a & −b \\ c & d \end{matrix}]. Pólya [52] asked in 1913 whether such a formula is

also possible for n ≥ 3, i.e., whether there is a sign matrix [ϵ_{ij}] such that per_{n} = det[ϵ_{ij}x_{ij}]. This was disproved by Szegő [58] in the same year. Marcus and Minc [44] strengthened this result by showing that there is no matrix [f_{pq}] of linear forms f_{pq} in the variables x_{ij} such that per_{n} = det[f_{pq}].

But what happens if we allow for the determinant a larger matrix?

We can express per_{3} as the determinant of a matrix of size 7, whose entries are constants or variables, cf. [27]:

per_{3} = det [\begin{matrix}0 & 0 & 0 & 0 & x_{33} & x_{32} & x_{31} \\ x_{11} & 1 & 0 & 0 & 0 & 0 & 0 \\ x_{12} & 0 & 1 & 0 & 0 & 0 & 0 \\ x_{13} & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & x_{22} & x_{21} & 0 & 1 & 0 & 0 \\ 0 & x_{23} & 0 & x_{21} & 0 & 1 & 0 \\ 0 & 0 & x_{23} & x_{22} & 0 & 0 & 1 \end{matrix}] .

Definition 2.1. The determinantal complexity dc(f) of a polynomial f ∈ K[x_{1}, …, x_{N}] is the smallest s such that there exists a square matrix A of size s, whose entries are affine linear functions of x_{1}, …, x_{N}, such that f = det(A). Moreover, we write dc(m) := dc(per_{m}).

We clearly have dc(2) = 2. By the above formula, dc(3) ≤ 7. Recent work showed the optimality: dc(3) = 7; cf. [30, 2].

2.1. An upper bound. The following nice upper bound is due to Grenet [27], based on ideas in Valiant [59].

Theorem 2.2 (Grenet). We have dc(m) ≤ 2^{m} − 1.

Proof. 1. We first give the determinant of a matrix A of size m a combinatorial interpretation. We consider the complete directed graph with the node set [m] := {1, 2, … m} and the edges (i, j) carrying the weight a_{ij}. Moreover, we interpret a permutation π of [m] as the collection of their disjoint cycles (including loops for the fixed points) and call this a cycle cover c of the digraph. We write sgn(c) := sgn(π). The weight of c is defined as the product of the weights of the edges occurring in c.

Then we see that det(A) equals the sum of the signed weights over all cycle covers of the digraph:

det(A) = ∑_{c} sgn(c) weight(c).

2. We build now a digraph P_{m} (see Figure 1). Its node set is the power set 2^{[m]} of [m]. For each S ∈ 2^{[m]} of size i − 1, where 1 ≤ i ≤ m, and j ∈ [m] \ S, we form a directed edge from S to S ∪ {j} of weight x_{ij}. It is easy to see that

per_{m}(X) = ∑_{π} weight(π),

where the sum is over all directed paths π going from ∅ to [m]. (We define the weight of π as the product of the weights of its edges.)

We perform some modifications in this graph: we add loops of weight one at all nodes S ∈ 2^{[m]} different from ∅ and [m], and we identify the node ∅ with the node [m]. Let A denote the weighted adjacency matrix of the resulting digraph. Its size is 2^{m} − 1.

Then it is easy to see that we obtain a weight preserving bijection between the set of directed paths π between ∅ and [m] in the original digraph and the set of cycle covers c_{π} in the modified digraph. We obtain

(−1)^{m−1} per_{m}(X) = ∑_{π}(−1)^{m−1} weight(π) = ∑_{c} sgn(c) weight(c),

which shows that indeed dc(m) ≤ 2^{m} − 1. □

Landsberg and Ressayre [37] recently proved that the representation per_{m} = det(A) in the proof of Theorem 2.2 is optimal among all representations respecting “half of the symmetries” of per_{m}.

2.2. A lower bound. The following result due to Mignon and Ressayre [45] is the best known lower bound for dc(m), except for a recent improvement over K = ℝ due to Yabe [63], which states (m − 1)^{2} + 1 ≤ dc(m).

Theorem 2.3 (Mignon and Ressayre). We have m^{2}/2 ≤ dc(m) if charK = 0.

Proof. The idea is to consider the Hessian H_{f} of a polynomial f ∈ K[x_{1}, …, x_{N}]:

H_{f} := [\frac{∂^{2}f}{∂x_{α}∂x_{β}} ]_{1≤α,β≤N} .

We note that \frac{∂^{2} det_{n}}{∂x_{ij}∂x_{kℓ}} equals the minor of X obtained by deleting the rows i, j and columns j, ℓ.

The following is straightforward to verify using the chain rule.

Lemma 2.4. If we perform an affine linear transformation on f ∈ K[x_{1}, …, x_{N}], namely,

F (x_{1}, …, x_{M}) := f(L · [ x_{1} ; ⋮ ; x_{M} ] + b), L ∈ K^{N×M}, b ∈ K^{N},

then

H_{F} (x) = L^{T} H_{f}(Lx + b)L.

4 PETER BÜRGISSER

Figure 1. The construction for m = 3. Courtesy of J. Draisma [22].

Now we assume dc(m) ≤ n. This means we have a representation

(2.1)  per_{m}(X) = det(A(X)),

where A(X) is of size n and the entries of A are affine linear in the X-variables. Lemma 2.4 implies

(2.2)  H_{per}(X) = L^{T} H_{det}(A(X))L,

where L ∈ K^{n^{2}×m^{2}} is the matrix of the linear map corresponding to the affine map A.

We substitute in (2.1) the matrix X by some M ∈ K^{m×m} which satisfies per(M) = 0, and we set N := A(M). Then,

0 = per(M) = det(A(M)) = det(N),

so that N is rank deficient. Moreover, (2.2) implies

(2.3)  rank H_{per}(M) ≤ rank H_{det}(N).

The determinant is special in the sense that its Hessian has small rank at rank deficient matrices N.

Lemma 2.5. The rank of H_{det}(N) at a matrix N ∈ K^{n×n} only depends on the rank s of N. If s < n, then

rank H_{det}(N) ≤ 2n.

Proof. (Sketch) det: K^{n×n} → K is an invariant with respect to the action of SL_{n} × SL_{n} on K^{n×n} via (S, T) · N := SNT^{−1}. Using Lemma 2.4 one sees that H_{det} : K^{n×n} → K is an invariant under this action as well. This implies the first assertion.

For the second assertion, take N in normal form (s ones on the diagonal and zeros otherwise) and compute the rank H_{det}(N). □

In contrast, the permanent has the following property.

Lemma 2.6. There exists M ∈ K^{m×m} such that per(M) = 0 and H_{per}(M) has rank m^{2}. (Here we assume charK = 0.)

Proof. (Sketch) One may take

M = [\begin{matrix}1 − m & 1 & ⋯ & 1 \\ 1 & 1 & ⋯ & 1 \\ ⋮ & ⋮ & & ⋮ \\ 1 & 1 & ⋯ & 1 \end{matrix}] ,

which satisfies per(M) = 0. It is elementary, though a bit cumbersome, to verify that H_{per}(M) has full rank. □

Using Lemma 2.5 and Lemma 2.6 in (2.3), we obtain

m^{2} = rank H_{per}(M) ≤ rank H_{det}(N) ≤ 2n

and the assertion follows. □

We remark that [16] has an extension of Theorem 2.3 to positive characteristic.

3. An attempt via algebraic geometry and representation theory

How could we possibly prove better lower bounds on dc(m)?

3.1. The determinant variety Ω_{n}. We assume K = ℂ in the following. We consider Sym^{n} ℂ^{n^{2}} as the space of homogeneous polynomials of degree n in n^{2} variables. The group GL_{n^{2}} acts on Sym^{n} ℂ^{n^{2}} by linear substitution.

Definition 3.1. The orbit GL_{n^{2}} · det_{n} is obtained by applying all possible invertible linear transformations to det_{n}. The orbit closure of det_{n},

Ω_{n} := \overline{GL_{n^{2}} · det_{n}} ⊆ Sym^{n} ℂ^{n^{2}},

is its closure with respect to the Euclidean topology. We call Ω_{n} the determinant variety.

Example 3.2. 1. If n = 2, we have

GL_{4} · det_{2} = {quadratic forms of rank 4}, Ω_{2} := Sym^{2} ℂ^{4}.

2. We have for ϵ → 0

det [\begin{matrix}x_{11} & ϵx_{12} \\ ϵx_{21} & x_{22} \end{matrix}] = x_{11}x_{22} − ϵ^{2}x_{12}x_{21} ⟶ x_{11}x_{22} ∈ Ω_{2} for ϵ → 0.

The latter observation generalizes to any n and hence x_{11} ⋯ x_{nn} ∈ Ω_{n}.

Remark 3.3. For n = 3, the boundary of Ω_{n} has been determined recently [28], but for n = 4 it is already unknown.

The following observation allows to study Ω_{n} with the methods of algebraic geometry.

Theorem 3.4. Ω_{n} is Zariski-closed, i.e., the zero set of a system of polynomial equations.

This is a consequence of a general principle saying that, for any constructible subset of ℂ^{N}, the Zariski closure and the closure with respect to the Euclidean topology coincide, see Mumford [50, §2.C].

We make now the following observation.

Suppose dc(m) ≤ n with m > 2, say per_{m}(X) = det(A(X)), where A(X) is of size n, with affine linear entries in x_{11}, …, x_{mm}. (By Theorem 2.3 we have m < n.) Homogenizing this equation with the additional variable t, we obtain

(3.1)  t^{n−m} per_{m}(X) = t^{n} per_{m} (\frac{1}{t}X) = t^{n} det (A(\frac{1}{t}X)) = det (tA(\frac{1}{t}X)).

The entries of the matrix tA(\frac{1}{t}X) are linear forms in t and the X-variables. We call t^{n−m} per_{m}(X) the padded permanent.

The n^{2} entries of tA(\frac{1}{t}X), arranged as a vector, may be thought of as being obtained by multiplying some matrix L ∈ ℂ^{n^{2}×(m^{2}+1)} with (x_{11}, …, x_{mm}, t)^{T}. Now think of t as being one of the variables in {x_{11}, …, x_{nn}}\{x_{11}, …, x_{mm}}. Then L·(x_{11}, …, x_{mm}, t)^{T} = L′ · (x_{11}, …, x_{nn})^{T}, where L′ is obtained by appending n^{2} − m^{2} − 1 zero columns to L. We thus see that t^{n−m} per_{m}(X) is obtained from det_{n} by the substitution L′. Since GL_{n^{2}} is dense in ℂ^{n×n}, we can approximate L′ arbitrarily closely by invertible matrices and hence we obtain

t^{n−m} per_{m}(X) ∈ Ω_{n}.

Mulmuley and Sohoni [48] proposed to prove that t^{n−m} per_{m}(X) ∉ Ω_{n}, which is stronger than dc(m) > n, but which has the benefit that this problem can be naturally approached by tools from algebraic geometric. In particular, methods from geometric invariant theory can be brought into play.

The basic strategy for proving lower bounds is now to exhibit a polynomial function

R: Sym^{n} ℂ^{n^{2}} → ℂ

that vanishes on Ω_{n}, but not on the padded permanent t^{n−m} per_{m}(X). Theorem 3.4 tells us that this strategy “in principle” must work, but how on earth could we find such a function R?

The idea is to exploit the symmetries. The determinant variety Ω_{n} clearly is invariant under the action of the group GL_{n^{2}} on Sym^{n} ℂ^{n^{2}}. We consider the vanishing ideal

I(Ω_{n}) = {R | R vanishes on Ω_{n}},

which is invariant under the action of GL_{n^{2}}. We bring now the representation theory of GL_{n^{2}} into play and try to understand which types of irreducible GL_{n^{2}}-modules appear in I(Ω_{n}).

3.2. A primer on representation theory. Our treatment here is extremely brief. Basically, we just recall definitions and introduce notations. E.g., see [25] for more information on this classical topic.

It is well-known that the isomorphism types of irreducible (rational) GL_{n^{2}}-modules can be labelled by highest weights, which we can view as λ ∈ ℤ^{n^{2}} such that λ_{1} ≥ ⋯ ≥ λ_{n^{2}}. The Schur–Weyl module V_{λ} = V_{λ}(GL_{n^{2}}) denotes an irreducible GL_{n^{2}}-module of highest weight λ.

If λ_{n^{2}} ≥ 0, then λ is a partition of length ℓ(λ) := #{i | λ_{i} ≠ 0} ≤ n^{2} and size |λ| := ∑_{i} λ_{i}. We briefly write λ ⊢_{n^{2}} |λ| for this.

Example 3.5. 1. If λ = (δ, …, δ) for δ ∈ ℤ, then V_{λ} = ℂ with the operation g · 1 = det(g)^{δ}.

2. If λ = (δ, 0, …, 0) for δ ∈ ℕ, then V_{λ} = Sym^{δ} ℂ^{n^{2}}.

The group GL_{n^{2}} acts on Sym^{d} Sym^{n} ℂ^{n^{2}}, and we are interested in its isotypical decomposition:

(3.2)  Sym^{d} Sym^{n} ℂ^{n^{2}} = ⨁_{λ⊢dn} pleth_{n}(λ)V_{λ}.

The arising multiplicities pleth_{n}(λ) ∈ ℕ are called plethysm coefficients.

Remark 3.6. The decomposition of Sym^{d} Sym^{n} ℂ^{2} describes the invariants and covariants of binary forms of degree n. This was a subject of intense study in the 19th century and famous names like Cayley, Sylvester, Clebsch, Gordan, Hermite, Hilbert, … are associated with it (e.g., see [56, 57]). However, in the above situation of forms of many variables, little is known.

We now go back to the vanishing ideal of Ω_{n} and ask for the isotypical decomposition of the degree d component of its vanishing ideal I(Ω_{n}):

(3.3)  I(Ω_{n})_{d} = ⨁_{λ⊢dn} multdet_{n}(λ)V_{λ}.

Our goal is to get some information about the arising multiplicities multdet_{n}(λ). It will be convenient to say that the elements of the isotypical component multdet_{n}(λ)V_{λ} contain the equations for Ω_{n} of type λ. Representation theory tells us that the equations “come in modules”. The multiplicity multdet_{n}(λ), multiplied by dim V_{λ}, tells us how many linearly independent equations of type λ there are.

In order to say something about multdet_{n}(λ), we recall the following crucial quantity.

Definition 3.7. Let λ_{i} ⊢_{m_{i}} N, i = 1, 2, 3, be three partitions of N with length ℓ(λ_{i}) ≤ m_{i}. Their Kronecker coefficient is defined as the multiplicity of the irreducible GL_{m_{1}} × GL_{m_{2}} × GL_{m_{3}}-module in Sym^{N} (ℂ^{m_{1}} ⊗ ℂ^{m_{2}} ⊗ ℂ^{m_{3}}):

k(λ_{1}, λ_{2}, λ_{3}) := mult (V_{λ_{1}} ⊗ V_{λ_{2}} ⊗ V_{λ_{3}}, Sym^{N} (ℂ^{m_{1}} ⊗ ℂ^{m_{2}} ⊗ ℂ^{m_{3}})).

It is well-known that, by Schur–Weyl duality, there is also an interpretation of Kronecker coefficients in terms of representations of the symmetric group S_{N}: we have

k(λ_{1}, λ_{2}, λ_{3}) = dim ([λ] ⊗ [μ] ⊗ [ν])^{S_{N}} ,

where [λ] denotes an irreducible S_{N}-module of type λ (Specht module).

Unfortunately, despite being fundamental, Kronecker coefficients are not well understood. We believe that they should count some efficiently describable objects, but such a description has so far only be achieved in special cases (notably, if one of the partitions is a hook, cf. [3]). Computer science has developed models to express this question in a rigorous way. We encode partitions as lists of binary encoded integers.

Problem 3.8. Is the function (λ_{1}, λ_{2}, λ_{3}) ↦ k(λ_{1}, λ_{2}, λ_{3}) in the complexity class #P?

We will see that the case where two of the three partitions are equal and of rectangular shape n × d = (d, …, d) (n times), is of special interest to us. We therefore define

(3.4)  k_{n}(λ) := k(λ, n × d, n × d) for λ ⊢ dn.

3.3. Obstructions. The coordinate ring of Ω_{n} consists of the restrictions of polynomial functions to Ω_{n} and can be described as

ℂ[Ω_{n}] := ℂ[ Sym^{n} ℂ^{n^{2}}]/I(Ω_{n}).

The multiplicity of the irreducible GL_{n^{2}}-module V_{λ} in ℂ[Ω_{n}] can be expressed as

(3.5)  k̃_{n}(λ) := pleth_{n}(λ) − multdet_{n}(λ),

which we shall call GCT-coefficients. The following theorem, which is due to Mulmuley & Sohoni [49], shows that k̃_{n}(λ) is upper bounded by the special Kronecker coefficients k_{n}(λ). A refinement of this result can be found in [15].

Theorem 3.9 (Mulmuley and Sohoni). We have k̃_{n}(λ) ≤ k_{n}(λ) for λ ⊢_{n^{2}} dn.

We explain now how we intend to apply this theorem for the purpose of lower bounds. (Currently, this plan could not yet be realized, and we will explain below some of the difficulties encountered with its realization.)

Suppose that k_{n}(λ) = 0. Then Theorem 3.9 implies that multdet_{n}(λ) = pleth_{n}(λ). Looking at the decompositions (3.2) and (3.3), we infer that any polynomial R ∈ Sym^{d} Sym^{n} ℂ^{n^{2}} of type λ vanishes on the determinant variety Ω_{n}. If we are lucky, and additionally, some R of type λ satisfies R(t^{n−m} per_{m}) ≠ 0, then we can conclude that the padded permanent t^{n−m} per_{m} does not lie in Ω_{n} . Therefore the lower bound dc(m) > n would follow.

We call such a partition λ an (occurrence) obstruction proving dc(m) > n.

The nonvanishing condition for R has the following consequences. First of all, we must have pleth_{n}(λ) > 0. Moreover, we have the following constraints on the shape of λ.

Theorem 3.10 (Landsberg and Kadish). If there exists R ∈ Sym^{d} Sym^{n} ℂ^{n^{2}} of type λ ⊢_{n^{2}} dn such that R(t^{n−m}g) ≠ 0 for some form g of degree m in ℓ ≤ n^{2} variables, then ℓ(λ) ≤ ℓ + 1 and λ_{1} ≥ |λ|(1 − m/n).

The first assertion is from [15] and the second is from [33]. We omit the proof.

Hence an obstruction λ has relatively few rows and almost all of its boxes are in its first row. More specifically, in our situation, we have ℓ = m^{2}. Therefore, a hypothetical sequence (λ^{m}) of obstructions certifying at least m^{2}/2 ≤ dc(m) must satisfy ℓ(λ^{m}) ≤ m^{2} + 1 and lim_{m→∞} λ_{1}^{m}/|λ^{m}| = 1.

To further simplify, let us now forget about the nonvanishing of R on the padded permanent and make the following definition.

Definition 3.11. An obstruction for forms of degree n is a partition λ ⊢_{n^{2}} dn, for some d, such that k_{n}(λ) = 0 and pleth_{n}(λ) > 0.

Proposition 3.12. Assume there exists an obstruction λ for forms of degree n with ℓ = ℓ(λ) rows. Then a generic polynomial f ∈ Sym^{n} ℂ^{ℓ} of degree n in ℓ variables satisfies dc(f) > n.

Proof. The assumption pleth_{n}(λ) > 0 implies that there exists some homogeneous polynomial function R: Sym^{n} ℂ^{n^{2}} → ℂ of type λ; cf. (3.2). Moreover, we may assume that the restriction of f to Sym^{n} ℂ^{ℓ} does not vanish. (For this, one needs to know that pleth_{n}(λ) does not change when removing zeros from λ.) By Theorem 3.9, k_{n}(λ) = 0 implies k̃_{n}(λ) = 0 and hence R vanishes on Ω_{n}; cf. (3.2). For a generic f ∈ Sym^{n} ℂ^{ℓ} we have R(f) ≠ 0. Hence f ∉ Ω_{n}, which proves that dc(f) > n. □

Example 3.13 (Ikenmeyer [29]). λ = (13, 13, 2, 2, 2, 2, 2) is an obstruction for forms of degree 3 in 7 variables. Indeed, |λ| = 36 = 12·3, ℓ(λ) = 7 and one can check with computer calculations that pleth_{3}(λ) = 1 and k_{3}(λ) = 0. (We compute Kronecker coefficients with an adaption by J. Hüttenhain of a code originally written by H. Derksen.) In this situation, there is (up to scaling) a unique highest weight function R: Sym^{3} ℂ^{9} → ℂ of degree 12 and type λ. This function R vanishes on Ω_{3}.

Let us point out that the dimension of the “search space” Sym^{12} ℂ^{165} in which R lives is enormous: we have Sym^{3} ℂ^{9} ≃ ℂ^{165} and dim Sym^{12} ℂ^{165} ≈ 1.3·10^{19}. We have found the “needle in a haystack” with the help of representation theory and extensive calculations! It should also be emphasized that it is possible to describe R in a concise way using symmetrizations, cf. [29].

The following is a major open problem!

Problem 3.14. Find families of obstructions for forms with few rows.

3.4. Sketch of proof of Theorem 3.9.

3.4.1. Symmetries of the determinant. The symmetries of det_{n} are captured by the stabilizer group

stab_{n} := {g ∈ GL(ℂ^{n^{2}}) | det(g(X)) = det(X)},

where we interpret in this formula X as a vector of length n^{2}. For A, B ∈ SL_{n} we consider the following linear map given by matrix multiplication:

(3.6)  g_{A,B}: ℂ^{n×n} → ℂ^{n×n}, X ↦ AXB.

We have det(AXB) = det(A) det(X) det(B) = det(X). Hence g_{A,B} ∈ stab_{n}. Are these all elements of the stabilizer group of det_{n}? No, the transposition τ: ℂ^{n×n} → ℂ^{n×n}, X ↦ X^{T} clearly also belongs to stab_{n}.

The following result due to Frobenius [24] in fact states that each element of stab_{n} is of the form g_{A,B} or τg_{A,B}. (This was rediscovered later by Dieudonné [21].) We skip the proof.

Theorem 3.15 (Frobenius). The stabilizer group stab_{n} of det_{n} is generated by τ and the g_{A,B} for A, B ∈ SL_{n}. We have

stab_{n} ≃ (SL_{n} × SL_{n})/μ_{n} ⋊ ℤ_{2},

where μ_{n} := {t id_{n} | t^{n} = 1}.

3.4.2. Multiplicities in the coordinate ring of the orbit of det_{n}. In algebraic geometry, one defines a regular function φ: GL_{n^{2}} · det_{n} → ℂ as a function such that each point of the orbit GL_{n^{2}} · det_{n} has an open neighborhood on which φ can be expressed as the quotient of two rational functions. We denote by ℂ[GL_{n^{2}} · det_{n}] the ring of regular functions on the orbit.

Let us point out that the orbit is a smooth algebraic variety that is well understood in various senses. By going over to the orbit closure Ω_{n}, one adds limit points at the boundary, and we expect the situation to become very complicated. (Compare [38, 11] for some results.)

Clearly, we have the following inclusion of rings of regular functions:

ℂ[Ω_{n}] ⊆ ℂ[ GL_{n^{2}} · det_{n} ].

By comparing multiplicities, it follows that for λ ⊢_{n^{2}} dn,

k̃_{n}(λ) = pleth_{n}(λ) − multdet_{n}(λ) = multiplicity of V_{λ} in ℂ[Ω_{n}]
≤ multiplicity of V_{λ} in ℂ[GL_{n^{2}} · det_{n}]
= dim (V_{λ})^{stab^{n}} (algebraic Peter–Weyl theorem)
≤ k_{n}(λ) (see below).

The Peter–Weyl theorem is a well-known theorem from harmonic analysis, telling us about the irreducible G-modules in the space L^{2}(G, ℂ) of quadratic integrable functions on a compact Lie group G. (If G is finite, this is just the well-known decomposition of the regular representation.) For the second equality above, we used an algebraic version of the Peter–Weyl theorem; cf. [35, Chap. II, Sec. 3, Thm. 3] or [53, Sec. 7.3].

We now justify the last inequality. It is here that Kronecker coefficients enter the game! Schur–Weyl duality implies that, by restricting the GL_{n^{2}}-action of V_{λ}(GL_{n^{2}}) with respect to the homomorphism GL_{n} × GL_{n} → GL_{n^{2}}, (A, B) ↦ A ⊗ B, we obtain

V_{λ}(GL_{n^{2}}) ↓_{GL_{n} × GL_{n}}= ⨁_{μ,ν ⊢_{n}|λ|} k(λ, μ, ν) V_{μ}(GL_{n}) ⊗ V_{ν}(GL_{n}).

We look now for SL_{n} × SL_{n}-invariants. They occur on the right-hand side only if μ = ν = n × d and |λ| = dn. Note that A ⊗ B is just another way of writing g_{A,B}; see (3.6). Using Theorem 3.15, we obtain

dim (V_{λ}(GL_{n^{2}}))^{stab^{n}} ≤ dim V_{λ}(GL_{n^{2}})^{SL_{n} × SL_{n}} = k(λ, n × d, n × d) = k_{n}(λ).

This completes the proof of Theorem 3.9.

3.5. Obstructions must be gaps. We address now the question of how to exhibit obstructions for forms. Example 3.13 was found with extensive calculations. We will see here that, in a certain sense, obstructions are quite rare, or at least hard to find.

Progress on Problem 3.14 is thus imperative. We do not want to hide the fact that we do not know whether there exist enough obstructions for achieving the desired lower bounds on determinantal complexity. In fact, the state of the art is that, so far, no lower bound on dc(m) has been obtained along these lines. However, let us point out that in the related, but simpler situation of border rank of tensors, lower bounds have been proven by exhibiting obstructions; see [13].

We consider the following set of highest weights,

K_{n} := {λ | λ ⊢_{n^{2}} dn for some d and k_{n}(λ) > 0}.

From Definition 3.7 it easily follows that λ, μ ∈ K_{n} implies λ+μ ∈ K_{n}. Moreover, 0 ∈ K_{n}. Hence K_{n} is a monoid. (It follows from general principles that K_{n} is finitely generated; cf. [4].)

Example 3.16. To illustrate the next step, consider the submonoid M := {0, 3, 5, 6, 8, 9, …} of ℕ, which clearly generates the group ℤ. From sx ∈ M, s ≥ 1, we cannot deduce that x ∈ M, due to the presence of the “holes” 1, 2, 4, 7. Filling in these holes, we obtain the monoid ℕ. The holes are usually called the gaps of the monoid M; cf. [54]. In general, one calls the process of filling in the gaps saturation.

In our situation of interest, we make the following definition.

Definition 3.17. The saturation of K_{n} is the set of partitions λ with ℓ(λ) ≤ n^{2} such that |λ| is a multiple of n and there exists a “stretching factor” s ≥ 1 satisfying sλ ∈ K_{n}. The gaps of K_{n} are the elements in the saturation of K_{n} that do not lie in K_{n}.

Remark 3.18. To fully justify the naming “saturation” here, one has to show that the group generated by K_{n} consists of all λ ∈ ℤ^{n^{2}} such that n divides ∑_{i} λ_{i}. (For n ≥ 7 this was shown in [32]; for n = 2 it is false.)

The following result is established in [8].

Theorem 3.19 (B, Christandl, Ikenmeyer). The saturation of the monoid K_{n} equals the set of all partitions λ with ℓ(λ) ≤ n^{2} such that |λ| is a multiple of n.

This result implies that obstructions must be gaps of the monoid K_{n}. The relevance of Theorem 3.19 is that it excludes the use of asymptotic techniques for finding obstructions.

Theorem 3.9 states that k̃_{n}(λ) ≤ k_{n}(λ). However, we only need k̃_{n}(λ) = 0 for implementing our strategy of proving lower bounds. Indeed, the replacement of k̃_{n}(λ) by the Kronecker coefficient k_{n}(λ) corresponds to replacing the coordinate ring of the orbit closure by the larger coordinate ring of the orbit, and this was only done because we better understand the latter.

So one might hope that Theorem 3.19 fails for the smaller multiplicities k̃_{n}. Unfortunately, this does not turn out to be the case. Before stating the next result, we introduce a certain combinatorial conjecture.

A Latin square of size n is map T: [n]^{2} → [n], viewed as an n × n matrix with entries in [n], such that in each row and each column each entry in [n] appears exactly once. So, in each column and row we have a permutation of [n]. The column sign of T is defined as the product of the signs of column permutations. The Latin square T is called column-even if this sign equals one, otherwise T is called column-odd. See Figure 2 for an illustration.

\begin{matrix}− & + & − & − \\ 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{matrix}

Figure 2. A Latin square with column-sign −1.

It is an easy exercise to check that, if n > 1 is odd, then there are as many column-even Latin squares of size n as there are column-odd Latin squares of size n.

The Alon–Tarsi conjecture [1] states that, if n is even, then the number of column-even Latin squares of size n is different from the number of column-odd Latin squares of size n. This conjecture is known to be true if n = p ± 1 where p is a prime, cf. [23, 26].

The following result is due to Kumar [36]. (Note that, in contrast with Theorem 3.19, it only makes a statement about the λ with ℓ(λ) ≤ n.)

Theorem 3.20 (Kumar). If the Alon–Tarsi conjecture holds for n, then for all λ with ℓ(λ) ≤ n such that |λ| is a multiple of n, we have k̃_{n}(nλ) > 0.

In fact, it is possible to obtain an unconditional result at the price of losing the information about the specific stretching factor n. The following result is from [10].

Theorem 3.21 (B, Hüttenhain, Ikenmeyer). For all λ with ℓ(λ) ≤ n such that |λ| is a multiple of n, there exists s ≥ 1 such that k̃_{n}(sλ) > 0.

4. Positivity of Kronecker coefficients

Motivated by the attempt described in the previous section, notable progress was made about understanding when Kronecker coefficients are positive. We report on this in the remainder of this survey.

4.1. Testing positivity is NP-hard. It is known that testing the positivity of Littlewood–Richardson coefficients can be done in polynomial time; cf [47, 40, 12]. Mulmuley conjectured [46] that testing positivity of Kronecker coefficients can be done in polynomial time as well. For fixed m and partitions λ, μ, ν of length at most m this is true, see [18]. However, an exciting recent result [31] shows that, in general, this is not the case. For the following hardness results, we may even assume that the partitions are given as lists of integers encoded in unary. (A positive integer m encoded in unary has size m; thus considering unary encoding makes the problem easier.)

Theorem 4.1 (Ikenmeyer, Mulmuley, Walter). Testing positivity of Kronecker coefficients is an NP-hard problem.

We are going to outline the proof. By a 3D-relation we shall understand a finite subset R of ℕ^{3}. For i ∈ ℕ we set

x_{R}(i) := #{(x, y, z) ∈ R | x = i},

and we call the sequence x_{R} := (x_{R}(0), x_{R}(1), …) the x-marginal of R. We may interpret x_{R} as a partition of |R] if the entries of x_{R} are monotonically decreasing. (There is no harm caused by the fact that the indexing of x_{R} starts with 0.) Similarly, we define the y-marginal y_{R} and the z-marginal z_{R} of R. Note that, if R is contained in the discrete cube {0, …, m − 1}^{3}, then x_{R}, y_{R}, z_{R} have at most m nonzero components. The problem of reconstructing R from its marginals is sometimes called “discrete tomography”.

We call a 3D-relation R a pyramid if (x, y, z) ∈ R implies (x′, y′, z′) ∈ R for all (x′, y′, z′) ∈ ℕ^{3} such that x′ ≤ x, y′ ≤ y, z′ ≤ z. In the literature, one often calls pyramids plane partitions. In fact, they are just the 3D-analogues of Young diagrams.

Let λ′ denote the partition conjugate to λ obtained by a reflection of its Young diagram at the main diagonal.

Definition 4.2. For λ, μ, ν ⊢ d we denote by t(λ, μ, ν) the number of 3D-relations R with x-marginal λ′, y-marginal μ′, and z-marginal ν′. Moreover, let p(λ, μ, ν) denote the number of pyramids R with the marginals λ′, μ′, ν′.

The following result was previously proved by Manivel [43] and rediscovered in [13, 31]; compare also Vallejo [60].

Lemma 4.3. We have p(λ, μ, ν) ≤ k(λ, μ, ν) ≤ t(λ, μ, ν) for λ, μ, ν ⊢ d.

Proof. Recall that [λ′] ≃ [λ] ⊗ [1^{d}], where d = |λ|. Suppose that λ′, μ′, ν′ have at most m parts. Then we have

k(λ, μ, ν) = mult([λ] ⊗ [μ] ⊗ [ν], [d])
= mult([λ′] ⊗ [μ′] ⊗ [ν′], [1^{d}])
= mult (V_{λ′}(GL_{m}) ⊗ V_{μ′}(GL_{m}) ⊗ V_{ν′}(GL_{m}), Λ^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m})),

where for the last equality we have used Schur–Weyl duality.

Let e_{j} denote the jth canonical basis vector of ℂ^{m}. To a 3D-relation R = {(x_{i}, y_{i}, z_{i}) | 1 ≤ i ≤ d} ⊆ {0, …, m − 1}^{3} such that |R| = d, we assign the vector (only defined up to sign)

v_{R} := ± ∧_{i=1}^{d} (e_{x_{i}} ⊗ e_{y_{i}} ⊗ e_{z_{i}}) ∈ ∧^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m}).

Note that the v_{R} form a basis of ∧^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m}). In fact, v_{R} is a weight vector of weight (x_{R}, y_{R}, z_{R}), since, for a triple

g = (diag(a_{0}, …, a_{m−1}), diag(b_{0}, …, b_{m−1}), diag(c_{0}, …, c_{m−1}))

of invertible diagonal matrices, we have

g · v_{R} = a_{0}^{x_{R}(0)} ⋯ a_{m−1}^{x_{R}(m−1)}b_{0}^{y_{R}(0)} ⋯ b_{m−1}^{y_{R}(m−1)}c_{0}^{z_{R}(0)} ⋯ c_{m−1}^{z_{R}(m−1)} v_{R}.

We conclude that t(λ, μ, ν) equals the dimension of the weight space of weight (λ′, μ′, ν′) in Λ^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m}).

At the beginning of the proof, we observed that k(λ, μ, ν) equals the multiplicity of V_{λ′}(GL_{m}) ⊗ V_{μ′}(GL_{m}) ⊗ V_{ν′}(GL_{m}) in Λ^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m}), which is the dimension of the vector space of highest weight vectors of weight (λ′, μ′, ν′) in Λ^{d}(ℂ^{m} ⊗ ℂ^{m} ⊗ ℂ^{m}). So we conclude that k(λ, μ, ν) ≤ t(λ, μ, ν).

Finally, if R is a pyramid, then it is easy to check that (g_{1}, g_{2}, g_{3}) · v_{R} = v_{R}, where g_{1}, g_{2}, g_{3} are invertible upper triangular matrices with 1’s on the diagonal. In this case, v_{R} is therefore a highest weight vector. This implies p(λ, μ, ν) ≤ k(λ, μ, ν). □

We will show now that certain constraints on the marginals of a 3D-relation R enforce that R must be a pyramid.

The distance of the barycenter b_{R} := \frac{1}{|R|} ∑_{p∈R} p of R to the linear hyperplane orthogonal to the diagonal (1, 1, 1) is given by h_{R} := b_{R} · (1, 1, 1)^{T}, up to the scaling factor \sqrt{3}. The distance h_{R} can be expressed in terms of the marginals of R by

(4.1)  |R| h_{R} = ∑_{(x,y,z)∈R}(x + y + z) = ∑_{i} i (x_{R}(i) + y_{R}(i) + z_{R}(i)).

For s ≥ 1 we consider the simplex P (s) := {(x, y, z) ∈ ℕ^{3} | x + y + z ≤ s − 1}, which has the cardinality |P (s)| = s(s + 1)(s + 2)/6. For d ≥ 1 we define s(d) as the maximal natural number s such that |P (s)| ≤ d.

Assume now that a 3D-relation R satisfies P (s) ⊆ R ⊂ P (s + 1) for some s. Then necessarily s = s(d), where d := |R|. In this situation, it is easy to see that h_{R} = h(d), where

(4.2)  h(d) := \frac{|P (s)|}{d} h_{P (s)} + (1 − \frac{|P (s)|}{d}) s.

If λ′, μ′, ν′ denote the marginals of R, then we have by (4.1),

(4.3)  ∑_{i} i (λ′_{i} + μ′_{i} + ν′_{i}) = d h(d).

We call a triple λ, μ, ν ⊢ d of partitions simplex-like if (4.3) holds.

Lemma 4.4. Any 3D-relation R, whose marginals are simplex-like, is a pyramid. Hence k(λ, μ, ν) = t(λ, μ, ν) if (λ, μ, ν) is simplex-like.

Proof. The first assertion is easy to prove and the second one follows with Lemma 4.3. □

The following result was shown in [5].

Theorem 4.5 (Brunetti, Del Lungo, Gérard). Deciding t(λ, μ, ν) > 0 is an NPhard problem.

The catch is that the reduction in the proof of this theorem from 3D-matching is such that one can actually reduce to simplex-like triples (λ, μ, ν) of partitions. This completes our sketch of the proof of Theorem 4.1. In fact, the NP-hardness reduction in the proof of Theorem 4.5 leads to an efficient and explicit way to produce many gaps of the Kronecker monoid. We are not aware of any other way to obtain this result! Unfortunately, the reduction breaks down for the most wanted situation of partition triples (λ, μ, μ) where μ is a rectangle. In fact, one can prove that t(λ, n × d, n × d) > 0 if λ ⊢ dn such that ℓ(λ) ≤ min{d^{2}, n^{2}}, see [31, Thm. 6.9].

From the proof of Theorem 4.5 one obtains the following insights, which show a remarkable interplay between computer science and algebraic combinatorics.

• There is a positive #P-formula for a subclass of triples of partitions, whose positivity of Kronecker coefficients is NP-hard to decide.

• The Kronecker monoid has many gaps, and we can efficiently compute subexponentially many of them. More specifically, for any 0 < ϵ < 1 there is 0 < a < 1 such that, for all m, there exist Ω(2^{m^{a}}) many partition triples (λ, μ, μ) such that k(λ, μ, μ) = 0, but there exists s ≥ 1 with k(sλ, sμ, sμ) > 0. Moreover, ℓ(μ) ≤ m^{ϵ} and |λ| = |μ| ≤ m^{3}. Finally, there is an efficient algorithm to produce these partitions.

Since the reduction breaks down for the most wanted situation of partition triples (λ, μ, μ) where μ is a rectangle, this fails to provide a solution for Problem 3.14.

4.2. Testing asymptotic positivity may be feasible. We finish by mentioning a further recent insight.

Definition 4.6. The asymptotic positivity problem for Kronecker coefficients is the problem of deciding for given λ, μ, ν (in binary encoding) whether k(sλ, sμ, sν) > 0 for some s ≥ 1.

This problem can be rephrased as a membership problem to a (family of) polyhedral cones, that we may call Kronecker cones. They are of relevance for the quantum marginal problem of quantum information theory; see [34, 19, 20].

Theorem 4.1 states that the positivity testing problem for Kronecker coefficients is NPhard. By contrast, the following recent result [9] tells us that the asymptotic version of this problem should be considerably easier.

Theorem 4.7 (B, Christandl, Mulmuley, Walter). The asymptotic positivity problem for Kronecker coefficients is in NP ∩ coNP.

In fact, we have now good reasons to conjecture that the asymptotic positivity problem for Kronecker coefficients can be solved in polynomial time. In view of the known algorithms and the complicated face structure of the Kronecker cones [55, 61], this is quite surprising.

The proof of Theorem 4.7 combines different techniques. The containment in NP is a consequence of the description of the Kronecker cone as the image of the so-called moment map, which is a consequence of a general result due to Mumford [51]; see also [4]. Moment maps are studied in symplectic geometry.

The basis of the containment in coNP is a description of the facets of the Kronecker cone due to Ressayre [55]. Vergne and Walter [61] provided a modification of Ressayre’s description that is efficiently testable, which leads to the containment in coNP.

5. Note added in proof

Since the writing of this survey in the fall of 2015, important progress has been made with regard to the feasibility of the attempt outlined in Section 3.

In a breakthrough work, Ikenmeyer and Panova [32] showed that the vanishing of rectangular Kronecker coefficients cannot be used to prove superpolynomial lower bounds on the determinantal complexity of the permanent polynomials!

Recall that, by Theorem 3.10, an occurrence obstruction λ proving dc(m) > n necessarily satisfies ℓ(λ) ≤ m^{2} + 1 and λ_{1} ≥ |λ|(1 − m/n). (By a minor modification of the notion of padded permanents, we may even assume ℓ(λ) ≤ m^{2}.)

More specifically, Ikenmeyer and Panova proved the following.

Theorem 5.1 (Ikenmeyer and Panova). Let λ ⊢ dn such that ℓ(λ) ≤ m^{2}, λ_{1} ≥ |λ|(1 − m/n), and assume n > 3m^{4}. Then pleth_{n}(λ) > 0 implies k_{n}(λ) > 0.

This result does not yet rule out the occurrence based approach towards VP ≠ VNP as outlined in Section 3, since it refers to the Kronecker coefficients k_{n}(λ) of rectangular partitions and not to the GCT-coefficients k̃_{n}(λ). (Recall those are the multiplicities in the coordinate ring of the orbit closure of Ω_{n}; see (3.5) and Theorem 3.9.)

However, shortly after the appearance of [32], Bürgisser, Ikenmeyer and Panova [14] proved a similarly devastating result for the GCT-coefficients.

Theorem 5.2 (B, Ikenmeyer, and Panova). Let λ ⊢ dn such that we have ℓ(λ) ≤ m^{2}, λ_{1} ≥ |λ|(1 − m/n), and assume n > m^{25}. Then pleth_{n}(λ) > 0 implies k̃_{n}(λ) > 0.

The main ingredient behind the proof of Theorem 5.2, besides a splitting technique as for Theorem 5.1, is the encoding of a generating system of highest weight vectors in plethysms Sym^{d} Sym^{n} V by (classes of) tableaux with contents d × n, as well as the analysis of their evaluation at tensors of rank one in a combinatorial way. This is similar to [7, 29]. A further technique is the “lifting” of highest weight vectors of Sym^{d} Sym^{n} V, when increasing the inner degree n, as introduced by Kadish and Landsberg [33]. This is closely related to stability property of the plethysm coefficients [62, 17, 42]. Remarkably, for the proof of Theorem 5.2, the only information needed about the orbit closures Ω_{n} is that they contain certain padded power sums, see also [11].

5.1. Final remarks. Unfortunately, Theorem 5.2 rules out the possibility of proving VP ≠ VNP via occurrence obstructions.

Let us emphasize that there still remains the possibility that the approach via representation theoretic obstructions may succeed when comparing multiplicities. Indeed, if the orbit closure Z_{n,m} of the padded permanent t^{n−m} per_{m} is contained in Ω_{n}, then the restriction defines a surjective GL_{n^{2}}-equivariant homomorphism ℂ[Ω_{n}] → ℂ[Z_{n,m}] of the coordinate rings, and hence the multiplicity of the type λ in ℂ[Z_{n,m}] is bounded from above by the GCT-coefficient k̃_{n}(λ). Thus, proving that k̃_{n}(λ) is strictly smaller than the latter multiplicity implies that Z_{n,m} ⊈ Ω_{n}. Mulmuley pointed out to us a paper by Larsen and Pink [39] that is of potential interest in this connection.

In this context let us remark that [18] shows that comparing multiplicities by asymptotic methods cannot be sufficient for the purpose of complexity separation.

To conclude, even if the approach via multiplicities should turn out to be impossible as well, we should keep in mind that the noncontainment of orbit closures in principle can be proved by exhibiting some highest weight vector functions (see [13, Prop. 3.3]). Classical invariant theory and representation theory should provide guidelines on how to find such functions, even though our current understanding of this is very limited.

Acknowledgements. I thank Jesko Hüttenhain, Christian Ikenmeyer, Joseph Landsberg, and Ketan Mulmuley for their feedback. Special thanks go to Christian Krattenthaler for his detailed comments on the manuscript. I am grateful to the Simons Institute for the Theory of Computing in Berkeley for making possible the semester program “Algorithms and Complexity in Algebraic Geometry”, that provided ideal conditions for achieving the recent progress outlined in this survey.

References

[1] Noga Alon and Michael Tarsi. Colorings and orientations of graphs. Combinatorica, 12(2):125–134, 1992.

[2] Jarod Alper, Tristram Bogart, and Mauricio Velasco. A lower bound for the determinantal complexity of hypersurface. Found. Comput. Math., 2016. To appear.

[3] Jonah Blasiak. Kronecker coefficients for one hook shape. arXiv:1209.2018, 2012.

[4] Michel Brion. Sur l’image de l’application moment. In Séminaire d’algèbre Paul Dubreil et Marie-Paule Malliavin (Paris, 1986), volume 1296 of Lecture Notes in Math., pages 177–192. Springer, Berlin, 1987.

[5] Sara Brunetti, Alberto Del Lungo, and Yan Gérard. On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays. In Proceedings of the Workshop on Discrete Tomography: Algorithms and Applications (Certosa di Pontignano, 2000), volume 339, pages 59–73, 2001.

[6] Peter Bürgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer Verlag, 2000.

[7] Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer. Even partitions in plethysms. Journal of Algebra, 328(1):322 – 329, 2011.

[8] Peter Bürgisser, Matthias Christandl, and Christian Ikenmeyer. Nonvanishing of Kronecker coefficients for rectangular shapes. Adv. Math., 227(5):2082–2091, 2011.

[9] Peter Bürgisser, Matthias Christandl, Ketan Mulmuley, and Michael Walter. On the complexity of the membership problem for moment polytopes. arXiv:1511.03675, 2015.

[10] Peter Bürgisser, Jesko Hüttenhain, and Christian Ikenmeyer. Permanent versus determinant: not via saturations. arXiv:1501.05528, 2015.

[11] Peter Bürgisser and Christian Ikenmeyer. Fundamental invariants of orbit closures. arXiv:1511.02927, 2015.

[12] Peter Bürgisser and Christian Ikenmeyer. Deciding positivity of Littlewood-Richardson coefficients. SIAM J. Discrete Math., 27(4):1639–1681, 2013.

[13] Peter Bürgisser and Christian Ikenmeyer. Explicit lower bounds via geometric complexity theory. Proceedings 45th Annual ACM Symposium on Theory of Computing 2013, pages 141–150, 2013.

[14] Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. arXiv:1604.06431, 2016.

[15] Peter Bürgisser, J.M. Landsberg, Laurent Manivel, and Jerzy Weyman. An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP. SIAM J. Comput., 40(4):1179–1209, 2011.

[16] Jin-Yi Cai, Xi Chen, and Dong Li. Quadratic lower bound for permanent vs. determinant in any characteristic. Comput. Complexity, 19(1):37–56, 2010.

[17] Christophe Carré and Jean-Yves Thibon. Plethysm and vertex operators. Adv. in Appl. Math., 13(4):390–403, 1992.

[18] Matthias Christandl, Brent Doran, and Michael Walter. Computing multiplicities of Lie group representations. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, pages 639–648. IEEE Computer Soc., Los Alamitos, CA, 2012.

[19] Matthias Christandl and Graeme Mitchison. The spectra of density operators and the Kronecker coefficients of the symmetric group. Comm. Math. Phys., 261(3):789–797, February 2006.

[20] Matthias Christandl, Aram Harrow, and Graeme Mitchison. On nonzero Kronecker coefficients and what they tell us about spectra. Comm. Math. Phys., 270(3):575–585, 2007.

[21] Jean Dieudonné. Sur une généralisation du groupe orthogonal à quatre variables. Arch. Math., 1:282– 287, 1949.

[22] Jan Draisma. Geometry, invariants, and the elusive search for complexity lower bounds. SIAM News, 48(6), 2015.

[23] Arthur A. Drisko. Proof of the Alon-Tarsi conjecture for n = 2^{r}p. Electron. J. Combin., 5:Research paper 28, 5 pp. (electronic), 1998.

[24] Georg Frobenius. Über die Darstellung der endlichen Gruppen durch lineare Substitutionen. Sitzungsber Deutsch. Akad. Wiss. Berlin, pages 994–1015, 1897.

[25] William Fulton and Joe Harris. Representation Theory - A First Course, volume 129 of Graduate Texts in Mathematics. Springer, 1991.

[26] David G. Glynn. The conjectures of Alon-Tarsi and Rota in dimension prime minus one. SIAM J. Discrete Math., 24(2):394–399, 2010.

[27] Bruno Grenet. An upper bound for the permanent versus determinant problem. Accepted for Theory of Computing, 2011.

[28] Jesko Hüttenhain and Pierre Lairez. The boundary of the orbit of the 3 by 3 determinant polynomial. arXiv:1512.02437, 2015.

[29] Christian Ikenmeyer. Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients. PhD thesis, Institute of Mathematics, University of Paderborn, 2012.

[30] Christian Ikenmeyer and Jesko Hüttenhain. Binary determinantal complexity. Linear Algebra and its Applications, 504:559–573, 2016.

[31] Christian Ikenmeyer, Ketan Mulmuley, and Michael Walter. On vanishing of Kronecker coefficients. arXiv:1507.02955, 2015.

[32] Christian Ikenmeyer and Greta Panova. Rectangular Kronecker coefficients and plethysms in geometric complexity theory. arXiv:1512.03798, 2015.

[33] Harlan Kadish and J. M. Landsberg. Padded polynomials, their cousins, and geometric complexity theory. Comm. Algebra, 42(5):2171–2180, 2014.

[34] Alexander Klyachko. Quantum marginal problem and representations of the symmetric group. arXiv:quant-ph/0409113, 2003.

[35] Hanspeter Kraft. Geometrische Methoden in der Invariantentheorie. Aspects of Mathematics, D1. Friedr. Vieweg & Sohn, Braunschweig, 1984.

[36] Shrawan Kumar. A study of the representations supported by the orbit closure of the determinant. Compositio Mathematica, 151:292–312, 2 2015.

[37] Joseph Landsberg and Nicolas Ressayre. Permanent v. determinant: an exponential lower bound assuming symmetry and a potential path towards Valiant’s conjecture. arXiv:1508.05788, 2015.

[38] Joseph M. Landsberg, Laurent Manivel, and Nicolas Ressayre. Hypersurfaces with degenerate duals and the geometric complexity theory program. Comment. Math. Helv., 88(2):469–484, 2013.

[39] M. Larsen and R. Pink. Determining representations from invariant dimensions. Invent. math., 102:377–389, 1990.

[40] Jesús De Loera and Tyrrell McAllister. On the computation of Clebsch-Gordan coefficients and the dilation effect. Experiment. Math., 15(1):7–19, 2006.

[41] Guillaume Malod and Natacha Portier. Characterizing Valiant’s algebraic complexity classes. Journal of Complexity, 24:16–38, 2008.

[42] L. Manivel. Gaussian maps and plethysm. In Algebraic geometry (Catania, 1993/Barcelona, 1994), volume 200 of Lecture Notes in Pure and Appl. Math., pages 91–117. Dekker, New York, 1998.

[43] Laurent Manivel. Applications de Gauss et pléthysme. Ann. Inst. Fourier (Grenoble), 47(3):715–773, 1997.

[44] Marvin Marcus and Henryk Minc. On the relation between the determinant and the permanent. Illinois J. Math., 5:376–381, 1961.

[45] Thierry Mignon and Nicolas Ressayre. A quadratic bound for the determinant and permanent problem. Int. Math. Res. Not., 79:4241–4253, 2004.

[46] Ketan D. Mulmuley. Geometric complexity theory VI: the flip via positivity. Technical report, Computer Science Department, the University of Chicago, 2010.

[47] Ketan D. Mulmuley, Hariharan Narayanan, and Milind Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin., 36(1):103–110, 2012.

[48] Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496–526 (electronic), 2001.

[49] Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties. SIAM J. Comput., 38(3):1175–1206, 2008.

[50] David Mumford. Algebraic geometry. I. Classics in Mathematics. Springer-Verlag, Berlin, 1995. Complex projective varieties, Reprint of the 1976 edition.

[51] Linda Ness. A stratification of the null cone via the moment map. Amer. J. Math., 106(6):1281–1329, 1984. With an appendix by David Mumford.

[52] Georg Pólya. Aufgabe 424. Arch. Math. Phys., 20:271, 1913.

[53] Claudio Procesi. Lie groups. Universitext. Springer, New York, 2007. An approach through invariants and representations.

[54] Jorge Luis Ramírez Alfonsín. The Diophantine Frobenius problem, volume 30 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2005.

[55] Nicolas Ressayre. Geometric invariant theory and the generalized eigenvalue problem. Invent. Math, 180:389–441, 2010.

[56] Issai Schur. Vorlesungen über Invariantentheorie. Bearbeitet und herausgegeben von Helmut Grunsky. Die Grundlehren der mathematischen Wissenschaften, Band 143. Springer-Verlag, Berlin-New York, 1968.

[57] Bernd Sturmfels. Algorithms in invariant theory. Texts and Monographs in Symbolic Computation. Springer-Verlag, Vienna, 1993.

[58] Gábor Szegő. Zu Aufgabe 424. Arch. Math. Phys., 21:291–292, 1913.

[59] Leslie G. Valiant. Completeness classes in algebra. In Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979), pages 249–261. ACM, New York, 1979.

[60] Ernesto Vallejo. Plane partitions and characters of the symmetric group. J. Algebraic Combin., 11(1):79–88, 2000.

[61] Michèle Vergne and Michael Walter. Inequalities for moment cones of finite-dimensional representations. arXiv:1410.8144, 2015.

[62] Steven H. Weintraub. Some observations on plethysms. J. Algebra, 129(1):103–114, 1990.

[63] Akihiro Yabe. Bi-polynomial rank and determinantal complexity. arXiv:1504.00151, 2015.