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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 21:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .