Polynomial outputs containing a particular Integer sequence

We will prove that such polynomials don't exist.

Let $$P(X)=a_nX^n+a_{n-1}X^{n-1}+\ldots+a_1X+a_0\quad(a_n\neq0,a_i\in\mathbb{Z})$$ We know that $$\lim_{x\rightarrow\infty}\frac{|P(x)|}{|x|^n}=a_n$$

By hypothesis $\forall$ $m\in\mathbb{N}$, $P(x)=2^m$ has at least one solution in $\mathbb{N}$. Hence we can find a sequence $\{x_m\}_{m=1}^{\infty}$ in $\mathbb{N}$ such that $P(x_m)=2^m$.

Claim $1$: $$\lim_{m\rightarrow\infty}\left|\frac{x_{m+1}}{x_m}\right|=2^{\frac{1}{n}}$$ and $$\lim_{m\rightarrow\infty}\frac{a_n|x_m|^n}{2^m}=1$$

Proof: Since, $$\lim_{x\rightarrow\infty}\frac{|P(x)|}{|x|^n}=a_n$$ therefore $$\lim_{x\rightarrow\infty}\frac{|x|^n}{|P(x)|}=\frac{1}{a_n}\;(a_n\neq0)$$ Moreover, since $P(x_m)=2^m$ tends to $\infty$ as $m\rightarrow\infty$, $|x_m|$ increases to $\infty$ as $m\rightarrow\infty$. Hence $$\lim_{m\rightarrow\infty}\frac{|P(x_{m+1})|}{|x_{m+1}|^n}=a_n$$ $$\implies\lim_{m\rightarrow\infty}\frac{2^{m+1}}{|x_{m+1}|^n}=a_n$$ Similarly, $$\lim_{m\rightarrow\infty}\frac{2^m}{|x_m|^n}=a_n$$ $$\implies\lim_{m\rightarrow\infty}\frac{|x_{m+1}|^n}{|x_m|^n}=2$$ $$\implies\lim_{m\rightarrow\infty}\left|\frac{x_{m+1}}{x_m}\right|=2^{\frac{1}{n}}$$ Again $$\lim_{m\rightarrow\infty}\frac{|x_m|^n}{|P(x_m)|}=\frac{1}{a_n}\implies\lim_{m\rightarrow\infty}\frac{a_n|x_m|^n}{2^m}=1$$

Now since $P(X)\in\mathbb{Z}[X]$, for any $a,b\in\mathbb{Z}$, $(a-b)\mid(P(a)-P(b))$. Therefore, $(x_{m+1}-x_m)\mid(P(x_{m+1})-P(x_m))=(2^{m+1}-2^m)=2^m$. Hence $(x_{m+1}-x_m)$ is a power of $2$. Let $\{b_m\}_{m=1}^{\infty}$ be the sequence in $\mathbb{N}$ such that $(x_{m+1}-x_m)=2^{b_m}$. Therefore $\frac{x_{m+1}}{x_m}-1=\frac{2^{b_m}}{x_m}\;\forall\; m\in\mathbb{N}$.

Since $x_m\in\mathbb{N}$, we actually have $$\lim_{m\rightarrow\infty}\frac{x_{m+1}}{x_m}=2^{\frac{1}{n}}$$ and $$\lim_{m\rightarrow\infty}\frac{2^{\frac{m}{n}}}{x_m}=a_n^{\frac{1}{n}}$$ Combining these we get $$\lim_{m\rightarrow\infty}\frac{x_{m+1}}{x_m}-1=\lim_{m\rightarrow\infty}\frac{2^{b_m}}{2^{\frac{m}{n}}}\frac{2^{\frac{m}{n}}}{x_m}=\lim_{m\rightarrow\infty}2^{\left(b_m-\frac{m}{n}\right)}\lim_{m\rightarrow\infty}\frac{2^{\frac{m}{n}}}{x_m}=a_n^{\frac{1}{n}}\lim_{m\rightarrow\infty}2^{\left(b_m-\frac{m}{n}\right)}$$ $$\implies 2^{\frac{1}{n}}-1=(a_n)^{\frac{1}{n}}\left[\lim_{m\rightarrow\infty}2^{(nb_m-m)}\right]^{\frac{1}{n}}\tag{*}$$ Now since the sequence $\{2^{(nb_m-m)}\}_{m=1}^{\infty}$ converges, $\{nb_m-m\}_{m=1}^{\infty}$ also converges and being a sequence of integers, $$\lim_{m\rightarrow\infty}(nb_m-m)=k\in\mathbb{Z}$$ Hence we get, $$(2^{\frac{1}{n}}-1)^n=a_n2^{k}$$ Now $Q(X)=(X+1)^n-2$ is an irreducible polynomial(irreducible by Eisenstein's criterion) with $(2^{\frac{1}{n}}-1)$ as a root. Hence $Q$ is the minimal polynomial of the algebraic integer $(2^{\frac{1}{n}}-1)$ of degree $n$. Again $R(X)=X^n-a_n2^{k}\in\mathbb{Z}[X]$ is another monic polynomial of degree $n$ with $(2^{\frac{1}{n}}-1)$ as a root. Due to uniqueness of minimal polynomial we have, $$Q(X)\equiv R(X)$$ It's only possible when $n=1$. Hence $P$ must be a linear polynomial. Therefore there does not exist polynomials of degree $n>1$ satisfying the hypothesis.

$\tag*{$\square$}$

We claim that for each natural $k>1$ there exists no polynomial $P$ of degree $k$ with integer coefficients such that $P(\Bbb N)$ contains all but finitely many numbers $2^m$, $m\in\Bbb N$. Indeed, suppose to the contrary that there exists such a polynomial $P(x)=\sum_{i=0}^k a_i x_i$, $a_k\ne 0$. If $a_k<0$ then $P(n)<0$ for all sufficiently large $n$, so $a_k>0$. Since $a_k(x\pm 1)^k=a_kx^k\pm ka_kx^{k-1}+\dots$, considering a polynomial $P(x-\ell)$ for some natural $\ell$, without loss of generality we can suppose that $-ka_k<a_{k-1}<ka_k$.

Put $a=a_k^{-1/k}$ and $\xi=2^{1/k}$. For any natural $m$ we have $$P(a\xi^m\pm 1)-2^m=\pm ka_k(a\xi^m)^{k-1}+a_{k-1}(a\xi^m)^{k-1}+O((a\xi^m)^{k-2}).$$ So there exists $M_1>0$ such that $P(a\xi^m-1)< 2^m< P(a\xi^m+1)$ for each natural $m>M_1$. By the assumption, there exists $M_2\ge M_1$ such that for each natural $m>M_2$ there exists $n_m$ such that $P(n_m)=2^m$. Since $P$ is a polynomial, there exists $M’$ such that $P(M’)=\max \{P(x): 0\le x\le M’\}$ and $P(x)$ is increasing for $x\ge M’$. It follows that $|a\xi^m-n_m|\le 1$ for each $m>M_2$ such that $a\xi^m>M’ +1$.

Since $n_{m+1}- n_m$ divides $P(n_{m+1})-P(n_m)=2^m$, it follows that $n_{m+1}- n_m=2^p$ for some natural $p$. Thus
$$2^p-2<a\xi^{m+1}- a\xi^{m}<2^p+2.$$ There exists $M_3\ge M_2$ such that for each natural $m>M_3$ holds $a\xi^m> M’+1$ and each interval $(2^p-2, 2^p+2)$ for $p\in\Bbb N$ contains at most one difference $a\xi^{m+1}- a\xi^{m}$ with $m>M_3$. This leads to a contradiction, because for each natural $N$ a segment $[0,2^N+2]$ contains $N$ such intervals but at least $\log_k (2^N/a)-1=kN -\log_k a-1$ such differences.

In this separate post I'm going to prove a statement which is a special case from one aspect and general from other. I have proved in my previous post that there does not exist a polynomial with integer coefficients of degree greater than $1$ such that $P(\mathbb{N})$ contains $\{2^m:m\in\mathbb{N}\}$. We move from $\mathbb{Z}[X]$ to $\mathbb{R}[X]$. Then we will be dealing with a very large class now. But we know that to achieve something we have to lose something. Possibly, we can only prove this statement for monic polynomials.

Claim: Let $P(X)\in\mathbb{R}[X]$ be monic. Let $$\{2^m:m\in\mathbb{N}\}\subset P(\mathbb{N})$$ Then we must necesaarily have $\deg(P)=1$

Proof: Let us call a monic polynomial $P(X)$ in $\mathbb{R}[X]$ good if $\{2^m:m\in\mathbb{N}\}\subset P(\mathbb{N})$. We see that $P(X)$ is good $\implies$ $Q_c(X)=P(X+c)$ is good for any integer constant $c$. Let $$P(X)=X^n+a_{n-1}X^{n-1}+\ldots+a_1X+a_0$$ Then $$Q_c(X)=P(X+c)=(X+c)^n+\sum_{j=0}^{n-1}a_j(X+c)^j=X^n+\sum_{j=0}^{n-1}b_j(c)X^j$$ Now we can choose $c$ to make $b_{n-1}(c)$ lie in the interval $[0,n-1]$. So we can $\mathrm{WLOG}$ assume that $0\leq a_{n-1}\leq (n-1)$. Consider the auxiliary polynomial $R(X)=P(X)-X^n=a_{n-1}X^{n-1}+\ldots+a_1X+a_0$. Let, if possible, $n>1$. There exists a sequence $\{x_m\}_{m=1}^{\infty}$ in $\mathbb{N}$ such that $P(x_m)=2^m$ for all $m\in\mathbb{N}$. We see that $$\lim_{k\rightarrow\infty}\left|\frac{P(x_{kn})}{x_{kn}^n}\right|=1\implies \lim_{k\rightarrow\infty}\frac{2^{kn}}{x_{kn}^n}=1\implies \lim_{k\rightarrow\infty}\frac{2^k}{x_{kn}}=1$$ It's easy to verify that we can choose sufficiently large $k\in\mathbb{N}$ such that $2^k\geq(x_{kn}+1)$. Therefore $R(x_{kn})=P(x_{kn})-x_{kn}^n=2^{kn}-x_{kn}^n\geq(x_{kn}+1)^n-x_{kn}^n\geq nx_{kn}^{n-1}$. If $a_{n-1}\geq1$, then $nx^{n-1}>R(x)$. Which is a contradiction since $x_{kn}$ grows arbitrarily as $k\rightarrow\infty$. Again if $R(X)\not\equiv0$ and $a_{n-1}=0$, then we have $x^{n-1}>|R(x)|>0$ for negative leading coefficient of $R(X)$. But we can choose sufficiently large $k\in\mathbb{N}$ such that $(x_{kn}-1)\geq2^k$. Hence, $|R(x_{kn})|=|P(x_{kn})-x_{kn}^n|=x_{kn}^n-2^{kn}\geq x_{kn}^n-(x_{kn}-1)^n\geq x_{kn}^{n-1}$. Again a contradiction since $x_{kn}$ grows arbitrarily as $k\rightarrow\infty$! If $R(X)$ has positive leading coefficient then we can reach a contradiction similarly as we did in the case when $a_{n-1}\geq1$. Finally $P(X)\equiv X^n$ clearly not possible for $n>1$. Hence we conclude that $n$ must necessarily be $1$.

$\tag*{$\square$}$

This is Problem 6 from Bulgarian MO 2003. Here is the official solution as found cited in https://artofproblemsolving.com/community/c6h590651p3498282 with few error corrections:

Denote by $m$ and $a$ the degree and the leading coefficient of $P(x)$, respectively. Let $x_n$ be an integer solution of the equation $P(x)=2^n$. Since $\lim_{n\to \infty}|x_n|=+\infty$, then $\lim_{n \to \infty} \frac{a|x_n|^m}{2^n}=1$ and hence $\lim_{n \to \infty}|\frac{x_{n+1}}{x_n}|=\sqrt[m]{2}.$

On the other hand, $x_{n+1}-x_n$ divide $P(x_{n+1})-P(x_n)$ and thus $|x_{n+1}-x_n|=2^{k_n}$ for some $k_n \geq 0$. Then $$ \left|\frac{x_{n+1}}{x_{n}}\right|=\frac{2^{k_n}}{|x_n|}+\varepsilon_n, $$ where $\varepsilon_n=\pm 1$ and we get that $$ \sqrt[m]{2}=\lim_{n \to \infty}\left(\frac{2^{k_n}}{|x_n|}+\varepsilon_n\right)=\lim_{n \to \infty}\left(2^{k_n}\sqrt[m]{\frac{a}{2^n}}+\varepsilon_n\right). $$ Note that $\varepsilon_n$ equals either $1$ or $-1$ for infinitely many $n$. Since the two cases are similar, we shall consider only the second one. Let $1=\varepsilon_{i_1}=\varepsilon_{i_2}=\dots$. Then $$ \sqrt[m]{2}-1=\sqrt[m]{a\lim_{j \to \infty}2^{mk_{i_j}-i_j}} $$ and hence the sequence of integers $mk_{i_j}-i_j$ converges to some integer $l$. It follows that $(\sqrt[m]{2}-1)^m=a2^{l}$ is a rational number. According to the Eisenstein criterion, the polynomial $x^m-2$ is irreducible. Hence $(x+1)^m-2$ is the minimal polynomial of $\sqrt[m]{2}-1$. It follows that $(x+1)^m-2=x^m-a2^{l}$ which is possible only for $m=1$.

Let $P(x)=ax+b$. Then $a(x_2-x_1)$ divides $2$ and thus $a=\pm 1, \pm 2$. Now it follows easily that all polynomials with the desired property are of the form $P(x)=a(x+b)$, where $a=\pm 1, \pm 2$ and $b$ is an arbitrary integer.

A partial answer, for quadratic polynomials. Except for squares, a quadratic polynomial $P \in \mathbb{Z}[x]$ cannot take all values of the form $4^m$. If $$P(x) = a x^2 + b x + c$$ with $a >0$ is quadratic but not a square then the discriminant of $P(x)-4^m$ is $$b^2 - 4a c + a 4^{m+1}$$ and $d = b^2-4 a c \neq 0$. However, if $$d + a 4^{m+1} = A^2$$ is a square, then $$(2A)^2 = 3d + d + a 4^{m+2}$$ and so $d + a 4 ^{m+2}$ is not a square if it exceeds $\tfrac94d^2$. Therefore, $P(x)=4^m$ does not have an integral solution for all $m\geq 0$.