Determining that the given integer is greater than all roots of given polynomial

Given the integer $k$ and the polynomial $p(x)$ with all real roots and integer coefficients, how can I determine that $k$ is greater than all roots of $p(x)$, without calculating the exact values of its roots? For example, $k=6$ is greater than all roots of polynomial $p(x)=x^2-2x-8$, whose roots are -2 and 4. (This is a part of some algorithm problem.)

Edit I missed one condition: $p(x)$ has exactly $n$ distinct real roots where $n$ is the degree of $p(x)$.

• Might be able to use Gershgorin's Circle Theorem on the associated matrix whose characteristic polynomial is equal to $p(x)$. – Adrian Keister Jun 21 '18 at 14:27

For the given example, let $\,x = t+6\,$ then $\,q(t)=p(x-6)=t^3 + 18 t^2 + 106 t + 196\,$. It follows by Descartes' rule of signs that $\,q(t)\,$ has no positive roots, therefore $\,p(x)\,$ has no root larger than $6$.

In general, the location of the real roots can be algorithmically determined using Sturm sequences.

• Thanks! This would be helpful much. – Jeongu Kim Jun 22 '18 at 7:34

Depending on the precision you need, there is the inequality $$R \leq 2 \max\{|a_{n-1}|,\sqrt{|a_{n-2}|}, \sqrt[3]{|a_{n-3}|}, \dots, \sqrt[n]{|a_0|}\}$$

Where $R$ is the largest root of $f(x) = x^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \dots + a_0$

So, for your example, we can say that the largest root of $x^2 - 2x -8$ is at most $2 \max\{2,\sqrt{8}\} = 5.65$.

Note that this leaves a gap, but there are techniques to improve the bound given to get the nearest integer to the root.

The sum of the roots of a polynomial is given by the Vieta Formula:

$S = -\frac{a_{n-1}}{a_n}$

For $p(x) = x^2 - 2x - 8 \rightarrow S = 2 = -2 + 4$

Then you have a method to check if $k > S$

• But some roots could be large and positive and others large and negative giving a small sum. For example, $(x-10)(x+10)=x^2-100$ and the sum of the roots is $0$. – Ross Millikan Jun 21 '18 at 15:11
• Good point! That changes all. – kub0x Jun 21 '18 at 15:42

First of all if $p(x)$ has exactly $n$ real roots ,where $n$ is its degree, than, if $k$ verify your condition , you have that

$p(k)>0$

So if your $k$ in that particular class of polinomial is that $p(k)\leq0$ than $k$ can not soddisfy your condition

In general you can use the Vieta’s Formula

• $p(k) > 0$ does not guarantee that $k$ is greater than all roots of $p(x)$. e.g. $k=-3$ and $p(x)=x^2-2x-8$ – Jeongu Kim Jun 21 '18 at 14:41
• Sure sorry I say that badly – Federico Fallucca Jun 21 '18 at 14:45