# Polynomial outputs containing a particular Integer sequence

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?

• How about $P(n)=n$? May 21 '20 at 14:17
• Maybe you meant to require that $P$ have degree $>1$?
– lulu
May 21 '20 at 14:19
• ya sorry, forgot to add it May 21 '20 at 14:22
• Note that if we only wanted the values $2^n$ with even $n$, we could take $P(x) = x^2$. May 21 '20 at 15:33
• Do you start at $m=0$ or $m=1$ ? May 23 '20 at 12:24

## 6 Answers

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

• I can prove this for monic polynomials with real coefficients. I will post it soon. There are some internet issues. Apologies. May 24 '20 at 17:04
• There’s a sign change directly after the introduction of $b_m$. It should be $$\frac{x_{m+1}}{x_m} - 1 = \frac{2^{b_m}}{x_m}.$$
– WimC
May 24 '20 at 18:18
• @WimC Thanks. I've edited my post. May 24 '20 at 18:56
• I think there is a small mistake here. In the line I have marked $(*)$, you seem to be saying$$2^{b_m-\frac mn}=2^{\frac1n}2^{nb_m-m}$$which is not correct. However I believe if this is fixed the solution still works (and actually is a little simpler). Please let me know if I misinterpreted what you meant. Apr 21 at 2:23
• Looks good to me now! Apr 22 at 1:38

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.

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

• I wouldn't normally edit for personal clarity, but having all those alphas next to a's was making my eyes hurt a little bit... May 24 '20 at 16:48

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

• Why $P(X)$ is good $\implies$ $Q_c(X)=P(X+c)$ is good for any integer constant $c$? We have $Q_c(\Bbb N)=P(\Bbb N+c)$, and the latter set a priori can be a proper subset of $P(\Bbb N)$, missing some $2^k$'s. May 25 '20 at 12:12
• If $P(x_m)=2^m$ then $Q_c(x_m-c)=P(x_m-c+c)=2^m$. You can see that in order to make the coefficient $a_{n-1}$ lie in $[0,n-1]$, we can work with negative integers $c$ so $x_m-c$ is still natural. May 25 '20 at 12:32

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.

• Now looking at it, I am not sure how they got $2^{k_{i_j}-i_j}$ instead of $2^{k_i-\frac{i_j}{m}}$, since there is $\sqrt[m]{\frac{1}{2^n}}$ originally... So fixed those as well hopefully, wouldn't expect the official solution to have that many errors.
– Sil
May 25 '20 at 9:52
• It seems there should be "$\sqrt[m]{a}\lim_{j \to \infty}2^{k_{i_j}-i_j/m}$" instead of "$\sqrt[m]{2a}\lim_{j \to \infty}2^{mk_{i_j}-i_j}$". May 25 '20 at 12:06
• @AlexRavsky I think the intent was to have convergent sequence of integers, so that would not work. I have changed it though to be consistent. Please feel free to fix any more issues you find in the official solution.
– Sil
May 25 '20 at 12:14

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

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