Is it a known result that the Collatz Tree repeats on itself indefinitely?

192 Views Asked by At

With reference to my visual pattern of the Collatz problem, I recognize that the Collatz tree for numbers of the form $6x-1$ (for $x\in\mathbb{Z}$ & $x>0$) and $1-6x$ (for $x\in\mathbb{Z}$ & $x\leq0$) has layers (a known fact) but also that the first layer alone repeats on itself indefinitely. My question is whether the repetition of the first layer on itself is a known result and what would be it's implication. My research has come up empty-handed.
Details.
The binary tree below shows the first layer up to depth 4 and its repetitive nature. Notice we would have infinite subtrees with root 0 should we extend the tree indefinitely.

enter image description here

What do I mean by ‘layer’? Each number, x, has two children on each layer given by the formulas below where $n\in\mathbb{N}$ and $n=1$ produces children on the first layer, $n = 2$ produces children on the second layer, and so on.

enter image description here

To make my post brief, I have omitted a proof of my claim. However, if a proof is needed, I can supply it upon request. My thinking is that this may be a known fact due to the trivial 1,4,2,1 cycle, but I have not come across any Collatz tree with this repetitive nature.

1

There are 1 best solutions below

2
On BEST ANSWER

This is actually a necessary consequence of the function you describe always mapping 2 to 1.

Given any function $f:\mathbb{Z}\rightarrow\mathbb{Z}$, such that $f(0)=0$ and $\#f^{-1}(n) = 2$ for each $n$. Then we can describe 2 functions $g$ and $h$ where $g<h$ and $\{g(n), h(n)\} = f^{-1}(n)$.

In this way the sequence of finite sequences described as $X_0 = (0)$ and $$X_{n+1} = \big(g(X_n[0]), h(X_n[0]), g(X_n[1]), h(X_n[1]), \ldots, g(X_n[2^n-1]), h(X_n[2^n-1])\big).$$ This is exactly what you defined in your graph, but without the edges.

We can also see that finite sequence $X_{n+1}$ contain a copy of $X_n$. You can prove this by induction. The basestep consists of recognizing that $X_1 = \big(g(0), h(0)\big)$. Because $0$ is an element of the pre-image of $f$ either $g(0)$ or $h(0)$ must equal $0$. So $X_1$ contains the sequence $(0)$.

The induction step goes as follows. Let the statement hold for $X_n$ meaning that $X_n$ contains a subsequence equal to $X_{n-1}$ without loss of generality say the first half. Then the first half of $X_{n+1}$ is defined as $$\big(g(X_n[0]), h(X_n[0]), g(X_n[1]), h(X_n[1]), \ldots, g(X_n[2^{n-1}-1]), h(X_n[2^{n-1}-1])\big),$$ but we assumed that $X_n$ was equal to $X_{n-1}$ on the first half of its terms so this is equal to $$\big(g(X_{n-1}[0]), h(X_{n-1}[0]), g(X_{n-1}[1]), h(X_{n-1}[1]), \ldots, g(X_{n-1}[2^{n-1}-1]), h(X_{n-1}[2^{n-1}-1])\big).$$ This by definition is the sequence $X_n$ concluding the induction step.

So the pattern you discovered is indeed real, and much stronger even as every layer repeats infinitely many times!