This question is based on this old MathOverflow question: How this set of functions is ordered?
In that question, Vladimir Reshetnikov asked about a class $S$ of functions $f:\mathbb{N}\to\mathbb{N}$ (note that $\mathbb{N}$ here includes $0$, this is important, because this is what allows us to do some rudimentary "programming" with this construction -- see my answer at the linked question) defined recursively as follows:
- The constant $0$, constant $1$, identity, and successor functions are in $S$
- Given $f,g,h\in S$, one has $n\mapsto f^{g(n)}(h(n))\in S$.
I've been thinking about this construction again and in particular have been wondering: Is there any function $f\in S$ which is bounded but not eventually periodic?
(Or, as I was originally thinking of it: What sets can we detect? I.e. what functions can we construct in $S$ with image contained in $\{0,1\}$? Can we detect any sets that are not eventually arithmetic progressions? Like say the set of squares or the set of powers of $2$? I don't see how to do either of those!)
I had originally hoped to prove there was not such a function, as part of an attempted proof that the predecessor function is not in $S$, but now I suspect that there is such an $f$; I even have a candidate for it, but the candidate seems difficult to analyze.
Specifically: Define $g(n)$ by $g(9q+r)=10\cdot2^q+r$, for $0\le r<9$. Then let $f(n)=g^n(n) \bmod{6}$; this is a function in $S$ (I'll justify that below). Doing some experiments, $g^n(0) \bmod{6}$ also seems to work, which might be easier to analyze, but I haven't really gotten anywhere with that either.
(I say "mod 6", but really either mod 2 or mod 3 individually should work.)
Anyway, that's the question and my candidate. Below the bar I'll put more information (like why $f\in S$ or why I think $f$ might work).
Proof that $f\in S$: By the constructions used to answer the older question, we can construct $h\in S$ defined by $h(n)=2n-18$ if $n\equiv 8\pmod{10}$ and $h(n)=n+1$ otherwise. Then $g(n)=h^n(10)$. So therefore $f\in S$ and then again by the constructions used to answer the older question, we can mod out by $6$ (or whatever you like).
Why I think this candidate might work: My idea was as follows: The problem with iterating something of the form $n\mapsto a^n$ (to get a tetration type function) and then taking that modulo some $m$ is that $a^n$ mod $m$ depends on $n$ modulo $\phi(m)$, which for $m>1$, is less than $m$. So after enough iterations it depends on $n$ modulo $1$, and things stabilize. More generally I'm pretty sure that as long as the $g(n)$ that you're iterating depends, mod any given $m$, on $n$ modulo $m'$ where $m'\le m$ (for large enough $n$), you similarly get eventual periodicity, though the argument is more complicated and I didn't fully check it. So, I figured, what if we could get a sequence of $m_0<m_1<m_2<\ldots$ such that $g(n)$ depends modulo $m_i$ on $n$ modulo $m_{i+1}$? The idea is that the $g$ I defined above satisfies that, with $m_i=2\cdot3^{i+1}$. Because, you see, modulo $3^k$, $2$ is a generator, with order $2\cdot3^{k-1}$, so I figured, if I can just slow things down by a factor of $9$, that should do it.
(I am eliding here the distinction between a modulus of $3^k$ and a modulus of $2\cdot 3^k$ but these are not very different for our purposes here. I said above it should work mod $6$ but I was originally thinking of it as mod $3$. The reason it should work mod $2$ is that its values mod $2$ depend on its values mod $9$, and mod $9$ it should similarly lack any eventual period.)
