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 “<a href=”http://arxiv.org/abs/1909.03562″>Almost all Collatz orbits attain almost bounded values</a>”, submitted to the proceedings of the <a href=”https://www.cambridge.org/core/journals/forum-of-mathematics-pi”>Forum of Mathematics, Pi</a>. In this paper I returned to the topic of the notorious <a href=”https://en.wikipedia.org/wiki/Collatz_conjecture”>Collatz conjecture</a> (also known as the ${3x+1}$ conjecture), which I previously discussed in <a href=”https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/”>this blog post</a>. 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

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

Establishing the conjecture for all ${N}$ remains out of reach of current techniques (for instance, as discussed in the <a href=”https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/”>previous blog post</a>, it is basically at least as difficult as <a href=”https://en.wikipedia.org/wiki/Baker%27s_theorem”>Baker’s theorem</a>, 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 <a href=”https://mathscinet.ams.org/mathscinet-getitem?mr=1980260″>of Krasikov and Lagarias</a> 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 <a href=”https://mathscinet.ams.org/mathscinet-getitem?mr=568274″>by Terras</a> that for almost all ${N}$ (in the sense of <a href=”https://en.wikipedia.org/wiki/Natural_density”>natural density</a>), one has ${\mathrm{Col}_{\min}(N) < N}$ . This was then improved <a href=”https://mathscinet.ams.org/mathscinet-getitem?mr=567874″>by Allouche</a> to ${\mathrm{Col}_{\min}(N) < N^\theta}$ for almost all ${N}$ and any fixed ${\theta > 0.869}$ , and extended later <a href=”https://mathscinet.ams.org/mathscinet-getitem?mr=1290275″>by Korec</a> 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):

<blockquote>Theorem 2 <a name=”main”></a> 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). </blockquote>

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 <a href=”https://mathscinet.ams.org/mathscinet-getitem?mr=1309539″>observed by Bourgain</a> 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 <a href=”https://en.wikipedia.org/wiki/Geometric_distribution”>geometric distribution</a> 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 <a name=”coe”> $\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)$ 
</a> 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 <a name=”starb”> $\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)$ 
</a> $\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 <a name=”rate”> $\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)$ 
</a> 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 <a href=”#rate”>(3)</a> then typically takes a form like ${M/2^{2m}}$ with ${M}$ an integer between ${0}$ and ${3^n}$ ). This analysis of the component <a href=”#rate”>(3)</a> of <a href=”#coe”>(1)</a> 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 <a href=”#starb”>(2)</a> we have to exploit the mixing effects of the remaining portion of <a href=”#coe”>(1)</a> that does not come from <a href=”#rate”>(3)</a>. After some standard Fourier-analytic manipulations, matters then boil down to obtaining non-trivial decay of the <a href=”https://en.wikipedia.org/wiki/Characteristic_function_(probability_theory)”>characteristic function</a> of ${\mathbf{Syrac}({\bf Z}/3^n{\bf Z})}$ , and more precisely in showing that <a name=”charb”> $\displaystyle \mathbb{E} e^{-2\pi i \xi \mathbf{Syrac}({\bf Z}/3^n{\bf Z}) / 3^n} \ll_A n^{-A} \ \ \ \ \ (4)$ 
</a> for any ${A > 0}$ and any ${\xi \in {\bf Z}/3^n{\bf Z}}$ that is not divisible by ${3}$ .

If the random variable <a href=”#coe”>(1)</a> was the sum of independent terms, one could express this characteristic function as something like a <a href=”https://www.encyclopediaofmath.org/index.php/Riesz_product”>Riesz product</a>, which would be straightforward to estimate well. Unfortunately, the terms in <a href=”#coe”>(1)</a> are loosely coupled together, and so the characteristic factor does not immediately factor into a Riesz product. However, if one groups adjacent terms in <a href=”#coe”>(1)</a> 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 <a href=”#coe”>(1)</a> as an averaged Riesz product. One can use this to establish the bound <a href=”#charb”>(4)</a> 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 <a href=”https://en.wikipedia.org/wiki/Renewal_theory”>renewal process</a>) 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 <a href=”#charb”>(4)</a>, and thus Theorem <a href=”#main”>2</a>.

406 comments

Comments feed for this article

10 September, 2019 at 8:40 am

goingtoinfinity

What is the relations between results for “almost all” cases vs. subsequent proofs of the full result, from historic examples? Are there good examples where the former influences the developments of the later? Or is it more common that, proving results for full results of a mathematical question, is conducted in an entirely different way usually?

As an example, Falting’s proof that there are only finitely many solutions to Fermat’s Last Theorem — did his techniques influence and appear in Wiles’s/Taylor’s final proof?

10 September, 2019 at 9:10 am

Terence Tao

One can broadly divide arguments involving some parameter (with a non-empty range) into three types: “worst case analysis”, which establish some claim for all choices of parameters; “average case analysis”,which establish some claim for almost all choices of parameters; and “best case analysis”, which establish some claim for at least one choice of parameters. (One can also introduce an often useful variant of the average case analysis by working with “a positive fraction” of choices rather than “almost all”, but let us ignore this variant for sake of this discussion.) There are obvious implications between the three: worst case analysis results imply average case analysis results (these are often referred to as “deterministic arguments”), and average case analysis results imply best case analysis results (the “probabilistic method”). In the contrapositive, if a claim fails in the average case, then it will also fail in the worst case; and if it fails even in the best case, then it fails in the average case. However, besides these obvious implications, one generally sees quite different methods used the three different types of results. In particular, average case analysis (such as the arguments discussed in this blog post) gets to exploit methods from probability (and related areas such as measure theory and ergodic theory); best case analysis relies a lot on explicit constructions to design the most favorable parameters for the problem; but worst case analysis is largely excluded from using any of these methods, except when there is some “invariance”, “dispersion”, “unique ergodicity”, “averaging” or “mixing” property that allows one to derive worst-case results from average-case results by showing that every worst-case counterexample must generate enough siblings that at they begin to be detected by the average-case analysis. For instance, one can derive Vinogradov’s theorem (all large odd numbers are a sum of three primes) from a (suitably quantitative) almost all version of the even Goldbach conjecture (almost all even numbers are the sum of two primes), basically because a single counterexample to the former implies a lot of counterexamples to the latter (see Chapter 19.4 of Iwaniec-Kowalski for details). At a more trivial (but still widely used) level, if there is so much invariance with respect to a parameter that the truth value of a given property does not actually depend on the choice of parameter, then the worst, average, and best case results are equivalent, so one can reduce the worst case to the best case (such arguments are generally described as “without loss of generality” reductions).

However, in the absence of such mixing properties, one usually cannot rigorously convert positive average case results to positive worst case results, and when the worst case result is eventually proved, it is often by a quite different set of techniques (as was done for instance with FLT). So it is often better to think of these different types of analysis as living in parallel, but somewhat disjoint, “worlds”. (In additive combinatorics, there is a similar distinction made between the “100% world”, “99% world”, and “1% world”, corresponding roughly to worst case analysis and the two variants of average case analysis respectively, although in this setting there are some important non-trivial connections between these worlds.) In the specific case of the Collatz conjecture, the only obvious invariance property is that coming from the Collatz map itself ( $N$ obeys the Collatz conjecture $\mathrm{Col}_{\min}(N)=1$ if and only if $\mathrm{Col}(N)$ does), but this seems too weak of an invariance to hope to obtain worst case results from average case ones (unless the average case results were really, really, strong).

11 September, 2019 at 4:42 am

Buzzman

Let $u$ and $v$ denote the odd and even parities, respectively, of the terms in the Collatz orbit $\{N, \textnormal{Col} (N), \ldots, \textnormal{Col}^{n}(N)\}$ , where $n=u+w$ . Define $\delta = \log_{2}(3)-1$ such that

$f_{n,u}(N) = \sum_{i=0}^{u} \binom{n}{i}$ ,

where $u =\lfloor (n+1) / (\delta +1) \rfloor$ with the floor function being a stopping time criterion. Parenthetically, one can also express $f_{n,w}(N)$ taking $w = \lfloor \delta (n+1) / (\delta +1) \rfloor$ . Then a simple proposition for $N \in \mathbb{N}$ satisfying the “almost all” argument, in the sense that $\textnormal{Col}_{min} (N) < N$ , is of the form

$F_{n,w}(N) = \dfrac{2^{n}+f_{n,w}(N)}{2^{n+1}}$ ,

where $F_{n,w}(N) \to 1$ as $n \to \infty$ . Observe that $F_{n,w}(N)$ decomposes into $1/2$ probability for $N$ even and $f_{n,w}(N)/2^{n}$ for $N$ odd. The same argument applies for $F_{n,w}(N)$ if one takes $f_{n,w}(N)$ . Exceptional cases are due mostly to $N \equiv 7\pmod{8}$ or when such $N$ are iterates of $N \equiv 1, 3, 5 \pmod{8}$ .

11 September, 2019 at 7:15 am

suitably impressed

That’s a wonderfully clarifying set of remarks, that deserves promotion to a blogpost of its own.

14 September, 2019 at 9:39 am

random reader

In addition to Terry’s (amazing) remarks on worst vs average case, the methodological distinctions between qualitative vs quantitative, and constructive vs nonconstructive, are further dividing lines that are predictive of when the proof of a weaker result can be re-used in a proof of a stronger result.

As in the worst vs average, unless there is some transference principle to go from one side of the divide to the other, methods and results on the weak side will typically be dis-similar to those on the strong side.

The example of Faltings’ theorem (Mordell conjecture) was a good one. It is a qualitative result, finite number of rational points, with no bound on the size of the solutions. Finding all of the rational points on specific curves, and proving that those are all the solutions, is superficially a similar problem but in practice uses different techniques than Faltings.

14 September, 2019 at 11:17 am

Terence Tao

One further addendum: even when there are no direct transference results between different “worlds” of result types, and even when the methods of proof in different worlds are quite distinct, one can still use the relative difficulty between results in one world as a predictor of the relative difficulty in another world. For instance, suppose that two similar-looking statements $X$ and $Y$ , with the “almost all” versions of both $X$ and $Y$ known, but the “all” versions of both statements not known, then there may be no way to transfer the almost all theorems and methods to the all setting. But if the almost all version of $X$ was more difficult to establish than the almost all version of $Y$ , then it is then reasonable to predict that the “all” version of $X$ will similarly be more difficult to establish than the “all” version of $Y$ .

14 September, 2019 at 12:16 pm

random reader

To formalize: comparative difficulty tends to transfer along (both the horizontal and vertical directions of) the commutative diagrams we call “analogies”.

Speaking of transference principles, having arbitrarily slow unbounded functions seems similar to the principle in nonstandard analysis that infinite (nonstandard) objects are equivalent to unbounded sequences of finite/standard objects, e.g., over/under-spill, or the translation between nonstandard and epsilon-delta definitions in calculus. Here there is no obvious transference from arbitrarily good almost-everywhere asymptotic bounds to a finite bound holding a.e., but are there similar situations in analysis where the finite a.e. statement (the equivalent in this context of “almost all integers go to 1 under the Collatz iteration”) is actually known to be false?

14 September, 2019 at 6:00 pm

Terence Tao

One can easily cook up examples. For instance, for any function $f: {\bf N}+1 \to {\bf R}$ that goes to infinity, one can easily show (using the Weyl equidistribution theorem) that $1/\{ \sqrt{2} N \} \leq f(N)$ for almost all $N$ (in the sense of natural density), where $\{x\}$ is the fractional part of $x$ , but there is no bound $C$ such that $1/\{ \sqrt{2} N \} \leq C$ for almost all $C$ . (Instead, the previous claim is equivalent to the assertion that for each bound $C$ , the bound $1/\{ \sqrt{2} N \} \leq C$ holds for a set of $N$ of density that depends on $C$ , but goes to 1 as $C \to \infty$ .)

14 September, 2019 at 1:47 pm

random reader

This is turning into a very interesting side discussion making (somewhat) precise what is normally unwritten folk wisdom. To that end I’ll add an addendum to Terry’s addendum on relative difficulty.

The informal judgement that result X is harder to prove than related (e.g., weaker) result Y, often rests on the use of particular advanced tools as modules in the proof of X and not Y. Typical examples:

X requires explicit error estimates in the prime number theorem (or some analytic property of the Riemann zeta function), but Y only uses the infinitude of prime numbers.

X uses the Weil conjectures or things only known to follow from those, but Y only uses Lang-Weil estimates for the number of points on varieties mod p.

X uses the classification of finite simple groups, Y uses basic representation theory of finite groups.

X uses algebraic K-theory, Y uses De Rham cohomology on smooth manifolds.

In many cases of this sort, the machinery used in X is a black box, effectively an extra set of axioms. So X is from this point of view a result in a stronger formal system (as long as one does not resort to re-proving from scratch results equivalent to the black box) than the one used to prove Y, and the comparison of difficulty becomes similar to that of results proved with and without a particular axiom (e.g., the Axiom of Choice, or Excluded Middle). This makes the comparison closer to the constructive/nonconstructive distinction, polynomial vs exponential time for algorithms, and independence results in logic where the weaker system simply cannot prove a particular theorem. Also, there is often a sort of “reverse mathematics” where a cluster of X-like results all imply or are implied by the advanced module used to prove X (analogous to the polynomial reductions in NP completeness), or are equivalent to each other, giving evidence that the heavy machinery is really necessary.

1 June, 2020 at 2:59 pm

Vincent

Sir what is formular of collatz conjecture

3 June, 2020 at 9:40 am

Michael M. Ross

Look beyond the conventional formula. The conjecture can be simplified to this:

Given three arithmetic operations:

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

For every odd input integer n, can only one output, a or b or c, be a whole odd number.

If this statement is true, the conjecture is true. (It would take too long to explain why, but it’s certainly not higher mathematics or advanced number theory as I see it.)

28 December, 2019 at 5:28 pm

michaelmross

Nevertheless, the foundation of the conjecture is facile:
“All 3x+1 sequence steps for odd ns are equivalent to multiplication by 0.25, 0.75, and 1.5 for n + 1 or n – 1.”
https://www.quora.com/Is-the-Collatz-conjecture-trivial/answer/Michael-M-Ross

28 December, 2019 at 9:36 pm

Anonymous

Your Quora answer is nonsense

29 December, 2019 at 6:39 am

michaelmross

“Utter nonsense”, said Wittgenstein of Cantor :)

29 December, 2019 at 3:41 pm

Anonymous

Sounds like a fair comparison to me

25 February, 2020 at 1:36 pm

Alberto Ibañez

I can’t visualize what the worst case form for a Collatz dynamic might be. Is it possible that it is where the number of even steps is equal to or close to that of even steps?

5 May, 2020 at 12:31 pm

Idriss

Somehow using a different method than yours I have achieved a result that is similar in generality. I am curious of your input on it. https://hal.archives-ouvertes.fr/hal-02488108/document

5 May, 2020 at 11:17 pm

Alberto Ibañez

Hello @ Idriss, I don’t know if your comment is for someone in particular. I have read your paper, but I need time to understand it well with my basic mathematics. If you are interested in my opinion, I think we are in the scenario that “all orbits, even the worst possible, are bounded, either up to 1, or up to n”.
No orbit, infinite n, can escape infinity.
Well, for all odd n, n + 1 is even, in the form $a \ times 2 ^ {x}$ , and in a Col2 map, in x steps, it is even, therefore, at least the number of divisions by 2 is greater than the number of multiplications by 3, if k is the number of odd steps, multiplications by 3, and y is the number of even steps, divisions by 2, for all n, when k tends to infinity, y is much greater than k, and y – k tends to infinity, and no orbit escapes infinity, then it tends to 1, it has negative drift, or it tends to n, it would enter periodic orbit.

27 November, 2020 at 6:48 am

Idriss

I have attempted a completely different approach http://idrissaberkane.org/wp-content/uploads/2020/11/Endomorphisms_of_the_Collatz_quiver.pdf

10 September, 2019 at 11:29 am

Pete

To give a different viewpoint..
Today, immediately after you conjecture ‘all X satisfy..’ you would want to at least heuristically convince yourself that your conjecture holds for almost all X (ideally with a few different random models).
But suppose you prove ‘almost all X’ for some reasonable random model. Is this good evidence that ‘all X’? Well, for a (obviously stupid) example, you might conjecture every $n$ -vertex graph with minimum degree $\sqrt{n}$ is Hamiltonian. This is false – but true a.a.s. for a bunch of natural random models. The proofs that the random models are a.a.s. Hamiltonian, though, use the randomness in a very essential way.

On the other hand, suppose I prove that ‘all X such that horrible structural condition’. If ‘horrible structural condition’ happens to hold for almost all X (for some reasonable model) then I’m likely to title my paper ‘Almost all X…’ simply because it sells better. Such a proof quite possibly could be useful in a proof of ‘all X’; maybe later I (or someone) can weaken the horribleness and deal with the remaining cases.

Short version: no rigorous connection, but if you look at the proof of ‘almost all’ you may sometimes find it is useful.

7 October, 2019 at 3:59 pm

not all graphs are like that

Random (“almost all”) behavior rarely predicts extremal (“all”) behavior for graphs, unlike the situation in number theory.

For the integers the random models of primes, Diophantine equations, Collatz, class groups, etc are all pretty good at making predictions that seem correct empirically and can sometimes be proved by (much harder) deterministic methods. Often even a very naive model is informative, as in the discussion in this comment section of whether “negative drift” is potentially enough to make general Collatz type iterations go bounded.

The extremal problems for graphs maybe resemble more the “irregularity of distribution” questions for primes, i.e., how far can things diverge from the predictions of the random model.

28 December, 2019 at 11:12 am

Jackson

I have created the proof for this. I tried email professors, but no response. If you have suggestions, let me know.

10 September, 2019 at 11:17 am

omarleoblog

The teorem of the conjecture is very awesome. Maybe because the teorem has a lot of results.

10 September, 2019 at 12:13 pm

Terry Tao partial results on Collatz conjecture

[…] Tao announced today that he has new partial results toward proving the Collatz conjecture. His blog post and arXiv paper are both entitled “Almost all Collatz orbits attain almost bounded […]

10 September, 2019 at 12:45 pm

Частичные результаты Терри Тао о гипотезе Коллатца {/} For coders {}

[…] результаты в доказательстве гипотезы Коллатца. Его Сообщение блога а также бумага arXiv оба имеют название «Почти все […]

10 September, 2019 at 2:22 pm

Anonymous

It seems that in the summands of (2) a second probability symbol $\mathbb P$ is missing.

[Corrected, thanks – T.]

10 September, 2019 at 5:17 pm

Anonymous

“in the sense of logarithmic density”
I do not understand this. Could you please explain this?

10 September, 2019 at 8:17 pm

Lior Silberman

Let $A\subset\mathbb{N}+1$ be a set of positive integers. We measure its “natural density” as follows: we impose a cutoff $x$ , and ask: “what proportion of integers up to $x$ are contained in $A$ ?”. If this proportion tends to a limit $\Delta(A)$ as $x\to\infty$ we say that the “natural density” of $A$ is $\Delta(A)$ . In symbols

$\Delta(A) = \lim_{x\to\infty} \frac{\# \left(A\cap[1,x]\right)}{x}\,.$

This notion of “density” gives each integer an equal weight. We can define a new notion of “size” by giving the integer $n$ the weight $\frac{1}{n}$ . We would then measure the “proportion” of the interval $[1,x]$ occupied by $A$ by the following fraction:

$\frac{\sum_{n\in A, n\leq x} \frac{1}{n}}{\sum_{n \leq x} \frac{1}{n}}\,.$

Suppose now that this ratio tends to a limit $\delta(A)$ as $x\to\infty$ . Note that the denominator (a partial sum of the harmonic series) is very close to $\log x$ . We therefore have

$\delta(A) = \lim_{x\to\infty}\frac{\sum_{n\in A, n\leq x} \frac{1}{n}}{\log x}\,.$

This limit (if it exists) is called the “logarithmic density” of $A$ (note the logarithm in the denominator).

10 September, 2019 at 8:39 pm

Alex Jones

Fix a property $P$ that a positive integer $n$ might have. Say $P(n) = 1$ if $n$ has property $P$ and $P(n) = 0$ otherwise. It is said that almost all positive integers (w.r.t. logarithmic density) have property $P$ if $\lim_{N \to \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{P(n)}{n} = 1$ .

10 September, 2019 at 8:25 pm

Lior Silberman

On page 2 of the paper (definition of logarithmic density) you have “for all $A\subset S$ where you probably mean “for all $A \subset\mathbb{N}+1$ .

[Thanks, this will be corrected in the next revision of the ms. -T]

10 September, 2019 at 9:29 pm

Anonymous

Thank you for your reply !

10 September, 2019 at 10:39 pm

Buzzman

Your formulation takes $Col(N)=3N+1$ if $N$ is odd and $N/2$ if $N$ is even. There should be appropriate clarification when citing previous results based on $Col(N) = (3N+1)/2$ if $N$ is odd.

11 September, 2019 at 1:24 pm

Terence Tao

I refer to this acceleration of the Collatz map as $\mathrm{Col}_2$ in the paper. It is not difficult to see that $\mathrm{Col}_{\min}(N) = (\mathrm{Col}_2)_{\min}(N)$ for all $N$ , so all the results in the literature concerning $\mathrm{Col}_{\min}$ hold without any changes if one works with $\mathrm{Col}_2$ instead.

11 September, 2019 at 8:12 pm

Buzzman

I see now. And I can only smile at how shallow I can be, but always fervent at learning your depth. Thanks.

11 September, 2019 at 3:27 am

Anonymous

It seems that in definition 1.2 In the arXiv paper, $A \subset S$ should be $A \subset R$

[This will be corrected in the next revision of the ms, thanks -T.]

11 September, 2019 at 4:15 am

Anonymous

In definition 1.7 it seems clearer to replace $\mu \geq 1$ by the strict inequality $\mu > 1$

[This will be corrected in the next revision of the ms, thanks -T.]

11 September, 2019 at 7:17 am

David

It would obviously be nice to extend the result to showing that $\mathrm{Col}_{\mathrm{min}}$ was bounded on almost all integers. Having toyed around with this result for a bit, it seems that you clearly can’t have a positive logarithmic density subset on which $\mathrm{Col}_{\mathrm{min}}$ limits to infinity (because then you can set $f(n) = \mathrm{min}_{x \geq n, x \in N} \mathrm{Col}_{\mathrm{min}}$ and some element will have to be bounded by its own $\mathrm{Col}_{\mathrm{min}}$ value.)

However, it feels hard to construct such a set even if you assume the stronger result for a contradiction. Is there a good reason for an obstruction to this method?

11 September, 2019 at 7:36 am

David

More specifically, are there well known examples of functions of $\mathbb{N}$ which are not bounded (more weakly) on any subset of positive density or (more strongly) on almost all integers and yet have no positive density subsets on which the function goes to infinity?

11 September, 2019 at 1:44 pm

Terence Tao

If there is no set of positive density on which a function $f$ is bounded, then for each threshold $C_0$ , the set $\{ N: f(N) \leq C_0 \}$ must necessarily be of zero density, and a standard diagonalisation argument then shows that $f(N) \to \infty$ outside of a set of density zero.

11 September, 2019 at 1:37 pm

Terence Tao

This is discussed in Remark 1.4 of the paper. The best one seems to be able to do with the methods in the paper is to show that for each $C_0 > 0$ , one has $\mathrm{Col}_{\min}(N) \leq C_0$ for a set of positive integers $N$ of logarithmic density $1 - O( \log^{-c} C_0 )$ for some absolute constant $c>0$ (though there is some hope of reducing the error $\log^{-c} C_0$ a bit). In particular, for sufficiently large $C_0$ , one can show $\mathrm{Col}_{\min}(N) \leq C_0$ for a positive logarithmic density set of integers; in principle, this could be combined with a numerical verification of cases up to $C_0$ to obtain the result that the Collatz conjecture held for a set of positive logarithmic density. (Thanks to Ben Green for pointing out this possibility to me.) Unfortunately the value of $C_0$ produced by the arguments in my paper, while in principle explicit, are almost certainly too enormous for this strategy to be easily implemented, but perhaps some variant of the methods in my paper could be used to achieve this.

11 September, 2019 at 12:59 pm

David Lowry-Duda

I haven’t had the time to work out the details, but it seems to me that much of what you’ve written would apply for something like the 5n+1 variant of the Collatz conjecture. I wonder if it is also true that almost all (5n+1)-collatz orbits attain almost bounded values?

I think this would be a bit interesting since it is believed that there are orbits in the (5n+1)-collatz problem that get arbitrarily large.

Does this happen to be something you have thought about?

11 September, 2019 at 1:33 pm

Terence Tao

The argument relies in many places on the inequality $\frac{\log 3}{2 \log 2} < 1$ , to ensure that the Collatz iterations have average negative logarithmic drift. Since $\frac{\log 5}{2\log 2} > 1$ , I would instead expect the reverse to be true for the $5n+1$ map, namely that almost all $5n+1$ iterates would escape to infinity. (Unfortunately the method of proof in this paper won’t extend to this case, as the probability measures are now being stretched into ever larger regions of space rather than being compressed into ever smaller regions, and one can’t hope to keep the probability measures stable in total variation in the former case.)

11 September, 2019 at 5:00 pm

David Lowry-Duda

Aha, I understand. Thank you.

14 September, 2019 at 7:31 am

oculus drift

Is the negative-drift condition enough to get the same type of result for generalized Collatz recursions (finite partition of N into arithmetic progressions with a linear function on each progression)? i.e. if the map heuristically pulls integers toward 1 on average, then the almost everywhere quasi-boundedness holds. It’s hard to hope for anything more than that, and the statement is not so strong as to contradict the undecidability of such recursions in general.

14 September, 2019 at 8:33 am

Terence Tao

This is a very good question. One has to be careful however to define “negative drift” properly – a naive definition can give incorrect predictions. For instance, consider the map that sends $n \mapsto 2n$ when $n = 0 \hbox{ mod } 10$ , and $n \mapsto \frac{n-j}{10}$ when $n = j \hbox{ mod } 10$ for $j=0,\dots,9$ . A typical number $n$ has a 90% chance of being reduced in size by 10 by this map, and a 10% chance of doubling, which would naively suggest a negative drift, but in fact pretty much all orbits get sent to infinity, because they almost certainly meet the $0 \hbox{ mod } 10$ residue class at some point, at which point they grow exponentially.

Perhaps to define negative drift properly one has to define the dynamics on the profinite integers $\hat {\mathbb Z} = \prod_p {\mathbb Z}_p$ instead of the natural numbers (actually one should not need to use all primes here, only the primes that show up in the modulus of the residue classes and in the linear coefficient $a$ of the affine maps $n \mapsto an+b$ should be relevant, for instance for Collatz it is the dynamics on ${\mathbb Z}_2 \times {\mathbb Z}_3$ which is relevant). If the dynamics on $\hat {\mathbb Z}$ maps Haar measure towards an ergodic invariant probability measure $\mu$ then one can then define the drift to be the mean value of $\log a$ with respect to this measure, and one could tentatively conjecture that the results of my paper would extend to any dynamics with an ergodic limiting measure with negative drift. For instance in the case of Syracuse the attracting measure $\mu$ on ${\mathbb Z}_2 \times {\mathbb Z}_3$ is the law of $(\mathbf{X}_2, \mathbf{X}_3)$ , where (in the notation of the paper) $\mathbf{X}_2, \mathbf{X}_3$ are independent random variables with the laws of $\mathbf{Haar}(2\mathbb{Z}_2+1), \mathbf{Syrac}(\mathbf{Z}_3)$ respectively; if one includes other primes $p \neq 2,3$ then one just adds on independent copies of $\mathbf{Haar}(\mathbb{Z}_p)$ . Here the drift is $\log \frac{3}{4}$ . (If one uses the original Collatz map rather than the Syracuse acceleration then the invariant measure is somewhat more complicated to describe; roughly speaking it is $2^{\mathbf{n}} (\mathbf{X}_2, \mathbf{X}_3)$ , where $\mathbf{n}$ is a non-normalised uniform probability kernel on the natural numbers independent of $\mathbf{X}_2, \mathbf{X}_3$ , conditioned to the event $\mathbf{n} \leq \mathbf{Geom}(2)$ for a geometric random variable $\mathbf{Geom}(2)$ independent of all previous variables.) By the ergodic theorem, negative drift would imply that almost all profinite integers would exhibit orbits whose cumulative linear multiplier would go to zero in the Archimedean sense, which would heuristically support almost all orbits becoming bounded.

One interesting question would be to see if one can construct an iteration that had negative drift in the above sense, but which still had at least one unbounded orbit. I don’t think the Conway-style FRACTRAN iterations can achieve this, but perhaps some more subtle variant of them can.

14 September, 2019 at 10:34 am

random reader

The nondegeneracy condition seems to be that the associated finite Markov chain has a single ergodic component (ie., strongly connected subgraph of recurring states) and then the contraction/expansion factor should be the same as on the adelic thing. I am assuming here that, taking N = product of all the primes (each to the largest power it occurs in the congruence moduli, numerators and denominators of the linear maps), there is a suitable and not too complicated sense in which the iteration is a Markov chain whose states are “randomly chosen integers in one residue class mod N”, which would be a restatement and formalization of the probability heuristic, and then to use that chain to calculate the contraction factor.

Assuming that this could be done, is it plausible that your methods adapt without major new ideas to the general iteration, or are they tied in some way to the map being 3x+1?

A related question (to assess dependence on 3x+1 versus variants with the same contraction factor) is the adversarial 3x+1 problem. The Collatz iteration, but sometimes changed to 3x+A where A is chosen each time from a given finite set of alternatives (such as anything from -10 to +10). If an adversary can change 100 percent, or 1 percent, or O(log n), of the applications of 3x+1 to (3x+A)’s, can it force the iteration to go unbounded? If the adversary always has enough freedom to force divergence, is that still true if the choices of A’s are require to equal, in average, the A in the iteration (such as +1 for Collatz) or to concentrate suitably around that number?

14 September, 2019 at 5:50 pm

Terence Tao

I think it would be non-trivial, but perhaps possible, to extend the arguments in this paper to this more general setting. The original Collatz problem has a nice property that I rely on somewhat heavily in my paper, namely that the iteration is controlled entirely by the 2-adic nature of the starting point, but the irregularities of distribution caused by the iteration only manifests in the 3-adic statistics. (In particular, there is a key use of the Chinese remainder theorem in the proof of Lemma 5.2 that basically relies on this decoupling between the controlling coordinates and the irregularly distributed coordinates.) For more general Collatz-type systems this would not be the case and the analysis may become somewhat more difficult (though perhaps not completely intractable).

I would imagine that an adversarial model could flip a negative drift model such as the original Collatz to a positive drift one given enough options available to the adversary, which would provide heuristic justification at least for unbounded orbits.

14 September, 2019 at 6:58 pm

random reader

Thanks for that inspiring answer (and the blog that makes such Q & A possible). It sounds like either the full generalization is attainable, or there are very interesting things to learn about the decoupling property and its extensions and possible role as a (dis)obstruction.

14 September, 2019 at 11:41 pm

Alberto Ibañez

Despite having no prestige to lose, I do not want to interfere in your great work with my comments of, surely, low quality, but in turn, I think it is time to try to expose my intuitions about the conjecture. When you talk about “nondegeneracy condition” it is because the conjecture avoids this condition or seeks it. I say this because if it is possible to represent the binary relations of the function in some way, we would obtain an infinite Boolean matrix, and apparently, it must be singular or degenerate. “Singular matrices are rare in the sense that a square matrix randomly selected from a continuous uniform distribution on its entries will almost never be singular.” (Wikipedia).If this is so, and if the conjecture is true, it is precisely because the function 3n + 1, and apparently perhaps only it, manages to avoid the kind of residue 0 mod 3 and at the same time from an initial N, also manages to avoid the residue class 0 mod N.If this is so, and if the conjecture is true, it is precise because the function 3n + 1, and apparently perhaps only it, manages to avoid the kind of residue 0 mod 3 and at the same time from an initial N, also manages to avoid the residue class 0 mod N. These characteristics prevent get trapped in a periodic orbit. In the 5n + 1 conjecture, we know that certain numbers fall into periodic orbits and, I don’t know if by chance, but at least a multiple of 3 is involved. Perhaps this condition is what makes it impossible for any multiple of 3 to fall into a periodic orbit, and perhaps the truth of the conjecture is here because it is the multiples of 3 that enable the possibility of entering a periodic orbit.
Maybe I extend too much, but I want to take the opportunity to ask if Professor Tao’s strategy would change if instead of using mod 3 ^ n, would use mod N, where N is the starting point, to see if zero residue mod N is avoided.
Another question I wanted to ask is whether it is interesting or possible to try to prove that if we assume that no N falls into a periodic orbit, it could be shown that no N escapes to infinity, and therefore the truth of the conjecture would depend solely on demonstrating that no it is possible to fall into a periodic orbit. Thanks.

11 September, 2019 at 11:10 pm

Anonymous

Dear Sir.Tao,
Thanks you very much,
We are in a math conference in our country now. We are talking about you very much. We expect you have a hattrick in September, 2019 with Twin primes conjecture, Goldbach conjecture beside above Collatz conjecture.
Best wishes,

11 September, 2019 at 3:50 pm

Ridiculous Amateur

I’m an amateur who didn’t take any math beyond undergrad and so *surely* I will embarass myself here, but I’ve come back to Collatz a lot over the years and I always feel like I’m stumbling somewhere near the answer.
If we can show that repeated application of Col() to any N > 1 will always eventually produce an integer < N (‘reduce’), that removes both the possibility of any other orbits and the possibility of unbounded growth in one go. Easier said than done, but that one property is all we need.
So what I do next is start carving up N into constructible categories that reduce, thereby chipping away at the space where a counterexample could exist.

Obviously even N reduce immediately and need no further consideration.
Fairly trivially, N of the form 4k+1 reduce in 3 applications of Col(), since 4k+1 is necessarily odd, 3 * (4k+1) + 1 = 12k + 4 which is divisible by 4 and so halves twice to yield 3k + 1. 3k + 1 > 4k + 1, so we reduce.
That’s now 3/4 of all N that reduce! Wow, we’re really cooking! Duh, the constructions get hairier from here, but there’s still a pattern hiding in there.

Skipping over the repeated applications and just listing some reductions with (the proportion of N now shown to reduce) and [H]alve and [M]ultiply sequence, we have:
2k -> k (1/2)[H]
4k + 1 -> 3k + 1 (3/4) [MHH]
16k + 3 -> 9k + 2 (13/16) [MHMHHH]
32k + 11 -> 27k + 10 (27/32) [MHMHHMHH]
32k + 23 -> 27k + 20 (28/32) [MHMHMHHH]
128k + 7 -> 81k + 5 (113/128) [MHMHMHHMHHH]
128k + 15 -> 81k + 10 (114/128) [MHMHMHMHHHH]

This is hardly comprehensive, but continuing to fill these out will inch us closer and closer to showing ‘all N’ reduce and if along the way somebody sees a hidden relation or pattern we can close the whole thing.

What I see is that the power of 2 acts as the left-hand coefficient and represents the number of ‘halving’ applications of Col() and the right hand power of 3 is the ‘multiplying’ applications of Col(). We know the power of 2 is always such that the result is greater than the power of 3 on the other side. Any less and it wouldn’t be a reduction, any more and we would have ‘passed’ the reduction.
This means some powers of 2 will never show up, because there’s no available power of 3 for them to reduce. Any 8k + x is more-than-reduced from a 3k + y form, and insufficient to reduce a 9k + y form.
So we can trace out the ‘possible’ forms by examining the relationship between growth of powers of 2 and 3. We know how many M/H operations will happen and it’s only the order that can change.
The possible orderings are bounded by needing to always follow M with H and needing to ‘spread out’ the H operations so as to not overcome the M until the end. The k term remains even until the final application of Col().
So that leaves the constant term to ‘select’ the order within the valid options – or the order to select the constant, however you want to view it.

Even if this approach *doesn’t* reveal any fundamental truth or provide unique insight to solve the problem, it *does* allow a computer program to very quickly prove an arbitrary fraction of possible N reduce, which is much better than counting and testing individual numbers.

12 September, 2019 at 4:06 am

Terence Tao

I think you may be on your way to rediscovering the arguments and results of Terras (link to article here). In the language of this blog post or my paper, the conclusion is that $\mathrm{Col}_{\min}(N) < N$ for almost all $N$ (in the sense of natural density). It is true that if one could in fact show that $\mathrm{Col}_{\min}(N) < N$ for all $N>1$ (not just almost all), this would resolve the Collatz conjecture, but this is one of these situations where there seems to be an enormous gap in difficulty between “almost all” results and “all” results.

14 September, 2019 at 12:14 am

Anonymous

Suppose that a function $f$ from $\mathbb N$ into itself has the property that if $Col_{min}(N) 1$ then Collatz conjecture would follow. Is $f(N) = N$ the smallest function with this property?

[It appears that your comments are being parsed incorrectly due to the use of < and > symbols that are parsed as HTML tags. Use < and > instead -T.]

14 September, 2019 at 12:43 am

Anonymous

Somehow (perhaps because of the symbol 1$ can be relaxed to a function $f(N) \geq N$ while still implying the Collatz conjecture?
Is it possible that there is such $f(N)$ whose growth is faster(!) than N?

[It appears that your comments are being parsed incorrectly due to the use of < and > symbols that are parsed as HTML tags. Use < and > instead -T.]

14 September, 2019 at 9:18 am

Anonymous

Suppose that a function $f : \mathbb N \to \mathbb N$ has the property that $Col_{min}(N) < f(N)$ for all $N > 1$ implies Collatz conjecture. Is there such $f(N)$ (with this property) whose growth to infinity is faster than $N$ ?

14 September, 2019 at 9:57 am

Terence Tao

Well, one trivially has the bound $\mathrm{Col}_{\min}(N) \leq N$ , so this question is equivalent to the full Collatz conjecture.

18 September, 2019 at 2:04 am

Alberto Ibañez

The difference between “almost all” and “all” , can be infinite or can you establish that there is a finite number of counterexamples? I say it because if there is an orbit that escapes to infinity, it has infinite n odd ones, in addition to its 2 multiples. But if you can be established that the number of counterexamples must be finite, there can be no orbits that escape to infinity.

18 September, 2019 at 4:41 am

Jef

Back to 3x-1, what percentage of the natural numbers map to 1 as opposed to 5 and 17 combined?

18 September, 2019 at 9:23 am

Craig

Doing a quick spreadsheet calculation, I found that for the 3x-1 conjecture, of all numbers from 1 to 10,000, 3,244 numbers eventually reach 1, 3,213 numbers eventually reach 5, and 3,543 numbers eventually reach 17.

So it’s about one third going to 1, one third going to 5, one third going to 17.

18 September, 2019 at 11:33 am

Alberto Ibañez

Dear Jef. I liked to study the 5n + 1 variant to know why the conjecture fails, especially as regards the periodic orbits. The orbits that escape to infinity do not understand them very well, although both, seen from the inverse maps, apparently are orbits, or numbers, that are not generated from 1, so they never reach 1, from the original map. I have not studied the 3n-1 map, but I understand that it fails like 5n + 1, or is it interesting for something else other than being the original with the changed sign?

19 September, 2019 at 5:36 am

Jeff

Alberto,

Crandall’s 1978 paper in Mathematics of Computation has what you are looking for. His qx+1 problem.

You’ll see cycles correspond with solutions to Diophantine equations.

The most fascinating aspect about these problems is the hypothetical existence of divergent sequences. Forget the confusing terminology of orbit and trajectory etc.

19 September, 2019 at 1:44 pm

Alberto Ibañez

I have read Crandall’s 1978 paper and like the recent paper of Professor Tao, I can follow the plotline, but I cannot follow the demonstrations, which are well above my level. How does Collatz’s conjecture relate to diophantine equations if the conjecture is true?That’s why I try to take the guess to places I can understand, simple places. On equivalent problems of the form qx + r, sometimes we forget the importance of the function n / 2 for the peers. In the previous post of the professor, I leave a comment that talked about how I see the conjecture. When applying n / 2 we divide N into an infinite collection of disjoint infinite subsets/subgraphs, whose root is an odd number, of the form n and its 2 multiples. When you apply the function of the qx + r form, you are choosing how or where you want these subsets/subgraphs to join. Depending on the form you choose, you will get different results. For almost everything N, when you use the 3n + 1 function, you can avoid creating periodic loops, and that the resulting graph is a single graph weakly connected and oriented to 1. But I cannot visualize how an orbit could escape to infinity, since that every odd number connects to the graph. Analyzing this graph, it seems that several things can be deduced as if all N is connected, it is as if there is a single congruence class, and if it is possible to create the characteristic matrix, the vectors that form it are lineal dependent, that is, Its determinant is 0. Since it is an infinite matrix, it seems that it would be necessary to know if it is possible to explore the functional determinant of this infinite matrix via the zeta function of the operator.
Speaking of the property of the resulting graph, the property of the graph is weakly connected, it seems to have some connection with the property of being simply connected in the Poincare conjecture. In his paper, the professor speaks of triangles, although I do not understand the meaning. I have tried to see the conjecture in the unit circle, where a rectangular triangle is formed whose hypotenuse measures 3n + 1, the cosine is 3n and the versine is 1. For true, the value of all the hypotenuse 3n + 1 is of form 4 + 6x, (in the conjecture 5n + 1 would be 6 + 10x) where x is the ordinal of n odd. If the conjecture enters periodic orbit the value of this hypotenuse would reach from an initial n value, the value n * 2 ^ x, or the versine would have to be a multiple of n.when the value of the hypotenuse is a power of 2, then From a cosine triangle 3n, several triangles will have been formed that finally reduce to the triangle h = 4, cosine = 3 and versine = 1 and to point 1. In my words there is not much mathematical rigor, only intuition, that there is some detail that escapes us, to be able to demonstrate that cannot fall into a periodic orbit.

19 September, 2019 at 2:10 pm

Jeff

Alberto,

I spent years reading and re-reading Crandall’s paper. It is hard to follow, and it was his first publication. Not even in his field. Think he earned a degree in physics. But the answers you seek are in it.

As far as this ms is concerned. There isn’t anything rigorous about it when applied to 3x+1. Most of Crandall’s results are rigorous. It’s up to the reader to decide which ones, the journals are not perfect. Blogs like this one certainly have the potential to help.

Yes it is hard to imagine what a divergent sequence looks like. Take another look at the formulas in Crandall’s paper.

20 September, 2019 at 7:10 pm

Robert Frost

I rather feel the number of congruence classes which reduce is infinite in number, so you could continue for a long time and still not classify them all. Then the requirement would be to find the symmetry by which these classes are generated and show then that there is an induction which accounts for them all. The character of this induction however is complex, going up to N^N, each step being of one dimension greater than the previous. Such an approach leads into the theory of Borel sets, measure theory, sigma algebra… which is as far as I have got in that direction.

The best result I saw of your form took this so far as to show that proving any one class congruent to 1 mod 2^n converges, is equivalent to the conjecture. If that result can be metrized and used to show convergence to $1 \pmod 2^\infty$ in the 2 adic space is sufficient, this proves the conjecture, and IMO that is the closest I ever saw anybody get.

11 September, 2019 at 5:34 pm

Almost all Collatz orbits attain almost bounded values – INDIA NEWS

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

11 September, 2019 at 8:12 pm

Anonymous

1） almost all {N} (in the sense of natural density)
2） almost all {N} (in the sense of logarithmic density).
1) is not equivalent to 2）？

12 September, 2019 at 3:59 am

Terence Tao

If a property holds for almost all $N$ in the sense of natural density, then it also holds for almost all $N$ in the sense of logarithmic density (this is a good exercise in summation by parts). However, the converse is not always true. For instance, the property of not having a number of digits that is a perfect square (that is, not lying in any interval of the form $[10^{n^2-1}, 10^{n^2}-1]$ ) holds for almost all $N$ in the sense of logarithmic density, but not in the sense of natural density.

13 September, 2019 at 1:03 am

Alberto Ibañez

First of all, congratulations on this new breakthrough. It has made me very happy that you dedicate your time and effort to this conjecture that so many amateurs dream of making some small advance that helps their resolution, although it is evident that the mathematics necessary to solve it are only within the reach of high-level mathematics.
About “…the possibility of some very rare exceptional {n} for which the orbit goes to infinity, or gets trapped in a periodic loop”, from your previous post. How it is now with this new result?, I mean if the possibility is still less yet, or remains the same, but reinforced from a stronger point of view, in the sense of logarithmic density.
About “…the property of not having a number of digits that is a perfect square (that is, not lying in any interval of the form [10^{n^2-1}, 10^{n^2}-1]) holds for almost all N in the sense of logarithmic density, but not in the sense of natural density.”. I wish I could understand, is there a simple way to explain this?. Thank you. (Written with the help of Google translate and Grammarly)

13 September, 2019 at 7:11 am

Terence Tao

One can use the arguments in the paper to show that the set of points that are in a periodic loop have zero density (in fact the set of exceptions up to $[1,x]$ is of size $O(x^{1-c})$ for some $c>0$ ; I will sketch the argument in the next revision of the ms. However, the arguments do not say anything directly about the proportion of points whose orbit will eventually be trapped in a periodic loop, or will eventually go to infinity; the analysis in the paper can control most initial values to the point where they can be carried very close to $1$ , but after that they are free to either get sent to $1$ , get trapped in some other periodic loop, or go to infinity, and I don’t see any rigorous tools to determine which of these is the most probable outcome.

The verification of the claims about natural density and logarithmic density are a good exercise in computing sufficiently good upper and lower bounds on various averages. The continuous version of the exercise might be a good warm up for you. Namely: let $E := [0,+\infty) \backslash \bigcup_{n=1}^\infty [10^{n^2-1}, 10^{n^2}-1]$ be the set of positive reals that lie outside the intervals $[10^{n^2-1}, 10^{n^2}-1]$ . See if you can show that (a) the limit $\lim_{x \to \infty} \frac{1}{x} \int_0^x 1_E(t)\ dt$ does not exist, and (b) the limit $\lim_{x \to \infty} \frac{1}{\log x} \int_1^x 1_E(t)\ dt$ does exist and is equal to 1. For (a) one needs to get a lower bound for the average for some values of $x$ and an upper bound for other values of $x$ that are incompatible with the scenario where the limit exists. For (b) one needs upper and lower bounds for the average for all large $x$ that converge to each other as $x \to \infty$ . Using the asymptotic notation $O()$ will make the calculations easier, and drawing pictures of the set (and perhaps of the areas under the curve one needs to integrate) may guide your intuition.

20 September, 2019 at 7:23 pm

robfrot

I often wondered whether there is a contradiction to be had from density arguments, of the form that any counterexample must also have nonzero density. Every counterexample is after all, essentially isomorphic to the known graph, and having a periodic orbit or infinitely ascending sequence rather than a fixed point, is in a sense larger. The suggestion would be to hypothesize another orbit having some least integer n and show that its density in the integers is greater than nonzero.

10 April, 2020 at 9:50 am

Alberto Ibañez

Dear Professor Tao, when you talk about “… the analysis in the paper can control most initial values to the point where they can be carried very close to 1”, does this refer to values greater than 1?

I wanted to present a situation and how it could be interpreted.

One way to express Collatz conjecture is:

$n\times \frac{3^{k}}{2^{y}}+\frac{TCR}{2^{y}}$

for n = odd, where k = odd steps(3n) and y = even steps(n/2)

and TCR are the numbers of the form

$\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}$

Assuming we don’t enter a periodic loop.

If we can demonstrate that when k grows to infinite, and y always grows much more than k, and y-k tends to infinity, (is this a known fact?)

without taking into account the term

$\frac{TCR}{2y}$

Can we affirm that we not only reach a value less than n but less than 1 always?

Once below these values, could they rise above n or 1?

Could we say that if k goes to infinity

$n \times \frac{3^{k}}{2^{y}}$ tends to zero?

If we add the term

$\frac{3^{k-1} 2^{a_1}}{2^{y}} + \frac{3^{k-2} 2^{a_2}+ \ldots }{2^{y}} + \frac{2^{a_k}}{2^{y}}$ , would it still be below n? or above 1?

$\frac{3^{k-1} 2^{a_1}}{2^{y}}$ tends to zero?

$\frac{3^{k-2} 2^{a_2}+ \ldots }{2^{y}}$ tends to zero?

$\frac{2^{a_k}}{2^{y}}$ is always a power of 2?

Can we affirm that when k goes to infinity the conjecture tends to a power of 2?

Thanks.

12 September, 2019 at 5:21 am

Terry Tao: can an approach used to prove almost all cases be extended to prove all cases? – Julia Wolffe's Notes

[…] Terry Tao posted to the arXiv his paper Almost all Collatz orbits attain almost bounded values, which caused quite the stir on social media. For instance, this Reddit post about it is only a day […]

12 September, 2019 at 4:23 pm

Craig

Does the result also hold for the 3n-1 conjecture? (Where the plus is replaced with a minus) This conjecture is known to be false.

13 September, 2019 at 12:57 am

Anonymous

Craig, what do you mean about 3n-1 being known to be false? Is it known to diverge for some n? I just tested it up to 1e8 and found the informal paper http://vixra.org/abs/1610.0106 which claims to have tested it to 1e9. Are there some more publications? It’s surprising that there is not much info about this sequence. It doesn’t seem to have been studied much, but its behaviour superficially resembles 3n+1’s. Wikipedia also says nothing about it.

13 September, 2019 at 4:51 am

Craig

The 3n-1 conjecture does not hold for n=5 an n=17. You get a cycle. It probably never diverges, just like the 3n+1 conjecture.

13 September, 2019 at 6:39 am

Craig

The probable reason why the 3n-1 conjecture is not found so much in the literature is because it is false. But it is very important, since it demonstrates that any proof of the 3n+1 conjecture use the fact that the 3n+1 function has a plus sign and not a minus sign.

13 September, 2019 at 10:29 am

Anonymous

Ok, thanks. I took the 3n-1 conjecture to mean that 1, 5, and 17 were the only cycles, per the vixra paper. A similar thing happens with the 3n+1 conjecture if you allow negative n. There are several known cycles but’s an open question whether there are more.

13 September, 2019 at 11:43 am

Craig

There is nothing stopping a 3n+1 sequence or a 3n-1 sequence from diverging to infinity. That can happen if most of the iterates in such a sequence use the function (3n+1)/2 or (3n-1)/2 instead of n/2. Even though the probability of this happening is nil, it is still possible. Because of this, I can’t see how anyone will ever prove that either sequence cannot diverge to infinity. The best one can do is do what Prof Tao did in his new paper.

13 September, 2019 at 4:43 pm

Anonymous

I’m saying 3n-1 has 3 known cycles, so the 3n-1 conjecture (i.e. statement whose truth value is unknown) would be that all n end up in one of those 3 cycles. The conjecture is false if some number escapes to infinity, or if some number lands in a cycle other than the known 3. Anyway it sounds like that question is still open.

13 September, 2019 at 7:05 am

Terence Tao

One would have to check the details carefully, but on a quick glance it would appear that the main results of my paper would also cover the $3x-1$ iteration, after inserting some minus signs in various places (most notably in the definition of the offset map). Heuristically one would expect all orbits of this iteration to be bounded (and thus eventually periodic), although the precise set of possible limiting cycles is different.

EDIT: One slightly tricky thing is that in the 3x-1 case the analogue offset map $F_n$ would only be expected to stabilise if one fixes the parity of $n$ due to a new factor of $(-1)^n$ in the map. So one may have to only work with even iterates of the analogue of the Syracuse map, rather than all iterates, in order to get around this problem. But this should only require some minor notational complications in the argument rather than necessitate any serious new difficulties.

SECOND EDIT: On further thought, the offset map for the $3x-1$ map doesn’t actually contain a $(-1)^n$ factor, so the arguments should in fact go through without difficulty (indeed, one can think of the $3x-1$ iteration as nothing more than the usual $3x+1$ iteration applied to negative integers). The previous comments would apply however for a $-3x+1$ iteration for instance.

14 September, 2019 at 12:58 pm

Alberto Ibañez

I do not know if I bring some light, but I think that 3n + 1 is symmetric with respect to zero, that is, using negative numbers, to 3n-1, and 3n-1 with positive numbers behaves the same, it is symmetric with respect to 0, to the 3n +1 with negative numbers.

17 September, 2019 at 11:40 pm

Gottfried Helms

This idea of “symmetry” does not really hold. A (somehow) popular equation which must be satisfiable for cycles states $2^S=(3+1/a_1)(3+1/a_2)...(3+1/a_N)$ with $N$ odd steps and $S$ as sum of even steps. Now if you insert positive numbers for the $a_k>1$ then the rhs is between $3^N$ and $4^N-\delta=2^{2N}-\delta$ and if you insert negative numbers then the existence of a perfect power of 2 between $2^N+\delta$ and $3^N$ is another question. Of course we have always latex $N-2$ possible solutions for S between $2^N < 2^S < 2^{2N}$ but it might be, that the value $3^N$ lies such that either there is no perfect power of 2 between $2^N < 3^N$ and instead all $N-2$ perfect powers lay between $3^N < 2^{2N}$ or conversely. So solutions for cycles are *not* symmetric around zero.

17 September, 2019 at 11:58 am

Jeff

So since an infinite subset of the natural numbers map to 5 under 3x-1, almost all leaves that many numbers unaccounted for. Especially when this method sets the target bound of 1!

Basically, 3x-1 gives a concrete example that this ms represents no progress whatsoever on 3x+1. Just like all of the references it cites.

13 September, 2019 at 10:33 am

Жандос Мәмбетәлі

Collatz conjecture in reverse:
Suppose we have such a Collatz fraction:
$\frac{\frac{2^{k_i}-1}{3} \cdot 2^{k_{i-1}}-1}{3}_{{...}_{\frac{\frac{2^{k_2}-1}{3} \cdot 2^{k_1}-1}{3}}}$
which is equal to a natural number. Then, for each power of two $2^{k_x}$ we have many other degrees of the form $2^{k_x+(3^x-3^{x-1})n}$ , $n\geqslant 1, n \in N$ ; any of which can replace the power of two $2^{k_x}$ and get another integer (natural) fractional solution.
$k_1, k_2, ... , k_i$ – Are different natural numbers.
Example:
$k_1=\{0, 2, 4, 6, 8, 10, ...\}$
$k_2=\{2, 8, 14, 20, 26, ...\}$
$k_3=\{2, 20, 38, 56, ...\}$
for: ${\frac{\frac{\frac{2^{k_3}-1}{3} \cdot 2^{k_2}-1}{3} \cdot 2^{k_1}-1}{3}}$ .
Depending on the $n$ , we equate the result of calculating such a fraction to $A_{n_x}$ , then the relations of finite differences $A$ will be:
$\frac{A_{n_x+1}-A_{n_x}}{A_{n_x}-A_{n_x-1}}=2^{3^x-3^{x-1}}$
where $x$ this is a subscript exponent $K$ associated with $n$ , (the index of the power of two of the variable part of the fraction).

13 September, 2019 at 11:20 am

Terry Tao prouve presque la conjecture de Collatz - Technologik.fr

[…] Presque toutes les orbites de Collatz atteignent des valeurs presque limitées (article de blog) […]

13 September, 2019 at 2:32 pm

Anonymous

Is it possible to extend the method for some collatz-like sequences in $\mathcal N^2$ ?

14 September, 2019 at 10:15 am

Has there been any work on quantifying “almost all”? For instance, is it known that there are c, d < 1 such that for large enough N, all but $N^c$ of integers between 1 and N have minimal element of the Collatz orbit at most $N^d$ ?

14 September, 2019 at 5:45 pm

Terence Tao

This particular claim essentially follows from the first part of Proposition 1.11 of my paper (which also applies if the logarithmic distribution is replaced by the uniform distribution). It may have implicitly also appeared in the previous papers of Allouche and Korec mentioned in the paper, though I don’t have those references handy at present.

29 September, 2019 at 12:47 pm

Jeff

Three up votes to one down vote.

3x-1…

Let’s keep the pun and the fun.

14 September, 2019 at 12:37 pm

Anonymous

Is there any probabilistic conjecture on the distribution of the lengths of orbits starting with a given distribution of the initial element of the collatz sequence ?

14 September, 2019 at 5:40 pm

Terence Tao

Yes; see for instance this paper of Kontorovich and Lagarias.

14 September, 2019 at 1:53 pm

Anonymous

Since it is not known if the Collatz conjecure is decidable, the current situation is similar to that of the RH (if it is undecidable then it must be true!)

14 September, 2019 at 2:16 pm

not necessarily

No, because boundedness of individual orbits (unlike RH counterexamples) cannot necessarily be determined by finite calculation. Collatz conjecture, whether that means “all orbits include 1” or “all orbits eventually go below 3 zillion”, could be undecidable because one particular orbit is unbounded, but there is no proof of that in the axiom system chosen as a foundation. If there were a proof that a particular finite algorithm can test any given N for having an unbounded orbit or not, then the problem becomes RH-like in that undecidable implies true (i.e., every N passes the test, so there are no counterexamples, but there is no uniform proof that all N have this property).

15 September, 2019 at 6:19 am

itaibn

If I’m not mistaken, the proof of the prime number theorem can be thought of as first establishing that the prime numbers are on average distributed that way in the sense of logarithmic density, and then showing that the prime numbers are not correlated to any $n^{is}$ and usually Fourier analysis to establish the distribution of the prime numbers in ordinary density. Is it possible that a similar approach here will establish a result like this one but in the sense of ordinary density instead of logarithmic density? Specifically, we can seek out complex measures of the form $f (n) n^{is}$ , where $f$ is continuous in the 3-adic topology, which are eigenfunctions of the dynamics. I believe these measures can be characterized similarly to the Syracuse measure in (1), but with an extra weight $3^{-is} 2^{i (a1 + \dots + a_n)}$ , modulo sign and similar errors. If all the eigenvalues for $s \neq 0$ have norm less than one then we will expect that starting from a uniform distribution these components will become negligible and only the Syracuse distribution will remain.

15 September, 2019 at 6:34 am

Terence Tao

Yes, I believe that some argument along these lines (considering the joint behaviour of the Syracuse iteration in both the “3-adic” and “Archimedean” aspects, by working with a joint character $\chi(n) n^{it}$ instead of just a 3-adic character $\chi(n)$ in Proposition 1.17 (or equation (7.2)) of my paper, and in particular trying to estimate expressions such as ${\mathbb E} 2^{-it\mathbf{a}_{[1,n]}} \chi(2^{-\mathbf{a}_1} + 3^1 2^{-\mathbf{a}_{[1,2]}} + \dots + 3^{n-1} 2^{-\mathbf{a}_{[1,n]}})$ ) should eventually be able to upgrade the “logarithmic density” aspect of my theorem to “natural density”, although the calculations in Section 5 will have to be replaced by a more careful computation that keeps much better track of the Archimedean behaviour of the Syracuse iteration and its potential coupling with the 3-adic behaviour. (It may potentially be that the notation and arguments become cleaner if one works on the adeles ${\mathbb A}$ instead on various components of the adeles such as ${\mathbb Z}_3$ , ${\mathbb Z}_3 \times {\mathbb R}$ , or (as is done in my paper) ${\mathbb Z}/3^n {\mathbb Z}$ , in the spirit of Tate’s thesis, particularly if one wants to generalise to other Collatz type iterations as discussed in other comments here. I also have the vague sense that the nonabelian Fourier analysis of the affine (semi-)group $\mathrm{Aff}({\mathbb A})$ on the adeles might also be naturally involved in all this analysis.) If one is lucky one may be able to leverage the existing purely 3-adic theory in my paper as a “black box” to handle the $t=0$ case and use some other, simpler, argument to handle the $t \neq 0$ case, again somewhat in analogy with the prime number theorem. (The analysis in this paper of Lagarias and Soundararajan on Benford’s law in the Collatz iteration may also be of relevance here. Related to this, I suspect that to get a sufficient amount of Archimedean equidistribution one would need something like Baker’s theorem on the Diophantine nature of $\log 2 / \log 3$ .)

I don’t have any plans to work on this particular refinement of the results (and all my current graduate students and postdocs are busy with their own projects and/or are working in rather different areas of mathematics than the ones that are relevant here), so you (or anyone else) are certainly welcome to pursue it if you wish.

29 December, 2019 at 5:16 pm

michaelmross

The distribution of odd sequence steps is given by a simple function:

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

Another way to express this is to say: Given three arithmetic operations, for every odd number n only a or b or c can be a whole odd number.

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

Then you can see that the ratio must be 2:1:1 of the three possible operations.

You can triangulate the result of the congruence-based additive function or the a,b,c algorithm and the conventionally expressed Collatz function using factors of 2 and 3, referencing the a, b, c operations:

a: Input factor of 2 is replaced with an output factor of 3
b: Input factors of 2*2 are replaced with an output factor of 3
c: Input factors of 2*2 are eliminated

– Remember that the factoring is being applied to n+1 or n-1 (where n is odd).
– Operation c can correspond with powers of 2, by consecutive repetition.

15 September, 2019 at 7:45 am

mayor of Simpleton

In Remark 1.4 of the paper, at the end of the paragraph, is the equivalence literally with sets of log density approaching 1 (i.e., there always exists a regular enough subset whose log density exists) or the a priori weaker statement that the lim inf (of the sequence computing) log density goes to 1 as the Collatz orbit-minimum parameter is raised?

In either case there is a formulation of the main result without slow-growing functions, as “[lim sup] log-density of exceptions (Collatz orbit stays above C) goes to 0 as C increases” but it wasn’t immediately obvious which sense of lim-sup applies.

15 September, 2019 at 8:07 am

Terence Tao

Oh, good point. I had assumed without thinking about it too hard that every set of lim-inf log density at least $\alpha$ had a subset whose log-density existed and was equal to $\alpha$ , which is why I formulated the remark as stated, but now that I look at it more carefully this is not the case, and one should indeed use the lim-inf formulation instead to get the actual formal equivalence (although it may be possible in this specific case to still recover the stronger claim currently stated in Remark 1.4 even if it is not logically equivalent to the main theorem). This will be corrected in the next revision of the ms.

15 September, 2019 at 11:30 am

Terrence Tao’s Progress on the Collatz Conjecture | An Unstructured Mess

[…] Paper: https://arxiv.org/abs/1909.03562 Tao’s blog post about the paper: https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/ Wikipedia page for Collatz conjecture: https://en.wikipedia.org/wiki/Collatz_conjecture A slightly […]

17 September, 2019 at 3:54 am

Sandor Pozsik

Dear Mr. Tao,
There could be a way to prove conjecture:
1) An impair number will always be followed by a pair.
2) A pair number will either be followed by an impair and then see point 1, either by a pair number.
3) No number is repeated within one series.
4) If the number is a power of 2, the series will converge to 1.
5) from Points 1,2 and 3 we see that unrepeated pair numbers will be generated infinitely, except if the series reaches a number which is a power of 2 (point 4).
6) The probability of generating a power of 2, when generating infinite number of pair numbers is 100%, so it is 100% sure that the serie will reach a power of 2 and then converge to 1.
Best Regards,
Sandor

18 September, 2019 at 12:53 am

Anonymous

Dear Pro.Tao
Maths problems always everyone nerve in the world.So, today I want to tell a fun story in order to reduce stress.”Last night, I intruded into Pro.Tao’s house to steal money from a big box.Unfortunely , after I broke the box , I found no money in the box. Materials in the box such as Hodge conjecture, P vs Np , Goldbach conjecture,Navier Stokes , Riemann…..solved by Pro.Tao.”
A forever fan of Pro.Tao
Best wishes

19 September, 2019 at 3:23 am

Ridiculous Professional

Gowers has a viXra overlay journal with double the publication rate as Pi. So maybe if things don’t go well with the next revision you could consider submitting there.

19 September, 2019 at 9:32 am

notyetready

Do you think there might be some relationship between the 3x+1 problem and the abc conjecture ? Saying it differently, one may wonder whether both conjectures coud be a logical outcome of a single and more general statement (possibly undecidable) concerning the additive properties of numbers composed of large powers (of 2 and 3 in the case of 3x+1).

19 September, 2019 at 6:55 pm

Terence Tao

There is indeed a relation between the 3x+1 problem and results such as Baker’s theorem which establish some separation between powers of 2 and powers of 3, and which provide key examples of where the abc conjecture is known to hold; for instance results such as Baker’s theorem have been used to rule out certain types of Collatz cycles, and to establish Benford type laws for Collatz iterations. See my previous blog post on the Collatz conjecture for further discussion.

20 September, 2019 at 2:44 am

Anonymous

Is the complexity of the Collatz iteration dependent on the irrationality measure of $\log 3 / \log 2$ ?

20 September, 2019 at 9:37 pm

Tom

There are relationships between Pillali’s and ABC conjecture. It is quite important for Collatz’s hypothesis to know how many solutions exist for 2^(x + y)-3^y=k, for some fixed k. Similar questions are raised by the Pillali’s hypothesis which is related to ABC conjecture. We have solved so far only the case for k=1 (Catalan Conjecture). We do not know if there is a finite amount of other solutions. For example, if there were an infinite amount solutions for k=5, then there is a higher probability that then some 2^(x+y)-3^y=5 divides equation (5):

https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/

The solution of the ABC hypothesis and Pillali’s conjecture can supports the Collatz hypothesis. But the fact that Collatz problem contains such problems may indicate that it is much more difficult than these problems.

21 September, 2019 at 4:25 am

Alberto Ibañez

I am not sure of the relationship that may exist between Pillali, ABC and Collatz. I knew the relationship between Collatz and diophantine equations, although I have not fully understood it, recently, thanks to Jeff’s advice, I am trying to understand this relationship through the paper On the “3n + 1” Problem
By R. E. Crandall (1978). Somehow then Pillali and ABC should be related to the diophantine equations. But apart from this, for Collatz, solutions of the form $2^{x}-3^{y}= k$ .with fixed k, should not be of the form $2^{x}-n \times 3^{y}= k$ , for almost all N, where k takes values from the form $\displaystyle 3^{y-1} 2^{x_1} + 3^{y-2} 2^{x_2} + \ldots + 2^{x_y}$ (8) of the previous post of the professor about Collatz, where k can only be 1 when y = 1. Although we are assuming the conjecture true, we can study the cases. The value of k somehow sets the value of 3 ^ y. For y = 1, there are infinite powers of form 2 ^ 2n, which give us infinite values of n that meet this condition: 1,5,21,85, … (4n + 1). different values of k, for n odd, must be odd and not multiples of 3. Somehow the different orbits of Collatz, for odd n, are comparable to the factorization in prime numbers, that is, for each value of k there is a unique value 3 ^ y and a unique value of 2 ^ x, for a unique n, which satisfies equality (for n even it is almost equal with some nuance). I don’t know if through this equality, setting values of k, 3 ^ y can be set and consequently set 2 ^ x, for a unique value of n. But we can also propose equality so that an orbit enters a periodic cycle, which would be of the form $n \times 2^{x}-n \times 3^{y}=n \times k$ . For this equality we have a certain advantage, knowing that if it is more than probable that the conjecture is true, the only possible solution to this equation must be when n = 1 and k = 1. I am far from knowing how to handle this equality, although one way of seeing it is that $n \times 2^{x}\equiv n \times k \pmod n$ and $n \times 2^{x}\equiv n \times k (mod3^{y})$ . I’ve always thought that the g.c.d and the Bezout identity have something to say here, but I don’t know attack this relationship.
And we can even pose the orbits that escape to infinity for a fixed k, where $y= \infty$ , then we have $n \times 3 ^{\infty}$ , would be infinite, and we would need some number that by subtracting infinity is k, or $n= \frac{\chi -y}{3 ^{\infty}}$ ,with infinite n in this way. Although the consistency of this approach is not very well. I don’t know if transcendence is here, because of the connection of transcendence and Collatz I still don’t understand and I have to improve it.
As for connections with other conjectures, based on my intuition and almost always devoid of any rigor, I see some connection with Poincare and rectangular triangles in 2-d reducible to 1 point, as I indicated in a previous comment. And even, very speculatively, I like to see the conjecture related to inflationary theory and big-bang, in the sense of how from a point a connected infinity can be created, or how this could be reduced by a single point. Thanks.Sorry for latex, I don’t do very well lately.

25 April, 2020 at 9:46 am

Anonymous

Is it possible that the Collatz conjecture can be proved from an ineffective version of the ABC conjecture?

25 April, 2020 at 7:18 pm

Terence Tao

Well, nothing can be ruled out completely (if for no other reason than the trivial observation that any proof of the Collatz conjecture can be converted into a proof of the Collatz conjecture “from” an ineffective version of the ABC conjecture simply by introducing the latter in a gratituous fashion), but my feeling would be that the ABC conjecture would at best be useful for limiting some of the possible behaviours of Collatz cycles but would not for instance be of much use in preventing the scenario in which a single exceptional Collatz orbit goes off to infinity.

25 April, 2020 at 11:36 pm

Alberto Ibañez

Estimated professor, do you think we are in that scenario where we can affirm that the worst possible orbit cannot escape infinity?

https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/#comment-545943

With the last neurons I have left, I am trying to create a system of equations that allows us to ensure that of the infinite possible linear combinations for all

$n \times 3^{k} + d = 2^{y}$ ,

there are infinite correct solutions, from the fact that when reaching cycle 4 -2-1-4 can continue iterating infinitely, and the minimum solution, which first reaches 1, is the solution we are looking for.

$n\times x + d=2^{y}$

$x = 3^{k}+ r$

$n\times r + d = TCR$

$n\times r + d = TCR\equiv d\equiv 2^{y}(modn)$

always there is a moment that

$n\times r + d = TCR\equiv d\equiv 2^{y}(mod3^{k})$

when the orbit reaches 1.

I have recently learned that the problem we encounter to solve a diophantine equation, that the number of unknowns is greater than the number of equations, in our case, 3 unknowns for an equation. I will try to collect all the information we know and with a last advance I will write a comment to see if we are capable of assembling a system of equations compatible with a solution.

14 May, 2020 at 12:54 am

Alberto Ibañez

When we find a solution like

$5 \times 3 +1 = 16$ ,

$5 \times 3^{2} +19 = 64$

$5 \times 3^{3} + 121 = 256$

they are also solutions, so there must be a solution such that

$5 \times 3+1= 16$

$5 \times 3+1-4= 16-4$

$5 \times 3 - 3 = 4 \times (4-1)$

$5-1 = 4$

if this could be interpreted as a system of equations, in the form

$n \times 3^{k} + d = 2^{y}$

$n \times 3^{k-1} - x = 2^{y-2}$

$x = \frac {d-2^{y-2}}{3}$

perhaps we could establish that it is an indeterminate compatible system and that there exists a value such that

$n-d_{n}= 2^{y-2k}$

I cannot finish seeing what mechanism leads us to find these solutions, either because it is a trivial aspect that does not contribute anything interesting, but I comment on it in case it might have any interest. Thank you.

14 May, 2020 at 11:48 pm

Alberto Ibañez

For some known solutions of the form

$n \times 3^{k} + d_{k} = 2^{y}$

there is a solution such that

$n \times 3^{k+1} + d_{k+1} = 2^{y+2}$

where

$d_{k} 2^{y}$

something like $d_{k}$ is the last value less than $2^{x-2}$

If in some way we can establish that this condition is necessary and/or sufficient for solutions to existing, perhaps there is a mechanism that allows us to establish that such a solution will always exist, perhaps avoiding the possibility of entering a non-trivial orbit.

$n \times 3^{1} + d_{1} = 2^{x}$

$n \times 3^{2} + d_{2} = 2^{x}$

…

$n \times 3^{k} + d_{k} = 2^{y}$

$n \times 3^{k+1} + d_{k+1} = 2^{y+2}$

$n \times 3^{k+2} + d_{k+2} = 2^{y+4}$

…

$d_{1} = 1$ is the solution

$d_{2},d_{3},...,d_{k} 2^{y}$

$d_{k+2} > 2^{y+2}$

$d_{k+3} > 2^{y+4}$

…

15 May, 2020 at 12:05 am

Alberto Ibañez

*error correction

– $d_{k}2^{y}$ is

$d_{k} 2^{y}$

– $d_{2},d_{3},...d_{k}2^{y}$ is

$d_{2},d_{3},...d_{k-1}< 2^{x-2}$

$d_{k} 2^{y}$

2 July, 2020 at 2:51 am

Anonymous

Periodic non-trivial orbits

If this orbit exists, the equation of the form

$n\times 3^{k}+ n\times d= n\times 2^{y}$

must be fulfilled, that is, there cannot be any periodic orbit that does not meet this condition, right?

The conjecture gives us some additional information

– $3^{k}$ is smaller than $2^{y}$

-Can we establish that $2^{y}$ must also be less than $3^{k+1}$ ?
If so, between $3^{k}$ and $3^{k+1}$ are there 1 or 2 possible values for $2^{y}$ ?

-If there is a solution we would have k odd numbers that meet the equation

-Regarding the possible values that $n\times d$ can take, these cannot be multiples of 3, which is
why multiples of 3 cannot enter a loop

-They must also have the form of (8)

$\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}$

, and be bounded
between a minimum value, which responds to the form

$3^{k}-2^{k} =3^{k-1}+3^{k-2}2^{1}+...+2^{k-1} = (n\times d)_{min}$

, and a maximum value,

$3^{k-1}+3^{k-2}2^{a1}+...+2^{y-1} = (n\times d)_{max}$ , for each value of $3^{k}$

-It seems that of the possible values that $n\times d$ could take, these would be 1 + 2 + .. + k values. From these we would need that k values, at least, are multiples of d

-According to some observed orbits, of the possible values between $(n\times d)_{min}$ and $(n\times d)_{max}$ for a given $3^{k}$ , many values are prime and the rest co-prime, that is, there are no k multiple values of d, it even seems that none ,or that is, all values are co-prime

– In fact, if the conjecture is true, in that there is no non-trivial orbit, we could establish that for all $3^{k}$ , of the 1 + 2 + .. k possible values of the form (8), between the minimun and the maximun possible value, there are no k values multiples of d ,or even, regardless of the value of d, there are no k values that are not coprime , or even, all possible values are coprime.

Do you think it is plausible to try to demonstrate this fact?

12 November, 2020 at 8:24 am

Alberto Ibañez

Hello everyone. I would like to recover this argument from the previous comments.
If Collatz’s conjecture is true it has this form

$n3^{k}+d_{3^{k}}=2^{y}$ (1)

Where n is an odd number, k is the number of odd steps and y is the number of even steps.

As it reaches a power of 2, it reaches 1, and it enters the trivial periodic orbit. So we can keep iterating and we find that

$n3^{k+1}+d_{3^{k+1}}=2^{y+2}$ , where $d_{3^{k+1}}=3d_{3^{k}}+2^{y}$

$n3^{k+2}+d_{3^{k+2}}=2^{y+4}$

…

This process can be done in reverse,

$n3^{k}+d_{3^{k+1}}=3\times 2^{y-2}+2^{y-2}$

$n3^{k}+d_{3^{k+1}}-2^{y-2}=3\times 2^{y-2}$

$n3^{k-1}+d_{3^{k-1}}= 2^{y-2}$

…

in addition to being a uniform process and we arrive at

$n-d_{n}=2^{y-2k}$ (2)

That is, if there is a solution (1), there is (2)
Could we ask ourselves the opposite? That is, if there is a solution (2), is there a solution (1)?

Note: This process seems to be followed without problems when y-2k is positive, but when it is negative it seems to get stuck at the value 1, $2^{0}$ and 2, $2^{1}$ , and it does not seem to be able to advance to negative powers of 2 with negative exponent, and it alternates values from 1(or 2) to -1(or -2) until reaching n-d = + \- 1(or 2).
This I have been able to observe in the orbit of 27,for example, where we arrive at $27\times 3 ^ 6-19682 = 1$ , and it does not seem that we can arrive at $27-d = - 2 ^ {|70-(2\times 41)|}$ . At this point I would appreciate your opinions.

Ok, if there is a solution we have

$n-d_{n}=2^{y-2k}$ (2)

and we know that

$3n+1= \chi$ , so

$\lambda = 3d_{n}+1$ ,

and when y-2k is positive, for some known orbits, it is a power of 2, so perhaps it could always be a power of 2, or in the case of negative y-2k it couod be + \-1(or 2), then

$\chi = 3\times 2^{y-2k}+\lambda$

Of course, if this argument is correct, with this information, is it possible that there is some trick to know if there is a solution?

Thank you for your answers.

19 September, 2019 at 9:44 am

Robert Frost

Would there seem to be any hope of sharpening your results by restricting to only the 5-rough numbers? Eliminating the leaves of the graph by considering $+2^{\nu_2(x)}\cdot3^{\nu_3(x)}$ which commutes with multiplication by both 2 and 3 gives an even superior form of the problem IMO than the Syracuse function, it being surjective.

19 September, 2019 at 10:16 am

Robert Frost jr.

“And tall and in a port of air”

Almost anything is doable if we drop the chains of rigor.

19 September, 2019 at 1:52 pm

Robert Frost

rigour follows insight

19 September, 2019 at 7:03 pm

Terence Tao

A single iteration of the Syracuse map already places one in the setting of 5-rough numbers (numbers not divisible by either 2 or 3), so the effect of restricting to this setting on the analysis of the paper (which is studying a significantly larger number of iterates) is fairly minimal.

Once one restricts to 5-rough numbers, the Syracuse function is not only surjective, but it has an approximately invariant measure $\nu$ , which one can view as the main source of the results of this paper. This measure can be defined as

$\displaystyle \nu(\{N\}) := \frac{3^{n} \mathbb{P}( \mathbf{Syrac}({\mathbb Z}/3^n {\mathbb Z}) = N \hbox{ mod } 3^n )}{N}$

where $n$ is a natural number comparable to a small multiple of $\log N$ (the stabilisation result in Proposition 1.14 my paper ensures that the exact choice of $n$ is not terribly important). This is an infinite measure supported on the 5-rough numbers, and Proposition 1.14 combined with Lemma 1.12 basically tell one that $\nu$ is approximately invariant: $\nu(\mathrm{Syr}^{-1}(E)) \approx \nu(E)$ for any set $E$ of 5-rough numbers. This measure implicitly makes an appearance at the end of Section 5 of the paper.

19 September, 2019 at 11:59 pm

Robert Frost

Thank-you, this really helps add some insight for me as I had found myself getting sucked towards Baire/Borel sets, invariant measures and sigma-algebras in studying this problem so it’s pleasing to find connections to this ball-park already made.

19 September, 2019 at 10:00 am

Robert Frost

On a related note… can you send 2Z-1 to a subset of an interval of the real line in such a way that some superfunction of the Collatz function on the same segment has orbits only the same periodicity as the function in Z? Via Sharkovskii’s theorem this would prove the nonexistence of trivial loops by contradicting known results that orbits of period 2 do not exist.

19 September, 2019 at 7:41 pm

Terence Tao

Given how oscillatory Collatz maps and their iterates are, I am sure that any reasonable continuous extension of these maps to the real line will inevitably create any number of new fixed points from the intermediate value theorem. The dynamics of the Collatz map involve not only the Archimedean completion ${\mathbb R}$ of the rationals, but also the 2-adic and 3-adic completions, so it is unlikely that a purely real-based approach is going to capture enough of the complexity of the Collatz dynamics to resolve the problem.

19 September, 2019 at 11:45 pm

Robert Frost

It’s fitting that you mentioned both 2-adic and 3-adic because I had already restrained myself from the following comment… I have hope that a completion of the 5-rough positive integers using a composite of the 2 and 3 adic metrics might yet lead to an algebraic solution dropping out. $(3x+\prod_p p^{v_p(x)})/2=2x$ after all. Then quotient out the powers of 2 and 3 from the multiplicative monoid. The conjecture effectively states that $0$ may only be approached through $2^m3^n$ so it seems natural to send $2^m3^n$ to zero as $n,m$ to infinity. On an algebraic note, it’s perhaps worth pointing out that the orders of cycles over the 5-rough integers (both positive and negative) give the dihedral group D7. On another note, more related to your previous post and the connection to transcendental numbers there is a “lowest” (in reverse) 5-rough trajectory which is not 1,1,1… namely 1,5,13,17,11,7,37,49,… which is almost certainly of some use. Its parity sequence I imagine is not in Z_2 since it obviously never terminates although I would be curious whether some root of unity or other such object might be appended to Z_2 in order to contain it.

20 September, 2019 at 3:22 am

Robert Frost jr.

What do you mean when you say

“… which is almost certainly of use…”

Thanks.

20 September, 2019 at 7:07 am

Robert Frost

@Robert Frost Jr. I’ll overlook your name and assume for now you’re not being disingenuous. I mean this: Let $T(x)$ be the isometry on $\Bbb Z_2$ given by recording a $1$ for every odd number and a zero for every even, in a Collatz sequence orbited by the $(3x+1)/2$ version of the graph. Then there is a “lowest trajectory in $\mathbb{Z}^+$ ” given by $1,1,1...$ having $T(x)=\overline{01}_2=-\frac13$ . Extending to infinite trajectories (heading backwards) requires $T:\to$ something at least as big as $\Bbb Q_2$ in which case there are at least two further “lowest” trajectories in $\mathbb{Z}^+$ : The trajectory $T(x)=\overline{0001}_2=-\frac1{15}$ is the “general” lowest possible trajectory (i.e. if we do not assume every sequence converges to $1$ . But if all sequences *do* converge to $1$ then this bound sharpens to $\underline x=T(S)$ where $S$ is the sequence $T(\ldots1,1,5,13,17,11,7,37,49,\ldots)=\overline{01}.00010010111000101\ldots_2>-0.2590$ . Then my claim is that the precise nature of this number $\underline x$ is almost certainly a useful connection between the Collatz graph and transcendental number theory. There’s also a connection between this number and a (not well-founded) set of ordinals which is invariant under truncation/subset but I haven’t got that quite straight in my mind yet.

20 September, 2019 at 9:17 am

Robert Frost jr.

Can you define the form of the subset of odd numbers which, by your mapping, are identified with sequences of the form 1,1,1,…
of arbitrary finite length?

22 September, 2019 at 8:49 am

Robert Frost

If $T(x)$ is the isometry on $\Bbb Z_2$ defined above and you ask for which sequence $x$ gives $T(x)=\overline1_2$ , only a constant sequence of 2-adic numbers has this form – it is in fact $-1,-1,\ldots$ and since $T$ is an isometry it’s the only element in $\Bbb Z$ with this property.

20 September, 2019 at 2:04 am

Alberto Ibañez

Estimated Professor: About”how oscillatory Collatz maps and their iterates are”.The classical interpretation of the conjecture creates these chaotic behaviors, but is it possible to interpret the conjecture by avoiding these behaviors? Moreover, are they useful for solving the conjecture for all N? For example, following the conjecture via the Bohm and Sontacchi, maintaining the numerator without dividing by the powers of 2 and adding the numbers of the form (8) of the previous post. This segment grows continuously until finding a power of 2, and if does not fall from n in a $n \ times 2 ^ x$ , does it seem to have infinite probabilities of finding a power of 2 versus? probabilities of not finding it and escaping to infinity, which would imply an infinite number of counterexamples to the conjecture.
Another example could be to study the equation of the form $n \times 3 ^ {k} + n \times y = n \times 2 ^ x$ if n enters a periodic orbit, with $n \times y$ of the form (8), where $n \times 2 ^ x \equiv n \times and \ pmod n \hbox{ and } (mod 3 ^ k)$ , where the result is, securely, only possible with n = 1.
Or even restrict the conjecture to the unit circle, forming a right triangle where the hypotenuse would be the 3n + 1 values, the cosine the 3 ^ k * n values and the difference between the two values. While I don’t know how to attack this option, it seems possible, at least, to study it.
Or even the representation of the function in the Cartesian axes is simple, although it cannot tell us anything. Thank you.

20 September, 2019 at 5:49 am

Jeff

I agree. And to add, any affirmation of 3x+1 implies no solutions to (7.3) per the constraints given in Crandall’s 1978 paper.

And affirmation of a finite solution set to (7.3) is exactly the finite cycles Conjecture.

It is massively difficult, and if you watch the literature you will see number theorists are progressively developing techniques to settle such questions.

Now stick in hypothetical divergent sequences…

Trying to skate around real progress is futile. And any perceived insights are delusions.

22 September, 2019 at 2:28 am

Alberto Ibañez

Dear Jeff. I am still studying Crandall’s 1978 paper. I do not quite understand it and I do not quite understand you, but I seem to intuit something. The hypothetical existence of orbits that seem to escape to infinity is deduced from the existence of orbits of infinite steps. These orbits would produce infinite counterexamples to the conjecture, and it seems strange not to have found at least one. Then there are the orbits that are trapped in a periodic cycle, which involve a finite number of counterexamples. These orbits, in the sense that Collatz’s algorithm only stops when it reaches 1, has infinite steps, then they are infinite periodic. Is it possible that these two types of orbits are really the same? It has been misunderstood that there are orbits that have infinite steps, periodical orbits, with the fact that they escape to infinity?.
Regarding the diophantine equation of the form

$2 ^ x-3 ^ k = y$

, it seems that their solutions give us the possible periodic orbits for some n and some y. But it seems that it is somehow decontextualized, and it should be of the form

$n \times 2^{x}-n \times 3^{k}= n \times y$

, although I don’t know if it’s really better that way. If the only solution is the known for n = 1, y = 1, k = 1, x = 2, then the conjecture is true. In my previous comment I tried to analyze how to attack this equality, both for orbits that enter periodic orbit, and for those that escape to infinity, but if they are the same, it would be enough to demonstrate only one of the options.
If for almost all n it is true that

$2^{x}-n\times 3^{k}= y$

, and for a periodic orbit, it is necessary that

$n \times 2^{x}-n\times 3^{k}= n \times y$

, comparatively it seems that the distance separating the powers of 2 and 3, for almost every n, is less than that necessary to reach a periodic orbit. Some interesting questions in these equalities are that both
$y$ and $n \times y$ must be of the form
$\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}$
(8). The value of k is fixed for the value of (8).

For there to be a number that belongs to a periodic cycle we would have to study

$n \times 2^{x}\equiv n \times y \pmod n$
$n \times 2^{x}\equiv n \times y (mod3^{k})$

and so that n escape to infinity we would have

$n=\frac{\chi }{3^{\infty }}$

where $\chi = n\times 2^{x}-n\times y,\: or\: 2^{x}-y,\: or\: a \: number$

, where the only possible solution seems to be 0 or 1.

22 September, 2019 at 7:24 am

Jeff

Alberto,

Ibanez make great electric guitars. Any relation?

You have a lot of ideas. One really great one is characterization of a lower bound for differences of powers of 3 and nearest powers of 2.

My gosh, we cannot even prove the bound is exponential!

As for this paper, you’ll notice earlier questions about ‘closing the gap’ between all and almost all.

Well, that would entail completely removing all probabilistic arguments from it. How much of the paper would be left?

22 September, 2019 at 8:06 am

Terence Tao

Baker’s theorem provides an exponential lower bound for the difference between powers of 3 and powers of 2. See Corollary 4 of https://terrytao.wordpress.com/2011/08/21/hilberts-seventh-problem-and-powers-of-2-and-3/ Unsurprisingly, these sorts of results end up being used in some of the Collatz literature, for instance in ruling out certain types of cycles.

As I mentioned in an earlier comment, there is only a very slim chance for directly transferring an “almost all” result in this setting to an “all” result, but the chance is not entirely non-zero, particularly if one can somehow combine the “almost all” result with some complementary non-trivial results on the Collatz problem. Here is one unlikely but theoretically possible scenario: an almost all result is proven that shows that all but at most $O(x^\theta)$ starting points in $[1,x]$ end up at a value bounded by a constant $C$ . This by itself does not settle the problem: but suppose one also shows that any counterexample to Collatz has a pre-image tree that grows faster than $x^{\theta'}$ for some $\theta' > \theta$ (for instance the Krasikov-Lagarias result mentioned in the paper is of this type with $\theta' = 0.84$ ). Combining the two claims, we conclude that all counterexamples to Collatz must attain a value less than $C$ , otherwise the second claim would contradict the first. If this value of $C$ was small enough, one could then hope to resolve the full conjecture by a numerical calculation verifying the Collatz conjecture up to $C$ . (Note that this last step would also allow one to distinguish the $3x+1$ problem from the $3x-1$ problem, for which the first two steps might still work, with only the numerical verification step differing between the two iterations.)

Personally I view the above scenario as being remote (among other things, as I discussed in my previous post, pulling this off must require at some point either using or proving some version of Baker’s theorem.) However, as I also pointed out in another comment, even in the absence of direct transferability, getting a better understanding of the relative difficulty of various “almost all” problems can give some heuristic insight into the relative difficulty of various “all” problems, which can lead to predictions as to the right proof strategy even before this strategy can actually be executed. For instance, Conway’s FRACTRAN iterations show that there are some Collatz-like problems for which the analogous conjecture is undecidable. This is often viewed as an obstruction to proving the Collatz conjecture. On the other hand, the result in my paper relies heavily on the existence of an invariant adelic measure for the iteration with negative drift, and it does not appear that the undecidable FRACTRAN iterations have such a measure. So this raises some interesting, and potentially tractable questions: (a) do the results in my paper work for any Collatz-like iteration with an invariant adelic measure with negative drift? and (b) are there any examples of Collatz-like iterations which have an invariant adelic measure with negative drift, but which contain unbounded orbits? If the answer to (a) turns out to be “Yes” and (b) turns out to be “We can’t find any”, then this suggests that the natural general conjecture for Collatz-type iterations should be “Every Collatz-type iteration with an invariant adelic measure with negative drift should have all orbits bounded”. This abstracts away the role of special numbers such as 2 and 3 (and also avoids having to distinguish for instance between the 3x+1 iteration and the 3x-1 iteration), explains the distinction between the 3x+1 and 5x+1 iteration (the latter having positive drift) or the FRACTRAN iteration (for which the invariant adelic measure is either non-existent or has positive drift), and may give clues as to what the right way to proceed further is (for instance, such a conjecture has a flavour of a “local to global principle”, suggesting that ideas in the penumbra of other such local-to-global principles (e.g., the Bombieri-Lang conjecture) may be relevant). Of course this is all still rather speculative, but these are typical of the way other partial results in other mathematical problems have led to further insights and progress.

Finally, it is worth pointing out that while proximity to well known problems often serves as motivation for mathematical research, these problems are by no means the only objective, and one can often get unexpected other advances in mathematics even if one only obtains partial progress towards the initial motivating goal. For instance, a large fraction of algebraic number theory was developed in hopes of resolving Fermat’s last theorem; it did not succeed at this goal, and FLT was eventually established by rather different means, but the theory was still immensely valuable nonetheless. Sieve theory was invented to try to solve conjectures such as the twin prime conjecture; it has thus far been unable to achieve this (roughly speaking, it only controls “almost primes” rather than “primes”, without the addition of highly nontrivial extra input), but nonetheless has become a basic part of the analytic number theory toolkit. More recently, the work of Einseidler, Katok, and Lindenstrauss establishing a strong “almost all” version of the Littlewood conjecture is not expected to lead to a full resolution of that conjecture, but nonetheless has generated a lot of advances in our understanding of entropy methods in homogeneous dynamics. (See also this post of mine on the particularly valuable nature of partial progress in mathematics, which is nearly unique amongst all disciplines in this respect.)

22 September, 2019 at 10:13 am

Jeff

@Tao,

Corollary 4 looks like observations I circulated about a decade ago. When did you add them to that post?

Anyway, I’ll be as precise as possible here regarding the adjective “exponential”.

Are you saying there exists some legitimate, fixed, positive constant beta such that 3 to the power of beta is strictly less than the right-hand side of the inequality in Corollary 4?

22 September, 2019 at 10:26 am

Jeff

Addendum,

Oh yeah, we must scale beta by multiplying by x in order to get the form of a legitimate exponential bound.

22 September, 2019 at 3:22 pm

Jeff

@Tao,

Okay, so does your Corollary 4 give an ‘almost’ exponential lower bound?

I don’t understand.

22 September, 2019 at 5:16 pm

Buzzman

@Terry,

I think the powers of 3 and powers of 2 arising from the expansion of the $\textnormal{Syr}$ function for $n$ iterations lead to an undecidable expression since the inverse of $\textnormal{Syr}(N)$ , by one step of iteration, leads to one-to-many mapping from an odd $N \not \equiv 0\pmod{3}$ to an infinite set of odd iterates. Unless I misunderstood your language, I do not get how one can establish a bound in such a case. I believe that the intricate patterns in Collatz dynamics can be simplified, without loss of information, by bypassing the even operations and examining instead the odd trajectories in reverse through the inverse of the $\textnormal{Syr}$ function, as earlier noted by Lagarias. It appears to me that there has been less effort in this regard. Since there always exists an integer $N$ where any $n$ compositions of $\textnormal{Col}_{2}(N)$ generate a parity vector consisting entirely of $1s$ even as $n \to \infty$ , then any resulting bound $O(N^{\theta})$ will always yield $\theta < 1$ . At any rate, your partial result is already tremendous by novelty of approach.

23 September, 2019 at 3:58 am

Jeff

@Terry,

Was looking at the 2003 paper of Krasikov and Lagarias in Acta Arithmetica. The remark at the top of page 254 raised a red flag with me.

Did they misunderstand what form an exponential lower bound takes?

23 September, 2019 at 4:52 pm

Jeff

The link to the partial progress post is missing. It seems way off base and actually, a bit contrived, given this paper.

But this paper is not partial progress anyway.

It says on Wikipedia that the paper of Krasikov and Lagarias gives rigorous bounds. I’m thinking not.

What is especially interesting is that it is elementary. Hmm.

26 September, 2019 at 2:00 am

Alberto Ibañez

Dear Professor: Constate C seems to be relevant in the conjecture. Surely its nature is obvious, but I do not quite understand it. Is it big? Is it small? Is there any way to explain its nature in an accessible way? I have read your previous post many times but I did not understand the relationship with Baker, although I think I begin to understand it. Observing the nature of the periodic orbits of 5n + 1 and 3n-1, I have observed that the value k, the number of iterations of the cycle or the power of 3, as you can see, coincides with the cardinality of the set n odd that are counterexamples to the conjecture for a value y (or q), the distance between a power of 2 and 3.the higher is k, the greater the number of counterexamples Is that relevant? and for orbits that escape to infinity? I still don’t see that infinite odd numbers can have an unlimited orbit, or what form they have when heuristically it is almost impossible for even a small number of counterexamples to be given? Finally, I cannot find information about “an invariant adelic measure”, is possible to talk about it? thank you very much.

27 September, 2019 at 12:26 am

Jeff

Alberto,

One thing to notice is that Crandall’s (7.3) exists, in a philosophical sense, without the 3x+1 map. We can write it down and ask about the existence of solutions without consideration of the iterations of the map.

But the reason there are so many papers on this problem is because the iterations gives us something to grab onto.

The probability type arguments ignore an infinite subset of the iterations, at best.

Now we have earlier comments about a proof strategy built upon this draft paper suggesting we could ‘abstract’ away special numbers such as 2 and 3.

Well, that would amount to erasing (7.3) all together. Besides, who really cares if more solutions exist to it.

22 September, 2019 at 8:58 am

Robert Frost

On the oscillatory nature of iterates of collatz maps as a barrier to the application of Sharkovskii’s theorem, it should be borne in mind that one is free to multiply any $2\Bbb N-1\to2\Bbb N-1$ Collatz sequence by any arbitrary sequence drawn from $2^m3^n$ without affecting the integrity of the sequence, with $n,m$ from sets at least as large $\Bbb Z$ but possibly larger. I imagine Bakers theorem will inform the degree to which such a process can remove the oscillatory properties of sequences but that part is beyind me.

19 September, 2019 at 5:30 pm

Anonymous

Dear Pro.Tao,
May I have a suggestion?
Why do not you have a new polymath to solve Collatz conjecture?
Only 10% you have a complete proof.
Or there are other many reasons:
1)Very little experts on Collatz conjecture in the world
2) Your breakthrough is very new and suddenly that makes other mathematicians can not catch up you

20 September, 2019 at 2:45 am

Theo

Let’s assume we forget about the even numbers.
Let’s also assume we generate the Collatz sequence starting from 1 by using a given recursive function f(x).
We forget about the even numbers.
f(1) would give us 1 – 5 – 21 – 85 – 341 – 1365 – etc..
The results of f(1) we would give us the terms of the following functions
f(5) we would us 3 – 13 -53 -213 – 853 – etc..
The results of f(5) we would give us the terms of the following functions
f(13) we would us 17 – 69 – 277 -1109 – 4437 – etc..
f(53) we would us 35 – 141 – 565 -2261 – 9045 – etc..
If all functions were based on the results of the previous functions like f(13) which is based on f(5) which is based on f(1) would we be able to say that if any odd numbers belong to that function then it must come from f(1) through a finite number of iterations?

20 September, 2019 at 11:53 pm

Anonymous

The simple Collatz iteration with its complicated orbits may be viewed as a kind of “chaotic” dynamics (“locally unstable” yet “globally almost bounded”) on the integers. This seems closely related to chaotic dynamics, so it may be interesting to find a “natural” definition for its analogous Mandelbrot set.
The Mandelbrot set is defined as the set of complex numbers $c$ for which the function $f_c(z) = z^2 + c$ does not diverge when iterated from $z = 0$ , so it seems that a natural analogous discrete “Collatz-Mandelbrot set” for $\mathbb Z^2$ may be defined as the set of $(a, b) \in \mathbb Z^2$ for which the function $g_{a, b}(x)$ does not diverge when iterated from $x=0$ . Where $g_{a, b}(x)$ is a “Collatz-like” function defined over the integers by $g_{a, b}(x) = a x +b$ for odd integers $x$ and $g_{a, b}(x) = x /2$ for even integers $x$ .

21 September, 2019 at 3:21 am

Anonymous

Since $g_{a, b}(0) = 0$ , it is more interesting to start with $x = 1$ (or any other odd integer.)

21 September, 2019 at 3:16 am

Alex

elder brother,nice to meet you!

22 September, 2019 at 1:24 am

Buzzman

The way I see it, establishing asymptotic bounds of the form $N^{\theta}$ for $N \in \mathbb{N}$ satisfying $\textnormal{Col}_{min} (N)=1$ always leads to $\theta<1$ since there always exist $N$ that monotonically increase for any $n \in \mathbb{N}$ compositions of $\textnormal{Col}_{2} (N)$ . If one takes every even integer input $N$ as convergent since $\textnormal{Col}_{2}(N) < N$ , then it suffices to prove the Collatz conjecture only for odd $N$ . However, any odd $N \equiv 7\pmod{8}$ of the form $N =2^{k}b-1$ for $b \in \mathbb{N}$ , where obviously $N$ is Mersenne if $k=1$, can be made monotonically increasing for increasing $k$ . Hence, one expects that the exceptions to any derived asymptotic bounds are odd $N$ of such forms, as initial inputs or as iterates in the trajectory of any odd $N \equiv 1, 3, 5\pmod{8}$ or both. Alternatively, one can invert the $\textnormal{Syr}$ function to map odd $N \not \equiv 0\pmod{3}$ to odd $N$ . The resulting iteration of the inverse $\textnormal{Syr}$ function constructs an arborescence graph $G=(V,E)$ , with vertex and edge sets $V$ and $E$ , respectively. Then one can alternatively prove the Collatz conjecture by showing that every vertex in $V$ is unique and that $V$ exactly covers the set of odd natural numbers.

22 September, 2019 at 10:15 am

Buzzman

Where it appears above, it should read: $\textnormal{Col}_{2}(N)>N$ (for even input $N$ ).

22 September, 2019 at 8:22 pm

Anonymous

Dear Dr.Tao,
When I was childhood, I always admire the best heroes in the science such as Newton, Einstein , Euler. Now , I also admire them. But , after reseaching the best heroes in the world nearly 30 years, I have found that you have many special things which above heroes never have. I can not express here , because after writting out here, many people against me. It’s the best way that a long time will prove all. Many people in the world will understand , maybe more 50 years later, it’s that time maybe you die.That is a problem.
And today I want to discuss other probem.I am not surprised after you claim of proving Collatz conjecture in September 2019.I acknowledge very well that you solved Collatz 2-3 years ago not 2019. And I also know that you have solved many big conjectures , but you do not till post them.Why? You are humble , humanity, not selfish. You want share profits to other mathematicians. I wonder if you do not reveal Collatz this year, other mathematicians succeed in proving Collatz, that’s time many big prizes belong to them not you. That is a thing I only admire and like you , not other mathematicians. Like a race, your speed is the fastest, but you control to limit your speed to yield other men. You accept you are behind them.
And now who else find my idea right, please up vote
Thanks all you very much.

22 September, 2019 at 10:27 am

Buzzman

Sorry, please ignore the suggested correction. The initial statement stands as is. Obviously, I’m a stupid who can’t understand my nonsense.

22 September, 2019 at 8:25 pm

Tom

I am an independent researcher, an amateur (but I’ve been dealing with this problem for 10 years). I created a symmetric-key cryptographic system based on Collatz functions and Collatz-like functions. I’d like to meet someone who could review my algorithm, possibly publish it with me (because my own description will probably have many formal shortcomings). Where to find specialists for this problem who know something about cryptography at the same time?

23 September, 2019 at 9:03 am

Jeff

Here’s a recent proof attempt

http://www.sciencepublishinggroup.com/journal/paperinfo?journalid=141&doi=10.11648/j.pamj.20180705.12

23 September, 2019 at 10:42 am

Anonymous

lol

23 September, 2019 at 1:56 pm

Anonymous

that’s a scam pay per publishing journal so anything published there can be safely disregarded

23 September, 2019 at 3:54 pm

Jeff

The finite cycles Conjecture will someday yield. And I think amateurs will have just as much credit as the professionals at that time.

Ramanujan was largely self taught. Now we have the internet. So it won’t be too much longer before the next Ramanujan surfaces and comes to our rescue.

27 September, 2019 at 2:04 pm

Alberto Ibañez

@jeff keeping infinite periodic orbits aside, orbits that escape to infinity, unbounded or infinite orbits are the same, right? So was Crandall the first to postulate the existence of these orbits? Are there other researchers who postulated the existence of these unlimited orbits?

27 September, 2019 at 3:06 pm

Jeff

Yes, unbounded sequences are not cycles. Collatz himself seems to be the first one to think of them with this map. But the concept of unbounded sequences probably goes back thousands of years.

And they may not be relevant at all for anything of practical use when comes to 3x+1. In practice we cannot iterate the map ‘forever’. So just knowing whether additional solutions exist to (7.3) ought to be enough for us.

The finitist view has strength here.

27 September, 2019 at 3:18 pm

Jeff

To add, an infinite solution set to (7.3) defines cycles of arbitrary finite length. So the idea of an unbounded sequence is silly from an ultra-finitist view point.

It’s almost like a nonsensical artifact of iterating the map.

When I was in school my teacher taught me that math operations are instantaneous. If this were true then it would not take any time at all for hypothetical unbounded 3x+1 sequence to reach the undefined state of infinity. So the question is instantaneously nonsensical!

I’d love to hear what Doron has to say about such sequences.

27 September, 2019 at 3:41 pm

Jeff

Here’s one for you,

Can you prove the number of cycles of any given length is finite?

If so, it still leaves open the possibility of an infinite solution set.

Maddening isn’t it?

28 September, 2019 at 12:00 am

Alberto Ibañez

Not really, Jeff. Infinity is our friend. For an odd n, in Syr-map, in an unbounded orbit, n would not be a single number, as a counterexample to the conjecture, there would be infinite counterexample numbers of the conjecture, which is exactly on the opposite side to the heuristic of the previous post “Heuristically applying the Borel-Cantelli lemma, we thus expect that there are only a finite number of counterexamples to the weak Collatz conjecture (and inserting a bound such as ${k \ geq 105 {,} 000}$ , one, in fact, expects it to be extremely likely that there are no counterexamples at all)”. Even more so considering that the value of k is the value of the number of counterexamples. Despite not knowing exactly the transcendentality and its relation to Collatz, for an infinite orbit, we would have an infinite collection of diophantine equations, where the infinites n of the infinite orbit are no solution, then these numbers, very speculatively, should be transcendental, and I believe that no natural number is transcendental.
Then somehow the events should lead us to the fact that if an orbit is infinite, it is infinite periodic, and that all orbits are bounded, either up to 1 or up to n, to subsequently attack the impossibility of periodic loops in 3n + 1. Very speculatively, of course. Thank you.
Another issue to keep in mind is that I think we have screwed up this comment thread. My sincerest apologies to Professor Tao, and all my respect for his work.

28 September, 2019 at 4:39 am

Jeff

Alberto, I agree with the concept of a potential infinity. I disagree with the concept of actual infinity.

That is why hypothetical divergent 3x+1 sequences are fascinating to me. They cross from being defined to undefined. Are they both? Is that a contradiction in itself?

And is the question and the search for an answer a complete waste of precious time?

3 October, 2019 at 9:50 am

Gastón Fernando Murillo Plúas

Let’s evaluate in the opposite direction. If you come from the infinite, even if there are no unbounded orbits, there would be an infinite amount of regressive operations of the algorithm and we could never know if it would reach 1. On the other hand, show that there are no unbounded orbits in addition to 4, 2, 1 I think That would be more feasible.

11 October, 2019 at 1:34 am

Alberto Ibañez

Hi Gaston. If I understood you, indeed, for the Collatz conjecture two possibilities remain open:
1. The possibility of orbits that escape to infinity,(for every Collatz-like maps) that is, not bounded. Current techniques seem unable to attack this problem. From my point of view, which I think is the same as @ jeff, the correct question would be, are there unbounded orbits? Exists? Starting from a natural number, is it possible that the orbit reaches infinity? I don’t know if this debate is a closed or open debate, I suppose it is open, and it certainly seems very interesting. For me, in my modest opinion, conceptually they cannot exist and every orbit would be bounded, either from n to 1 or from n to n.

2. The possibility of periodic orbits. In other Collatz type maps, you can observe the nature and functioning of these orbits, even with very small numbers. For the Collatz map we know that even a very large number does not give any periodic orbit of the form

$n\times 2^{x}-n\times 3^{k}= n\times y$

where the only known solution is the trivial one, $x= 2,k= 1,n= 1,y= 1$ ,
With this advantage I propose, although I don’t know if in a correct way, this linear congruence system,

$n \times 2^{x }\equiv n \times y \pmod n$
$n \times 2^{x} \equiv n \times y (mod\: 3^{k})$

or,

$n \chi \equiv ny \pmod n$
$n \chi \equiv ny (mod\: 3^{k})$ ,

where $\chi= power\, of\, 2$ ,

I repeat that I don’t know if it is raised correctly, but if we can use GCD and Bezout’s identity to know that the only possible solution is the trivial one, then it is not possible that there is a non-trivial periodic orbit. Can there be a solution other than the trivial one?.

11 October, 2019 at 5:07 am

Jeff

Yes gentlemen. As you say, the question of the existence of a divergent sequence really belongs to the philosophers, not the mathematicians. Papers like this one assume actual infinity exists and the authors believe they can somehow rigorously argue the non existence of divergent sequences. Well they certainly do not exist if we reject actual infinity to begin with.

That leaves open the possibility of more solutions to Crandall’s (7.3). We can find practical use cases for the answer to this question.

11 October, 2019 at 8:44 am

Jeff

PhD is a Doctor of Philosophy. To me actual infinity should be reserved for masters degrees and higher. All mention and ridiculous use of it should be footnotes in all undergraduate textbooks aside from ones for philosophy degrees. Then kids can learn about and solve problems that actually have a positive impact on society. How’s that for a political statement. Well maybe a social statement. :-).

14 October, 2019 at 7:50 am

Gastón Fernando Murillo Plúas

If the results of the conjecture were strictly n * 2 ^ x we would have an immediate inductive test, but there is a slight distortion at the beginning of the natural numbers. Although an inductive demonstration proving that odd numbers are grouped into sub sets where 2 ^ x is one of the variables for the polynomial is feasible, it is not simple.

On the other hand, the orbits will grow more the greater the number that is taken because in a sieve where all the numbers must pass through the first ordered subset of odd ones evaluated at 2 ^ x you must add the steps that the first odd number requires to reach 1. That is to say you can have a larger number than the one you take from the first subset but if you have to go through a previous number it will have fewer steps. So the number of steps for a number to reach 1 can be countless if you take an uncountable number.

But periodically infinite orbits would not exist if we take into account that the algorithm sequences are ambiguous, that is, they increase from an odd number and then descend and may then rise and fall continuously. But if the density of the increments is 0 and the density of the decreases is 1 then it cannot be returned to a previous orbit in addition to 4, 2, 1.

The calculation falls into a contradiction. Even if the density of the increments was 0 it would never reach 0 because the numbers are infinite and at some point the descent would necessarily begin taking a value greater than 0 than later if it would descend to 1. If somewhere in the descent the orbit increases again it would require a calculation with a rational result and this calculation must be greater than 1 but since the density of the descent is 1 you cannot calculate a return to a previous orbit unless it is the original orbit 4, 2, 1.

How is it demonstrated? The path is the calculation of the algorithm between the subsets of the odd numbers.

23 September, 2019 at 6:17 pm

Jeff

There is potentially substantial value with this paper if it included just how awfully it handles 3x-1. It shows just how untrustworthy ‘heuristic’ intuition is. Well, provided there isn’t some other gaps of rigor.

26 September, 2019 at 3:43 am

Jeff

Seeing as how stuff like this paper get published on a regular basis instead of real partial progress, you have my permission to acknowledge my helpful comments. I cannot speak for the multitude of others who have helped for free.

Best of luck!

24 September, 2019 at 1:53 pm

Jeff

Good grief, another one

https://www.hindawi.com/journals/jps/2019/6814378/

24 September, 2019 at 1:59 pm

Jeff

Here’s a revision to one, but I cannot find a date.

29 September, 2019 at 6:50 am

Jeff

Doron opinion 111

http://sites.math.rutgers.edu/~zeilberg/Opinion111.html

To add to it,

Almost All also means Almost None.

No rigor here. Did someone really get awarded a fields medal for NOT proving anything at all?

Sounds like the award has been miserably devalued.

5 November, 2019 at 7:42 pm

Jeff

Yeah we don’t need proofs. Who reads and understands them anyway?

10 November, 2019 at 7:06 am

Jeff

https://sites.math.rutgers.edu/~zeilberg/Opinion174.html

Algorithms are Proofs. For example,

1. Assume Math operations are instantaneous.
2. How can we prove 3 times 15 plus 1 equals 46?

3. Answer, we use an algorithm, the most basic one: order of operations!

4. Philosophically the answer is 46 with or without us humans. And it just is.

5, notice, however, the algorithm cannot be fully evaluated until us humans give the definite form of 15.

6. 3x+1 is great, but x doesn’t tell us enough. Further, 3x+1 exists in other number systems, such as binary.

7. Finally, if 3 times 15 plus 1 equals 46 only exists because we humans exist, then divergent sequences do not exist, obviously.

Proof already inherited the earth. It’s foundation is our very survival, which depends on trust. Trust but verify.

https://en.m.wikipedia.org/wiki/Ishango_bone

3 December, 2019 at 6:01 am

Jeff

Math is the art of making sense out of nonsense.

“Order” of operations implies time to calculate is bounded “above” zero, even for some arbitrary object such as the universe itself. This deduction in turn implies divergent sequences do not exist as complete objects.

What really “matters” is whether the number of solutions to Crandall’s 7.3 is finite and what that number is, or that there are as many as we should ever need.

5 December, 2019 at 6:07 am

Jeff

Our perception of “time” is synonymous with our perception of “order”. You cannot have one without the other. And it doesn’t seem delusional to me. Hypothetical Divergent sequences are dumb and insidious mind traps. In my humble opinion:-).

9 December, 2019 at 10:04 am

Alberto Ibañez

Hi, @jeff.You know that I agree with you about hypothetical divergent sequences. And surely many more people will agree with you, but somehow we have to shape this idea, either from the axiom of the infinite, with some logical argument, or prove it mathematically. So I hope we are encouraged to make a collaborative effort for this interesting partial result.
On the other hand, I would like to say that the recent events about eigenvectors and eigenvalues encourage me to continue thinking about Collatz, in some apparently short and simple aspect or detail that has gone unnoticed, or even, why not, that in the depths of Arxiv the answer has already been lost. Thank you.

29 September, 2019 at 7:30 am

Jeff

Not my field but if we say the natural numbers are defined as a complete set

https://en.m.wikipedia.org/wiki/Axiom_of_infinity

Then divergent sequences have form as complete objects, assuming math operations are instantaneous.

If we toss the axiom of infinity, then we can prove by contradiction that divergent sequences do not exist. But that goes for lots of sequences.

The great thing here is that we could still have ‘potentially’ infinite solutions to Crandall’s (7.3) without the axiom of infinity!

Any qualified mathematicians ever publish on this topic?

29 September, 2019 at 8:35 am

Jeff

To me, the axiom of infinity does not define infinity per say. But one could say it almost defines infinity.

Has anyone ever assessed the purely number theoretical results which cannot be proven without the axiom of infinity?

30 September, 2019 at 2:48 am

Alberto Ibañez

@jeff What do you think of my idea about the transcendentality of the infinite numbers (counter-examples) belonging to an unbounded orbit? If they are not a solution to infinite diophantine equations, perhaps they could be a solution to another diophantine equation, but then they would belong to a bounded orbit.
About unbounded or infinite orbits and some untold variants of Conway, Professor Tao commented in his previous post “… that the examples of undecidable recursions of Conway’s type are (as far as I am aware) examples that tend to have an output larger than the input “,” it doesn’t seem like there is enough time to do any undecidably complicated mathematics in the interim. Of course, this is not a rigorous proof of anything. “But for unbounded orbits, taking into account the infinite iterations, not only iteration after iteration, if it seems that it could fit into being undecidable, hence the difficulty and the absence of appropriate techniques to solve it. If arithmetically, algebraically, topologically, geometrically, … were undecidable, then, perhaps, it could only be decidable under some kind of logical axiom

30 September, 2019 at 5:00 am

Jeff

Alberto, pi is transcendental, which just means it is not a solution of a nonzero polynomial equation with integer coefficients.

Who cares? So maybe it is a solution to some polynomial with at least one coefficient of the summands equal to, say, 2/3.

What a weird fetish. And good for nothing of practical use.

Anyway, a divergent sequence starts from a finite, meaning defined, positive integer. And since math operations are instantaneous and we admit the axiom of infinity, the sequence itself ‘almost’ has form. But there is no last element, and no repeated elements, so there is no form…

With no form, which is what Terry proposes by abstracting away special numbers like 2 and 3, anything goes. So yes, I suppose infinite iteration of the 3x+1 map could give a transcendental output.

30 September, 2019 at 6:25 am

Jeff

To add, almost all real numbers are transcendental. But almost none of them form!

Ha! Seriously, this is modern mathematics.

30 September, 2019 at 8:50 am

Jeff

Again this is why the hypothetical divergent sequence is fascinating to me. The 3x+1 problem has a little of everything in it. And the iterations almost give it life.

What’s weirder yet, is Big Bang theorists are seemingly ignorant of the fact that their mathematical models of our universe use the axiom of infinity.

1 October, 2019 at 3:43 am

Jeff

In our minds we iterate the 3x+1 map a finite number of steps and then conclude that the process may hypothetically never EQUAL one. We do it with a single number and we do it symbolically with x. Recall x is a member of a set, and thusly ‘represents’ a single number. But x is not as ‘well defined’ as say the number 1.

So it really doesn’t matter whether the set of natural numbers is complete, in other words, that actual infinity exists. Potential infinity allows us to give form to as many numbers as we should need, where memory space and time are the only limitations.

To me if a divergent sequence were to exist, who cares? Besides where exactly would it exist?

3 October, 2019 at 10:03 am

Gastón Fernando Murillo Plúas

So the first step would be to demonstrate that divergent orbits are finite and being finite would necessarily involve a convergent orbit. So far this would serve to demonstrate that the convergent orbit does not involve another divergent orbit instead of ending in 1 I do not see a clear path.

3 October, 2019 at 9:01 am

Anonymous

Let $S$ be the set of positive integers which have finite Collatz orbits.
Let $f(n)$ denote the length of the Collatz orbit corresponding to any integer $n \in S$ . Is it possible (by these methods) to give an EXPLICIT bound for $f(n)$ for almost any $n \in S$ ?

3 October, 2019 at 11:33 am

Gastón Fernando Murillo Plúas

Separating them into ordered subsets yes, but only for the number of steps from an odd number to another odd number using 2 variables. For the number of steps up to 1 I think it involves many more variables.

5 October, 2019 at 7:29 am

notyetready

Heuristically, it is conjectured that the total stopping time $f(n) < \log n$ for all sufficiently large $n$ and $C \approx 42$ , provided that the an odd $x$ is mapped to $(3x+1)/2$ in a single step. Off course, no explicit upper bound can be proved up to now, at least for a positive density of the integers.

7 October, 2019 at 8:22 am

Gastón Fernando Murillo Plúas

Heuristically according to who?

7 October, 2019 at 1:56 pm

notyetready

See this paper of Lagarias and Weiss, dealing with stochastic models:
https://www.jstor.org/stable/2959662

8 October, 2019 at 9:49 am

Gastón Fernando Murillo Plúas

I read it. I find no sense in decreasing one iteration for each time an odd number is calculated. The amount of iterations has nothing to do with the initial value with which it begins to iterate. But let’s take an example of the method used, this is taking (3x + 1) / 2 as a step.

I can take the 1,628,896,171,349 that would be found at 14 iterations of the next odd number calculated, that is 298,259,797 that would be found at 14 iterations of the next one that would be 54,613 that would be found at 15 iterations of 5 totaling 43 iterations.

This is taking high potencies. Now let’s take low powers. From 8,097 to 5, I would have 43 iterations always calculating the next odd number with low powers, which is from 2 ^ 1 to 2 ^ 4 maximum.
But what if I take 43 iterations directly through 5? Then I would have to take the number 14,660,155,037,013 which is much greater than 1,628,896,171,349.

Of course it will be greater, logically that you will always have a greater number when you use a greater power at a value that you calculate twice with powers in half and worse with the difficulty of a 3x + 1 algorithm where you cannot count on 1 in 3 odd values to continue. The rest of logarithmic calculations on peaks of iterations is constant and inductive. But that does not mean that there cannot be an unbounded or infinitely divergent orbit, even if the latter is false.

9 October, 2019 at 6:53 pm

osobliwy_nick

To determine if there are divergent sequences, we must realize a fact that there are numbers – “engines”, that can accelerate a given string to infinity. And there are very few of them. These numbers are:

2^n*j-1
2^n*j-5, 2^n*j-7, 2^n*j-10
2^n*j-17, 2^n*j-25, 2^n*j-37, 2^n*j-55, 2^n*j-82, 2^n*j-41, 2^n*j-61, 2^n*j-91, 2^n*j-136, 2^n*j-68, 2^n*j-34

The numbers of this character always generate a number greater than themselves after n steps in the collatz sequence. Any other numbers of the form 2^n*j-k will not satisfy this relationship. Each 2^n*j-k number gives a number smaller than themself after n steps. Therefore the divergent sequence must regularly reach some number of characters:

2^n*j-1
2^n*j-5, 2^n*j-7, 2^n*j-10
2^n*j-17, 2^n*j-25, 2^n*j-37, 2^n*j-55, 2^n*j-82, 2^n*j-41, 2^n*j-61, 2^n*j-91, 2^n*j-136, 2^n*j-68, 2^n*j-34

Is it possible? I don’t know, but if we answer this question, we will solve the problem of divergent sequences.

10 October, 2019 at 6:10 am

Anonymous

Dear Pro.Tao,
After I” drank” beer “Collatz”, I felt the smell was very delicious. I want to drink beer “Twin” now. Hurry up! Sir. I am very thristy now.
Always forward to Sir,
Best of luck!

29 October, 2019 at 2:51 am

hooobla

Let $P(N)$ denote power set of $N$ (set of natural numbers). $P(P(.....P(N)...)$ for n iterations is denoted by $P(N,n)$ .Does there exists n such that there is bijection from $P(N,n)$ to $R$ ?

31 October, 2019 at 2:53 am

robfrotRob Frost

no, there is no ceiling on $n$ because e.g. $(2^{2n}-1)/3$ is a solution.

31 October, 2019 at 2:31 pm

Robert White

I have a computer program (visualizer) and computational analysis that proves the conjecture but I don’t have the math to express it in formal terms. The entire conjecture can be summarized as “hammering off significant digits destroys information”.

The insights come from the vector operators used in graphics routines where you load multiple scalars into a wide register and then work on (e.g. multiply) them all at once.

In essence, when viewed as an electronic computation in a register of infinite width you can ignore all the divide-by-two operations; in electronic computation dividing by two is just register shifting. The only reason to divide by two is to align the destructive +1 term with the least significant set bit in the register.

So once you replace the conditional divide-if-even and the aligned +1 with a vectorized operator to find the least set bit and add it into the term all the distracting “spirals” disappear.

The actual transformations at each step become
(1) Expansive Term -> N=N+3
(2) Destructive Term -> N+=(1<<count_trailing_zeros(n))

Now you have a finite state machine, a la Conway's game of life.

There are only four (if memory serves) possible bit patterns at the most significant position that the by which the Expansive Term can extend the value.

The Destructive Term can remove any number of bits up to but excluding the most significant bit.

There is no feedback system where bit N can affect any bit M where M is less than N.

Only a highly ordered least significant bitset can delay the destructive term, forcing ti to only consume one bit, but that ordered bitset creates a smaller, disordered bitset at its upper extent when processed by the Expansive Term; this means that the ordered bitset cannot propagate its properties indefinitely.

The result is that there can exist no bitset such that the Expansive Term can consistently produce as many extension bits as the Destructive Term consumes.

The visuallizer is super simple, but it's at home and I'm at work.

I can demonstrate all the validity of all the algorithmic transformations, including a version of the visualizer that works on the native (untransformed) original form of the function exactly as originally written.

I've been sitting on this for years but I don't know any mathematicians and everybody assumes the extra-disciplinary ideas are Dunning-Kruger madness.

1 November, 2019 at 3:31 pm

Robert White

Here’s the visualizer I discussed above. It uses the unmodified conjecture and does several simple things.

(1) It prints the binary from left-to-right least-to-most significant bit
(2) I counts up the number of times the term has been divided by 2.
(3) Puts in leading pad characters matching the number of times the divide/shift operation has taken place.

Arguments are [ [ ] ]

By default the fill character is underscore, but using a zero is particularly illuminating.

In the output mode you can use any value 1 through 7, lowest bit is “classic output mode” that shows the base conjecture result, second bit is show immediate value after multiply, third bit is show value after increment.

The default display value is six (6) which shows the condensed visualization without the “shift spirals”.

https://onlinegdb.com/S1c-3Vccr

Notice the montonic nature of the expansion, if forms a line of near constant slope. The destructive term has no such constraint.

The most interesting values are any 2^n and (2^n – 1) input. The former is an instant collapse to just one set bit, while the latter produces the longest possible sequence single-bit destructive delay possible for any number less than 2^n.

You just have to be ready to see the state machine instead of the divide-by-two spiral.

NOTE: visualizer not for non-positive numbers.

1 November, 2019 at 3:39 pm

Robert White

Self-reply…

My appologies, the web tool seems lock the arguments when I share the block. You may need to copy the code and paste it into a fresh project page.

The above block will run 1023 in classic mode, where the output is the classic conjecture “spiral”.

The below will run 1023 in the proof-visualization order.

https://onlinegdb.com/SkTCeH99H

Compare the leading and trailing line slopes.

1 November, 2019 at 3:50 pm

Robert White

/sigh : arguments are [ value [ mode [ fill character ] ] ]

I wish the forum allowed editing, the first try ate the definition because I used angle-bracket like you do in linux manual pages.

1 November, 2019 at 5:20 pm

Robert White

Ah, there’s that assumption again. No arguments against, just automatic downvote. 8-)

The data clearly shows that the Expansive term can only add one or two bits to the state machine while the Destructive term can remove any number from 1 to all-but-one bits in a single operation; and the two operations alway alternate one-for-one.

There is no possible bit pattern between the leading and trailing bits that can cause expansion by X1 or X01, and there is no pattern that sustain the all-ones pattern that prevents the destruction of more than one per cycle.

The internal disorder of the bits between the leader and trailer cannot stop the decay because a higher-order bit can never influence a lower-order bit in any way.

You just have to compare the pre and post increment values, which is where the information content of the number is discared/destroyed.

I’ll stop now.

1 November, 2019 at 9:24 pm

HCL

Why is the title of the paper not “Almost all Collatz orbits attain bounded values”?

My second question is:
Why is the title of the paper not “All Collatz orbits attain almost bounded values”?

Thank you!

7 November, 2019 at 7:36 pm

Jeff

Why all the press like in popular mechanics about a preprint that doesn’t prove anything at all on 3x+1?

Tell you what though. There has been a spike in arxiv preprints the past few months. Even my preprint picked up another citation. But I actually proved some theorems… but who cares :-).

6 November, 2019 at 8:52 am

y.y.

The page “Residue-class-wise affine group” in wikipedia writes “…Collatz conjecture, which is assertion about a surjective, but not injective residue-class-wise affine mapping.” Certainly, {2N_0+1} maps to {2N_0+1≢0(mod.3)}. but its inverse mapping, which is able to be bijection by rcwa with matrices. and I have found that. There can be defined easily “almost all odd” goes to small of itsef in n times iteration. and then also can be defined ￢”almost all odd” odd goes to small of itself in m times iteration by set theoritical way.

8 November, 2019 at 7:56 am

y.y.

and the equation(because there exists a bijective map between x and f^-1(x)) contains S3.

13 November, 2019 at 10:41 pm

Spesialcoklat WA:08984230641

By following pde coprogress dn/dq=(3n+2)/2^q have solution ln(3n+2)^(1/3)=-1/(2^q.ln2)~ln(2^2^q) then q~log2log2(3n+2)^(1/3)

15 November, 2019 at 7:03 pm

Rudi

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be defined by $f(n)=\frac{6n+1+M_k}{4}$ where $n\in\mathbb{N}$ and $k\in\mathbb{N}$ , and $M_k$ is a Mersenne number.

$k$ -index may be found by finding the highest exponent that divides $n$ . This can also be done by the bitwise exclusive or operator: $\oplus$

Or we define the function as:

Let $C:\mathbb{N}\rightarrow\mathbb{N}$ :
$C(n)=\frac{3n}{2} + \frac{n \oplus (n-1) + 1}{4}$ where $n\in\mathbb{N}$ .

This is my first post ever with latex code on wordpress, so hopefully it is displayed correctly. The problem is to prove that one of these functions at some time in their trajectory reaches 2^x (some power of two), Or that all the remaining factors remaining are just twos.

16 November, 2019 at 2:31 pm

Daniel Parry

I was playing around with this problem for fun and I found that the Syracuse map you described pops out of using characteristic functions to run the Affine map backwards. It seems to describe the minimal element in the limit as n\to \infty.

The sequence \vec{a} appears to be representing a path on the tree run in reverse. The minimal element of the cycle, as being part of a cycle, seems to imply that the a_i must be cyclical if it were to describe the minimum element.

Would this help in improving the analysis?

19 November, 2019 at 11:56 pm

isaac mor

in order to solve this problem you first need to get to the cycle bounds

like this:

Collatz Conjecture – Cycle bounds

x = number of even values in a cycle
y = number of odd values in a cycle

x+y < (8/9) * floor(1.5^y)

then you are lowering the limit even more …

to get to

positive cycles:

x = roundup ( y * ln3/ln2 )

negative cycles:

x = rounddown ( y * ln3/ln2 )

then you need to get the formula for the minimum cycle with the lower and higher values to be asa closest as possible

and then you can solve it :)

1 December, 2019 at 8:10 am

Georgiy

Best instrument to prove Collatz Conjecture is Canonical Collatz Tree
All details described in book
Proof of the Collatz conjecture (Problems – Ideas – Solutions) Amazon March 15, 2019 by Georgiytyshko Tyshko
Any questions and critics you may tell in
Howwewanttolive.livejournal.com

12 December, 2019 at 7:41 pm

vznvzn

hi TT fyi all heres a nice writeup in quanta mag
“Mathematician Proves Huge Result on ‘Dangerous’ Problem” https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/

delighted that you returned to this subj after ~8yrs. congrats on the recent results. a little annoyed with the tone of the article, but it probably does reflect widespread social anxiety about the problem. myself have called it like a “femme fatale”. there seems to be a semiconscious assumption of “all or nothing” on this problem even by the leaders in the field. what is wrong with incremental results? in a word, nothing!

collatz is an outstanding/ exceptional problem to work on. even if a researcher can see that a solution seems unlikely, new insights into the problem not seen elsewhere are not extremely difficult and feel theres no shame in pursuing them, quite to the contrary think its as honorable as the best of mathematics. it seems some of the aversion to this problem is that it hasnt been connected to any deep theory. but on the other hand, why not make the opposite conclusion, given that it doesnt seem to connect to anything known, that there must be deep *future* theory around here somewhere, that this is just a tip of an iceberg…!

my other complaint (and not pretending either that many are listening, lol) is that almost nobody talks about “fractals” in reference to this problem. there are some isolated exceptions. after many years of banging on it with computational experiments (and its great to hear you are not averse to them yourself) the fractal nature seems like a foremost aspect to approaching/ understanding it.

could write far more and have elsewhere, encourage visitors/ feedback https://vzn1.wordpress.com/category/collatz/

13 December, 2019 at 2:13 pm

Alberto Ibañez

I still think about the numbers of the form (8) of the previous post
$\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}$
For orbits that reach 1
$2^{ak+1}- n \times 3^{k}$ , they have this form.
For periodic orbits
$(2^{ak+1}-3^{k}) \times n$ , where k n numbers have this form
For unbounded orbits, none of the above conditions are met for infinite n numbers.

I have known this notable product, Difference of Nth Powers, which has a certain resemblance, with the problem at hand.

$a^{n}-b^{n}= (a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^{2}+...+b^{n-1})$

Could it be useful for the Collatz conjecture?

24 December, 2019 at 3:24 am

Alberto Ibañez

The intention of this strategy is to demonstrate that there are no unbounded orbits. The way to achieve it would be to know if it is possible to transfer the properties of the notable product difference of nth powers, that is, the form, (8), to any possible Collatz sequence. If there is a mechanism that converts the difference of nth potency into a Collatz sequence, and there is always an n such that the difference conserves the form (8), then perhaps, it would be possible to affirm that all the orbits are bounded to the nth power.
I have not found that mechanism, but perhaps for some of you, it is easier to find that mechanism, or of course, to rule out that possibility.
I present some examples in case someone sees how a difference of nth power is transformed into a sequence of Collatz, where the difference maintains the form (8).

For $3^{1}-2^{1}= 1$

$2^{4}-3^{1} \times {\color{Red} 5}= 1$
$2^{6}-3^{1 }\times {\color{Red} 21}= 1$
$2^{8}-3^{1} \times {\color{Red} 85}= 1$
…

For $3^{2}-2^{2}= 3^{1}+2^{1}= 5$

$2^{5}-3^{2} \times {\color{Red} 3}= 3^{1}+2^{1}=5$
$2^{7}-3^{2} \times {\color{Red} 13}= 3^{1}+2^{3}= 11$
$2^{9}-3^{2} \times {\color{Red} 53}= 3^{1}+2^{5}= 35$
$2^{10}-3^{2} \times {\color{Red} 113}= 3^{1}+2^{2}= 7$
…
For $3^{3}-2^{3}= 3^{2}+3^{1} \times 2^{1}+2^{2}= 19$

$2^{9}-3^{3} \times {\color{Red} 17}= 3^{2}+3^{1} \times 2^{2}+2^{5}= 53$
$2^{10}-3^{3} \times {\color{Red} 35}= 3^{2}+3^{1} \times 2^{1}+2^{6}= 79$
$2^{11}-3^{3} \times {\color{Red} 75}= 3^{2}+3^{1} \times 2^{1}+2^{3}= 23$
…

For $3^{4}-2^{4}= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{2}+2^{3}= 65$

$2^{10}-3^{4} \times {\color{Red} 11}= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{3}+2^{6}= 133$
$2^{11}-3^{4} \times {\color{Red} 23}= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{2}+2^{7}= 185$
$2^{12}-3^{4} \times {\color{Red} 45}= 3^{3}+3^{2} \times 2^{3}+3^{1} \times 2^{5}+2^{8}= 451$
…

For $3^{5}-2^{5}= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{3}+2^{4}= 211$

$2^{11}-3^{5} \times {\color{Red} 7}= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{4}+2^{7}= 347$
$2^{12}-3^{5} \times {\color{Red} 15}= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{3}+2^{8}= 451$
$2^{13}-3^{5} \times {\color{Red} 29}= 3^{4}+3^{3} \times 2^{3}+3^{2} \times 2^{4}+3^{1} \times 2^{6}+2^{9}= 1145$
…
…

**orbits belongs to numbers in red color.

***numbers with form (8) are

$\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}= 3^{k-1}+6\chi +2^{a_{k}}$

and numbers with form
$a^{n-1}+ a^{n-2}b+a^{n-3}b^{2}+...+b^{n-1}= a^{n-1}+ab\chi +b^{n-1}$

it’s obvious, but maybe $\chi$ may have relevance. Thanks

2 January, 2020 at 4:45 am

Alberto Ibañez

Examples of some know orbits

For $3^{1}-2^{1}= 1$

$2^{4}-3^{1} \times 5= 1$
$2^{6}-3^{1 }\times 21= 1$
$2^{8}-3^{1} \times 85= 1$
…

For $3^{2}-2^{2}= 3^{1}+2^{1}= 5$

$2^{5}-3^{2} \times 3= 3^{1}+2^{1}=5$
$2^{7}-3^{2} \times 13= 3^{1}+2^{3}= 11$
$2^{9}-3^{2} \times 53= 3^{1}+2^{5}= 35$
$2^{10}-3^{2} \times 113= 3^{1}+2^{2}= 7$
…
For $3^{3}-2^{3}= 3^{2}+3^{1} \times 2^{1}+2^{2}= 19$

$2^{9}-3^{3} \times 17= 3^{2}+3^{1} \times 2^{2}+2^{5}= 53$
$2^{10}-3^{3} \times 35= 3^{2}+3^{1} \times 2^{1}+2^{6}= 79$
$2^{11}-3^{3} \times 75= 3^{2}+3^{1} \times 2^{1}+2^{3}= 23$
…

For $3^{4}-2^{4}= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{2}+2^{3}= 65$

$2^{10}-3^{4} \times 11= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{3}+2^{6}= 133$
$2^{11}-3^{4} \times 23= 3^{3}+3^{2} \times 2^{1}+3^{1} \times 2^{2}+2^{7}= 185$
$2^{12}-3^{4} \times 45= 3^{3}+3^{2} \times 2^{3}+3^{1} \times 2^{5}+2^{8}= 451$
…

For $3^{5}-2^{5}= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{3}+2^{4}= 211$

$2^{11}-3^{5} \times 7= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{4}+2^{7}= 347$
$2^{12}-3^{5} \times 15= 3^{4}+3^{3} \times 2^{1}+3^{2} \times 2^{2}+3^{1} \times 2^{3}+2^{8}= 451$
$2^{13}-3^{5} \times 29= 3^{4}+3^{3} \times 2^{3}+3^{2} \times 2^{4}+3^{1} \times 2^{6}+2^{9}= 1145$
…
…

2 January, 2020 at 7:16 am

Alberto Ibañez

Now let’s look and compare some known orbits.

$3^{2}-2^{2}= 3+2= 5 \mapsto 2^{5}-3^{2} \times 3= 5$

$2^{2} \times 2^{3}= 3^{2} \times 2^{3}-5 \times 2^{3}$

$2^{2} \times 2^{3}= (3^{2} \times 2^{3}-3^{2} \times 5)-5 \times 2^{3}+3^{2} \times 5$

$3^{2}-2^{2}=3+2=5 \mapsto 2^{7}-3^{2} \times 13 = 3+2^{3}=11$

$2^{2} \times 2^{5}= 3^{2} \times 2^{5}-5 \times 2^{5}$

$2^{2} \times 2^{5}= 3^{2} \times 2^{5}-3^{2} \times 19-(5 \times 2^{5}-3^{2}\times 19)$

$3^{3}-2^{3}= 3^{2}+3 \times 2+2^{2}= 19 \mapsto 2^{9}-3^{3} \times 17= 3^{2}+3 \times 2^{2}+2^{5}= 53$

$2^{3} \times 2^{6}= 3^{3} \times 2^{6}-19 \times 2^{6}$

$2^{3} \times 2^{6}= 3^{3} \times 2^{6}-3^{3} \times 47-(19 \times 2^{6}-3^{3} \times 47)$

Is it possible to establish a general mechanism that relates the difference of nth power and the orbits of Collatz? Is this mechanism trivial or does it provide us with no interesting information?
At the moment I can not visualize this general mechanism, although obviously these are known orbits that end in 1, could we establish that there is always an n that meets equality and the difference preserves the shape? Could it be used to rule out the existence of periodic orbits? Thank you.

29 January, 2020 at 12:04 pm

Alberto Ibañez

https://drive.google.com/open?id=14de4QiGD147d1yIfnrupbTEtB2E-3idF
Hi everyone. Although there is a new post by Professor Tao, I wanted to close my approach to the conjecture with a basic scheme that summarizes my approach. The numbers of the form (8) share structure with the difference of nth power, which to simplify I call it TCR, Tao-Collatz Reminder.
The conjecture needs to answer two questions:
-1. Are there periodic orbits?
-2. are there infinite orbits?
We know that the conjecture is true for many values. All reach 1 and there are no periodic orbits (except the trivial).
This approach to the conjecture through the notable product difference of nth power could serve to illustrate the mechanism of why the orbits reach 1, and also how the mechanism of the periodic orbits works and why they cannot occur for the powers of 2 and 3 .
Once this question was resolved, one could then attack the existence or not of infinite orbits, or at least, do it independently.Thanks

23 February, 2020 at 2:52 am

Alberto Ibañez

Continuing with this approach to the Collatz conjecture from the notable product difference Nth powers and focusing on the study of periodic orbits, we find a condition that meets the known periodic orbits of maps $3n-1$ and $5n + 1$ .
For a periodic orbit, it is fulfilled that

$2^{k}< 3^{k}< 2^{k+y}< 3^{k}\times n< 2^{k+y}\times n$

Is this condition necessary for a periodic orbit?
Unlike the orbits that reach 1

$2^{k}< 3^{k}< 3^{k}\times n < 2^{k+y}$

Can this condition be possible in a periodic orbit?

For maps type $an-1$ we have that, for a periodic orbit

$2^{k}< 2^{k+y}< 3^{k}< 2^{k+y}\times n < 3^{k}\times n$

Unlike the orbits that reach 1

$2^{k} < 3^{k}< 2^{k+y}< 3^{k}\times n$ ,

their behavior is a little different, but the structure of the periodic orbits is equivalent.

Some concepts to consider:

-Multiples of 3 cannot enter periodic orbit.
-The notable product difference of nth powers is the value

$2^{k}-3^{k}=3^{k-1}+3^{k-2}\times 2^{1}+...+2^{k-1}$

whose structure coincides with the numbers of the form (8) from the post https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2- and-3 / , which I call $TCR$ for short, and that coincides with the minimum possible value for

$2^{k+y}\times n - 3^{k}\times n=n\times x= TCR_{min}$

– $2^{k+y}-3^{k}= x$ ,

$2^{k+y} \times n -3^{k} \times n= n \times x$

– $k+y$ is the number of even steps, then $y$ is the increment of divisions of 2 with respect to $k$

– $k$ is the number of even steps, and in a periodic orbit represents the cardinality of the set of odd numbers $(n_{1}< ... 1$
$2^{6}\setminus 3^{3}> 2$
$2^{7}\setminus 3^{3}> 4$
$2^{8}\setminus 3^{3}> 9$
$2^{9}\setminus 3^{3}> 18$
$2^{10}\setminus 3^{3}> 37$

If $x 3$

We can find the values of $n_{max}$ for each $2^{k+y}$ from the values of $TCR_{max}$

For $2^{5}\rightarrow TCR_{max}=49\setminus 5=(2^{k+y}-3^{k})\leq 9$
For $2^{6}\rightarrow TCR_{max}=89\setminus 37=(2^{k+y}-3^{k})\leq 2$
For $2^{7}\rightarrow TCR_{max}=169\setminus 101=(2^{k+y}-3^{k})\leq 1$
For $2^{8}\rightarrow TCR_{max}=329\setminus 229=(2^{k+y}-3^{k})\leq 1$

For this orbit, we can observe that when the values of $y$ increase, the distance $x$ increases much faster than $TCR_ {max}$ , which seems to make a solution incompatible that is not for values of $2^{k+y}$ closer to $3^{k}$ .

with the possible periodic orbit $3^{3}-2^{5}=5$ , we hava that $n_{min} > 3$ and $n_{max}\leq 9$ . The values 5,7,9 are possible solution but we know that 3 multiples cannot enter in a periodic orbit and we have not k solutions.
But it seems that we are missing something else, somehow we need to find a minimum value for $n_ {max}$ , that is, that between $n_{1}$ and $n_{k}$ there is a minimum distance within the possible solutions to the periodic orbit, which becomes more evident with the study of the possible orbits for $3^{4}$ , $3^{5}$ , …
Having explored several options,one of the possible ways to calculate the minimum value of $n_ {max}$ could be:

$\frac{TCR_{min}}{n_{min}}= \frac{TCR_{max}}{n_{max}}$

and we have that $\frac{19}{5}= \frac{49}{n_{max}}\Rightarrow n_{max}> 12$ , but in the orbit $n_{max}\leq 9$ , that is out of range. Although I understand that it seems a bit “ad hoc”.

-Periodic orbits for $3^{4}$ , where

$2^{7}-3^{4}= 47= x$ , $3^{4}-2^{4}= TCR_{min}= 65$ , $n_{min}= \frac{65}{47}> 1$ , $TCR_{max}= 331$ , $n_{max}= \frac{331}{47}\leq 7$ , $\frac{TCR_{min}}{3}= \frac{TCR_{max}}{n_{max}}\rightarrow \frac{65}{3}= \frac{331}{n_{max}}\rightarrow n_{max}> 15$

-Periodic orbits for $3^{5}$ , where

$2^{8}-3^{5}= 13= x$ , $3^{5}-2^{5}= TCR_{min}= 211$ , $n_{min}= \frac{211}{13}> 16$ , $TCR_{max}= 1121$ , $n_{max}= \frac{1121}{13}\leq 86$ , $\frac{TCR_{min}}{17}= \frac{TCR_{max}}{n_{max}}\rightarrow \frac{211}{17}= \frac{1121}{n_{max}}\rightarrow n_{max}> 90$

Of course it is necessary to implement this approach to $(k,n,x,y)\rightarrow \infty$ and improve the calculations of $n_ {min}$ , $n_ {max}$ , $TCR_ {max}$ and give rigor and mathematical structure, if possible, of course.Somehow it seems that for every possible periodic orbit between a power of 2 and 3 the $n_{max}$ value is always lower than the minimum $latex n_{max} needed to form a periodic orbit. I assume that this work, with my basic mathematics, can be totally useless, but, as always, I hope it can be useful to answer the question: Are there periodic orbits in the Collatz conjecture?
At your disposal. Thank you.

24 February, 2020 at 2:10 am

Alberto Ibañez

**note: I upload the comment again because a part has not been loaded and I have corrected some minor errors.

For a periodic orbit, it is fulfilled that

$2^{k}< 3^{k}< 2^{k+y}< 3^{k}\times n< 2^{k+y}\times n$

Is this condition necessary for a periodic orbit?

Unlike the orbits that reach 1

$2^{k}< 3^{k}< 3^{k}\times n < 2^{k+y}$

Can this condition be possible in a periodic orbit?

For maps type $3n-1$ we have that, for a periodic orbit

$2^{k}< 2^{k+y}< 3^{k}< 2^{k+y}\times n < 3^{k}\times n$

Unlike the orbits that reach 1

$2^{k} < 3^{k}< 2^{k+y}< 3^{k}\times n$ ,

their behavior is a little different, but the structure of the periodic orbits is equivalent.

Some concepts to consider:

-Multiples of 3 cannot enter periodic orbit.
-The notable product difference of nth powers is the value

$2^{k}-3^{k}=3^{k-1}+3^{k-2}\times 2^{1}+...+2^{k-1}$

whose structure coincides with the numbers of the form (8) from post https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3 /, which I call $TCR$ for short, and that coincides with the minimum possible value for

$2^{k+y}\times n - 3^{k}\times n=n\times x= TCR_{min}$

– $2^{k+y}-3^{k}= x$ ,

$2^{k+y} \times n -3^{k} \times n= n \times x$

– $k+y$ is the number of even steps, then $y$ is the increment of divisions of 2 with respect to $k$

– $k$ is the number of odd steps, and in a periodic orbit represents the cardinality of the set of odd numbers $n_{1}< ... 1$
$2^{6}\setminus 3^{3}> 2$
$2^{7}\setminus 3^{3}> 4$
$2^{8}\setminus 3^{3}> 9$
$2^{9}\setminus 3^{3}> 18$
$2^{10}\setminus 3^{3}> 37$

If $x 3$

We can find the values of $n_{max}$ for each $2^{k+y}$ from the values of $TCR_{max}$

$\frac{TCR_{min}}{n_{min}}= \frac{TCR_{max}}{n_{max}}$

and we have that $\frac{19}{5}= \frac{49}{n_{max}}\Rightarrow n_{max}> 12$ , but in the orbit $n_{max}\leq 9$ , that is out of range. Although I understand that it seems a bit “ad hoc”.

-Periodic orbits for $3^{4}$ , where

-Periodic orbits for $3^{5}$ , where

Of course it is necessary to implement this approach to $(k,n,x,y)\rightarrow \infty$ and improve the calculations of $n_ {min}$ , $n_ {max}$ , $TCR_ {max}$ and give rigor and mathematical structure, if possible, of course.Somehow it seems that for every possible periodic orbit between a power of 2 and 3 the $n_{max}$ value is always lower than the minimum $n_{max}$ needed to form a periodic orbit. I assume that this work, with my basic mathematics, can be totally useless, but, as always, I hope it can be useful to answer the question: Are there periodic orbits in the Collatz conjecture?
At your disposal. Thank you.

25 April, 2020 at 6:46 am

Alberto Ibañez

To finish this argument about periodic orbits we can establish that $2^{y}-3^{k} = d$ , we need $n_{1}.n_{2}, ... n_{k}$ values, at least, such that $n \times d$ have the form of TCR(8) and are between a min and max value. Let’s see a simple example

$2^{5}-3^{3}=5$

$TCR_{min}=2^{3}-3^{3}=3^{2}+3\times 2+2^{2}=19$

$TCR_{2}=3^{2}+3\times 2+2^{3}=23$

$TCR_{3}=3^{2}+3\times 2+2^{4}=31$

$TCR_{4}=3^{2}+3\times 2^{2}+2^{3}=29$

$TCR_{5}=3^{2}+3\times 2^{2}+2^{4}=37$

$TCR_{max}=3^{2}+3\times 2^{3}+2^{4}=49$

We can see that of all the possible values, none is a multiple of d, so they do not meet this condition. This fact must be maintained, if the conjecture is true, for all distances between $3^{k}+d=2^{y}$ . For all possible values, there are no k values multiple of d.

28 April, 2020 at 7:49 am

Alberto Ibañez

A possible way to study possible periodic orbits

$n\times (2^{y}-3^{k})=3^{k-1}+3\times x+2^{^{k-1,...,y-1}}$

Or otherwise

$n=\frac{3^{k}-2^{k}+\triangle TCR}{2^{y}-3^{k}}=\frac{3^{k}-2^{k}+\triangle TCR}{(2^{y}-2^{k})-(3^{k}-2^{k})}$

$\triangle TCR$ = increments from minimum to maximum value, and it can take values

$\triangle TCR=3x+2^{k+1,k+2,...y-1}$ , where x can be 0

$2^{y}-2^{k}=2^{k}\times (2^{y-k}-1)$

Is possible?

13 December, 2019 at 11:45 pm

Smith foster

How about this way?
If it’s possible to prove the equation
“2^a+(2^b-1)/3+3c=n”
is correct, which means ,to each positive integer “n”, there is a series of numbers “a” “b” “c”(they are all positive integer, and they are not related to each other ) to make up the “n”.
Because when you list the numbers from “1” to a larger number according to the forming order, there is no branch until it’s “16”, either “5” or “32” is ok to result in “16” , and if you continue to list the numbers, you’ll find these three basic forms are ok to result in “1” .
Actually I’ve found there are some mistakes this way, but does this conception work?

15 December, 2019 at 8:52 pm

thor

There are 8 kinds of odds for 16k+1, 16k+3, 16k+5, 16k+7, 16k+9, 16k+11, 16k+13, 16k+15. If you can prove after some steps, the 8 kinds always appear in same probability, the odd numbers will keep getting smaller. The Collatz conjecture can be proved.

16 December, 2019 at 1:45 am

Giả thuyết 3n+1 | REDSTAR-BLOG DÀNH CHO TOÁN

[…] đây nhà toán học lỗi lạc Terence Tao vừa có một bước tiến lớn sau vài thập kỉ cho giả thuyết 3n+1 hay còn được gọi là giả […]

16 December, 2019 at 10:30 pm

Matt: Comments And Collatz Conundrum - RSSFeedsCloud

[…] always said that comments are the best part of blogging, but this is a particularly cool example. Here’s Terence’s latest post on it, with an excellent comment thread […]

18 December, 2019 at 12:50 am

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明！ - 程式筆記

[…] Almost all Collatz orbits attain almost bounded values […]

18 December, 2019 at 3:02 pm

Michael Mark Ross

Collatz sequences are essentially a parlor trick. While I’m sure Professor Tao has uncovered much of value in his recent paper, the 3x+1 problem has no intrinsic value. I can state the solution in its simplest form as just this:

Given three arithmetic operations, a, b, c:

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

For every odd number n, either a or b or c is a whole odd number. That’s it – everything else is embellishment and ornamentation (in particular, the even numbers).

For visual thinkers: https://drive.google.com/file/d/1iY7HMO0BJbdw9EQX3BnYGvXDyBNQ1ITH/view

18 December, 2019 at 6:08 pm

Jeff

Don’t think we’ll see revision 3 any time soon. But for you, what about 3x-1?

18 December, 2019 at 4:09 pm

Michael Mark Ross

I must rephrase that for the sake of proving I can write grammatical English: “For every odd number n, only a or b or c can be a whole odd number.”

19 December, 2019 at 2:45 am

Jeff

You have to prove that the usual two piece 3x+1 function is ‘equivalent’ to your three piece function on the odds. This is the so called ‘transference’ Terry wants for his preprint, but is impossible to achieve in way one can extract trustworthy results from with a probabilistic approach. So prove equivalence, Then you can work with your new function and rigorously prove stuff to knock our socks off with:-). It is not enough that only one of either a, b or c is odd for a given odd input.

19 December, 2019 at 10:24 am

Jeff

How many odds have you tested? Any professional number theorist would perk up at an opportunity to explain why the two mappings coincide on the odds under repeated iteration.

19 December, 2019 at 10:45 am

Jeff

Also, proving equivalence in this case and for larger classes of functions may be really helpful in and of itself. But you will still be stuck trying to prove the non existence of non trivial cycles for 3x+1. And your a results in an increase to the sequence whereas b and c give decreases.

But your observation is really good. Glad you have kept pushing it into the public eye!

19 December, 2019 at 12:23 pm

Jeff

Charles Cadogen already proved your c. It should not be too hard to prove your a and b and establish equivalence.

19 December, 2019 at 12:40 pm

Jeff

Hmm maybe not. 13 maps to 5 under 3x+1 but it maps to 3 under your map. Am I missing something? This is why I asked how many odds you have checked.

Nonetheless, something of value may truly be found in your observation. Calculations should guide you here.

20 December, 2019 at 7:46 am

Sharmila Kopanathi

Dear Prof. Tao and the rest of the research community,
I apologize for barging into a research discussion forum to seek your urgent help, but such is my current circumstance. I left the US for India in 2013 to work on a couple of unsolved problems on my own. I got some preliminary results related to integer factorization in Oct 2017. Since then, my laptops have been taken over, I was put on 24/7 surveillance and my house has been bugged. They have practically taken over my life, preventing me from enjoying even momentary solitude to continue my work. They stole my past and present work. They started using advanced psychological torture techniques against me taking advantage of my inability to cope due to severe anxiety associated with this situation. They started commenting online about my most private activities. I experienced sudden shocks to my brain several times during these past 5 years. I experienced facial paralysis and reduced vision. This terror campaign continues to this day. They have recruited my neighbors as well to harass, humiliate and invade my privacy 24/7 from close proximity. They destroyed 5 years of my precious life. The local police, the FBI , IC3 have not been of any help. I tried sending you, Profs. Manindra Agrawal,, Manjul Bhargava emails. I even spoke to Prof. Agrawal a couple of times. He even acknowledged that he received my email. I have since been blocked from contacting anyone n the US, Please help me escape this terror campaign. Thank you. My gmail is not secure. Nor is my twitter account.
Sincerely, Sharmila Kopanathi

20 December, 2019 at 1:08 pm

Michael Mark Ross

Thank you for the generous response to my post. Here is essentially the same thing (I hope my latex works) as a function using congruence classes.

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

The table should show why this has to be an infinite function.
https://drive.google.com/file/d/1yDClElWLnm1H-dsa_KeBorcl44A8yNfY/view?usp=sharing
(You’ll notice that input a, b, c and output a, b, c have a fixed combination of 16 pairs.)

P.S. I’m an empiricist. I can’t provide proof, just observation.

20 December, 2019 at 6:04 pm

Jeff

Well, the sequence of odds matches for n=27. What other values of n give matches. Just look for a pattern. The proof will follow from a pattern. You may end up with an infinite subset. That would be nice. Do all multiples of 3 match? For example…

20 December, 2019 at 6:18 pm

Jeff

Well, double check your calculations for n=27. Not all match.

21 December, 2019 at 3:39 am

Alberto Ibañez

Hello @michael @jeff. I do not understand the strategy.Could you please explain as simple as possible?. Later I will try to explain my approach about notable product difference nth power and the form of odd numbers $n /not equiv 0 (mod3)$

20 December, 2019 at 1:13 pm

Michael Mark Ross

Here is the function: https://drive.google.com/file/d/1V0zV1P7tY7f2qtkobhEIlFs2vUqvEo0l/view?usp=sharing

21 December, 2019 at 1:46 am

Michael Mark Ross

Not quite sure I understand what you’re saying about 27. Nothing unusual about 27 except it’s divisible by 3 – and therefore would not occur in a 3x+1 sequence. Such numbers belong to a proper superset of the odd members of a 3x+1 sequence. The third congruence class in fact contains every odd number. So yes every odd output number is repeated twice, but for different inputs. However, that’s where it becomes interesting in showing why cyclicality is possible for 3x>1, but not for 3x+1.

21 December, 2019 at 5:44 am

Jeff

Repeated Iteration of the 3x+1 map starting with x=27 gives a subsequence of odd numbers which is,

27, 41, …, 1 where upon the 1 repeats.

I thought the sequence you have in your spreadsheet has some mistakes. But now I think you are trying something different. What I’m suggesting is you list the elements of your sequence next to the one given by 3x+1.

Then see which iterations match and then look for a pattern. So you are working visually…

21 December, 2019 at 6:00 am

Jeff

The only way you can use your function to make rigorous deductions about 3x+1 is to show exactly where they behave the same. So I’m trying to point you in that direction.

Of course a probabilistic approach is doomed from the get go :-).

21 December, 2019 at 1:49 am

Michael Mark Ross

(Repeated twice when tabulating – obviously not twice in sequences.)

21 December, 2019 at 8:43 am

Jeff

It would be a big task, but an addendum to the various outdated surveys on 3x+1 listing proof strategies in plain language would be very helpful, in my opinion.

List a strategy, then state what worked and what failed and why. There are bound to be hundreds of strategies. A big Class includes the various probabilistic approaches. They cannot work! It is not even debatable.

In this way we can track things, avoid making the same mistakes more than once etc. But speaking from personal experience, one has to be able to convince themselves of when a given strategy fails to hold promise!

21 December, 2019 at 9:18 am

Michael Mark Ross

Jeff, do you understand the unvarying and by definition regularity of the table? https://drive.google.com/file/d/1yDClElWLnm1H-dsa_KeBorcl44A8yNfY/view. Further you can demonstrate the divergent series (algroithmically here) is the same as the convergent series, which is unique for a given n:
Do
a = ((n + 1) * (2 / 3)) – 1
b = ((n – 1) * (4 / 3)) + 1
c = (n * 4) + 1

If a = Int(a) Then
n = a
ElseIf b = Int(b) And Modop(b,2) 0 Then
n = b
ElseIf c = Int(c) Then
n = c
End If
Loop
Then you need only show that no two a or bs can point to the same c, since c is a series of every odd number. You do this by looking at contradictions (loops) for any case pf 3x>1. These are easy to find. What’s the difference? It’s quite subtle. I have the answer to this.

Anyway, I truly appreciate your interest, and there are always communication difficulties when essentially texting. All the best!

21 December, 2019 at 1:18 pm

Jeff

Okay, I’m going to put forth a real effort to see what you are seeing. I checked your sequence of odds starting with 27. It contains every single odd given by 3x+1 and in the exact order. However, it also contains extra odd terms,

111,607,769,81,15 and 3, and in that order. Do I have that much correct?

21 December, 2019 at 1:22 pm

Jeff

111,607,769,81,15, 13, and 3

21 December, 2019 at 1:55 pm

Jeff

And these are exactly the values for which your function says to subtract 1 and divide by 4. Okay, so your c or your otherwise part of your function should instead read: if n is congruent to 8 modulo 5. I’ll look at it more later:-).

21 December, 2019 at 1:56 pm

Jeff

I mean 5 modulo 8…

21 December, 2019 at 2:29 pm

Jeff

Back again, for your a,b and c you need to say

n congruent to 3 modulo 4,
n congruent to 1 modulo 8, and
n congruent to 5 modulo 8, respectively.

This helps make it clear that it is a function on the odds because the Union of the sets given by those forms is all of the odds. Next you need to see what the range of your function is. Can you do that?

21 December, 2019 at 5:01 pm

Jeff

Once you check the range you’ll see an easier way to write your function by comparing it with 3x+1.

f = 3n+1 for n congruent to 3mod4 or 1mod8
= (n-1)/4 for n congruent to 5mod8.

So iterates of your function are the same as 3x+1 for all odd values apart from ones of the form 8x+5.

So super interesting. Wondering if anyone else is going to chime in?

21 December, 2019 at 5:28 pm

Michael Mark Ross

As I think you see, the superset numbers are all in C, divide by 2 twice. More here: https://www.quora.com/Why-is-the-Collatz-conjecture-so-resistant-to-being-proven-or-disproven-I-would-think-that-a-solution-lies-along-the-convergence-to-powers-of-2-path/answer/Michael-M-Ross

21 December, 2019 at 5:31 pm

Michael Mark Ross

With respect to congruence, it’s very clear-cut if you see the three operations in the function must be taken sequentially: https://www.quora.com/Why-hasnt-the-Collatz-conjecture-been-proven-yet-when-it-sounds-so-logical/answer/Michael-M-Ross

21 December, 2019 at 7:26 pm

Jeff

Well, written in the way I suggest may allow you to prove whether subsequences of just the odd values of 3x+1 sequences are in fact subsequences of those given by your function for every odd starting value. That’s what you want to know.

22 December, 2019 at 4:08 am

Jeff

Wait a minute, I goofed trying to translate it. Your function is

f = (3n+1)/2 if n is congruent to 3mod4
= (3n+1)/4 if n is congruent to 1mod8
= (n-1)/4 if n is congruent to 5mod8.

My comment still applies. If you can prove what I suggest, then you will have established ‘equivalence’.

At that point everyone would want to revisit old proof strategies with your new function. Because your function ‘would’ amount to a major simplification.

If you cannot prove it, calculations may help show why not…

22 December, 2019 at 4:21 am

Jeff

And a note to the readership. It would be unethical to dance off into the sunset with Michael’s observation and try to pass off whatever immediate results may follow as your own.

Please give Michael a chance to prove or disprove the desired equivalence exists.

24 December, 2019 at 12:32 pm

Jeff

Michael, it is a tad tricky but not too hard to prove. Your function is equivalent to 3x+1 in the way I stated above. Try to prove it. Hint: the only tricky part is to check what happens with starting values of the form 32n+5.

Merry Christmas!

Your name deserves to be coauthor on every immediate publication that should follow using your observation.

It may not help us settle the Conjecture, but it already constitutes legitimate partial progress!

Good job sir.

25 December, 2019 at 12:10 am

面对数学史上最简单的未解之谜，陶哲轩给出了几十年来最重要的证明 – 克拉茨 – 每日要闻

[…] Almost all Collatz orbits attain almost bounded values […]

25 December, 2019 at 5:23 pm

E.xu (@Exu16749831)

1 Collatz Process and Inverse Collatz Process are both Deterministic Processes
2 Collatz Process has only One Cycle the Trivial Cycle and Inverse Collatz Process has No Cycle
3 Two Collatz Processes can only Intersect Once by Merging Into Same Collatz Process … Two Inverse Collatz Processes do not intersect .. A Collatz Process and A Inverse Collatz Process can only Intersect Once ..
4 Inverse Collatz Map maps a Collatz Process with n tuples inverse-surjectively to roughly n/6 Inverse Collatz Processes
5 suppose there was a Collatz Process with Infinite Tuples then there must be a Minimal Tuple confining the Collatz Process .. so the Maximal Tuple of the Collatz Process goes to infinity
6 by abusing Heuristic Argument it can be presumed that the Sizes Of Steps Of Collatz Process Converge .. so it can also be Naively Presumed that the Size Of Steps Of Inverse Collatz Process Diverge …
8 Suppose there was Collatz Process with Infinite Tuples and Minimal Tuple m .. Naively the Sizes Of Steps Of This Collatz Process converge to 1 after ${frac\{log m}{log 4/3}}$ steps .. Use Inverse Collatz Map to Map this Collatz Process Inverse-Surjectively to roughly m/6 Inverse Collatz Processes with Infinite Tuples and Minimal Tuple m … Pigeon Hole Principle says that This Collatz and those Inverse Collatz Processes Must Intersect More Than Once … which can be seen as Proof By Contradiction ..

26 December, 2019 at 12:09 pm

Jesse Nochella

I made a Wolfram Demonstration on the Inverse Collatz function about 10 years ago.I know proofs can be easy to some. Lets just consider.the inverse n/2 -> 2n. we know this generates all powers of 2. Okay, so what’s the first 3n+1 -> (n-1)/3 we do to every other power of 2 as we go up the chain? It creates a repeating binary pattern of 101010101… depending on how many powers of 2 it has. The collatz conjecture can be proven by saying that you can generate every natural number with this tree sequence. Therefore every (n-1)/3 generates a class of numbers and every 2n can augment them,

There is thus a mapping to the sequence of 1’s and 0’s that correspond as to whether you used 3n+1 or n/2 in the sequence to every natural number and there is a pattern to it.

26 December, 2019 at 2:59 pm

michaelmross

Jeff, try this:
https://docs.google.com/document/d/1qwgmMbmC7emrbuZQLVCtOWFPDuxd7UDXxOkpnCQ2GRw/edit?usp=sharing

27 December, 2019 at 8:07 am

Jeff

Hi Michael. It’s very hard to read for me. You’ll get more mileage with it if you write the function as I suggested sir. As sets, the intersection of the forms 4n+3 , 8n+1 and 8n+5 are empty. And the Union is all odds. So this notation alone replaces several paragraphs and your table. No need for the algorithm or to track three columns of calculations as examples and so on. You just say repeated iteration gives…

27 December, 2019 at 9:54 am

Jeff

Michael. Here is a link to paper you can use as a guide to help you with notation and a proof. You are working in the forward direction just like the author here is

By proving equivalence as stated above you will have that nonexistent nontrivial cycles from repeated iteration of your map implies no nontrivial cycles from iteration of the 3x+1 map.

You still have to prove stuff with your map. At worst it will give us new insight. At best it will give us a way to settle the Conjecture. So it is a great observation.

It replaces the even numbers with some odd numbers.

27 December, 2019 at 4:16 pm

michaelmross

Jeff, that paper is too advanced, too elaborate, and too long for me. I see this as a very thin problem at its foundation – as simple as “a,b,c” in fact*. That’s why I have clarity on it. My little paper shouldn’t be hard to read – I’m disappointed!

Let me summarize what I said:
— I initially state all sequence steps conform to a function with three outputs: a,b,c. I also show an algorithmic equivalent based on there being 1-in-3 whole numbers for all outputs.
— Then I demonstrate that the operations that produce the three outputs conform exactly with what can happen with division by 2 in the conventionally stated 3x+1 problem – by analyzing factors of 2 (and 3). Note that the nonobviousness of this approach is because I’m looking only at the odd numbers but performing the “trick” of a transform back to even.
— Having shown there can only be three outputs by definition, I show the equivalence of results for 3x+1 and a,b,c. I also provide a table to clarify the relationship between odd and even numbers and factors – and that the three outputs for sequential odd numbers (n*1.5, n*0.75, and n*0.25) repeat infinitely.

It was your suggestion to find an equivalence to the a,b,c function – and that turns out to be the factors of 2 for n-1 and n+1. Thanks!

* When this is generally realized, it could be a singular embarrassment to mathematicians.

27 December, 2019 at 5:41 pm

Jeff

They embarrass themselves by handing out awards to folks who almost prove stuff, but who don’t really prove anything of merit or usefulness. The author of that paper really proves stuff, but pays lip service to references that don’t.

His approach and notation is exactly what you want to use if you wish to reach a wider audience. But this is just my suggestion. I can’t help you anymore than this Michael.

Wishing you all the best!

27 December, 2019 at 6:29 pm

michaelmross

Pleasure talking with you Jeff!

1 January, 2020 at 3:06 am

Maths student

Dear Prof. Tao,

I hope that nobody will mistake the following for an attack, but it seems as though current mathematical methods in additive combinatorics and related subjects are mostly adequate for tackling qualitative phenomena, instead of quantitative ones. The most important problems you’ve solved seem to be qualitative ones, instead of quantitative ones.

W/BR

1 January, 2020 at 8:56 am

Terence Tao

In analysis (including additive combinatorics) there is always a tradeoff between the quantitative strength of the results obtainable by current theory, and the breadth of that theory; and to make progress we need people working at all locations of the frontier of this tradeoff (and interacting with mathematicians at other locations on the frontier). I actually view my research as sitting roughly at the midpoint of this frontier; on the one hand a fair part of my research concerns taking some general but very qualitative results obtained using such “soft” methods as ergodic theory or compactness methods, and converting them to bounds that are quantitative but rather poor (e.g., exponential or even tower exponential in nature, and often with implied constants that are not explicit, and sometimes even ineffective). On the other hand the type of results I and my coauthors produce have sometimes been made more quantitative by other authors. For instance, several years ago Tamar Ziegler and I used ergodic theory and nonstandard analysis methods to prove the first concatenation theorems for Gowers type norms, in which control of a function in many local Gowers norms could be concatenated into control in a single global Gowers norm. The arguments were somewhat difficult and entirely qualitative. However, recently Sarah Peluse and Sean Prendiville have found much more quantitative Fourier-analytic methods to establish concatenation theorems that gave significantly better results; their proof techniques are quite distinct from ours, but I think it is fair to say that they might not have known to try to prove such quantitative theorems if the qualitative theorems of Tamar and myself had not already been in the literature. This seems to be the general pattern in the broader ecosystem of research in analysis: “soft” methods give the initial outline of what the true theory should look like, which then inspires later “hard” methods to come in and make the theory more efficient, more quantitative, and more powerful. Even if the soft results do not directly make progress on quantitative problems, they often show the way and help build up a general “big picture” intuition as to what type of quantitative results one should expect to be true, what their relative difficulties will be, and what type of techniques would be effective in attacking them.

There is a similar role played by many other tradeoffs in analysis, in which results in weaker regimes yield insight on the contours of the problems in stronger regimes. In the results in this current blog post, the main tradeoff here is between “almost all” results and “all” results, which I have already discussed in previous comments. Other tradeoffs include perturbative vs. non-perturbative regimes, high-regularity data vs. low-regularity data, non-uniform bounds vs. uniform bounds, low dimension vs. high dimension, toy model equations vs. physically realistic equations, discrete vs. continuous (or vice versa), non-Archimedean vs. Archimedean domains, constant coefficients vs. variable coefficients, ineffective vs. effective bounds, etc., etc.. The “horizontal” progress of exploring how a theory changes as one varies these parameters, when viewed narrowly, may not appear at first to make direct “vertical” progress on attacking the original problems that motivate that theory, but when viewed more broadly, this horizontal exploration often generates very valuable indirect progress, for instance by generating useful toy models of these problems as a test bed for intuition and strategies (and in particular to generate key “vertical” breakthroughs that can then later be transferred horizontally back to the original problem).

1 January, 2020 at 3:57 pm

Gim Towers

You write way too well :)

2 January, 2020 at 10:58 am

Anonymous

Is it really your name ?

7 January, 2020 at 8:25 am

E.xu (@Exu16749831)

i did not think you to take this as big deal .. it was Intersection Of Deterministic Processes and Deterministic Inverse Processes With Sizes Of Steps fit in probabilistic pattern .. Collatz Process is Not Random Process .. if you can not Probabilistic Methods ..

7 January, 2020 at 8:27 am

E.xu (@Exu16749831)

i saw you were trying to Factorize Characteristic Function .. Gap-Between-Two-Consecutive-Primes trick can not be used to prove Collatz Conjecture ..

29 January, 2020 at 11:57 pm

armchair speculations

Ramsey theory as currently formulated is not all that quantitative to begin with. The functions of interest are so hard to compute or approximate (even very crudely) that gathering useful experimental data is impossible. I think it is safe to say that there are no credible conjectures on the true growth rate of most Ramsey-style problems or what quantities might control the problem.

It seems to me that this is inherent in considering arbitrary colorings and that some sort of order parameter(s) are missing from the story. e.g. the number of irregular pairs plays this role in Malliaris and Shelah’s analysis of the regularity lemma for graphs.

2 January, 2020 at 10:48 am

gregmonahangmailcom

Dr. Tao

An amateur mathematician, so be gentle.

This certainly isn’t a proof, but consider this approach.

Select a number N that is sufficiently small enough that the numbers 1-N can be inspected to show that they collapse to 1. Call this set of numbers S because they represent the current solution set.

Now consider the set of numbers 1-2N. The numbers 1-N are already in the solution set S. The even numbers between N+1 and 2N have a second number that is half their value and lands them in the solution space S which is solvable. The result is that all even numbers between N+1 to 2N are also in the solution space S. This implies that all even numbers are in the solution space S.

Every odd number in the range N+1 to infinity is multiplied by 3 and then added by 1. Any odd number multiplied by another odd number (like 3) yields an odd number. Adding 1 makes this second number an even number. We’ve already shown that all even numbers are in the solution space S. We’ve now shown that any odd number above N yields an even number that eventually yields 1.

2 January, 2020 at 11:15 am

Anonymous

Your claim that all even numbers are in $S$ seems to be false (just try to write its proof …)

2 January, 2020 at 2:10 pm

michaelmross

You know you can exclude “S”. You don’t need a single even number to yield 1 and yet generate every odd number in a sequence. You just restate the conjecture. Algorithmically, it’s trivial to demonstrate this:

Do
If Modop(n + 1, 4) = 0 Then
n = ((n + 1) * (3/2)) – 1
ElseIf Modop(n – 1, 8) = 0 Then
n = ((n – 1) * (3/4)) + 1
Else
n = (n – 1) * (1/4)
End If
Loop

2 January, 2020 at 7:28 pm

Rason Lee

Greetings from Singapore. I wrote a computer programme in javascript to group starting numbers N by their orbits’ upper bound sequence should there be at least one other matching, if not, by their upper bound values (as far as I observed, all numbers group by these two variables). Running the programme for up to N = 10 Million, I further observed the trend that numbers temporarily grouped by their upper bound values will eventually fall into a collection based on their upper bound sequence. The trend of matching density in log scale is as follow –

Percentage of non-matching sequences:
…up to 10: 4 / 4 = 100%
…up to 100: 15 / 49 = 30.6%
…up to 1,000: 222 / 482 = 46%
…up to 10,000: 540 / 3,821 = 14%
…up to 100,000: 550 / 34,622 = 1.59%
…up to 1,000,000: 548 / 343,839 = 0.159%
…up to 10,000,000: 544 / 3,427,576 = 0.0159%

Prima facie is that the resultant percentage oscillates (wobbles) to an approximately steady state of ×0.1 per decade, while the absolute number of non-matching sequences appears to decrease after 100,000. Suppose the number of non-matching sequences reaches and remains at 0, then all possible orbits’ upper bound sequence would have logically been identified. Hence, I believe with greater computing power (which I have not), it can be superficially/ergodically concluded that all numbers will eventually fall into a convergent orbit by an underlying upper bound sequence pattern that can be extrapolated to infinity, despite the formal mathematical relationship between the orbits being unknown.

More of my thoughts in the following Facebook post where I included in the comments a maze analogy and proof of no periodic orbit for N > 1 – https://www.facebook.com/iplaytherecorder/posts/10157656812184519

p/s I started on the problem from scratch a week ago without knowledge of prior art, thus I’m not sure if I have used the right jargons or made any new insights. Pedagogical-wise, my bias is towards explaining things like I’m fresh out of high school, so as to better promote STEM education and interest in related innovation to the general public.

Thanks for reading and best regards.

2 January, 2020 at 7:48 pm

Rason Lee

pp/s Append below sample outputs of my javascript programme to clarify what I termed as “upper bound sequence” and “upper bound value” –

Note: sequence ‘x’ denotes (×3+1) and ‘d’ denotes ÷2

Upper bound sequence/value of odd numbers up to 77 –
Starting numbers with upper bound sequence xxdx: 3,11,19,35,43,51,67,75
Starting numbers with upper bound sequence x: 5,13,17,21,29,33,37,45,49,53,61,65,69,77
Starting numbers with upper bound sequence xxdxxdxdx: 7,23
Starting numbers with upper bound sequence xxddxdx: 25,57
Starting numbers with upper bound value 52: 9
Starting numbers with upper bound value 160: 15
Starting numbers with upper bound value 9232: 27,31,41,47,55,63,71,73
Starting numbers with upper bound value 304: 39,59
Percentage of non-matching sequences: 12/38 = 31.6%

Upper bound sequence/value of odd numbers up to 79 –
Starting numbers with upper bound sequence xxdx: 3,11,19,35,43,51,67,75
Starting numbers with upper bound sequence x: 5,13,17,21,29,33,37,45,49,53,61,65,69,77
Starting numbers with upper bound sequence xxdxxdxdx: 7,23
Starting numbers with upper bound sequence xxdxxdxdxxdxdxdx: 15,79
Starting numbers with upper bound sequence xxddxdx: 25,57
Starting numbers with upper bound value 52: 9
Starting numbers with upper bound value 9232: 27,31,41,47,55,63,71,73
Starting numbers with upper bound value 304: 39,59
Percentage of non-matching sequences: 11/39 = 28.2%

3 January, 2020 at 1:03 pm

La conjetura 3x + 1 está cerca de resolverse | – Juegos Online Paraguay

[…] escribe en su blog: «estamos ante una situación en donde parece haber una gran brecha entre «casi […]

3 January, 2020 at 4:58 pm

La conjetura 3x + 1 está cerca de resolverse - Comunidad Informativa

[…] escribe en su blog: «estamos ante una situación en donde parece haber una gran brecha entre «casi todos» y […]

3 January, 2020 at 7:01 pm

La conjetura 3x + 1 está cerca de resolverse - Descargas Noticias y todo

[…] escribe en su blog: «estamos ante una situación en donde parece haber una gran brecha entre «casi […]

5 January, 2020 at 12:31 pm

Rason Lee

Correction to above trend analysis due to a mistake in array sizing. Further tallied inter-decade matching rate and concluded similar, though on a different premise. It is observed that overall matching appears to tend to 100% still, however the graph is more likely to resemble underdamping throughout, and perhaps perpetually. Hence the eventual phenomenon of “almost all orbits” could be an effect of point sampling bobbing at 100%, i.e. an infinite number of upper bound sequences exists, but the matching trend towards and about 100% necessarily implies that all orbits are bounded. Tally outputs as follow –

Percentage of non-matching upper bound sequences for odd numbers up to 100 = 15 / 49 = 30.6%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 3 / 4 = 75.0%;
Percentage of matching upper bound sequences from above 10th percentile = 29 / 44 = 65.9%.

Percentage of non-matching upper bound sequences for odd numbers up to 1,000 = 239 / 499 = 47.9%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 3 / 15 = 20.0%;
Percentage of matching upper bound sequences from above 10th percentile = 215 / 449 = 47.9%.

Percentage of non-matching upper bound sequences for odd numbers up to 10,000 = 1,252 / 4,999 = 25.0%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 32 / 239 = 13.4%;
Percentage of matching upper bound sequences from above 10th percentile = 3,386 / 4,499 = 75.3%.

Percentage of non-matching upper bound sequences for odd numbers up to 100,000 = 8,363 / 49,999 = 16.7%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 245 / 1,252 = 19.6%;
Percentage of matching upper bound sequences from above 10th percentile = 37,150 / 44,999 = 82.6%.

Percentage of non-matching upper bound sequences for odd numbers up to 1,000,000 = 62,924 / 499,999 = 12.6%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 1,826 / 8,363 = 21.8%;
Percentage of matching upper bound sequences from above 10th percentile = 390,559 / 449,999 = 86.8%.

Percentage of non-matching upper bound sequences for odd numbers up to 10,000,000 = 499,887 / 4,999,999 = 10.0%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 15,856 / 62,924 = 25.2%;
Percentage of matching upper bound sequences from above 10th percentile = 4,024,211 / 4,499,999 = 89.4%.

Percentage of non-matching upper bound sequences for odd numbers up to 100,000,000 = 4,009,615 / 49,999,999 = 8.02%;
Percentage of non-matching upper bound sequences from 10th percentile that eventually found match = 109,241 / 499,887 = 21.9%;
Percentage of matching upper bound sequences from above 10th percentile = 41,190,871 / 44,999,999 = 91.5%.

16 January, 2020 at 12:57 am

Pedro Bizarro

I think I found a method to look for values that of a cycle other than 4.2.1
What I did was analyze the “inverse function”. From here I saw that the values obtained can be seen as a “chain” that has certain properties.
Then I considered what numbers could form a cycle
By analyzing it in this way, I could remove as numbers that form a cycle to the numbers multiple of 3; Then, considering that there is some other cycle than 4,2,1, I began to analyze which numbers could be those of greater value and of less value.
I could find that the smallest number within the cycle of this chain must be of the form 12n-1 or 12n-5; By doing more operations, I was able to reduce the numbers to those of the form 24n-1,24n-17,48n-5 or 48n-37. You can reduce the numbers further, but it is a bit difficult to do it manually.
When searching for the largest number, I found that the largest number should be of the form 18n-1 or 18n-7. I could reduce it to the 36n-7 or 36n-19 form. I continued to operate it and could reduce it to the 108n-91,108n-79,108n-55 or 108n-7 form.

19 January, 2020 at 12:02 am

Pedro Bizarro

I have analyzed my method again and discovered that the only cycle that exists is 4.2.1
First I considered that there is a different cycle than 4.2.1, this cycle must have a maximum and minimum odd number
When analyzing the maximum odd number, I discovered that it must have the form 36n-19 or 36n-7
Using the collatz function, I discovered that one of the following numbers within the cycle should have the form 27n-14 or 27n-5
When using the “inverse function”, I discovered that the previous odd number within the cycle must have the form 24n-13 or 24n-5
Since these numbers are within the cycle, the numbers of the form 27n-14 or 27n-5 must reach the numbers of the form 24n-13 or 24n-5 using only the collatz function (multiply 3, add 1 and divide by one power of 2 indefinitely) which is clearly impossible
I did all this analysis graphically, but here in the comments I can’t put the graphics

19 January, 2020 at 12:03 pm

Anonymous

Such analysis should be written in a rigorous (non-graphical) form.

21 January, 2020 at 6:04 am

gabekhan7

I apologize if these are obvious or obviously wrong questions, but I was wondering if there is a quantitative version of the “almost global in time” estimates. In other words, given a slow growing function f and a “generic” number N (so that $Col_{min} N < f(N)$ ), can you give any sense of how large k needs to be so that $Col^k(N) < f(N)$ . In other words, is there some sense of how many iterations of the Collatz map you need "on average" to get below some threshold. I guess this would depend on the particular choice of f, and would seem to get larger the slower that f grows.

As a follow up question, can your result can be combined with the Krasikov-Lagarias result to get better estimates on how many numbers reach 1? This is terribly naive, and so must be wrong, but if there is a set S of density $x^{.84}$ whose Collatz iterations can be shown to reach one, and the "generic" Collatz map reaches values much smaller than N, it seems like it might be possible to get some lower bounds on how many orbits hit S (and thus also go to one). Is there a reason that S and orbits of the Collatz map do not collide in a naive way?

21 January, 2020 at 11:01 am

Terence Tao

The arguments in my paper allow one to take $k = O(\log N)$ . With more effort it may be possible to obtain the more precise value $k = \frac{2+o(1)}{\log(4/3)} \log N$ (or $k = \frac{1+o(1)}{\log(4/3)} \log N$ if one uses Syracuse iterations instead of Collatz (this limiting value of $k$ roughly corresponds to the infinite time limit $t \to \infty$ for autonomous PDE).

The arguments in my paper are unable to “see” anything going on in subsets of $[1,x]$ that are sparser than about $x \log^{-c} x$ in cardinality, so in particular would not be able to interact with the Krasikov-Lagarias set with the current level of bounds. Perhaps in the future one could potentially imagine the error terms in the almost all results and the lower bounds on the preimage results improving to the extent that they can start working with each other, although this possibility looks somewhat remote. However, there is a link between KL type bounds and uniform distribution of the Syracuse random variables in my paper, in that a (currently unproven) equidistribution hypothesis on the former can lead to improvements on the latter (in particular, to replace the 0.84 exponent by any exponent less than 1); I may detail this in a separate blog post.

31 January, 2020 at 5:29 pm

Michael M. Ross

I haven’t found a clear definition of a Syracuse function. I immediately think of any case where n>1 for 3x+n. Does this qualify? These Collatz-type functions produce obvious counterexamples to 3x+1 on the question of cyclicality. For example, taking 3x+17 for 27 there is a 21-step loop beginning with 41 in the odd-only sequence (using my own odd-only function) and a 49-step loop beginning with 140 using the conventional even-odd function. (They are equivalent.)

I notice that complex cycles occur only where it’s possible for the common differences of odd input-output numbers to be zero. That requires what I’ll call a zero-point equilibrium. What is that? It’s simply the n in 3x+n. It means that for 3x+17 the zero point is 17 – and for 3x+1 it’s 1, of course. For 3x+17, common differences have inverse pairs: +14, −14 and −20, +20. For the 3x+17 loop for 27, the addition of common differences yields 0 (+368-368). Such inverse-pair symmetry can never exist for 3x+1.

3 February, 2020 at 11:18 pm

IngoA

It is a little bit offtopic, but there is a random version of the Collatz problem where convergence to the limit set {1, 2, 4} is rather obvious and easy to prove:
(i) Like “in Collatz”, an odd number n is transformed to 3n+1.
(ii) For an even number n a random decision is made: with probability 1/2, n is divided by 2 (like in Collatz), but with the other 1/2, n is divided by 2 and 1 is subtracted from the outcome. Subsequent random decisions are made independently of each other.
The modification in (ii) makes sure that for each even n, the result is even again with probability 1/2.
4 leads either to 2 or to 1, both with probability 1/2.
The expected number of iterations until 1 is reached for the first time is c*log(n_0), where “magic” 4/3 occurs in c somehow.

25 January, 2020 at 3:58 pm

Equidistribution of Syracuse random variables and density of Collatz preimages | What's new

[…] natural numbers obeys the Collatz conjecture. This is not yet established, although the results in my previous paper do at least imply that a positive density set of natural numbers iterates to an (explicitly […]

3 February, 2020 at 12:03 pm

Los primos de la conjetura de Collatz - La Ciencia de la Mula Francis

[…] Tao, “The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3,” What’s New, 25 Aug 2011; Terence Tao, “Almost all Collatz orbits attain almost bounded values,” What’s […]

22 February, 2020 at 10:16 pm

Brian

Thank you for answering question about the Nash embedding theorem. I saw this in an article:
In the 1970s, mathematicians showed that almost all Collatz sequences — the list of numbers you get as you repeat the process — eventually reach a number that’s smaller than where you started. [End quote]

I am unaware of the precise statement of this theorem. So it sounds like it is saying the limit of f^m, where I mean the mth iterate of the Collatz function, when applied to x is going to be smaller than x.

Lets say limit as m approaches infinity of f^m(x) is y and note y<x.

There has got to be something to the fact that we can apply the theorem to y and get a limit of y2<y.

With finitely many applications of this theorem, we get down to 1 eventually.

Is there any idea there that might be useful.

24 February, 2020 at 10:20 am

Terence Tao

The sequence $f^m(x)$ does not have a limit as $m \to \infty$ (conjecturally, it will oscillate indefinitely between the values 1,4,2 after some point). The result of Terras referred to here is discussed for instance at http://www.ericr.nl/wondrous/terras.html . It asserts that for almost all $x$ , there exists an $m$ such that $f^m(x) < x$ . As I discuss in my paper, it is tempting to iterate such results by applying them to $f^m(x)$ in place of $x$ , but the difficulty is that the iterate $f^m(x)$ may lie in the small exceptional set not covered by the "almost all" result of Terras. It is possible to get around this difficulty to a large extent if one has something resembling an invariant measure for the dynamics, and this is the starting point for the arguments in my own paper.

24 February, 2020 at 9:31 pm

y.y.

Such the small exceptional set can be identified. Consider the intersection of the set and its image, then partition the set of the intersection into six subsets. We can see that those subsets get to be null in f^(1+1) *1, 2, 3, 4, 5, n_0+2 times iteration, respectively. That means that the exceptional set can be moved to the “almost all” result. There is inverse function by means of the Residue-class-wise affine mapping which S_3 acts on. So that it is possible to identify the expectional set.

……with no proof. I’m not mathematician, sorry.

25 February, 2020 at 1:27 pm

Alberto Ibañez

I don’t quite understand “the dynamics” in the Collatz conjecture. If the numbers are abstract entities and the set of natural numbers is a perfectly ordered set, arranged according to a certain function that places each number equidistant to the next, in a straight line one behind the other, and once ordered we label them, calling the first 1 , to the second 2, … this perfect order is “absolute”, or is it an “ad hoc” order? If we tell this set to be ordered according to another function, that of Collatz, where an arborescence is created, even if it has periodic orbits, even with divergent orbits, it is also not a perfectly ordered set, according to the function? and they are not both static orders? what mathematical sense does it have to compare two equal sets, perfectly ordered, although differently?
if we talk about the economy or the weather, they are changing, a dollar today is worth something else tomorrow, or if you release a balloon every time it moves differently, influenced by other factors, but the orbits of Collatz are fixed, they never change

25 February, 2020 at 2:21 pm

Michael M. Ross

Little tin soldiers stepping in uniform.
https://drive.google.com/file/d/1C0yxIPNCI4fYIfSXOlCAc_9jitRDrBI9/view?usp=sharing

25 February, 2020 at 2:34 pm

Anonymous

Perhaps it may help to read this Wikipedia article
https://en.wikipedia.org/wiki/Order_theory

23 February, 2020 at 5:12 am

Barry Hirschfeld

PART 1. Lists

Following is the set of lists where the elements of all lists have the form
(positive odd integer, 1 to infinity)*(2^n, n integer, goes from 0 to infinity):
1, 2, 4, 8,…
3, 6, 12, 24,…
5, 10, 20, 40,…
7, 14, 28, 56,…
9, 18, 36, 72,…
and so on.
Each new term in a list is twice the value of the previous term.

The lists cover all positive integers because all integers can be represented as
(positive odd integer, 1 to infinity)*(2^n, n integer, goes from 0 to infinity).

NOTE: No integer in one list is found in any other list because integers in all
other lists have a different odd factor (3, 5, 7,…), and because integers in the
list with 1 as its first element can be represented without any odd factor.

PART 2. Get unique even integer from unique odd integer, and vice-versa

PART 2.0. CS and RCS

We denote a Collatz sequence by CS and a reverse Collatz sequence by RCS

PART 2.1. Get even integer from odd integer for a CS

Multiply odd integer, 2d-1, by 3 and add 1 to give even integer, 3(2d-1)+1.
2d-1 and 3(2d-1)+1 have a 1-to-1 relationship: given one of these terms, the
other term can be found. E.g., if 2d-1 is 5 then 3(2d-1)+1 is 16 & vice-versa.
This even integer is not divisible by 3, and dividing by 2^n does not help.

PART 2.2. Get odd integer from even integer for a CS

Divide the even integer by 2 until you get an odd integer as the quotient.
The dividend and the quotient have a 1-to-1 relationship.

PART 2.3. Get even integer from odd integer for a RCS

Multiply the odd integer by 2 as many times as is necessary.
The multiplicand and the product have a 1-to-1 relationship.

PART 2.4. Get odd integer from even integer for a RCS

We let the odd integer be 2d-1, the even integer be 2v, and the odd integer at
the start of the even integer’s list be 2c-1.

There are three possible cases:
(2c-1) mod 3 = 0. Here the odd integer at the start of the even integer’s list is
divisible by 3, as is the even integer, so that no new odd integer is possible.
(2c-1) mod 3 = 1. Here (2c-1)(4^p)-1 is divisible by 3, p is positive integer.
(2c-1) mod 3 = 2. Here (2c-1)2(4^(p-1))-1 divisible by 3, p positive integer.
For example:
Case 1: If 2c-1 = 9 then no “(even integer in this list)-1” is divisible by 3.
Case 2: If 2c-1 = 7 then (7*4^p-1)/3 = 9, 37, 149,… for p = 1, 2, 3,…
Case 3: If 2c-1 = 5 then (5*2*4^(p-1)-1)/3 = 3, 13, 53,… for p = 1, 2, 3,…

2v and 2d-1 have a 1-to-1 relationship: given one of these terms, the other
term can be found. For example, if 2v is 16 then 2d-1 is 5.

NOTE: We shall ignore the 1 (in 1, 5, 21, etc.) that is gotten from the 4 in
list 1, 2, 4, 8, 16, etc. for three reasons.
First, keeping the 1 leads to a duplication of the original list 1, 2, 4, 8, 16,…
Second, the 4, 2, 1 of the original list results in a loop: 4=>2, 2=>1, 1=>4.
Third, the 1 so obtained is not unique; it already exists in 1, 2, 4, 8, 16 etc.

PART 2.5. Ratios of integers in a list, odd to odd and even to even

For (2c-1) mod 3 = 1 (see PART 2.4), the ratio of two consecutive even
integers used to get two odd integers is 4; for example, 28 and 112.
The same ratio holds for (2c-1) mod 3 = 2; for example, 10 and 40.

Because the ratio of two even integers (used to get odd integers) is 4, thus
3(2d-1)+1 is followed by4(3(2d-1)+1), or by 12(2d-1)+4.
We subtract 1 and divide by 3, getting 4(2d-1)+1 for the next odd integer.

This new odd integer has increased in size from (2d-1) to 4(2d-1)+1, or
4 times the previous odd integer, plus 1. For example, if 2d-1 is 5, then
4(2d-1)+1 is 21; and if 2d-1 is 13, then 4(2d-1)+1 is 53.

PART 3. A RCS that does not start from 1

We can start a RCS from an odd number other than 1, even from an odd
integer whose connection to (the list that starts with) 1 is not known.

The rules for getting the new odd and even integers are set out in PART 2,
and are not dependent on where the RCS starts (and in particular these new
integers are all unique).

Even if afterward we complete the RCS to include 1 and the full set of lists,
the new odd and even integers encountered do not change their values.

PART 4. Loop-free

We start a CS with an odd integer and we count as a step only when another
odd integer is reached.

We start a RCS with the odd integer 1, and we count as a step only when
another odd integer is reached.

In stepping through a RCS (and through its lists), every integer encountered,
whether odd or even, must be unique: see NOTE in PART 1.

Even were we to start a RCS at odd integer 2d-1, and not at 1, the new odd
and even integers encountered as we step through the RCS from 2d-1 would
be the same as if we had started at 1 (see PART 3).

So if when stepping through any RCS means that every integer encountered
must be unique, then this means that a RCS may not have a loop.

Let us assume a CS with a loop. It starts with odd integer 2d’-1, where the
prime indicates the first occurrence of 2d-1. We go s steps until we reach the
integer 2d”-1 a second time, where the double prime indicates the second
occurrence of 2d-1. That is, we have a loop: 2d’-1 and 2d”-1.

Now, go in the opposite direction, that is, in a RCS, starting from 2d”-1 (that
is, from the 2d”-1 that we had reached after going s steps in the CS). So we
go s steps in a RCS and expect to reach the original 2d’-1.

Except we cannot reach the original 2d’-1 in a RCS, because every integer,
odd or even, encountered in a RCS is unique no matter where we started; i.e.
no RCS may have a loop (see above), it cannot contain both 2d’-1 and 2d”-1.

Conclusion: our original assumption about re-encountering 2d-1 after s steps
in a CS must be false, so that a CS may not have a loop.

PART 5. Infinity, possible or not possible?

We use a concrete – but technically incorrect – example for illustration.
We assume that, say 29, is the integer for a Collatz sequence that goes to
infinity; 29 actually converges to 1, not infinity, but we shall ignore this.

To get to the next step in the sequence we do 3(29)+1 to get 88, and then
divide by 2 until an odd integer is reached; viz., 11, the next step.

We can multiply 29 by 4 and add 1 (see PART 2.5) to get 117. We do
3(117)+1 to get 352, and divide by 2 until the same odd integer as for29 is
reached; viz., 11. We thus see that 117 also goes to infinity.

We can multiply 117 by 4 and add 1 to get 469, etc. And we can multiply
469 by 4 and add 1, etc. In other words, not just 29 goes to infinity, there are
an infinite number of integers going to infinity (117, 469, 1877, etc.).
That is, there is not just one bad actor (29), there is an infinity of them.

(Sometimes it is possible to subtract 1 from 29 and divide by 4 to get an odd
integer (see PART 2.5), here 7, then multiply 7 by 3 and add 1 to get 22, and
then divide 22 by 2 until an odd integer is reached, here 11, so that 7 also
goes to infinity. Then we do the same procedure for 7 as we did for 29, until
we reach an integer that is not an odd integer. But this procedure can be
done only a finite number of times, so its effect is unimportant.)

We saw that the step after 29 is 11. Multiply 11 by 3 and add 1 to get 4, and
divide 34 by 2 until we reach an odd integer, 17, which is the next step.

As with 29, we can multiply 11 by 4 and add 1 to get 45, multiply 45 by 3
and add 1 to get 136, and divide by 2 until we get an odd integer, also 17.
So we see that 45, like 11, also goes to infinity.

Here too there are an infinite number of integers going to infinity
(11, 45, 181, etc.). And we can do to 17 what we did to 29 and 11. Etc.

Of course, all this is nearly identical to what we could do with integers in a
Collatz sequence that converge to 1.
Except that when an integer converges to 1, everything stops when it reaches
1, but an integer that goes to infinity takes an infinite number of steps to go
there and includes with itself infinities of other integers each step on the way

Could it be that, for all integers, the ones that converge to 1 have a measure
of 0 compared to the measure of 1 for integers that go to infinity?
So what?
For example, we know that on the 0 to 1 x-axis the Reals have a measure of
0 while the Irrationals+Transcendentals have a measure of 1, yet the Reals
are nonetheless doing quite well even with a measure of 0.
Here too, even were Integers (converges to 1) found to have a measure of 0,
compared to a measure of 1 for Integers (goes to infinity), we shouldn’t care.

Or, maybe not. Maybe it’s when comparing Reals to Irrationals+
Transcendentals that we don’t care if the Reals have a measure of 0, but
when comparing Reals to Reals (as in our case) we do care, so that a Collatz
sequence that goes to infinity (instead of to 1) should not be possible.

So, should a Collatz sequence that goes to infinity be possible, or not?

Gentlemen and Ladies of the blue-ribbon jury, I rest my case.

24 February, 2020 at 3:04 am

Barry Hirschfeld

Yes, what I wrote above is unclear and deserves thumbs down.

BUT, I request looking at PART 4 (toward its start), beginning with:
“So if when stepping through any RCS means that every integer encountered
must be unique, then this means that a RCS may not have a loop.”

And read from there to the end of PART 4, which finishes with::
“a CS may not have a loop” (Note: “loop” means “circuit”.)
You agree, or don’t agree?

25 February, 2020 at 11:32 am

Barry Hirschfeld

1. Showed that operations in Collatz sequence & reverse CS are single-valued.
2. Showed that every integer in reverse Collatz sequence MUST be unique.
3. Assumed that a Collatz sequence (CS) has a loop/circuit at integer 2s-1, & from second instance of 2s-1 in CS use RCS to try to return to first instance.
4. RCS failed to return to first instance of 2s-1 because 2s-1 not unique.
5. Conclusion: Assumption of loop/circuit (second instance of 2s-1)
in CS was wrong, a Collatz sequence may NOT have a loop/circuit.
Agree/disagree?

25 February, 2020 at 12:06 pm

Alberto Ibañez

Hello Barry, do not despair. Surely your comment has been seen by many blog friends, even by Professor Tao. And it may not be all the good you think it is, although my opinion is of little mathematical value.
About loops, it seems that your argument states that $ latex a \ neq b $, $ latex b \ neq c $, … but does not imply that $ latex z \ neq a $, in my very modest opinion. Regards

25 February, 2020 at 6:02 pm

Barry Hirschfeld

Thank you for your reply.
You may be on to something, but I am not familiar with Latex.
Could you please rewrite your comment using FORTRAN (EQ, NE, LT, LE, MT, ME) instead of Latex..

26 February, 2020 at 3:18 am

Barry Hirschfeld

Alberto:
I figured out the Latex, but do not know to what you refer (“your argument”); viz., on which line – 1,2,3,4,5 – in my short “proof” are you commenting?
(I totally agree with your comment, but do not think I use it anywhere.)

(BTW, I meant GT and GE, not MT and ME.)

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

	Aditya Guha Roy on Additive combinatorics
	Hollis Williams on The effective potential of an…
	Hollis Williams on The effective potential of an…
	Hollis Williams on The effective potential of an…
	Anonymous on 254A, Notes 3: The operator no…
	Anonymous on Analysis I
	Aziz Lokhandwala on Einstein’s derivation of…
	Terence Tao on Analysis I
	michaelmross on WordPress LaTeX bug collection…
	Yaj Yaj on WordPress LaTeX bug collection…
	Anonymous on Analysis I
	Anonymous on Course announcement: 246B, com…
	Anonymous on 254A, Notes 0: A review of pro…
	Anonymous on 246A, Notes 5: conformal …
	song d on Analysis I

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

406 comments

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

406 comments