3 edited tags
2 deleted 2 characters in body

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_k$ 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! 1 # 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_k$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!