6
$\begingroup$

Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates $f(p),f(f(p)),\ldots$ are bounded? Is this problem known to be algorithmically undecidable?

This was posted on Math stackexchange here .

$\endgroup$
1
  • $\begingroup$ Two things that might be related: The Matyasevic-Theorem which sais that solving diophantine equations is undecidable. Additionally, maybe the theorem that the Z3 computer is turing complete might be related, since the Z3 computer only supported addition, multiplication and square rooting. See en.wikipedia.org/wiki/Z3_%28computer%29. $\endgroup$ Aug 26, 2014 at 9:43

2 Answers 2

2
$\begingroup$

This is almost an answer, but not quite:

It is known that determining if $(0,0)$ is a point in the attractor of an IFS, is undecidable, see this paper. This is very close to what you have.

There is also a very concrete problem, where one iterates a rational map, and it is unknown if starting with $x=2$ is unbounded. I think the map was $x \mapsto x-1/x$ but I might be mistaken.

There are also non-computable julia sets obtained from polynomial iteration, see here.

$\endgroup$
8
  • $\begingroup$ The sentence "It is known.." is missing some words? $\endgroup$ Aug 26, 2014 at 8:17
  • $\begingroup$ Ah, yes :). Fixed! $\endgroup$ Aug 26, 2014 at 8:18
  • 1
    $\begingroup$ On the other hand, Section 5 of the Braverman and Yampolsky paper (your second link) says that filled Julia sets are computable. $\endgroup$ Aug 26, 2014 at 15:43
  • $\begingroup$ @RobertIsrael: True, but in the filled version, you can essentially paint all points that converges nicely (which are outside the julia set), so this is no surprise. The points in the julia set are the "hard" ones. $\endgroup$ Aug 26, 2014 at 19:08
  • $\begingroup$ @Per: Thank you for the reference to the result on IFS undecidability. Alas, I don't see how to the IFS result here. However the second point, about the map $x\to x-1/x$ seems really interesting. Do you have a reference? $\endgroup$ Aug 27, 2014 at 7:12
0
$\begingroup$

The following answer is relevant:

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

As there, the key question is which definition of decidability to use. The most natural notion comes from computable analysis. Here the point is ever only known up to some finite precision, and then the answer to "can you determine whether the iterates are bounded" is trivially negative. On the other hand, the similar question of computing the filled Julia set (i.e., set of points with bounded orbits) was settled in the positive by Braverman and Yampolsky, as pointed out by Robert. This means essentially that you can tell at least whether there is a point with bounded orbit nearby or not.

Of course, you are asking about maps with rational coefficients, and if you are interested in the behaviour of rational starting points, then you have a decision problem in the classical sense of computer science, whose decidability is likely an open question. However, in my view it is not a natural question from the point of view of dynamics, since the answer then seems to have much more to do with "what can we say about the existence and behaviour of rational/algebraic points in Julia sets?" rather than "can we decide whether a point has bounded orbit?" ...

$\endgroup$
1
  • $\begingroup$ For example, I don't think anything is known regarding (classical) decidability of $\{c\in\mathbb{Q}: x\mapsto x^2+c \mbox{ has an attracting cycle}\}$. $\endgroup$ Aug 30, 2014 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.