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

2 Answers 2

Reset to default
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:

Improve this answer
$\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$
    – Yuval Filmus
    Commented 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$
    – David E Speyer
    Commented 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$
    – Gerry Myerson
    Commented 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$
    – Gerry Myerson
    Commented 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.)

Improve this answer
$\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$
    – Gerry Myerson
    Commented 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$
    – Joe Silverman
    Commented 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$
    – Joe Silverman
    Commented Aug 13, 2013 at 1:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .