6
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ Where are you assuming this polynomial lives to begin with? Real coefficients? Rational? $\endgroup$ Oct 28, 2010 at 2:29
  • $\begingroup$ Reals coefficients. $\endgroup$ Oct 28, 2010 at 2:58
  • $\begingroup$ 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. $\endgroup$
    – Nick S
    Oct 28, 2010 at 3:39

2 Answers 2

7
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 28, 2010 at 3:08
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 28, 2010 at 3:14
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2010 at 5:06
  • 2
    $\begingroup$ @David, since the problem is about iterates at 0, your counterexample does not apply. Easily fixed; take $P(x)=(x^2+4)/2$. $\endgroup$ Oct 28, 2010 at 5:09
5
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Aug 13, 2013 at 0:32
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 13, 2013 at 1:40
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 13, 2013 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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