Do any of these sequences have infinitely-many distinct iterates under run-length substitution?

Solution 1:

The answer is yes.

Let $\mathbb N$ denote the set $\{1,2,...\}$ of positive integers and $P=\{1,2\}^{\mathbb N}$. Given any $\rho\in P$ we will define $\varphi_\rho\in S$ such that all $T$-iterates of $\varphi_\rho$ remain in $S$ and $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$ for all $k\in\mathbb N$, where $\rho(k)$ denotes the $k$-th element of $\rho$, and $(T^{k-1}(\varphi_\rho))(1)$ denotes the first element of the $(k-1)$-st iterate, $(T^{k-1}(\varphi_\rho))$, of $\varphi_\rho$.

If $T^k(\varphi_\rho)$, $k\in\mathbb N$, is eventually cyclic, that is, if there are $n,m$ such that $T^{k+m}(\varphi_\rho)=T^k(\varphi_\rho)$ for all $k\ge n-1$, then clearly the sequence of the corresponding first coordinates, namely $(T^k(\varphi_\rho))(1)$, $k\in\mathbb N$, would also be eventually cyclic. Hence $\rho$ turns out to be eventually cyclic, with $\rho(k+m)=\rho(k)$ for all $k\ge n$.

Since $P$ is uncountable (with $|P|=\mathfrak c =2^{\aleph_0}$) and since there are only countably many eventually cyclic sequences $\rho\in P$, it follows that for all the uncountably many remaining choices of $\rho$ the iterates under $T$ of $\varphi_\rho$ would never repeat. Thus, to complete the proof, it only remains to define $\varphi_\rho$ with the above properties, for each $\rho\in P$.

I will just illustrate the construction of $\varphi_\rho$, given $\rho\in P$, with a couple of examples. First, say $\rho$ starts as $\langle 2,1,2,2,1,... \rangle$, or, abbreviated, as $21221..$. List the elements of $\rho$ in a column, from top to bottom, as illustrated:
$\\ 2\\ 1\\ 2\\ 2\\ 1\\ ... $

Then, starting with lower and lower rows, work backwards, to define larger and larger initial segments of the first row, which will be our $\varphi_\rho$. That is, start with row $2$, work backwards, then start with row $3$, work backwards, etc. Here is how it works when we start with row $2$ (and work backwards, that is, partially define row $1$ so that an application of $T$ to row $1$ results in row $2$):
$\\ 21\\ 1\\ 2\\ 2\\ 1\\ ... $

Then start with row $3$ and work backwards (so that an application of $T$ to row $2$ results in row $3$, and an application of $T$ to row $1$ results in row $2$:
$\\ 21221\\ 112\\ 2\\ 2\\ 1\\ ... $
We do all this subject to the requirement that each row remains in $S$ and has runs of length at most $2$.

From the given initial segment of $\rho$ following this procedure we obtain:
$\\ 2122112112212\\ 11221221\\ 2212\\ 21\\ 1\\ ... $
where the first row represents an initial segment of the $\varphi_\rho$ that we construct.

As a different example say $\rho$ starts at $\rho=\langle 2,1,1,1,2,1,,... \rangle=211121..$. Listing the elements of $\rho$ in a column, from top to bottom, we have:
$\\ 2\\ 1\\ 1\\ 1\\ 2\\ 1\\ ... $

Working from row $3$ backwards we have:
$\\ 2112\\ 12\\ 1\\ 1\\ 2\\ 1\\ ... $
and working from row $6$ backwards we have:
$\\ 21122122121121\\ 122121121\\ 121121\\ 1121\\ 21\\ 1\\ ... $
where, again, the first row represents an initial segment of the corresponding $\varphi_\rho$ that we construct.

Clearly, by construction, each $T^k(\varphi_\rho)$ remains in $S$, and $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$, which completes our answer.

What follows below an an older and more complicated recursive construction of $\varphi_\rho$. You need not read it, though I will leave at available.

I post a second answer (compared not to the above, but to versions posted even earlier), that uses the same ideas as my previous answer (that is, earlier answer posted separately), but is written better (I think (well, at hindsight, clearly not as good as the simple description given above)). I would keep the previous answer too (... someone voted it up (no longer, perhaps the vote was retracted or there was also another vote down, but anyway) so I hate to erase it now, besides it might be of some interest, but please do not read my older answer unless you would like to see how I came up with this example, and unless you are ready to put up with the inconsistencies there, which I do not intend to clean).

So here is what I hope the better example.

The answer is ``yes''. I describe a procedure that produces many examples (it only fails to produce an example for a countable subset of a certain product space of uncountable cardinality).

Let $\mathbb N$ denote the set of positive integers and $P=\{1,2\}^{\mathbb N}$. (There are some fine notational adjustments that could be made in what follows, depending on whether one takes $0\in\mathbb N$ or $0\not\in\mathbb N$; my notation is consistent with the latter choice, that is, $1=\min\mathbb N$.)

We will define a map $\varphi$ from $P$ to $S$. That is, $$\varphi: P \to S, \mathrm{\ if\ } \rho\in P \mathrm{\ then\ } \varphi_\rho\in S$$

The $n$-th element of a sequence will be denoted like $\rho(n)$ or $\varphi_\rho(n)$. The map $\varphi$ will have the following two properties:

1. $T^k(\varphi_\rho)\in S$ for all $k\in \mathbb N\cup\{0\}$ and all $\rho\in P$,

2. For all $k\in\mathbb N$, $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$.

Condition 2 implies that if the sequence $\langle \varphi_\rho,T(\varphi_\rho),T^2(\varphi_\rho),..., T^k(\varphi_\rho),... \rangle$ is eventually cyclic, that is, if there are $n,m\in\mathbb N$ with $T^k(\varphi_\rho)=T^{k+m}(\varphi_\rho)$ for all $k\ge n-1$, then the sequence $\rho=\langle\rho(1),\rho(2),...\rangle$ is eventually cyclic, with $\rho(k)= \rho(k+m)$ for all $k\ge n$.

Let $P_0$ be the subset of $P$ consisting of all eventually cyclic sequences, and let $P_1=P\setminus P_0$. Since $P_0$ is countable and $P$ is uncountable (with $|P|=\mathfrak c = 2^{\aleph_0}$, the cardinality of the continuum), we have that $P_1$ is uncountable (with $|P_1|=\mathfrak c$). Thus, all $T$-iterates of $\varphi_\rho$ remain in $S$ and are never repeating, whenever $\rho\in P_1$. This shows that not only examples do exist, but there are uncountably (continuum) many of them.

In order to construct $\varphi$ we first construct another map $$\beta: P \to P, \mathrm{\ if\ } \rho\in P \mathrm{\ then\ } \beta_\rho\in P$$

To define $\beta$, we take all initial segments of $\rho$, reverse each, and put them one after the other. To illustrate, say $\rho$ starts as $\langle2,1,1,1,2,1,... \rangle$, or abbreviated $211121..$. Then the initial segments of $\rho$ are $\langle2 \rangle$, $\langle2,1 \rangle$, $\langle2,1,1 \rangle$, $\langle2,1,1,1 \rangle$, $\langle2,1,1,1,2, \rangle$, $\langle2,1,1,1,2,1 \rangle$, ... , or abbreviated,

$$2,21,211,2111,21112,211121,...$$

Reversing each initial segment we obtain

$$2,12,112,1112,21112,121112,...$$

and concatenating these we obtain that $\beta_\rho$ starts as

$$212112111221112121112...= \langle2,1,2,1,1,2,1,1,1,2,2,1,1,1,2,1,2,1,1,1,2,... \rangle $$

Formally let $t_n=\frac{n(n+1)}2$ denote the $n$-th triangular number. Then $\beta_\rho(t_n-m)=\rho(m+1)$ for all $n$, and all $m\in\{0,1,...,n-1\}$.

We now start the construction of $\varphi_\rho$. To illustrate, let again $\rho$ start as $211121..$., so $\beta_\rho$ starts as $212112111221112121112..$. List the elements of $\beta_\rho$ in a vertical column starting at the bottom and going up like this:

$\\ ... \\ 2\\ 1\\ 1\\ 2\\ 1\\ 2 $

Working "backwards" define partial rows consistent with the leftmost column, as described below. Let $p^j$ denote partial row $j$ (counted from bottom) and $p^j(n)$ denote the $n$-th element of $p^j$. The requirement is that $T(p^{j+1})=p^j$. For example, $p^2$ must be a partial sequence that starts with $\beta_\rho(2)$, in our example $\beta_\rho(2)=1$, and such that $T(p^2)$ starts as $p^1$. Thus, $p^2$ must start as $11$, and for convenience (and to make sure that the lengths of the $p^j$ strictly increase even in cases when $\beta_\rho(1)=1$) we also add a terminating element consistent with $p^2$ being an initial segment of a sequence in $S$ and having runs of length at most $2$, so $p^2$ starts as $112$. (Here we only apply the restriction of $T$ to just a finite sequence, so the rest of the sequence (which cannot be determined by the given information) could be denoted by a $*$, e.g. $p^2=112*$.) Then, $p^3$ must be a partial sequence that starts with $\beta_\rho(3)$, in our example $\beta_\rho(3)=2$, and such that $T(p^3)$ starts as $p^2$. Thus, $p^3$ starts as $21221$. Since the first element of $p^j$ is given, namely $p^j(1)=\beta_\rho(j)$ the construction as described so far is unambiguous, and produces the following partial rows for our example.

$\\ ... \\ 211212212211212212112\\ 12112122112112\\ 112112212\\ 21221\\ 112\\ 2 $

Let $|p^j|$ denote the length of (the defined part of) $p^j$, and let $|p^j|_2$ count how many times the number $2$ occurs in $p^j$. For example $|21221|=5$ and $|21221|_2=3$. It is easily shown that $|p^{j+1}|=|p^j|+|p^j|_2 +1$ for all $j$, and (using that the last two elements of $p^j$ are always different) that $|p^j|_2\le |p^j|-1$ for all $j\ge2$. It follows that $|p^j|<|p^{j+1}|\le 2 |p^j|$ for $j\ge2$.

Let $J_1=\{\frac{n(n+1)}2: n\in\mathbb N\}$ be the set of all triangular numbers. We will construct a decreasing sequence of infinite sets $J_1\supset J_2 \supset J_3 \supset ...$, and simultaneously define $\varphi_\rho(n)$ as follows. Set $\varphi_\rho(1)=\rho(1)$. Note that $p^j(1)=\beta_\rho(j)=\beta_\rho(t_n)=\rho(1)$ for all $j\in J_1$ (where $j=t_n$ is a triangular number for some $n$).

For each $j\ge2$, we have that $p^j(2)$ is defined and is in $\{1,2\}$. Split $J_1\setminus\{1\}$ into the disjoint union of two sets, $J_1(1)=\{j\in J_1\setminus\{1\}:p^j(2)=1\}$, and $J_1(2)=\{j\in J_1\setminus\{1\}:p^j(2)=2\}$. At least one of these two sets must be infinite. If $J_1(1)$ is infinite then let $J_2=J_1(1)$ and $\varphi_\rho(2)=1$. Else let $J_2=J_1(2)$ and $\varphi_\rho(2)=2$. Proceed by recursion as follows.

Split $J_n\setminus\{1,...,n\}$ into two sets, $J_n(1)=\{j\in J_n\setminus\{1,...,n\}:p^j(n+1)=1\}$, and $J_n(2)=\{j\in J_n\setminus\{1,...,n\}:p^j(n+1)=2\}$. If $J_n(1)$ is infinite then let $J_{n+1}=J_n(1)$ and $\varphi_\rho(n+1)=1$. Else let $J_{n+1}=J_n(2)$ and $\varphi_\rho(n+1)=2$.

This defines $\varphi_\rho(n)$ for all $n$. Note that if $j\in J_n$ with $|p^j|\ge n$ then $p^j(k)=\varphi_\rho(k)$ for all $k\in\{1,2,...,n\}$. (Use that $J_n\subset J_{n-1}\subset ... \subset J_1$ .)

Next we show that for all $k\in\mathbb N$ we have $(T^{k-1}(\varphi_\rho))(1)=\rho(k)$. When $k=1$, $(T^{0}(\varphi_\rho))(1)=\varphi_\rho(1)=\rho(1)$. Now fix $k>1$. Note that if $|p^j|$ is large enough, e.g. if $|p^j|\ge3^k$, then $(T^{k-1}(p^j))(1)$ is defined (use that $|T(p^{m+1})|=|p^m|\ge\frac{|p^{m+1}|}2$ for all $m\ge2$). Pick $j$ large enough subject to the following conditions: $j\in J_{3^k}$, $|p^j|\ge3^k$, and $j=t_n$ with $n>k$. Then $(T^{k-1}(\varphi_\rho))(1)=(T^{k-1}(p^j))(1) =\beta_\rho(t_n-(k-1))=\rho((k-1)+1)=\rho(k)$.

The proof that $T^k(\varphi_\rho)\in S$ for all $k$, and all $\rho\in P$ is similar. Indeed if $T^k(\varphi_\rho)\not\in S$ then either $(T^k(\varphi_\rho))(m)\ge3$ for some $m$, or $(T^k(\varphi_\rho))$ has an infinite run. In the latter case $(T^{k+1}(\varphi_\rho))(m)\ge3$ for some $m$, so it reduces to the former. But if $(T^k(\varphi_\rho))(m)\ge3$ then we could pick large enough $n$ and $j$ with $j\in J_n$ and $|p^j|\ge n$ such that $3\le(T^k(\varphi_\rho))(m)= (T^k(p^j))(m)\in\{1,2\}$, a contradiction.