Skip to main content
4 of 6
fixed name spelling

Let $X=(X_{ij})_{1\le i,j\le n}$ be a generic $n\times n$ matrix and $F_1(X)={\rm det}(X)$ the degree $n$ homogeneous polynomial given by the determinant. Let $$ F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right] $$ which takes the permanent of an $m\times m$ submatrix and multiplies by one's favorite linear form in order to make another homogeneous polynomial of degree $n$ (one could also use the entry $X_{11}$ instead of $X_{nn}$). This modification is called padding. Then define the number $$ c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \} $$ where $G$ is $GL(n^2)$ acting on the affine space of dimension $n^2$ where $X$ lives and $\overline{G\cdot F_i}$ are Zariski closures of orbits. The big conjecture in the area or Valiant's Hypothesis (a complex version of ${\rm P}\neq{\rm NP}$) is that $c(m)$ grows faster than any polynomial in $m$.

Now if $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$, then one has a surjective $G$-equivariant map $$ \mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d $$ between degree $d$ parts of the coordinate rings of these orbit closures. So the game is to try to show that this does not happen, for $n$ insufficiently large relative to $m$, by proving the existence of a multiplicity obstruction, i.e., an irreducible representation $\lambda$ for which multiplicities satisfy $$ {\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d) $$ or at the level of ideals $$ {\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ . $$

An optimistic approach is to try to show there exist occurrence obstructions, i.e., $\lambda$'s such that ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$ and ${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$. This hope has been squashed in the work of Bürgisser, Ikenmeyer and Panova mentioned by Timothy. However, the possibility of multiplicity obstructions is still open.

I think the approach by Mulmuley is to try prove the existence of such multiplicity obstructions by leveraging all the tools available from representation theory for the computation of these multiplicities. Personally, I have never been a fan of this approach. Having studied 19th century invariant theory in some depth, it seems more natural to me to approach the orbit separation problem using the explicit tools from that era. This article by Grochow seems to also point in a similar direction (I suspect the third article mentioned by Joseph is in the same vein). In classical language (see Turnbull or Littlewood), one has to explicitly construct a mixed concomitant which vanishes on $F_1$ but not on $F_2$. One also has to do this infinitely often (in $m$) in order to establish the superpolynomial growth property. Such a concomitant is the same as a specific $G$-equivariant map from your favorite model for the irreducible representation $\lambda$ to the polynomial algebra in the $n^2$ variables $X$ (Grochow calls that a separating module). Invariant theorists from the 19th century had two methods for generating such objects: elimination theory and diagrammatic algebra.

A very baby example where $F_1$ and $F_2$ are binary quartic forms under the action of $G=SL(2)$ (see this MO question) is say $$ F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4 $$ and $$ F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ . $$ A separating concomitant (here in fact a covariant) is the Hessian of a generic binary quartic $F$ $$ H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ . $$ It vanishes (identically in $x,y$) for $F=F_1$ but not for $F=F_2$. In this case, the Hessian can be seen as an equivariant map form the irreducible given by the second symmetric power (of the fundamental two-dimensional representation) into the coordinate ring for the affine space of binary quartics.

So a possible superoptimistic "plan" for GCT involves the following sequence of steps.

  1. Find a way to generate tons of concomitants.

  2. Identify some explicit candidates for the vanishing on $F_1$ and prove that property.

  3. Show they don't vanish on $F_2$.

Step 1) is in principle solved by the First Fundamental Theorem for $GL(n^2)$ but there is a mismatch: the determinant is a natural object in the invariant theory for $GL(n)\times GL(n)$ (acting on rows and columns) rather than $GL(n^2)$. One could try to repair the mismatch by expressing the basic building block for the invariant theory of $GL(n^2)$ in terms of the one for $GL(n)\times GL(n)$ (see this MO question for a similar reduction problem from $SL(n(n+1)/2)$ to $SL(n)$).

Guessing the right candidates for Step 2) looks hard to me. Knowing beforehand that some multiplicities ${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$ are nonzero would definitely help. Although, one could procrastinate and defer the proof of nonidentical vanishing of the concomitant to Step 3) which should show more than that anyway. If one has such right candidates, showing they vanish on $F_1$ may be easy by arguments one could call Pauli's exclusion principle (contracting symmetrizations with antisymmetrizations), high chromatic number property, or simply `lack of space'.

However, I think the most difficult part is Step 3). For example, in my paper "16,051 formulas for Ottaviani's invariant of cubic threefolds" with Ikenmeyer and Royle, the guessing was done by computer search, but with the right candidate in hand, the vanishing on $F_1$ was relatively easy to explain (it's a rather pretty example of chromatic number due to the global properties of the graph rather than some big clique). The analogue of Step 3) in our article was done by brute force computer calculation and we still don't have a clue for why it is true. The paradigmatic problem related to Step 3) is the Alon-Tarsi conjecture (see this MO question and this one too). In my opinion, one needs to make progress on that kind of question (the Four Color Theorem is of this type too, via a reduction due to Kauffman and Bar-Natan) before Valiant's Conjecture.

Since the question is about breakthroughs in GCT. I think this article by Landsberg and Ressayre also deserves some attention since it suggests that a reasonable guess for the exact value of $c(m)$ is $$ \left(\begin{array}{c}2m\\ m \end{array}\right)-1\ . $$ Note that a proof of concept for the explicit "Step 1),2),3) approach", on a much simpler problem, was given by Bürgisser and Ikenmeyer in this article. Finally, for more information on GCT, I highly recommend the review "Geometric complexity theory: an introduction for geometers" by Landsberg.

PS: I should add that my pessimism is specific to the Valiant Hypothesis which is the `Riemann Hypothesis' in the field. Of course, one should not throw the baby with the bath water and denigrate GCT because it so far failed to prove this conjecture. There are plenty of more approachable problems in this area where progress has been made and more progress is expected. See in particular the above-mentioned article by Grochow and review by Landsberg.