Polynomial outputs containing a particular Integer sequence

Question

Does there exist a polynomial $P$ of degree greater than $1$ and with integer coefficients such that for every natural number $m$ there exists a natural number $n$ such that $P(n)=2^m$?

This question seems very tricky and interesting, I guess some kind of interpolation might be of help but I could not figure out a proper solution. Comparing growth rate in this problem seems to be of no use as its an existence problem and polynomial does tend to infinity. Help. What about proving there does not exist such a monic polynomial?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

I will prove this for all real polynomials.

Lemma: If $P \in \mathbb{R}[x]$ satisfies $P(a) = b$ for infinitely many pairs of integers $(a, b)$, then $P \in \mathbb{Q}[x]$.

Proof: Enumerate these integer pairs as $(a_1, b_1), (a_2, b_2), \dots$. Suppose $\deg P = n$. Then, consider $Q \in \mathbb{Q}[x]$ with $\deg Q \leq n$ satisfying $Q(a_i) = b_i$ for $i = 1, 2, \dots, n+1$. Note that this exists by Lagrange Interpolation.

Then $R(x) := P(x) - Q(x) = 0$ at $x = a_1, a_2, \dots, a_{n+1}$, but $\deg R \leq n$. Hence $R(x) = 0$, so $P(x) = Q(x)$. Thus, $P \in \mathbb{Q}[x]$. $_\blacksquare$

Now we can apply this lemma to the question to reduce this to the case where $P \in \mathbb{Q}[x]$. This is equivalent to finding all polynomials $P \in \mathbb{Z}[x]$ such that there exist infinitely pairs of integers $(x, y)$ such that $P(x) = 2^y z$ for some fixed constant $z$.

If we let $a$ denote the leading coefficient, $n$ denote the degree of $P$, and let the sequence of satisfying $(x, y)$ be $(x_1, 1), (x_2, 2), \dots$, then observe that $P(x_k) = 2^{k}z \implies x_k = \sqrt[n]{\frac{2^{k}z}{a}}(1+o(1))$.

This implies for large enough $k$, $x_{k+1} - x_k$ is strictly increasing. However, we also have $x_{k+1} - x_k \mid P(x_{k+1}) - P(x_k)$, so $x_{k+1} - x_k$ is eventually of the form $2^m c$, for some $c \mid z$. Since this difference is strictly increasing and $z$ is a constant value, there will exist some $K$ such that $x_{k+1} - x_k \geq 2^{k-K}$ for large enough $k$. Hence, $\frac{x_k}{2^k} \geq C > 0$ for all positive integers $k$ for some real $C$.

However, if $n > 1$, then $x_k = \sqrt[n]{\frac{2^{k}z}{a}}(1+o(1)) \implies \frac{x_k}{2^k} \to 0$ as $k \to \infty$, so there exists large enough $k'$ such that $\frac{x_{k'}}{2^{k'}} < C$, contradicting the above.

Therefore, $n = 1$, contradicting the hypothesis so we're done.

For linear polynomials, if $a = \frac{p}{q}$ for integers $p, q$ with $q > 0$ and $\gcd(p, q) = 1$, $P$ is of the form $a(x+b)$ where $p \in \{\pm 1, \pm 2\}, q \in \mathbb{N}$ and $b \in \mathbb{Z}$ such that $q \mid b$.