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

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!

-
One way of thinking about the Ackermann function is as a sequence of sequences: the recursion definition tells you how to index the next row using the previous row and an index depending on the previous row. Gerhard "Ask Me About System Design" Paseman, 2011.10.28 –  Gerhard Paseman Oct 29 '11 at 0:37
Are these satisfactory answers? Q1: All cycles are finite and have lengths that are powers of 2,Q2: all cycles are finite,Q3: Under most definitions of typical, a random sequence has an infinite cycle therefore there will be no periodicity and $s_k(n)\to \infty$ as $k\to \infty$ almost certainly for all $n$. –  Gjergji Zaimi Oct 29 '11 at 0:52
Wonderful answers, Gjergji!! But can you give some hints as to why for each, some indication of your reasoning? Thanks! –  Joseph O'Rourke Oct 29 '11 at 1:08
I suggest editing the tag (inf)infinite sequences, unless you are making a nod towards $\mathbb{N}$ being the smallest of infinities. –  Zack Wolske Oct 29 '11 at 2:20

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.

-
Thanks, Will, especially for your last remark, which is surely good advice. –  Joseph O'Rourke Oct 29 '11 at 12:57
Are you satisfied with the amount of explanation between the two answers and Gjergi's comment. I could provide a formal argument why his and my answers are correct. –  Will Sawin Oct 29 '11 at 20:29

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.

-
I like your $s_1 = s_{2n + 1}$ example, Zack---very clever! –  Joseph O'Rourke Oct 29 '11 at 13:00