## When are infinitely many points in the orbit of a polynomial integers?

This question is inspired by a riddle in math.stackexchange.

Let $P$ be a polynomial, and $O = \{P^{(n)}(0) : n \geq 0\}$ be its orbit under zero (viewed as a set). Suppose that $O$ contains infinitely many integers. Is it true that for some $n$, $P^{(n)}$ is a polynomial with integral coefficients?

We can ask the same question replacing integers with rationals.

EDIT: Nick and David gave simple counterexamples for the first question. Still open:

1. In the setting of the original question, is it true that some composition power of $P$ takes integers to integers?
2. The original question with rationals.
-
 Where are you assuming this polynomial lives to begin with? Real coefficients? Rational? – Jeremy West Oct 28 2010 at 2:29 Reals coefficients. – Yuval Filmus Oct 28 2010 at 2:58 The open question 1 should be: If the orbit under zero contains infinitely many (different) integers, is it true that some power of $P$ takes integers into integers? The example I posted takes integers into integers, so it is still a counterexample. – Nick S Oct 28 2010 at 3:39

$P(x)= \frac{x(x+1)}{2} +1$.

It is easy to see that $P^{n+1}(0) > P^n(0)$ and $P$ maps the integers into the integers.

But I think (didn't check it, might be one of these facts which are obvious but wrong) that

$$P^{(n)}(x) = \frac{1}{2^{m}} x^{2^n}+....\notin \mathbb{Z}$$

where $m$ is probably $m=2^n+1$.

The right question to ask might be if $f$ maps the integers into the integers....

Disregard the following part, as it was pointed in the comments, it only works if for each $k$ we can find an $l$ and $n_1,..., n_k$ so that $f^{(n_i)}(0)$ and $f^{(n_i+l)}(0)$ are integers(or rational for the second question).

EDIT: P.S. The answer with the rationals turns out to be true, I think (my algebra is rusty):

Let $P$ be such a polynomial, and let $m$ be the degree of $P$. Then using the Lagrange interpolation formula, you can reconstruct $P(x)$ from $m+1$ distinct integer values of the type $P^{(k)}(0)$, and since all of these are rational, all the coefficients are rational. Actually this way one can prove the following Lemma:

-
@Nick For the question about rationals, you can try $P(x) = \sqrt{2}x + \sqrt{2}-1$. Then $P(P(x)) = 2x+1$, and so the orbit will contain $2^n-1$ for all $n$. Your method works only if there is an $n$ such that infinitely many times $P^{(t+n)}(0),P^{(t)}(0)$ are both rationals. Conceivably, this can fail to happen. – Yuval Filmus Oct 28 2010 at 3:08
For a different kind of counterexample, consider $P(x) = (x^2-1)/2+1$. Starting with any odd integer $>1$ gives an infinite orbit of odd integers, but $P$ does not take integers to integers. – David Speyer Oct 28 2010 at 3:14
I don't see how Lagrange applies to this problem. Suppose $P^{(n)}(0)$ is an integer if and only if $n$ is a power of 2. Then there's no guarantee that there are $m+1$ integer, or even rational, values of $x$ such that $P(x)$ is an integer. To get rational coefficients, you need both argument and value to be rational. – Gerry Myerson Oct 28 2010 at 5:06
@David, since the problem is about iterates at 0, your counterexample does not apply. Easily fixed; take $P(x)=(x^2+4)/2$. – Gerry Myerson Oct 28 2010 at 5:09