The graph of Rule 110 and vertices degree

Question

Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete):

It induces a map $R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $R(n)$ is that of $n$ after the application of Rule 110. For examples, $R(0)=0$, $R(1)=3$, $R(2)=6$ and $R(3)=7$.
See below the illustration for $R(571)=1647$:

There is an OEIS sequence computing $R(n)$ for $n<2^{10}$: A161903.

Definition: Let $\mathcal{G}$ be the graph with $\mathbb{N}$ as set of vertices and $\{\{n,R(n)\}, n \in \mathbb{N} \}$ as set of edges.

The graph $\mathcal{G}$ has infinitely many connected components and its vertices degree is not bounded above.
The proof follows from Lemmas D and E, below.

Question: Is the vertices degree bounded above on each connected component of $\mathcal{G}$?

---

Lemma A: For $n,r>0$, we have that $2^{r-1}n<R^r(n)<2^{r+1}n$.
Proof: Immediate. $\square$

Lemma B: $R(n)$ is even iff $n$ is even.
Proof: A portion $(\epsilon_1,\epsilon_2,0)$ gives $0$ by applying Rule 110 iff $\epsilon_2=0$. $\square$

Lemma C: For $r,k>0$, $R^r(n) = 2kn$ iff $n=0$.
Proof: If $n>0$ then there is $s \ge 0$ such that $n=2^sm$ and $m$ odd. But $R^r(2^sm) = 2^s R^r(m)$, so $R^r(m)=2km$, it follows by Lemma B that $m$ is even, contradiction. $\square$

Lemma D: For $n,r>0$, $n$ and $2^rn$ are not in the same connected component of $\mathcal{G}$.
Proof: If $n$ and $2^rn$ are in the same connected component then there are $r_1,r_2>0$ such that $R^{r_1}(n) = R^{r_2}(2^rn) = 2^r R^{r_2}(n)$, so by Lemma A, $r_1 = r_2 +r$. Then, $R^{r}(m)=2^rm$ with $m=R^{r_2}(n)$, thus $m=0$ by Lemma C, contradiction. $\square$

Lemma E: For any $n>0$, there is a vertex of $\mathcal{G}$ of (finite) degree $\ge n$.
Proof: The pattern of $r \ge 2$ successive black cells (corresponding to the vertex $2^r-1$) is the image of any pattern of $r-1$ cells without successive white cells, without three successive black cells and whose first and last cells are black, see for example below with $r=27$:

Clearly, for $r$ large enough, the vertex $2^r-1$ has degree $\ge n$. $\square$

Exercise: Show that $|R^{-1} (\{ 2^r-1 \}) | = \sum_{2a+b = r} {a \choose b}$, known as the Padovan sequence.

---

Bonus question: What is the sequence $\mathcal{S}$ of minimal numbers of the connected components of $\mathcal{G}$?

Note that $\mathcal{S} \subset \mathbb{N} \setminus R(\mathbb{N}^*) = \{0, 1, 2, 4, 5, 8, 9, 10, 11, 16, 17, 18, 19, \dots \}$, so:

• $\{0,1,2,4,8\} \subset \mathcal{S}$, by Lemmas B and D.
• $5 \in \mathcal{S}$ iff $\forall r_1, r_2>0$ then $R^{r_1}(1) \neq R^{r_2}(5)$.
• $11 \not \in \mathcal{S}$ because $R^4(1) = R(11)=31$.
• I don't know for the other numbers appearing above.

A search for "$0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18$" gives one result only, the Fibbinary numbers $\mathcal{F}$, i.e. the integers whose binary representation contains no consecutive ones (the number of such numbers with $n$ bits is the $n$th Fibonacci number). It is related to Zeckendorf's theorem.

Is it true that $\mathcal{F} \subseteq \mathcal{S}$, or even $\mathcal{F} = \mathcal{S}$?

Note that $\mathcal{F} \subset \mathbb{N} \setminus R(\mathbb{N}^*)$ because a portion $(0,0,1,\epsilon)$ gives $(1,1)$ by applying Rule 110.
I don't know whether $19 \in \mathcal{S}$, but $19 \not \in \mathcal{F}$.

Answer 1

I guess I'll indulge in my guilty pleasure a bit. The connected component of the number $1$ has unbounded degree.

Let $X = \{x \in \{0,1\}^{\omega} \;|\; \sum x < \infty\}$, the finite support configurations (which you identified with the naturals) and let $f : X \to X$ be rule $110$ with left and right flipped. After a lot of trial and error I managed to figure out this is called rule 124 in Wolfram's (very convenient and intuitive) naming scheme. This is just so natural numbers go to the right.

We will show that the connected component of the configuration $x = 1000...$ satisfies that for all $k \in \mathbb{N}$ there are infinitely many $n$ such that $f^n(x)$ has at least $k$ preimages in $X$. Let $y \in \{0,1\}^{\omega \times \omega}$ be the spacetime diagram of $x$, so $y_{(i,0)} = x_i$ and $y_{(i,j+1)} = f((y_{(h,j)})_h)_i$. The key to proving it is the following:

The set $\{(m,n) \;|\; y_{(m,n)} = 1\}$ is semilinear.

Semilinear subsets of $\mathbb{Z}^d$ are finite unions of linear sets, which in turn are sets of the form $a + V$ where $V = \langle v_1,v_2,...,v_n \rangle$ where $\langle \cdots \rangle$ denotes the smallest submonoid containing the $v_i$. Equivalently it means definability in Presburger arithmetic.

I won't actually give a precise proof, but this is seen from a simulation of the first ~3000 steps of evolution, and unless I've missed some very subtle period-breaking phenomenon -- which I doubt because eyes usually jump at those --, this should not take long to prove rigorously by pen-and-paper, or by computer. (You could (at least in theory) do it in Walnut, since semilinear implies $k$-automatic, presumably there are also direct implementations of Presburger arithmetic.)

Now, all we need to observe is that in some of the periodic growing areas of $y$ (there are two) you can locate a diamond, i.e. a word $w$ such that the preimage used above it is $u$, and there is another word $v$ with the same image $w$ and the same two left- and rightmost symbols. Then more and more instances of $u$ appear on the line above and you can change any subset of them to $v$.

For all $k$, $y$ has a row with at least $k$ disjoint occurrences of $01011101100 \mapsto 111011111$ any subset of which can be changed to $01100101100 \mapsto 111011111$.

(Those are in terms of the flipped rule. In terms of $110$, these would be $00110111010 \mapsto 111110111$ vs $00110100110 \mapsto 111110111$. Also, I write $u \mapsto w$ for the usual application of the rule to words, so it shortens them by one on both sides.)

Description of spacetime

I will describe what is seen in a non-rigorous fashion, but of course the finite steps are completely proved by just seeing them in the simulator, and given these initial steps, as I've stated above, the final conclusion is something that can be proved by pen and paper (disclaimer: I did not actually write a proof, as it is still a lot of work).

I recommend drawing a spacetime diagram yourself, I used Golly and you can find Golly compatible rule files at the end of this post.

So, the support will grow steadily as a triangle, the leftmost border stays put (as you observed) and the right border moves at speed $1$. After around 100 steps, the roughly 70 rightmost cells of the spacetime diagram form a complicated glider, then there is a slightly denser area, then there is another glider, and the rest is again this denser stuff. (The leftmost "glider" is not really a glider, because it's not moving periodically, but in this informal description I use this term anyway.) We can already observe that the rightmost glider will never change its behavior as it is evolving with a period of 16 and moving at the speed of light. But that is not enough to solve your question.

The pattern looks nice for a few hundred steps, but around 600 steps the glider on the left suddenly blows up!

Fast forward to step 1200 (lots of things happen on the way) and you have two gliders moving to the right. Now the leftmost one suddenly turns into a left-going glider (marked with a green 1 in the figure). Then the central glider suddenly disappears at step 2086 (marked with a green 2), and right after that the leftmost glider hits the left boundary at step 2160 and turns into another glider going to the right.

It takes a few hits from glider gunfire, but then seems to become resistant to it.

Fast-forward a few thousand steps and it is still going strong.

In fact...

there no more surprises!

You can now prove (by induction) that this pattern persists: the glider on the left keeps moving at speed $(18, 213)$, and shoots additional gliders to the left which hit the left boundary every $140$ steps, and the rightmost glider sends additional gliders periodically, which hit the left glider but don't destroy it. The phases match up after some time, which is really the reason why nothing strange happens.

Alternatively, you can prove as I suggested above that $y$ is semilinear: just write the formulas, and check that this semilinear set is closed under rule $110$: it's decidable whether a given semilinear set is the spacetime diagram of a given CA (for example by the Presburger characterization). I'm sure $y$ is semilinear, because all the things that are happening are is periodic, different types of things happen in areas bounded by rational inequalities (or rational lines), and there are only finitely many phenomena (like, four) going on. And then there's about a million bits of garbage at the beginning, which you just code in.

Ok, so now we need to find occurrences of $01011101100 \mapsto 111011111$. Well, that's one of the steps of one of the gliders that are being gunned periodically from right to left.

Golly compatible rules:

Here's rule 110, call it (e.g.) W110.rule and put it in the Rules folder. Then open it in Golly.

@RULE W110
@TABLE
n_states:2
neighborhood:Moore
symmetries:none

var a={0,1}
var b={0,1}
var c={0,1}
var d={0,1}
var e={0,1}
var f={0,1}
var g={0,1}

# C,N,NE,E,SE,S,SW,W,NW,C'
0,0,0,a,b,c,d,e,0,0
0,0,1,a,b,c,d,e,0,1
0,1,0,a,b,c,d,e,0,1
0,1,1,a,b,c,d,e,0,1
0,0,0,a,b,c,d,e,1,0
0,0,1,a,b,c,d,e,1,1
0,1,0,a,b,c,d,e,1,1
0,1,1,a,b,c,d,e,1,0

And here's rule 124:

@RULE W124
@TABLE
n_states:2
neighborhood:Moore
symmetries:none

var a={0,1}
var b={0,1}
var c={0,1}
var d={0,1}
var e={0,1}
var f={0,1}
var g={0,1}

# C,N,NE,E,SE,S,SW,W,NW,C'
0,0,0,a,b,c,d,e,0,0
0,0,1,a,b,c,d,e,0,0
0,1,0,a,b,c,d,e,0,1
0,1,1,a,b,c,d,e,0,1
0,0,0,a,b,c,d,e,1,1
0,0,1,a,b,c,d,e,1,1
0,1,0,a,b,c,d,e,1,1
0,1,1,a,b,c,d,e,1,0