2
$\begingroup$

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

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

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

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