Almost all Collatz orbits attain almost bounded values

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

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

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

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

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

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

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

Thus for instance one has ${\mathrm{Col}_{\min}(N) < \log\log\log\log N}$ for almost all ${N}$ (in the sense of logarithmic density).

The difficulty here is one usually only expects to establish “local-in-time” results that control the evolution ${\mathrm{Col}^n(N)}$ for times ${n}$ that only get as large as a small multiple ${c \log N}$ of ${\log N}$ ; the aforementioned results of Terras, Allouche, and Korec, for instance, are of this time. However, to get ${\mathrm{Col}^n(N)}$ all the way down to ${f(N)}$ one needs something more like an “(almost) global-in-time” result, where the evolution remains under control for so long that the orbit has nearly reached the bounded state ${N=O(1)}$ .

However, as observed by Bourgain in the context of nonlinear Schrödinger equations, one can iterate “almost sure local wellposedness” type results (which give local control for almost all initial data from a given distribution) into “almost sure (almost) global wellposedness” type results if one is fortunate enough to draw one’s data from an invariant measure for the dynamics. To illustrate the idea, let us take Korec’s aforementioned result that if ${\theta > \frac{\log 3}{\log 4}}$ one picks at random an integer ${N}$ from a large interval ${[1,x]}$ , then in most cases, the orbit of ${N}$ will eventually move into the interval ${[1,x^{\theta}]}$ . Similarly, if one picks an integer ${M}$ at random from ${[1,x^\theta]}$ , then in most cases, the orbit of ${M}$ will eventually move into ${[1,x^{\theta^2}]}$ . It is then tempting to concatenate the two statements and conclude that for most ${N}$ in ${[1,x]}$ , the orbit will eventually move ${[1,x^{\theta^2}]}$ . Unfortunately, this argument does not quite work, because by the time the orbit from a randomly drawn ${N \in [1,x]}$ reaches ${[1,x^\theta]}$ , the distribution of the final value is unlikely to be close to being uniformly distributed on ${[1,x^\theta]}$ , and in particular could potentially concentrate almost entirely in the exceptional set of ${M \in [1,x^\theta]}$ that do not make it into ${[1,x^{\theta^2}]}$ . The point here is the uniform measure on ${[1,x]}$ is not transported by Collatz dynamics to anything resembling the uniform measure on ${[1,x^\theta]}$ .

So, one now needs to locate a measure which has better invariance properties under the Collatz dynamics. It turns out to be technically convenient to work with a standard acceleration of the Collatz map known as the Syracuse map ${\mathrm{Syr}: 2{\bf N}+1 \rightarrow 2{\bf N}+1}$ , defined on the odd numbers ${2{\bf N}+1 = \{1,3,5,\dots\}}$ by setting ${\mathrm{Syr}(N) = (3N+1)/2^a}$ , where ${2^a}$ is the largest power of ${2}$ that divides ${3N+1}$ . (The advantage of using the Syracuse map over the Collatz map is that it performs precisely one multiplication of ${3}$ at each iteration step, which makes the map better behaved when performing “ ${3}$ -adic” analysis.)

When viewed ${3}$ -adically, we soon see that iterations of the Syracuse map become somewhat irregular. Most obviously, ${\mathrm{Syr}(N)}$ is never divisible by ${3}$ . A little less obviously, ${\mathrm{Syr}(N)}$ is twice as likely to equal ${2}$ mod ${3}$ as it is to equal ${1}$ mod ${3}$ . This is because for a randomly chosen odd ${\mathbf{N}}$ , the number of times ${\mathbf{a}}$ that ${2}$ divides ${3\mathbf{N}+1}$ can be seen to have a geometric distribution of mean ${2}$ – it equals any given value ${a \in{\bf N}+1}$ with probability ${2^{-a}}$ . Such a geometric random variable is twice as likely to be odd as to be even, which is what gives the above irregularity. There are similar irregularities modulo higher powers of ${3}$ . For instance, one can compute that for large random odd ${\mathbf{N}}$ , ${\mathrm{Syr}^2(\mathbf{N}) \hbox{ mod } 9}$ will take the residue classes ${0,1,2,3,4,5,6,7,8 \hbox{ mod } 9}$ with probabilities

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

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

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

where ${\mathbf{a}_1,\dots,\mathbf{a}_n}$ are iid copies of a geometric random variable of mean ${2}$ .

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

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

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

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

A first hint of how to proceed comes from the elementary number theory observation (easily proven by induction) that the rational numbers

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

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

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

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

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

for any ${A > 0}$ and any ${\xi \in {\bf Z}/3^n{\bf Z}}$ that is not divisible by ${3}$ .

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

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

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

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

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

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

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

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

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

(which we view as a two-dimensional renewal process) contains at least a few points lying outside of ${B}$ .

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

166 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.

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.

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.

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.

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.

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.

https://pdfs.semanticscholar.org/f3c0/13d8bb641513da2a0cb84936b9ef9fc6ad46.pdf

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.

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!

	Anonymous on Hilbert’s fifth problem…
	Juan Orozco (@JuanOr… on Mertens’ theorems
	Anonymous on 245A, Notes 5: Differentiation…
	Math Vault on There’s more to mathematics th…
	Terence Tao on 245A, Notes 5: Differentiation…
	Anonymous on 245A, Notes 5: Differentiation…
	Jamie on Request for comments from the…
	Kevin Ford on 254A, Notes 2: Complex-analyti…
	Mizar on The spectral theorem and its c…
	Anonymous on Polymath15, eleventh thread: W…
	Anonymous on Polymath15, eleventh thread: W…
	Anonymous on About
	Ali Sada on About
	Anonymous on 245A, Notes 5: Differentiation…
	Terence Tao on Hilbert’s fifth problem…

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

166 comments

Leave a Reply Cancel reply

For commenters

Almost all Collatz orbits attain almost bounded values

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

166 comments

Leave a Reply Cancel reply

For commenters