\documentclass[11pt]{article}
\begin{document}
%%%%% written in LaTeX %%%
\addtolength{\oddsidemargin}{-1.25cm}
\addtolength{\textwidth}{3cm}
\addtolength{\textheight}{4cm}
\addtolength{\topmargin}{-2cm}
\newcommand{\noi}{\noindent}
\newcommand{\ra}{\rightarrow}
\newcommand{\sig}{\sigma}
\newcommand{\eps}{\epsilon}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\TREE}{\mbox{TREE}}
\newcommand{\lam}{\lambda}
\newcommand{\ah}{\alpha}
\newcommand{\ol}{\overline}
\newcommand{\gam}{\gamma}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bec}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{define}{Definition}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}
\bec {\Large\bf Symmetric Functions} \ece
Now for a change of pace which has applications to what we are doing and
is interesting by itself. Lets look at polynomials in $n$ variables
$x_1,\ldots,x_n$. In our examples we'll take $n=3$ and call the
variables simply $x,y,z$.
We'll call a polynomial symmetric if no matter how you permute the
variables you get the same thing. For example: $x^{20}+y^{20}+z^{20}$
or $x^5y^5+x^5z^5+y^5z^5$. One class is of particular interest
to us. For $1\leq i\leq n$ define the $i$-th {\em elementary symmetric
polynomial} as the sum of all of the products of $i$ distinct variables.
That is, $s_1=x+y+z$, $s_2=xy+xz+yz$, $s_3=xyz$.
Suppose
\beq f(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_0 \eeq
is a monic polynomial of degree $n$ with
roots $\ah_1,\ah_2,\ldots,\ah_n$. (When $\ah$ is a root of multiplicity $m$ just
write it $m$ times here.) Then
\beq
f(x)=x^n+a_{n-1}x^{n-1}+\ldots+a_0 = (x-\ah_1)\cdots (x-\ah_n)
\eeq
Multiplying out the product, $x^{n-1}$ has coefficient $-(\ah_1+\ldots+\ah_n)$,
the constant coefficient is $(-1)^n\ah_1\cdots \ah_n$ and, in general, the
coefficient of $x^{n-i}$ is $(-1)^i$ times the value of the $i$-th symmetric
polynomial $s_i$ on the values $\ah_1,\ldots,\ah_n$. For $n=3$, calling the
roots $\ah,\beta,\gam$, we have
\beq a_1 = -(\ah+\beta+\gam) \eeq
\beq a_2 = (\ah\beta+\beta\gam+\ah\gam) \eeq
\beq a_3 = -(\ah\beta\gam) \eeq
\begin{theorem}\label{g1} Any symmetric polynomial in $x_1,\ldots,x_n$ can be expressed
in terms of the elementary symmetric polynomials.
\end{theorem}
This can get pretty bogged down in notation so we will first only show the
argument for $n=3$ with variable $x,y,z$. We say two monic momomials (i.e., with constant
coefficient one) have the same {\em form} if they have the same exponents with
the same multiplicities. For any monic monomial $g(x)$ we let $\ol{g(x)}$ denote the
sum of all monomials with that form. Thus for $a,b,c$ distinct nonnegative integers
\beq \ol{x^ay^bz^c}:= x^ay^bz^c+x^az^by^c+y^ax^bz^c+y^az^bx^c+z^ax^by^c+z^ay^bx^c
\eeq
We do not double count so, for example,
\beq \ol{x^2y^2z} = x^2y^2z+x^2z^2y+ y^2z^2x \eeq
(That is, we don't count, say, $y^2x^2z$ separately. This is only a technical point.)
A monoic monomial is determined by the exponents written in decreasing order, that is,
$(a_1,\ldots,a_n)$ with $a_1\geq\ldots\geq a_n\geq 0)$ or, for $n=3$, simply $(a,b,c)$
with $a\geq b\geq c \geq 0$.
Any symmetric polynomial can be expressed as a linear combination of these
so it suffices (we are now doing only the case $n=3$) to write $\ol{x^ay^bz^c}$
in terms of $s_1,s_2,s_3$. We actually get the expression by reducing to simpler
(more on that later) terms.
If $a,b,c$ are positive, simply take out a common factor of $s_3=xyz$.
If $a=b>0=c$ express
\beq \ol{x^ay^a} = (xy+xz+xy)^a - \Delta \eeq
As the other two parts are symmetric their difference
$\Delta$ is also symmetric. But all the terms in $\Delta$ have all three
variables and so they can be reduced.
{\tt Example:} With $a=b=2, c=0$:
\beq (x^2y^2+x^2z^2+y^2z^2)= (xy+xz+yz)^2 - 2xyz(x+y+z) \eeq
If $a>b>0=c$ express
\beq \ol{x^ay^b} = \ol{x^by^b}\cdot \ol{x^{a-b}} + \Delta \eeq
The polynomials $\ol{x^by^b}$ and $\ol{x^{a-b}}$, being smaller, have already
been done. Again, $\Delta$, as the difference of symmetric polynomials, is
symmetric and again all terms in $\Delta$ have all three variables and so
they can be reduced.
{\tt Example:} With $a=5$, $b=2$, $c=0$:
\beq \ol{x^5y^2}= (x^2y^2+x^2z^2+y^2z^2)(x^3+y^3+z^3)-x^2y^2z^2(x+y+z) \eeq
Finally when $a>0=b=c=0$ we express
\beq x^a+y^a+z^a = (x+y+z)^a + \Delta \eeq
Again $\Delta$ is symmetric, and consists only of terms on two or three
variables, which we have already done.
{\tt Example:} With $a=4$, $b=0$, $c=0$:
\beq x^4+y^4+z^4 = (x+y+z)^4 - 4\ol{x^3y} - 6\ol{x^2y^2} - 12xyz(x+y+z) \eeq
There is a powerful consequence.
\begin{theorem}\label{g2} Let $L$ be any subfield of $C$. Let $f(x)\in L[x]$
be a polynomial of degree $n$ with complex roots $\ah_1,\ldots,\ah_n$.
(For multiple roots we repeat the root.) Then any symmetric polynomial of
$\ah_1,\ldots,\ah_n$ is in $L$.
\end{theorem}
{\tt Proof:} From Theorem \ref{g1} we write any symmetric polynomial in
terms of the elementary symmetric polynomials and their values are $\pm$
the coefficients of $f(x)$, which are in $L$.
{\tt Example:} Take $L=Q$ (the main case we shall use) and let
$\ah,\beta,\gam$ be the roots of $f(x)=x^3+x^2+2x+1$. Consider
$\kappa=\ah^3+\beta^3+\gam^3$. We express
\beq \kappa = (\ah+\beta+\gam)^3-3(\ah^2\beta+\cdots+\gam^2\beta)-6\ah\beta\gam
\eeq
and further reduce
\beq \ah^2\beta+\cdots+\gam^2\beta)=(\ah\beta+\ah\gam+\beta\gam)(\ah+\beta+\gam)
- 3\ah\beta\gam
\eeq
We know $\ah+\beta+\gam=-1$ and $\ah\beta+\ah\gam+\beta\gam= 2$ and
$\ah\beta\gam =-1$ so
$\ah^2\beta+\ldots+\gam^2\beta=2(-1)-3(-1)= -5$ and so
$\kappa=(-1)^3-3(-5)-6(-1)=-10$.
How do we turn this into a rigorous proof for a general number of
variables $n$. For each $\vec{a}=(a_1,\ldots,a_n)$ with
$a_1\geq\ldots a_n\geq 0$
let $MM(\vec{a})$ denote the monic polynomial
\beq \label{g4} MM(\vec{a}) = \ol{x_1^{a_1}\cdots x_n^{a_n}} \eeq
We set $D=D(\vec{a})=a_1+\ldots a_n$ and call $D(\vec{a})$ the degree of $\vec{a}$.
(Note it is the degree of the associated monic polynomial.
The idea is to subtract off from $MM(\vec{a})$ some combination of elementary
symmetric polynomials so as to be left with simpler forms. But what do
we mean by simpler? The notion of simpler, and even more the analysis of simpler,
shall be quite complicated! We define an ordering on the possible $\vec{a}$. Let
$\vec{a}=(a_1,\ldots,a_n)$ and $\vec{b}=(b_1,\ldots,b_n)$ with
$a_1\geq\ldots a_n\geq 0$ and $b_1\geq\ldots b_n\geq 0$.
\ben
\item\label{g5} If $D(\vec{a})\neq D(\vec{b})$ then the one with
the smaller degree is called
simpler.
\item\label{g6} Now suppose $b_1+\ldots+b_n=a_1+\ldots+a_n$. Let $i$ be the
smallest index (it may be that $i=1$) with $a_i\neq b_i$. If $a_i < b_i$ we
then say $\vec{a}$ is simpler than $\vec{b}$, else $\vec{b}$ is simpler.
\een
Among the $\vec{a}$ with the same sum of coordinates, simpler can be thought
of as a lexicographical ordering of the possible vectors, thought of as
words.
We want to show that, for any $\vec{a}$, $MM(\vec{a})$ can be expressed in
terms of the elementary symmetric functions. We do this by a double induction,
first on the degree $D$ and then, amongst those of a given degree $D$, in
order of simplicity as given by (\ref{g6}) above. To start the induction, for
$D=1$ the only vector is $\vec{a}=(1,0,\ldots,0)$ and $MM(\vec{a})=s_1$.
Now suppose the result is true for all $\vec{b}$ of degree less than $D$
and for all $\vec{b}$ simpler than $\vec{a}$. If $a_n\neq 0$ we reduce
by writing
\beq\label{g7} MM(\vec{a}) = s_n\cdot MM((a_1-1,\ldots,a_n-1)) \eeq
That is, we take out the common factor of $s_n=x_1\cdots x_n$ and are left
with something of smaller degree. Now we come to the main case. We write
(we assume $a_n=0$)
\beq\label{g8}
MM(\vec{a}) = s_1^{a_1-a_2}s_2^{a_2-a_3}\cdots s_{n-1}^{a_{n-1}-a_n} + STUFF
\eeq
Observe that the product on the RHS is a symmetric polynomial of degree
$D$ and so STUFF is a symmetric polynomial of degree $D$ and so we only have
to check that all of the forms in STUFF are simpler than $\vec{a}$.
We pause for an example. Consider $n=5$ and $\vec{a}=(10,7,4,0,0)$. Call
the variables $v,w,x,y,z$ for convenience. Then
(\ref{g8}) becomes
\beq \label{g9}
\ol{v^{10}w^7x^4}=(v+w+x+y+z)^3(vw+\ldots+yz)^3(vwx+\ldots + xyz)^4 + STUFF
\eeq
Looking at the leftmost terms in the products on the right we get
$v^3(vw)^3(vwx)^4$ which is precisely the $v^{10}w^7x^4$ that we want.
The general term consists of three from $v,\ldots,z$, three from $vw,\ldots,yz$
and four from $vwx,\ldots,xyz$. One such term would be taking $v,v,w;vw,vw,wx,
vwx,vwx,vwy,vwy$. That gives $v^8w^8x^3y^2$ and, indeed, $(8,8,3,2,0)$ is simpler
than $(10,7,4,0,0)$.
It may be helpful to think of the forms of these monomials in terms of balls in
bins. Imagine $n$ bins labelled with the $n$ variables $x_1,\ldots,x_n$. The
monomial polynomial $MM(\vec{a})$ corresponds to placing $a_i$ balls in the
bin marked $x_i$ Here is a picture corrsponding to the $\vec{a}$ of the example.:
\begin{verbatim}
x
x
x
x x
x x
x x
x x x
x x x
x x x
x x x
- - - - -
v w x y z
\end{verbatim}
Now each term from $s_i$ consists of $i$ balls in $i$ different bins. A term in the product
consists of placing $i$ balls in $i$ different bins $a_i-a_{i+1}$ times for $1\leq i \leq n$.
In the example above we have
$v^8w^8x^3y^2$ as follows:
\begin{verbatim}
x
x
x
x x
x x
x x
x x x
x x x
x x x
x x x
- - - - -
v w x y z
\end{verbatim}
The claim is that no matter how we
place $i$ balls in $i$ different bins $a_i-a_{i+1}$ times for $1\leq i \leq n$ we
end up with a $\vec{b}=(b_1,\ldots,b_n)$ which is simpler than $\vec{a}$.
First look at $b_1$. We can have at most one ball in a bin from each placement
and so
\beq \label{g10}
b_1 \leq (a_1-a_2)+(a_2-a_3)+\ldots+ (a_{n-1}-a_n) = a_1
\eeq
Now consider the total number of balls in two bins. We get at most two balls in
the two bins from each placement except that the placement of one ball (corresponding
to the $a_1-a_2$ factors of $s_1$) gives only one ball in the two bins so
\beq \label{g11}
b_1+b_2 \leq (a_1-a_2)+2(a_2-a_3)+\ldots+ 2(a_{n-1}-a_n) = a_1 + a_2
\eeq
In general, for $1\leq j\leq n-1$ consider the total number of balls in any $j$ bins.
When $i\leq j$ and $i$ balls are placed in $i$ different bins there are at most
$i$ balls in those $j$ bins while when $i>j$ there are at most $j$ balls in thos
$j$ bins. Thus
\beq \label{g12}
\sum_{k=1}^j b_k \leq \sum_{i=1}^j i(a_i-a_{i+1}) + j\sum_{i=j+1}^{n-1} (a_i-a_{i+1})
= \sum_{k=1}^j a_k
\eeq
But (\ref{g12}), for $1\leq j\leq n-1$, implies $\vec{b}$ is simpler than (or equal to)
$\vec{a}$. If $\vec{b}\neq \vec{a}$ let $j$ denote the first coordinate for which
$b_j\neq a_j$. As $b_k=a_k$ for $k