Download article (PDF)
This article is published open access.
T. Tao and the Syracuse conjecture
English translation of the paper “T. Tao et la conjecture de Syracuse” published in , Number 168, April 2021
English translation of the paper “T. Tao et la conjecture de Syracuse” published in La Gazette des Mathématiciens, Number 168, April 2021
We will first recall the Syracuse conjecture (also known as the “” problem) and give a very quick overview of the known results on the subject. Then we will attempt to give some of the ideas behind a remarkable recent result of T. Tao on this conjecture.
The Syracuse conjecture, also called Collatz conjecture, Kakutani conjecture or problem (there is even a paper by B. Thwaites entitled My conjecture), is one of those extraordinarily attractive mathematical questions whose simplicity of statement is matched by their difficulty of proof, to the extent that many (most) of these questions are still open. One can think for example of the Goldbach conjecture or of the Fermat(–Wiles) theorem. A common characteristic of these very difficult conjectures is that their simple statements attract many amateurs, who are certainly well-intentioned, but who are sometimes difficult to convince that their approach is as naive as it is false. One can, however, hardly blame them, since even “professional mathematicians” are regularly seduced by these conjectures, and then realise that their own attempts towards a proof are unsuccessful. They probably do not know that P. Erdős once said to J. C. Lagarias, referring to this conjecture: “Hopeless. Absolutely hopeless”, which is … not very encouraging.
Let us recall the statement of the Syracuse–Collatz–Kakutani––Thwaites problem.
Conjecture. Let be the function defined on the positive integers by
Then all the orbits of are ultimately equal to .
In other words, defining as the -th iterate of , the orbit of every integer under , i.e., the sequence , contains the number , from which it alternatively takes the values and .
Remark. (i) This conjecture is clearly equivalent to the following one: Let be the -adic valuation of the integer (in other words, the largest integer such that divides ) and the function defined on the odd integers by . Then, for any odd integer , there exists an integer such that .
(ii) The history of this conjecture and practically all the results before the one by T. Tao which is the subject of this paper can be found in the book by J. C. Lagarias [9 J. C. Lagarias, The ultimate challenge: the 3x+1 problem. Amer. Math. Soc., Providence, RI (2010) ].
We propose here to first recall the results that have been proved so far, and then to try to summarise Tao’s result, which is stated as follows in [12 T. Tao, Almost all orbits of the Collatz map attain almost bounded values. arXiv:1909.03562 (2020) ].
Almost all orbits of contain an almost bounded element.
2 First steps
The simplicity of the statement of this conjecture is likely to impel us to “play” with it and to do experiments. If we compute the iterates of on sufficiently small integers, we soon see that the orbits reach , and are therefore ultimately equal to . We also see that the pre-period (i.e., the part before the periodic part) of the orbit of is (curiously?) much longer than that of the smaller integers.
Another very general observation is that applying to “half of all integers”, namely the even ones, results in a value smaller than the starting one. Furthermore, if we consider integers of the form , successive applications of give . Since (at least for ), we thus obtain that “a quarter of the integers” leads, after just two iterations of , to a number smaller than the starting one. So in fact at least “ of all integers” belong to the set . More precisely, the natural density of a set of integers is by definition the limit, if it exists, of (and we define the upper and lower density by replacing the limit by the upper and lower limit). Thus what we just saw is equivalent to the statement that the lower density of the set is larger than or equal to . If we now proceed by considering the integers of the form with , then the integers in the residual classes modulo for , we successively obtain lower bounds for the lower density of which are closer and closer to . The author of this paper carried out these experiments in the second half of the 1970s with one of the first programmable pocket calculators (a TI 58): after keeping the machine running for forty-eight hours or more, we obtained values so close to that it was tempting to try to prove this result, in the hope that it would be simpler than the initial conjecture.
It is now time to do some mathematics – simple for the moment – by stating the following result.
The lower density of is equal to , and the same holds for the density of .
The proof is based upon the study of residual classes modulo . The above sketch for integers modulo or is easily generalised by induction on .
Let . Then
For all in , we have
We see from this proposition that the study of for will involve truncated sums of binomial coefficients. In order to estimate these sums, we use the following lemma.
Lemma. For all , there exists an such that
for all sufficiently large values of .
A proof of this lemma suggested by G. Tenenbaum uses the relation
which can be proved by finite induction on and which is, by the way, one of the exercises in the beautiful book by L. Comtet (see [4 L. Comtet, Analyse combinatoire. Tome I. Collection SUP: “Le Mathématicien”, Presses Universitaires de France, Paris (1970) , Exercise 12, p. 91]). For more details, one may refer to a paper by the author published in the Séminaire de Théorie des Nombres de Bordeaux [1 J.-P. Allouche, Sur la conjecture de “Syracuse–Kakutani–Collatz”. In Sém. Th. Nombres, Bordeaux, CNRS, Talence, Exp. No. 9, 15 (1979) ]. The result on density was also proved independently by C. J. Everett in 1977 [5 C. J. Everett, Iteration of the number-theoretic function f(2n)=n, f(2n+1)=3n+2. Adv. Math. 25, 42–45 (1977) ], H. Möller in 1977 [10 H. Möller, F-Normalreihen. J. Reine Angew. Math. 289, 135–143 (1977) ] and E. Heppner in 1978 [6 E. Heppner, Eine Bemerkung zum Hasse-Syracuse-Algorithmus. Arch. Math. (Basel) 31, 317–320 (1978/79) ], and also by R. Terras in his papers of 1976 and 1979 [13 R. Terras, A stopping time problem on the positive integers. Acta Arith. 30, 241–252 (1976) , 14 R. Terras, On the existence of a density. Acta Arith. 35, 101–102 (1979) ], either for the initial problem or for the generalisation due to H. Hasse, see the remark at the end of this section. These different papers written independently at about the same time suggest that the result on density is not very difficult. It relies on a non-trivial limit, which is still a reasonably easy exercise. They also reveal the absence of electronic tools at that time (even if Zentralblatt existed in paper form as well as MathSciNet which was called Mathematical Reviews). I remember, however, that M. Mendès France told me about Heppner’s and/or Möller’s paper afterwards and put an “anonymous” letter with easily recognisable handwriting in my locker: Forget about this problem. A friend who wishes you well – which confirms Erdős’ opinion as reported by Lagarias.
Why doesn’t this density result provide a proof of the conjecture? It is the remaining term in the limit for the density computation that spoils the party – the result we actually obtain can be stated as follows:
for some in , and in fact even if we had , we would still only obtain a weak form of the conjecture, namely that any orbit will eventually “loop” (i.e., is ultimately periodic1Let us recall that a sequence is said to be ultimately periodic if it is periodic for large enough indices, i.e., if there exist and such that, for all and for all , we have .), but there could be more than one loop. One can even refine this by making the above depend on (logarithmically), but this still remains far from the actual conjecture even in its weak form.
However, what the author had overlooked was that the result he had obtained in [1 J.-P. Allouche, Sur la conjecture de “Syracuse–Kakutani–Collatz”. In Sém. Th. Nombres, Bordeaux, CNRS, Talence, Exp. No. 9, 15 (1979) ] (actually a bit more precise than that stated above) could yield something more, namely that the set is of density for . It was I. Korec who mentioned in 1994 in [7 I. Korec, A density estimate for the 3x+1 problem. Math. Slovaca 44, 85–89 (1994) ] that this was pointed out by the referee of his paper. Korec improves the value to , which is about (see the review MR1290275 by Lagarias on MathSciNet).
Remark. A more general formulation of the conjecture, due to H. Hasse, is to replace “multiply by and add , then divide by , or divide by , depending on the value modulo of the starting integer”, by “multiply by and add a suitable residue in a complete system of fixed residues, then divide by , or divide by , depending on whether the starting integer is not or is divisible by ”. The conjecture is then that there exists a function such that if , then all orbits are ultimately periodic and there is a finite number of possible periods, and if , then there exists at least one non-ultimately periodic orbit. Möller [11 H. Möller, Über Hasses Verallgemeinerung des Syracuse-Algorithmus (Kakutanis Problem). Acta Arith. 34, 219–226 (1977/78) ] proposes the function . (Note that is “just” under the threshold for .) Some of the authors quoted above also give density results for this generalisation.
3 Going a bit further
We now give some brief indications on other results (the book by Lagarias mentioned above is very complete and includes in particular an impressive annotated bibliography). We will not discuss the numerical results which produce huge integers such that the conjecture is true for all integers , nor to those which show that the number of elements of any possible period apart from for the orbits of the function is necessarily fantastically large.
An interesting theoretical question is: can we say anything about the integers for which there exists such that ? In other words, can we ask “how many” pre-images of exist under the iterates of ? Because our lack of understanding of this function , we cannot even say that this set has density . The best result obtained thus far is a lower bound of the type
for sufficiently large , with one of the most recent values for being , see [8 I. Krasikov and J. C. Lagarias, Bounds for the 3x+1 problem using difference inequalities. Acta Arith. 109, 237–258 (2003) ].
4 The result obtained by T. Tao
4.1 Introductory remarks
As is the case for the classical conjectures recalled at the beginning of this overview, whenever we fail to obtain a desired result, we always try to obtain at least a weaker form. A typical example is Goldbach’s conjecture, for which J. R. Chen proved a weaker form in [3 J. R. Chen, On the representation of a larger even integer as the sum of a prime and the product of at most two primes. Sci. Sinica 16, 157–176 (1973) ]: Any sufficiently large even number is the sum of a prime number and a number having at most two prime factors. Or think of the Fermat–Wiles theorem, for which an attempt was made to restrict to the “first case” (if , then . Some results of this kind have been described above, in particular the one which states that the density of the set is equal to for .
This last result can be expressed as follows: Almost all integers have in their orbit by an element smaller than the -th power of the considered integer. This is of course a (convenient) abuse of language since density is not a probability on the integers. Using this terminology, one can ask which “best function” could be obtained to replace in the set , while keeping the natural density of this set equal to . In other words, should be such that almost all integers have an element in their orbits by . A caveat is necessary: as pointed out for example in Tao’s paper, one cannot “improve” by “iterating”. Indeed, even if it is true that, for almost all integers , there exists an element with , one cannot apply the result of “almost all” to to obtain an element such that , and thus , because could very well belong to the set of exceptions of the “almost all” and have no associated . Let us also note that we do not know how to obtain , since we do not know (end of the previous section) that the Syracuse conjecture is true for almost all integers. Tao’s “tour de force” is to prove, up to replacing the natural density by the logarithmic density (see below), that one can take for any function tending to infinity, as slowly as one wants for an infinitely large argument. For example, Tao writes, perhaps as a wink to estimates “à la Erdős”, . He summarises this in a figurative way, stating that we can take an “almost bounded” .
Definition. A set of integers is said to have a logarithmic density equal to if the limit, when tends to infinity, of
exists and equals .
Remark. If the natural density of a set of integers exists, its logarithmic density also exists and is equal to the natural density. The converse is not true.
4.2 T. Tao’s theorem
As we have seen above, Tao stipulates in his theorem a striking, even mediatic (in the non-pejorative sense of the term …) statement: Almost all orbits of contain an almost bounded element. This means that, for any function which tends to infinity, the logarithmic density of the set is equal to . We will try to describe (as Tao himself does in the first pages of his paper) in a heuristic way, yet avoiding technical details (the paper has 49 pages), the steps of the proof and the small improvements that it suggests.
(1) Studying the function is classically equivalent to studying the function that Tao calls Syr. Let be the -adic valuation of the integer , that is if divides and does not divide . We define the function Syr on odd integers by
Of course, the Syracuse conjecture is that, for any odd integer , there exists an integer such that . And Tao’s original statement is equivalent to: Let be a function defined on the odd integers that tends to infinity at infinity. Then, for almost all integers , there exists an integer such that (here “almost all integers” means that the set of odd integers for which the property is true, is of logarithmic density in the set of all integers).
(2) How do we compute the iterates of Syr for an odd integer ? Note that , , , etc. Clearly,
This formula can be compared with the one seen above for : , which essentially says that we can estimate the values of successive images of an integer in a class modulo from the images of a representative of this class, until a number of iterations equal to (this number is thus of the order of the logarithm of the considered integer if we have chosen the representative in ).
(3) Take as above . Then, heuristically, for a “typical” odd integer large enough, and much smaller than , the vector behaves like a geometric random vector of size and parameter , i.e., an -tuple of independent random variables, all geometric with parameter . More precisely, the “behaves like” has to be taken in the sense of a small distance between random variables, where the distance between two discrete random variables and taking their values in the same discrete space is the total variation
A proposition proved in Tao’s paper states that the heuristic property in italics at the beginning of step (3) is justified if is uniformly distributed modulo for slightly larger than . This gives a good control of for almost all and for of the order of with a small constant . Since one heuristically has an estimate like , in fact (by the central limit theorem or by the Chernoff bound), one can in this way already obtain again Korec’s result recalled above: the density of the set is for . As Tao points out, a result of this kind is somewhat analogous to “almost sure local wellposedness results” for evolutionary partial differential equations, in which one has good short-time control for almost all initial conditions. Additionally, the theorem we want to prove is similar to an “almost sure almost global wellposedness” result. Now how to get from “local” to “global”?
(4) The last and most difficult step is to answer the above question by introducing a function that further “accelerates” the maps and Syr seen above. This “first passage” function Pass is defined as follows: for and any odd integer , we write
with the usual convention that if for all . The first passage function is then defined by
Tao is then inspired by a work of J. Bourgain [2 J. Bourgain, Periodic nonlinear Schrödinger equation and invariant measures. Comm. Math. Phys. 166, 1–26 (1994) ] who goes from a local almost everywhere to a global almost everywhere, thanks to the construction of an invariant probability measure. Alas! This is impossible here, but the author gets around this issue by introducing a family of probability measures which are approximately transported one to the other by iterating Syr a variable number of times. This is what will permit the use of an iterative argument, which was not feasible “directly” as we pointed out at the beginning of Section 4.1 with and .
We will not go any further in this attempt to demystify Tao’s beautiful proof, whose high technicality, but above all its inventiveness, have been barely touched. To try to summarise it – too schematically – let us start by describing a temptation shared both by the professional mathematician who discovers the Syracuse conjecture and by the amateur: basically, iterating the application from the beginning seems to consist roughly of replacing every second time (when is odd) by approximately , and of replacing every other time (when is even) by ; in other words, applying amounts to multiplying approximately by . For example (with a “reasonably chosen” initial integer),
that is to say
Thus the orbit of a typical integer seems to be obtainable approximately by a sequence of multiplications by . It is this temptation, which obviously does not constitute a proof, that Tao, at the cost of unprecedented effort and technicality for such an apparently innocent statement, has transformed into a proof for almost all integers. There should not be any misunderstanding about the purpose of this remark: to go from “we multiply roughly by ” to Tao’s proof and its half a hundred pages is at least as difficult as transforming a frog or a toad into a charming princess or prince.
5 So, what now?
Now what can we expect for this conjecture? Tao indicates that, by further refining his approach, it should be possible to replace “almost all in logarithmic density” with “almost all in natural density”. But he leaves little hope that the function tending to infinity as slowly as one likes in his statement can be replaced by a constant. In other words, even the statement “the orbit of almost any integer is ultimately periodic” is still totally out of reach.
Acknowledgements The author thanks Sophie Grivaux and Damien Gayet for convincing him to present T. Tao’s paper and also for their enthusiasm. He also thanks the two referees for their valuable comments which helped to improve the first version of this text.
The EMS Magazine thanks La Gazette des Mathématiciens for authorisation to republish this text, which is an English translation of the paper entitled “T. Tao et la conjecture de Syracuse” published in La Gazette des Mathématiciens, Number 168, April 2021. The author would like to thank Miriam Gellrich Pedra and Jean-Bernard Bru for their translation of the original paper.
Jean-Paul Allouche is Directeur de recherche emeritus at CNRS. He is working at IMJ-PRG, Sorbonne, Paris on subjects relating number theory and theoretical computer science, including the so-called automatic firstname.lastname@example.org
Let us recall that a sequence is said to be ultimately periodic if it is periodic for large enough indices, i.e., if there exist and such that, for all and for all , we have .
- J.-P. Allouche, Sur la conjecture de “Syracuse–Kakutani–Collatz”. In Sém. Th. Nombres, Bordeaux, CNRS, Talence, Exp. No. 9, 15 (1979)
- J. Bourgain, Periodic nonlinear Schrödinger equation and invariant measures. Comm. Math. Phys. 166, 1–26 (1994)
- J. R. Chen, On the representation of a larger even integer as the sum of a prime and the product of at most two primes. Sci. Sinica 16, 157–176 (1973)
- L. Comtet, Analyse combinatoire. Tome I. Collection SUP: “Le Mathématicien”, Presses Universitaires de France, Paris (1970)
- C. J. Everett, Iteration of the number-theoretic function f(2n)=n, f(2n+1)=3n+2. Adv. Math. 25, 42–45 (1977)
- E. Heppner, Eine Bemerkung zum Hasse-Syracuse-Algorithmus. Arch. Math. (Basel) 31, 317–320 (1978/79)
- I. Korec, A density estimate for the 3x+1 problem. Math. Slovaca 44, 85–89 (1994)
- I. Krasikov and J. C. Lagarias, Bounds for the 3x+1 problem using difference inequalities. Acta Arith. 109, 237–258 (2003)
- J. C. Lagarias, The ultimate challenge: the 3x+1 problem. Amer. Math. Soc., Providence, RI (2010)
- H. Möller, F-Normalreihen. J. Reine Angew. Math. 289, 135–143 (1977)
- H. Möller, Über Hasses Verallgemeinerung des Syracuse-Algorithmus (Kakutanis Problem). Acta Arith. 34, 219–226 (1977/78)
- T. Tao, Almost all orbits of the Collatz map attain almost bounded values. arXiv:1909.03562 (2020)
- R. Terras, A stopping time problem on the positive integers. Acta Arith. 30, 241–252 (1976)
- R. Terras, On the existence of a density. Acta Arith. 35, 101–102 (1979)
Cite this article
Jean-Paul Allouche, T. Tao and the Syracuse conjecture. Eur. Math. Soc. Mag. 123 (2022), pp. 12–16DOI 10.4171/MAG/64
This open access article is published by EMS Press under a CC BY 4.0 license, with the exception of logos and branding of the European Mathematical Society and EMS Press, and where otherwise noted.