MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.
share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer
@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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.