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

Question

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)$.

Answer 1

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.

Answer 2

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

Answer 3

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$

Answer 4

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.