The theory of symmetric functions, which generalizes some ideas that came up in the previous discussion of Polya theory, can be motivated by thinking about polynomial functions of the roots of a monic polynomial . Problems on high school competitions often ask for the sum of the squares or the cubes of the roots of a given polynomial, and those not familiar with symmetric functions will often be surprised that these quantities end up being integers even though the roots themselves aren’t integers. The key is that the sums being asked for are always symmetric in the roots, i.e. invariant under an arbitrary permutation. The coefficients of a monic polynomial are the elementary symmetric polynomials of its roots, which we are given are integers. It follows that any symmetric polynomial that can be written using integer coefficients in terms of the elementary symmetric polynomials must in fact be an integer, and as we will see, every symmetric polynomial with integer coefficients has this property.
These ideas lead naturally to the use of symmetric polynomials in Galois theory, but combinatorialists are interested in symmetric functions for a very different reason involving the representation theory of . This post is a brief overview of the basic results of symmetric function theory relevant to combinatorialists. I’m mostly following Sagan, who recommends Macdonald as a more comprehensive reference.
A lemma on group actions
First, a straightforward lemma. Let be a group acting on a set and extend this group action to a representation of on the free module with basis over some commutative ring .
Lemma: The fixed points of the action of on form a submodule spanned by the vectors of the form , where is an orbit of the action of on .
Proof. Clearly any linear combination of such vectors are fixed points. In the other direction, if is a fixed point, then it must be equal to
for every . It follows that for every ; in particular, if are in the same orbit. The conclusion follows.
The symmetric group acts on by permutation of the variables, and the fixed points of this action are the symmetric polynomials, denoted . Since symmetry is preserved under addition and multiplication, and since symmetric polynomials inherit the grading from , the symmetric polynomials form a graded -algebra. General results in algebra then guarantee that the symmetric polynomials are finitely generated, but we’ll be able to prove this directly.
where is the stabilizer of any monomial of type under the action of ; this ensures that the above sum has every monomial in the orbit exactly once. If the partition doesn’t have parts then the extra factors are set to . By the lemma, the degree component of has as a basis the monomial symmetric polynomials corresponding to partitions of with at most parts. This implies the following.
Theorem: The Hilbert series of is .
Proof. The conjugate of a partition with at most parts is a partition in which every part has size at most , and such a partition is uniquely specified by describing how many parts of each size it has. This is exactly what the generating function above does.
(Molien’s theorem generalizes this result, but the invariant-theoretic aspects aren’t too relevant to what we’re doing here.)
This result suggests that is generated by algebraically independent polynomials, one of each degree; such an algebra would have the same Hilbert series as the one above, since the homogeneous elements of degree would be spanned by products of the generators of total degree . This is in fact the content of the fundamental theorem of symmetric polynomials. Recall that the elementary symmetric polynomials can be defined by
Equivalently, we can define . Considering arbitrary products of such polynomials is easiest with the following notation: given a partition where each part has size at most , define
where . Note that the restriction on is by size of parts rather than number; the restriction is natural because isn’t well-defined.
Theorem: The degree part of has as a basis the polynomials corresponding to partitions of where each part has size at most . Equivalently, is freely generated as an -algebra by .
Proof. We are done if we can show that the coefficients expressing in terms of form a matrix whose inverse has coefficients in . In fact, it turns out that with a suitable choice of ordering this matrix is upper-triangular with all diagonal entries , which gives the result immediately. To see this, we’ll use the dominance or majorization order on two partitions of the same integer, where if and only if for all . Then we claim that there exist integer coefficients such that
To see this visually, write down a monomial in by drawing the Young diagram of and filling in the row corresponding to with the monomial chosen from the factor , placing the labels in increasing order. This gives a Young tableau with rows strictly increasing. Now note that since can only appear in the first column of such a tableau, the greatest power of in any such monomial is ; generally, can only appear in the first columns, which means that the monomials that appear in are precisely the monomials dominated by . The equality case only occurs if the column consists entirely of , so the coefficient of is as desired.
As the above discussion suggests, symmetric polynomials can be thought of as certain kinds of weighted generating functions. For example, counts compositions of type , counts subsets of of size , and counts Young tableaux with strictly increasing rows. Changing “subset” to “multiset,” i.e. “strictly” to “weakly,” we obtain the complete homogeneous symmetric polynomials, which can be defined by
Again, given a partition we can define
and we expect as before that has basis where the parts of the partition have size at most . In fact, we can deduce this directly from the fundamental theorem thanks to the identity , which gives
The power symmetric polynomials are defined by
Again, given a partition we define
Again, has degree . I personally think of as computing where is a matrix with eigenvalues . It follows that should satisfy a linear recurrence with characteristic polynomial , so we should have
This is most of Newton’s identities already: we just need to describe for . The generating functions proof is essentially one I've already given in past GILA posts. Write and differentiate both sides, then multiply by . This gives
Multiplying both sides by we obtain the identity
Essentially the same argument applied to also gives
One might now expect that by writing the elementary symmetric polynomials in terms of the power symmetric polynomials, we could conclude that the symmetric polynomials have as a basis the power symmetric polynomials. Unfortunately, that pesky factor implies that this isn’t true for general . For example, if has characteristic , then , so we have less polynomials to work with than we expect. And if isn’t invertible in , then can’t be generated by the power symmetric polynomials. Fortunately, if contains , everything works out. To see this more explicitly, note that Newton’s sums are equivalent to the pair of identities
The second identity should be familiar from the previous post on the cycle index polynomials of the symmetric groups. As stated in this form we get an explicit formula for the in terms of the by expanding the exponential as follows: given a permutation with cycle type a partition , define . Then
This follows because the sign of a cycle of even length is negative and sign is multiplicative. Similarly,
These identities hold over any field of characteristic zero and more generally over any -algebra. They imply, among other things, that it is possible to compute the characteristic polynomial of a square matrix by taking traces of its powers.
The ring of symmetric functions
As the above examples show, the interesting identities among symmetric polynomials hold independent of the number of variables; they only depend on the partitions involved. One reason we should expect this to be true is that setting in a symmetric polynomial identity among variables immediately gives a symmetric polynomial identity among variables that is essentially identical in the terms involved for sufficiently large . It would therefore be nice to reverse this process and prove symmetric polynomial identities “abstractly” rather than fixing the number of variables in advance.
This abstract setting is known as the ring of symmetric functions, although it does not really consist of a ring of functions in the usual sense. As the Wikipedia article describes, it can be thought of in two ways:
- Start with the ring of power series in countably many variables over a commutative ring and consider only the elements of finite degree, then only the elements invariant under the full permutation group of a countable set, or
- Consider the homomorphisms given by sending to and set up a direct limit / colimit.
To keep things concrete we’ll take the first perspective, although the second is an important conceptual point. The ring of symmetric functions over , denoted , is spanned as an -module by the monomial symmetric functions
where range over all distinct indices and ranges over all partitions. is graded by degree with multiplication is defined as expected, although it is no longer finitely generated, and one can check that all of the above proofs make perfect sense in this setting; in particular is freely generated by the elementary symmetric functions, defined as the coefficients of
and extended to partitions by multiplicativity; similarly for the complete homogeneous symmetric functions. We therefore know that the functions are all bases of with no restriction on the partition and under the same assumptions as before so is . The Hilbert series of is therefore equal to ; this is precisely the limit, in the -adic topology, of the Hilbert series of as tends to infinity.
Relationship to representation theory
Recall that the number of conjugacy classes of , hence the number of irreducible representations, is the number of partitions of . This implies that the class functions of over form a -module of dimension , so the countable direct sum
has Hilbert series as an -module if the degree of the elements of is defined to be .
Over , there is a distinguished basis of given by the irreducible characters associated to the partitions of , and there is a distinguished inner product given by
with respect to which the irreducible characters are orthonormal, i.e. one has . This inner product extends to by declaring characters of different degree to be orthogonal. A question then naturally presents itself: does there exist an invertible linear transformation such that
- there exists a nice inner product on such that preserves the inner product of class functions, and
- there exists a nice multiplication on such that preserves the product of symmetric functions?
As we will see, the answer to both questions is yes.