Uniformly generated submodules of permutation modules - Over fields of characteristic 0

This paper is motivated by a link between algebraic proof complexity and th e representation theory of the finite symmetric groups. Our perspective lea ds to a new avenue of investigation in the representation theory of S,,. Mo st of our technical results concern the structure of "uniformly" generated submodules of permutation modules. For example, we consider sequences {W-n} (n epsilonN) of submodules of the permutation modules M-(n-k,M-1k) prove th at if the sequence Ii:, is given in a uniform (in n) way - which we make pr ecise - the dimension p(n) of W-n las a vector space) is a single polynomia l with rational coefficients, for all but finitely many "singular" values o f n, Furthermore, we show that dim (W-n) < p(n) for each singular value of n greater than or equal to 4k. The results have a non-traditional flavor ar ising from the study of the irreducible structure of the submodules W, beyo nd isomorphism types. We sketch the link between our structure theorems and proof complexity questions, which are motivated by the famous NP vs, co-NP problem in complexity theory. In particular, we focus on the complexity of showing membership in polynomial ideals, in various proof systems, for exa mple, based on Hilbert's Nullstellensatz. (C) 2001 Elsevier Science B.V. Al l rights reserved.