Implementing geometric complexity theory: On the separation of orbit closures via symmetries

1^st July 2020, 14:00 Microsoft Teams
Christian Ikenmeyer

Abstract

Understanding the difference between group orbits and their closures is
a key difficulty in geometric complexity theory (GCT): While the GCT
program is set up to separate certain orbit closures, many beautiful
mathematical properties are only known for the group orbits, in
particular close relations with symmetry groups and invariant spaces,
while the orbit closures seem much more difficult to understand.
However, in order to prove lower bounds in algebraic complexity theory,
considering group orbits is not enough.
In this paper we tighten the relationship between the orbit of the power
sum polynomial and its closure, so that we can separate this orbit
closure from the orbit closure of the product of variables by just
considering the symmetry groups of both polynomials and their
representation theoretic decomposition coefficients. In a natural way
our construction yields a multiplicity obstruction that is neither an
occurrence obstruction, nor a so-called vanishing ideal occurrence
obstruction. All multiplicity obstructions so far have been of one of
these two types.
Our paper is the first implementation of the ambitious approach that was
originally suggested in the first papers on geometric complexity theory
by Mulmuley and Sohoni (SIAM J Comput 2001, 2008): Before our paper, all
existence proofs of obstructions only took into account the symmetry
group of one of the two polynomials (or tensors) that were to be
separated. In our paper the multiplicity obstruction is obtained by
comparing the representation theoretic decomposition coefficients of
both symmetry groups.
Our proof uses a semi-explicit description of the coordinate ring of the
orbit closure of the power sum polynomial in terms of Young tableaux,
which enables its comparison to the coordinate ring of the orbit.
This is joint work with Umangathan Kandasamy

Additional Materials

• https://arxiv.org/abs/1911.03990