Wednesday, 24 August 2016

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 nx1=0 has x=1/n as the only solution. But if a root is irrational, can it be smaller than 1/n?


Answer



Let the polynomial be f(x)=akxk+ak+1xk+1++amxm, where ak0. Note that if $0\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 n, and that the first nonzero coefficient has absolute value 1.)



Conversely, we can find such polynomials f(x) with positive roots arbitrarily close to 1n+1. Namely, consider fm(x)=1mj=1nxj.

Note that fm(1n+1) converges to 0 from above as m. Moreover, for any ϵ>0, fm(1n+1+ϵ)<0 for all sufficiently large m (since you can choose m such that fm(1n+1)<ϵ, and fm(1n+1)fm(1n+1+ϵ)nϵ by looking at the linear term alone). By the intermediate value theorem, fm must then have a root between 1n+1 and 1n+1+ϵ.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...