15
$\begingroup$

How many real solutions $(r_1, r_2, \cdots, r_n)$ are there such that $(r_1, r_2, \cdots, r_n)$ are the roots of the polynomials $x^{n} + r_1 x^{n-1} + r_2 x^{n-2} + \cdots + r_n$

For $n = 2, 3, 4$ I found $2, 4, 5$ real solutions, and $2, 6$, and according to WA and assuming a double root, $24$ complex solutions. Is it possible to generalize this for real/complex solutions? In particular, a proof (or dispute of the fact) that the number of complex solutions follows the factorials, and if possible also find a pattern for the number of real solutions. I would prefer not an answer that is just a computation to show a pattern up to some $n$.

Edited because of bounty.

$\endgroup$
  • 1
    $\begingroup$ From Vieta's formulas, it follows that $\displaystyle\prod_{k=1}^{n-1}r_k=(-1)^n$, and that $\displaystyle\sum_{k=2}^nr_k=-2r_1$. $\endgroup$ – Lucian Dec 24 '13 at 16:41
6
+50
$\begingroup$

First, we may note that if $(r_1,\ldots,r_n)$ is a solution for the degree $n$ problem, then $(r_1,\ldots,r_n,0)$ is a solution for the degree $n+1$ problem, and vice versa.

Second, as has already been pointed out by benh, the solution space for $r=(r_1,\ldots,r_n)$ is given by the solutions of the set of the $n$ polynomial equations $$ \sigma_k(-r)=\sigma_k(-r_1,\ldots,-r_n)=r_k $$ where $\sigma_k$ is the $k$th symmetric function, and the left-hand side are the coefficients of $\prod_{i=1}^n(t-r_i)$. These have degrees $1,2,\ldots,n$.

In the generic case, you can count the number of solutions by multiplying the degrees of the polynomials, which tells us there should be $n!$ complex solutions. This assumes we count roots with multiplicities, that there are no roots "at infinity", and that equations form a complete intersection (i.e. the solution space consists of a discrete set of points and no higher-dimensional sets).

If the solution space has positive dimension, there would be solutions "at infinity". By "at infinity", I mean we embed $n$-space into the projective $n$-space, and the new point are the ones at infinity. A point at infinity can be described by a "line" (i.e. complex plane) through the origin: i.e. by $(sx_1,\ldots,s_xn)$ as $s$ goes to infinity, where the $x_i$ are not all zero. So, I need to show that there are no solutions at infinity.

More formally, the projective $n$-space is given by the ratios $[x_0:x_1:\ldots:x_n]$ where not all $x_i$ are zero, which is the same as saying that the projective point corresponds to the line (complex plane) $(sx_0,\ldots,sx_n)$ (i.e. these all represent the same point in the projective space). The regular $n$-space is the subspace given by $[1:x_1:\ldots:x_n]$, while the points at infinity are those with $x_0=0$.

If there are solutions at infinity, then the leading terms (i.e. top degree terms) of the $n$ polynomials $\sigma_k(-r)-r_k$ must all be zero at that point. For $k>1$, the leading term is simply $\sigma_k(-r)$. If $\sigma_n(-x)=0$ for some $x=(x_1,\ldots,x_n)$, then one of the $x_i$ must be zero; if also $\sigma_{n-1}(-x)=0$, then another one must be zero; and so on down to $\sigma_2(-x)=0$, hence $n-1$ of the $x_i$ must be zero. Finally, we have the last equation, $x_1+\sigma_1(x)=2x_1+x_2+\cdots+x_n=0$ with $n-1$ of the $x_i$ equal to zero, which forces the last one to be zero as well. Thus, there are no solutions at infinity.

So, counting complex solutions with multiplicity yields $n!$ solutions.

However, I suspect it would be a lot tougher to identify the real solutions.

$\endgroup$
  • $\begingroup$ So if I understand you correctly, you have a set of $n$ equations, each of degree $1, 2, \dots, n$, so each has independently $1, 2, \dots, n$ solutions. Thus, when you multiply all of the possibilities together in a combinatorics-esque style, you get $n!$? (Sorry, I'm not very knowledgable about this) $\endgroup$ – MCT Mar 23 '14 at 1:00
  • 2
    $\begingroup$ In $n$ dimensional space, the zero set of a degree $p$ polynomial will be a $n-1$ dimensional "surface" of degree $p$ (if "degree" is defined in the right way). If you take $k$ polynomials of degrees $p_1,\ldots,p_k$, you'll get a $n-k$ dimensional "surface" of degree $p_1\cdots p_k$. This is true for the generic case (i.e. except special cases). In the projective $n$ space, if you count solutions with multiplicity, the only special case is when the solution has higher dimensionality than $n-k$. $\endgroup$ – Einar Rødland Mar 23 '14 at 1:51
  • $\begingroup$ Okay, thank you. Assuming no solution comes within the next couple days covering the real solutions, I will award you the bounty. $\endgroup$ – MCT Mar 24 '14 at 0:04
2
$\begingroup$

The coefficient $a_k$ of the polynomial $f$ is (up to a sign) the $k$-th elementary symmetric polynomial in $n$ variables evaluated at the complex roots of $f$, that is:

$$ \begin{eqnarray} r_1 &=& -e_1(r_1,...,r_n)&=&r_1+...+r_n \\ r_2 &=& e_2(r_1,...,r_n)&=&r_1r_2+r_1r_3...+r_{n-1}r_n \\ r_n &=& (-1)^ne_n(r_1,...,r_n)&=&r_1\cdot \cdot \cdot r_n \end{eqnarray}$$

So from an algebraic-geometric point of view, you are asking for the vanishing set of the set of polynomials $$\Big(-e_1(X_1,...,X_n)-X_1\;,\;\dots\;,\;(-1)^ne_n(X_1,...,X_n)-X_n \Big).$$

As the elementary symmetric polynomials generate the ring of all symmetric polynomials (hence the name), the set of all solutions should be a finite algebraic subset of $\Bbb C^n$.

From an analytical point of view, the solutions are determined by these $n$ algebraic equations.

$\endgroup$
  • $\begingroup$ Right, I understand as much. So are you contending that there are no generalizations, not even for the number of real/complex roots? $\endgroup$ – MCT Dec 24 '13 at 17:02
  • $\begingroup$ My answer was intended to point on some structure I would start with to analyze the problem. Basically, I am contending that one could give algebraic geometry a chance to solve this problem, because I doubt that closed forms for the coefficients will help us here. $\endgroup$ – benh Dec 24 '13 at 17:27
1
$\begingroup$

Alpha confirms your counts for degree $3$. The number of complex solutions look like the triangular numbers. That is surprising-I would expect the factorials, as that is the product of the degrees of the equations. Unfortunately, when I went fourth degree, Alpha started only giving the value of one variable, not all four. I did get $23$ solutions out of Alpha (clicking on more roots) for the fourth degree equation. Five of them were $r_1=1$ but the others were all distinct. There were two other real solutions for $r_1$, but it didn't show the rest were real.

$\endgroup$
  • $\begingroup$ I used fourth degree for alpha as well, which is how I got 5 real 10 complex. wolframalpha.com/input/… $\endgroup$ – MCT Dec 24 '13 at 16:39
  • 2
    $\begingroup$ In the window with complex solutions there is a button for More Solutions which got me to 18 after a few clicks. I suspect one of the real solutions (probably $0,0,0,0$) is a double root, which gets us to 24 $\endgroup$ – Ross Millikan Dec 24 '13 at 16:45
  • $\begingroup$ Also, why do you say the complex solutions look like triangular numbers? Is $1, 2, 6, 24$ not the factorials? $\endgroup$ – MCT Dec 24 '13 at 17:08
  • $\begingroup$ @user92774: yes, but you had $2,6,10$ in there at the time. I was just noticing that they were triangular. $\endgroup$ – Ross Millikan Dec 24 '13 at 17:16
1
$\begingroup$

Using this code to generate the equations in Mathematica

n = 7;
vars = {a, b, c, d, e, f, g};
eqs = Table[(-1)^i SymmetricPolynomial[i, vars] - vars[[i]], {i, n}];
eqs // InputForm

and Macaulay2 to compute dimensions and degrees, we get:

Macaulay2, version 1.5
warning: sample Factory finite field addition table file missing, factorization may fail: /usr/share/Macaulay2/Core/factory/gftable.31.2
with packages: ConwayPolynomials, Elimination, IntegralClosure, LLLBases,
               PrimaryDecomposition, ReesAlgebra, TangentCone

i1 : R = QQ[a, b, c]

o1 = R

o1 : PolynomialRing

i2 : I = ideal (-2*a - b - c, -b + a*b + a*c + b*c, -c - a*b*c);

o2 : Ideal of R

i3 : dim I

o3 = 0

i4 : degree I

o4 = 6

i5 : R = QQ[a, b, c, d];

i6 : I = ideal (-2*a - b - c - d, -b + a*b + a*c + b*c + a*d + b*d + c*d, 
      -c - a*b*c - a*b*d - a*c*d - b*c*d, -d + a*b*c*d);

o6 : Ideal of R

i7 : dim I

o7 = 0

i8 : degree I

o8 = 24

i9 : R = QQ[a, b, c, d, e];

i10 : I = ideal (-2*a - b - c - d - e, -b + a*b + a*c + b*c + a*d + b*d + c*d + 
        a*e + b*e + c*e + d*e, -c - a*b*c - a*b*d - a*c*d - b*c*d - 
        a*b*e - a*c*e - b*c*e - a*d*e - b*d*e - c*d*e, 
       -d + a*b*c*d + a*b*c*e + a*b*d*e + a*c*d*e + b*c*d*e, 
       -e - a*b*c*d*e);

o10 : Ideal of R

i11 : dim I

o11 = 0

i12 : degree I

o12 = 120

i13 : R = QQ[a, b, c, d, e, f];

i14 : I = ideal (-2*a - b - c - d - e - f, -b + a*b + a*c + b*c + a*d + b*d + 
        c*d + a*e + b*e + c*e + d*e + a*f + b*f + c*f + d*f + e*f, 
       -c - a*b*c - a*b*d - a*c*d - b*c*d - a*b*e - a*c*e - b*c*e - 
        a*d*e - b*d*e - c*d*e - a*b*f - a*c*f - b*c*f - a*d*f - b*d*f - 
        c*d*f - a*e*f - b*e*f - c*e*f - d*e*f, 
       -d + a*b*c*d + a*b*c*e + a*b*d*e + a*c*d*e + b*c*d*e + a*b*c*f + 
        a*b*d*f + a*c*d*f + b*c*d*f + a*b*e*f + a*c*e*f + b*c*e*f + 
        a*d*e*f + b*d*e*f + c*d*e*f, -e - a*b*c*d*e - a*b*c*d*f - 
        a*b*c*e*f - a*b*d*e*f - a*c*d*e*f - b*c*d*e*f, -f + a*b*c*d*e*f);

o14 : Ideal of R

i15 : dim I

o15 = 0

i16 : degree I

o16 = 720

i17 : R = QQ[a, b, c, d, e, f, g];

i18 : I = ideal (-2*a - b - c - d - e - f - g, -b + a*b + a*c + b*c + a*d + b*d + 
        c*d + a*e + b*e + c*e + d*e + a*f + b*f + c*f + d*f + e*f + 
        a*g + b*g + c*g + d*g + e*g + f*g, -c - a*b*c - a*b*d - a*c*d - 
        b*c*d - a*b*e - a*c*e - b*c*e - a*d*e - b*d*e - c*d*e - a*b*f - 
        a*c*f - b*c*f - a*d*f - b*d*f - c*d*f - a*e*f - b*e*f - c*e*f - 
        d*e*f - a*b*g - a*c*g - b*c*g - a*d*g - b*d*g - c*d*g - a*e*g - 
        b*e*g - c*e*g - d*e*g - a*f*g - b*f*g - c*f*g - d*f*g - e*f*g, 
       -d + a*b*c*d + a*b*c*e + a*b*d*e + a*c*d*e + b*c*d*e + a*b*c*f + 
        a*b*d*f + a*c*d*f + b*c*d*f + a*b*e*f + a*c*e*f + b*c*e*f + 
        a*d*e*f + b*d*e*f + c*d*e*f + a*b*c*g + a*b*d*g + a*c*d*g + 
        b*c*d*g + a*b*e*g + a*c*e*g + b*c*e*g + a*d*e*g + b*d*e*g + 
        c*d*e*g + a*b*f*g + a*c*f*g + b*c*f*g + a*d*f*g + b*d*f*g + 
        c*d*f*g + a*e*f*g + b*e*f*g + c*e*f*g + d*e*f*g, 
       -e - a*b*c*d*e - a*b*c*d*f - a*b*c*e*f - a*b*d*e*f - a*c*d*e*f - 
        b*c*d*e*f - a*b*c*d*g - a*b*c*e*g - a*b*d*e*g - a*c*d*e*g - 
        b*c*d*e*g - a*b*c*f*g - a*b*d*f*g - a*c*d*f*g - b*c*d*f*g - 
        a*b*e*f*g - a*c*e*f*g - b*c*e*f*g - a*d*e*f*g - b*d*e*f*g - 
        c*d*e*f*g, -f + a*b*c*d*e*f + a*b*c*d*e*g + a*b*c*d*f*g + 
        a*b*c*e*f*g + a*b*d*e*f*g + a*c*d*e*f*g + b*c*d*e*f*g, 
       -g - a*b*c*d*e*f*g);

o18 : Ideal of R

i19 : dim I

o19 = 0

i20 : degree I

o20 = 5040
$\endgroup$
  • $\begingroup$ Ah. I have a sign wrong! I'll fix this later. $\endgroup$ – Mariano Suárez-Álvarez Dec 24 '13 at 17:34
  • $\begingroup$ It looks like it is confirming that there are $n!$ solutions for degree $n$, at least up to $n=8$ Correct? $\endgroup$ – Ross Millikan Dec 24 '13 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.