One of the most notorious problems in elementary mathematics that remains unsolved is the Collatz conjecture, concerning the function defined by setting when is odd, and when is even. (Here, is understood to be the positive natural numbers .)
Conjecture 1 (Collatz conjecture) For any given natural number , the orbit passes through (i.e. for some ).
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 odd, then is even, and so . Because of this, one could replace by the function , defined by when is odd, and when is even, and obtain an equivalent conjecture. Now we see that if one chooses “at random”, in the sense that it is odd with probability and even with probability , then increases by a factor of roughly half the time, and decreases it by a factor of half the time. Furthermore, if is uniformly distributed modulo , one easily verifies that is uniformly distributed modulo , and so should be roughly times as large as half the time, and roughly times as large as the other half of the time. Continuing this at a heuristic level, we expect generically that half the time, and the other half of the time. The logarithm of this orbit can then be modeled heuristically by a random walk with steps and occuring with equal probability. The expectation
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 is chosen uniform at random (e.g. in some large interval ). (It also suggests that if one modifies the problem, e.g. by replacing to , 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 for time about 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 from the integers to the -adics . This compact abelian group comes with a Haar probability measure, and one can verify that this measure is invariant with respect to ; 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 is a random -adic integer, then almost surely the orbit 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 , as this is a measure zero subset of . 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 on the unit circle is well understood from ergodic theory (in particular, almost all orbits will be uniformly distributed), but the orbit of a specific point, e.g. , is still nearly impossible to understand (this particular problem being equivalent to the notorious unsolved question of whether the digits of are uniformly distributed).
The above heuristic argument only suggests decreasing orbits for almost all (though even this remains unproven, the state of the art is that the number of in that eventually go to is , a result of Krasikov and Lagarias). It leaves open the possibility of some very rare exceptional for which the orbit goes to infinity, or gets trapped in a periodic loop. Since the only loop that lies in is (for ) or (for ), we thus may isolate a weaker consequence of the Collatz conjecture:
Conjecture 2 (Weak Collatz conjecture) Suppose that is a natural number such that for some . Then is equal to , , or .
Of course, we may replace with (and delete ““) 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 and :
Conjecture 3 (Reformulated weak Collatz conjecture) There does not exist and integers
such that is a positive integer that is a proper divisor of
Proof: To see this, it is convenient to reformulate Conjecture 2 slightly. Define an equivalence relation on by declaring if for some integer , thus giving rise to the quotient space of equivalence classes (which can be placed, if one wishes, in one-to-one correspondence with the odd natural numbers). We can then define a function by declaring
for any , where is the largest power of that divides . It is easy to see that is well-defined (it is essentially the Syracuse function, after identifying with the odd natural numbers), and that periodic orbits of correspond to periodic orbits of or . Thus, Conjecture 2 is equivalent to the conjecture that is the only periodic orbit of .
Now suppose that Conjecture 2 failed, thus there exists such that for some . Without loss of generality we may take to be odd, then . It is easy to see that is the only fixed point of , and so . An easy induction using (2) shows that
where, for each , is the largest power of that divides
In particular, as is odd, . Using the recursion
we see from induction that divides , and thus :
Since , we have
for some integer . Since is divisible by , and is odd, we conclude ; 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 , integers
and a natural number such that (1) holds. As , we see that the right-hand side of (1) is odd, so is odd also. If we then introduce the natural numbers by the formula (3), then an easy induction using (4) shows that
with the periodic convention for . As the are increasing in (even for ), we see that is the largest power of that divides the right-hand side of (5); as is odd, we conclude that is also the largest power of that divides . We conclude that
and thus is a periodic orbit of . Since is an odd number larger than , this contradicts Conjecture 3.
Call a counterexample a tuple that contradicts Conjecture 3, i.e. an integer and an increasing set of integers
such that (1) holds for some . We record a simple bound on such counterexamples, due to Terras and to Garner :
Lemma 5 (Exponent bounds) Let , and suppose that the Collatz conjecture is true for all . Let be a counterexample. Then
Proof: The first bound is immediate from the positivity of . To prove the second bound, observe from the proof of Proposition 4 that the counterexample will generate a counterexample to Conjecture 2, i.e. a non-trivial periodic orbit . As the conjecture is true for all , all terms in this orbit must be at least . An inspection of the proof of Proposition 4 reveals that this orbit consists of steps of the form , and steps of the form . As all terms are at least , the former steps can increase magnitude by a multiplicative factor of at most . As the orbit returns to where it started, we conclude that
whence the claim.
The Collatz conjecture has already been verified for many values of (up to at least , according to this web site). Inserting this into the above lemma, one can get lower bounds on . For instance, by methods such as this, it is known that any non-trivial periodic orbit has length at least , as shown in Garner’s paper (and this bound, which uses the much smaller value 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 and , then , and from basic combinatorics we see that there are different ways to choose the remaining integers
to form a potential counterexample . As a crude heuristic, one expects that for a “random” such choice of integers, the expression (1) has a probability of holding for some integer . (Note that is not divisible by or , 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 where the right-hand side in (1) is too small to be divisible by , 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 is
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 , with the approximation here accurate to many decimal places.
We need a lower bound on . Here, we will use Baker’s theorem (as discussed in this previous post), which among other things gives the lower bound
for some absolute constant . Meanwhile, Stirling’s formula (as discussed in this previous post) combined with the approximation gives
where is the 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 well away from would suffice. In particular, one does not need an enormous value of ; even (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 , 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
In some very special cases, this can be done. For instance, suppose that one had with at most one exception (this is essentially what is called a -cycle by Steiner). Then (8) simplifies via the geometric series formula to a combination of just a bounded number of powers of and , 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 -cycles cannot actually occur, and similar methods have been used to show that -cycles (in which there are at most exceptions to ) do not occur for any , as was shown by Simons and de Weger. However, for general increasing tuples of integers , 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 .
Amusingly, there is a slight connection to Littlewood-Offord theory in additive combinatorics – the study of the random sums
generated by some elements of an additive group , or equivalently, the vertices of an -dimensional parallelepiped inside . Here, the relevant group is . The point is that if one fixes and (and hence ), and lets vary inside the simplex
then the set of all sums of the form (8) (viewed as an element of ) contains many large parallelepipeds. (Note, incidentally, that once one fixes , all the sums of the form (8) are distinct; because given (8) and , one can read off as the largest power of that divides (8), and then subtracting off one can then read off , and so forth.) This is because the simplex contains many large cubes. Indeed, if one picks a typical element of , then one expects (thanks to Lemma 5) that there there will be indices such that for , which allows one to adjust each of the independently by if desired and still remain inside . This gives a cube in of dimension , which then induces a parallelepiped of the same dimension in . A short computation shows that the generators of this parallelepiped consist of products of a power of and a power of , and in particular will be coprime to .
If the weak Collatz conjecture is true, then the set must avoid the residue class in . Let us suppose temporarily that we did not know about Baker’s theorem (and the associated bound (7)), so that could potentially be quite small. Then we would have a large parallelepiped inside a small cyclic group that did not cover all of , which would not be possible for small enough. Indeed, an easy induction shows that a -dimensional parallelepiped in , with all generators coprime to , has cardinality at least . This argument already shows the lower bound . In other words, we have
Proposition 6 Suppose the weak Collatz conjecture is true. Then for any natural numbers with , one has .
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 and powers of 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 with , one has for some absolute constant .
Proof: (Informal sketch only) Suppose not, then we can find with of size . We form the set as before, which contains parallelepipeds in of large dimension that avoid . We can count the number of times 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 (and the fact that ) forces the generators to be concentrated in a Bohr set, in that one can find a non-zero frequency such that of the generators lie in the set . However, one can choose the generators to essentially have the structure of a (generalised) geometric progression (up to scaling, it resembles something like for ranging over a generalised arithmetic progression, and 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 , though one can use more elementary methods here due to the very strong nature of the Bohr set concentration (being of the “ concentration” variety rather than the “ concentration”).). This furnishes the required contradiction.
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 and powers of .
Unfortunately, once one uses the transcendence theory bound (7), the size of the cyclic group becomes larger than the volume of any cube in , and Littlewood-Offord techniques are no longer of much use (they can be used to show that is highly equidistributed in , but this does not directly give any way to prevent from containing ).
One possible toy model problem for the (weak) Collatz conjecture is a conjecture of Erdos asserting that for , the base representation of contains at least one . (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
with and . (When , of course, one has .) 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 has about base digits, so the heuristic probability that none of these digits are equal to is , which is absolutely summable.
355 comments
Comments feed for this article
18 February, 2023 at 4:08 pm
Ulrich Sondermann
While working on recursion, I noticed that 3x+1 returns repunits in base 3. Generally bx+c returns repunits in base b of c digits c<b. I have no idea if this will help anyone working on collatz. All of the repunit numbers lead to 1.
30 March, 2023 at 5:11 am
Terence Tao makes development on the Collatz conjecture (2019) – CYBE
[…] this previous August an anonymous reader left a observation on Tao’s weblog. The commenter urged in search of to clear up the Collatz conjecture for “virtually […]
27 November, 2023 at 3:53 am
Alberto Ibañez
Hello everyone. Again here. If you find it interesting, I would like to discuss the possibility of entering a periodic orbit.
As we know, multiples of 3 odd cannot enter a periodic orbit. In fact, if the conjecture is true, ignoring the possibility of unbounded orbits, every sequence until reaching 1 has as its origin a multiple of 3 odd, so we can prove that every collatz sequence, that is, in reverse, will always be found with a multiple of 3. To do this I have made a table where we can see all the odd numbers that are not multiples of 3 and follow their path by multiplying them by a power of 2 and subtract 1 and where we can recognize those numbers that are multiples of 9, which when divided by 3 will be multiples of 3. I would have liked to make this table larger, but it is the best thing to do, so I invite you to make it larger if it is of your interest.
In short, the question would be whether for every odd n that runs through, like a Collatz sequence going backwards, this table is always trapped in a multiple of 9.
Note that for every 6 positions both from left to right and from top to bottom we find a multiple of 9.
Thank you and I hope you may have some interest. All the best
27 November, 2023 at 4:00 am
Alberto Ibañez
Sorry, I can’t upload it correctly. I write the latex in case you can upload it correctly.
Thank you
\begin{table}
\centering
\begin{tabular}{c|ccccccccc}
1 & 2 & 4 & 8 &16 &32 & 64 & 128 & 256 \\ \hline
1 &1 & 3 & 7 & 15& 31 & \underline{63} & 127 & 255 & \\
5 & \underline{9} & 19 &39 &79 &159 &319 &\underline{639} &1279 & \\
7 &13 &\underline{27} &55 &111 &223 &447 & 895& \underline{1791} & \\
11 & 21 & 43 & 87 & 175 & \underline{351} & 703 & 1407 & 2815 & \\
13 & 25 & 51 & 103 & \underline{207}&415 & 831 & 1663 & 3327 & \\
17 & 33 & 67 & \underline{135} & 271&543 &1087 & 2175& 4351 & \\
19 & 37 &75 & 151 & 303& 607 & \underline{1215} & 2431 & 4863 & \\
23 & \underline{45} & 91 & 183 & 367& 735 & 1471 & \underline{2943} & 5887 & \\
25 & 49 & \underline{99} & 199 & 399 & 799 & 1599& 3199 &\underline{6399} & \\
\end{tabular}
\caption{9 multiples}
\label{tab:my_label}
\end{table}
28 November, 2023 at 7:51 am
Anonymous
Is anyone jnterested in my research results concerning the Collatz-Problem (w-schlund@web.de)
29 November, 2023 at 12:33 am
Anonymous
No not at all interested in ur ‘obsessions’
5 December, 2023 at 3:50 pm
Anonymous
“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.”
Intuitively yes all the sums of the form (8) are distinct, but this argument can’t be correct as otherwise a1, a2… will be determined by k alone using this algorithm.
5 December, 2023 at 5:29 pm
Terence Tao
The argument does not assert that can be determined by alone, but rather by a combination of and the quantity (8).
7 December, 2023 at 1:47 pm
Anonymous
Sorry the copy/paste seems to have messed up so I’ll post again.
“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.”
The number of different ways of choosing a_1, a_2 etc should be k^(a-k)
If we define d_i as a_{i+1} – a_{i} , then d_i >= 1, and the number of different ways of choosing a_1, a_2 etc. is the same as choosing d_1, d_2 etc.
This can be calculated by setting d_i = 1 initially, then putting the rest of the balls (a-k in total) into different d_i positions (k in total to choose from). There are {k^(a-k)} different ways to do this.
The {k^(a-k)} different ways to choose a_1, a_2 are not independent in term of co-prime with {q}, as if one of them is divisible by q, then the other k-1 values in the same cycle will be divisible by q as well. Therefore the top term should be {k^(a-k-1)}. This gives the total number of solutions as:
\sum_{k}^{}\frac{1}{q}{k}^{a-k-1}
I don’t think the series is convergent given the lower bound from Baker’s thereom.
7 December, 2023 at 4:24 pm
Terence Tao
Your procedure is not injective: if you put the first ball into the position and the second ball into the position, for instance, this produces the same outcome as when you instead put the first ball into the position and the second ball into the position. So the number of combinations is much smaller than , and as I stated is actually (these results are sometimes known as “Stars and bars” theorems).
10 March, 2024 at 3:16 am
Alberto Ibañez
On the existence of non-trivial periodic orbits
We have that
Professor says “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 (8)”
which for simplicity we can call TCR
whose size is
If there are at least k values of this set that are multiples of q, then a non-trivial orbit will exist.
if we can establish
where is the difference of nth power
and
and
We will have within the set of TCR numbers of the form 8 several subsets that differ in a multiple of 3 and the last term, which is a difference in powers of 2
The question, which I am not able to resolve, is whether these subsets are easier to study if it is possible that they are multiples of q.
Thank you
19 March, 2024 at 3:42 am
Alberto Ibañez
On the existence of non-trivial periodic orbits
I want to propose a possible way to attack this question.
It would be about studying the minimum value of q for each power of 3 and the smallest power of 2 greater than that power of 3, for positive q.
With the means I have done an excel and see the values up to 3^45 and you can see that the value of q grows and grows. Surely this may be very obvious to all of you and perfectly established
We also know that for each power of 3 and depending on the value of the power of 2 we have a finite set of numbers of the form (8), which for simplicity is called TCR, possible candidates to form a periodic orbit, with a maximum value and minimum
The idea would be to study the maximum value of this set for each power of 3 and the minimum value of q. This would already be far outside my possibilities beyond a few calculations.I’m sure many of you can formalize these calculations, if they are possible.
If we divide this value of TCR max for each value of q min, for each power of 3, we obtain the highest number that would form that possible periodic orbit, and if in some way it will be observed that the limit(?) of this function(?) will remain below the values that today we know reach 1, perhaps it could be established that there is no possibility that any number (set of numbers) can be part of a periodic orbit.
I really don’t know if this approach could have any interest and is worth studying.
Anyway, thanks
19 March, 2024 at 4:35 am
Anonymous
Related:
https://oeis.org/history/view?seq=A370354&v=9999
https://oeis.org/history/view?seq=A370484&v=9999
https://oeis.org/history/view?seq=A370935&v=9999
(not approved and published yet, so treat as WIP)
8 December, 2023 at 3:01 am
Anonymous
See also https://oeis.org/A100982.
(and its “history”)
19 January, 2024 at 2:56 pm
Aleksandr Turnaev
Based on the formulation of conjecture 3, it actually seems that it is not true.
Indeed, if we extend the hypothesis to negative n, it will obviously be incorrect, since in addition to the cycle starting from 1, there are also cycles starting from $-1,-5,-17$.
Let’s consider what is remarkable about the cases $n=1, -1, -5$.
Note that
$$1=\frac{2^0}{2^2-3^1}=\frac{2^0}{1}$$
$$-1=\frac{2^0}{2^1-3^1}=\frac{2^0}{-1}$$
$$-5=\frac{2^{1}+2^{0}\cdot3^{1}}{2^{3}-3^{2}}=\frac{2^1+2^0\cdot 3^1}{-1}$$
That is, in a sense, all these cycles are trivial, since the denominator is $1$ or $-1$ and therefore the numerator does not matter.
But in the case of negative numbers, there are also non-trivial cycles, for example, induced by $-17$:
$$
-17 = \frac{2^{7}+2^{6}\cdot3+2^{5}\cdot3^{2}+2^{3}\cdot3^{3}+2^{2}\cdot3^{4}+2^{1}\cdot3^{5}+2^{0}\cdot3^{6}}{2^{11}-3^{7}} = \frac{\ldots}{-139}
$$
Of course, the number is small in absolute value, but nevertheless. The question arises, what is the fundamental difference between the cases of positive natural numbers and negative ones, why can’t some non-trivial cycle suddenly arise?
24 February, 2024 at 11:00 pm
Anonymous
The is no difference, in both cases total number of cycles is thought to be finite. And taken that for values at least up to 2^70 conjecture is already verified, chances are there are no more cycles.. Unless one finds a way to construct series of n with exponentially growing stopping times, which seems unlikely
10 April, 2024 at 10:48 am
Anonymous
See also
https://oeis.org/history/view?seq=A370484&v=9999
for the transcendental angle.