For any continuous map $f:\mathbb{R}\to\mathbb{R}$, the set of periods is a suffix of the Sharkovskii order of the positive integers. By "period" I mean the length $m$ of a cycle $x_0, f(x_0), f(f(x_0)), \ldots, f^{(m)}(x_0)=x_0$ where $m$ is the first iterate of $f$ that maps $x_0$ back to itself.
Specifically, $f$ may have:
- No periodic points at all
- Periods $2^k$ for $0\leq k \leq K$ for some $K$ (and no others)
- Periods $2^k$ for all $k$ (and no others)
- A period $P=2^K b$ for some odd $b>1$, and with it all periods of the form $2^k b'$ where $k>K$ or ($k=K$ and $b'>b$), as well as every $2^k$ with no odd part. (But no others).
A polynomial $f(x)\in\mathbb{Z}[x]$ with integer coefficients induces a continuous function. Is it decidable which of these is the case, and with which parameters?
Clearly, there's an algorithm to decide if $f$ has a given period $p$: the iterate $f^{(p)}$ is a polynomial, and we can determine if $f^{(p)}(x)=x$ has any solutions that aren't already solutions for a smaller iterate.
But this doesn't immediately suggest an algorithm to determine the precise suffix.
Is there such an algorithm?