Almost all Collatz orbits attain almost bounded values

10 September, 2019 in math.DS, math.NT, math.PR, paper | Tags: Collatz conjecture, renewal process

I’ve just uploaded to the arXiv my paper “Almost all Collatz orbits attain almost bounded values“, submitted to the proceedings of the Forum of Mathematics, Pi. In this paper I returned to the topic of the notorious Collatz conjecture (also known as the ${3x+1}$ conjecture), which I previously discussed in this blog post. This conjecture can be phrased as follows. Let ${{\bf N}+1 = \{1,2,\dots\}}$ denote the positive integers (with ${{\bf N} =\{0,1,2,\dots\}}$ the natural numbers), and let ${\mathrm{Col}: {\bf N}+1 \rightarrow {\bf N}+1}$ be the map defined by setting ${\mathrm{Col}(N)}$ equal to ${3N+1}$ when ${N}$ is odd and ${N/2}$ when ${N}$ is even. Let ${\mathrm{Col}_{\min}(N) := \inf_{n \in {\bf N}} \mathrm{Col}^n(N)}$ be the minimal element of the Collatz orbit ${N, \mathrm{Col}(N), \mathrm{Col}^2(N),\dots}$ . Then we have

Conjecture 1 (Collatz conjecture) One has ${\mathrm{Col}_{\min}(N)=1}$ for all ${N \in {\bf N}+1}$ .

Establishing the conjecture for all ${N}$ remains out of reach of current techniques (for instance, as discussed in the previous blog post, it is basically at least as difficult as Baker’s theorem, all known proofs of which are quite difficult). However, the situation is more promising if one is willing to settle for results which only hold for “most” ${N}$ in some sense. For instance, it is a result of Krasikov and Lagarias that

$\displaystyle \{ N \leq x: \mathrm{Col}_{\min}(N) = 1 \} \gg x^{0.84}$

for all sufficiently large ${x}$ . In another direction, it was shown by Terras that for almost all ${N}$ (in the sense of natural density), one has ${\mathrm{Col}_{\min}(N) < N}$ . This was then improved by Allouche to ${\mathrm{Col}_{\min}(N) < N^\theta}$ for almost all ${N}$ and any fixed ${\theta > 0.869}$ , and extended later by Korec to cover all ${\theta > \frac{\log 3}{\log 4} \approx 0.7924}$ . In this paper we obtain the following further improvement (at the cost of weakening natural density to logarithmic density):

Theorem 2 Let ${f: {\bf N}+1 \rightarrow {\bf R}}$ be any function with ${\lim_{N \rightarrow \infty} f(N) = +\infty}$ . Then we have ${\mathrm{Col}_{\min}(N) < f(N)}$ for almost all ${N}$ (in the sense of logarithmic density).

Thus for instance one has ${\mathrm{Col}_{\min}(N) < \log\log\log\log N}$ for almost all ${N}$ (in the sense of logarithmic density).
The difficulty here is one usually only expects to establish “local-in-time” results that control the evolution ${\mathrm{Col}^n(N)}$ for times ${n}$ that only get as large as a small multiple ${c \log N}$ of ${\log N}$ ; the aforementioned results of Terras, Allouche, and Korec, for instance, are of this type. However, to get ${\mathrm{Col}^n(N)}$ all the way down to ${f(N)}$ one needs something more like an “(almost) global-in-time” result, where the evolution remains under control for so long that the orbit has nearly reached the bounded state ${N=O(1)}$ .
However, as observed by Bourgain in the context of nonlinear Schrödinger equations, one can iterate “almost sure local wellposedness” type results (which give local control for almost all initial data from a given distribution) into “almost sure (almost) global wellposedness” type results if one is fortunate enough to draw one’s data from an invariant measure for the dynamics. To illustrate the idea, let us take Korec’s aforementioned result that if ${\theta > \frac{\log 3}{\log 4}}$ one picks at random an integer ${N}$ from a large interval ${[1,x]}$ , then in most cases, the orbit of ${N}$ will eventually move into the interval ${[1,x^{\theta}]}$ . Similarly, if one picks an integer ${M}$ at random from ${[1,x^\theta]}$ , then in most cases, the orbit of ${M}$ will eventually move into ${[1,x^{\theta^2}]}$ . It is then tempting to concatenate the two statements and conclude that for most ${N}$ in ${[1,x]}$ , the orbit will eventually move ${[1,x^{\theta^2}]}$ . Unfortunately, this argument does not quite work, because by the time the orbit from a randomly drawn ${N \in [1,x]}$ reaches ${[1,x^\theta]}$ , the distribution of the final value is unlikely to be close to being uniformly distributed on ${[1,x^\theta]}$ , and in particular could potentially concentrate almost entirely in the exceptional set of ${M \in [1,x^\theta]}$ that do not make it into ${[1,x^{\theta^2}]}$ . The point here is the uniform measure on ${[1,x]}$ is not transported by Collatz dynamics to anything resembling the uniform measure on ${[1,x^\theta]}$ .
So, one now needs to locate a measure which has better invariance properties under the Collatz dynamics. It turns out to be technically convenient to work with a standard acceleration of the Collatz map known as the Syracuse map ${\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1}$ , defined on the odd numbers ${2{\bf N}+1 = \{1,3,5,\dots\}}$ by setting ${\mathrm{Syr}(N) = (3N+1)/2^a}$ , where ${2^a}$ is the largest power of ${2}$ that divides ${3N+1}$ . (The advantage of using the Syracuse map over the Collatz map is that it performs precisely one multiplication of ${3}$ at each iteration step, which makes the map better behaved when performing “ ${3}$ -adic” analysis.)
When viewed ${3}$ -adically, we soon see that iterations of the Syracuse map become somewhat irregular. Most obviously, ${\mathrm{Syr}(N)}$ is never divisible by ${3}$ . A little less obviously, ${\mathrm{Syr}(N)}$ is twice as likely to equal ${2}$ mod ${3}$ as it is to equal ${1}$ mod ${3}$ . This is because for a randomly chosen odd ${\mathbf{N}}$ , the number of times ${\mathbf{a}}$ that ${2}$ divides ${3\mathbf{N}+1}$ can be seen to have a geometric distribution of mean ${2}$ – it equals any given value ${a \in{\bf N}+1}$ with probability ${2^{-a}}$ . Such a geometric random variable is twice as likely to be odd as to be even, which is what gives the above irregularity. There are similar irregularities modulo higher powers of ${3}$ . For instance, one can compute that for large random odd ${\mathbf{N}}$ , ${\mathrm{Syr}^2(\mathbf{N}) \hbox{ mod } 9}$ will take the residue classes ${0,1,2,3,4,5,6,7,8 \hbox{ mod } 9}$ with probabilities

$\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}$

respectively. More generally, for any ${n}$ , ${\mathrm{Syr}^n(N) \hbox{ mod } 3^n}$ will be distributed according to the law of a random variable ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ on ${{\bf Z}/3^n{\bf Z}}$ that we call a Syracuse random variable, and can be described explicitly as

$\displaystyle \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) = 2^{-\mathbf{a}_1} + 3^1 2^{-\mathbf{a}_1-\mathbf{a}_2} + \dots + 3^{n-1} 2^{-\mathbf{a}_1-\dots-\mathbf{a}_n} \hbox{ mod } 3^n, \ \ \ \ \ (1)$

where ${\mathbf{a}_1,\dots,\mathbf{a}_n}$ are iid copies of a geometric random variable of mean ${2}$ .
In view of this, any proposed “invariant” (or approximately invariant) measure (or family of measures) for the Syracuse dynamics should take this ${3}$ -adic irregularity of distribution into account. It turns out that one can use the Syracuse random variables ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ to construct such a measure, but only if these random variables stabilise in the limit ${n \rightarrow \infty}$ in a certain total variation sense. More precisely, in the paper we establish the estimate

$\displaystyle \sum_{Y \in {\bf Z}/3^n{\bf Z}} | \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^n{\bf Z})=Y) - 3^{m-n} \mathbb{P}( \mathbf{Syrac}({\bf Z}/3^m{\bf Z})=Y \hbox{ mod } 3^m)| \ \ \ \ \ (2)$

$\displaystyle \ll_A m^{-A}$

for any ${1 \leq m \leq n}$ and any ${A > 0}$ . This type of stabilisation is plausible from entropy heuristics – the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ of geometric random variables that generates ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ has Shannon entropy ${n \log 4}$ , which is significantly larger than the total entropy ${n \log 3}$ of the uniform distribution on ${{\bf Z}/3^n{\bf Z}}$ , so we expect a lot of “mixing” and “collision” to occur when converting the tuple ${(\mathbf{a}_1,\dots,\mathbf{a}_n)}$ to ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ ; these heuristics can be supported by numerics (which I was able to work out up to about ${n=10}$ before running into memory and CPU issues), but it turns out to be surprisingly delicate to make this precise.
A first hint of how to proceed comes from the elementary number theory observation (easily proven by induction) that the rational numbers

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{n-1} 2^{-a_1-\dots-a_n}$

are all distinct as ${(a_1,\dots,a_n)}$ vary over tuples in ${({\bf N}+1)^n}$ . Unfortunately, the process of reducing mod ${3^n}$ creates a lot of collisions (as must happen from the pigeonhole principle); however, by a simple “Lefschetz principle” type argument one can at least show that the reductions

$\displaystyle 2^{-a_1} + 3^1 2^{-a_1-a_2} + \dots + 3^{m-1} 2^{-a_1-\dots-a_m} \hbox{ mod } 3^n \ \ \ \ \ (3)$

are mostly distinct for “typical” ${a_1,\dots,a_m}$ (as drawn using the geometric distribution) as long as ${m}$ is a bit smaller than ${\frac{\log 3}{\log 4} n}$ (basically because the rational number appearing in (3) then typically takes a form like ${M/2^{2m}}$ with ${M}$ an integer between ${0}$ and ${3^n}$ ). This analysis of the component (3) of (1) is already enough to get quite a bit of spreading on ${ \mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ (roughly speaking, when the argument is optimised, it shows that this random variable cannot concentrate in any subset of ${{\bf Z}/3^n{\bf Z}}$ of density less than ${n^{-C}}$ for some large absolute constant ${C>0}$ ). To get from this to a stabilisation property (2) we have to exploit the mixing effects of the remaining portion of (1) that does not come from (3). After some standard Fourier-analytic manipulations, matters then boil down to obtaining non-trivial decay of the characteristic function of ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ , and more precisely in showing that

$\displaystyle \mathbb{E} e^{-2\pi i \xi \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) / 3^n} \ll_A n^{-A} \ \ \ \ \ (4)$

for any ${A > 0}$ and any ${\xi \in {\bf Z}/3^n{\bf Z}}$ that is not divisible by ${3}$ .
If the random variable (1) was the sum of independent terms, one could express this characteristic function as something like a Riesz product, which would be straightforward to estimate well. Unfortunately, the terms in (1) are loosely coupled together, and so the characteristic factor does not immediately factor into a Riesz product. However, if one groups adjacent terms in (1) together, one can rewrite it (assuming ${n}$ is even for sake of discussion) as

$\displaystyle (2^{\mathbf{a}_2} + 3) 2^{-\mathbf{b}_1} + (2^{\mathbf{a}_4}+3) 3^2 2^{-\mathbf{b}_1-\mathbf{b}_2} + \dots$

$\displaystyle + (2^{\mathbf{a}_n}+3) 3^{n-2} 2^{-\mathbf{b}_1-\dots-\mathbf{b}_{n/2}} \hbox{ mod } 3^n$

where ${\mathbf{b}_j := \mathbf{a}_{2j-1} + \mathbf{a}_{2j}}$ . The point here is that after conditioning on the ${\mathbf{b}_1,\dots,\mathbf{b}_{n/2}}$ to be fixed, the random variables ${\mathbf{a}_2, \mathbf{a}_4,\dots,\mathbf{a}_n}$ remain independent (though the distribution of each ${\mathbf{a}_{2j}}$ depends on the value that we conditioned ${\mathbf{b}_j}$ to), and so the above expression is a conditional sum of independent random variables. This lets one express the characeteristic function of (1) as an averaged Riesz product. One can use this to establish the bound (4) as long as one can show that the expression

$\displaystyle \frac{\xi 3^{2j-2} (2^{-\mathbf{b}_1-\dots-\mathbf{b}_j+1} \mod 3^n)}{3^n}$

is not close to an integer for a moderately large number ( ${\gg A \log n}$ , to be precise) of indices ${j = 1,\dots,n/2}$ . (Actually, for technical reasons we have to also restrict to those ${j}$ for which ${\mathbf{b}_j=3}$ , but let us ignore this detail here.) To put it another way, if we let ${B}$ denote the set of pairs ${(j,l)}$ for which

$\displaystyle \frac{\xi 3^{2j-2} (2^{-l+1} \mod 3^n)}{3^n} \in [-\varepsilon,\varepsilon] + {\bf Z},$

we have to show that (with overwhelming probability) the random walk

$\displaystyle (1,\mathbf{b}_1), (2, \mathbf{b}_1 + \mathbf{b}_2), \dots, (n/2, \mathbf{b}_1+\dots+\mathbf{b}_{n/2})$

(which we view as a two-dimensional renewal process) contains at least a few points lying outside of ${B}$ .
A little bit of elementary number theory and combinatorics allows one to describe the set ${B}$ as the union of “triangles” with a certain non-zero separation between them. If the triangles were all fairly small, then one expects the renewal process to visit at least one point outside of ${B}$ after passing through any given such triangle, and it then becomes relatively easy to then show that the renewal process usually has the required number of points outside of ${B}$ . The most difficult case is when the renewal process passes through a particularly large triangle in ${B}$ . However, it turns out that large triangles enjoy particularly good separation properties, and in particular afer passing through a large triangle one is likely to only encounter nothing but small triangles for a while. After making these heuristics more precise, one is finally able to get enough points on the renewal process outside of ${B}$ that one can finish the proof of (4), and thus Theorem 2.

414 comments

Comments feed for this article

27 February, 2020 at 3:43 am

Barry Hirschfeld

Folks, I’m leaving you and starting my own website. I thank all those who helped me, whether with thumbs down or actual comments, whether I agreed with you or not; I wish you all the best.

One final note. In my post of 23 Feb., in the last part (PART 5), i showed that if there is one CS that goes to infinity then there are an infinite number, and that for each step the sequence (or orbit) takes toward infinity it adds yet another infinity of integers that go toward infinity.
Yesterday I looked at the very start of this website. There, Prof. Tao says “Almost all Collatz orbits attain almost bounded values”.
This theorem of his negates the possibility of what I showed above.
That is, NO integer in a CS can go to infinity.

Good bye and good luck.

27 February, 2020 at 3:48 pm

Alexandre

Dear Terence Tao,

Maybe I have missed something, but on Lemma 7.1:

1. “the event a1 + a2 = 2” should be “the event a1 + a2 = 3”

2. each pair has probability 1/8 rather than 1/2.

Best

[Thanks, this will be corrected in the next revision of the ms. For 2., the probability here is conditional rather than absolute. -T]

28 February, 2020 at 9:40 am

Alexandre

Continuing…

I am trying to follow your Lemma 4.1.

3. I suppose you are considering $\mathbf{a}_{[1,0]} =0$ and “ $\ll$ ” stands for “much smaller than”.

4. You have to show that $\sum_{k=0}^{n-1} q_k \ll 2^{-cn}$ , where $q_k = \mathbb{P}(\mathbf{a}_{[1,k]} < m \leq \mathbf{a}_{[1,k+1]})$ for $k=0,\ldots,n-1$ .

Observe that $\sum_{k=0}^{n-1} q_k \leq n \max_{0 \leq k \leq n-1} q_k$ . Therefore,

4.1 " $q_k \ll n^{-1}2^{-cn}$ for each $k=0,\ldots, n-1$ " if, and only if,

4.2 " $\max_{0 \leq k \leq n-1} q_k \ll n^{-1}2^{-cn}$ " which implies

4.3 $\sum_{k=0}^{n-1} q_k \ll 2^{-cn}$ .

Maybe there is a key property I have missed, but as far as I can see it is not sufficient to show that $q_k \ll 2^{-cn}$ for each $0 \leq k \leq n-1$ . If $c \approx 0$ , then $n$ must be a huge number for $n2^{-cn}$ to be very small. Remember that You also consider that $n$ is much smaller than $\log N$ .

Best regards,
A Patriota.

28 February, 2020 at 1:27 pm

Terence Tao

Yes, using the conventions of the paper one has $a_{[1,0]}=0$ . The notation $\ll$ (Vinogradov notation) is explained in the first paragraph of Section 2; it does not mean “much smaller than”, but rather “bounded by a constant multiple of”.

28 February, 2020 at 2:23 pm

Alexandre

Thanks. I’ve realized that right after posting and I couldn’t edit it. You’re right, in fact the probability is 1/2 after conditioning on $\mathbf{a}_1 + \mathbf{a}_2 = 3$ . Thanks again.

However, steps 4.1 – 4.3 above seem to be valid for the “bounded by a constant multiple of” definition. You have to deal with n terms $q_0,\ldots,q_{n-1}$ where some of them depend on n, don’ t you?

Sorry to take your time on these small things. I need to understand Lemma 4.1 and Proposition 1.9 because they will be helpful for my own work.

4 March, 2020 at 8:47 am

Terence Tao

A bound of the form $q_k \ll 2^{-cn}$ implies the apparently stronger bound $q_k \ll n^{-1} 2^{-c' n}$ as long as the new constant $c'$ is smaller than the original constant $c$ , because the sequence $2^{-cn} / (n^{-1} 2^{-c' n}) = n 2^{-(c-c') n}$ is uniformly bounded in $n$ . So the (lower order) polynomial factor $n^{-1}$ can be obtained “for free” by slightly weakening the (higher order) exponential factor $2^{-cn}$ .

6 March, 2020 at 2:24 pm

Alexandre

I got it:

“recall we allow c to vary even within the same line”

Thanks

6 March, 2020 at 3:37 pm

Alexandre

Some more small typos I came across so far:

1. Formula (6.2) $\mathbf{a}_{[i+i, j]}$ should be $\mathbf{a}_{[i, j]}$

2. Formula (7.29) $j=\mathbb{N}$ should be $j \in \mathbb{N}$

I am still reading your paper and trying to get in the proofs as much as I can. Number theory is not my field of expertise, but I am very interested because of the probabilistic results.

I am having some insights from it. I noted there is a way to get more information from the properties of the Syracuse random variables.

thanks a lot.

A. Patriota

[Thanks, these corrections will be appear in the next revision of the ms – T.]

7 March, 2020 at 12:25 pm

Alexandre

3. in Formula (5.3), I guess it should be $\mathbb{P}(|Geom(2)^{n_0}| \leq 1.9 n_0)$ rather than $\mathbb{P}(|Geom(2)^{n}| \leq 1.9 n_0)$ .

It seems you could’ve taken the value $(2-\epsilon)$ , for any $0<\epsilon < 2$ , instead of 1.9. I know it is not relevant for that argument in your manuscript, but it will be important for me. If you'd like to see why, I can send you in private.

A. Patriota.

[Thanks, this will be corrected in the next revision of the ms. Yes, for my argument the 1.9 could have been replaced by any constant $2-\varepsilon$ with $\varepsilon > 0$ and $2^{2-\varepsilon} > 3$ ; the 1.9 is chosen purely for sake of concreteness. -T]

15 March, 2020 at 9:56 am

Alexandre

3. On the bottom of pg 18: “This constrains $\mathbf{N}$ to a single odd residue class module $2^{|\vec{a}|+1}$ “. Please verify if it should be $2^{|\vec{a}|}$ instead of $2^{|\vec{a}|+1}$ . Thanks.

A. Patriota

[I believe the text is correct as it stands – T.]

2 March, 2020 at 9:33 am

Student

Terence Tao,I hope you will answer me. Riho Terras (1979), On the existence of a density, Acta Arithmetica 35 (1979), 101–102. (MR 80h:10066).

This paper supplies additional details concerning the proof in Terras (1976) that the set of integers having an infinite stopping time has asymptotic density zero. The proof in Terras (1976) had been criticized by Möller (1978). In a note added in proof the author asserts that the proofs of Terras (1976) are faulty.

What do you think about? in the interval $[1,n]$ Is the natural density of all possible counter-examples zero?

4 March, 2020 at 8:53 am

Terence Tao

Note that Terras’s definition of a “stopping time” is the first time in which the iterate drops below the initial value; it should not be confused with the first time in which the iterate attains the value 1. Certainly any number $n > 1$ that has an infinite stopping time will be a counterexample to Collatz, but the converse is not true; one can potentially imagine a counterexample to Collatz whose orbit initially drops below its starting value (thus leading to a finite stopping time), before going to infinity. (However, it is true, that if a counterexample to Collatz exists, then the smallest such counterexample will have infinite stopping time.)

Terras’s argument (as corrected in 1979) does indeed show that the natural density of numbers with infinite stopping time is zero; these results have been improved since by Allouche, Korec, and in my own paper. However, none of these results imply that the natural density of numbers that are counterexamples to Collatz (which is potentially a larger set) is also zero. I discuss this a bit further in Remark 1.4 of my own paper.

4 March, 2020 at 4:02 pm

lone student

Thank you for being kind and answering me. In the meantime, I apologize for the absence of the word “Mr” against your name. I’m new to WordPress. I could not edit the comment. I use it for the first time. Whether it is diverge to infinity or cyclic, any counterexample will have “infinity” stopping time. So every non-finite loop, which does not give result “1-4-2-1”, is actually infinite. And as you said, any counter example really will have a very large set. This is the conclusion I got from your answer:

Exact Question: In the interval [1,n] is the natural density of all possible counter-examples for the Collatz Conjecture, zero?

Exact Answer: NO.

Do you confirm my conclusion? Did I understand your answer correctly?

Thank you very much! And I am also sorry for English grammar.

9 March, 2020 at 12:35 pm

Anonymous

why discuss something if there is proving of a problem

14 March, 2020 at 9:25 am

Alberto Ibañez

Another dynamic equivalent to the Collatz conjecture.

$6x_{0}\rightarrow 6x_{k}$

where all $x_{0}=n \rightarrow ... \rightarrow x_{k-1}= 2 \rightarrow x_{k}=0$ ,

the 6 multiplicative table.

This dynamic is a kind Syracuse-map, but instead of being

$odd \rightarrow odd$

it is of the form

$x\equiv 4(mod6)\rightarrow x\equiv 4(mod6)$

$even\equiv 1(mod3)\rightarrow even\equiv 1(mod3)$

these numbers are of the form $4 + 6x$ and in recurrence we can do without constant 4 and the map is

$6x_{0} \rightarrow 6x_{1}$

the table of 6.

Some examples:

$10=4+6\times 1\rightarrow 16= 4+6\times 2\rightarrow 4= 4+6\times 0$

$64=4+6\times 10\rightarrow 16= 4+6\times 2\rightarrow 4= 4+6\times 0$

$22=4+6\times 3\rightarrow 34= 4+6\times 5\rightarrow 52=4+6\times 8\rightarrow 40=4+6\times 6\rightarrow 10=4+6\times 1\rightarrow 16= 4+6\times 2\rightarrow 4= 4+6\times 0$

This same reformulation is applicable to a $3n-1$ map, which would be $2 + 6x \rightarrow 2 + 6x$ , with a different dynamic, or to a $5n + 1$ map, which would be $6 + 10x \rightarrow 6 + 10x$ , the table of 10, although I have not delved into these dynamics so far.Nor do I know if these equivalent dynamics have already been studied or represent something new.

The dynamics work in the following way:

Direct map $n \rightarrow ... \rightarrow 1$ ,

in our case from

$x_{0}=n \rightarrow ... \rightarrow 2 \rightarrow 0$

$x_{0}\, odd \rightarrow x_{1} = \frac{3x_{0}+1}{2}$

$x_{0}\, even \rightarrow$

$\rightarrow x_{0}\equiv 0(mod4)4,8,12,16,... \rightarrow x_{1} = \frac{3x_{0}}{4}$

$\rightarrow x_{0}\equiv 0(mod2)2,6,10,14,... \rightarrow x_{1} = \frac{x_{0}-2}{4}$

Inverse map $1 \rightarrow ... \rightarrow n$ ,

in our case from

$0 \rightarrow 2 \rightarrow n$

Function 1 : $x_{0}\, odd\equiv 1(mod6) 1,7,13,19,... \rightarrow x_{1}= 4x_{0}+2$ generate (6,30,54,78,…)

$x_{0}\, odd\equiv 3(mod6)3,9,15,21,...\rightarrow$

Function 2 : $\rightarrow x_{1}= 4x_{0}+2$ generate (14,38,62,86,…)

Function 3 : $\rightarrow x_{1}= \frac{4x_{0}}{3}$ generate (4,12,20,28,36,44,…)

$x_{0}\, odd\equiv 5(mod6)5,11,17,23,...\rightarrow$

Function 4 : $\rightarrow x_{1}= 4x_{0}+2$ generate (22,46,70,94,…)

Function 5 : $\rightarrow x_{1}= \frac{2x_{0}-1}{3}$ generate (3,7,11,15,…)

$x_{0}\, even\equiv 0(mod6)0,6,12,18,...\rightarrow$

Function 6 : $\rightarrow x_{1}= 4x_{0}+2$ generate (2,26,50,78,…)

Function 7 : $\rightarrow x_{1}= \frac{4x_{0}}{3}$ generate (0,8,16,24,32,…)

$x_{0}\, even\equiv 2(mod6)2,8,14,20,...\rightarrow$

Function 8 : $\rightarrow x_{1}= 4x_{0}+2$ generate (10,34,58,82,…)

Function 9 : $\rightarrow x_{1}= \frac{2x_{0}-1}{3}$ generate (1,5,9,13,…)

Function 10 : $x_{0}\, even\equiv 4(mod6)4,10,16,22,...\rightarrow x_{1}= 4x_{0}+2$ generate (18,42,66,90,…)

Inverse map functions 5 and 9 generate odd numbers in apparent order, functions 1,2,3,4,6,7,8,10 generate even numbers, also in an orderly and uniform manner, which leads me to think that from $4 + 6 \times 0$ we can generate all $4 + 6 \times n$ and equivalently, that from 4 on the inverse map of Collatz all N can be generated, then all N would reach 4-2-1.

I certainly do not know if this dynamic represents a new way of attacking the problem, much less if it is appropriate or even simpler, although it does not seem so. In the absence of further study, I ask for your help and advice to know if you think it is an appropriate path or if some techniques can be applied, beyond my reach, a satisfactory result could be reached to rule out the existence of periodic orbits or unbounded orbits. Sincerely. Thank you.

*Please forgive me it latex fails

https://drive.google.com/file/d/1SJp1oYSKr6CtvTyd-Gufa3YahkV92_4G/view?usp=sharing

15 March, 2020 at 8:29 pm

Gottfried H

In the style of the syracuse-notation it is easy to see that it is a conjugacy: instead of $x_{k+1}= (3x_k+1)/2^A$ we have $y_{k+1}= (y_k/2^A)*3+1$

16 March, 2020 at 9:11 am

Alberto Ibañez

On unbounded orbits, those that escape to infinity.

On these orbits, in the study of the worst possible orbits, it seems that these have the shape of a $Col_{2}$ map $n\rightarrow \frac{3n+1}{2}= n+\frac{n+1}{2}$ , where for each odd step, there is a single even step, and the sequence works $Odd\rightarrow Odd$ .

Have we an answer to the fact that this process is repeated indefinitely for some n?
or is it known that for all n this process is not repeated indefinitely?

I don’t know if we have already the answer, but it seems that the answer could be yes, that for all n, the worst map $Col_{2}$ cannot be kept indefinitely and at some point, the number of even steps always increases by at least one more step than odd step every recursion cycle that results in an even number, and this increment accumulates. This means that when $k=odd steps$ , increases infinitely, the distance between $x=even steps$ , also increases infinitely $x-y \rightarrow \infty$ and would justify that $2^{x}\ll 3^{k}$ for the worst of the orbits, and that for the Collatz recursion of the form

$n\times \frac{3^{k}}{2^{x}}+\frac{3^{k-1}+3^{k-2}\times 2^{a1}+...+2^{k-1}}{2^{x}}$

ignoring at the moment $\frac{3^{k-1}+3^{k-2}\times 2^{a1}+...+2^{k-1}}{2^{x}}$ and the fact that it can enter periodic orbit,

$2^{x}\gg 3^{k}$ , and $\frac{3^{k}}{2^{x}}\ll 1$ and $n\times \frac {3^{k}}{2^{x}}< n$

For the study of the worst orbits we use the $Col_{2}$ map

$Odd\rightarrow Odd\rightarrow ...\rightarrow Even ?$

To find out if we always find an even number, for the worst orbit, over the set of odd numbers 3,5,7,9,11,13,15,17,… and the values for the worst possible orbit

$3^{k}-2^{k}= 3^{k-1}+3^{k-2}\times 2^{a1}+...+2^{k-1}$ , the Notable Product Difference Nth powers, and we will discard those numbers that give even solutions for the worst possible orbit.

For

$\frac {3n+1}{2}\rightarrow 3,7,11,15,19,...$ give odd solutions

$\frac {3^{2}n+ (3^{2}-2^{2})}{4}\rightarrow 7,15,23,31,...$ give odd solutions

$\frac {3^{3}n+ (3^{3}-2^{3})}{8}\rightarrow 15,31,47,63...$ give odd solutions

$\frac {3^{4}n+ (3^{4}-2^{4})}{16}\rightarrow 31,63,95,127...$ give odd solutions

…

This recursion is maintained indefinitely and although the solution sets are infinite, the cardinality of the set seems to decrease and it also seems to indicate that for all n there is a moment when the set of numbers in the recursions finds an even number, even after a very large number of iterations which is only divided once by 2, and the worst possible orbit is bounded for all n in each cycle

$Odd\rightarrow Odd\rightarrow...\rightarrow Even$

and the values of $x= even steps$ , is greater than $k = odd steps$ and

although the distance $x-k$ can grow very slowly

when $k \rightarrow \infty$ , $x-k \rightarrow \infty$

and would justify that

$\frac{3^{k}}{2^{x}}< 1$ and for

$n\times \frac{3^{k}}{2^{x}} 3^{k}$ and

$n\times \frac{3^{k}}{2^{x}}< n$ for all n?

Or less or equal if it reaches a multiple of n?

Sincerely, thank you.

https://drive.google.com/file/d/1CrtqDEWmqufcOE3LFS6UJMv1mn7VcFE0/view?usp=sharing

16 March, 2020 at 9:33 am

Alberto Ibañez

$Odd\rightarrow Odd\rightarrow...\rightarrow Even$

and the values of $x= even steps$ , is greater than $k = odd steps$
and although the distance $x-k$ can grow very slowly,

when $k \rightarrow \infty$ , $x-k \rightarrow \infty$

and would justify that $\frac{3^{k}}{2^{x}}< 1$ and for

$n\times \frac{3^{k}}{2^{x}} 3^{k}$ and $n\times \frac{3^{k}}{2^{x}}< n$ for all n?

Or less or equal if it reaches a multiple of n?

Sincerely, thank you.

16 March, 2020 at 9:48 am

Alberto Ibañez

**Third try

$Odd\rightarrow Odd\rightarrow...\rightarrow Even$

and the values of $x= even steps$ , is greater than $k = odd steps$

and although the distance $x-k$ can grow very slowly

when $k \rightarrow \infty$ , $x-k \rightarrow \infty$

and would justify that $\frac{3^{k}}{2^{x}}< 1$ and for

$n \times \frac{3^{k}}{2^{x}} 3^{k}$ and $n\times \frac{3^{k}}{2^{x}}< n$ for all n?

Or less or equal if it reaches a multiple of n?

Sincerely, thank you.

16 March, 2020 at 9:57 am

Alberto Ibañez

**So sorry

Is there an explicit way to calculate that for all n, in a $Col_{2}$ recursion for the worst possible orbit? we always find an even value? I do not know if there is already an answer to this question, and it is enough to justify the statement that all orbits are bounded, even so, it seems, according to my observations, that it could be of the form:

$n\rightarrow n+\frac{n+1}{2}= n+\frac{2^{x}\times y}{2}\rightarrow ...\rightarrow n+y\times (3^{x}-2^{x})= EVEN$

If this condition is true for all n, and all the worst $Col_{2}$ orbits are bounded, in the sense that they always find an even number, and almost is divided by 2 more than one time after a number of iterations $Odd\rightarrow Odd$

Is it sufficient to affirm that when $k \rightarrow \infty$ , $x-k \rightarrow \infty$ and $2^{x}> 3^{k}$ and $n\times \frac{3^{k}}{2^{x}}< n$ for all n?

Or less or equal if it reaches a multiple of n?

Sincerely, thank you.

16 March, 2020 at 8:32 pm

Anonymous

Is it possible to get more information on the Collatz iteration by defining also a notion of “entropy” for this map (as done e,g, in the recent solution of Erdos discrepancy problem) ?

4 April, 2020 at 7:11 pm

lz2263546927

Constructing Integer Ring Transformation：
1.
n,d∈Z
x=3n+d
y=3n-d
z=n/2
2.
①n∈Z+,d∈Z+ ②n=0,d=0 ③n∈Z-,d∈Z-

x=3n+d x=3×0+0 x=3n-d
⇆ ⇆
y=3n-d y=3×0-0 y=3n+d

z=n/2 z=0/2 z=n/2

(1)n∈Z+,d∈Z+
【1】(3×1+d1-1)/3=(3×1-d1)/2，
d1=1；
(3×1-d2-1)/3=(3×1+d2)/2，
d2=-1.
【2】(3×1-d3)/2=2(3×1+d 3)，
d3=9/5；
(3×1+d4)/2=2(3×1-d4)，
d4=-9/5.
【3】3(3×1-d5)+1=2(3×1+d5)，
d5=4/5；
3(3×1+d6)+1=2(3×1-d6)，
d6=-4/5.
If d=1, x2=4, y2=2, topological cycle A=(4, 2, 1, 4) can be obtained. according to the transformation rule, if topological fixed point n=1, x4=3×1+1=4, y4= 3×1-1=2, topological cycle S=(4, 2, 1, 4)=A can be obtained, so S is homeomorphic to A, so topological cycle (A, A) can be obtained, so A is a single connected domain, so 3n+1 transformation on positive integer rings has and only topological cycle A⇆A.

(2)n∈Z-,d∈Z-
〈1〉From (1), it can be seen that this transformation is equivalent to (1) when n=-1, so d=-1, x5=-2, y5=-4, the topological cycle B=(-1, -2, -1) can be obtained. Because of -4∉B, so n=-1 is not a topological fixed point and does not satisfy the transformation rule, so the topological fixed point n=-2 is taken.
〈2〉
【1】[3×(-2)-d7-1]/3=[3×(-2)+d7]/2,
d7=4/5；
[3×(-2)+d8-1]/3=[3×(-2)-d8]/2，
d8=-4/5.
【2】[3×(-2)-d9]/2=2[3×(-2)+d9]，
d9=18/5；
[3×(-2)+d10]/2=2[3×(-2)-d10]，
d10=-18/5.
【3】3[3×(-2)+d11]+1=2[3×(-2)-d11],
d11=1；
3[3×(-2)-d12]+1=2[3×(-2)+d12]，
d12=-1.
If d=-1, x6=-5, y6=-7, the topological cycle C=(-5, -14, -7, -20, -10, -5) can be obtained. According to the transformation rule, the topological fixed point n=-14 is taken.
〈3〉
【1】[3×(-14)-d13-1]/3=[3×(-14)+d13]/2,
d13=8；
[3×(-14)+d14-1]/3=[3×(-14)-d14]/2，
d14=-8.
【2】[3×(-14)-d15]/2=2[3×(-14)+d15],
d15=126/5；
[3×(-14)+d16]/2=2[3×(-14)-d16]，
d16=-126/5.
【3】3[3×(-14)+d17]+1=2×[3×(-14)-d17]，
d17=41/5；
3[3×(-14)-d18]+1=2[3×(-14)+d18]，
d18=-41/5.
If d=-8, x7=-34, y7=-50, the topological cycle D=(-34, -17, -50, -25, -74, -37, -110, -55, -164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34) can be obtained. According to the transformation rule, the topological fixed point n=-17 is taken.
〈4〉
【1】[3×(-17)-d19-1]/3=[3×(-17)+d19]/2，
d19=49/5；
[3×(-17)+d20-1]/3=[3×(-17)-d20]/2，
d20=-49/5.
【2】[3×(-17)-d21]/2=2[3×(-17)+d21]，
d21=153/5；
[3×(-17)+d22]/2=2[3×(-17)-d22]，
d22=-153/5.
【3】3[3×(-17)+d23]+1=2[3×(-17)-d23]，
d23=10；
3[3×(-17)-d24]+1=2[3×(-17)+d24]，
d24=-10.
If d=-10, then x8=-41, y8=-61, the topological cycle E=(-41, -122, -61, …, -41)=D can be obtained, so E is homeomorphic to D, so the topological cycle (D, D) can be obtained, so D is a simple connected domain, so B, C, D are homotopy, so 3n+1 transformation on negative integer rings has 3 topological cycles：(B⇆B)⇆(C⇆C)⇆(D⇆D)。
From the integer ring transformation, it can be seen that 3n+1 transformation on the whole ring has 5 topological cycles, where 0 is defined as an even number and 0⇆0 is a singular topological cycle, and there are：(A⇆A)⇆(0⇆0)⇆(B⇆B)⇆(C⇆C)⇆(D⇆D)。

5 April, 2020 at 8:17 am

Aran

Dear Mr. Tao and readers,

I have found a function that seems to measure the distance between any odd number to the even number with an identical “sequence”. By sequence I mean two properties:

– The number of arithmetic steps until the cycle 4,2,1 is reached is equal. Also called “height of n”.
– The series of numbers of the odd and even n have identical values. Also called “trajectory”.

Unfortunately, I am not even aware if this is something trivial, well known or new. A mentor advised me to contact Mr. Tao about this. It seems Mr. Tao has no capacity, which is why I am inclined to not write directly and in his forum instead.

With best regards.

19 April, 2020 at 6:42 am

Anonymous

It’s quite remarkable that the key insight for discrete dynamic eventually comes from the PDE world. Perhaps the other way round, e.g. hard PDE problems like Navier-Stocks can benefit from a reformulation in terms of discrete dynamics? It seems that that’s what Stephen Wolfram has been doing all along, e.g. deriving fluid equation from cellular automaton dymaics: https://www.stephenwolfram.com/publications/academic/cellular-automaton-fluids-theory.pdf His recent work go as far as to claim that basically all fundamental physics should follow from a discrete dynamics: https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ What’s your thoughts on this?

19 April, 2020 at 12:00 pm

Terence Tao

My thoughts on the analogy between fluid equations and cellular automata may be found at Section 1.3 of my paper https://arxiv.org/abs/1402.0290

19 April, 2020 at 10:44 am

Michael M. Ross

“A Poincaré map can be interpreted as a discrete dynamical system with a state space that is one dimension smaller than the original continuous dynamical system.” The CC is extremely amenable to simplification using a first recurrence map applied to the odd numbers.

19 April, 2020 at 6:31 pm

Fabien

There is a remarkable property in the collatz conjecture : It’s possible to group all numbers in a two coordinate system : the first is the number of time x3+1 has been used and the second the number of dividing by 2. If you draw that you get for each number a little group of number (logarithmic on Y axe) :

Now the fun part : if you animate all the number of a coordinate, let say for example the [3, 20] (so all the number obtained with 3 times 3x+1 and 20 times divide by 2) which have 40 numbers you get a sort of “enumeration” that look surprisingly like a “count system” :

I have the intuition that it’s “easy” to find a formula to that enumeration and that if we “sum” all the numbers in all coordinate we simply find the N ensemble. I do not have the mathematical background to do that but the idea is here I think.

Good luck for the first one who will win the run ! :)

19 April, 2020 at 10:50 pm

Fabien

With the 38656 between 38682 and 38720 it’s better (ordered by the number of the group is not always correctly showing the “counting system”) :

1 May, 2020 at 3:22 am

Maria

I guess what are the purple numbers on the bottom line, power of 2 of each column, but what’s the divider at the end, 27 ?

1 May, 2020 at 4:34 am

Fabien

Maria, it’s the global divider in the interesting (I find) Collatz equation form :

1 May, 2020 at 6:31 am

Maria

so 3^x with x the number of *3+1.
Nice general form of the equation.

30 April, 2020 at 5:57 am

Houdini

Interesting & original (& nice to see animated !) point of view, good to identify “groups” in the structure, but still I think it will not be as you think an “almost done job” with it and just a “little run” left to do…

1 May, 2020 at 1:49 am

Fabien

Thanks Houdini. But even if it’s true that I realise now that it’s not so simple, I still have the feeling that those group of numbers corresponding to [count of x3+1, count of dividing by 2] is a key to solve that problem (a simple solution, which makes it the One in The book for the Collatz problem ;) )

20 April, 2020 at 9:26 pm

Anonymous

Collatz conjecture would be discribable by something like representation theory. Actually, there is permutation group of S_3 acting on the syracuse inverse mapping for solving pigeonhole “problem”. and I use matrices like Young diagram to show partition of residues of 2N_0+1/〇Z.

Then think the inverse mapping as generating series of all 2N_0+1;
f^-(1+μ) {●}.
where {●} is generator(s). then it can gives such inequality(s) (very simply);
f^-(1+μ) {●} ＜ {●} ≤ f^-(1+μ) {●}.
the generator(s) itself also belongs to f^-(1+μ) {●}. so “almost all” odd are in RHS except a certain small set.

Then look at the intersection of the certain small set(LHS) and its generator {●}, we can see that it goes to be null in finite times. In other words, all elements in LHS map to the generator {●} which {●} ∈ RHS in finite times.

Finally {●} = RHS = 1. Iff the all variables in the equation are 0.
I think I have found the invariant (like) measure as Professor Tao mentioned. The problem is I am an amateur.

21 April, 2020 at 2:23 am

y.y.

The structure of the conjecture is able to describe as a certain vector, scalar multiplication/addition, group operation, and set theory. I’m not certain that it is applicable for other problems for example Navier Stolks. Anyway the conjecture has beautiful structure like Cantor set, I would like to show more details if some one gives it rigorous proof and contribute for mathematics.

23 April, 2020 at 9:36 am

Fabien

Another one ! The group of [x, 15] (so all the numbers obtained with anytime 3x+1 and 15 times divide by 2) which have 50 numbers. Not sure if it’s useful after all but I like very much to look at it, it’s hypnotic :)

1 May, 2020 at 4:09 am

Aran

I have also found an interisting property of the collatz conjecture:
for any odd number my linear function 10+x_n * 17 can describe the even number with the identical trajectory and height of n.
x_n is the position of all odd numbers in an fix axis: n=1, x_n=-1; n = 3, x_n=0 ; n = 5 , x_n=1; […] ; n = 63.728.127, x_n=31.864.062

1 May, 2020 at 7:13 am

Anonymous

Dynamical systems generated by a simple principle may have a very rich “macroscopic scale” structure (e.g. fractals, or the sequence of primes) but still may have also some “local scale properties” (e.g. Ramanujan’s tau function tau(n) which has a large scale chaotic-like behavior but still has certain interesting small-scale modularity properties).
Perhaps the Collatz iteration too has such small-scale modularity properties.

1 May, 2020 at 8:46 am

Michael M. Ross

It maybe that the point your making is more subtle than I understand, but small-scale properties are eliminated by discarding the even numbers. For example:

Odd-Even
43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Odd-only
43, 65, 49, 37, 9, 7, 11, 17, 13, 3, 5, 1

1 May, 2020 at 11:55 am

Aran

I sadly made a typing error. My linear formula to find any n_even, if n_odd is given, with the identical trajectory and height of n is:

10 * x_n + 17=y

y describes the distance between the odd and even number.

To find the n_even with you use:

y + n_odd = n_even

x_n is the position of all odd numbers in a fix axis:

n=1, x_n=-1;
n = 3, x_n=0;
n = 5 , x_n=1;
[…]
n = 63.728.127, x_n=31.864.062

1 May, 2020 at 8:53 am

Michael M. Ross

[you’re] This uses an alternate algorithm that produces, always, the same result.

a = ((n + 1) * (3 / 2)) – 1
b = ((n – 1) * (3 / 4)) + 1
c = (n – 1) * (1 / 4)

For every odd number n, only a or b or c can be a whole odd number.

18 May, 2020 at 12:35 am

Anonymous

What if we regard N as a unknown number ,as a combinded probability,to calculate expect of N?
such as assume N as even number，then N has 1/2 probability be 2*m(m∈ any odd number)，has 1/4 probability be 2^2*m,has 1/8 probability be 2^3*m etc.
Could it be a direction to solve collatz conjecture,or just totally wrong at begining? I have no idea about it but expecting smart guys reply,Thx!

15 June, 2020 at 11:01 am

Juan C Tejada

In my humble opinion, the formula has to include this kind of information…

2 = {(“E”/2) (“O” x 3 +1 sobre 2)} N

Where “E” = Even number (or the number 2 if non-existant)
Where “O” = Odd number (or 1/3 if non-existant)
Where “N” = Number of times required

15 June, 2020 at 11:03 am

Juan C Tejada

sorry.

sobre = “over”

1 July, 2020 at 5:28 am

Matthias Hippold

I see that by plugging in 1 and n in 6.2. I get at least

$\displaystyle a_{[1,n]} \geq 2(n-1)-C_A(\sqrt{n(\log(n))}+\log(n)),$

which also is greater than $n \frac{\log 3}{\log 2}$ , but how can I get the stronger statement?

But the more important question is the following.

It is then claimed, that for the stopping time it holds:

$\displaystyle k_{\text{stop}}= n \frac{\log(3)}{2 \log(2)}+O(C_A^2 \log(n))$ .

I do not understand the last statement. In the “worst” case, all the $a_i$ are 1 and then this would not hold. Clearly, this example would violate the inequality in the beginning, but why is this the case in general?

Furthermore, it is claimed, that the stopping time $k$ iff

$\displaystyle a_{[1,l]} \leq n \frac{\log 3}{\log 2}-C_A^3 \log n < a_{[1,l+1]}$

Where does the $C_A^3$ instead of $C_A^2$ come from?
Thank you in advance for any help.

7 July, 2020 at 5:28 pm

Terence Tao

There was a typo; the lower bound on $a_{[1,n]}$ should have contain a $2(n-1)$ term rather than $2n$ . For your second question, one applies (6.2) with $(i,j) = (1,k), (1,k+1)$ to obtain

$\displaystyle 2(k-1) - C_A(\sqrt{n \log n} + \log n) \leq n \frac{\log 3}{\log 2} - C_A^2 \log n \leq 2k + C_A (\sqrt{n \log n} + \log n)$

which will be incompatible with $k \leq n \frac{\log 3}{2 \log 2} - C C_A^2 \log n$ or $k \geq n \frac{\log 3}{2 \log 2} + C C_A^2 \log n$ if $C$ is large enough.

The $C_A^3$ in (6.6) (and subsequently) is a typo; it should be $C_A^2$ . All occurrences of $C_A^3$ should be replaced by $C_A^2$ (alternatively one could replace all occurrences of $C_A^2$ with $C_A^3$ ).

2 August, 2020 at 11:54 am

Alberto Ibañez

COLLATZ accelerated map (I do not know if it is already known) .It is based on a Col2 map, which together with the notable product difference nth power, follows and shortens the worst possible orbit. In case it could have any interest

$n\rightarrow n+(n+1)= n+(z\times 2^{x})= n+(z\times (3^{x}-2^{x}))= n_{1}\setminus 2^{a_{1}}= n_{2}\rightarrow ...\rightarrow 1$

with n odd

for example, the known trajectory of number 27 reaches 1 in 17 steps

4 August, 2020 at 3:03 am

Li Jiang

The Collatz Conjecture and Linear Indefinite Equation

For the collatz conjecture, we define an iterative formula of odd integers
according to the basic theorem of arithmetic, and give the concept of iterative exponent. On this basis, a continuous iterative general formula for odd numbers is derived. With the formula, the equation of cyclic iteration is deduced and get the result of the equation without a positive integer solution except 1. On the other hand, the general formula can be converted to linear indefinite equation. The solution process of this equation reveals that odd numbers are impossible to tend to infinity through iterative operations. Extending the result to even numbers, it can be determined that all positive integers can return 1 by a limited number iterations.

http://www.sciepub.com/tjant/content/8/2

5 August, 2020 at 4:40 am

Michael M. Ross

Li Jiang, I have a response, 5 Aug, but unfortunately I didn’t nest it under yours.

8 August, 2020 at 6:52 am

Hollis Williams

Hi Li, this looks like a publication in a predatory journal unfortunately. The bad website is an immediate giveaway, plus the imperfect English of the titles of the articles. It’s also associated with Science and Education (SciEP), who are known and blacklisted for their predatory journals.

5 August, 2020 at 4:38 am

Michael M. Ross

How do you address cyclicality or circularity – loops? For example, changing the addend to 17, 3x+17, you have the following cycle for n=27:
181,41,35,61,11,25,23,43,73,59,97,77,15,31,55,91,145,113,89,71,115,181

5 August, 2020 at 7:04 am

Li Jiang

Michael M. Ross, the collatz conjecture here is only 3x+1. I defined an iterative operation T=(3x+1)/2^a (a is the number of factors of even 3x+1, these factors are equal to 2), so T is also an odd number. My paper only proved 3x+1, i.e all positive numbers are neither divergent nor cyclic. I did not considering 3x+17, you can take a closer look at my paper.

6 August, 2020 at 2:38 am

Anonymous

Citing you conclusion: “Since each positive even number can be converted to an odd number after divided by factors equal to 2, the above conclusion also applies to even numbers. So all positive integers are convergent”

Are you saying you solved the Collatz conjecture?

6 August, 2020 at 11:10 am

Anonymous

He “solved” it in the same sense as hundreds before him.

8 August, 2020 at 12:57 pm

Hollis Williams

It’s in an article published by a predatory journal, so it’s overwhelmingly likely that the person has not solved the Collatz conjecture, even if they think they have.

8 August, 2020 at 5:21 pm

michaelmross

Publishing in a “predatory journal” doesn’t imply anything about the author except he’s desperate to see his work in print and on the internet. If you don’t have credentials or referrals, the options are limited. Maybe he didn’t know about Vixra and sites like that.

9 August, 2020 at 3:35 am

Hollis Williams

Publishing in predatory journals harms a person’s reputation, so yes, it does imply something about the author (it implies that they can’t be taken seriously). I believe that at this point everyone who writes articles and has an Internet connection knows about ArXiv. I suspect that the person had the article rejected as an ArViv submission and so sent it to a fake journal with no rigorous peer review process, instead of being sceptical and taking a look at what was wrong with their argument, which is a necessary part of slowly learning how to do mathematics.

7 August, 2020 at 6:26 am

Michael M. Ross

Syracuse algorithms: two ridiculously simple, superfast Python scripts for generating odd-only sequences. (I’ve posted them on Quora.) https://qr.ae/pNsQvL

9 August, 2020 at 4:48 pm

Michael M. Ross

I should say that the algorithms use an invertible, or bidirectional, first-return function – such that input n output n. The output of the inverted function cannot be finite. The Syracuse set from n –> x and the inverted Syracuse set from x–>n are equal.

11 August, 2020 at 6:54 am

Michael M. Ross

I’m just stating a fact here about the algorithmic invertibility of a Syracuse function. If you disagree, give me a reason, rather than a downvote. (I attempted to put a symbol between input n and output n to denote bidirectional, but evidently associated with SQL injection, so disappeared.) I wish I knew how to paste images into these posts. If this latex fails, I provide a link to the functions:

Syracuse (convergent)
$f(n) = \begin{cases} ((n+1) \frac {3}{2})-1 & \mbox{if } n+1 \equiv 0 \mbox{ (mod } 4) \\ ( (n-1) \frac {3}{4})+1 & \mbox{if } n-1 \equiv 0 \mbox{ (mod } 8) \\ (n-1)4 & \mbox{otherwise } \end{cases}$

Inverted Syracuse (divergent)
$f(n) = \begin{cases} ((n+1) \frac {2}{3})-1 & \mbox{if } n+1 \equiv 0 \mbox{ (mod } 3) \\ ( (n-1) \frac {4}{3})+1 & \mbox{if } n-1 \equiv 0 \mbox{ (mod } 6) \\ (n-1)4 & \mbox{otherwise } \end{cases}$

(The inverted function can only create sequences that are nonfinite.)

https://qr.ae/pNsQ2o

8 August, 2020 at 3:55 pm

Steve

I’ve noticed that if you plot n and f(n) on log-log, you always wind up with two parallel lines. Could that provide any sort of additional help knowing how the function is bounded? The solution travels back and forth along those lines, but vastly more towards the 4,2,1 orbit than towards higher numbers.

8 August, 2020 at 9:39 pm

Anonymous

Here f(n) is the collatz iteration? If so, you’ve discovered the fact that log(xy)=log(x)+log(y).

11 August, 2020 at 12:23 am

Li Jiang

Maybe my article The Colltatz Conjecture and Linear Indefinite Equition was not published in a more famous journal, but if Prof. Terence Tao read this article, he would understand: this article does prove Collatz (3x+1)conjecture.

http://www.sciepub.com/tjant/content/8/2

13 August, 2020 at 11:09 am

Hollis Williams

Li, I mean you no disrespect, but that is extremely unlikely. Simply stating that you have proved a conjecture does not mean you have proved it. Tao (and all professional mathematicians) are very busy and cannot be expected to read every article which is sent their way. If you publish your proof in a fake journal which publishes worthless articles, it’s a safe assumption that the proof you propose is very likely worthless, and no time needs to be expended in reading it to come to that conclusion. I suggest that you reconsider your proof and try to find the point where you have gone wrong.

11 August, 2020 at 11:08 am

Alberto Ibañez

Hello Li JIANG. Good luck with your demonstration. I would be very grateful if you could explain point 3. Possibility of cyclic, in more detail, if possible. Thank you

11 August, 2020 at 12:24 pm

Anonymous

I would also like to understand more. The paper is very short, so if it is wrong, someone should find the error quite fast. No need to dig through many pages. Anyone sees some flaws?

11 August, 2020 at 3:46 pm

Li Jiang

Dear Alberto Ibañez
The essence of the 3x+1 conjecture is the iterative operation of odd numbers. It is known from the basic theorem of arithmetic: the number of factors with a value equal to 2 in each even number is determined for the even number, so an iterative operation for odd numbers x can be defined. That is: $T=(3x+1)/2^a$, (where a is the number of factors whose value in 3x+1 is equal to 2), the result of the operation T is still odd.
According to this definition, the general formula for odd continuous iteration can be derived, that is
$ T^{(k)}(x)=\dfrac{\displaystyle{3^k x+\sum_{i=1}^{k}2^{g(i-1)}3^{k-i}}}{2^{g(k)}}. $
From this, if the odd continuous iteration may cause loops, then we can deduce the equation that
$ x=\dfrac{\displaystyle{3^k x+\sum_{i=1}^{k}2^{g(i-1)}3^{k-i}}}{2^{g(k)}}. $
Solving this equation can get the result that the equation has no positive integer solution except 1, which indicates that continuous iteration cannot cause a loop.

12 August, 2020 at 8:31 am

Michael M. Ross

(Your latex is fine – you just have to use $latex at the beginning on WP.)

You can look at the impossibility of loops from the point of view of common differences between inputs and outputs. For there to be a loop the sum of positive and negative differences must sum to 0 – that must be so. You can then show by contradiction how this can occur for, say, 3x+17, but not for 3x + 1, by tabulating inputs and outputs:

1 –> 25 = 14
13 –> −1 = −14
17 –> 17
21 –> 1 = −20
23 –> 43 = 20

We can call n –> n the equilibrium point. Every n in 3x+n has such a point, and of course it’s always the addend of 3x.

Whereas for 3x + 1, the equilibrium point is of course 1, and so is asymmetrical (only permitting the trivial loop, which in an odd-only function is actually 1 –> 1):

5 –> 1 = −4
7 –> 11 = 4
1 –> 1
…
…

If you look at the tabulation of inputs and outputs for 3x+1 you will see why this equilibrium would not occur again. But maybe there would be difficulty in formally proving this also eliminates another means of zero-summed loops.

27 August, 2020 at 5:42 am

Ken Surendran

See for latest work at
arXiv:2008.02161

27 August, 2020 at 8:26 am

michaelmross

Agreed, there are three categories of numbers – but I don’t understand the Starter, Intermediary and Terminal construct. I see there are three and only three, according to congruence, and three operations associated with them:

$n+1 \equiv 0 \mbox{ (mod } 4) \\ n-1 \equiv 0 \mbox{ (mod } 8) \\ n-1 \equiv 0 \mbox{ (mod } 2)$
$((n+1)*1.5)-1) \\ ((n-1)*0.75)+1) \\ (n-1)*0.25$

This generates the “lattice” structure of merging sequences:
https://tinyurl.com/yyo688mb

27 August, 2020 at 5:17 pm

Ken Surendran

There are two types of Intermediary integers (6m+1 and 6m+5).

27 August, 2020 at 9:03 pm

Mathematicians Are So Close to Cracking This 82-Year-Old Riddle – The Endless Night

[…] breakthrough post is titled “Almost All Collatz Orbits Attain Almost Bounded Values.” Let’s break that down slightly. Collatz Orbits are just the little sequences you get with the […]

28 August, 2020 at 7:01 pm

Ken Surendran

Only odd Integer are considered in this study.
Collatz Conjecture y = (3x+1) / 2^α (Equation-1) where α > 0 is an integer, is considered in this study. Here, x and y are odd integers.
Odd integers are ‘categorized’ from Collatz conjecture perspective in the following:
1. End integer is 1 (since this where the process ends)
2. Starter Integers are of the form 6m+3 where m = 0, 1, 2, 3, … and these are odd multiples of 3. They are named as Starter Integers since they cannot be Collatz conjecture results [they can never be ‘y’ in Equation-1] but the conjecture process can start with them. One-third of the odd integers are Starter integers.
3. Terminal integers are those whose Collatz conjecture result is 1 (i.e., the End integer). They terminate the conjecture process by producing 1 as the result in a single use of Equation-1. Such integers are: 5, 21,85,341, 1365,… which are related by 4x+1, where x is the previous integer in the series. Excluding those Starter integers like 21, 1365 that are odd multiples of 3 (every third Terminal integer is in the list) each of the remaining two-thirds of the Terminal integers have a set of Pre-terminal integers. For instance, the conjecture result for the integers 3, 13, 53, 213, … is 5, a Terminal integer. Also these Pre-terminal integers are related by 4x+1 (x being the previous integer in the list).
For naming convenience, the non-Starter integers, i.e., the odd integers of the form 6m+1 and 6m+5 are called the Intermediary integers. Also, each Intermediary integer is the Collate conjecture result for a set of odd integers, that are related by 4x+1 (x being the previous integer in the set). Expressions for generating such sets of odd integers are provided in Section 5. Sample sets of odd integers are provided for both 6m+1 (in Table 4A) and 6m+5 (in Table 4B) type integers. As indicated earlier in Dr. Tao’s narrative, one-third of the odd integers are involved in dealing with 6m+1 and two-thirds are involved in dealing with 6m+5.
Another classification of odd integers from Collatz conjecture perspective is based on value of α an integer x uses in Equation-1. It is noted that all the integers of the form 4m+1 use α ≥ 2 and the rest of the integers (that are of the form 4m+3) use α=1. The conjecture results of the 4m+3 integers are all of the form 6m+5. In Table 5, the conjecture behavior of the 4m+3 integers (based on their trajectory-length with continuous use of α = 1) are presented.

19 September, 2020 at 10:33 am

Anonymous

The link details: https://arxiv.org/abs/2008.02161

5 September, 2020 at 9:25 am

Closing An Open Problem | Gödel's Lost Letter and P=NP

[…] Conjecture : Terence Tao made important progress on this notorious problem. He […]

19 September, 2020 at 3:25 pm

michaelmross

Engineering vs Number Theory: Never the twain shall meet.

20 September, 2020 at 5:41 am

Anonymous

That was also Hardy’s opinion. But several cryptographic number-theoretic applications in engineering (e.g. RSA) show the contrary.

9 October, 2020 at 10:00 pm

La Congettura di Collatz: un passo verso la risoluzione?

[…] Terence Tao, riporto due link: uno a una versione discorsiva del suo metodo (più digeribile) e uno alla descrizione più formale, per la quale serve un’attrezzatura matematica che, ahimè, non […]

3 November, 2020 at 9:12 am

Faiz

Collatz Conjecture:
Lets use binary approach
If number is even then 0 else if odd then 1
Eg:-5(odd)-16(even)-8(even)-4(even)-2(even)-1(odd)
100001->5
Similarily 010100001->6
001 ->4
Now lets try opposite, instead lets take a binary number and try to make repeating number from it.
Lets say a function P which takes a binary number and converts it into repeating collatz number.
Eg: P(001)=4
But what about P(1001),P(100101) and many??
Actually we can form a repeating number from them too with this formula:
Number of zeroes in binary number=x
Number of ones in binary number =y
Formula= C/(2^x – 3^y)
To find the value of C is little tricky ,first we see binary number from left to right if first digit is 1 then we store 1 (say in variable “result”)and when we see zero then we increase the power of two(say in variable “pow2”) each time, If we see 0 as first digit in binary number then we store 0 in result variable but dont forget to increase power of 2 as well and when we see 1 again we multiply result variable by 3 and add pow2 and then again store it in result.The final result is our answer C

Eg: 100 Result Pow2
1 1 2^0=1
0 1 2^1=2
0 1 2^2=4

Hence the final result is 1 or C =1
Formula= C/(2^x – 3^y)=1/(2^2-3^1)=1
1 is indeed repeating collatz number.

Eg: 1001 Result Pow2
1 1 2^0=1
0 1 2^1=2
0 1 2^2=4
1 3*(1)+4=7 2^2=4

C=7
Formula= C/(2^x – 3^y)=7/(2^2-3^2)= -7/5
Haha -7/5 is indeed a repeating collatz number
How? Just apply operation as in binary number 1001

First step: 3*(-7/5)+1=-16/5 [Since first digit is 1 and this says to apply operation 3n+1]

Second step : -16/5 ×1/2 =-8/5[Since second digit 0 says to divide by 2]

Thirs step : -8/5 ×1/2=-4/5[Third digit 0]

Fourth step: 3×(-4/5)+1= -7/5 [ Fourth digit 1]

(Yaay -7/5 the number we started with)

Eg: 00011 Result Pow2
0 0 2^1=2
0 0 2^2=4
0 0 2^3=8
1 3×(0)+8=8 2^3=8
0 8 2^4=16
C=8
Formula= C/(2^x – 3^y)=8/(2^4-3^1)= 8/13
Yes 8/13 is indeed a repeating collatz number
You can check by applying operations as in binary numbers stated.

So just take any random binary number and feed it in function P and it will indeed give a repeating collatz number which might give us a fraction or negative number or a proper positive integer. If we managed to get a proper positive integer except 4,2,1 then we can disprove collatz conjecture.

Thats all if you want then you can contact me on my email:faiz262003@gmail.com
Thank you : )

5 November, 2020 at 9:49 am

Alexandre Patriota

Professor Terence Tao,

In your Proposition 1.9, you assume that $\mathbf{N} \mod 2^m$ is approximately uniformly distributed in $\mathbb{Z}/2^m\mathbb{Z}$ in the sense described in equation (1.11). This assumption implies that the distribution of the random version (RV) of the n-Syracuse valuation is approximately distributed as n-iid copies of a geometric random variable with probability of success 1/2. The validity of Theorems 1.3 and 1.5 depends on this specific geometric distribution with expectation 2, since if it were a geometric distribution with expectation smaller than $\log_2 3$ the consequences would be different.

I ran some simulations and noticed that the maximum estimated probability of success the RV-Syracuse valuation is strictly above 0.5 and below 0.7. This indicates that the geometric distribution with expectation 2 might not be representing the process well. It would be nice to consider “worse” scenarios, where the expectation is smaller than 2. The uniform distribution assumption could be relaxed to a class of distributions which would allow other than geometric distribution with expectation 2 to describe the probabilistic behaviour of the RV-Syracuse valuation.

I tried working on the assumptions of Proposition 1.9, but I am stuck in some details since I am not an expert in number theory. My guess is that Theorems 1.3 and 1.5 are valid if the expectation of the RV- Syracuse valuation is larger than $\log_2 3$ (or some limit version of this statement):

1. it is the case that ${\rm Syr}_{{\rm min}}(N) < f(N)$ for almost all $N \in 2\mathbb{N}+1$ , if the expectation of the RV-Syracuse valuation is larger than $\log_2 3$ .

2. It is not the case that ${\rm Syr}_{{\rm min}}(N) < f(N)$ for almost all $N \in 2\mathbb{N}+1$ , if the expectation of the RV-Syracuse valuation is smaller than $\log_2 3$ .

It seems one needs to explore the consequences in terms of probability distributions of the following fact: $\mathbf{N}$ is constrained to a single odd residue class module $2^{|a|+1}$ . The uniform distribution simplifies the problem, but we do not necessarily have to impose this assumption.

Best
A. Patriota.

8 November, 2020 at 9:28 pm

Terence Tao

Proposition 1.9 is applied in the paper near the beginning of Section 7, to the logarithmic distribution on $[y, y^\alpha]$ , with $2^m$ basically a small power of $y$ (such as $y^{0.1}$ ). The hypothesis (1.11) can be verified in that case by use the integral test to calculate the probability that any given residue class modulo $2^m$ is attained.

If instead one used the logarithmic uniform distribution on $[1,x]$ for ${\bf N}$ , the deviation of the Syracuse random variables from the geometric distribution would be expected to be of the order of $O(1/\log x)$ since ${\bf N}$ will be bounded with this probability. However it would still converge to geometric (albeit rather slowly) in the limit $x \to \infty$ . But in this paper I am not applying Proposition 1.9 directly to this distribution.

9 November, 2020 at 6:52 am

Alexandre Patriota

I just noticed that you have updated Proposition 1.9 in version 3 of your manuscript in arxiv. Maybe that would have an effect in my simulations.

You meant “the beginning of Section 5” on the top of page 19, right?

11 November, 2020 at 8:28 am

Alexandre Patriota

“The hypothesis (1.11) can be verified in *that case*…”

*That case* seems to be dependent on the logarithmic density definition of “almost all” which induces $\mathbf{N}$ to be logarithmically uniformly distributed which implies that $\mathbf{N} \mod 2^m$ is approximately uniformly distributed which, by its turn, implies that the random Syracuse valuation is close to a geometric random variable with mean 2.

If $\mathbf{N}$ is randomly generated according to a different probability law (i.e., we would have a change in the “almost all” definition), then what does guarantee that the random Syracuse valuation is close to a geometric random variable with average 2?

If the results are robust, they should not depend too much on the probability law used to define “almost all”. Is it possible to change the definition of “almost all” such that it keeps the same essence of “almost all” concept but makes your main theorems invalid?

For instance, you can change the probability $\mathbb{P}(\mathbf{\log}(2\mathbb{N}+1 \cap [1,x]))$ to a different version indexed by a parameter $\theta \in (0, \infty)$ , namely, $\mathbb{P}_\theta(\mathbf{\log}(2\mathbb{N}+1 \cap [1,x]))$ such that for some values of $\theta$ , say $\theta \geq \log_2 3$ , the main results hold valid and for others, say $\theta < \log_2 3$ , the main results fail.

What can prevent me from finding such a probability $\mathbb{P}_\theta$ ?

14 November, 2020 at 5:38 pm

Terence Tao

Well, if the Collatz conjecture is true, then the conclusion of my theorem would hold for all $N$ , not just almost all $N$ , so in particular one would get an almost all result for an arbitrary distribution. I suspect the theorem is provable using the notion of natural density instead of logarithmic density, and in fact I know some people who are working on this extension of the result right now; the logarithmic distribution is convenient for technical reasons (in particular it can handle the dilation aspects of the iterated Syracuse map quite easily, leaving only the translation aspects to be understood carefully) but is unlikely to be a genuine restriction to the method in my opinion.

14 November, 2020 at 6:53 pm

Alexandre Patriota

Yes, but as we do not know whether the Collatz conjecture is true or not, the conclusion that ${\rm Syr}_{{\rm min}}(N) < f(N)$ for almost all $N \in 2\mathbb{N}+1$ seems to be derivable only under some contexts.

My conjecture is that

1. your results remain true for any RV-Syracuse valuation whose expectation is larger than $\log_2 3$ (or under similar conditions), since this is a consequence if the Collatz conjecture is true.

2. your results fail to be true if the RV-Syracuse valuation has expectation smaller than $\log_2 3$ .

Naturally, the "almost all" concept has to be defined in such a way to allow these cases.

I am not sure exactly how to prove it and that is the main reason I am writing here. I tried to work on it, but it is not my field and I already spent a lot of time on it.

Maybe someone can explore other versions of "almost all" that allow those distributions. I am still a little bit concerned about my simulation results. When I have time, I will work more on it.

Best regards,
A. Patriota.

14 November, 2020 at 7:19 pm

michaelmross

Some properties are far from arbitrary – for one, the stopping times of sequences are eminently predictable in two important cases:
If sequence n+1 ≡ 0 (mod 4), sequence 6n+3 has the same stopping time.
If sequence n−1 ≡ 0 (mod 8) , sequence 3n+2 has the same stopping time.
I just noticed this, and find it reassuring we’re not dealing with something too wild and woolly.

16 November, 2020 at 2:11 am

Alberto Ibañez

Hello, how can I understand with my high school math level what it means that the expectation is larger or smaller than \ log_2 3?, Thanks

16 November, 2020 at 6:08 am

Robert Frost

@Alberto the expectation is the mean of all possible outcomes, weighted according to each outcome’s likelihood. $r=\log_3(2)\approxeq 0.6309$ . If you roll a standard 6-sided dice your expected outcome is $3.5$ because there are six equally likely outcomes and if you add them all together and divide by six, you get $3.5$

16 November, 2020 at 5:00 am

Robert Frost

You prove the statement the statement “almost all trajectories converge to $n$ ” but is your proof true independently of $n=1$ ? Because it it were not, this would surely give us the proof. Because I assume it would be a contradiction that almost all trajectories converge to $1$ and also converge to $n\neq 1$ .

18 November, 2020 at 3:55 am

Alberto Ibañez

Thanks @robert frost, although I can’t quite understand it. I wanted to see if it could be related to two facts, which I don’t know if they have something to do with it, but I still expose them.
The first is that every worst orbit is finite, which I explained in a previous comment, and that when k, the number of odd steps tends to infinity, y the number of even steps is always much greater, that is, y-k tends to infinite.
If we use a col2 map that takes us through the worst possible orbit, for an odd n, if n +1 = z * 2^k, in k iterations the resulting value is NEVER odd(0% probabiliy), that is, at least it is divided more than 1 time by 2.
Does this fact influence the calculation of probabilities?

“for instance, one can compute that for large random odd ${\mathbf{N}}$ , ${\mathrm{Syr}^2(\mathbf{N}) \hbox{ mod } 9}$ will take the residue classes ${0,1,2,3,4,5,6,7,8 \hbox{ mod } 9}$ with probabilities

$\displaystyle 0, \frac{8}{63}, \frac{16}{63}, 0, \frac{11}{63}, \frac{4}{63}, 0, \frac{2}{63}, \frac{22}{63}$ ,
that is, any more of these probabilities becomes 0?

The second fact is that, for known orbits reaching 1, although only checked for a few given my limitations,
in the iteration of 3n + 1.3n, it is multiplied by 3, while +1 is multiplied by 3 and a power of 2 is added, let’s say that the evolution of the term + 1, is gaining weight in% with respect to the sum n * 3^k + d, until + d reaches a value greater than 25% of the sum, although it is after reaching a power of 2.
Could we suggest that the weight of the term +1 in the iteration of the sum 3n + 1 evolves to exceed 25% of the total is always possible and does it mean that there is always a solution?
thanks and sorry if i say a lot of nonsense

26 November, 2020 at 4:07 am

kenoc22

I have spent 2 months writing collatz conjecture python programs to understand the sequences and patterns produced by the Collatz Conjecture and have come a long way in understanding but am still only opening the gate to the party and have not feasted on the solution as you have with your advanced level of mathematical understanding and skills. I’m using basic arithmetic sequences which has allowed me to work out all of the Collatz even number states 3N+1 = (6m +4) where m = 0,1,2,3,4…. and N=2m+1 and there are 12 states I have designated as C0 to C11. The “multiply by 3 plus” algorithm only transitions to states C0, C2,C3,C5,C6,C8,C9,C11 while states C1,C4,C7,C10 only appear once in any iteration at the beginning and only if the first iteration of “multiply by 3 plus 1” points to one of these states, dependent solely on the number chosen to perform the conjecture algorithm. I have mapped all the state transitions and how they transition from one state to the next, dependent on odd and evenness and the the factors of 4,8,16,32 etc. C0,C8, perform 2 divisions by 2, while C1,C3,C5,C9 and C11 perform only 1 division by 2 and C2 and C6 perform 3 or more divisions by 2. What I have proven using the probabilities of all the states is the occurrences of each of the states in any trajectory (not of form 2^^K +- 1) is that the average number of states for larger numbers equate to:

C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11
N 0-1 2N N 0-1 2N N 0-1 2N N 0-1 2N

ie as an example from my python program
Number:
1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220000

Collatz C_0 to C_11 totals:[282, 0, 610, 251, 0, 560, 269, 0, 528, 296, 0, 520]

From the information gained by mapping all the state transitions and understanding the number of states in each trajectory , independent of the size of the number I was able to calculate the probabilities of each state occurring and the probabilities align with the state number ratios for each trajectory. Based on the probabilities for each state I can prove non rigorously therefore that the average value of the number of multiply by 3’s is less than the average number of divide by 2’s implying the conjecture always must converge for large number long trajectories based on the probabilities.

I know this is a non-rigorous proof because I am using the probabilities of the states occurring based on their transitions from other states rather than proving that a generic starting number will gradually reduce in size as the conjecture iterates over a long trajectory to prove convergence but this is a basic proof using probability that can give some credence to the conjecture that it is valid for all whole numbers.

26 November, 2020 at 6:05 pm

kenoc22

have got myself into a rabbit hole with my approach as I don’t have the mathematical expertise of the mathematicians such as Terence Tao, a mathematical master of the times, nor their primed skills to solve this rigorously but programming this algorithm has revealed a lot, as well as looking at it through the state transition perspective because it helped in understanding the trajectory patterns. What I have found as mentioned in previous reply is the strong bias towards the ratios of number of states in the trajectory as shown in my reply preceding. As an example I have run my python algorithm on the following 2 large numbers.

1. 3^10,000 and is 4,772 digits in length and trajectory totals 38,126 “multiply by 3 plus 1” iterations
Collatz C_0 to C_11 totals:[3214, 0, 6322, 3214, 1, 6381, 3158, 0, 6381, 3213, 0, 6242]
This follows the general pattern:
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11
N 0-1 2N N 0-1 2N N 0-1 2N N 0-1 2N

2. 3^29,999 and is 14,314 digits in length and trajectory totals 114,015 “multiply by 3 plus 1” iterations
Collatz C_0 to C_11 totals:[9510, 1, 18969, 9471, 0, 18918, 9442, 0, 19050, 9670, 0, 18984]
This follows the general pattern:
C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11
N 0-1 2N N 0-1 2N N 0-1 2N N 0-1 2N

Now I know this number of states breaks down near numbers of the form 2k
and specifically numbers 2k -1 and 2k +1 but it is easy to prove why because there is a preamble of repeated states until the 2k factor is removed by multiple iterations and then the trajectories appear to follow this pattern.

In general based on the numbers I have run there is an absolutely strong tendency to convergence based on the probabilities of hitting odd and even sub number ‘n’ within m where N=2m+1 and m=12n + {0,1,2,3,4,5,6,7,8,9,10,11} and n = 0,1,2,3… and multiples of 4,8,16,32… and alternate odd numbers within ‘n’.

In terms of the strong convergence for all whole numbers:
State: C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11
Number of states: N 0-1 2N N 0-1 2N N 0-1 2N N 0-1 2N
Average Divide
by 2: 2^2 1 > 2^8 2 1 2^2 >2^4 1 2^2 2 1 2^2
Average Multiply
by 3: 3 1 3^2 3 1 3^2 3 1 3^2 3 1 3^2

So the average long multiply by 3 divided by 2 factor for the trajectories of large numbers is” 3^12 / 2^22 = 0.36 and so convergence is a very strong factor in general but this is not a rigorous proof just a calculation of the strong general bias to convergence based on observation and on the general probabilities of the state transitions.

26 November, 2020 at 6:18 pm

kenoc22

In the preceding reply it mentions 2k , 2k +1 and 2k -1 but the exponent has been removed by the text editor when pasting and should be 2^k, 2^k +1, and 2^k -1 otherwise the comment related to this section is incorrect.

26 November, 2020 at 2:01 pm

Anonymous

Is it possible to use AI deep-learning algorithms to discover more (still unknown) nontrivial patterns in the $Col$ , $Syrac$ and related similar iterations – which might help deducing stronger quantitative results on this conjecture?

3 December, 2020 at 1:39 pm

Josh Bourgeois

Well, I’ve tossed my hat into the ring. https://observablehq.com/@thepeoplesbourgeois/so-this-whole-collatz-conjecture-thing

3 December, 2020 at 2:40 pm

michaelmross

You must know that in order to prove a mathematical conjecture, you have to be a mathematician, accredited and respected. Even if your paper were true, it has no standing. Further, it’s algorithmic, not algebraic. Lastly, as far as I can see, it doesn’t address the whole question of circularity – why does the same number never recur in a sequence. Nevertheless, it may have value!

3 December, 2020 at 3:19 pm

Anonymous

It’s embarrassing that you think you proved anything.

3 December, 2020 at 9:03 pm

Li Jiang

Hi, Terence Tao
Please read my article The Collatz Conjecture and Linear Indefinite Equation
at http://www.sciepub.com/tjant/content/8/2

3 December, 2020 at 9:10 pm

Li Jiang

29 December, 2020 at 11:48 am

Alexander Grigoriev

Mr Li Jiang,

What are your thoughts on my comment below?

Regards,
Alex

27 December, 2020 at 1:51 pm

Fabian

Maybe there is a slight parsing error after “This was then improved by Allouche to”.
Aditionally, in the following sentence appears theta which is not defined before.
Thank you for your cool blog.
Fabian

[Corrected, thanks – T.]

29 December, 2020 at 11:47 am

Alexander Grigoriev

Consider a set of Ki>0.
If it’s possible to prove that the product:

П((3Ki+2)/(2Ki+1))

can never be a power of 2 (means its factors can never fully cancel each other, leaving only 2s from the numerator), then this will prove that a Collatz sequence can never loop.

Context:

A Collatz sequence of odd numbers 2Ki+1 is equivalent to series of multiplications by:

(3Ki+2)/((2Ki+1)*2^Ni),

where division by 2^Ni means discarding all least significant zeros from the intermediate result.

If the sequence loops to the initial number, this means the product of such terms becomes equal exactly to 1, or the product of terms without 2^Ni in the denominator becomes equal to exact power of 2.

It seems that, without even considering Ki belonging to a Collatz sequence, it’s not possible to find such a set that the product above will become a power of 2.

The only such trivial value is K=0, which makes the term equal to 2, which corresponds to the only known loop starting from 1.

29 December, 2020 at 12:07 pm

Alexander Grigoriev

To avoid confusion:
Of course, the canonical formula for Collatz (from 2Ki+1) would be:
(6Ki+4)/((2Ki+1)*2^Ni)

but we can just drop that extra 2, so it becomes 3Ki+2 in the numerator.

29 December, 2020 at 9:37 pm

Alexander Grigoriev

I suspect if such a set existed, the minimum set would be pretty trivial and not unique. Yet, a brute force search in 40 bit space (each Ki checked for up to 10 bit for 2, 3, 4 terms) brought no results.

29 December, 2020 at 12:24 pm

Alexander Grigoriev

If we can prove that a Collatz sequence starting from any arbitrary odd number N will eventually produce a smaller number M, then it will prove that Collatz sequence always converges to 1.

If we consider as a single step multiplying the previous number by 3, adding 1, and then discarding all least significant zeros, such a step will (on logarithmic average) multiply the number by 3/4.
On average, each step discards two zeros, which is equivalent to dividing by 4. (one zero is discarded with probability 1/2, two zeros with probability 1/4, 3 zeros with probability 1/8, and such series 1/2+2/4+3/8+4/16… sums to 2 zeros on average).
Thus, any long enough sequence, even though it may wander up and down, would inevitably come below its starting number.

Note that all starting numbers expressible as 4K+1 reach a smaller number after a single step. Only the starting numbers expressible as 4K+3 will produce a non-trivial sequence before reaching a smaller number.

I address (im)possibility of loops in my previous comment.

20 January, 2021 at 2:59 am

La conjecture de Syracuse : temps de vol, altitude maximale, atterrissage…. | Autrement qu'être Mathesis uni∜ersalis Problema Universale Heidegger/Husserl être/conscience : plan vital-ontologique vs plan spirituel d'immanence CLAVIS UN

[…] https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ […]

23 January, 2021 at 6:00 am

marcos luz

Dear Prof. Tao, it is may be the case that in proper log scale, Collatz sequences for very large initial numbers can related to geometric Brownian motion (strong numerical indications), as recently published in Physical Review Research: https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.3.013073

10 April, 2021 at 5:13 am

Hubert Schaetzel

Let us consider the 4, 2, 1, 4… cycle on the positive side of Z. Is it isolated ? No. This cycle is the root of a tree growing indefinitely above it. Let us look at the negative side of Z. There are (at least) 3 cycles. Are they isolated ? No, of course. Each cycle is the root of a tree growing indefinitely above it. So let us think a few seconds and state together : Any number is trivially (and proof is easily given of that) within a tree which expands infinitely. There can be nothing like a cycle with no branches developing out of its 1 mod 3 and 2 mod 3 valued integers which won’t give new ramifications. So if one can prove that this expansion is of non-zero density in Z, one can than conclude with Riho Terras theorem given in 1976 (The 4, 2, 1 cycle tree is of density 1 in N). This is not so hard. One can even fully describe the Pascal triangle based characteristics of that expansion (within appendix 5 of given reference).
https://hubertschaetzel.wixsite.com/website Terras sheet

	Giovanni Di Savino on The parity problem obstruction…
	Zach Hunter on Additive combinatorics
	Richard Harris on The Riemann hypothesis in vari…
	Richard Harris on The Riemann hypothesis in vari…
	Richard Harris on The Riemann hypothesis in vari…
	Role Models to Stop… on Career advice
	Role Models for High… on Does one have to be a genius t…
	Role Models for High… on Be professional in your w…
	Role Models for High… on Be patient
	Role Models for High… on Think ahead
	Role Models for High… on Attend talks and conferences,…
	Role Models for High… on Ask yourself dumb questions –…
	Role Models for High… on Learn the power of other mathe…
	Role Models for High… on Learn and relearn your fi…
	Role Models for High… on Work hard

Almost all Collatz orbits attain almost bounded values

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

414 comments

Leave a Reply Cancel reply

For commenters

Almost all Collatz orbits attain almost bounded values

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

414 comments

Leave a Reply Cancel reply

For commenters