8
$\begingroup$

In this question we were asked for roots of $9x^3 - 18x^2 - 4x + 8 = 0$ and I remarked on the rational root theorem. In fact, the roots are $2, \frac 23, \frac {-2}3$. When checking them it would be nice to use an exact form of the fractions, but in fact many will use a calculator. When checking $\frac 23$, mine makes an error of about $10^{-11}$.

It is not hard to estimate the error if the value is really a root, using the machine epsilon times the size of the terms in the polynomial, so one will not reject a true root, but what about the other direction?

For a polynomial $f(x)$ with integer coefficients of reasonable size, how small can $f(x_0)$ be where $x_0$ is a root candidate from the rational root theorem but not a root? If the real roots are rational we are limited by the fact that the rationals can't be too close together. One of my first efforts was $(x-2+i)(x-2-i)(3x-8)=3x^3-20x^2+47x-40$, which has $f(2)=-2$, pretty small compared to the terms but not small enough to fool anybody. Can we do better?

  • 0
    It seems as though you could construct an example using the definition of the machine epsilon.2012-08-21

1 Answers 1

8

I propose $f(x) = A x^n -A x +1$. Then $f(1/A)=1/A^{n-1}$.

This is basically best possible, although one could make the trap less obvious. If $f(x) = Ax^n + \cdots$, then $f(p/A)$ will always be a rational with denominator $A^{n-1}$, so we can't get smaller than $1/A^{n-1}$.