Formal Definition
of the Varieties

for the interested readers, we now formally define the varieties D[det, m] and D[perm,
n, m] and the action of G on them.
let Y be an m × m variable matrix. let X be an n × n submatrix of Y, say its lower-right n
× n subminor. let z be any entry of Y outside X. let V be the vector space of homogeneous
polynomials of degree m in the variable entries of Y. thus, det(Y ) is an element of
V. let D~ [det, m] be the set of elements in V of the form det( Y ¢), where Y ¢ is an m × m
matrix whose entries are complex homogeneous linear combinations of the variable
entries of Y. then, D[det, m] ⊆ V is the closure of D~[det, m] in V in the usual complex
topology of V. It can be shown to be an algebraic variety. the variety D [perm, n, m] ⊆ V
is constructed similarly using the homogeneous polynomial zm−n perm(X) OE V in place
of the determinant. It can be shown25 that these varieties have the required property
mentioned in ( 1). actually the varieties here are the affine cones of the projective varieties
defined in Mulmuley and sohoni. 25
the action of G = GLk(C), k = m2, on these varieties is defined as follows. first, observe
that the space V is a representation of G by a natural action which, for any matrix s OE G,
maps any point (homogeneous polynomial) p(Y) OE V to the point p(s −1Y ). here, we think
of Y as an m2-vector by straightening it, say, rowwise. It can be shown that D[det, m] and
D[perm, n, m] are invariant under this action of G on V. this induces a natural action of G
on these varieties as well. Under this action, each matrix in G acts on a variety by moving its
points around and thereby inducing an automorphism. With this action, the coordinate
ring of D[det, m], by which we mean the space of polynomial functions on V restricted to
D[det, m], becomes a representation of G: just map a polynomial function f (v) to f (s − 1◊v) for
any s OE G and v OE D[det, m]. here s − 1◊v denotes the point in D[det, m] obtained by letting s − 1
OE G act on v. the coordinate ring of D[perm, n, m] is similarly a representation of G.

f s(z –) = f (z –s).

( 2) be the coordinate ring of E. This is the space of polynomial functions on R3 restricted to E. Then, this action of U on E also makes R[E] a representation of U: given q  U just map any polynomial function f (x–) = f (x1, x2, x3) on E to f (q ⋅ x–), where q ⋅ x–  E denotes the point obtained by rotating x–  E around the x3 axis by the angle q.

Similarly, the group G = GLkC, with
k = m2, acts on the varieties D[det, m]
and D[perm, n, m] moving their points
around (Figure 1), and this action of
G on the varieties makes their coordi-
nate rings (the spaces of polynomial
functions on them) representations of
Each finite-dimensional represen-
tation of G is like a complex build-
ing that can be decomposed into the
building blocks—the Weyl modules.
Fundamental significance of Weyl’s
classification results from the com-
plexity theoretic perspective is the fol-
lowing. The dimension of each Weyl
module Vλ(K) is in general exponen-
tial in the bit length of λ. But it has a
compact (polynomial size) specifica-
tion, namely, the labeling partition λ.
Existence of such compact specifica-
tions of irreducible representations of
G plays a crucial role in what follows.

G. A formal definition of the action of G and the representation structures of the coordinate rings of D[det, m] and D[perm, n, m] are discussed later.

These representation structures turn out26 to depend critically on the properties (D) and (P), respectively. Specifically, the properties (D) and (P) put strong restrictions as to which irreducible representations of G can occur as G-subrepresentations of these coordinate rings.

Formally, a geometric obstruction to the inclusion ( 1) for given n and m is an irreducible representation Vl(G) of G (a Weyl module) that occurs as a G-subrepresentation in the coordinate ring of D[perm, n, m] but not in the coordinate ring of D[det, m]c; see Figure 1. The partition λ here is called a geometric obstruction label. The existence of such an obstruction guarantees that the inclusion as in ( 1) is impossible, because otherwise the obstruction would occur as a G-subrepresentation in the coordinate ring of D[det, m] as well.

Thus, to solve the (strong) permanent vs. determinant conjecture, it suffices to show the following:

Geometric obstruction hypothesis (Goh). 26 A geometric obstruction exists when m is polynomial in n.

It is conjectured in Mulmuley22 that GOH, or rather its slightly relaxed form, is equivalent to the strong permanent vs. determinant conjecture.

 

figure 2. An ellipsoid.

x3

a

Ellipsoid E

θ x1

x2

The flip

With the help of GOH, we have reduced the nonexistence problem under consideration to an existence problem. For general varieties, such an existence problem is hopeless. But we can hope to prove existence of a geometric obstruction using the characterization by symmetries provided by the properties (P) and (D). We turn to this story here.

The strategy is to construct, for any n and m polynomial in n, a geometric obstruction label λ explicitly in time polynominal in n and m by exploiting the properties (P) and (D). We call this strategy the flip, because it reduces the nonexistence problem under consideration to the problem of proving existence of a geometric obstruction, and furthermore, the c Strictly speaking, we have to use the duals of the coordinate rings here.