7
$\begingroup$

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

enter image description here

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$:

enter image description here

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$:

enter image description here

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}$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.