Abstract:
This paper is motivated by a link between algebraic proof
complexity and the representation theory of the finite symmetric groups. Our
perspective leads to a series of non-traditional problems in the
representation theory of 
.
Most of our technical results concern
the structure of ``uniformly'' generated submodules of permutation modules.
We consider (for example) sequences 
of submodules of the permutation
modules 
and prove that if the modules are given in a
uniform way - which we make precise - the dimension p(n) of (as a
vector space) is a single polynomial with rational coefficients, for all but
finitely many ``singular'' values of n. Furthermore, we show that 
for each singular value of 
. The results have a
non-traditional flavor arising from the study of the irreducible structure of
the submodules beyond isomorphism types.
We sketch the link between our structure theorems and proof complexity questions, which can be viewed as special cases of the famous NP vs. co-NP problem in complexity theory. In particular, we focus on the efficiency of proof systems for showing membership in polynomial ideals, for example, based on Hilbert's Nullstellensatz.
Available as PostScript, PDF, DVI.