4
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks! This would be helpful much. $\endgroup$ – Jeongu Kim Jun 22 '18 at 7:34
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ross Millikan Jun 21 '18 at 15:11
  • $\begingroup$ Good point! That changes all. $\endgroup$ – kub0x Jun 21 '18 at 15:42
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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$ $\endgroup$ – Jeongu Kim Jun 21 '18 at 14:41
  • $\begingroup$ Sure sorry I say that badly $\endgroup$ – Federico Fallucca Jun 21 '18 at 14:45

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.