Determine all polynomials $P(x)$ with integer coefficients such that, for any positive integer $n$, the equation $P(x)=2^n$ has an integer root.
Problem
Source: Bulgarian MO 2003: P6
Tags: algebra, polynomial, limit, induction, algebra unsolved
23.05.2014 04:44
Let $x_n$ be an integer solution of $P(x)=2^n$ and let $S^+=\{n: x_n>0\}$ and $S^-=\{n: x_n<0\}$. Without loss of generality assume that cardinality of $S^+$ is infinite (otherwise consider $P(-x)$ instead of $P(x)$). Let $S^+_0=\{n \in S^+: x_n<x_{n+1}\}$ and $S^-_0=\{n \in S^-: x_n>x_{n+1}\}$ . Let $\deg P=m$ and let $a_m$ be the leading coefficient of $P$. We will prove that $m=1$. For a contradiction assume that there is $P$ such that $m\geq 2$. Note that for all $M$ we can find $N(M)$ such that $|x_n| \geq M$ for all $n\geq N(M)$. Since \[\lim_{|x| \to \infty}\dfrac{|P(x)|}{|a_mx^m|}=1\] there exists $N$ such that $\dfrac{|P(x_n)|}{|a_mx_n^m|} \in \left(\dfrac{16}{17},\dfrac{18}{17}\right)$ for all $n \geq N$. $\textbf{Claim: } |x_n| < |x_{n+1}|<\dfrac{3}{2}|x_n|$ for all $n \geq N$. $\textit{Proof: }$ If $|x_n| \geq |x_{n+1}|$ then \[2=\dfrac{|P(x_{n+1})|}{|P(x_n)|}=\dfrac{|P(x_{n+1})|}{|a_mx_{n+1}^m|}\dfrac{|a_mx_n^m|}{|P(x_n)|}\left|\dfrac{x_{n+1}}{x_n}\right|^m < \dfrac{18}{17}\cdot\dfrac{17}{16}\cdot 1 <2\] which is a contradiction. Similarly if $|x_{n+1}|\geq \dfrac{3}{2}|x_n|$ then \[2=\dfrac{|P(x_{n+1})|}{|P(x_n)|}=\dfrac{|P(x_{n+1})|}{|a_mx_{n+1}^m|}\dfrac{|a_mx_n^m|}{|P(x_n)|}\left|\dfrac{x_{n+1}}{x_n}\right|^m>\dfrac{16}{17}\cdot\dfrac{17}{18}\cdot\dfrac{9}{4}=2\] and we again get a contradiction. Now we have following two main cases: $\textbf{Case 1:}$ Suppose cardinality of $S^+_{0}$ is infinite. Then for all $N \leq n \in S^+_0$ we have $x_n < x_{n+1}<\dfrac{3}{2}x_n$ Now observe that for any $n$ \[(x_{n+1}-x_n) \Big| P(x_{n+1})-P(x_n)=2^n \Longrightarrow |x_{n+1}-x_{n}|=2^{k_n}\] So for $N \leq n \in S_0^+$ we get $x_n+2^{k_n}=x_{n+1}<\dfrac{3}{2}x_n \Longrightarrow 2^{k_n+1}<x_n$. Since $|x_{n+2}-x_{n+1}|=2^{k_{n+1}}$ we get $\textbf{Subcase 1:}$ If $x_{n+2}-x_{n+1}=-2^{k_{n+1}}$ then $x_{n+2}=x_{n+1}-2^{k_{n+1}}=x_n+2^{k_n}-2^{k_{n+1}}$. Since \[|2^{k_n}-2^{k_{n+1}}|=|x_{n+2}-x_{n}| \Big| P(x_{n+2})-P(x_n)=3\cdot 2^n\] we deduce that $k_{n+1} \in \{k_n \pm 1, k_n\pm 2\}$. Thus \[x_{n+1}>x_{n+2}=x_n+2^{k_n}-2^{k_{n+1}} \geq x_n-3\cdot 2^{k_n} > -x_n>-x_{n+1}\] Hence $|x_{n+2}| < |x_{n+1}|$ which is a contradiction. This implies that $x_m$ is increasing for $m\geq n \geq N$ with $n \in S^+_{0}$. $\textbf{Subcase 2:}$ If $x_{n+2}-x_{n+1}=2^{k_{n+1}}$ then $x_{n+2}=x_{n+1}+2^{k_{n+1}}=x_n+2^{k_n}+2^{k_{n+1}}$. Since \[2^{k_n}+2^{k_{n+1}}=x_{n+2}-x_{n} \Big| P(x_{n+2})-P(x_n)=3\cdot 2^n\] we deduce that $k_{n+1} \in \{k_n, k_n+1, k_n-1\}$. $(i)$ if $k_{n+1}=k_n$ then $x_{n+2}=x_n+2^{k_n+1}$. Use induction to prove that $x_{n+i}=x_n+2^{k_n+i-1}$. We already have this for $i=1,2$. Suppose it is true up to some $i \geq 2$. Then $x_{n+i+1}=x_{n+i}+2^{k_{n+i}}=x_n+2^{k_n+i-1}+2^{k_{n+i}}$. Since \[2^{k_n+i-2}+2^{k_{n+i}}=x_{n+i+1}-x_{n+i-1} \Big|3\cdot 2^{n+i-1}\] we get $k_{n+i} \in \{k_n+i-3, k_n+i-2, k_n+i-1\}$. If $k_{n+i}=k_n+i-3$ then $x_{n+i+1}=5\cdot 2^{k_n+i-3}+x_n$ and \[9\cdot 2^{k_n+i-4}=x_{n+i+1}-x_{n+i-3} \Big |15\cdot 2^{n+i-3}\textnormal{ if }i\geq 4\] \[5\cdot 2^{k_n+i-3}=x_{n+i+1}-x_{n+i-2} \Big |7\cdot 2^{n+i-2}\textnormal{ if }i=2\] which is a contradiction. For $i=3$ we have $x_{n+4}=x_n+5\cdot2^{k_n}$ and $x_{n+3}=x_n+2^{n+2}$. Hence $x_{n+5}=x_{n+4}+2^{k_{n+4}}=x_n+5\cdot2^{k_n}+2^{k_{n+4}}$ must satisfy \[2^{k_n}+2^{k_{n+4}}=x_{n+5}-x_{n+3} \Big |3\cdot 2^{n+3}\] \[5\cdot 2^{k_n}+2^{k_{n+4}}=x_{n+5}-x_{n} \Big |31\cdot 2^{n}\] which is impossible. Similarly if $k_{n+i}=k_n+i-2$ then $x_{n+i+1}=3\cdot 2^{k_n+i-2}+x_n$ and \[5\cdot 2^{k_n+i-3}=x_{n+i+1}-x_{n+i-2} \Big |7\cdot 2^{n+i-2}\textnormal{ if }i\geq 3\] \[3\cdot 2^{k_n+i-2}=x_{n+i+1}-x_{n+i-2} \Big |7\cdot 2^{n+i-2}\textnormal{ if }i=2\] which is a contradiction. So $k_{n+i}=k_n+i-1$ and $x_{n+i+1}=x_n+2^{k_n+i}$. Thus using above trick we get \[2^i=\dfrac{P(x_{n+i})}{P(x_n)}>\dfrac{16}{18}\left(\dfrac{x_{n+i}}{x_n}\right)^m>\dfrac{8}{9}\left(\dfrac{x_n+2^{k_n+i-1}}{x_n}\right)^2\geq\dfrac{2^{2k_n+2i+1}}{9x_n^2}\] and this cannot hold for large $i$. $(ii)$ if $k_{n+1}=k_n+1$ then $x_{n+2}=x_n+2^{k_n}+2^{k_n+1}$. Use induction to prove that $x_{n+i}=x_n+2^{k_n}+\dots +2^{k_n+i-1}$. For $i=1,2$ we already proved. Suppose it is true up to some $i \geq 2$. Then $x_{n+i+1}=x_{n+i}+2^{k_{n+i}}=x_n+2^{k_n}\dots+2^{k_n+i-1}+2^{k_{n+i}}$. Since \[2^{k_n+i-1}+2^{k_{n+i}}=x_{n+i+1}-x_{n+i-1} \Big|3\cdot 2^{n+i-1}\] we get $k_{n+i} \in \{k_n+i-2, k_n+i-1, k_n+i\}$. If $k_{n+i}=k_n+i-1$ then $x_{n+i+1}=x_n+2^{k_n}\dots+2^{k_n+i-1}+2^{k_n+i-1}$ and \[5\cdot 2^{k_n+i-2}=x_{n+i+1}-x_{n+i-2} \Big |7\cdot 2^{n+i-2}\] which is a contradiction. If $k_{n+i}=k_n+i-2$ then $x_{n+i+1}=x_n+2^{k_n}\dots+2^{k_n+i-1}+2^{k_n+i-2}$ and \[9\cdot 2^{k_n+i-3}=x_{n+i+1}-x_{n+i-3} \Big |15\cdot 2^{n+i-3}\textnormal{ if }i \geq 3\] If $i=2$ then check that $x_{n+1}=x_n+2^{k_n}, x_{n+2}=x_n+3\cdot 2^{k_n}, x_{n+3}=x_n+4\cdot 2^{k_n}$ implies $x_{n+4}=x_n+5\cdot 2^{k_n}$ and this contradicts to $x_{n+5}=x_n+5\cdot 2^{k_{n+4}}$ and this is a contradiction because \[2^{k_n}+2^{k_{n+4}}=x_{n+5}-x_{n+3} \Big|3\cdot 2^{n+3}\] and \[5\cdot 2^{k_n}+2^{k_{n+4}}=x_{n+5}-x_{n} \Big|31\cdot 2^{n}\] So $k_{n+i}=k_n+i$ and $x_{n+i+1}=x_n+2^{k_n}\dots+2^{k_n+i-1}+2^{k_n+i}$. Since $x_{n+i}=x_n+2^{k_n}(2^i-1) \geq x_n+2^{k_n+i-1}$ as above we get a contradiction. $(iii)$ if $k_{n+1}=k_n-1$ then $x_{n+2}=x_n+2^{k_n}+2^{k_n-1}$. Since $x_{n+3}=x_{n+2}+2^{k_{n+2}}=x_n+2^{k_n}+2^{k_n-1}+2^{k_{n+2}}$ we get \[3\cdot 2^{k_n-1}+2^{k_{n+2}}=x_{n+3}-x_n \mid 7\cdot 2^n\] and \[2^{k_n-1}+2^{k_{n+2}}=x_{n+3}-x_{n+1} \mid 3\cdot 2^{n+1}\] These two implies $k_{n+2}=k_n-1$ and $x_{n+3}=x_n+2^{k_n+1}$. Now, since $x_{n+4}=x_{n+3}+2^{k_{n+3}}=x_n+2^{k_n+1}+2^{k_{n+3}}$ we get \[2^{k_n}+2^{k_{n+3}}=x_{n+4}-x_{n+1} \mid 7\cdot 2^{n+1}\] and \[2^{k_n-1}+2^{k_{n+3}}=x_{n+4}-x_{n+2} \mid 3\cdot 2^{n+2}\] But there is no $k_{n+3}$ satisfying both of these. Contradiction. $\textbf{Case 2:}$ Suppose cardinality of $S^+_{0}$ is finite. By considering $P(-x)$ we also deduce that $S^-_0$ is finite. Since we also know that $|x_{n}|<|x_{n+1}|$ we deduce that $x_n$'s alternate signs for all sufficiently large $n$. Now pick $n\geq N$ sufficiently large so that $0<x_n<x_{n+2}<\dots$ and $0>x_{n+1}>x_{n+3}>\dots$ and then apply above reasoning to this subsequence. Since \[x_{n+2}-x_n \Big| 3\cdot 2^n \Longrightarrow x_{n+2} \in \{x_{n}+2^{s_n},x_n+3\cdot 2^{s_n}\}\] $\textbf{Subcase 1: }$ If $x_{n+2}=x_n+3\cdot 2^{s_n}$ then $x_{n+1}=x_{n+2}-2^{k_{n+1}}=x_n+3\cdot 2^{s_n}-2^{k_{n+1}}$. Also we have $x_{n+1}=x_n-2^{k_n}$. Hence \[2^{k_{n+1}}-3\cdot 2^{s_n}=2^{k_n}\Longrightarrow k_n=s_n=k_{n+1}-2\] Thus $x_{n+1}=x_n-2^{k_n}$ and $x_{n+2}=x_{n}+3\cdot 2^{k_n}$. Write $x_{n+3}=x_{n+1}-c\cdot 2^{\ell_{n+1}}$ where $c \in \{1,3\}$ as above. $(i)$ if $c=1$ then $x_{n+3}=x_{n+1}-2^{\ell_{n+1}}=x_n-2^{k_n}-2^{\ell_{n+1}}$. So \[x_{n+2}-x_{n+3} \Big| 2^{n+2} \Longrightarrow 2^{k_n+2}+2^{\ell_{n+1}} \Big|2^{n+2} \Longrightarrow \ell_{n+1}=k_n+2\] Then $x_{n+3}=x_n-5\cdot 2^{k_n}$ and \[5\cdot 2^{k_n}=x_{n}-x_{n+3} \Big| 7 \cdot 2^{n}\] Contradiction. $(ii)$ if $c=3$ then $x_{n+3}=x_{n+1}-3\cdot 2^{\ell_{n+1}}=x_n-2^{k_n}-3 \cdot 2^{\ell_{n+1}}$. So \[x_{n+2}-x_{n+3} \Big| 2^{n+2} \Longrightarrow 2^{k_n+2}+3\cdot 2^{\ell_{n+1}} \Big|2^{n+2} \Longrightarrow \ell_{n+1}=k_n+2\] Then $x_{n+3}=x_n-13\cdot 2^{k_n}$ and \[13\cdot 2^{k_n}=x_{n}-x_{n+3} \Big| 7 \cdot 2^{n}\] Contradiction. $\textbf{Subcase 2: }$ If $x_{n+2}=x_n+2^{s_n}$ then $x_{n+1}=x_{n+2}-2^{k_{n+1}}=x_n+2^{s_n}-2^{k_{n+1}}$. Since $x_{n+1}=x_n-2^{k_n}$ we get \[2^{k_{n+1}}-2^{s_n}=2^{k_n}\Longrightarrow k_n=s_n=k_{n+1}-1\] Thus $x_{n+1}=x_n-2^{k_n}$ and $x_{n+2}=x_{n}+2^{k_n}$. This in particular shows that $x_n-x_{n+1}=x_{n+2}-x_n \hspace{5pt}(\ast)$. Again write $x_{n+3}=x_{n+1}-c \cdot 2^{\ell_{n+1}}$ for some $c \in\{1,3\}$. $(i)$ if $c=1$ then $x_{n+3}=x_{n+1}-2^{\ell_{n+1}}=x_n-2^{k_n}-2^{\ell_{n+1}}$. So \[x_{n+2}-x_{n+3} \Big| 2^{n+2} \Longrightarrow 2^{k_n+1}+2^{\ell_{n+1}} \Big|2^{n+2} \Longrightarrow \ell_{n+1}=k_n+1\] Then $x_{n+3}=x_n-3\cdot 2^{k_n}$ and \[3\cdot 2^{k_n}=x_{n}-x_{n+3} \Big| 7 \cdot 2^{n}\] Contradiction. $(ii)$ if $c=3$ then $x_{n+3}=x_{n+1}-3\cdot 2^{\ell_{n+1}}=x_n-2^{k_n}-3 \cdot 2^{\ell_{n+1}}$. So \[x_{n+2}-x_{n+3} \Big| 2^{n+2} \Longrightarrow 2^{k_n+1}+3\cdot 2^{\ell_{n+1}} \Big|2^{n+2} \Longrightarrow \ell_{n+1}=k_n+1\] Then $x_{n+3}=x_n-7\cdot 2^{k_n}$. Now replace $n$ with $n+2$ and apply case $2$ to $n+2$. Then from $(\ast)$ we get \[8\cdot 2^{k_n}=x_{n+2}-x_{n+3}=x_{n+4}-x_{n+2}\Longrightarrow x_{n+4}=x_n+9\cdot 2^{k_n}\] Hence \[9\cdot 2^{k_n}=x_{n+4}-x_{n} \Big| 15 \cdot 2^n\] and we get contradiction. This shows that $m\leq 1$. Obviously $P$ can not be constant and check that linear polynomials satisfying problem are $\pm(x+a)$ and $\pm 2(x+a)$ for some constant $a$.
23.05.2014 18:58
Are you sure you solved it?(so long) Can Lagrange's Interpolation help?
23.05.2014 22:01
utkarshgupta wrote: Are you sure you solved it?(so long) Yes it is long but it looks like correct solution. You can check it. I hope someone will write simple and short solution.
24.01.2016 17:04
Let $m=\deg P$ and let $a$ be the coefficient of $x^m$. Let $x_n$ be an integer solution to $P(x)=2^n$. Since $\lim_{n\to\infty}|x_n|=+\infty$, $$\lim_{n\to\infty}\frac{a|x_n|^m}{2^n}=1\implies\lim_{n\to\infty}\left\vert\frac{x_{n+1}}{x_n}\right\vert=\sqrt[m]2.$$But $(x_{n+1}-x_n)\mid P(x_{n+1})-P(x_n)$, so $|x_{n+1}-x_n|=2^{k_n}$ for some $k_n\geq0$. Thus $$\left\vert\frac{x_{n+1}}{x_n}\right\vert=\frac{2^{k_n}}{|x_n|}+\epsilon_n,$$where $\epsilon_n=\pm1$. It follows that $$\sqrt[m]2=\lim_{n\to\infty}\left(\frac{2^{k_n}}{|x_n|}+\epsilon_n\right)=\lim_{n\to\infty}\left(2^{k_n}\cdot\sqrt[m]{\frac{a}{2^n}}+\epsilon_n\right).$$Note that $\epsilon_n$ equals $1$ or $-1$ for infinitely many $n$. WLOG, we consider the first case. Let $s_i$ be the set of indices for which $\epsilon_{s_i}=1$. Then $$\sqrt[m]2-1=\sqrt[m]a\lim_{i\to\infty}2^{k_{s_i}-s_i},$$so $k_{s_i}-s_i$ converges to some integer $\ell$. It follows that $\left(\sqrt[m]2-1\right)^m=a2^{m\ell}$ is an integer. But by Eisenstein's criterion, $x^m-2$ is irreducible, so $(x+1)^m-2$ is the minimal polynomial of $x=\sqrt[m]2-1$, hence $$(x+1)^m-2=x^m-a2^{m\ell}\implies m=1.$$ Let $P(x)=ax+b$. Then $a(x_2-x_1)\mid2$, so it follows that $\boxed{P(x)=a(x+b)}$, where $a\in\{\pm1,\pm2\},b\in\mathbb{Z}$. 777th post!
25.01.2016 15:06
Let $x_n$ be an integer solution of $P(x)=2^n$, $a$ and $m$ be respectively the leading coefficient and the degree of $P$. Then: \[ x_n = a^{-1/m}\cdot 2^{n/m}(1+o(1)) \,\,\,\,\,\, (*)\]($o(1)$ means that $o(1)\to 0$ as $n\to \infty$ ). Using (*), it's easy to see $x_{n+1}-x_n$ strictly increases from some place on. Since $x_{n+1}-x_n \mid P(x_{n+1})-P(x_n)$, it follows $x_{n+1}-x_n$ will be a power of two, and since it strictly increases for sufficiently large $n$, $x_{n+1}-x_n \geq 2^{n-n_0}$, for some fixed $n_0$. It yields: \[x_n \geq C\cdot 2^n \,,\, \forall n\in \mathbb{N} \,\,\,\,\,\, (**)\]for some constant $C>0$. Now, assuming $m\geq 2$ leads to a contradiction, since the rate of growth of $x_n$, according to (**), would be bigger than the growth of $x_n$ according to (*). So, $m=1$, and the result follows immediately. Comment: The official solution is pretty much the same as in the post #5, even in the notations and wording!? Anyway, all approaches presented here are rather algebraic (NT). I have posted the above solution some years ago in a Bulgarian math forum. The algebraic (or NT) arguments used are as little as possible. The only NT argument used is: $x-y \mid P(x)-P(y)$ for $x,y\in \mathbb{Z}$ and $P$ with integer coefficient.
19.12.2024 19:31
I'm just curious tho, I'm currently working on a problem like this, but instead it change $2^n$ to $6^n+3^n+2^n$, it seems like my approach to the original problem did not work in this tho, any idea :d