Symmetric Polynomials (I)

[ Background required: knowledge of basic algebra and polynomial operations. ]

After a spate of posts on non-IMO related topics, we’re back on track.

Here, we shall look at polynomials in n variables, e.g. P(x, y, z) when n = 3. Such polynomials are said to be symmetric if it remains the same after we swap any two variables. E.g. P(x, y) = xy + 3 is symmetric since P(x, y) = P(y, x). Likewise, $P(x,y) = x^3 + y^3 + 3xy$ is symmetric while $P(x,y,z) = x^3 - y^3 + z^3$ is not symmetric.

Let’s consider the case n=2. Two obvious symmetric polynomials in x,y are the sum and product:

$P(x,y) = x+y, \quad Q(x,y) = xy.$

Key result. Any symmetric polynomial in x and y with integer coefficients can be expressed as a polynomial in P and Q with integer coefficients.

In particular, if the sum and product of x and y are integers, then $x^n + y^n$ is also an integer (for any natural number n) although x and y themselves may not be integral: e.g. $x = 3 + \sqrt 2$ , y = 3 – \sqrt 2$.

Example. Consider the polynomial $x^3 + y^3$ . This can be written as $(x+y)(x^2 - xy + y^2) = P\cdot (x^2 + y^2 - Q)$ and then we use the substitution $x^2 + y^2 = (x+y)^2 - 2xy = P^2 - 2Q$ . So $x^3 + y^3 = P^3 - 3PQ$ .

Better Method. Instead of tediously calculating $x^n + y^n$ in this manner, we denote $S_n = x^n + y^n$ for integer n and proceed to derive a recurrence relation in $S_n$ . First, suppose we fix x and y; let $T^2 - aT + b$ be the quadratic equation with roots x and y. Then $a = x+y = P(x,y)$ and $b = xy = Q(x,y)$ . Now since x and y are both roots of that quadratic equation, we have:

$x^2 - ax + b = 0, \quad y^2 - ay + b = 0.$

Multiplying the two equations by $x^n, y^n$ respectively, we obtain:

$x^{n+2} - a x^{n+1} + b x^n = 0, \quad y^{n+2} - a y^{n+1} + b y^n = 0.$

Adding them, we get: $S_{n+2} - a S_{n+1} + b S_{n+2} = 0$ . Since this holds for any x and y, we see that $S_{n+2} = P \cdot S_{n+1} - Q\cdot S_n$ as polynomials in x and y.

Example. Now we can express $x^5 + y^5$ as a polynomial in P and Q with just a bit of work. Starting with $S_0 = x^0 + y^0 = 2$ and $S_1 = x+y = P$ , we have:

$S_2 = P \cdot S_1 - Q \cdot S_0 = P^2 - 2Q$ ;
$S_3 = P \cdot S_2 - Q \cdot S_1 = P^3 - 3PQ$ ;
$S_4 = P \cdot S_3 - Q \cdot S_2 = P^4 - 4P^2 Q + 2Q^2$ ;
$S_5 = P \cdot S_4 - Q \cdot S_3 = P^5 - 5P^3 Q + 5 PQ^2$ .

Now we can use this technique to solve the following problems.

Problem 1. Solve the simultaneous equations $x+y = 2, x^5 + y^5 = 82$ .

Solution. We consider the quadratic equation $T^2 - pT + q = 0$ whose roots are x and y. In other words, $T^2 - pT + q \equiv (T-x)(T-y)$ as polynomials. From the above computations, we have $p = x+y = 2$ and thus

$82 = x^5 + y^5 = p^5 - 5p^3 q + 5pq^2 \implies q^2 - 4q = 5$ .

Solving for q gives $q = 5, 1$ . The first case gives complex roots while the second case gives $(x,y) = (1+\sqrt 2, 1-\sqrt 2)$ or $(1 - \sqrt 2, 1 + \sqrt 2)$ . ♦

Note. An alternate solution exists, via the substitution $x = 1 + t, y = 1-t$ . Try it!

Problem 2 (AIME 1990 Q15) Let a, b, x, y be real numbers such that:

$ax + by = 3, \quad ax^2 + bx^2 = 7, \quad ax^3 + by^3 = 16, \quad ax^4 + by^4 = 42.$

Compute $ax^5 + by^5$ . [ Note: it may not be possible to arrive at the answer via guesswork; in fact, a, b, x, y may well be irrational, but the above sums turn out to be rational. ]

Solution. We consider the quadratic equation $T^2 - pT + q = 0$ whose roots are x and y. In other words, $T^2 - pT + q \equiv (T-x)(T-y)$ as polynomials. As above, we get $x^2 - px + q = 0$ and $y^2 - py + q = 0$ . Multiplying the two equations by $ax^n$ and $by^n$ respectively, we get:

$(ax^{n+2}) - p(ax^{n+1}) + q(ax^n) = 0, \quad (by^{n+2}) - p(by^{n+1}) + q(by^n) = 0.$

Now we denote $S_n = ax^n + by^n$ . Upon adding the above two equations, we get a recurrence:

$S_{n+2} = p\cdot S_{n+1} - q\cdot S_n.$

We are given: $S_1 = 3$ , $S_2 =7$ , $S_3 = 16$ , $S_4 = 42$ . Substituting into the recurrence relation above, we obtain:

$16 = 7p - 3q, \quad 42 = 16p - 7q$

which is wholly linear! So we easily solve that to obtain $p=-14, q=-38$ and the final answer is:

$ax^5 + by^5 = S_5 = -14 S_4 + 38 S_3 = 20$ . ♦

Exercise 1. Suppose x and y are roots of $T^2 - 3T + 1 = 0$ . Find the quadratic equation whose roots are $x^3 + y^2 - 3x + 1$ and $y^3 + x^2 - 3y + 1$ .

[Hint : if you do it “right”, the calculation should not be too tedious.]

Exercise 2. (USSR) Suppose α and β are roots of the equation $x^2 + px + 1 = 0$ ; γ and δ are roots of the equation $x^2 + qx + 1 = 0$ . Prove that

$(\alpha - \gamma)(\beta - \gamma)(\alpha +\delta)(\beta + \delta) = q^2 - p^2.$

Exercise 3. Prove that if P(x, y) is a symmetric polynomial which is divisible by (x – y), then it is in fact divisible by $(x-y)^2$ .

(To be continued … )

1 Response to Symmetric Polynomials (I)

Vanya says:

February 7, 2020 at 10:18 am

Could you please provide your email address to me?