Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 40 (1999), No. 1, 27-51.

Multisymmetric Functions

John Dalbec

Department of Mathematics, Yale University 10 Hillhouse Ave., P. O. Box 208283 New Haven CT 06520-8283, USA

Abstract. We develop a theory of multisymmetric functions along the lines of the theory of ordinary symmetric functions presented in [9]. We extend this theory to the multihomogeneous case (factorizable forms) in characteristic 0. In addition, we present proofs of several results that appear in [7] without proof, as well as counterexamples to some claims made therein.

Introduction

A symmetric polynomial is a polynomial in n variables that is invariant under the action of S_{n} that permutes the variables. This definition can be generalized as follows: a multisymmetric polynomial is a polynomial in nr variables, divided into blocks of r variables each, that is invariant under the action of S_{n} that permutes the blocks, preserving the order of the variables within each block. The generalization makes more sense if we think of symmetric polynomials as regular functions on the product of n copies of the ground field k = k^{1} that are invariant under permutation of the copies. Then multisymmetric polynomials are the same except for the fact that the ground field k is replaced by the vector space k^{r}. The theory of multisymmetric polynomials has been studied both classically [7, 10] and recently [11].

Since k^{r} is isomorphic to the r-dimensional affine space A_{k}^{r}, we can further generalize symmetric polynomials by substituting other algebraic varieties for k. Substituting the rdimensional projective space P_{k}^{r} for k gives the homogeneous multisymmetric polynomials. These polynomials are also called factorizable forms. Given a set of n points in P_{k}^{r}, the homogeneous multisymmetric polynomials of multidegree (1, 1, …, 1) evaluated at the coordinates of the points are the coefficients of the Chow form [4] of the point set.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1999 Heldermann Verlag

Many of the results in Section 1 are found in [7] without proof. The main new results of this article are Proposition 1.10, Theorem 1.11, and Theorem 2.1.

1. Inhomogeneous multisymmetric functions

1.1. The ring of multisymmetric functions

Here we adapt Macdonald’s construction of the ring of ordinary symmetric functions [9]. Fix positive integers n and r, and let the symmetric group S_{n} act on the matrix of indeterminates

X = ( \begin{matrix}x_{1,1} & x_{1,2} & ⋯ & x_{1,r} \\ x_{2,1} & x_{2,2} & ⋯ & x_{2,r} \\ ⋮ & ⋮ & ... & ⋮ \\ x_{n,1} & x_{n,2} & ⋯ & x_{n,r} \end{matrix} )

by permuting the rows (that is, by left multiplication). Let

R_{n,r} = Z[x_{1,1}, x_{1,2}, …, x_{n,r}],

and let Λ_{n,r} be its invariant subring under the given action of S_{n}. We call Λ_{n,r} the ring of multisymmetric polynomials on (A^{r})^{n}. It has the induced grading

Λ_{n,r} = ⨁_{d=0}^{∞} Λ_{n,r}^{d}.

For fixed positive integers m, n, and r such that m ≥ n, there is a ring map

π_{m,n,r}: R_{m,r} → R_{n,r}

defined by

π_{m,n,r}(x_{i,j}) = \{ \begin{matrix}x_{i,j} & i ≤ n \\ 0 & i > n. \end{matrix}

Thinking of polynomials in R_{m,r} as functions of m points in A^{r}, this map specializes the last m − n points to the origin. In fact, this map is a map of graded rings, so it induces maps

π_{m,n,r}^{d}: R_{m,r}^{d} → R_{n,r}^{d}

on the graded pieces of R_{m,r} and R_{n,r}. We will abuse notation by also using π_{m,n,r} to denote the induced map from Λ_{m,r} to Λ_{n,r}, and similarly for π_{m,n,r}^{d}. For fixed positive integers r and d, the Abelian groups Λ_{n,r}^{d} and the maps π_{m,n,r}^{d} form an inverse system in the category of Abelian groups and homomorphisms. Let Λ_{r}^{d} be the inverse limit of this inverse system, that is,

Λ_{r}^{d} = lim_{←} Λ_{n,r}^{d},

and let Λ_{r} be the graded ring whose dth graded piece is Λ_{r,d}, that is,

Λ_{r} = ⨁_{d=0}^{∞} Λ_{r}^{d}.

We observe that, in fact, Λ_{r} is the inverse limit of the inverse system of graded rings Λ_{n,r} and graded ring maps π_{m,n,r} in the category of graded rings and maps. For fixed positive integers r and s such that r ≤ s, there is a graded ring map

π_{r,s}: Λ_{r} → Λ_{s}

defined by

π_{r,s}(x_{i,j}) = x_{i,j}.

The graded rings Λ_{r} and the graded ring maps π_{r,s} form a directed system in the category of graded rings and maps. Let Λ be the direct limit of this directed system in the category of (graded) rings and (graded) ring maps, that is,

Λ = lim_{→} Λ_{r}.

We call Λ the ring of multisymmetric functions.

1.2. Generators

Given a monomial m in the variables x_{i,j}, we may construct its symmetrization by summing over its orbit under the group action. The symmetrization of a monomial may also be called a symmetrized monomial or a monomial multisymmetric function. The additive group of the ring Λ is the free Abelian group generated by the symmetrizations (with respect to S_{∞}) of all monomials in the variables x_{i,j}. We will investigate its multiplicative structure later.

Given a monomial m in the variables x_{i,j}, we may construct its exponent matrix from the matrix X by replacing each variable by its exponent in the monomial m. If the exponent matrices of two monomials differ by a row permutation, then the monomials have the same symmetrization. Furthermore, rows in which all entries are zero may be ignored when computing symmetrizations. We will use the notation

m_{v_{1},v_{2},...,v_{k}}

to denote the symmetrization of the monomial with exponent matrix

( v_{1} v_{2} ⋯ v_{k} )^{T} .

We may assume that none of the vectors v_{i} are zero, and we may reorder them as necessary. For example,

m_{(1,1),(1,0)} = ∑_{i≠j} x_{i,1}x_{i,2}x_{j,1}.

We also distinguish two families of symmetrized monomials. The elementary multisymmetric functions are symmetrizations of monomials whose exponent matrices have only 0 and 1 as row sums. That is, each row of the matrix has at most one nonzero entry, which must be 1 if it exists. By contrast, the power sum multisymmetric functions are symmetrizations of monomials whose exponent matrices have only one nonzero row. These multisymmetric functions are uniquely determined by the vector v of column sums of the exponent matrix. Therefore, we denote them by e_{v} and p_{v}, respectively. For example,

e_{(2,1)} = m_{(1,0),(1,0),(0,1)} = ∑_{{i<j \atop k≠i,j}} x_{i,1}x_{j,1}x_{k,2}

and

p_{(2,1)} = m_{(2,1)} = ∑_{i} x_{i,1}^{2}x_{i,2}.

We will see in Section 1.3 that the elementary multisymmetric functions and the power sum symmetric functions generate the algebra Λ ⊗ Q. By contrast, we will see in Section 1.4 that the elementary multisymmetric functions do not generate Λ. (This differs from the case of ordinary symmetric functions, in which the elementary symmetric functions do generate the ring of symmetric functions.)

It will sometimes be more convenient to associate an elementary multisymmetric function to the unordered tuple (or multiset) listing the index of each column of the exponent matrix with multiplicity equal to the column sum. In this case we will use the notation

e′_{i_{1},i_{2},...,i_{k}}.

For example, e_{(2,1)} = e′_{1,1,2}.

The importance of the vectors of row and column sums of an exponent matrix is due to the fact that these are weight vectors of the actions of the diagonal tori (C^{∗})^{n} and (C^{∗})^{r} on the corresponding monomial, where (C^{∗})^{n} and (C^{∗})^{r} act on the matrix X by left and right multiplication, respectively.

Where we refer to ordinary symmetric functions, we will use Macdonald’s notation [9]. The reader familiar with ordinary symmetric functions will note that we have not defined complete homogeneous multisymmetric functions or Schur multisymmetric functions. If we define the complete homogeneous multisymmetric functions by analogy with the complete homogeneous symmetric functions, so that, for example,

h_{(2,1)} = ∑_{{i≤j \atop k}} x_{i,1}x_{j,1}x_{k,2},

then we have

Proposition 1.1. The complete homogeneous multisymmetric functions are not a generating set for the Q-algebra Λ ⊗ Q.

Proof. In the example above, it is easy to see that h_{(2,1)} factors as h_{(2,0)}h_{(0,1)}. In general, we have

h_{(v_{1},v_{2},...,v_{n})} = h_{v_{1}e_{1}}h_{v_{2}e_{2}} ⋯ h_{v_{n}e_{n}}.

Thus the complete homogeneous multisymmetric functions are products of the complete homogeneous symmetric functions in each of the columns of the matrix X from Section 1.1. The complete homogeneous symmetric functions are polynomials in the elementary symmetric functions. However, the function e_{(1,1,0,0,...,0)} is not a polynomial in the other elementary multisymmetric functions; otherwise there would be a relation of degree 2, which cannot happen by Lemma 1.7. □

(An alternative method of proof is to observe that the complete homogeneous symmetric polynomials in the columns of X are algebraically independent, and so generate a polynomial ring. But the rings of multisymmetric polynomials are not polynomial rings by Theorem 1.5.)

In order to generalize Schur polynomials, it would be necessary to characterize Λ as a representation ring.

1.3. Conversion algorithms

Theorem 1.2. [7] The power sum multisymmetric functions generate the algebra Λ ⊗ Q.

Proof. Consider the product

p_{v}m_{v_{1},v_{2},...,v_{k}}.

It may be decomposed into two kinds of terms; “cross terms”, in which the variables contributed by the power sum multisymmetric function have a different first index than any of the variables contributed by the monomial multisymmetric function, and “non-cross terms”, in which some of the variables have the same first index. The “cross terms” add up to

m_{v,v_{1},v_{2},...,v_{k}},

and the “non-cross terms” add up to

∑_{i=1}^{k} m_{v_{1},v_{2},...,v_{i}+v,...,v_{k}}.

Actually, this formula is correct only when none of the monomial multisymmetric functions have repeated indexing vectors. When such a monomial multisymmetric function appears in this formula, it must be multiplied by the product of the factorials of the multiplicities of its indexing vectors. For example, in

m_{v_{1},v_{2},v_{2},v_{3},v_{3},v_{3}}

the vector v_{i} appears with multiplicity i, so this monomial multisymmetric function should be multiplied by 1!2!3! = 12. We can now use the formula

p_{v}m_{v_{1},v_{2},...,v_{k}} = m_{v,v_{1},v_{2},...,v_{k}} + ∑_{i=1}^{k} m_{v_{1},v_{2},...,v_{i}+v,...,v_{k}}  (1)

to express any monomial multisymmetric function in terms of power sums and monomial multisymmetric functions involving fewer rows. For example,

2m_{(1,0),(1,0),(0,1)} = p_{(1,0)}m_{(1,0)(0,1)} − m_{(2,0),(0,1)} − m_{(1,0),(1,1)}.

Applying this formula recursively rewrites any monomial multisymmetric function as a polynomial in the power sum multisymmetric functions with rational coefficients. □

Theorem 1.3. [7] The elementary multisymmetric functions generate the algebra Λ ⊗ Q.

Proof. We assume the Newton relations

ne_{n} + ∑_{i=1}^{n−1}(−1)^{i}p_{i}e_{n−i} + (−1)^{n}p_{n} = 0

from the theory of ordinary symmetric functions. Now the ring of ordinary symmetric functions is the invariant subring of Z[x_{1}, x_{2}, …] under permutation of the variables. Let λ_{1}, λ_{2}, … be indeterminates and substitute

x_{i} = ∑_{j} λ_{j}x_{i,j}.

The coefficient of λ_{1}^{n_{1}}λ_{2}^{n_{2}} ⋯ λ_{k}^{n_{k}} in e_{n} is e_{(n_{1},n_{2},...,n_{k})}, and the corresponding coefficient in p_{n} is

\binom{n}{n_{1}, n_{2}, …, n_{k}}p_{(n_{1},n_{2},...,n_{k})}.

The resulting relations may be written as

|v|e_{v} + ∑_{{v=v_{1}+v_{2} \atop v_{1},v_{2}≠0}} (−1)^{|v_{1}|}\binom{|v_{1}|}{v_{1}}p_{v_{1}}e_{v_{2}} + (−1)^{|v|}\binom{|v|}{v}p_{v} = 0

where | · | is the 1-norm and the parentheses indicate the multinomial coefficient

\binom{n}{(n_{1}, n_{2}, …, n_{l})} = \frac{n!}{∏_{i=1}^{l} n_{i}!}.

We can now use this formula to express power sum multisymmetric functions in terms of elementary multisymmetric functions and power sums of lower degree. For example,

3p_{(2,1)} = p_{(2,0)}e_{(0,1)} + 2p_{(1,1)}e_{(1,0)} − p_{(1,0)}e_{(1,1)} − p_{(0,1)}e_{(2,0)} + 3e_{(2,1)}.

Applying the formula recursively rewrites any power sum multisymmetric function as a polynomial in the elementary multisymmetric functions with rational coefficients. □

Of course, the relations above may be used to convert polynomials in the elementary multisymmetric functions to polynomials in the power sum multisymmetric functions and thence to Q-linear combinations of monomial multisymmetric functions by applying them in the reverse order.

The complexity of the conversion algorithms in this section is necessarily bounded below by the size of the output. Let B(n) be the nth Bell number, which is the number of ways of dividing a set of n elements into disjoint subsets. It is known that B(n) grows faster than e^{n} as n grows arbitrarily large.

Proposition 1.4. The representation of m_{(e_{1},e_{2},...,e_{k})} = e_{(1,1,...,1)} as a polynomial in the generalized Newton power sums contains B(k) terms, as does the representation of p_{(1,1,...,1)} in terms of elementary multisymmetric functions.

Proof. We use the Newton relations to express e_{k} in terms of power sums and p_{k} in terms of elementary symmetric functions. The resulting formulas may be found in §3 of [7], for example:

(−1)^{k−1} \frac{1}{k}p_{k} = ∑(−1)^{λ_{1}+λ_{2}+···+λ_{k}−1} \frac{(λ_{1} + λ_{2} + ⋯ + λ_{k} − 1)!}{λ_{1}!λ_{2}! ⋯ λ_{k}!}e_{1}^{λ_{1}}e_{2}^{λ_{2}} ⋯ e_{k}^{λ_{k}}

and

(−1)^{k−1}e_{k} = ∑ \frac{(−1)^{λ_{1}+λ_{2}+···+λ_{k}−1}}{λ_{1}!λ_{2}! ⋯ λ_{k}!} (\frac{p_{1}}{1} )^{λ_{1}} (\frac{p_{2}}{2} )^{λ_{2}} ⋯ (\frac{p_{k}}{k} )^{λ_{k}}

where the sums are taken over all partitions λ = 1^{λ_{1}}2^{λ_{2}} … k^{λ_{k}} of k. We ignore the coefficients except to note that they are nonzero. These formulas imply that the representations of e_{k} in terms of power sums and of p_{k} in terms of elementary symmetric functions have a nonzero term corresponding to each partition of k.

When we make the substitution x_{i} = ∑_{j} λ_{j}x_{i,j} as above and compute the coefficient of λ_{1}λ_{2} ⋯ λ_{k} on each side, we obtain a nonzero term corresponding to each partition of the set {1, 2, …, k}, because all the underlying partitions of k appear in the formulas above. Since the number of partitions of {1, 2, …, k} is B(k), the number of terms in the expansions of e_{(1,1,...,1)} and p_{(1,1,...,1)} is also B(k). □

If we write the function e_{(1,1,...,1)} (k ones) as a monomial multisymmetric function, the size of the input is k^{2}, the number of entries in the exponent matrix. If we leave it in the form of an elementary multisymmetric function, the size of the input is the number of entries in the indexing vector, which is k. Therefore, converting monomial multisymmetric functions to generalized Newton power sums has worst-case complexity at least O(B(\sqrt{size of input})), and converting between elementary multisymmetric functions and generalized Newton power sums has worst-case complexity at least O(B(size of input)). However, in practice these algorithms seem to work well, much as Gröbner bases do despite their double-exponential worst-case complexity.

1.4. Relations

We recall

Theorem 1.5. (Shephard-Todd-Chevalley theorem [14, 3, 13]) The ring of invariants C[x]^{G} of a finite group G is a polynomial ring if and only if the group has a generating set that acts by pseudoreflections on C[x]_{1}.

(A pseudoreflection has exactly one eigenvalue that is not 1.) In the case of multisymmetric functions, all the eigenvalues of the action of a group element occur with multiplicity divisible by r. When r > 1, this means that no element of S_{n} acts by a pseudoreflection, so for n > 1 (S_{n} ≠ {e}), Λ_{n,r} is not a polynomial ring.

For integers n, r > 1, we can also see that the elementary multisymmetric polynomials are algebraically dependent in Λ_{n,r} by the fact that there are \binom{n+r}{r} − 1 > nr elementary multisymmetric polynomials in nr variables. (The inequality is an easy induction on r.) By contrast,

Theorem 1.6. The elementary multisymmetric functions are algebraically independent in Λ.

Proof. We begin with a lemma about the degrees of algebraic relations among elementary multisymmetric polynomials. Fix n and r, and let S_{n,r} be the polynomial ring Z[ y_{v} | v ∈ N^{r}, 0 < |v| ≤ n] whose variables correspond to the elementary multisymmetric polynomials e_{v} in Λ_{n,r} and have the same degrees, that is, the degree of y_{v} is just the 1-norm of v. Let I_{n,r} be the kernel of the ring map σ_{n,r}: S_{n,r} → Λ_{n,r} that takes y_{v} to e_{v}.

Lemma 1.7. The nonzero elements of I_{n,r} have degree at least n + 2.

Proof. We compute the Hilbert functions of S_{n,r} ⊗ Q and Λ_{n,r} ⊗ Q. The number of ways to select r of n objects with replacement is \binom{n+r−1}{r}. This is also the number of nonnegative integer vectors of length n and 1-norm r; just assign an object to each position in the vector, and let the corresponding entry be the number of times the object was chosen.

Given a monomial in the elementary multisymmetric polynomials, we may form an exponent matrix by stacking the indexing vectors of the factors on top of one another. The row sums of this matrix form a partition of the degree of the monomial. The sizes of the parts of the partition are then at most n. Conversely, any matrix whose row sums are at most n corresponds to a nonzero monomial in the elementary multisymmetric polynomials. Therefore, the Hilbert function of S_{n,r} ⊗ Q in degree d may be computed by counting the distinct matrices (up to row permutations) whose row sums form a partition of d with parts of size at most n.

Given a monomial multisymmetric polynomial, the row sums of its exponent matrix also form a partition of the degree, and the number of parts is at most n. Conversely, any matrix with at most n rows corresponds to a monomial multisymmetric polynomial. Therefore, the Hilbert function of Λ_{n,r} ⊗ Q in degree d may be computed by counting the distinct matrices (up to row permutations) whose row sums form a partition of d with at most n parts.

Given a partition p = 1^{i_{1}}2^{i_{2}} … k^{i_{k}}, we can count the number of distinct matrices (up to row permutations) with the given row sum partition. For each j between 1 and k, we must choose with replacement i_{j} vectors of length r and 1-norm j. These choices are independent, so the total number of possible choices is

f(p, r) = ∏_{j=1}^{k} \binom{\binom{r+j−1}{j} + i_{j} − 1}{i_{j}}.

When d ≤ n, the sets of possible row sum partitions are the same for matrices corresponding to monomials in the elementary multisymmetric polynomials and for matrices corresponding to monomial multisymmetric polynomials. Furthermore, when d = n + 1, the only difference between the two sets is that the first contains the partition 1^{n+1} and the second contains the partition n + 1 instead. But f takes the same value on these partitions:

f(1^{n+1}, r) = \binom{\binom{r+1−1}{1} + n + 1 − 1}{n + 1} = \binom{\binom{r}{1} + n}{n + 1} = \binom{r + n}{n + 1} and
f(n + 1, r) = \binom{\binom{r+n+1−1}{n+1} + 1 − 1}{1} = \binom{\binom{r+n}{n+1}}{1} = \binom{r + n}{n + 1}.

Therefore, the Hilbert functions of S_{n,r} ⊗ Q and Λ_{n,r} ⊗ Q are the same in degrees less than n + 2. Since σ_{n,r} ⊗ Q is onto by the algorithms of the previous section, it follows that it must be one-to-one on the degree d parts for d < n + 2. Therefore, the nonzero elements of I_{n,r} must have degree at least n + 2. □

We now continue the proof of the theorem. Suppose that f is an algebraic relation among the elementary multisymmetric functions in Λ. That is, let S be the polynomial ring over Q in the variables y_{v}, where v ranges over all nonnegative integer vectors of finite length whose last entries are positive. Then we have the obvious map σ: S → Λ. Suppose that f is in the kernel of σ. It must be homogeneous with respect to the grading deg y_{v} = |v|, so let d be its degree with respect to this grading. Each term of f is in Λ, hence in some Λ_{r} by construction. Since f is a polynomial, it has finitely many terms, and so can be written as a relation among the elementary multisymmetric functions in Λ_{r} for some fixed r. Now project f from Λ_{r} to Λ_{d,r} using the natural map. No term of f vanishes under the projection, since none of the elementary multisymmetric functions involved has degree larger than d. Therefore, f projects to a nonzero relation of degree d among the elementary multisymmetric polynomials in Λ_{d,r}, contradicting the lemma. Thus there are no algebraic relations among the elementary multisymmetric functions in Λ. □

We can make the same argument using power sum multisymmetric functions in the place of the elementary multisymmetric functions, so that the power sum multisymmetric functions are also algebraically independent in Λ. This proves that Λ ⊗ Q = S, which is just a polynomial ring in countably many variables, and thus the conversions performed by the algorithms of the previous section have a unique result.

As mentioned in Section 1.2, and in contrast to the case of ordinary symmetric functions, the elementary multisymmetric functions are not a generating set for the ring Λ. For example,

p_{(1,1,1)} = e_{(1,0,0)}e_{(0,1,0)}e_{(0,0,1)} −

− \frac{1}{2} (e_{(0,1,1)}e_{(1,0,0)} + e_{(1,0,1)}e_{(0,1,0)} + e_{(1,1,0)}e_{(0,0,1)}) + \frac{1}{2}e_{(1,1,1)}

and

p_{(2,2)} = e_{(1,0)}^{2}e_{(0,1)}^{2} − \frac{2}{3} (e_{(2,0)}e_{(0,1)}^{2} + 2e_{(1,0)}e_{(1,1)}e_{(0,1)} + e_{(0,2)}e_{(1,0)}^{2}) +

+ \frac{1}{3} (e_{(1,1)}^{2} + 2e_{(2,0)}e_{(0,2)}) + \frac{2}{3} (e_{(2,1)}e_{(0,1)} + e_{(1,2)}e_{(1,0)}) − \frac{2}{3}e_{(2,2)}.

Since conversions between power sum and elementary multisymmetric functions are unique, either of these conversion equations shows that the elementary multisymmetric functions are not a basis for Λ. Both examples are included in order to show precisely which rings Λ_{n,r} are generated by the elementary multisymmetric polynomials.

Since there are no relations of degree 3 in I_{n,r} for any n and r, the expansion of p_{(1,1,1)} proves that the elementary multisymmetric polynomials do not generate Λ_{n,r} for n ≥ 2 and r ≥ 3. (If n = 1, then p_{(1,1,1)} = e_{(1,0,0)}e_{(0,1,0)}e_{(0,0,1)}.) Since there are no relations of degree 4 in I_{n,r} for n > 2, the expansion of p_{(2,2)} proves that the elementary multisymmetric polynomials do not generate Λ_{n,r} for n ≥ 3 and r ≥ 2. Thus the only cases where the elementary multisymmetric polynomials generate Λ_{n,r} are n = 1 (the group action is trivial), r = 1 (the ordinary symmetric polynomials), and n = r = 2.

In Λ_{2,2}, we have the conversion equation

p_{(2,2)} = e_{(1,0)}^{2}e_{(0,1)}^{2} − e_{(2,0)}e_{(0,1)}^{2} − e_{(1,0)}e_{(1,1)}e_{(0,1)} − e_{(0,2)}e_{(1,0)}^{2} + 2e_{(2,0)}e_{(0,2)}.

In fact, we have the following

Theorem 1.8. The elementary multisymmetric polynomials generate Λ_{2,2} as an algebra over the integers (that is, as a ring).

Proof. We will show that

B = {e_{(1,0)}, e_{(0,1)}, e_{(2,0)}, e_{(0,2)}} ∪ { m_{(n,0),(0,1)} | n ≥ 1 }

is a SAGBI basis [12] for Λ_{2,2} with respect to the reverse lexicographic term order with x_{1,1} > x_{1,2} > x_{2,1} > x_{2,2}. The theorem follows immediately because m_{(0,0),(0,1)} = e_{(0,1)}, m_{(1,0),(0,1)} = e_{(1,1)}, and

m_{(n,0),(0,1)} = e_{(1,0)}m_{(n−1,0),(0,1)} − e_{(2,0)}m_{(n−2,0),(0,1)},

so by induction on n, m_{(n,0),(0,1)} is a polynomial in the elementary multisymmetric polynomials with integer coefficients.

The initial terms of B are x_{1,1}, x_{1,2}, x_{1,1}x_{2,1}, x_{1,2}x_{2,2}, and x_{1,2}x_{2,1}^{n}. We claim that they generate the initial subalgebra of Λ_{2,2} with respect to the given order. Let f be a multisymmetric polynomial in Λ_{2,2}. It is a unique linear combination of monomial multisymmetric polynomials, so its initial term is the initial term of a monomial multisymmetric polynomial. Let (m_{ij}) be the exponent matrix of the initial term of f. Then either m_{12} > m_{22} or m_{12} = m_{22} and m_{11} ≥ m_{21}, otherwise interchanging the rows would produce a larger term of f in the term order. If the first case holds, then the initial term of f may be written as

(x_{1,1})^{m_{11}}(x_{1,2})^{m_{12}−m_{22}−1}(x_{1,2}x_{2,1}^{m_{21}})(x_{1,2}x_{2,2})^{m_{22}};

if the second case holds, then the initial term of f may be written as

(x_{1,1})^{m_{11}−m_{21}}(x_{1,2}x_{2,2})^{m_{12}}(x_{1,1}x_{2,1})^{m_{21}}.

Therefore the initial subalgebra of Λ_{2,2} is generated by the initial terms of B, which means that B is a SAGBI basis. Since the coefficients of the polynomials in B are all ±1, the subduction process cannot introduce denominators. □

Having obtained some information about the degrees of the relations on the rings Λ_{n,r}, we now consider how to go about computing some of them. In the big ring Λ ⊗ Q = S, every monomial multisymmetric function has a unique representation as a polynomial in the elementary multisymmetric functions. Any monomial multisymmetric function with more than n indexing vectors projects to zero in Λ_{n,r}. Therefore, we can write it as a polynomial in the elementary multisymmetric functions and project this polynomial onto S_{n,r} to obtain a relation. This method is described in §11 of [7].

Proposition 1.9. The relations obtained in this fashion generate I_{n,r} as a vector space.

Proof. Let f ∈ I_{n,r}. Then f ∈ S_{n,r}, and σ_{n,r}(f) = 0. Let g be the image of f under the embedding of S_{n,r} into S in which y_{v} ↦ y_{v}. Then g projects to zero in Λ_{n,r}. Write g as a linear combination of monomial multisymmetric functions. These multisymmetric functions must vanish in Λ_{n,r}. They cannot involve vectors with more than r entries, because g does not. Therefore, they must have more than n indexing vectors, and so we have written f as a linear combination of multisymmetric functions with more than n indexing vectors. □

In fact, if we settle for generating I_{n,r} as an ideal, we can use equation (1) to express any monomial multisymmetric function with more than n indexing vectors as a member of the ideal generated by the monomial multisymmetric functions with exactly n + 1 indexing vectors. (Unfortunately, this is still an infinite generating set.)

For example, the unique relation on Λ_{2,2} may be obtained from m_{(2,0),(0,1),(0,1)} in this fashion. In Λ ⊗ Q, this monomial multisymmetric function may be written as

\begin{matrix}\frac{1}{3}e_{(0,2)}e_{(1,0)}^{2} + \frac{1}{3}e_{(2,0)}e_{(0,1)}^{2} − \frac{4}{3}e_{(0,2)}e_{(2,0)} − \frac{1}{3}e_{(0,1)}e_{(1,1)}e_{(1,0)} \\ +\frac{1}{3}e_{(1,1)}^{2} − \frac{1}{3}e_{(2,1)}e_{(0,1)} + \frac{2}{3}e_{(1,2)}e_{(1,0)} − \frac{2}{3}e_{(2,2)} \end{matrix}

When we project to S_{2,2}, the last three terms disappear. We multiply the result by three to obtain

e_{(0,2)}e_{(1,0)}^{2} + e_{(2,0)}e_{(0,1)}^{2} − 4e_{(0,2)}e_{(2,0)} − e_{(0,1)}e_{(1,1)}e_{(1,0)} + e_{(1,1)}^{2} = 0.

The following is an approximate translation of two paragraphs in Section 16.4 of [7]. Junker uses r for the size of the symmetric group in the original, which has been changed to n below to match the notation in the rest of this article:

If one wants to obtain the complete relations for some Λ_{n,r}, it is enough to compute the relations of minimal degree for each n. All higher relations for smaller n are directly contained in these. A relation of weight n + 2 may be expressed in the form:

R_{2} + R_{3} + R_{4} + ⋯ + R_{n} = 0

where, for example, R_{i} denotes a polynomial of degree n + 2 in which each term involves an elementary multisymmetric polynomial of degree i, but none of higher degree. Then

R_{2} = 0

is a relation on Λ_{2,r},

R_{2} + R_{3} = 0

is a relation on Λ_{3,r},

R_{2} + R_{3} + R_{4} = 0

is a relation on Λ_{4,r}, and generally

R_{2} + R_{3} + R_{4} + ⋯ + R_{i} = 0

is a relation on Λ_{i,r}.

This claim implies that I_{n,r} is generated by its degree n + 2 part (the relations of minimal degree) together with the image of I_{n+1,r} in S_{n,r} (the higher relations). We will give a counterexample to this claim. First, let us further abuse notation by using π_{m,n,r} (where m > n) to denote the projection from S_{m,r} onto S_{n,r} defined by y_{v} ↦ y_{v}, as well as the previously defined maps from R_{m,r} onto R_{n,r} and from Λ_{m,r} onto Λ_{n,r}.

Proposition 1.10. The relation in I_{3,6} that comes from

m_{(1,1,0,0,0,0),(0,0,1,1,0,0),(0,0,0,0,1,0),(0,0,0,0,0,1)}

is not in the ideal generated by π_{4,3,6}(I_{4,6}) and the degree 5 part of I_{3,6}.

Remark. Using the “ms” package, this relation can be computed by typing

truncate(toe(m(a*b,c*d,f,g)),3);

Proof. Let J be the ideal of S_{3,6} generated by the degree 5 part of I_{3,6}. Then Junker’s claim implies that the diagram

S_{4,6}  ⟶^{π_{4,3,6}} S_{3,6}/J
↓σ_{4,6}  ↓σ_{3,6}
Λ_{4,6} ⊗ Q ⟶^{π_{4,3,6}} Λ_{3,6} ⊗ Q

is a fiber square. So let

Q = (S_{3,6}/J) ⊗_{S_{4,6}} (Λ_{4,6} ⊗ Q).

The kernel of the natural map Λ_{4,6} ⊗ Q → Q is then

K = σ_{4,6}(π_{4,3,6}^{−1}(J)).

The ideal K is generated by the images of the generators of J and the images of the elementary multisymmetric polynomials of degree 4, which generate the kernel of π_{4,3,6}: S_{4,6} → S_{3,6}. We will show by a dimension count that K is not the kernel of π_{4,3,6}: Λ_{4,6} → Λ_{3,6}.

Consider the multigraded piece of K on which the vector of column sums is (1, 1, 1, 1, 1, 1). We will compute a basis for this Q-vector space by analyzing the contributions from the generators of the ideal K. The elementary multisymmetric polynomials of degree 4 contribute 15 polynomials of the form e′_{1,2,3,4}e′_{5,6} and 15 polynomials of the form e′_{1,2,3,4}e′_{5}e′_{6}. The monomial multisymmetric polynomials of degree 5 (which generate J) contribute 60 polynomials of the form

m_{(1,1,0,0,0,0),(0,0,1,0,0,0),(0,0,0,1,0,0),(0,0,0,0,1,0)}e_{(0,0,0,0,0,1)}

for a generating set of 90 polynomials. However, the 15 polynomials of the form e′_{1,2,3,4}e′_{5}e′_{6} can each be expressed as a linear combination of the last 60 polynomials in two different ways, using equation (1) and the fact that e′_{k} = p_{e_{k}}. In particular, e′_{1,2,3,4}e′_{5}e′_{6} may be expressed as

m_{e_{1}+e_{5},e_{2},e_{3},e_{4}}e′_{6} + m_{e_{2}+e_{5},e_{1},e_{3},e_{4}}e′_{6} + m_{e_{3}+e_{5},e_{1},e_{2},e_{4}}e′_{6} + m_{e_{4}+e_{5},e_{1},e_{2},e_{3}}e′_{6}

or

m_{e_{1}+e_{6},e_{2},e_{3},e_{4}}e′_{5} + m_{e_{2}+e_{6},e_{1},e_{3},e_{4}}e′_{5} + m_{e_{3}+e_{6},e_{1},e_{2},e_{4}}e′_{5} + m_{e_{4}+e_{6},e_{1},e_{2},e_{3}}e′_{5}

where the boldface e_{i} in the subscripts denote the standard basis vectors for Z^{6}. (Note that the cross terms vanish in Λ_{4,6} because they have 5 indexing vectors, and that no indexing vectors occur with multiplicity greater than 1.) Thus there are only 60 linearly independent polynomials in K_{(1,1,1,1,1,1)}.

On the other hand, there are 65 linearly independent polynomials of degree (1, 1, 1, 1, 1, 1) in the kernel of π_{4,3,6}: Λ_{4,6} → Λ_{3,6}; of these, 20 have the form

m_{(1,1,1,0,0,0),(0,0,0,1,0,0),(0,0,0,0,1,0),(0,0,0,0,0,1)}

and 45 have the form

m_{(1,1,0,0,0,0),(0,0,1,1,0,0),(0,0,0,0,1,0),(0,0,0,0,0,1)}.

This shows that Q ≠ Λ_{3,6}, so that Junker’s claim is already false.

In fact, a computation using MAPLE [2] shows that the relations of the first form are in K, whereas the relations of the second form are not. To finish the proof of the proposition, we note that the kernel of the natural map from S_{3,6} to Q is generated by J and π_{4,3,6}(I_{4,6}). The multisymmetric polynomial

f = m_{(1,1,0,0,0,0),(0,0,1,1,0,0),(0,0,0,0,1,0),(0,0,0,0,0,1)}

in Λ_{4,6} maps to a nonzero element q ∈ Q, which lies in the kernel of the map from Q to Λ_{3,6} defined by the universal property of the tensor product. Take any element g ∈ σ_{4,6}^{−1}(f). Then π_{4,3,6}(g) maps to q under the tensor product map. Thus π_{4,3,6}(g) is an element of I_{3,6} that is not in the ideal generated by J and π_{4,3,6}(I_{4,6}). □

Although Junker’s claim is false, a weaker statement can be derived:

Theorem 1.11. The ideal I_{n,r} is the radical of the image of I_{n+1,r} under the map

π_{n+1,n,r}: S_{n+1,r} → S_{n,r}.

Proof. The sequence of maps

S_{n,r}→ → Λ_{n,r} ↪ R_{n,r}

dualizes to the sequence

A^{nr}→ → Sym^{n}A^{r} ↪ A^{\binom{n+r}{r}−1}.

We then have the diagram

A^{nr}  ⟶^{p_{n}} Sym^{n}A^{r}  ⟶^{i_{n}} A^{\binom{n+r}{r}−1}
↓j  ↓j  ↓j
A^{(n+1)r} ⟶^{p_{n+1}} Sym^{n+1}A^{r} ⟶^{i_{n+1}} A^{\binom{n+1+r}{r}−1}

where the vertical maps dualize the projection maps π_{n+1,n,r}. We claim that Sym^{n}A^{r} is the set-theoretic intersection of Sym^{n+1}A^{r} and A^{\binom{n+r}{r}−1}. That is, the right-hand square in the diagram is a pullback square in the category of algebraic varieties. To show this, we first compute X = p_{n+1}^{−1}(i_{n+1}^{−1}(j(A^{\binom{n+r}{r}−1}))).

The variety j(A^{\binom{n+r}{r}−1}) is defined by the equations y_{v} = 0 for all vectors v ∈ N^{r} with 1norm n+1. Its preimage under i_{n+1} is then defined by setting all elementary multisymmetric polynomials of degree n + 1 to zero. Now the elementary multisymmetric polynomials of degree n + 1 in Λ_{n+1,r} are the coefficients of

∏_{i=1}^{n+1} ∑_{j=1}^{r} λ_{j}x_{i,j}

with respect to the variables λ_{j}. If this function is identically zero for some specialization of the variables x_{i,j}, then one of the factors must be identically zero. This means that for the corresponding value of i all of the variables x_{i,j} vanish.

For a fixed i between 1 and n + 1, let X_{i} be the subspace of A^{(n+1)r} on which the variables x_{i,j} are zero for j = 1, 2, …, r. The subvariety X of A^{(n+1)r} on which the elementary multisymmetric polynomials of degree n + 1 are all zero is then X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{n+1} by the previous paragraph.

The S_{n+1}-action on A^{(n+1)r} permutes the components X_{i} of X symmetrically, so p_{n+1}(X_{i}) is independent of i. Therefore,

p_{n+1}(X) = p_{n+1}(X_{n+1}) = p_{n+1}(j(A^{nr}))
= j(p_{n}(A^{nr})) = j(Sym^{n}A^{r}).

Since p_{n+1} is onto, we have

j(Sym^{n}A^{r}) = i_{n+1}^{−1}(j(A^{\binom{n+r}{r}−1})),

that is, Sym^{n}A^{r} is the set-theoretic pullback of A^{\binom{n+r}{r}−1} along i_{n+1}.

Dualizing again, we see that the ideal of j^{−1}(Sym^{n+1}A^{r}) as a subvariety of A^{\binom{n+r}{r}−1} is π_{n+1,n,r}(I_{n+1,r}). This ideal has the same variety as the ideal I_{n,r} (which is radical because it was defined as the ideal of relations on a set of parameters), so the radical of π_{n+1,n,r}(I_{n+1,r}) is I_{n,r} by the Hilbert Nullstellensatz. □

2. Homogeneous multisymmetric functions

2.1. The ring of homogeneous multisymmetric functions

The construction of the ring of homogeneous multisymmetric functions is entirely analogous to that of the ring of (inhomogeneous) multisymmetric functions. As before, fix positive integers n and r, and let the symmetric group S_{n} act on the matrix of indeterminates

X̂ = ( \begin{matrix}x_{1,0} & x_{1,1} & ⋯ & x_{1,r} \\ x_{2,0} & x_{2,1} & ⋯ & x_{2,r} \\ ⋮ & ⋮ & ... & ⋮ \\ x_{n,0} & x_{n,1} & ⋯ & x_{n,r} \end{matrix} )

by permuting the rows. Let Λ̂_{n,r} be the multigraded invariant subring of the polynomial ring Z[x_{1,0}, x_{1,1}, …, x_{n,r}] under the given action of S_{n} and the grading in which x_{i,j} has weight e_{i}. We call Λ̂_{n,r} the ring of multisymmetric polynomials on (P^{r})^{n}. It has a natural Z-grading

Λ̂_{n,r} = ⨁_{d=0}^{∞} Λ̂_{n,r}^{d}

in which Λ̂_{n,r}^{d} consists of the multihomogeneous invariant polynomials of degree (d, d, …, d). (Note that, in order for a multihomogeneous polynomial to be invariant under the action of S_{n}, its multidegree must be invariant under the induced action.) For fixed positive integers m, n, and r such that m ≥ n, there is a natural ring map

π_{m,n,r}: Λ̂_{m,r} → Λ̂_{n,r}

defined by

π_{m,n,r}(x_{i,j}) = \{ \begin{matrix}x_{i,j} & i ≤ n \\ 1 & i > n, j = 0 \\ 0 & i > n, j > 0. \end{matrix}

Thinking of polynomials in Λ̂_{m,r} as functions of m points in P^{r}, this amounts to specializing the last m − n points to the standard coordinate point (1 : 0 : 0 : ⋯: 0). In fact, this map is a map of graded rings, so the graded rings Λ̂_{n,r} and graded ring maps π_{m,n,r} form an inverse system in the category of graded rings and maps. Let Λ̂_{r} be the inverse limit of this inverse system. For fixed positive integers r and s such that r ≤ s, there is a natural graded ring map

π_{r,s}: Λ̂_{r} → Λ̂_{s}

defined by

π_{r,s}(x_{i,j}) = x_{i,j}.

The graded rings Λ̂_{r} and the graded ring maps π_{r,s} form a directed system in the category of graded rings and maps. Let Λ̂ be the direct limit of this directed system. We call Λ̂ the ring of homogeneous multisymmetric functions. It has a special element ê that corresponds roughly to twisting; in each Λ_{n,r}, this element specializes to e_{(n,0,0,...,0)}. The quotient of Λ̂ by the principal ideal ê− 1 is Λ, because specializing e_{(n,0,0,...,0)} to 1 amounts to dehomogenizing with respect to the variables x_{i,0} for i = 1, 2, …, n.

2.2. Generators

Given any “monomial” m whose multidegree (weight with respect to the left action of the diagonal torus) has the form (d, d, …) and whose exponent matrix has all but finitely many rows of the form (d, 0, 0, …, 0), we call the symmetrization of m a monomial homogeneous multisymmetric function. The additive group of the ring Λ̂ is the free Abelian group generated by all monomial homogeneous multisymmetric functions.

We will use the notation

m_{v_{0},v_{1},...,v_{k}}

to denote the symmetrization of the “monomial” with exponent matrix

( v_{0} v_{1} ⋯ v_{k} de_{0} de_{0} ⋯)^{T} .

We may assume that none of the vectors v_{i} are zero, and we may reorder them as necessary. For example,

m_{(0,1,1),(1,1,0)} = ∑_{i≠j} x_{i,1}x_{i,2}x_{j,0}x_{j,1} ∏_{k≠i,j} x_{k,0}^{2}.

We also distinguish two families of symmetrized monomials. The homogeneous generalized Newton power sums are monomial multisymmetric functions with at most one indexing vector not of the form (d, 0, 0, …, 0). For example,

p_{(1,1,1)} = m_{(1,1,1)} = ∑_{i} x_{i,0}x_{i,1}x_{i,2} ∏_{j≠i} x_{j,0}^{3}.

The elementary homogeneous multisymmetric functions are symmetrizations of monomials whose exponent matrices have all row sums equal to 1. That is, each row of the matrix has exactly one nonzero entry, which must be 1. These multisymmetric functions are uniquely determined by the vector v of column sums of the exponent matrix. Therefore, we denote them by e_{v}. For example,

e_{(∞,2,1)} = m_{(0,1,0),(0,1,0),(0,0,1)} = ∑_{{i<j \atop k≠i,j}} x_{i,1}x_{j,1}x_{k,2} ∏_{l≠i,j,k} x_{l,0}.

It will sometimes be more convenient to associate an elementary multisymmetric function to the unordered tuple (or multiset) listing the index of each column of the exponent matrix (except the first) with multiplicity equal to the column sum. In this case we will use the notation

e′_{i_{1},i_{2},...,i_{k}}.

For example, e_{(∞,2,1)} = e′_{1,1,2}.

When describing homogeneous multisymmetric polynomials in one of the rings Λ̂_{n,r}, we will usually not omit the indexing vectors of the form (d, 0, 0, …, 0) from our notation for general monomial homogeneous multisymmetric functions, nor will we omit the index 0 from the e′ notation. For example, in Λ̂_{3,2} we would write m_{(0,1,1),(1,1,0),(2,0,0)} instead of m_{(0,1,1),(1,1,0)} and m_{(1,1,1),(3,0,0),(3,0,0)} instead of p_{(1,1,1)}. Similarly, in Λ̂_{6,2} we would write e_{(3,2,1)} = e′_{0,0,0,1,1,2} instead of e_{(∞,2,1)} = e′_{1,1,2}.

Whereas the elementary multisymmetric functions generate the ring of multisymmetric functions over the rationals, the corresponding result is false in the homogeneous case for any field. Some homogeneous multisymmetric functions can be expressed only as rational functions of the elementary homogeneous multisymmetric functions. For example, a Macaulay [1] calculation shows that the polynomial m_{(2,0,0),(0,2,0),(0,0,2)} in Λ̂_{3,2} cannot be expressed as a polynomial in the elementary homogeneous multisymmetric polynomials, but it can be expressed as a rational function:

m_{(2,0,0),(0,2,0),(0,0,2)} = −\frac{4e_{(1,2,0)}e_{(2,0,1)}^{2}}{3e_{(3,0,0)}} + \frac{4e_{(2,1,0)}e_{(2,0,1)}e_{(1,1,1)}}{3e_{(3,0,0)}} − \frac{1}{3}e_{(1,1,1)}^{2}

−\frac{2}{3}e_{(2,0,1)}e_{(0,2,1)} − \frac{4e_{(2,1,0)}^{2}e_{(1,0,2)}}{3e_{(3,0,0)}} + \frac{10}{3}e_{(1,2,0)}e_{(1,0,2)}

−\frac{2}{3}e_{(2,1,0)}e_{(0,1,2)}.

Theorem 2.1. The elementary homogeneous multisymmetric polynomials do not generate Λ̂_{n,r} ⊗ Q in degree d for n > d ≥ 2 and r ≥ nd − 1.

Proof. The proof for the case r ≥ nd − 1 is a simple dimension count. The number of monomials in the elementary homogeneous multisymmetric polynomials with column sum partition (1^{nd}0^{r+1−nd}) is

\binom{r + 1}{n, …, n}/d!

whereas the number of monomial multisymmetric polynomials with this column sum partition is

\binom{r + 1}{d, …, d}/n!

The following inequalities are equivalent:

\binom{r + 1}{n, …, n}/d! < \binom{r + 1}{d, …, d}/n!
\frac{(r + 1)!}{(r + 1 − nd)!(n!)^{d}d!} < \frac{(r + 1)!}{(r + 1 − nd)!(d!)^{n}n!}
\frac{1}{(n!)^{d}d!} < \frac{1}{(d!)^{n}n!}
(d!)^{n−1} < (n!)^{d−1}
(d!)^{n−d} < (n!/d!)^{d−1}
(d(d − 1) ⋯ 2)^{n−d} < (n(n − 1) ⋯ (d + 1))^{d−1}

Now we observe that the left-hand side and right-hand side of the last inequality both have (n − d)(d − 1) > 0 factors and that every factor on the left-hand side is smaller than every factor on the right-hand side. □

Conjecture 2.2. The condition r ≥ nd − 1 in Theorem 2.1 can be weakened to r ≥ 2.

This conjecture would follow from the inequality

\binom{\binom{r+n}{n} + d − 1}{d} < \binom{\binom{r+d}{d} + n − 1}{n}  (2)

under the same assumptions. The following conjecture implies weak inequality in (2):

Conjecture 2.3. (cf. [15]) The elementary homogeneous multisymmetric polynomials generate the degree n and higher parts of Λ̂_{n,r} ⊗ Q.

However, weak inequality implies strict inequality by the existence of a relation of degree n + 1 among the elementary homogeneous multisymmetric polynomials, for example, any of the Brill equations [5].

We may also ask what degrees are sufficient to generate Λ̂_{n,r} ⊗Q. For example, the degree 3 part of Λ̂_{4,2} ⊗ Q is generated by the parts of degrees 1 and 2 (as computed by Macaulay [1]), so the previous conjecture (if true) implies that Λ̂_{4,2} ⊗ Q is generated in degrees 1 and 2. The conjecture holds in the case n = 2:

Theorem 2.4. The ring Λ̂_{2,r} ⊗ Q is generated in degree 1, that is, by the elementary homogeneous multisymmetric polynomials.

Proof. Consider the Q-vector space

V = Q[x_{1,0}, x_{1,1}, …, x_{2,2d−1}]_{(d,d)}^{S_{d}≀S_{2}×S_{2}}

where one copy of S_{d} permutes the second indices 0, 1, …, d−1 and the other copy permutes the second indices d, d + 1, …, 2d − 1. The wreathing S_{2} exchanges the second indices i and d + i for all 0 ≤ i ≤ d − 1, and the remaining S_{2} permutes the first indices. If we assign the multidegree e_{j} to the variable x_{i,j}, then the monomials in V all have multidegree (1, 1, …, 1), because the group of permutations of the second indices is transitive.

Consider the basis of V consisting of the symmetrized monomials (where we symmetrize over S_{d} ≀ S_{2} × S_{2}):

{y_{k} = ∑ ( ∏_{i=0}^{k−1} x_{1,i}x_{2,d+i} ∏_{i=k}^{d−1} x_{2,i}x_{1,d+i})}_{k=0}^{⌊d/2⌋}

We claim that the following symmetrized sums of products of elementary homogeneous multisymmetric polynomials are also a basis:

{z_{k} = ∑ ( ∏_{i=0}^{k−1} e′_{i,i+k}e′_{i+d,i+k+d} ∏_{i=2k}^{d−1} e′_{i,i+d})}_{k=0}^{⌊d/2⌋}

For example, when d = 2, then z_{0} = e′_{0,2}e′_{1,3} + e′_{0,3}e′_{1,2} = 2y_{0} + y_{1} and z_{1} = e′_{0,1}e′_{2,3} = y_{1}.

We proceed as follows: write z_{i} as a linear combination of the basis elements y_{j} to obtain a coefficient matrix. Observe that y_{j} is the sum of the monomials in which the variables having second indices in the range 0 … d − 1 are divided into j variables with one first index and d − j variables with the other first index. Also, z_{i} is the sum of the monomials in the elementary multisymmetric polynomials such that i of the elementary multisymmetric polynomials have both indices in the range 0 … d − 1. Clearly each of the monomials in the expansion of z_{i} has i pairs of variables with second indices in the range 0 … d − 1 such that the first indices of each pair are different. Thus the expansion of z_{i} cannot involve any y_{j} with j < i, so the coefficient matrix is triangular. Furthermore, we may choose monomials in each of the elementary multisymmetric polynomials with one index in 0 … d − 1 and the other in d … 2d − 1 so that the variable with the smaller second index has first index 1.

In this monomial, the variables with second index in 0 … d − 1 are divided so that i have first index 2 and d − i have first index 1. Thus the expansion of z_{i} involves y_{i} with nonzero coefficient, so the coefficient matrix has nonzero diagonal. Thus it is nonsingular and {z_{k}} is a basis of V.

Now y_{0} = m_{(1,1,...,1,0,0,...,0),(0,0,...,0,1,1,...,1)} is a linear combination of the z_{k}, hence a polynomial in the elementary multisymmetric polynomials. We may now specialize some of the second indices to be the same; this allows us to write any monomial multisymmetric polynomial as a polynomial in the elementary multisymmetric polynomials. □

This theorem is false with integer coefficients:

m_{(1,1,0,0),(0,0,1,1)} = −\frac{1}{2}e_{(1,1,0,0)}e_{(0,0,1,1)} + \frac{1}{2}e_{(1,0,1,0)}e_{(0,1,0,1)} + \frac{1}{2}e_{(1,0,0,1)}e_{(0,1,1,0)}.

This expansion is unique; any relation of multidegree (1, 1, 1, 1) would dehomogenize to give a relation of degree 3 on Λ_{2,3}, which is impossible.

Generalizing this proof to the case of larger n looks difficult because of the combinatorial problems that arise. For example, when n = 3 and d = 4, the vector space

V = Q[x_{1,0}, x_{1,1}, …, x_{n,nd−1}]_{(d,d,...,d)}^{S_{d}≀S_{n}×S_{n}}

has dimension 9, there are 9 vectors z_{i}, and the coefficient matrix is triangular. But when n = 3 and d = 5, V is 13-dimensional, there are 14 vectors z_{i}, and the coefficient matrix does not contain a triangular submatrix. The z_{i} still span, but proving this requires computation of the coefficients.

2.3. Relations

The Brill equations [5] give a set of defining equations for the variety Sym^{n}P^{r} parametrized by the elementary homogeneous multisymmetric polynomials. This variety is also called the variety of factorizable forms, because it parametrizes forms of degree n on P^{r} that can be written as products of linear forms.

Proposition 2.5. The Brill equations define Sym^{n}P^{r} set-theoretically, but do not generate the ideal of this variety in general.

Proof. The first part is proved in [5], Chapter 4, Section 2. The second part is a weaker version of Jerzy Weyman’s result [15] that the Brill equations do not define a reduced scheme. Our method of proof is computational. We show that the Brill equations do not generate the ideal of Sym^{3}P^{3}. The Brill equations for Sym^{3}P^{3} consist of 875 independent quartics (computed using Macaulay [1] and MAPLE [2]). As in [15], we consider the variety Y_{3,3} of cubic forms that can be written as polynomials in three linear forms; for example,

\begin{matrix}(x_{0} + x_{1})(x_{0} + x_{2})^{2} − (x_{0} + x_{3})^{3} = \\ x_{0}^{2}x_{1} + 2x_{0}^{2}x_{2} − 3x_{0}^{2}x_{3} + 2x_{0}x_{1}x_{2} + x_{0}x_{2}^{2} − 3x_{0}x_{3}^{2} + x_{1}x_{2}^{2} − x_{3}^{3} \end{matrix}

gives a point of this variety. Clearly, the factorizable cubic forms are a subvariety, since they can be written as the product of three linear forms. The defining ideal of Y_{3,3} is given by 210 independent quartics, and possibly other polynomials of higher degree (Macaulay computation). None of the quartics belong to the ideal generated by the Brill equations, but they must belong to the defining ideal of Sym^{3}P^{3} because Sym^{3}P^{3} is a subvariety of Y_{3,3}. Thus the Brill equations do not generate the defining ideal of Sym^{3}P^{3}. □

The cubic forms parametrizing Y_{3,3} may also be described as not-necessarily-decomposable symmetric tensors of rank 3. Correspondingly, the quartics in its ideal have a nice description in terms of umbral calculus and the fourfold algebra [6]. (For those familiar with the notation of [6], the quartics are given by umbral expressions of the form ∏_{i=1}^{4}(xa_{i}^{(2)} | p_{1}p_{2}p_{3}), where x is a negative letter, a_{1}, a_{2}, a_{3}, and a_{4} are positive letters, and p_{1}, p_{2}, and p_{3} are positive places.) Together these two ideals generate the degree 4 part of the ideal of Sym^{3}P^{3}.

In the absence of a definitive computation of this ideal, the following conjecture remains open:

Conjecture 2.6. The defining ideal Î_{3,3} of Sym^{3}P^{3} is generated in degree 4.

Proof (assuming Conjecture 2.3). The Hilbert function of the free Q-algebra on the elementary homogeneous multisymmetric polynomials is given by

\binom{\binom{r+n}{n} + d − 1}{d} = \binom{\binom{3+3}{3} + d − 1}{d} = \binom{d + 19}{19}.

The Hilbert function of Λ̂_{3,3} ⊗ Q is given by

\binom{\binom{r+d}{d} + n − 1}{n} = \binom{\binom{3+d}{d} + 3 − 1}{3} = \binom{\binom{d+3}{3} + 2}{3}.

By a computation using Macaulay, the defining ideal of Sym^{3}P^{3} does not contain polynomials of degree less than 4. Therefore its Hilbert function h(d) in degrees d = 0, 1, 2, 3 is given by \binom{d+19}{19}. Assuming Conjecture 2.3, the elementary homogeneous multisymmetric polynomials generate Λ̂_{3,3} ⊗ Q in degrees 4 and higher, so for d ≥ 4,

h(d) = \binom{\binom{d+3}{3} + 2}{3}.

By another computation using Macaulay, the Hilbert function of the ideal generated by the degree 4 part of Î_{3,3} is the same as the Hilbert function of Î_{3,3} computed above. Since one ideal contains the other and they have the same Hilbert function, they are equal. □

Theorem 2.7. The defining ideal Î_{2,r} of the variety Sym^{2}P^{r} is generated by the 3×3 minors of an (r + 1) × (r + 1) symmetric matrix of indeterminates.

Proof. The elementary homogeneous multisymmetric polynomials may be expressed as inner products of 2-vectors: e′_{i,j} = (x_{1,i}, x_{2,i}) · (x_{2,j}, x_{1,j}). (If i = j, then we must multiply e′_{i,j} by 2 in this equation.) Therefore, the (r + 1) × (r + 1) matrix of elementary homogeneous multisymmetric polynomials factors as a product of an (r + 1) × 2 matrix and a 2 × (r + 1) matrix:

( \begin{matrix}2e′_{1,1} & e′_{1,2} & ⋯ & e′_{1,r+1} \\ e′_{1,2} & 2e′_{2,2} & ⋯ & e′_{2,r+1} \\ ⋮ & ⋮ & ... & ⋮ \\ e′_{1,r+1} & e′_{2,r+1} & ⋯ & 2e′_{r+1,r+1} \end{matrix} )=( \begin{matrix}x_{1,1} & x_{2,1} \\ x_{1,2} & x_{2,2} \\ ⋮ & ⋮ \\ x_{1,r+1} & x_{2,r+1} \end{matrix} )( \begin{matrix}x_{2,1} & x_{2,2} & ⋯ & x_{2,r+1} \\ x_{1,1} & x_{1,2} & ⋯ & x_{1,r+1} \end{matrix} ).

Therefore, the matrix of elementary homogeneous multisymmetric polynomials has rank at most 2, and so its 3 × 3 minors are all zero. We claim that the projective variety X_{2} of symmetric matrices of rank at most 2, which is defined by these minors, is irreducible and has dimension 2r. This follows from Propositions 4.2 and 6.1 of [8], or see the proofs below. Since Sym^{2}P^{r} also has dimension 2r, and is contained in X_{2}, the two varieties are the same. In order to conclude that Î_{2,r} equals the ideal generated by the 3 × 3 minors, we use Proposition 5.2 of [8], which implies that this ideal is radical.

We now prove the irreducibility of X_{2}, mostly using linear algebra. Let M be an (r +1)× (r + 1) matrix of rank 2. Choose a basis v_{1}, v_{2} of its column space. Then each column of M may be expressed as a unique linear combination of v_{1} and v_{2}, so M factors as (v_{1}|v_{2}) × N, where N is a 2 × (r + 1) matrix. Since M is symmetric, v_{1}^{T} and v_{2}^{T} are a basis for its row space. Since the rows of N are linear combinations of the rows of M, they may be expressed as unique linear combinations of v_{1}^{T} and v_{2}^{T}. Thus N factors as P × (v_{1}|v_{2})^{T}, where P is a 2 × 2 matrix. Since M is symmetric, M = (M + M^{T})/2. Therefore, M may be expressed as

( v_{1} v_{2} ) × \frac{1}{2}(P + P^{T}) × ( \begin{matrix}v_{1}^{T} \\ v_{2}^{T} \end{matrix} ) .

Clearly any matrix of this form is symmetric and has rank at most two. Since every matrix of rank less than two is the limit of matrices of rank two, X_{2} is the image of P^{2r+5} via the rational map

(p_{11} : p_{12} : p_{21} : p_{22} : v_{1} : v_{2}) ↦ M.

Since P^{2r+5} is irreducible, X_{2} is irreducible also.

We now show that X_{2} has dimension 2r. Let M = (m_{ij}) be a symmetric matrix whose upper left entry m_{11} and upper left 2 × 2 minor m_{11}m_{22} − m_{12}^{2} are nonzero. Since X_{2} is projective, we may assume that m_{11} = 1. Matrices of this type form an open set in X_{2}. Choose x to be a square root of m_{22} − m_{12}^{2}. Then M factors as

( \begin{matrix}1 & 0 \\ 0 & 1 \\ a_{1,3} & a_{2,3} \\ a_{1,4} & a_{2,4} \\ ⋮ & ⋮ \\ a_{1,r+1} & a_{2,r+1} \end{matrix} ) × ( \begin{matrix}1 & m_{12} \\ m_{12} & m_{22} \end{matrix} ) × ( \begin{matrix}1 & 0 & a_{1,3} & a_{1,4} & ⋯ & a_{1,r+1} \\ 0 & 1 & a_{2,3} & a_{2,4} & ⋯ & a_{2,r+1} \end{matrix} )

where a_{1,j} = m_{1j} − m_{12}m_{2j}/x and a_{2,j} = m_{2j}/x. Therefore,

(A^{2} \ V (m_{22} − m_{12}^{2})) × A^{2r−2}

is a double cover of the given open subset of X_{2} via the map

(m_{12}, m_{22}, a_{1,3}, a_{1,4}, …, a_{2,r+1}) ↦ M.

Therefore, X_{2} has the same dimension as A^{2} × A^{2r−2}, namely 2r. □

3. ms: a MAPLE package for multisymmetric functions

3.1. Introduction

The “ms” package provides MAPLE [2] functions for working with (inhomogeneous) multisymmetric functions in Λ ⊗ Q and Λ_{n,r} ⊗ Q. The main differences between the notation of Chapter 2 and the notation used in the “ms” package are that the columns of the matrices X used to construct the rings Λ_{n,r} are indexed by valid MAPLE names instead of numbers, and that the indexing vectors of multisymmetric functions are represented by monomials. The advantage of this notation is that we can leave r ≫ 0 unspecified. In this notation, the vector v = (a_{1}, a_{2}, …, a_{k}) is represented by the monomial mon(v) = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}}, where x_{1}, x_{2}, … is an enumeration of the valid MAPLE variable names. Thus the function e_{v} is represented by the MAPLE notation e(mon(v)), p_{v} = p(mon(v)), and

m_{v_{1},v_{2},...,v_{k}} = m(mon(v_{1}), mon(v_{2}), …, mon(v_{k})).

For example, suppose that the enumeration begins x, y, …. Then e_{(2,1)} = e(x^2 ∗ y), p_{(2,1)} = p(x^2 ∗ y), and m_{(1,1),(1,0)} = m(x ∗ y, x).

The “ms” package provides six functions. The functions toe(f), top(f), and tom(f) represent the multisymmetric function f ∈ Λ ⊗ Q as a polynomial in the elementary multisymmetric functions, a polynomial in the generalized Newton power sums, and a linear combination of monomial multisymmetric functions, respectively.

The function evalsf(f, n) represents the multisymmetric function f ∈ Λ_{n,r} ⊗ Q as a polynomial in R_{n,r}. The variable x_{i,j} is represented by the variable x_{j}[i] if x_{j} is not already an indexed variable name. If x_{j} has the form x[i_{1}, i_{2}, …, i_{k}], then x_{i,j} is represented by x[i_{1}, i_{2}, …, i_{k}, i].

Normally the symmetrization of a function refers to the sum or average of its images under the group action. Sometimes, however, we will want to multiply these images together instead of adding them. Formally speaking, we fix n, define R_{r} = Q[x_{1}, x_{2}, …, x_{r}], and define the algebra maps i_{k}: R_{r} → R_{n,r} ⊗ Q by i_{k}(x_{j}) = x_{k,j}. Then the multiplicative symmetrization of f ∈ R_{r} is given by i_{1}(f)i_{2}(f) ⋯ i_{n}(f).

The function symprod(f, n) computes the multiplicative symmetrization of f ∈ R_{r} and represents it as a linear combination of monomial multisymmetric functions. The function symprod(f, l, n) treats any variables not in the list l as belonging to the ground field. This is useful when one wants to symmetrize a function having unknown (or unspecified) coefficients.

Finally, the function truncate(f, n) computes the projection of f from Λ⊗Q to Λ_{n,r} ⊗Q by substituting a zero in place of each elementary multisymmetric function that has an indexing monomial of degree larger than n, and in place of each monomial multisymmetric function that has more than n indexing monomials.

I have not implemented error checking for invalid inputs. The variable names e, p, and m should not be assigned values or used in the indexing monomials; they are reserved for the bases of multisymmetric functions.

3.2. Examples

> toe(p(x*y^2));
e(x)*e(y)^2-e(x*y)*e(y)-e(y^2)*e(x)+e(x*y^2)
> toe(m(x*y^2));
e(x)*e(y)^2-e(x*y)*e(y)-e(y^2)*e(x)+e(x*y^2)
> top(e(x*y^2));
1/2*p(y)^2*p(x)-p(y)*p(x*y)-1/2*p(x)*p(y^2)+p(x*y^2)
> top(m(x,y,y));
1/2*p(y)^2*p(x)-p(y)*p(x*y)-1/2*p(x)*p(y^2)+p(x*y^2)
> tom(e(x*y^2));
m(x,y,y)
> tom(p(x*y^2));
m(x*y^2)
> tom(m(x,y)*m(y));
2*m(x,y,y)+m(x,y^2)+m(x*y,y)
> evalsf(e(x*y^2),3);
x[3]*y[1]*y[2]+x[2]*y[1]*y[3]+x[1]*y[2]*y[3]
> evalsf(p(x*y^2),3);
x[1]*y[1]^2+x[2]*y[2]^2+x[3]*y[3]^2
> evalsf(m(x,y^2),3);
x[2]*y[3]^2+x[1]*y[2]^2+x[1]*y[3]^2+x[2]*y[1]^2
+x[3]*y[1]^2+x[3]*y[2]^2
> symprod(1-2*x^3+3*x*y^2,3);
27*m(x*y^2,x*y^2,x*y^2)-18*m(x*y^2,x*y^2,x^3)+9*m(x*y^2,x*y^2)
+12*m(x*y^2,x^3,x^3)-6*m(x*y^2,x^3)+3*m(x*y^2)-8*m(x^3,x^3,x^3)
+4*m(x^3,x^3)-2*m(x^3)+1
> factor(evalsf(",3));
-(-2*x[3]^3+3*x[3]*y[3]^2+1)*(-2*x[2]^3+1+3*x[2]*y[2]^2)
*(-1+2*x[1]^3-3*x[1]*y[1]^2)
> symprod(a*x+b*y+c*z,[x,y,z],3);
a^3*m(x,x,x)+a^2*b*m(x,x,y)+a^2*c*m(x,x,z)+a*b^2*m(x,y,y)
+a*b*c*m(x,y,z)+a*c^2*m(x,z,z)+b^3*m(y,y,y)+b^2*c*m(y,y,z)
+b*c^2*m(y,z,z)+c^3*m(z,z,z)
> factor(evalsf(",3));
(a*x[3]+c*z[3]+b*y[3])*(x[2]*a+b*y[2]+c*z[2])
*(x[1]*a+b*y[1]+c*z[1])
> truncate(toe(p(x*y^2)),2);
e(x)*e(y)^2-e(x*y)*e(y)-e(y^2)*e(x)
> truncate(tom(m(x,y)*m(y)),2);
m(x,y^2)+m(x*y,y)

3.3. Computing the Chow form of a hypersurface section

We will compute the Chow form of the intersection of the twisted cubic and the Fermat cubic surface in P^{3}. The twisted cubic is given by the equations x^{2} − wy, xy − wz, and y^{2} − xz. We select the distinguished affine open set w ≠ 0 for our computations.

We begin by setting up the coefficients of the Chow form of the twisted cubic as the elementary multisymmetric functions of the intersection of the twisted cubic with a hyperplane. We need to choose the hyperplane so that all three intersection points lie within the selected affine open set. The one bad point is (0 : 0 : 0 : 1), and we can avoid it by choosing the hyperplane to have the form a + bx + cy + z = 0. The intersection points can then be written in the form (1 : x[i] : y[i] : z[i]), where i = 1, 2, 3. We take the remaining hyperplane to be 1 + Xx + Y y + Zz = 0. Substituting these two hyperplanes into the Chow form, we get the elementary multisymmetric function e(x^d ∗ y^f ∗ z^g) as the coefficient of X^{d}Y^{f}Z^{g}. The variables X, Y, and Z are represented below by the variables x, y, and z.

with(linalg);
A:=matrix([[a,b,c,1],[1,x,y,z]]); # Matrix of hyperplanes #
B:=map(columns->det(submatrix(A,1..2,columns)),choose(4,2));
# 2x2 minors #
C:=matrix([[B[1],  B[2],   B[3]],
           [B[2],B[3]+B[4],B[5]],
           [B[3],   B[5],  B[6]]]);
# Bezout matrix for the resultant of two cubics #
D:=det(C); # Chow form of twisted cubic #
G:=D/subs(x=0,y=0,z=0,D); # Normalize so that constant term = 1 #
S:=coeffs(G,[x,y,z],T);
# Coefficient of x^d*y^f*z^g is e(x^d*y^f*z^g) #
L:=map(i->T[i]=S[i],[$1..20]);
M:=table(L);
dada:=proc(m) M[m] end;
# Sends monomial to elementary multisymmetric fn. #

Now we compute the product of the values of the defining polynomial of the Fermat cubic at each of three points, and substitute the values of the elementary multisymmetric functions of the intersection points computed above into the result.

read ms;
F:=truncate(toe(symprod(1+x^3+y^3+z^3,3)),3);
# Symmetrization in terms of elementary multisymmetric functions #
F:=expand(eval(subs(e=dada,F)));
# Substitute coefficients of Chow form into F #

The result is the dehomogenization of the Chow form. It has degree 9, as predicted by Bezout’s theorem, so we homogenize it by multiplying each term by the power of the new variable d for which the product has degree 9.

dada:=proc(m) m*d^(9-degree(m)) end;
F:=eval(map(dada,F)); # Homogeneous Chow form #

References

[1] Bayer, D.; Stillman, M.: Macaulay: A system for computation in algebraic geometry and commutative algebra. 1982–1994; source and object code available for Unix and Macintosh computers; contact the authors, or download from math.harvard.edu via anonymous ftp.

[2] Char, Bruce W., et al.: MAPLE V Library Reference Manual. Waterloo Maple Publishing, Waterloo, Ontario, Canada, 1991.

[3] Chevalley, Claude: Invariants of finite groups generated by reflections. Amer. J. Math. 77 (1955), 778–782.

[4] Chow, Wei-Liang; van der Waerden, B. L.: Zur algebraischen Geometrie IX: Über zugeordnete Formen und algebraische Systeme von algebraischen Mannigfaltigkeiten. Math. Ann. 113 (1937), 692–704.

[5] Gel’fand, I. M.; Kapranov, Mikhail M.; Zelevinsky, Andrei V.: Discriminants, Resultants, and Multidimensional Determinants. Birkhäuser, Boston Basel Stuttgart 1994.

[6] Grosshans, Frank D.; Rota, Gian-Carlo; Stein, Joel A.: Invariant theory and superalgebras. American Mathematical Society, Providence, RI, 1987.

[7] Junker, F.: Über symmetrische Funktionen von mehreren Reihen von Veränderlichen. Math. Ann. 43 (1893), 225–270.

[8] Kutz, Ronald E.: Cohen-Macaulay rings and ideal theory in rings of invariants of algebraic groups. Trans. Amer. Math. Soc. 194 (1974), 115–129.

[9] Macdonald, Ian G.: Symmetric Functions and Hall Polynomials. Oxford University Press, New York 1979.

[10] MacMahon, Percy A.: Combinatory Analysis. 3rd ed. Chelsea Publishing Company, New York 1984.

[11] Pedersen, Paul: Calculating multi-dimensional symmetric functions using Jacobi’s formula. In: Proceedings AAECC 9, volume 539 of Springer Lecture Notes in Computer Science, 304–317, Springer 1991.

[12] Robbiano, Lorenzo; Sweedler, Moss: Subalgebra bases. In: Commutative Algebra, volume 1430 of Springer Lecture Notes in Mathematics, 61–87, Springer 1990.

[13] Serre, Jean-Pierre: Groupes finis d’automorphismes d’anneaux locaux réguliers. In: Colloque d’Algèbre (Paris, 1967), Exp. 8, 11 pp., Secrétariat mathématique, Paris 1968.

[14] Shephard, G. C.; Todd, J. A.: Finite unitary reflection groups. Canad. J. Math. 6 (1954), 274–304.

[15] Weyman, Jerzy: Remarks on the varieties of decomposable polynomials. Working notes, based in part on joint work with Andrei Zelevinsky.

Received April 23, 1997