TY - JOUR
AU - Søren Riis
AU - Meera Sitharam
PY - 1998/01/20
Y2 - 2019/12/15
TI - Uniformly Generated Submodules of Permutation Modules
JF - BRICS Report Series
JA - BRICS
VL - 5
IS - 20
SE - Articles
DO - 10.7146/brics.v5i20.19426
UR - https://tidsskrift.dk/brics/article/view/19426
AB - This paper is motivated by a link between algebraic proofcomplexity and the representation theory of the finite symmetricgroups. Our perspective leads to a series of non-traditionalproblems in the representation theory of Sn.Most of our technical results concern the structure of "uniformly"generated submodules of permutation modules. We consider(for example) sequences Wn of submodules of the permutationmodules M(n−k;1k) and prove that if the modules Wn aregiven in a uniform way - which we make precise - the dimensionp(n) of Wn (as a vector space) is a single polynomial with rationalcoefficients, for all but finitely many "singular" values of n. Furthermore, we show that dim(Wn) < p(n) for each singular value of n >= 4k. The results have a non-traditional flavor arising from the study of the irreducible structure of the submodules Wn 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.
ER -