Let $P(x)\in \mathbb{R}[x]$ satisfy the condition $P(x)=2^n$ has at least one rational root for each $n\in \mathbb{N}$.

Does it follow $P$ is linear?


I can prove this under the assumption that there exist infinitely many Mersenne primes!

If a polynomial of degree $n$ takes on $n+1$ different rational values for rational values of $x$, then by Lagrange interpolation it must in fact have rational coefficients. So we have $P(x) \in \mathbb{Q}[x]$.

By hypothesis there are rational numbers $r_n$ such that $P(r_n) = 2^n$. After replacing $P(x)$ with the polynomial $Q(x) = P(x + r_1) - 2$ and $sr_n$ with the sequence $s_n = r_n - r_1$, we have a rational polynomial $Q(x)$ and rational numbers $s_n$ with $s_1 = 0$ such that

$$Q(s_n) = 2^n - 2.$$

In particular, $Q(0) = 0$, so $Q(x)$ has constant term $0$. Let $m \in \mathbb{N}$ be the greatest common denominator among the coefficients of $Q(x)$, so that $R(x) = m Q(x)$ has integer coefficients with $\gcd = 1$. Then we have an integer polynomial $R(x) \in \mathbb{Z}[x]$ and rational numbers $s_n$ with $s_1 = 0$ such that

$$R(s_n) = (2^n - 2) m.$$

Write $R(x) = a_d x^d + \dots + a_1 x$. Then by the rational root theorem, $s_n$ must have numerator dividing $(2^n - 2) m$ and denominator dividing $a_d$.

Now assume that there are infinitely many Mersenne primes $M_p = 2^p - 1$. If we set $n = p + 1$ for $p$ the index of a Mersenne prime it follows that $s_{p+1}$ must have numerator dividing $2m M_p$. By picking $p$ large enough that $M_p > \sum |a_i| (2m)^i$ we can rule out the possibility that the numerator of $s_{p+1}$ divides $2m$, so it must be divisible by $M_p$. Since the denominator of $s_{p+1}$ divides $a_d$, it follows that $|s_{p+1}| \ge \frac{M_p}{|a_d|}$.

But this is incompatible with the growth rate of $R(x)$ unless $d = 1$. More precisely, if $r$ is sufficiently large then $R(r)$ grows at least as fast as $c_1 r^d$ for some constant $c_1$, meaning $R(s_{p+1}) \ge c_2 M_p^d$ for some constant $c_2 = \frac{c_1}{|a_d|^d}$, and taking $p$ sufficiently large this contradicts $R(s_{p+1}) = 2m M_p$ unless $d = 1$.

A slightly more careful version of this argument would be able to lower bound the complexity of a counterexample as a function of the size of the largest known Mersenne prime. According to Wikipedia, as of the time of writing the largest known Mersenne prime is

$$M_{82589933} = 2^{82589933} - 1$$

which is truly enormous.


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.