[FOM] Re: FOM Digest, Vol 14, Issue 10

[Adam Epstein]

> Suppose we are given a (maybe even fairly small) finite number of rational
> points in R^3 representing the initial positions of some Newtonian particles
> subject only to the Newtonian inverse square law of gravitation (say, in
> geometric units). We are also given initial velocity vectors for these
> particles, again by rational numbers.

......
>
> We want to know the recursion theoretic status of these algorithmic
> questions.
>
> What about polynomial time hardness with respect to log space linear time
> reductions?
>
> Harvey Friedman


I don't now anything about the status of these questions. But matters such
as these are already an issue for much more basic (if less physical)
dynamical systems. For example, consider the one-parameter familiy of
polynomial maps x->x^2+c. These are often studied over C (yielding
Julia sets and the Mandelbrot set) but for now restrict attention to real
values of x and real parameters c.

The existence of MANY periodic cycles is easy. Here what is interesting is
the existence of attracting cycles. And old theorem of Fatou specializes
here to assert that there is at most one attracting cycle.

With this background one could consider the following question often posed
by Milnor:

For a given rational number c, does the map x^2+c have an attracting cycle?

Is this matter necessarily decidable? If so, can one bound the complexity?

For many years it was an important open problem to show that the (open)
set of c\in[1/4,-2] (the rest of the parameter range being somewhat trivial
dynamically) for which there exists an attracting cycle is actually dense.
This was shown around 1993 by Lyubich and Graczyk-Swiatek.

Thus, it seems appropriate to consider the following variant questions:

Given a (rational) number c and some epsilon>0, can one prove by
elementary means (e.g. within Peano Arithmetic) that some parameter
within epsilon of c yields a map with an attracting cycle?

What is the relationship between the smallness of epsilon and the
largeness of the period of the attractor? If the period grows too rapidly
as epsilon->0 does this entail that the density theorem (after suitable
transcription, of course) is unprovable over PA? Does this approximation
problem have an interesting computational complexity?

To my knowledge, nobody is currently working on questions of this type.

Adam Epstein