# 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 '10 at 2:29
Reals coefficients. – Yuval Filmus Oct 28 '10 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 '10 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 '10 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 '10 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 '10 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 '10 at 5:09

A slight variant that turns out to be non-elemenatry is to replace the polynomial with a rational function. This leads to:

Theorem: Let $R(x)\in\mathbf{Q}(x)$ be a rational function of degree at least 2, let $\alpha\in\mathbf{Q}$ be an initial value, and suppose that the orbit $O_R(\alpha)=\{R^{(n)}(\alpha) : n\ge0\}$ contains infinitely many integers. Then the second iterate $R^{(2)}(x)$ of $R$ is a polynomial.

For specific $R$ there are often easy proofs, but in general the proof seems to require some non-trivial result on Diophantine approximation such as Thue's theorem. There's an exposition of the proof in The Arithmetic of Dynamical Systems (Springer 2007), Section 3.7. See Section 3.8 for a stronger result saying roughly that as $n$ gets large, then the numerator and denominator of $R^{(n)}(\alpha)$ have about the same number of digits. (There's one extra technical condition for this last result.)

-
Is the degree of a rational function defined to be the larger of the degrees of numerator and denominator? Is the $\alpha$ in the theorem an arbitrary complex number? Are there examples I should know of rational functions $R$ such that $R$ is not a polynomial, but its second iterate is? – Gerry Myerson Aug 13 '13 at 0:32
Hi Gerry, The degree of a rational function $F(X)/G(X)$ is indeed the larger of the degrees of the numerator and the denominator, where of course one has to ensure that $\gcd(F,G)=1$. In the statement I gave, $\alpha$ is a rational number. The theorem is true, mutatis mutandis, with $\mathbf{Q}$ replaced by a number field $K$ and "integer" replaced by "the ring of $S$-integers of $K$". I suspect it's true for $\alpha$ complex. I'll answer your last question in a second comment. – Joe Silverman Aug 13 '13 at 1:40
A reasonably elementary proposition says that if $R(x)$ is a rational function in $\mathbf{C}(x)$ of degree $d\ge2$, and if $R^{(n)}(x)$ is a polynomial for some $n\ge2$, then either $R(x)$ is a polynomial, or else there is a linear fractional transformation $L(x)=(ax+b)/(cx+d)$ such that $L^{-1}\circ R\circ L(x)=x^{-d}$. In other words, up to change of variables, the only rational function you need to worry about is $1/x^d$, whose second iterate is clearly a polynomial. There are many proofs. The one I like uses the Riemann-Hurwitz genus formula applied to $R$ as a self-map of the 2-sphere. – Joe Silverman Aug 13 '13 at 1:42