# Smallest positive root of polynomial with bounded coefficients

Given is a positive integer $n$. A polynomial has all coefficients being integers whose absolute value does not exceed $n$. What is the smallest possible positive root, if there is any?

If the root is rational, then by the rational root theorem, it cannot be smaller than $1/n$. The polynomial $nx-1=0$ has $x=1/n$ as the only solution. But if a root is irrational, can it be smaller than $1/n$?

• For $n=2$ the polynomial $(x+1)^2 -2$ has the root $\sqrt{2} - 1 \lt \frac{1}{2}$. – dxiv Oct 16 '16 at 5:20

Let the polynomial be $f(x)=a_kx^k+a_{k+1}x^{k+1}+\dots+ a_mx^m$, where $a_k\neq 0$. Note that if $0<x<1$, then $|a_k x^k|\geq x^k$ and $|a_{k+1}x^{k+1}+\dots+a_mx^m|< n\sum_{j=k+1}^\infty x^j=\frac{nx^{k+1}}{1-x}.$ This gives a lower bound on any root $x$ such that $0<x<1$: we must have $x^k< \frac{nx^{k+1}}{1-x}$, which is equivalent to $$x>\frac{1}{n+1}.$$
(Note that this bound does not really require the coefficients of $f(x)$ to be integers. It just requires them to all have absolute value $\leq n$, and that the first nonzero coefficient has absolute value $\geq 1$.)
Conversely, we can find such polynomials $f(x)$ with positive roots arbitrarily close to $\frac{1}{n+1}$. Namely, consider $$f_m(x)=1-\sum_{j=1}^m nx^j.$$ Note that $f_m\left(\frac{1}{n+1}\right)$ converges to $0$ from above as $m\to\infty$. Moreover, for any $\epsilon>0$, $f_m\left(\frac{1}{n+1}+\epsilon\right)<0$ for all sufficiently large $m$ (since you can choose $m$ such that $f_m\left(\frac{1}{n+1}\right)<\epsilon$, and $f_m\left(\frac{1}{n+1}\right)-f_m\left(\frac{1}{n+1}+\epsilon\right)\geq n\epsilon$ by looking at the linear term alone). By the intermediate value theorem, $f_m$ must then have a root between $\frac{1}{n+1}$ and $\frac{1}{n+1}+\epsilon$.