Author |
Topic: Symmetric Expressions (Read 1377 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Symmetric Expressions
« on: Nov 9th, 2003, 5:54am » |
 Quote  Modify
|
We will call an expression E(x1, …, xn) with n free variables rational if it is formed by means of 4 arithmetic operations (addition, subtraction, multiplication, division) on the variables.
We will call an expression symmetric if it is not changed by any permutation of variables x1, …, xn. For instance, x1 + x2 is a symmetric expression, while x1 - x2 is not.
Among all symmetric expressions of n variables the following are distinguished as elementary symmetric expressions:
A1 = x1 + … + xn
A2 = [sum]i<j xixj
A3 = [sum]i<j<k xixjxk
…
An = x1x2…xn
There is a theorem stating that every rational symmetric expression in n variables may be represented as a rational function of elementary symmetric expressions in these variables.
Find such representations for the following symmetric expressions in 3 variables:
1. x12 + x22 + x32
2. x13 + x23 + x33
3. (x1 - x2) 2(x1 - x3) 2(x2 - x3) 2
P.S. I am not sure if I put this problem under the right section. Originally, I wanted to put it under Putnam section, and give a more formal definition. But then, I thought that maybe there are more people looking at this section...
|
|
 IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Symmetric Expressions
« Reply #1 on: Nov 9th, 2003, 6:21am » |
Quote Modify
|
E1(x1,x2,x3) = A1*A1-A2-A2
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Symmetric Expressions
« Reply #2 on: Nov 9th, 2003, 8:58am » |
Quote Modify
|
E2(x1,x2,x3) = x13 + x23 + x33 = (E1(x1,x2,x3) [smiley=times.gif] A1) - (A2 [smiley=times.gif] A1) + A3 + A3 + A3
Hope that this helps... 
Barukh, your desicion to put it here was a right one !!!
|
| « Last Edit: Nov 9th, 2003, 9:56am by Dudidu » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Symmetric Expressions
« Reply #3 on: Nov 9th, 2003, 9:48am » |
Quote Modify
|
Fun!
#2 becomes simple if we note that A1A2 = 3A3 + [sum]i!=jxi2xj,
and if we expand out A13, it's clear the answer is
A13 - 3(A1A2-3A3) - 6A3 = A13 - 3A1A2 + 3A3.
As for #3, well, this might not be the best way to do it, but if we assume for the moment that x3=0, then we're looking for a function such that
E(x+y, xy, 0) = x2y2(x-y)2 = (xy)2((x+y)2-4xy),
which tells us E(A1,A2,A3) = A22 (A12-4A2) + A3F(A1,A2,A3).
Now assume x2=x3=y, then
E(x+2y, y(y+2x), xy2) = 0 = (y(y+2x))2((x+2y)2-4y(y+2x)) + xy2F(x+2y,y(y+2x),xy2),
where F is cubic, so it takes the form F(X,Y,Z)=aZ+bXY+cX3.
Then axy2+by(x+2y)(y+2x)+c(x+2y)3 = 4y3 + 12x2y + 15xy2 - 4x3.
The x3 can only come from one place, so c=-4, then b=18, and a=-27.
E(A1,A2,A3) = A22 (A12-4A2) + A3(18A1A2 -4A13 -27A3).
Of course, that's assuming the answer is a polynomial, but what are you gonna do?
[Edit]It's probably easier to substitute specific values for x1,x2,x3 to get a linear equation in a,b,c; do this 3 times and solve them.[/Edit]
|
| « Last Edit: Nov 9th, 2003, 1:41pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Symmetric Expressions
« Reply #4 on: Nov 10th, 2003, 12:21pm » |
Quote Modify
|
That's amazing! In fact, only the third expression is a "tough nut", but at least for it - I thought - it will take some time before the first solution. But this forum has enough smart people to ruin my hopes 
As for the last expression - I liked Eigenray's solution. Here's another approach, which requires some additional facts.
[smiley=blacksquare.gif]
First. define the following (symmetric) expressions: Pk = x1k + x2k + x3k. Note that in our notation P1 = A1, P2 = E1, P3 = E2.
Next, consider the following 3x3 matrix V:
[ 1 1 1 ; x1 x2 x3 ; x12 x22 x32 ]
It’s called the Vandermode matrix; it’s determinant is well known (is easily verified) |V| = (x2–x1)(x3–x1)(x3–x 2). Then,
E3 = |V|2 = |VVT| = | 3 P1 P2 ; P1 P2 P3 ; P2 P3 P4 |
So, it remains to express P4 in terms of A’s. To do this, note, that the equaition x3 - A1x2 + A2x - A3 = 0 has roots x1, x2, x3. Therefore, P3 - A1P2 + A2P1 - A3 = 0, and P4 = A1P3 - A2P2 + A3P1.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Symmetric Expressions
« Reply #5 on: Nov 10th, 2003, 8:49pm » |
Quote Modify
|
Neat; I don't think I've seen that before.
[sum]k=0n (-1)kAkPn-k = 0
It extends to sums of more than n terms also, with a simple double induction, except that we need to replace P0 with the constant n:
If we add on the element x, then AkPn-k becomes (Ak + xAk-1)(Pn-k + xn-k); all the new terms cancel except we get an extra -x(Pn-1 - A1Pn-2+ ... [pm] An-2P1 [pm] An-1(n-1)), which is zero by induction.
As a consequence, we can let Pk=[zeta](2k), and Ak = 1/(2k+1)!, by setting the infinite product for sin(x)/x equal to its power series. Then out pops
[sum]k=0n-1 (-1)k[pi]2k/(2k+1)! [zeta](2(n-k)) + (-1)nn[pi]2n/(2n+1)! = 0
n + [sum]k=1n (-1)k(2n+1C2k) (2k)!/[pi]2k [zeta](2r) = 0
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Symmetric Expressions
« Reply #6 on: Mar 8th, 2004, 12:59pm » |
Quote Modify
|
Here's another approach to #2.
Clearly E2 = x12 + x22 + x32 = A12 - 2A2.
x1, x2, x3 are roots of w3 - A1w2 + A2w - A3 = 0. Substitute and add:
E3 - A1E2 + A2A1 - 3A3 = 0.
Hence E3 = A1(A12 - 2A2) - A1A2 + 3A3 = A13 - 3A1A2 + 3A3.
|
| « Last Edit: Mar 9th, 2004, 1:56pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Earendil
Newbie
 
Gender:
Posts: 46
|
|
Re: Symmetric Expressions
« Reply #7 on: Mar 8th, 2004, 1:19pm » |
Quote Modify
|
Funny, it looks like this has something to do with Girard equations...  I'm not sure though, just a guess in the dark.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Symmetric Expressions
« Reply #8 on: Mar 9th, 2004, 5:28am » |
Quote Modify
|
on Mar 8th, 2004, 12:59pm, NickH wrote:| Multiply by wn to get a recurrence relation for An+3 in terms of An+2, An+1, An, where n > 0. |
|
Note, that there are exactly n elementary symmetric expressions of n variables, and only An may be computed using this approach, after A1 through An-1 are known.
What this gives, however, is the way to compute Pm in terms of Pm-1, Pm-2, ..., Pm-n (E's instead of P's in your notation).
Does it make sense?
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Symmetric Expressions
« Reply #9 on: Mar 9th, 2004, 1:59pm » |
Quote Modify
|
Thanks, Barukh, that was a typo. I meant to put En, by which I meant the sum of nth powers. I've removed the line.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print