# Detecting preperiodic points

In short, I need to prove whether I have preperiodic orbits or wandering orbits for some dynamical systems.

Not as short: Let $\phi$ be a rational map. Suppose we want to know if 0 is preperiodic under $\phi$. Of course if it were, were could iterate endlessly until finding some $i,j$ with $i\neq j$ and $\phi^i(0) = \phi^j(0)$, however if 0 is not preperiodic, we must find some way to detect this. There are height bounds, but they're very large (and I don't know if anyone's actually computed them yet, beyond just proving their existence..) so it would be nice to avoid that.

One method my supervisor and I have talked about, is reducing modulo some good prime $p$. Specifically, let $p$ be a prime of good reduction for $\phi$, and consider the reduced map $\tilde{\phi}$. If 0 is preperiodic under $\phi$, then it is not hard to see that it must also be preperiodic under $\tilde{\phi}$, so we can determine integers $k',n'$ such that $\tilde{\phi}^{k' + n'}(0) = \tilde{\phi}^{k'}(0)$. Moreover, it can be shown that $n'$ divides the period of 0 under $\phi$, and $k' \leq k$. My supervisor suggests there is a way that we can use this to show that 0 is either preperiodic or not, under $\phi$, but I don't see this.

My problem is, if 0 is preperiodic under $\phi$, there exists integers $k,n$ such that $\phi^{k+n} = \phi^k$, so summing everything up in this notation, we have

-$\tilde{\phi}^{k+n} = \tilde{\phi}^k$

-$\tilde{\phi}^{k'+n'} = \tilde{\phi}^{k'}$

-$n'|n$

-$k'\leq k$

where $n'$ and $k'$ are easy to compute (I will be dealing with small primes unless a magnificently horrible example arises, but I doubt this..) but I simply do not see any way of getting $k$ from this information. If I were to have a map $\phi$ such that it takes 100 000 iterations of 0 to get to a periodic point, yet the reduced map is periodic right away, the situation seems undetectable.

Any ideas? I feel like I must be missing something simple..

Filling in a few more details, if we have a periodic point $P$, there are results that say the period of $P$ under $\phi$ is a multiple of the period under $\tilde{\phi}$, so if we use a couple well chosen primes for reduction, our list of possible periods for $P$ will be small, and easy to check with a computer. Hence why we are attempting this approach. (Also, this comes from a question in arithmetic dynamics, if anyone feels the need for such a tag to be created.)

Thanks!

-
What about about $20$ well-chosen primes? As a bonus, procedure is then parallelizable. – André Nicolas Jul 7 '11 at 5:33
Sure, but we still don't know what $k$ is, and so if we're dealing with a point that is not preperiodic, we won't be able to stop having gone "far enough". We'll just keep searching and searching.. – Alex Jul 7 '11 at 5:42
Basically, without a notion of the size of $k$, this procedure will not work (I think?) – Alex Jul 7 '11 at 5:44
The suggestion was only about maybe radically speeding up the search. It can fail, if period is very large, or (by adding primes) can be turned into a possibly more efficient search than the usual one, but still a search. – André Nicolas Jul 7 '11 at 5:58
Fair enough, unfortunately I'm pretty sure most, if not all of my cases, are non-preperiodic. – Alex Jul 7 '11 at 7:28

If 0 is not preperiodic, I agree that a finite number of primes can never prove that. However, they might tell you that $k$ and $n$, if they exist, must be outlandishly large, which one can take as an indication that 0 is not preperiodic.

-
This is what I was concerned of :< – Alex Jul 7 '11 at 7:30

Alright, what my supervisor had in mind was to show a point is not preperiodic, by showing none of the points in its orbit can be periodic. If we have a map $\phi$ and it's reduction at $p$, $\tilde{\phi}$, then if $\phi$ has a periodic point $z$ of period $n$, we know $\tilde{\phi}$ has $z$ as a periodic point, with period $n'$, where $n'$ divides $n$.

So, it's not full proof, but we can use multiple primes, say $p_1,p_2,\ldots,p_m$ and test the period of the points in the orbit of 0 for each of the reduction maps at $p_i$, suppose the periods are $n_1,n_2,\ldots,n_m$. Then we know if there is a periodic point in the orbit of 0 under $\phi$, it must be a multiple of $n_1,n_2,\ldots,n_m$. In fact, the works of Li, Morton-Silverman, Narkiewicz, Pezda and Zieve combined tells us exactly what the multiples can be. These are sufficiently restrictive, so that (one hopes) using enough good primes will give contradictory periods (i.e., $n = 3$ from one prime and $n = 5$ from another prime means there is no $n$!)

Fortunately, this was enough for all my (10 000) cases, and 0 is not preperiodic in every case, as expected!

If anyone would like the explicit references, I can certainly pop them up here. Otherwise, if you have access to The Arithmetic of Dynamical Systems by Joseph Silverman, it's the first theorem in section 2.6 (page 62).

-