You are currently browsing the tag archive for the ‘Collatz conjecture’ tag.

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)  0.869}, and extended later by Korec to cover all {\theta > \frac{\log 3}{\log 4} \approx 0.7924}. In this paper we obtain the following further improvement (at the cost of weakening natural density to logarithmic density):

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

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

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

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

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

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

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

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

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

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

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

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

\displaystyle  \ll_A m^{-A}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

One of the most notorious problems in elementary mathematics that remains unsolved is the Collatz conjecture, concerning the function {f_0: {\bf N} \rightarrow {\bf N}} defined by setting {f_0(n) := 3n+1} when {n} is odd, and {f_0(n) := n/2} when {n} is even. (Here, {{\bf N}} is understood to be the positive natural numbers {\{1,2,3,\ldots\}}.)

Conjecture 1 (Collatz conjecture) For any given natural number {n}, the orbit {n, f_0(n), f^2_0(n), f^3_0(n), \ldots} passes through {1} (i.e. {f^k_0(n)=1} for some {k}).

Open questions with this level of notoriety can lead to what Richard Lipton calls “mathematical diseases” (and what I termed an unhealthy amount of obsession on a single famous problem). (See also this xkcd comic regarding the Collatz conjecture.) As such, most practicing mathematicians tend to spend the majority of their time on more productive research areas that are only just beyond the range of current techniques. Nevertheless, it can still be diverting to spend a day or two each year on these sorts of questions, before returning to other matters; so I recently had a go at the problem. Needless to say, I didn’t solve the problem, but I have a better appreciation of why the conjecture is (a) plausible, and (b) unlikely be proven by current technology, and I thought I would share what I had found out here on this blog.

Let me begin with some very well known facts. If {n} is odd, then {f_0(n) = 3n+1} is even, and so {f_0^2(n) = \frac{3n+1}{2}}. Because of this, one could replace {f_0} by the function {f_1: {\bf N} \rightarrow {\bf N}}, defined by {f_1(n) = \frac{3n+1}{2}} when {n} is odd, and {f_1(n)=n/2} when {n} is even, and obtain an equivalent conjecture. Now we see that if one chooses {n} “at random”, in the sense that it is odd with probability {1/2} and even with probability {1/2}, then {f_1} increases {n} by a factor of roughly {3/2} half the time, and decreases it by a factor of {1/2} half the time. Furthermore, if {n} is uniformly distributed modulo {4}, one easily verifies that {f_1(n)} is uniformly distributed modulo {2}, and so {f_1^2(n)} should be roughly {3/2} times as large as {f_1(n)} half the time, and roughly {1/2} times as large as {f_1(n)} the other half of the time. Continuing this at a heuristic level, we expect generically that {f_1^{k+1}(n) \approx \frac{3}{2} f_1^k(n)} half the time, and {f_1^{k+1}(n) \approx \frac{1}{2} f_1^k(n)} the other half of the time. The logarithm {\log f_1^k(n)} of this orbit can then be modeled heuristically by a random walk with steps {\log \frac{3}{2}} and {\log \frac{1}{2}} occuring with equal probability. The expectation

\displaystyle \frac{1}{2} \log \frac{3}{2} + \frac{1}{2} \log \frac{1}{2} = \frac{1}{2} \log \frac{3}{4}

is negative, and so (by the classic gambler’s ruin) we expect the orbit to decrease over the long term. This can be viewed as heuristic justification of the Collatz conjecture, at least in the “average case” scenario in which {n} is chosen uniform at random (e.g. in some large interval {\{1,\ldots,N\}}). (It also suggests that if one modifies the problem, e.g. by replacing {3n+1} to {5n+1}, then one can obtain orbits that tend to increase over time, and indeed numerically for this variant one sees orbits that appear to escape to infinity.) Unfortunately, one can only rigorously keep the orbit uniformly distributed modulo {2} for time about {O(\log N)} or so; after that, the system is too complicated for naive methods to control at anything other than a heuristic level.

Remark 1 One can obtain a rigorous analogue of the above arguments by extending {f_1} from the integers {{\bf Z}} to the {2}-adics {{\bf Z}_2}. This compact abelian group comes with a Haar probability measure, and one can verify that this measure is invariant with respect to {f_1}; with a bit more effort one can verify that it is ergodic. This suggests the introduction of ergodic theory methods. For instance, using the pointwise ergodic theorem, we see that if {n} is a random {2}-adic integer, then almost surely the orbit {n, f_1(n), f_1^2(n), \ldots} will be even half the time and odd half the time asymptotically, thus supporting the above heuristics. Unfortunately, this does not directly tell us much about the dynamics on {{\bf Z}}, as this is a measure zero subset of {{\bf Z}_2}. More generally, unless a dynamical system is somehow “polynomial”, “nilpotent”, or “unipotent” in nature, the current state of ergodic theory is usually only able to say something meaningful about generic orbits, but not about all orbits. For instance, the very simple system {x \rightarrow 10x} on the unit circle {{\bf R}/{\bf Z}} is well understood from ergodic theory (in particular, almost all orbits will be uniformly distributed), but the orbit of a specific point, e.g. {\pi\hbox{ mod } 1}, is still nearly impossible to understand (this particular problem being equivalent to the notorious unsolved question of whether the digits of {\pi} are uniformly distributed).

The above heuristic argument only suggests decreasing orbits for almost all {n} (though even this remains unproven, the state of the art is that the number of {n} in {\{1,\ldots,N\}} that eventually go to {1} is {\gg N^{0.84}}, a result of Krasikov and Lagarias). It leaves open the possibility of some very rare exceptional {n} for which the orbit goes to infinity, or gets trapped in a periodic loop. Since the only loop that {1} lies in is {1,4,2} (for {f_0}) or {1,2} (for {f_1}), we thus may isolate a weaker consequence of the Collatz conjecture:

Conjecture 2 (Weak Collatz conjecture) Suppose that {n} is a natural number such that {f^k_0(n)=n} for some {k \geq 1}. Then {n} is equal to {1}, {2}, or {4}.

Of course, we may replace {f_0} with {f_1} (and delete “{4}“) and obtain an equivalent conjecture.

This weaker version of the Collatz conjecture is also unproven. However, it was observed by Bohm and Sontacchi that this weak conjecture is equivalent to a divisibility problem involving powers of {2} and {3}:

Conjecture 3 (Reformulated weak Collatz conjecture) There does not exist {k \geq 1} and integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

such that {2^{a_{k+1}}-3^k} is a positive integer that is a proper divisor of

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

i.e.

\displaystyle (2^{a_{k+1}} - 3^k) n = 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k} \ \ \ \ \ (1)

 

for some natural number {n > 1}.

Proposition 4 Conjecture 2 and Conjecture 3 are equivalent.

Proof: To see this, it is convenient to reformulate Conjecture 2 slightly. Define an equivalence relation {\sim} on {{\bf N}} by declaring {a \sim b} if {a/b = 2^m} for some integer {m}, thus giving rise to the quotient space {{\bf N}/\sim} of equivalence classes {[n]} (which can be placed, if one wishes, in one-to-one correspondence with the odd natural numbers). We can then define a function {f_2: {\bf N}/\sim \rightarrow {\bf N}/\sim} by declaring

\displaystyle f_2( [n] ) := [3n + 2^a] \ \ \ \ \ (2)

 

for any {n \in {\bf N}}, where {2^a} is the largest power of {2} that divides {n}. It is easy to see that {f_2} is well-defined (it is essentially the Syracuse function, after identifying {{\bf N}/\sim} with the odd natural numbers), and that periodic orbits of {f_2} correspond to periodic orbits of {f_1} or {f_0}. Thus, Conjecture 2 is equivalent to the conjecture that {[1]} is the only periodic orbit of {f_2}.

Now suppose that Conjecture 2 failed, thus there exists {[n] \neq [1]} such that {f_2^k([n])=[n]} for some {k \geq 1}. Without loss of generality we may take {n} to be odd, then {n>1}. It is easy to see that {[1]} is the only fixed point of {f_2}, and so {k>1}. An easy induction using (2) shows that

\displaystyle f_2^k([n]) = [3^k n + 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}]

where, for each {1 \leq i \leq k}, {2^{a_i}} is the largest power of {2} that divides

\displaystyle n_i := 3^{i-1} n + 3^{i-2} 2^{a_1} + \ldots + 2^{a_{i-1}}. \ \ \ \ \ (3)

 

In particular, as {n_1 = n} is odd, {a_1=0}. Using the recursion

\displaystyle n_{i+1} = 3n_i + 2^{a_i}, \ \ \ \ \ (4)

 

we see from induction that {2^{a_i+1}} divides {n_{i+1}}, and thus {a_{i+1}>a_i}:

\displaystyle 0 = a_1 < a_2 < \ldots < a_k.

Since {f_2^k([n]) = [n]}, we have

\displaystyle 2^{a_{k+1}} n = 3^k n + 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k} = 3 n_k + 2^{a_k}

for some integer {a_{k+1}}. Since {3 n_k + 2^{a_k}} is divisible by {2^{a_k+1}}, and {n} is odd, we conclude {a_{k+1} > a_k}; if we rearrange the above equation as (1), then we obtain a counterexample to Conjecture 3.

Conversely, suppose that Conjecture 3 failed. Then we have {k \geq 1}, integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

and a natural number {n > 1} such that (1) holds. As {a_1=0}, we see that the right-hand side of (1) is odd, so {n} is odd also. If we then introduce the natural numbers {n_i} by the formula (3), then an easy induction using (4) shows that

\displaystyle (2^{a_{k+1}} - 3^k) n_i = 3^{k-1} 2^{a_i} + 3^{k-2} 2^{a_{i+1}} + \ldots + 2^{a_{i+k-1}} \ \ \ \ \ (5)

 

with the periodic convention {a_{k+j} := a_j + a_{k+1}} for {j>1}. As the {a_i} are increasing in {i} (even for {i \geq k+1}), we see that {2^{a_i}} is the largest power of {2} that divides the right-hand side of (5); as {2^{a_{k+1}}-3^k} is odd, we conclude that {2^{a_i}} is also the largest power of {2} that divides {n_i}. We conclude that

\displaystyle f_2([n_i]) = [3n_i + 2^{a_i}] = [n_{i+1}]

and thus {[n]} is a periodic orbit of {f_2}. Since {n} is an odd number larger than {1}, this contradicts Conjecture 3. \Box

Call a counterexample a tuple {(k,a_1,\ldots,a_{k+1})} that contradicts Conjecture 3, i.e. an integer {k \geq 1} and an increasing set of integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

such that (1) holds for some {n \geq 1}. We record a simple bound on such counterexamples, due to Terras and to Garner :

Lemma 5 (Exponent bounds) Let {N \geq 1}, and suppose that the Collatz conjecture is true for all {n < N}. Let {(k,a_1,\ldots,a_{k+1})} be a counterexample. Then

\displaystyle \frac{\log 3}{\log 2} k < a_{k+1} < \frac{\log(3+\frac{1}{N})}{\log 2} k.

Proof: The first bound is immediate from the positivity of {2^{a_{k+1}}-3^k}. To prove the second bound, observe from the proof of Proposition 4 that the counterexample {(k,a_1,\ldots,a_{k+1})} will generate a counterexample to Conjecture 2, i.e. a non-trivial periodic orbit {n, f(n), \ldots, f^K(n) = n}. As the conjecture is true for all {n < N}, all terms in this orbit must be at least {N}. An inspection of the proof of Proposition 4 reveals that this orbit consists of {k} steps of the form {x \mapsto 3x+1}, and {a_{k+1}} steps of the form {x \mapsto x/2}. As all terms are at least {N}, the former steps can increase magnitude by a multiplicative factor of at most {3+\frac{1}{N}}. As the orbit returns to where it started, we conclude that

\displaystyle 1 \leq (3+\frac{1}{N})^k (\frac{1}{2})^{a_{k+1}}

whence the claim. \Box

The Collatz conjecture has already been verified for many values of {n} (up to at least {N = 5 \times 10^{18}}, according to this web site). Inserting this into the above lemma, one can get lower bounds on {k}. For instance, by methods such as this, it is known that any non-trivial periodic orbit has length at least {105{,}000}, as shown in Garner’s paper (and this bound, which uses the much smaller value {N = 2 \times 10^9} that was available in 1981, can surely be improved using the most recent computational bounds).

Now we can perform a heuristic count on the number of counterexamples. If we fix {k} and {a := a_{k+1}}, then {2^a > 3^k}, and from basic combinatorics we see that there are {\binom{a-1}{k-1}} different ways to choose the remaining integers

\displaystyle 0 = a_1 < a_2 < \ldots < a_{k+1}

to form a potential counterexample {(k,a_1,\ldots,a_{k+1})}. As a crude heuristic, one expects that for a “random” such choice of integers, the expression (1) has a probability {1/q} of holding for some integer {n}. (Note that {q} is not divisible by {2} or {3}, and so one does not expect the special structure of the right-hand side of (1) with respect to those moduli to be relevant. There will be some choices of {a_1,\ldots,a_k} where the right-hand side in (1) is too small to be divisible by {q}, but using the estimates in Lemma 5, one expects this to occur very infrequently.) Thus, the total expected number of solutions for this choice of {a, k} is

\displaystyle \frac{1}{q} \binom{a-1}{k-1}.

The heuristic number of solutions overall is then expected to be

\displaystyle \sum_{a,k} \frac{1}{q} \binom{a-1}{k-1}, \ \ \ \ \ (6)

 

where, in view of Lemma 5, one should restrict the double summation to the heuristic regime {a \approx \frac{\log 3}{\log 2} k}, with the approximation here accurate to many decimal places.

We need a lower bound on {q}. Here, we will use Baker’s theorem (as discussed in this previous post), which among other things gives the lower bound

\displaystyle q = 2^a - 3^k \gg 2^a / a^C \ \ \ \ \ (7)

 

for some absolute constant {C}. Meanwhile, Stirling’s formula (as discussed in this previous post) combined with the approximation {k \approx \frac{\log 2}{\log 3} a} gives

\displaystyle \binom{a-1}{k-1} \approx \exp(h(\frac{\log 2}{\log 3}))^a

where {h} is the entropy function

\displaystyle h(x) := - x \log x - (1-x) \log (1-x).

A brief computation shows that

\displaystyle \exp(h(\frac{\log 2}{\log 3})) \approx 1.9318 \ldots

and so (ignoring all subexponential terms)

\displaystyle \frac{1}{q} \binom{a-1}{k-1} \approx (0.9659\ldots)^a

which makes the series (6) convergent. (Actually, one does not need the full strength of Lemma 5 here; anything that kept {k} well away from {a/2} would suffice. In particular, one does not need an enormous value of {N}; even {N=5} (say) would be more than sufficient to obtain the heuristic that there are finitely many counterexamples.) 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).

This, of course, is far short of any rigorous proof of Conjecture 2. In order to make rigorous progress on this conjecture, it seems that one would need to somehow exploit the structural properties of numbers of the form

\displaystyle 3^{k-1} 2^{a_1} + 3^{k-2} 2^{a_2} + \ldots + 2^{a_k}. \ \ \ \ \ (8)

 

In some very special cases, this can be done. For instance, suppose that one had {a_{i+1}=a_i+1} with at most one exception (this is essentially what is called a {1}-cycle by Steiner). Then (8) simplifies via the geometric series formula to a combination of just a bounded number of powers of {2} and {3}, rather than an unbounded number. In that case, one can start using tools from transcendence theory such as Baker’s theorem to obtain good results; for instance, in the above-referenced paper of Steiner, it was shown that {1}-cycles cannot actually occur, and similar methods have been used to show that {m}-cycles (in which there are at most {m} exceptions to {a_{i+1}=a_i+1}) do not occur for any {m \leq 63}, as was shown by Simons and de Weger. However, for general increasing tuples of integers {a_1,\ldots,a_k}, there is no such representation by bounded numbers of powers, and it does not seem that methods from transcendence theory will be sufficient to control the expressions (8) to the extent that one can understand their divisibility properties by quantities such as {2^a-3^k}.

Amusingly, there is a slight connection to Littlewood-Offord theory in additive combinatorics – the study of the {2^n} random sums

\displaystyle \pm v_1 \pm v_2 \pm \ldots \pm v_n

generated by some elements {v_1,\ldots,v_n} of an additive group {G}, or equivalently, the vertices of an {n}-dimensional parallelepiped inside {G}. Here, the relevant group is {{\bf Z}/q{\bf Z}}. The point is that if one fixes {k} and {a_{k+1}} (and hence {q}), and lets {a_1,\ldots,a_k} vary inside the simplex

\displaystyle \Delta := \{ (a_1,\ldots,a_k) \in {\bf N}^k: 0 = a_1 < \ldots < a_k < a_{k+1}\}

then the set {S} of all sums of the form (8) (viewed as an element of {{\bf Z}/q{\bf Z}}) contains many large parallelepipeds. (Note, incidentally, that once one fixes {k}, all the sums of the form (8) are distinct; because given (8) and {k}, one can read off {2^{a_1}} as the largest power of {2} that divides (8), and then subtracting off {3^{k-1} 2^{a_1}} one can then read off {2^{a_2}}, and so forth.) This is because the simplex {\Delta} contains many large cubes. Indeed, if one picks a typical element {(a_1,\ldots,a_k)} of {\Delta}, then one expects (thanks to Lemma 5) that there there will be {\gg k} indices {1 \leq i_1 < \ldots < i_m \leq k} such that {a_{i_j+1} > a_{i_j}+1} for {j=1,\ldots,m}, which allows one to adjust each of the {a_{i_j}} independently by {1} if desired and still remain inside {\Delta}. This gives a cube in {\Delta} of dimension {\gg k}, which then induces a parallelepiped of the same dimension in {S}. A short computation shows that the generators of this parallelepiped consist of products of a power of {2} and a power of {3}, and in particular will be coprime to {q}.

If the weak Collatz conjecture is true, then the set {S} must avoid the residue class {0} in {{\bf Z}/q{\bf Z}}. Let us suppose temporarily that we did not know about Baker’s theorem (and the associated bound (7)), so that {q} could potentially be quite small. Then we would have a large parallelepiped inside a small cyclic group {{\bf Z}/q{\bf Z}} that did not cover all of {{\bf Z}/q{\bf Z}}, which would not be possible for {q} small enough. Indeed, an easy induction shows that a {d}-dimensional parallelepiped in {{\bf Z}/q{\bf Z}}, with all generators coprime to {q}, has cardinality at least {\min(q, d+1)}. This argument already shows the lower bound {q \gg k}. In other words, we have

Proposition 6 Suppose the weak Collatz conjecture is true. Then for any natural numbers {a, k} with {2^a > 3^k}, one has {2^a-3^k \gg k}.

This bound is very weak when compared against the unconditional bound (7). However, I know of no way to get a nontrivial separation property between powers of {2} and powers of {3} other than via transcendence theory methods. Thus, this result strongly suggests that any proof of the Collatz conjecture must either use existing results in transcendence theory, or else must contribute a new method to give non-trivial results in transcendence theory. (This already rules out a lot of possible approaches to solve the Collatz conjecture.)

By using more sophisticated tools in additive combinatorics, one can improve the above proposition (though it is still well short of the transcendence theory bound (7)):

Proposition 7 Suppose the weak Collatz conjecture is true. Then for any natural numbers {a, k} with {2^a > 3^k}, one has {2^a-3^k \gg (1+\epsilon)^k} for some absolute constant {\epsilon > 0}.

Proof: (Informal sketch only) Suppose not, then we can find {a, k} with {q := 2^a-3^k} of size {(1+o(1))^k = \exp(o(k))}. We form the set {S} as before, which contains parallelepipeds in {{\bf Z}/q{\bf Z}} of large dimension {d \gg k} that avoid {0}. We can count the number of times {0} occurs in one of these parallelepipeds by a standard Fourier-analytic computation involving Riesz products (see Chapter 7 of my book with Van Vu, or this recent preprint of Maples). Using this Fourier representation, the fact that this parallelepiped avoids {0} (and the fact that {q = \exp(o(k)) = \exp(o(d))}) forces the generators {v_1,\ldots,v_d} to be concentrated in a Bohr set, in that one can find a non-zero frequency {\xi \in {\bf Z}/q{\bf Z}} such that {(1-o(1))d} of the {d} generators lie in the set {\{ v: \xi v = o(q) \hbox{ mod } q \}}. However, one can choose the generators to essentially have the structure of a (generalised) geometric progression (up to scaling, it resembles something like {2^i 3^{\lfloor \alpha i \rfloor}} for {i} ranging over a generalised arithmetic progression, and {\alpha} a fixed irrational), and one can show that such progressions cannot be concentrated in Bohr sets (this is similar in spirit to the exponential sum estimates of Bourgain on approximate multiplicative subgroups of {{\bf Z}/q{\bf Z}}, though one can use more elementary methods here due to the very strong nature of the Bohr set concentration (being of the “{99\%} concentration” variety rather than the “{1\%} concentration”).). This furnishes the required contradiction. \Box

Thus we see that any proposed proof of the Collatz conjecture must either use transcendence theory, or introduce new techniques that are powerful enough to create exponential separation between powers of {2} and powers of {3}.

Unfortunately, once one uses the transcendence theory bound (7), the size {q} of the cyclic group {{\bf Z}/q{\bf Z}} becomes larger than the volume of any cube in {S}, and Littlewood-Offord techniques are no longer of much use (they can be used to show that {S} is highly equidistributed in {{\bf Z}/q{\bf Z}}, but this does not directly give any way to prevent {S} from containing {0}).

One possible toy model problem for the (weak) Collatz conjecture is a conjecture of Erdos asserting that for {n>8}, the base {3} representation of {2^n} contains at least one {2}. (See this paper of Lagarias for some work on this conjecture and on related problems.) To put it another way, the conjecture asserts that there are no integer solutions to

\displaystyle 2^n = 3^{a_1} + 3^{a_2} + \ldots + 3^{a_k}

with {n > 8} and {0 \leq a_1 < \ldots < a_k}. (When {n=8}, of course, one has {2^8 = 3^0 + 3^1 + 3^2 + 3^5}.) In this form we see a resemblance to Conjecture 3, but it looks like a simpler problem to attack (though one which is still a fair distance beyond what one can do with current technology). Note that one has a similar heuristic support for this conjecture as one does for Proposition 3; a number of magnitude {2^n} has about {n \frac{\log 2}{\log 3}} base {3} digits, so the heuristic probability that none of these digits are equal to {2} is {3^{-n\frac{\log 2}{\log 3}} = 2^{-n}}, which is absolutely summable.

Archives