7
$\begingroup$

Suppose I have a polynomial $p(x) = a_n x^n + ... + a_0$ where $a_n, \dots, a_0$ are integers. I would like to show that any root of this polynomial is either an integer or is far from an integer. That is, if $r$ denotes the fractional part of a root $x$, I want to show that either $r = 0$ or $r > w$ for some real valued $w$.

If the polynomial $p$ has degree one this is easy --- I know either $w = 0$ or $w \geq \frac{1}{|a_1|}$.

Is there a similar bound that can be shown for arbitrary polynomials, where the minimum non-zero value of $w$ can be bounded in terms of the sizes of $a_0, \dots, a_n$?

$\endgroup$
  • $\begingroup$ There are a couple of cases. The polynomial might have a root at the nearby integer $k$ or not. If so, perhaps root separation bounds are good enough. If not, then the polynomial has a value at least $1$ away from $0$ there, and we can bound $k$ and then $p'(x)$, so the polynomial can't reach $0$ too rapidly. $\endgroup$ – Douglas Zare Feb 28 '15 at 16:06
1
$\begingroup$

A bound follows from the general root separation theory. See Schonhage's 2006 paper (Journal of Symbolic Computation)> (see inequality (3) and the discussion following, about replacing the discriminant by $1.$)

$\endgroup$
  • 2
    $\begingroup$ What is the bound? $\endgroup$ – Richard Stanley Feb 27 '15 at 21:57
  • $\begingroup$ There is an inequality (3), but I do not quite understand how this result answers the question, since the paper gives lower bounds on the distance between roots, but David Harris is not assuming that his polynomial has an integer root. $\endgroup$ – Timothy Chow Feb 28 '15 at 3:56
  • 2
    $\begingroup$ Well you can always apply the bound to $(x-r) \, p(x)$ where $r$ is an integer approximation to a root, but still that's surely not the best way to solve the problem... $\endgroup$ – Noam D. Elkies Feb 28 '15 at 4:38
  • $\begingroup$ What Noam said. $\endgroup$ – Igor Rivin Feb 28 '15 at 16:53
10
$\begingroup$

This is a standard question in diophantine approximation. See for example Chapter 3 of Waldschmidt's book Diophantine Approximation of Linear Algebraic Groups. Here is the simplest bound that Waldschmidt gives. Assuming $a_0\ne 0$, let $H := \max_{0\le i\le n} |a_i|$. We will show that if $\alpha$ is any nonzero root of your polynomial, then $|\alpha| > 1/(H+1)$.

If $|\alpha| \ge 1$ then the inequality trivially holds. Otherwise, if $|\alpha|<1$, then

$${1\over |\alpha|} \le \left|{a_0\over \alpha}\right| = \left| a_1 + a_2\alpha + \cdots + a_n \alpha^{n-1} \right| \le H(1+|\alpha| + \cdots+|\alpha|^{n-1}) < {H\over 1-|\alpha|},$$ which rearranges to $|\alpha| > 1/(H+1)$.


Edit: See David Lampert's comment below for how to use the above bound to answer the question that David Harris asked.

$\endgroup$
  • $\begingroup$ Maybe this is very naive, but if $|\alpha| \ge 1$ (the trivial case, in your answer), then $|\alpha|$ can still be very close to an integer, right? (I understand that one can move $\alpha$ inside the interval $[0,1)$, by "translating" the polynomial, but I guess that doesn't preserve $H$.) $\endgroup$ – jmc Feb 28 '15 at 9:58
  • 2
    $\begingroup$ Edited: Apply Waldschmidt's bound to $1/\alpha$ (assuming $a_{0}a_{n} \ne 0$) and get $|\alpha|<(H+1)$, write an upper bound (in terms of $H,n$): $H_0 \ge max |coefficients|$ for the coefficients of all polynomials $p(x+k):|k|≤(H+1),k∈Z$, and then $w>1/(H_0+1)$ (again by Waldschmidt's bound). $\endgroup$ – David Lampert Feb 28 '15 at 23:46
  • $\begingroup$ This answer seems to give a lower bound of a root from $0$, not from an arbitrary integer. It seems to me that you can't get a general bound which is independent of $n,$ and only depends on the $|a_{i}|$. For example, $x^{n} - 3$ has a root $\alpha$ which is only slightly larger than $1 + \frac{\log 3}{n}.$ $\endgroup$ – Geoff Robinson Mar 2 '15 at 11:35
  • $\begingroup$ jmc and Geoff Robinson are correct; sorry for not finishing off the argument. David Lampert correctly explains how to use Waldschmidt's bound to answer the question that David Harris asked. In Diophantine approximation, bounding away from zero is usually the critical part of the argument and I forgot that David asked a slightly different question. $\endgroup$ – Timothy Chow Mar 2 '15 at 18:37

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.