Symmetric Polynomials

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 \).

Definition
 

The polynomial \( P(x_1,x_2,\dots,x_n) \) is {\em 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 {\em 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". 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 {\em 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:

Theorem 7.1
 

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 \).

Example
 

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 \).

Theorem 7.2
 

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.

Theorem 7.3 (Newton’s Theorem on Symmetric Polynomials)
 

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;\\ 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.

Problem 20
 

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.\]


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us