11
$\begingroup$

Background: Here's a crash course on the Collatz Conjecture. Basically, you take a number and if it is even you divide it by two. If a number is odd, you multiply it by three and then add one. You keep doing this until the number becomes 1. The conjecture says that performing this operation for any number eventually results in 1. A quick note on the numbers used, they must be positive non-zero integers. As pointed out by Gottfried, there are contradictions otherwise. Stating the above in mathematical form,

$$n_{t+1} = \begin{cases} n_t/2, & \text{if $n_t$ is even} \\ 3 \cdot n_t+1, & \text{if $n_t$ is odd} \end{cases}$$

What I found: Here's what was kind of surprising to me. If you perform $3 \cdot x+1$, where $x$ is odd, then you will always get an even number. However, ${x \over 2}$ doesn't always result in an odd number, if $x$ is even. My assumption is this, if one could figure out how many times you have to divide an even number by two to get an odd number, headway could be made in proving the conjecture. However, when I went to find $v_2(e)$, where $e$ is an even number, and $v_2(e)$ is the number of times you can divide the number by 2, I discovered a fractal like pattern! If you plot the values of this function, you get,

$$1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,\ldots$$

The first value is $v_2(2)$. The second is $v_2(4)$, and so on. The sequence corresponds to sequence A001511.

If you define an L-system with,

$$C_n \rightarrow C_n (+)^{n-1} P (-)^{n-1} C_n$$

Where $P$ is a plot move right command, $+$ is a move up command, $-$ is a move down command, and $C_n$ is the string. The up/down commands just add/substract from a counter. The plot command will actually plot the value, and move the independent variable up one. The values of $v_2(e)$ can be extracted from $C_n$ by "reading" $C_n$ left to right and adding $1$. The exponents, denote moving up/down $n-1$ times. Graphically, we have,

The graph

Questions: Since this function $v_2(e)$ has a self-similar (fractal-like) nature, does that mean that the Collatz Problem is related to fractals? Could this be used to study the problem? Since fractals are inherently complex to compute in a linear fashion, could this explain why the conjecture is so hard to prove? I believe it explains some of the complex behavior of the iterates under the Collatz system.

Addendum:

Given an odd number, the next odd number in the Collatz iteration is given by,

$$(1) \quad o_{t+1}={{3 \cdot o_t+1} \over {2^{v_2(3 \cdot o_t+1)}}}$$

Since any even number fed into the iteration is reduced to an odd number under the iteration, we need only consider odd numbers. Therefore, the Collatz conjecture is equivalent to the conjecture that the Dynamical System $(1)$ has one and only one fixed point and that this fixed point is $1$ and attractive. In addition, the basin of attraction for this fixed point is the entire set of positive odd numbers. Now we can finally see relevance of the self-similarity of $v_2(o_n)$. Its highly complex behavior results in unusually a complex behavior for the Dynamical System.

$\endgroup$
  • $\begingroup$ Can you say a little bit more on why you think that $M(e)$ defines a fractal? Hm, now it says "fractal like" and I'm not sure what that would mean exactly... $\endgroup$ – Stefan Mesken Sep 18 '15 at 15:51
  • $\begingroup$ The standard notation for $M(x)$ is $\upsilon_2(x)$ (see e.g. LTE paper). $\endgroup$ – user236182 Sep 18 '15 at 15:51
  • $\begingroup$ Here's a little more information about what you're calling $M(e)$: oeis/A001511 $\endgroup$ – Dr Xorile Sep 18 '15 at 15:57
  • $\begingroup$ @Stefan There's multiple ways to explain it. I used the formalism of L-Systems. $\endgroup$ – Zach466920 Sep 18 '15 at 15:58
  • 1
    $\begingroup$ @Nicco Yep, I think if one could find the cumulative average of $v_2(x)$ one could prove something very interesting. The scattering of large values could be why $n_t/2$ is applied more often than $3 \cdot n_t+1$. $\endgroup$ – Zach466920 Sep 18 '15 at 16:55
6
$\begingroup$

I think -although the problem has some "fractal" or "self-similar" structure- there is (at least) one more aspect to be looked at.

Consider the related problem where you insert "$3x-1$" for "$3x+1$" . (This is also simply looking at the negative integers in the original Collatz problem).
You'll have a very similar structure, again "fractal" looking. But now you'll have (at least) 3 cycles.

So we must introduce one more property which allows us to distinguish between a "1 existent cycle" fractal (with the $3x+1$) and a "3 different cycles exist" fractal (with the $3x-1$) problem.



What I think helps here is, to look at the inverse iteration.

For the original Collatz-problem this means: starting from $x_0=1$ we can construct all positive numbers by the iterative rule $$ x_{k+1,m} = {x_k \cdot 2^m - 1 \over 3} \text{for all $m$ where this is possible} $$ (only roughly defined) so $x_0=1$ defines somehow a root from where a stem, infinitely many twigs and leaves can be constructed - and with their rises and falls reach all positive numbers.

But for the $3x-1$-problem (the Collatz on the negative integers) this means: we need 3 roots, and each of the $3$ roots constructs its own specific tree with its own infinite sets of twigs and leaves - with their own risings and falls, but not overlapping and all 3 trees are needed to cover/construct all negative (in the Collatz-problem) numbers!


After that, the question of L. Collatz might be specified: "is it true, that on the positive numbers one root is sufficient, while on the negative numbers we need $3$ roots (even partially organized in cycles) to construct all (negative) numbers?"

So the "fractality" alone does not suffice; we need also an explanation for the question why the the set of positive numbers needs only one root and not -for instance- three as in the $3x-1$ problem.

$\endgroup$
  • $\begingroup$ What allows $1$ to be any more of a root than $2$ or $4$? How shall we decide which number of a cycle may be considered the root? $\endgroup$ – bitconfused Dec 26 '18 at 6:21
  • $\begingroup$ I use the "odds-only" version of the Collatz-problem, also known under the name "syracuse-problem". All my analyses are based on this "odd-only" concept. If you like to make the even values also explicite, then you are right - $2$ and $4$ have the same status as $1$, accepted. But since now there is a set of three numbers deserving a name, so I won't say "root" (which for me alludes to a single entity) but perhaps rather a "nest" (from which the birds start to fly in the morning) or perhaps a "corona" - a name introduced by some other Collatz-analytician.-Or something even more illustrative? $\endgroup$ – Gottfried Helms Dec 26 '18 at 10:38
3
$\begingroup$

As has been noted in the comments, this is called the $2$-adic valuation of $n$ and is noted as $v_2(n)$. In particular, if we take some $n<2^k$ we can notice the identity: $$v_2(n)=v_2(2^k-n)=v_2(2n)-1$$ which basically tells us that the function, in the interval $(0,2^{k+1})$ is composed of two copies of itself scaled by half on the $x$-axis and translated $1$ down (one of the copies gets reflected according to the above identity, but the reflection is along a symmetry of the function). Along with the fact that $v_2(2^k)=k$ this defines the function, as well as explains its fractal nature.

Something which you've not noted, but which is also true, is that if we consider the map $$f(x)=\begin{cases}\frac{3x+1}2&&\text{if }x \text{ is odd}\\ \frac{x}2 &&\text{if }x \text{ is even}\end{cases}$$ which is often how the Collatz conjecture is expressed*, then we can get sequences of odd numbers. In fact, noting that $$\frac{3x+1}2=\frac{3}2(x-1)+1$$ we find that iterating that function $n$ times starting from $x$ gives $\left(\frac{3}2\right)^n(x-1)+1$ so the number of times we hit odd numbers is $v_2(x-1)$ under this definition. It should be noted that using both "shortcuts" to define: $$\hat f(x)=\begin{cases}\left(\frac{3}2\right)^{v_2(x-1)}(x-1)+1&&\text{if }x \text{ is odd}\\\frac{x}{2^{v_2(x)}}&&\text{if }x\text{ is even}\end{cases}$$ then it is a result of Simon and De Weger that this map has no cycles of length $2\times 68$ or less (over the positive integers).

I would suggest that the appearance of the 2-adic valuation does not suggest a fractal nature to the problem itself except than to express the fact that the problem relates, somehow to factoring, where such structures naturally arise. Really, what may worry us is the appearance of both $v_2(x)$ and $v_2(x-1)$. This suggests that we care about the factorization both of $x$ and $x-1$ (but the relationship of these factorizations is not well understood). It also suggests a sensitivity to initial conditions - under the first $f$ I gave, we see that if $n$ will be halved many times before hitting an odd number, then $n+1$ will be increased many times before hitting an even number - so the best and worst cases are right next to each other.

(*A prime reason why this is a favored expression is that if we choose some $k$ and some sequence of parities (even/odd), then the portion of positive numbers $n$ such that $n,\,f(n),f^2(n),\,\ldots,\,f^{k-1}(n)$ matches that sequence of parities is asymptotically $\frac{1}{2^n}$. In particular, we can thus imagine that we randomly choose to multiply by $\frac{3}2$ or $\frac{1}2$ at each step - which would tell $f$ should be making things smaller when applied many times.)

$\endgroup$
  • $\begingroup$ Didn't know that you could do it that way. Of course, now that I think about it, it makes sense it could be done that way. However, I'm still inclined to believe fractals are underpinning this problem, even if said fractal is really coming from factorization nightmares. Even if I'm wrong, you'd be forced to admit that the system is at least Chaotic ;) as $x$ factors very differently from $x+1$, yet they are as close as you get, as far as initial conditions go. $\endgroup$ – Zach466920 Sep 18 '15 at 20:14
  • $\begingroup$ I see now that $\hat f(x)$ is a nice, concise definition for the 1-cycle-problem, and then for the m-cycle; your additionally explanations helped - thanks. It needed of course a certain time to translate it into my own logic.... $\endgroup$ – Gottfried Helms Sep 18 '15 at 22:38
1
$\begingroup$

I don't know if this answers your question, but it sure is fascinating. The Collatz function has been analytically extended to the complex numbers, and the plot of which points on the complex plane converge and which don't after successive iterations of the extended function (the same technique was famously used on the Mandelbrot set) forms a fractal, and a particularly beautiful one at that. Here are some pictures from the fractal made from the "shortcut" function pointed out by Milo Brandt, which is defined as

$$f(x)=\begin{cases}\frac{3x+1}2&&\text{if }x \text{ is odd}\\ \frac{x}2 &&\text{if }x \text{ is even}\end{cases}$$

extended to the complex numbers as

$$ f(z) = \frac{1}{4} (1 + 4z - (1 + 2z) cos (\pi z)) $$

Centered at the origin with a radius of 3: enter image description here

Centered at 5+0i with a radius of 5: enter image description here

An excellent description of how the function was extended can be found here: http://yozh.org/2012/01/12/the_collatz_fractal/ .

As a side note, there's a substantial cluster of convergent points around $e+0i$. I have no idea why.

$\endgroup$
  • 1
    $\begingroup$ re: your side note. Perhaps z=e+0i is important in understanding the difference in factorizations of successive positive integers... $\endgroup$ – frogfanitw Dec 8 '17 at 19:46
  • 1
    $\begingroup$ It seems to be important to just about everything else, so I don't doubt it. $\endgroup$ – Isaac Saffold Dec 8 '17 at 21:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.