Is there a effective computational criterion to all periodic points of a rational function are repelling.

Question

I came up with a question to know the fatou component of of some types of rational function. In some sense, I may need to give a computational criterion to existence of attracting periodic basin for a rational function, which is related to Fatou's theorem.

I tried some examples , however, sometimes I can not find attracting periodic point (period from 2 to 100) with the comupters. I have no idea to know whether it has a attracting basin basin for $f$ or not. For example, $$f(z) = -2/3*z+(-2*z^3+1)/(3*z^3+5*z).$$ By the software of Ultra Fractal, and it seems that the julia set of the example is very small (may be a Cantor set), I can only see the whole screen is black.

Answer 1

It seems that there is no criterion (an algorithm which will always give an answer). Consider the following simplified problem: is there a criterion that $z^2+c$ has an attracting fixed point in $C$? The set of such $c$ is a union of disjoint open regions. Each region is bounded by an algebraic curve, but the number of regions is infinite. Thus the set is not semi-algebraic, and there can be no "criterion".

So the situation is the following: if your computer finds an attracting point, then you are done. If not, you cannot make any conclusion.

But if the word "criterion" means only a sufficient condition for absence of attracting points then such criteria exist. In doing computation, one only has to look at the trajectories of the critical points. So if all critical points eventually are absorbed by repelling cycles, then there are no attracting fixed points, and $J=C$. This is a nice, verifiable condition which is most frequently used in showing that for some specific function $J=C$.

Answer 2

As Alexandre points out, if every critical point of a rational function is pre-periodic, then the Julia set of the function is the entire Riemann sphere. This is stated as Theorem 4.3.1 in Beardon's Iteration of Rational Functions. A simple example is $$f(z) = (z-2)^2/z^2$$ whose only critical points are $0$ and $2$ and satisfy $$2\rightarrow0\rightarrow\infty\rightarrow1\rightarrow1.$$ Unfortunately, this is a rather narrow criterion in that there may be many functions with full Julia set (i.e., the whole Riemann sphere) that don't satisfy the criterion.

There is, in principle however, a necessary and sufficient condition for a rational function to have full Julia set: There simply needs to be one point whose orbit is dense in the Riemann sphere (Thm 4.3.2 of Beardon). While I suspect this is impractical to use in a proof, it's simple to use as numerical evidence when you are unable to find attractive periodic orbits. Applying this to your function, I obtained the following picture which plots the first $20,000$ points of a random orbit on the Riemann sphere. I include the Mathematica code since I think it's quite simple and illustrates the idea.

f[z_] = -2/3*z + (-2*z^3 + 1)/(3*z^3 + 5*z);
pts = {Re[#], Im[#]} & /@ NestList[f, RandomComplex[], 20000];
pts3D = pts /. {x_, y_} -> {2 x, 2 y, (x^2 + y^2 - 1)}/(1 + x^2 + y^2);
Graphics3D[Point[pts3D]]

Definitely not proof of a dense orbit but compelling enough that I wouldn't spend my resources looking for very long attractive behavior. A similar picture is generated by the other example.

In order to appreciate this, it might be instructive to look at another example with no attractive orbits:

$$f(z) = (z^3 - z)/(-z^2 + 4 z + 1).$$

This function has parabolic fixed points at $0$ and $\infty$ both with multiplier $-1$. Furthermore, all critical points lie in the basins of these two points. Thus, you're not going to find attractive orbits. A million iterates from a random complex point for this function looks something like so on the Riemann sphere:

Quite different.

There is one other approach that might be fruitful - you might place your example in a parametrized family of functions, say:

$$f_{\lambda}(z) = \lambda\left(-2/3*z + (-2*z^3 + 1)/(3*z^3 + 5*z)\right).$$

We can now search for values of $\lambda$ where some attractive behavior is detected. It's not too hard to prove that $\infty$ is an attractive fixed point whenever $\lambda>3/2$. Thus, for all $\lambda\leq3/2$, we iterate from all six critical points of $f$ in search of attractive behavior. In the image below, the black region indicates that no attractive behavior was detected at all. The lighter shaded region indicates that some attractive behavior was detected. For each critical point, we iterate up to 250 times until an attractive orbit of length up to 25 is detected; we then add up those six values and shade according to that sum. Thus, a very light shade indicates that all six critical points converged quickly to an orbit.

Of interest for your question is the fact that the small yellow dot at the point $\lambda=1$ appears to be wholly contained in the black region. Again, not proof, but compelling.

Answer 3

The best way to study these questions is in the framework of computable analysis. I will take your rational function as being given by oracles for its coefficients and for its critical points. (That is, for a given epsilon, we expect to be able to know these values up to an error of epsilon.)

In this framework, the question "Does f have non-repelling periodic points?" is undecidable. Indeed, suppose that the rational map is such that it has only repelling periodic points and is not structurally stable. (Conjecturally, every map having only repelling periodic points is structurally unstable. Under many circumstances this is known; the simplest case is the postcritically finite case where it follows from work of Thurston.)

Then there are rational maps arbitrarily nearby that do have nonrepelling cycles, and hence we cannot distinguish between the two cases by considering our map only up to finite precision.

However, if we replace "non-repelling" by "attracting", then the problem is semi-decidable. Indeed, we basically just iterate the critical values and see whether they converge to an attracting cycle; this can be done rigorously. (I will omit the details, but suspect they can be found e.g. in the work of Braverman and Yampolsky.)

Of course, when your coefficients are given in some absolute way (e.g. as rational or algebraic numbers), then you can ask about this as a classical problem in computer science. This problem seems less natural, although I would expect it also to be undecidable. There is a result that says that the Mandelbrot set is undecidable in the sense of Shub-Smale (which assumes infinite-precision arithmetic), which suggests at least that the problem can't be solved in any naive way.

Of course, there are specific examples for which it can be verified that there are no nonrepelling cycles, as mentioned by Alexandre.