1
$\begingroup$

This is a generalization of Integrality of iterates of rational functions.

The question is: given an infinite sequence of rational numbers $a_0, a_1, \dotsc, a_n, \dotsc,$ is it always an orbit of $a_0$ under an iteration of a rational function? If the answer is in the affirmative, it will answer the original question. I am guessing it is undecidable, however.

EDIT Noam points out that the answer is not in general affirmative, but how does one decide (maybe if the growth is not too fast the answer is always yes?)

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ "maybe if the growth is not too fast the answer is always yes?" $-$ certainly not, because there are already uncountably many sequences with slow growth. Indeed if $a_{n+1}-a_n \in \{1,2\}$ for each $n$, but each of $1$ and $2$ occurs at least once, then there is no rational function taking $a_n$ to $a_{n+1}$ for each $n$. $\endgroup$
    – Noam D. Elkies
    Commented Sep 3, 2017 at 18:48

2 Answers 2

Reset to default
13
$\begingroup$

This cannot be true in general, simply because there are countably many rational functions with coefficients in $\bf Q$, and uncountably many sequences.

To construct an explicit counterexample, just have the $a_n$ grow fast enough, say $a_n = 2^{n!}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ True, but of course, the real question is whether you can tell. $\endgroup$
    – Igor Rivin
    Commented Sep 3, 2017 at 16:44
  • 2
    $\begingroup$ Not sure what the "real question" means as it stands: how can I be "given" an infinite sequence of rationals? $\endgroup$
    – Noam D. Elkies
    Commented Sep 3, 2017 at 16:49
  • 2
    $\begingroup$ @NoamD.Elkies: In the computability theory context (perhaps) hinted at by the OP, the sequence could be given by the label of a Turing machine that on input $n$ prints the $n$th member of the sequence. The 'real question' could then be if there is another TM that takes this label as its input and outputs the correct answer to the original question. (Of course, now you can't be given an arbitrary sequence, only computable ones.) $\endgroup$
    – Christian Remling
    Commented Sep 3, 2017 at 17:10
  • 5
    $\begingroup$ That interpretation seems to have a negative answer for reasons unrelated to what the OP has in mind. Given a computable function $f$ from ${\bf Z}_{\geq 0}$ to ${\bf Z}_{\geq 0}$, define another such function $a_f$ as follows: $a_f(n)=n$ if $f(m)\neq 0$ for all $m<n$, but $a_f(n) = n+1$ if $f(m)=0$ for some $m<n$. Then there exists a rational function taking each $a_f(n)$ to $a_f(n+1)$ iff $f(m) \neq 0$ for all $m$; and there's no algorithm that can decide that for every choice of $f$. $\endgroup$
    – Noam D. Elkies
    Commented Sep 3, 2017 at 17:36
  • 2
    $\begingroup$ If not then it only takes finitely many rational values, so no infinite orbit is possible. $\endgroup$
    – Noam D. Elkies
    Commented Sep 4, 2017 at 17:38
2
$\begingroup$

There are many simpler sequences which are not orbits, for example, it is impossible to have $a_n=a_{n+1}\neq a_{n+k}$ for some $k>1$.

This can be generalized to $a_n=a_{n+m}\neq a_{n+km},\; k>1$. In fact such sequences are not orbits of ANY function.

Other conditions can be obtained if $a_n$ has a limit, and tends to it with aproximately geometric speed. Then this limit must be an attracting point, and using the local linearization at this point one obtains VERY strong conditions on the sequence, and not only on its growth rate.

EDIT. For example, the following question was studied by Fatou. Instead of a rational function he considers an arbitrary analytic germ $f(z)=\lambda z+\ldots,\; |\lambda|<1$. He takes an orbit $a_n\to 0$, and makes a generating function $$g(\zeta)=\sum_{n=0}^\infty a_n\zeta^n.$$ He proves that $g$ is meromorphic in the whole plane with poles at the geometric progression $\lambda^{-k},\; k\geq 0$.

Fatou, P. Sur une classe remarquable de séries de Taylor. Ann. de l’Éc. Norm. (3) 27, 43-53 (1910).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I thought Igor Rivin intended (even if he didn't explicitly state this) that the $a_n$ be distinct. The limit-point construction is basically what I did, with rapid convergence to $\infty$ (which looks like any other point of the projective line in the context of rational functions). $\endgroup$
    – Noam D. Elkies
    Commented Sep 4, 2017 at 17:37
  • $\begingroup$ That's really cool! Presumably this is related to Silverman's theorem, as in @NoamD.Elkies' answer to the other question. $\endgroup$
    – Igor Rivin
    Commented Sep 4, 2017 at 17:40
  • 1
    $\begingroup$ @Igor Rivin: I think Fatou's theorem is simpler: it is a local result, near a fixed point, where the dynamics is very smle, while Silverman's theorem is global. $\endgroup$
    – Alexandre Eremenko
    Commented Sep 4, 2017 at 17:46

You must log in to answer this question.

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