Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It seems as though you could construct an example using the definition of the machine epsilon. –  Arkamis Aug 21 '12 at 16:20

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.