# Algorithm for determining when polynomial iteration is bounded?

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 .

• 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. – Christoph-Simon Senjak Aug 26 '14 at 9:43

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.

• The sentence "It is known.." is missing some words? – Brendan McKay Aug 26 '14 at 8:17
• Ah, yes :). Fixed! – Per Alexandersson Aug 26 '14 at 8:18
• 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 7:12

• 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 2:45