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$?

Improve this question
$\endgroup$
1
  • $\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
    Commented Feb 28, 2015 at 16:06

2 Answers 2

Reset to default
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.$)

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ What is the bound? $\endgroup$
    – Richard Stanley
    Commented Feb 27, 2015 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
    Commented Feb 28, 2015 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
    Commented Feb 28, 2015 at 4:38
  • $\begingroup$ What Noam said. $\endgroup$
    – Igor Rivin
    Commented Feb 28, 2015 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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Feb 28, 2015 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
    Commented Feb 28, 2015 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
    Commented Mar 2, 2015 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
    Commented Mar 2, 2015 at 18:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .