Polynomials (Table of contents)
# Symmetric Polynomials

**Definition**
**Theorem 7.1 **
**Example**
**Theorem 7.2 **
**Theorem 7.3 (Newton’s Theorem on Symmetric Polynomials)**
**Problem 20**

A *symmetric polynomial* in variables \(x_1,\dots,x_n\) is every
polynomial that is not varied by permuting the indices of the
variables. For instance, polynomial \(x_1^2\) is symmetric as a
polynomial in \(x_1\) (no wonder), but is not symmetric as a
polynomial in \(x_1,x_2\) as changing places of the indices 1 and 2
changes it to the polynomial \(x_2^2\).

The polynomial
\(P(x_1,x_2,\dots,x_n)\) is *symmetric*
if, for every permutation \(\pi\) of \(\{1\), \(2\), \(\dots\), \(n\}\),
\(P(x_1,x_2,\dots,x_n)\equiv
P(x_{\pi(1)},x_{\pi(2)},\dots,x_{\pi(n)})\).

An obvious property of a symmetric polynomial is that its coefficients at two terms of the forms \(x_1^{i_1}\cdots x_n^{i_n}\) and \(x_1^{j_1}\cdots x_n^{j_n}\), where \((j_1,\dots,j_n)\) is a permutation \((i_1,\dots,i_n)\), always coincide. For example, if the expansion of a symmetric polynomial in \(x,y,z\) contains the terms \(x^2y\), then it also contains \(x^2z,xy^2\), etc, with the same coefficient.

Thus, the polynomials \(\sigma_k\) \((1\leq k\leq n)\) introduced in section 2 are symmetric. Also symmetric is e.g. the polynomial \(x_1^2+x_2^2\).

A symmetric polynomial is said to be *homogenous* if all its
terms are of the same degree. Equivalently, polynomial \(T\) is
homogenous of degree \(d\) if \(T(tx_1,\dots,tx_n)=t^dT(x_1,\dots,x_n)\)
holds for all \(x\) and \(t\). For instance, \(x_1^2+x_2^2\) is homogenous
of degree \(d=2\), but \(x_1^2+x_2^2+1\), although symmetric, is not
homogenous.

Every symmetric polynomial in \(x_1,\dots,x_n\) can be written as a
sum of homogenous polynomials. Moreover, it can also be represented
as a linear combination of certain ``bricks_quot_. These bricks are the
polynomials \[T_a=\sum x_1^{a_{i_1}}\cdots x_n^{a_{i_n}}
\quad\quad\quad\quad\quad (\ast)\] for each \(n\)-tuple \(a=(a_1,\dots,a_n)\) of nonnegative
integers with \(a_1\geq\cdots\geq a_n\), where the summation goes over
all permutations \((i_1,\dots,i_n)\) of the indices \(1,\dots,n\). In
the expression for \(T_a\) the same summand can occur more than once,
so we define \(S_a\) as the sum of the *different* terms in
\((\ast)\). The polynomial \(T_a\) is always an integral multiple of
\(S_a\). For instance,
\[T_{(2,2,0)}=2(x_1^2x_2^2+x_2^2x_3^2+x_3^2x_1^2)=2S_{(2,2,0)}.\]

All the \(n\)-tuples \(a\) of degree \(d=a_1+\cdots+a_n\) can be ordered in a lexicographic order so that \[a > a^{\prime}\quad\mbox{if}\quad s_1=s^{\prime}_1,\dots,s_k=s^{\prime}_k\mbox{ and }s_{k+1} > s^{\prime}_{k+1}\;\mbox{ for some } k\geq1,\] where \(s_i=a_1+\cdots+a_i\). In this ordering, the least \(n\)-tuple is \(m=(x+1,\dots,x+1,x,\dots,x)\), where \(x=[d/n]\) and \(x+1\) occurs \(d-n[d/n]\) times.

The polynomials \(T_a\) can be multiplies according to the following simple formula:

If \(a=(a_1,\dots,a_n)\) and \(b=(b_1,\dots,b_n)\) are \(n\)-tuples of nonnegative integers, it holds that \[T_a\cdot T_b= \sum_{\pi}T_{a+\pi(b)},\] where the sum goes over all permutations \(\pi(b)\) of the \(n\)-tuple \(b\). (We define \((x_i)_{i=1}^n+(y_i)_{i=1}^n= (x_i+y_i)_{i=1}^n\).)

There are infinitely many mentioned bricks, and these are obviously not mutually independent. We need simpler elements which are independent and using which one can express every symmetric polynomial by basic operations. It turns out that these atoms are \(\sigma_1,\dots,\sigma_n\).

The following polynomials in \(x,y,z\) can be written in terms of \(\sigma_1,\sigma_2,\sigma_3\):

\(xy+yz+zx+x+y+z=\sigma_2+\sigma_1\);

\(x^2y+x^2z+y^2x+y^2z+z^2x+z^2y=\sigma_1\sigma_2-3\sigma_3\);

\(x^2y^2+y^2z^2+z^2x^2=\sigma_2^2-2\sigma_1\sigma_3\).

Every symmetric polynomial in \(x_1,\dots,x_n\) can be represented in the form of a polynomial in \(\sigma_1,\dots, \sigma_n\). Moreover, a symmetric polynomial with integer coefficients is also a polynomial in \(\sigma_1,\dots,\sigma_n\) with integer coefficients.

The proof of the previous theorem also gives us an algorithm for expressing each symmetric polynomial in terms of the \(\sigma_i\). Nevertheless, for some particular symmetric polynomials there are simpler formulas.

If we denote \(s_k=x_1^k+x_2^k+\dots+x_n^k\), then: \[\begin{array}{rcl} k\sigma_k&=&s_1\sigma_{k-1}-s_2\sigma_{k-2}+\dots+(-1)^ks_{k-1} \sigma_1+(-1)^{k+1}s_k;\newline s_m&=&\sigma_1s_{m-1}-\sigma_2s_{m-2}+\dots+ (-1)^{n-1}\sigma_ns_{m-n}\quad\mbox{za }m\geq n.\end{array}\] (All the polynomials are in \(n\) variables.)

The proof of the previous theorem also gives us an algorithm for expressing each symmetric polynomial in terms of the \(\sigma_i\). Nevertheless, for some particular symmetric polynomials there are simpler formulas.

Suppose that complex numbers \(x_1,x_2,\dots,x_k\) satisfy \[x_1^j+x_2^j+\dots+x_k^j=n,\hspace{5mm}\mbox{ for \(j=1,2,\dots, k\),}\] where \(n,k\) are given positive integers. Prove that \[(x-x_1)(x-x_2)\dots(x-x_k)=x^k-\binom n1 x^{k-1}+\binom n2 x^{k-2}- \dots+(-1)^k\binom nk.\]