6

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 .

Community
  • 1
Sidney Raffer
  • 6,159
  • 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 https://en.wikipedia.org/wiki/Z3_%28computer%29. – Christoph-Simon Senjak Aug 26 '14 at 09:43

2 Answers2

2

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.

Per Alexandersson
  • 15,598
  • The sentence "It is known.." is missing some words? – Brendan McKay Aug 26 '14 at 08:17
  • Ah, yes :). Fixed! – Per Alexandersson Aug 26 '14 at 08:18
  • 1
    On the other hand, Section 5 of the Braverman and Yampolsky paper (your second link) says that filled Julia sets are computable. – Robert Israel Aug 26 '14 at 15:43
  • @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. – Per Alexandersson Aug 26 '14 at 19:08
  • @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? – Sidney Raffer Aug 27 '14 at 07:12
  • @SRJ: The reference I got is this: http://mathoverflow.net/a/100391/1056, which further points to http://www.math.grinnell.edu/~chamberl/papers/mario_digits.pdf The problem seems to be from 2000. – Per Alexandersson Aug 27 '14 at 07:18
  • @Per '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.' - On the contrary, it is harder to prove computability of the filled-in Julia set in the case where this set has non-empty interior ... – Lasse Rempe Aug 29 '14 at 22:47
  • @LasseRempe-Gillen: Ah, my intuition was wrong then. :) – Per Alexandersson Aug 29 '14 at 23:44
0

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?" ...

Community
  • 1
Lasse Rempe
  • 6,455
  • 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}}$. – Adam Epstein Aug 30 '14 at 02:45