Given are polynomial $f(x)$ with non-negative integral coefficients and positive integer $a.$ The sequence $\{a_{n}\}$ is defined by $a_{1}=a,$ $a_{n+1}=f(a_{n}).$ It is known that the set of primes dividing at least one of the terms of this sequence is finite. Prove that $f(x)=cx^{k}$ for some non-negative integral $c$ and $k.$ Proposed by F. Petrov
HIDE: For those of you who liked this problem. Check this thread out.Problem
Source: Tuymaada 2003, day 2, problem 4.
Tags: algebra, polynomial, calculus, integration, number theory proposed, number theory
05.05.2007 17:36
It is not true. Can be $f^{(n)}(a)=a$, were $f^{(1)}(x)=f(x),f^{(n+1)}(x)=f(f^{(n)}(x))$. For example $f(x)=x^{2}-3$ and a=1 we have $f^{(2)}(1)=1.$
05.05.2007 17:52
mathmanman wrote: Given are polynomial $f(x)$ with non-negative integral coefficients and positive integer $a.$ Hmmm... Pierre.
13.08.2016 20:28
Solution. We shall use the fact that eventually all terms of the sequence $a_n$ become sufficiently large unless $f(X)=X$ in which case we are done anyways. We consider the two cases separately, when $f(0) \not= 0$ and when $f(0)=0$. In the former case, now, consider an $m$ such that for all $n \ge m$, we have $a_n > c$ where $c$ is a constant we shall mention later. Suppose that the set of all primes dividing at least one term of this sequence is $\{p_1, \dots , p_k\}$ for some $k \ge 1$. We write each term $a_l$ as the product $\prod p_i^{v_{p_i}(a_l)}$. To each $l$ assign the index $j$ such that the largest power in the product for $a_l$ is $p_j^{v_{p_j}(a_l)}$. It is clear, by the pigeonhole principle, that among the terms $\{a_n, \dots, a_{n+k}\}$ some two terms have the same index assigned to them. Therefore, we have a prime $p_i$ and an exponent $e_i$ such that $p_i^{e_i} \mid a_s$ and $p_i^{e_i} \mid a_{r+s}$ for some $m<n \le s$ and $r \le k$. Now, consider the fact that $$a_{r+s}=f^{r+s}(a)=f^r(f^s(a))=f^r(a_s) \equiv f^r(0) \,(\bmod \, a_s)$$yielding that $p_i^{e_i} \mid f^r(0)$ and since $r \le k$, the latter is bounded above by some constant, namely, the largest term $M$ in the sequence $\{f^t(0)\}_{1 \le t \le k}$. However, $p_i^{e_i} \ge \min (\sqrt[k]{a_s},\sqrt[k]{a_{r+s}})$. We can safely choose $c=M^k$ and be done with this case. For the latter, we write $f(X)=X^bg(X)$ for some integer $b \ge 1$ and see that $f^{j+1}(X)=\left(f^j(X)\right)^b\cdot g(f^(X))$. Let $\mathcal{P}$ denote the set of all primes dividing at least one term of the sequence $(a_n)_{n \ge 1}$. From here on, $p \in \mathcal{P}$ shall be assumed. Notice that $$f^{j+1}(X)=f(f^j(X)) \equiv f(0)=0 \, (\bmod \, f^j(X))$$for all $j \ge 0$. Choose $N$ sufficiently large and consider the term $a_{N+1}$ such that all primes $p \in \mathcal{P}$ divide $a_{N+1}=f^N(a)$; such an $N>0$ exists for obvious reasons. Let us consider $j>N$ and see that if $p \nmid g(0)$ then $v_p(g(f^j(0)))=0$ and if $p \mid g(0)$ then $v_p(f^{j+1}(0))>v_p(f^j(0))$ and so, for $j$ adequately large, $v_p(f^j(0))>v_p(g(0))$ and hence $v_p(g(f^j(0)))=v_p(g(0))$ is bounded above. Since all prime factors if $g$ come from $\mathcal{P}$ we see that $g(f^j(0))$ is bounded above. This fails to hold as $j \rightarrow \infty$ unless $g$ is the constant polynomial. We conclude that the only such polynomials are $f(X)=cX^k$ for some integers $k,c \ge 0$ which clearly satisfy our conditions.