If $P(x)-2^n$ has a rational root for each $n\in\mathbb{N}$, is $P$ linear?

Question

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?

Answer 1

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.