Find a method by which one can compute the coefficients of $P(x) = x^6 + a_1x^5 + \cdots+ a_6$ from the roots of $P(x) = 0$ by performing not more than $15$ additions and $15$ multiplications.
Problem
Source:
Tags: algebra, polynomial, roots, algorithm, IMO Shortlist
31.08.2010 02:55
Let the roots be $r_1, r_2, r_3, r_4, r_5, r_6$. Then calculate: $r_1+r_2=a$ $r_1r_2=b$ $r_3+r_4=c$ $r_3r_4=d$ $r_5+r_6=e$ $r_5r_6=f$ $a+c=g=r_1+r_2+r_3+r_4$ $g+e=-a_1=r_1+r_2+r_3+r_4+r_5+r_6$ $eg=h=r_1r_5+r_2r_5+r_3r_5+r_4r_5+r_1r_6+r_2r_6+r_3r_6+r_4r_6$ $ac=i=r_1r_3+r_2r_3+r_1r_4+r_2r_4$ $b+d=j=r_1r_2+r_3r_4$ $i+j=k=r_1r_2+r_1r_3+r_1r_4+r_2r_3+r_2r_4+r_3r_4$ $k+h=l=r_1r_2+r_1r_3+r_1r_4+r_2r_3+r_2r_4+r_3r_4+r_1r_5+r_2r_5+r_3r_5+r_4r_5+r_1r_6+r_2r_6+r_3r_6+r_4r_6$ $l+f=a_2=r_1r_2+r_1r_3+r_1r_4+r_1r_5+r_1r_6+r_2r_3+r_2r_4+r_2r_5+r_2r_6+r_3r_4+r_3r_5+r_3r_6+r_4r_5+r_4r_6+r_5r_6$ $ke=m=r_1r_2r_5+r_1r_3r_5+r_1r_4r_5+r_2r_3r_5+r_2r_4r_5+r_3r_4r_5+r_1r_2r_6+r_1r_3r_6+r_1r_4r_6+r_2r_3r_6+r_2r_4r_6+r_3r_4r_6$ $ad=n=r_1r_3r_4+r_2r_3r_4$ $bc=o=r_1r_2r_3+r_1r_2r_4$ $n+o=p=r_1r_2r_3+r_1r_2r_4+r_1r_3r_4+r_2r_3r_4$ $gf=q=r_1r_5r_6+r_2r_5r_6+r_3r_5r_6+r_4r_5r_6$ $m+q=r=r_1r_2r_5+r_1r_3r_5+r_1r_4r_5+r_2r_3r_5+r_2r_4r_5+r_3r_4r_5+r_1r_2r_6+r_1r_3r_6+r_1r_4r_6+r_2r_3r_6+r_2r_4r_6+r_3r_4r_6+r_1r_5r_6+r_2r_5r_6+r_3r_5r_6+r_4r_5r_6$ $r+p=-a_3=r_1r_2r_3+r_1r_2r_4+r_1r_2r_5+r_1r_2r_6+r_1r_3r_4+r_1r_3r_5+r_1r_3r_6+r_1r_4r_5+r_1r_4r_6+r_1r_5r_6+r_2r_3r_4+r_2r_3r_5+r_2r_3r_6+r_2r_4r_5+r_2r_4r_6+r_2r_5r_6+r_3r_4r_5+r_3r_4r_6+r_3r_5r_6+r_4r_5r_6$ $bd=s=r_1r_2r_3r_4$ $kf=t=r_1r_2r_5r_6+r_1r_3r_5r_6+r_1r_4r_5r_6+r_2r_3r_5r_6+r_2r_4r_5r_6+r_3r_4r_5r_6$ $ep=u=r_1r_2r_3r_5+r_1r_2r_4r_5+r_1r_3r_4r_5+r_2r_3r_4r_5+r_1r_2r_3r_6+r_1r_2r_4r_6+r_1r_3r_4r_6+r_2r_3r_4r_6$ $t+u=v=r_1r_2r_3r_5+r_1r_2r_4r_5+r_1r_3r_4r_5+r_2r_3r_4r_5+r_1r_2r_3r_6+r_1r_2r_4r_6+r_1r_3r_4r_6+r_2r_3r_4r_6+r_1r_2r_5r_6+r_1r_3r_5r_6+r_1r_4r_5r_6+r_2r_3r_5r_6+r_2r_4r_5r_6+r_3r_4r_5r_6$ $v+s=a_4=r_1r_2r_3r_4+r_1r_2r_3r_5+r_1r_2r_3r_6+r_1r_2r_4r_5+r_1r_2r_4r_6+r_1r_2r_5r_6+r_1r_3r_4r_5+r_1r_3r_4r_6+r_1r_3r_5r_6+r_1r_4r_5r_6+r_2r_3r_4r_5+r_2r_3r_4r_6+r_2r_3r_5r_6+r_2r_4r_5r_6+r_3r_4r_5r_6$ $pf=w=r_1r_3r_4r_5r_6+r_2r_3r_4r_5r_6+r_3r_1r_2r_5r_6+r_4r_1r_2r_5r_6$ $se=x=r_1r_2r_3r_4r_5+r_1r_2r_3r_4r_6$ $w+x=-a_5=r_1r_2r_3r_4r_5+r_1r_2r_3r_4r_6+r_1r_2r_3r_5r_6+r_1r_2r_4r_5r_6+r_1r_3r_4r_5r_6+r_2r_3r_4r_5r_6$ $sf=a_6=r_1r_2r_3r_4r_5r_6$ Now this may seem a little dull, but the motivation of the solution is this: first, find the symmetric sums for pairs of 2 variables, then combine root 1, 2, 3 and 4's symmetric sums to make all the symmetric sums for those 4, then use those and root 5 and 6's to create the sums for 6 variables. I think no matter what order you compute the symmetric sums, and how many you take at a time, it will still be 15 additions and 15 multiplications. Someone else can try it by splitting them into groups of 3 and 3 and post their findings, if they wish.
03.09.2010 07:34
Alternatively, we note that $15= 6\ choose 2$. Therefore, we will show by induction that we can get all symmetric sums of $r_1,r_2,...,r_n$ in $n \choose 2$ additions and multiplications. This is trivial for $n=1$, so now assume the result holds for $n=k$, we will show it holds for $n=k+1$. Assume $n=k+1$. Use $k \choose 2$ additions and multiplications to get the symmetric polynomials of the $r_1,r_2,...,r_k$. Then we have $k$ additions and $k$ multiplications left. If $T_r$ is the symmetric polynomial of degree $r$ for the $r_1,r_2,...,r_k$, then we can create $r_{k+1}T_1$, $r_{k+1}T_2$, ... , $r_{k+1}T_k$. $S_r=r_{k+1}T_{r-1}+T_r$, where $r_{k+1}T_0=r_{k+1}$. Then $S_r$ is the symmetric polynomial of degree $r$ of $r_1,r_2,...r_{k+1}$. Cheers, Rofler