Complexity in Invariant Theory.

Abstract

Computational invariant theory considers two problems in the representations of algebraic groups: computing generators for rings of polynomial invariant functions, and determining whether two points lie in the same orbit. This thesis examines the complexity of these tasks. On the one hand, to count generating invariants for a semisimple group, choose an representation of highest weight w, and consider the irreducible representations of highest weight nw. As n goes to infinity, the cardinality of a minimal generating set grows faster than any polynomial in n. On the other hand, one can separate the orbits of any algebraic group action in polynomial time using "constructible" functions defined by straight line programs in the polynomial ring, with a new "quasi-inverse" that computes the inverse of a function where defined.