COMPUTING BASES FOR RINGS OF PERMUTATION-INVARIANT POLYNOMIALS

Let R be a commutative ring with 1, let R[X(1),..., X(n)] be the polyn omial ring in X1,..., X(n) over R and let G be an arbitrary group of p ermutations of {X(1),..., X(n)}. The paper presents an algorithm for c omputing a small finite basis B of the R-algebra of G-invariant polyno mials and a polynomial representation of an arbitrary G-invariant poly nomial in R[X(1),..., X(n)] as a polynomial in the polynomials of the finite basis B. The algorithm works independently of the ground ring R , and the basis B contains only polynomials of total degree less than or equal to max{n, n(n - 1)/2}, independent of the size of the permuta tion group G.