4 ms·

As there's no formula for degree-5 polynomials and above, how do you distinguish between a real root vs. a real number + epsilon*i?

jcla1 2y ago
Just because of the impossibility of an exact formula for the roots of a high-degree polynomial that does not rule out the possibility of figuring out, say, the distribution of roots of such polynomials. The question is not about any polynomial in particular (hence Abel's theorem is no barrier). edit: Think of the following example: take a polynomial a_n x^n + ... + a_0, where the coefficients a_i are i.i.d. Bernoulli random variables. Even though the degree n might be large (> 4) I can say with confidence that such a polynomial has a real root (x = 0) with probability 1/2. Similar though more sophisticated arguments are at work in the linked question.
vouaobrasil 2y ago
The estimations are not based on numerics, but rather reasoning. For example, since real-valued polynomials are stable under complex conjugation, each complex root must have a complex conjugate. For polynomials with three distinct roots then, one must be real. This is just an EXAMPLE of the kind of reasoning that can be used to infer whether a root is purely real or complex. As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher. General formulas only exist for polynomials of degree four or lower. Of course, there are SPECIFIC formulas for specific KINDS of higher-degree polyomials. But for the general quintic and higher, nothing. That's already been proved classically.
- chongli 2y ago
  [flagged]
  - vouaobrasil 2y ago
    Hi, I read the post. The numerical approach gives the data. But the proof of the result uses analysis. I was talking about the proof. Thanks.
    - lupire 2y ago
      The roots of a polynomial vary smoothly as the coefficients vary. This is intuitively obvious. This is an important part of Abel's proof of the unsolvability of the quinitic. The probability of a random number being ambiguously real or complex has measure 0 (measure < epsilon, for all epsilon > 0), so you can ignore all computationally ambiguous cases. You don't need an exact calculation of any specific polynomial's root, to get the right answer of the measurement over all polynomials.
- orlp 2y ago
  > As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher. Note that there is no general formula for quintics (and higher) in radicals. But it is a bit arbitrary to draw the line there. There is also no 'general formula' using basic arithmetic operations (addition, subtraction, multiplication, division) that gives roots for x^2 = 2. However it is quite useful to be able to talk about those roots, so we added a dedicated symbol for them (sqrt), and more generally extended the definition of exponentiation to fractional powers. If it were generally useful to talk about the roots of quintics we also would've added common notation for their roots.
  - lanstin 2y ago
    People sort of have: https://en.wikipedia.org/wiki/Bring_radical https://en.wikipedia.org/wiki/Bring_radical
yorwba 2y ago
You use Budan's theorem https://en.wikipedia.org/wiki/Budan%27s_theorem https://en.wikipedia.org/wiki/Budan%27s_theorem to certify that there's exactly one (or exactly zero) real root in the interval (r - ɛ, r + ɛ]. As long as your guess r is within ɛ of a root, this allows distinguishing between real and complex roots even if you don't have the exact value. (There are instances where Budan's theorem cannot give an answer, e.g. most obviously if there's more than one root in the interval.)
red_trumpet 2y ago
I could imagine that one uses the derivative here. If x+iy and x-iy are complex roots, and y is really small, then the derivative at x should be small as well (if y = 0, you have a double zero, so p'(x)=0). So if p'(x) is far away from zero, you have a single real zero. And I guess double zeroes don't really happen with random coefficients.
HappyPanacea 2y ago
If we have polynomial with integer coefficients, we can bound the largest and smallest root by an expression that is maximum of abs. value of coefficients to some power. There should be similar bounds for the smallest imaginary value a root can have. If your polynomial have real numbers for coefficients having a formula doesn't help - we have the same problem of being not able to tell if number is equal zero. For example in the quadratic formula, we can have discriminant equal minus epsilon. If epsilon was zero there is no imaginary root but if it isn't we have an imaginary root.
bmacho 2y ago
I think the others answered your question. In addition, I suggest you to forget this "degree-5 polynomials" thing. They are not different from degree 2 polynomials in any meaningful way, if you talk about computing their roots or reason about their roots.
6gvONxR4sf7o 2y ago
There is a formula for arbitrary degree polynomials, it’s just difficult to apply: https://en.m.wikipedia.org/wiki/Thomae%27s_formula https://en.m.wikipedia.org/wiki/Thomae%27s_formula Apparently it’s the integrals involved that make it a challenge to use? You’re probably thinking of the theorem that these can’t always be expressed with just exponents and fractions and other plain algebraic operations.
klyrs 2y ago
There's an incredibly simple result of Sturm that allows one to compute intervals bounding the real roots of polynomials. https://en.wikipedia.org/wiki/Sturm%27s_theorem https://en.wikipedia.org/wiki/Sturm%27s_theorem That said, if you're working with finite precision, then there's an interesting question somewhere here -- given a polynomial with a certain number of real roots, how precisely do you need to know the coefficients before the answer changes?

jcla1 2y ago

Just because of the impossibility of an exact formula for the roots of a high-degree polynomial that does not rule out the possibility of figuring out, say, the distribution of roots of such polynomials. The question is not about any polynomial in particular (hence Abel's theorem is no barrier). edit: Think of the following example: take a polynomial a_n x^n + ... + a_0, where the coefficients a_i are i.i.d. Bernoulli random variables. Even though the degree n might be large (> 4) I can say with confidence that such a polynomial has a real root (x = 0) with probability 1/2. Similar though more sophisticated arguments are at work in the linked question.

vouaobrasil 2y ago

The estimations are not based on numerics, but rather reasoning. For example, since real-valued polynomials are stable under complex conjugation, each complex root must have a complex conjugate. For polynomials with three distinct roots then, one must be real. This is just an EXAMPLE of the kind of reasoning that can be used to infer whether a root is purely real or complex. As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher. General formulas only exist for polynomials of degree four or lower. Of course, there are SPECIFIC formulas for specific KINDS of higher-degree polyomials. But for the general quintic and higher, nothing. That's already been proved classically.

chongli 2y ago
[flagged]
- vouaobrasil 2y ago
  Hi, I read the post. The numerical approach gives the data. But the proof of the result uses analysis. I was talking about the proof. Thanks.
  - lupire 2y ago
    The roots of a polynomial vary smoothly as the coefficients vary. This is intuitively obvious. This is an important part of Abel's proof of the unsolvability of the quinitic. The probability of a random number being ambiguously real or complex has measure 0 (measure < epsilon, for all epsilon > 0), so you can ignore all computationally ambiguous cases. You don't need an exact calculation of any specific polynomial's root, to get the right answer of the measurement over all polynomials.
orlp 2y ago
> As for formulas: no, there is no GENERAL formula for the quintic polynomial or higher. Note that there is no general formula for quintics (and higher) in radicals. But it is a bit arbitrary to draw the line there. There is also no 'general formula' using basic arithmetic operations (addition, subtraction, multiplication, division) that gives roots for x^2 = 2. However it is quite useful to be able to talk about those roots, so we added a dedicated symbol for them (sqrt), and more generally extended the definition of exponentiation to fractional powers. If it were generally useful to talk about the roots of quintics we also would've added common notation for their roots.
- lanstin 2y ago
  People sort of have: https://en.wikipedia.org/wiki/Bring_radical https://en.wikipedia.org/wiki/Bring_radical

yorwba 2y ago

You use Budan's theorem https://en.wikipedia.org/wiki/Budan%27s_theorem https://en.wikipedia.org/wiki/Budan%27s_theorem to certify that there's exactly one (or exactly zero) real root in the interval (r - ɛ, r + ɛ]. As long as your guess r is within ɛ of a root, this allows distinguishing between real and complex roots even if you don't have the exact value. (There are instances where Budan's theorem cannot give an answer, e.g. most obviously if there's more than one root in the interval.)

red_trumpet 2y ago

I could imagine that one uses the derivative here. If x+iy and x-iy are complex roots, and y is really small, then the derivative at x should be small as well (if y = 0, you have a double zero, so p'(x)=0). So if p'(x) is far away from zero, you have a single real zero. And I guess double zeroes don't really happen with random coefficients.

HappyPanacea 2y ago

If we have polynomial with integer coefficients, we can bound the largest and smallest root by an expression that is maximum of abs. value of coefficients to some power. There should be similar bounds for the smallest imaginary value a root can have. If your polynomial have real numbers for coefficients having a formula doesn't help - we have the same problem of being not able to tell if number is equal zero. For example in the quadratic formula, we can have discriminant equal minus epsilon. If epsilon was zero there is no imaginary root but if it isn't we have an imaginary root.

bmacho 2y ago

I think the others answered your question. In addition, I suggest you to forget this "degree-5 polynomials" thing. They are not different from degree 2 polynomials in any meaningful way, if you talk about computing their roots or reason about their roots.

6gvONxR4sf7o 2y ago

There is a formula for arbitrary degree polynomials, it’s just difficult to apply: https://en.m.wikipedia.org/wiki/Thomae%27s_formula https://en.m.wikipedia.org/wiki/Thomae%27s_formula Apparently it’s the integrals involved that make it a challenge to use? You’re probably thinking of the theorem that these can’t always be expressed with just exponents and fractions and other plain algebraic operations.

klyrs 2y ago

There's an incredibly simple result of Sturm that allows one to compute intervals bounding the real roots of polynomials. https://en.wikipedia.org/wiki/Sturm%27s_theorem https://en.wikipedia.org/wiki/Sturm%27s_theorem That said, if you're working with finite precision, then there's an interesting question somewhere here -- given a polynomial with a certain number of real roots, how precisely do you need to know the coefficients before the answer changes?