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 … )

This entry was posted in Notes and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s