5
$\begingroup$

It's known that it's possible to determine whether some roots of a polynomial are rational by using rational root theorem. It's also known that Sturm's theorem can easily answer the question about existence of roots of a polynomial in a certain domain.

With these two facts in mind, there is this pack of questions, breaking down the one in title:

  • Is it possible to determine whether a polynomial has natural roots (such $x$ that $x\in\mathbb{N}$)?
  • Is it possible to determine whether a polynomial has integer roots (such $x$ that $x\in\mathbb{Z}$)?
  • Is it possible to determine whether a polynomial has irrational roots (such $x$ that $x\in\mathbb{I}$)?
  • Is it possible to determine whether a polynomial has real roots (such $x$ that $x\in\mathbb{R}$)?
  • Is it always true that any polynomial has complex roots (such $x$ that $x\in\mathbb{C}$)?
  • Can the questions above be answered if it's necessary to test for such roots in a certain domain (for example, integer roots inside $x\in(0,3)$ or rational roots inside $x\in(-5,8)$, in general, test for existence of roots $x\in A$ inside $x\in(x_1,x_2)$), and if yes, which of these can be and how?

Many thanks.

$\endgroup$
3
  • $\begingroup$ About the fifth question: a non-constant complex polynomial always has at least one complex root. This is the D'Alembert-Gauss theorem. $\endgroup$
    – Stef
    Jan 24 at 12:25
  • $\begingroup$ To test for the existence of integer roots inside a small interval domain, you could just calculate the value of that polynomial at very integer in that domain and see if you get a zero. $\endgroup$
    – Stef
    Jan 24 at 12:33
  • $\begingroup$ @Stef what do we consider a small interval domain? (0,1)? (0.(0)1,0.(0)2)? $\endgroup$
    – Rusurano
    Jan 24 at 13:57

1 Answer 1

5
$\begingroup$

The steps to determine the nature of roots (not counting multiplicities) of a polynomial $\,P\,$ in interval $\,I\,$ would be the following.

  • Check for multiple roots by calculating $\,D = \gcd(P,P')\,$ using the Euclidean algorithm. If $\,\deg D \gt 0\,$ divide by the common factor $\,P_1 = P / D\,$, then $\,P_1\,$ will have the same roots as $\,P\,$ but each of them with multiplicity $\,1\,$ i.e. $\,P_1\,$ will be the square free part of $\,P\,$. This step can potentially lower the degree of $\,P\,$ which simplifies subsequent calculations.

  • Use Sturm's theorem to determine the number $\,N_{\mathbb R}\,$ of real roots in $\,I\,$.

  • By the rational root theorem there is only a finite number of potential rational roots. Calculate the value of the polynomial for each candidate fraction that falls in interval $\,I\,$ (with the numerator dividing the constant term and the denominator dividing the leading coefficient) and determine the number $\,N_{\mathbb Q}\,$ of rational roots. Those with denominator $\,1\,$ are the integer roots, say $\,N_{\mathbb Z} \le N_{\mathbb Q}\,$ of them, and those which are also positive are the natural roots $\,N_{\mathbb N}\,$.

  • The irrational roots in $\,I\,$ are those which are real but not rational, so $\,N_{\overline{\mathbb Q}}= N_{\mathbb R} - N_{\mathbb Q}\,$.

The obvious relations hold $\,N_{\mathbb N} \le N_{\mathbb Z}\le N_{\mathbb Q}\le N_{\mathbb R} = N_{\mathbb Q} + N_{\overline{\mathbb Q}} \le \deg P_1 \le \deg P\,$.

The total number of roots (counting multiplicities) of $\,P\,$ in $\,\mathbb C\,$ is $\,N^* = \deg P\,$ by the fundamental theorem of algebra. The number of real roots $\,N_{\mathbb R}^*\,$ (counting multiplicities) can be determined using Sturm's theorem with $\,I \equiv \mathbb R\,$, applied to the finite sequence of square-free polynomials $\,P_k\,$ with $\,\deg P_k \gt 0\,$ defined by $\,D_1 = \gcd(P, P')\,$, $\,P_1 = P / D_1\,$, $\,D_2=\gcd(D_1, D_1')\,$, $\,P_2 = D_1 / D_2\,$, $\,\dots\,$ and adding up the counts, then the number of non-real complex roots (counting multiplicities) is $\,N_{\mathbb C \setminus \mathbb R}^*=N^* - N_{\mathbb R}^*\,$.

$\endgroup$
3
  • $\begingroup$ Let $p(x)=\sum_{j=0}^n A_jx^j$ with $n\ge 2$ and $A_n\ne 0.$ Let $B=1+\max_{j<n}|A_j/A_n|.$ It is very easy to prove that $|x|\ge B\implies |p(x)|\ge |A_nx^n|-\sum_{j=0}^{n-1} |A_jx^j|>0 .$ $\endgroup$ Jan 24 at 20:16
  • $\begingroup$ @DanielWainfleet The Cauchy bound and others referenced in the link are indeed useful when narrowing down the ranges (real or complex) where to look for potential roots. $\endgroup$
    – dxiv
    Jan 24 at 22:05
  • 1
    $\begingroup$ I didn't know it was called the Cauchy bound. I discovered it too (LOL)... Sometimes a linear change of variable is useful before applying the Cauchy bound...A limiting case is $x_n^2-nx_n-n=0$ with $x_n>0.$ We have $x_n-(n+1)\to 0$ as $n\to\infty.$ $\endgroup$ Jan 25 at 21:18

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.