Uniformly Generated Submodules of Permutation Modules

Søren Riis
Meera Sitharam

September 1998


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

Most of our technical results concern the structure of ``uniformly'' generated submodules of permutation modules. We consider (for example) sequences tex2html_wrap_inline25 of submodules of the permutation modules tex2html_wrap_inline27 and prove that if the modules tex2html_wrap_inline25 are given in a uniform way - which we make precise - the dimension p(n) of tex2html_wrap_inline25 (as a vector space) is a single polynomial with rational coefficients, for all but finitely many ``singular'' values of n. Furthermore, we show that tex2html_wrap_inline37 for each singular value of tex2html_wrap_inline39. The results have a non-traditional flavor arising from the study of the irreducible structure of the submodules tex2html_wrap_inline25 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.


Last modified: 2003-06-08 by webmaster.