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.
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
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.
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.