# How to check for roots of a polynomial from a certain number set in certain range?

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.

• About the fifth question: a non-constant complex polynomial always has at least one complex root. This is the D'Alembert-Gauss theorem.
– Stef
Jan 24 at 12:25
• 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.
– Stef
Jan 24 at 12:33
• @Stef what do we consider a small interval domain? (0,1)? (0.(0)1,0.(0)2)? Jan 24 at 13:57

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}^*\,$$.

• 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 .$ Jan 24 at 20:16
• @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.
– dxiv
Jan 24 at 22:05
• 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.$ Jan 25 at 21:18