Repeatedly indexing into an $\infty$-sequence of integers

Question

Suppose one has in hand an infinite sequence $s$ of distinct natural numbers, for example,

$$s=s_1=(1, 3, 5, 7, 9, 11, 13, 15, 17, 19,\ldots) \;.$$

So this sequence can be considered an injection $f: \mathbb{N} \mapsto \mathbb{N}$.

Now replace $s_1$ with $s_2$ by indexing in $s_1$ using $s_1$: $$s_2=(1, 5, 9, 13, 17, 21, 25, 29, 33, 37,\ldots) \;.$$ So we take the 1st, 3rd, 5th, ... elements of $s_1$ to form $s_2$. To construct $s_3$, index into $s_2$ using $s_2$: take the 1st, 5th, 9th, ... elements of $s_2$, i.e., $$s_3=(1, 17, 33, 49, 65, 81, 97, 113, 129, 145,\ldots) \;.$$ Note that, e.g., the 2nd element of $s_3$ is not $f^3(2) = 9$, but rather $f^2( f^2( 2)) = f^4(2) = 17$. Iterating once more we reach $$s_4=(1, 257, 513, 769, 1025, 1281, 1537, 1793, 2049, 2305,\ldots)\;. $$ Here, e.g., the 2nd element of $s_4$ is $f^8(2)=256 \cdot 2 - 255 = 257$.

Several questions:

Q1. For which starting sequences $s$ does this process lead to a fixed sequence, $s_k = s_{k+1}$? Certainly it does if $s$ represents the identity: $s_1=(1,2,3,4,5,\ldots)$. Are there any other fixed sequences?

Q2. For which starting sequences $s$ does this process lead to a cycle among the sequences, $s_k = s_{k+m}$, $m>1$? And can the length of such a cycle be predicted from the structure of the starting sequence?

Q3. What is the expected behavior under iteration of a "typical" (random?) starting injection $s$, under any reasonable sense of "typical"?

I feel certain this has all been studied before, and I am just not phrasing it in an easily recognizable manner. I would appreciate pointers—Thanks!

Answer 1

Q1. If the sequence is strictly increasing, there will be neither nontrivial fixed sequences nor cycles. Each sequence will increase faster than the next.

In general, the equation is obviously f(f(n))=f(n). To construct a sequence satisfying that equation, divide the natural numbers into a some number of equivalence classes, then map each class to one element of itself.

Q2. To solve the equation $f^{2^k}(n)=f(n)$, first divide the natural numbers into equivalence classes, then group the equivalence classes into cycles of order dividing $2^k-1$, then map each class to an element of the next class in its cycle.

Q3. In general, some registers of the sequence will stay fixed, some will stay in cycles, and some will go off to infinity. The proportions of each depend on the exact random distribution used to construct the sequence. If each number of the sequence is independent, the paths of the different registers will be relatively independent, interfering only if they intersect.

I think it probably makes more sense to study $f^1(n),f^2(n),f^3(n),\dots$ of which your sequences just form the power-of-$2$ component.

Answer 2

Suppose a sequence $s_k = (a_1, a_2, \ldots)$ has $s_k = s_{k+1}$. Then $a_i = a_{a_i}$, and by injectivity of $f$ (and hence iterations of $f$), we have $a_i = i$. So there is just one fixed sequence.

Here are a family of sequences where $s_1 = s_{2n + 1}$. Only the first $2^n + 1$ terms are permuted, and the rest of the sequence is a copy of the identity. If any number $a_i = i$ at some point during the iteration of sequences, then it will remain stationary forever, so we need only consider the first $2^n + 1$ terms. $$ s_1 = (2^n + 1, 1, 2, 3, \ldots, 2^n) $$ $$ s_2 = (2^n, 2^n + 1, 1, \ldots, 2^n - 1) $$ $$ s_3 = (2^n - 2, 2^n - 1, 2^n, 2^n + 1, 1, \ldots, 2^n - 3) $$ $$ s_4 = (2^n - 6, 2^n - 5, 2^n - 4 , 2^n - 3 , 2^n - 2, 2^n - 1, 2^n, 2^n + 1, 1, \ldots, 2^n - 7)$$ $$ \cdots $$ $$ s_{n+1} = (2, 3, \ldots, 2^n + 1, 1) $$ $$ s_{n+2} = (3, \ldots, 2^n + 1, 1, 2) $$ $$ s_{n+3} = (5, \ldots, 2^n + 1, 1, 2, 3, 4) $$ $$ \cdots $$ $$ s_{2n+1} = (2^n + 1, 1, 2, 3, \ldots, 2^n) $$

Doing the same thing beginning with $2^n$ instead of $2^n + 1$ leads to the identity. Doing it with $2^n + k$ where $0 < k < 2^n$ leads to a cycle with some term $s = (2^n + 1, 2^n + 2, \ldots, 2^n + k, 1, 2, \ldots, 2^n)$.

If there is some simple bounding condition as follows, then iterations will cycle locally, but may not globally. Suppose there is a sequence of natural numbers $0 = m_0 < m_1 < m_2 < \cdots$ such that for every $j$, $a_i \leq m_j$ for all $i \leq m_j$. Then the first $m_1$ terms will remain in the first $m_1$ places, the next $m_2 - m_1$ terms will remain in the next $m_2 - m_1$ places, etc. Since there are only $(m_{j+1} - m_j)!$ permutations of each of these sets, they must all eventually be cyclic individually. But we can choose these cycles to have no common multiple, e.g. take $m_{i+1} - m_i = 2^i + 1$, and repeat the construction above.