This little gemstone is hidden within the folds of algebraic combinatorics, but certainly deserves its name. Just as the Fundamental Theorem of Arithmetic gives us a way of writing common objects (numbers) in a canonical form (prime factorization), the Fundamental Theorem of Symmetric Function Theory allows us to express any symmetric function in a useful canonical form.
First, some background on symmetric functions. Like generating functions, symmetric functions arise naturally in combinatorics, and the coefficients are often the point of interest. In the poetic words of Herbert Wilf in his book generatingfunctionology:
A generating function is a clothesline on which we hang up a sequence of numbers for display.
I claim, and aim to demonstrate here, that
A symmetric function is a web of clotheslines on which we hang up a collection of numbers that are indexed by partitions.
Okay, so the clothesline might be a bit more complicated in this case. But it is much more useful for areas of mathematics in which partitions play an important role.
Let’s be more rigorous. A symmetric function (over ) is a polynomial or series in many variables with rational coefficients which is invariant (unchanging) under permutations of the variables. For instance, is a symmetric function in three variables, but is not, because interchanging and does not leave the function unchanged.
I find that writing out a symmetric function explicitly as a polynomial, like those above, is similar to expressing a number in base ten – sometimes it is useful, but other times you need its prime factorization. The “primes” of symmetric function theory are the elementary symmetric functions.
First, define For instance,
Let be a partition, that is, a finite sequence of positive integers written in nonincreasing order. Then the elementary symmetric function corresponding to is defined to be the product
The remarkable fact is that the symmetric functions form a basis for the -module of symmetric functions! In other words:
Fundamental Theorem of Symmetric Function Theory: Every symmetric function can be written uniquely in the form , where each .
So, the `s are a clothesline of sorts, indexed by the partitions, on which to hang coefficients.
For example, let’s try to write the symmetric function in terms of elementary symmetric functions. We have the functions , , and to work with. We can start by cubing :
We can replace the with . We now only need to write the term in terms of `s. The product is pretty close, but leaves us with an extra that we need to subtract out, giving us for the middle term. Putting this all together and solving for , we find:
It is fairly clear that a similar process can be used to express any symmetric function in terms of `s. But why is it unique?