\magnification = \magstep 1
\vsize 9 true in
\hsize 6.5 true in
\def\Z{{\Bbb Z}}
\def\({\left(}
\def\){\right)}
\def\goodbreak{\par\penalty-500 }
\def\problem#1\par{\bigskip\bigskip\goodbreak\centerline{Problem #1}\bigskip}
\define\Aut{\operatorname{Aut}}
\define\End{\operatorname{End}}
\font\bigbf=cmbx12
\def\ni{\noindent}
\def\bs{\bigskip}
\def\ms{\medskip}
\def\ss{\smallskip}
\def\subhead{\bf}
\centerline{ \bigbf Answer, October 11, 1989 }
\bs
\centerline { \bigbf Math 401 -- Second Course in Abstract Algebra, I}
\ms
\centerline { \bigbf Prof. Daniel Grayson }
\ms
\centerline { 2:00 PM MWF, Section F1, 241 Altgeld Hall }
\bs



\problem 3

Suppose a polynomial $f(x) = x^n + a_{1} x^{n-1} + \dots + a_{n-1} x + a_n$ has roots
$\alpha_1, \dots, \alpha_n$.  Suppose also that $P(T_1,\dots,T_n)$ is a
polynomial with the property that for any permutation $\sigma$, we have 
$P(T_1,\dots,T_n) = P(T_{\sigma 1},\dots,T_{\sigma n})$.  Such a polynomial is
called symmetric.
Develop an algorithm for locating a polynomial $Q(X_0,\dots,X_{n-1})$ so that
$P(\alpha_1,\dots,\alpha_n) = Q(a_1,\dots,a_n)$.

\bs\centerline{Solutions}\bs

We present two solutions below.  Both solutions have the marvelous feature that
we do not depend on the roots $\alpha_1,\dots,\alpha_n$ lying in a field.  We
let them lie in any commutative ring $R$, and then simply define $f(x)$ to be
the product $(x-\alpha_1)\cdots(x-\alpha_n)$.  In fact, we might just as well
use the ring $R[T_1,\dots,T_n]$ and take $\alpha_i = T_i$, all $i$.  Then the
coefficients $a_i$ are the elementary symmetric polynomials in the variables
$T_1,\dots,T_n$. 

\bs\centerline{Solution A}\bs

This proof was nearly obtained by one of the students, is easy to explain, but
hard to invent.  We proceed by induction on $n$ and on the total
degree of $P$.  Consider the polynomial $P(T_1,\dots,T_{n-1},0)$; by induction
on the number of variables, we may write this symmetric polynomial
in the form 
$$
	P(T_1,\dots,T_{n-1},0) = Q(a'_1,\dots,a'_{n-1})
$$
where $a'_1,\dots,a'_{n-1}$ are the symmetric functions in $n-1$ variables.  We
realize that replacing $T_n$ by $0$ in $a_i$ yields $a'_i$, so it follows that
replacing $T_n$ by $0$ in
$$
	P(T_1,\dots,T_{n-1},T_n) - Q(a_1,\dots,a_{n-1})
$$
yields $0$.  Thus 
$$
	P(T_1,\dots,T_{n-1},T_n) - Q(a_1,\dots,a_{n-1})
$$
is divisible by $T_n$, and by symmetry, it must be divisible by each of the
variables, and thus divisible by their product $a_n = T_1 T_2 \cdots T_n$.  So,
we write
$$
	P(T_1,\dots,T_{n-1},T_n) = Q(a_1,\dots,a_{n-1}) + a_n R(T_1,\dots,T_n)
$$
where $R$ is a symmetric polynomial.  Since $R$ has lower degree, by induction,
we may write
$$
	R(T_1,\dots,T_n) = S(a_1,\dots,a_n)
$$
for some polynomial $S$, and arrive at
$$
	P(T_1,\dots,T_{n-1},T_n) = Q(a_1,\dots,a_{n-1}) + a_n S(a_1,\dots,a_n),
$$
as desired.

\goodbreak

\bs\centerline{Solution B}\bs

This is a composite of the proofs arrived at by the small class groups.

We consider monomials in $T_1,\dots,T_n$.  A square-free monomial is one that
is not $1$ and contains no repeated factors, i.e., it divides $T_1 \cdots T_n$.

The first observation is that any monomial $M$ can be factored {\sl uniquely}
as a product $M_1 \cdots M_s$ of square-free monomials, where each one is
divisible by the next one.  Example: $T_1^2 T_2^3 T_3 = (T_1 T_2 T_3) (T_1 T_2)
(T_2)$.  The first monomial in this factorization is the product of the
variables which occur in $M$, and so on.

Let's say that a {\sl permutation} of a monomial $T_1^{i_1} \cdots T_n^{i_n}$ is
a monomial which has the form $T_{\sigma 1}^{i_1} \cdots T_{\sigma n}^{i_n}$ for
some permutation $\sigma$.  We will use the notation $\Sigma M$ for the sum of
the permutations of $M$.  Any symmetric polynomial $P$ is a linear combination
of polynomials of the form $\Sigma M$, so it will be enough to write $\Sigma M$
in terms of elementary symmetric polynomials.

The elementary symmetric polynomials have the following form:
$$
\align
a_1 &= \Sigma T_1 = T_1 + \dots + T_n 
\\
a_2 &= \Sigma T_1 T_2 = T_1 T_2 + T_1 T_3 + T_2 T_3 + \dots + T_{n-1} T_n
\\
\dots
\\
a_{n-1} &= \Sigma T_1 T_2 \cdots T_{n-1} = T_1 \cdots T_{n-1} + \cdots + T_2 \cdots T_{n}
\\
a_n &= \Sigma T_1 T_2 \cdots T_n = T_1 T_2 \cdots T_n
\\
\endalign
$$
We will try to express $\Sigma M$ in terms of these,
so we compare $\Sigma M$ to the product 
$$(\Sigma M_1) \cdots (\Sigma M_s).$$
They aren't equal, but the difference between them can be controlled.

A typical term of $(\Sigma M_1) \cdots (\Sigma M_s)$ is a product $N_1 \cdots
N_s$, where $N_i$ is a permutation of $M_i$ for each $1 \le i \le n$.  If it
happens that each $N_i$ is divisible by $N_{i+1}$, then in fact, $N_1 \cdots
N_s$ is also a term of $\Sigma M$.  Moreover, by the uniqueness mentioned
above, each term of $\Sigma M$ arises only once in this way.

So the difference
$(\Sigma M_1) \cdots (\Sigma M_s) - (\Sigma M)$ is the sum of those terms $N_1 \cdots
N_s$ where the divisibility condition breaks down.
Take one of those terms and consider the process of rewriting it as a product
of square-free monomials, each divisible by the next one.  If we let each
monomial be one layer of a stack, so that the first monomial is on the bottom,
and force the $i$-th variable to lie in column $i$ of the stack, then the
condition about divisibility amounts to saying that the stack has no components
floating in mid-air.  Repeating our first example, $ (T_1 T_2 T_3) (T_1 T_2)
(T_2)$ would look like this.
$$
\matrix
	T_2	\\
T_1	T_2	\\
T_1	T_2	T_3
\endmatrix
$$
Now after permuting the monomials in each layer of this stack, arriving at a
state where the divisibility condition is not satisfied, we might have $(T_2 T_3
T_4) (T_1 T_4) (T_3)$, looking like this.
$$
\matrix
		T_3\\
T_1			T_4\\
	T_2	T_3	T_4
\endmatrix
$$
To rewrite this as a product of square-free monomials, each divisible by the
next one, we simply let the floating variables fall, obtaining this stack,
$$
\matrix
		T_3	T_4\\
T_1	T_2	T_3	T_4
\endmatrix
$$
which corresponds to the factorization $(T_1 T_2 T_3 T_4) (T_3 T_4)$.

We'd like to express the feeling that those stacks where some variables have
fallen correspond to monomials which are smaller in some sense, so that we can
use induction on them.

There is more than one way to do this.  One way involves putting a sort of
lexicographic ordering on the monomials, and this is what most groups did.
Another way is this: we think of each variable in a stack as having the same
mass, and regard the total potential energy of the stack as a measure of the
size of the monomial.  Thus, when permutations of the layers allow variables to
fall, the potential energy will drop.  To be precise, we define 
\define\size{\operatorname{size}}
$$
	\size(T_1^{i_1} T_2^{i_2} \cdots T_n^{i_n}) = 
	\sum_{j=1}^{i_1} j + \sum_{j=1}^{i_2} j + \cdots + \sum_{j=1}^{i_n} j.
$$

With this definition, it is now clear that the size of the monomials in
$(\Sigma M_1) \cdots (\Sigma M_s) - (\Sigma M)$ is less that the size of $M$,
so by induction on the size of monomials, we may assume that this difference
(which is symmetric) can be written in terms of the elementary symmetric
polynomials.  Since each $\Sigma M_i$ is itself an elementary symmetric
polynomial, we can write $\Sigma M$ in terms of elementary symmetric
polynomials.

\end