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?

$\endgroup$
  • $\begingroup$ It seems as though you could construct an example using the definition of the machine epsilon. $\endgroup$ – Emily Aug 21 '12 at 16:20
8
$\begingroup$

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

$\endgroup$

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.