One of the most notorious problems in elementary mathematics that remains unsolved is the Collatz conjecture, concerning the function

Conjecture 1 (Collatz conjecture) For any given natural number

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

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

Remark 1 One can obtain a rigorous analogue of the above arguments by extending Haar probability measure, and one can verify that this measure is invariant with respect to pointwise ergodic theorem, we see that if integer, then almost surely the orbit generic orbits, but not about all orbits. For instance, the very simple system

The above heuristic argument only suggests decreasing orbits for almost all result of Krasikov and Lagarias). It leaves open the possibility of some very rare exceptional

Conjecture 2 (Weak Collatz conjecture) Suppose that

Of course, we may replace

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

Conjecture 3 (Reformulated weak Collatz conjecture) There does not exist

such that

i.e.

 

for some natural number

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

 

for any Syracuse function, after identifying 2 is equivalent to the conjecture that

Now suppose that Conjecture 2 failed, thus there exists (2) shows that

where, for each

 

In particular, as

 

we see from induction that

Since

for some integer (1), then we obtain a counterexample to Conjecture 3.

Conversely, suppose that Conjecture 3 failed. Then we have

and a natural number (1) holds. As (1) is odd, so (3), then an easy induction using (4) shows that

 

with the periodic convention (5); as

and thus 3.

Call a counterexample a tuple 3, i.e. an integer

such that (1) holds for some to Terras and to Garner :

Lemma 5 (Exponent bounds) Let

Proof: The first bound is immediate from the positivity of 4 that the counterexample 2, i.e. a non-trivial periodic orbit 4 reveals that this orbit consists of

whence the claim.

The Collatz conjecture has already been verified for many values of this web site). Inserting this into the above lemma, one can get lower bounds on

Now we can perform a heuristic count on the number of counterexamples. If we fix

to form a potential counterexample (1) has a probability (1) with respect to those moduli to be relevant. There will be some choices of (1) is too small to be divisible by 5, one expects this to occur very infrequently.) Thus, the total expected number of solutions for this choice of

The heuristic number of solutions overall is then expected to be

 

where, in view of Lemma 5, one should restrict the double summation to the heuristic regime

We need a lower bound on Baker’s theorem (as discussed in this previous post), which among other things gives the lower bound

 

for some absolute constant Stirling’s formula (as discussed in this previous post) combined with the approximation

where entropy function

A brief computation shows that

and so (ignoring all subexponential terms)

which makes the series (6) convergent. (Actually, one does not need the full strength of Lemma 5 here; anything that kept 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

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

 

In some very special cases, this can be done. For instance, suppose that one had by Steiner). Then (8) simplifies via the geometric series formula to a combination of just a bounded number of powers of by Simons and de Weger. However, for general increasing tuples of integers (8) to the extent that one can understand their divisibility properties by quantities such as

Amusingly, there is a slight connection to Littlewood-Offord theory in additive combinatorics – the study of the

generated by some elements

then the set (8) (viewed as an element of (8) are distinct; because given (8) and (8), and then subtracting off 5) that there there will be

If the weak Collatz conjecture is true, then the set (7)), so that

Proposition 6 Suppose the weak Collatz conjecture is true. Then for any natural numbers

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

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

Proof: (Informal sketch only) Suppose not, then we can find my book with Van Vu, or this recent preprint of Maples). Using this Fourier representation, the fact that this parallelepiped avoids Bohr set, in that one can find a non-zero frequency exponential sum estimates of Bourgain on approximate multiplicative subgroups of

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

Unfortunately, once one uses the transcendence theory bound (7), the size

One possible toy model problem for the (weak) Collatz conjecture is a conjecture of Erdos asserting that for 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

with 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