Magazine Cover
Download article (PDF)

This article is published open access.

MAG123pp. 12–16

T. Tao and the Syracuse conjecture

  • Jean-Paul Allouche

    Sorbonne Université, Paris, France

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 “3n+13n+1” 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.

1 Introduction

The Syracuse conjecture, also called Collatz conjecture, Kakutani conjecture or 3x+13x+1 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–(3x+1)(3x+1)–Thwaites problem.

Conjecture. Let ff be the function defined on the positive integers by

f(n)={3n+12if n is odd,n2if n is even.f(n)=\begin{cases}\dfrac{3n+1}{2}&\textrm{if}\ n\ \textrm{is odd},\\ \dfrac{n}{2}&\textrm{if}\ n\ \textrm{is even}.\end{cases}

Then all the orbits of ff are ultimately equal to (1,2,1,2,1,2,)(1,2,1,2,1,2,\ldots).

In other words, defining fkf^{k} as the kk-th iterate of ff, the orbit of every integer nn under ff, i.e., the sequence (n,f(n),f2(n),)(n,f(n),f^{2}(n),\ldots), contains the number 11, from which it alternatively takes the values 11 and 22.

Remark. (i) This conjecture is clearly equivalent to the following one: Let ν2(n)\nu_{2}(n) be the 22-adic valuation of the integer nn (in other words, the largest integer aa such that 2a2^{a} divides nn) and gg the function defined on the odd integers by Syr(n)=(3n+1)/2ν2(3n+1)\operatorname{Syr}(n)=(3n+1)/2^{\smash[b]{\nu_{2}(3n+1)}}. Then, for any odd integer nn, there exists an integer \ell such that Syr(n)=1\operatorname{Syr}^{\ell}(n)=1.

(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 3⁢x+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) ].

Theorem (Tao).

Almost all orbits of ff 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 ff on sufficiently small integers, we soon see that the orbits reach 11, and are therefore ultimately equal to (1,2,1,2,1,2,)(1,2,1,2,1,2,\ldots). We also see that the pre-period (i.e., the part before the periodic part) of the orbit of 2727 is (curiously?) much longer than that of the smaller integers.

Another very general observation is that applying ff 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 (4m+1)(4m+1), successive applications of ff give 4m+16m+23m+14m+1\to 6m+2\to 3m+1. Since 3m+1<4m+13m+1<4m+1 (at least for m>0m>0), we thus obtain that “a quarter of the integers” leads, after just two iterations of ff, to a number smaller than the starting one. So in fact at least “3/43/4 of all integers” belong to the set S:{n>0k,fk(n)<n}S\coloneq\{n>0\mid\exists k,\,f^{k}(n)<n\}. More precisely, the natural density of a set AA of integers is by definition the limit, if it exists, of #{nAnx}/x\#\{n\in A\mid n\leq x\}/x (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 SS is larger than or equal to 3/43/4. If we now proceed by considering the integers of the form 8m+j8m+j with j[0,7]j\in[0,7], then the integers in the residual classes modulo 2a2^{a} for a=4,5,a=4,5,\dots, we successively obtain lower bounds for the lower density of SS which are closer and closer to 11. 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 11 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.

Theorem.

The lower density of SS is equal to 11, and the same holds for the density of SS.

The proof is based upon the study of residual classes modulo 2a2^{a}. The above sketch for integers modulo 22 or 44 is easily generalised by induction on aa.

Proposition.

  1. Let α(a,j):#{v[0,a1]fv(j) odd}\alpha(a,j)\coloneq\#\{v\in[0,a-1]\mid f^{v}(j)\ \textrm{odd}\}. Then

    fa(2an+j)=3α(a,j)n+fa(j).f^{a}(2^{a}n+j)=3^{\alpha(a,j)}n+f^{a}(j).
  2. For all ii in [0,a][0,a], we have

    #{j[0,2a1]α(a,j)=i}=(ai).\#\{j\in[0,2^{a}-1]\mid\alpha(a,j)=i\}=\biggl(\genfrac{}{}{0.0pt}{0}{a}{i}\biggr).

We see from this proposition that the study of f(n)/nf(n)/n for nxn\leq x will involve truncated sums of binomial coefficients. In order to estimate these sums, we use the following lemma.

Lemma. For all ε(0,1)\varepsilon\in(0,1), there exists an η(0,1)\eta\in(0,1) such that

12aia/2>εa(ai)ηa\frac{1}{2^{a}}\sum_{\lvert i-a/2\rvert>\varepsilon a}\biggl(\genfrac{}{}{0.0pt}{0}{a}{i}\biggr)\leq\eta^{a}

for all sufficiently large values of aa.

A proof of this lemma suggested by G. Tenenbaum uses the relation

i=0m(ai)=(am)(am)12tm(2t)am1dtfor ma1\sum_{i=0}^{m}\biggl(\genfrac{}{}{0.0pt}{0}{a}{i}\biggr)=(a-m)\biggl(\genfrac{}{}{0.0pt}{0}{a}{m}\biggr)\int_{1}^{2}t^{m}(2-t)^{a-m-1}\,\mathrm{d}t\quad\textrm{for}\ m\leq a-1

which can be proved by finite induction on mm 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 11 was also proved independently by C. J. Everett in 1977 [5 C. J. Everett, Iteration of the number-theoretic function f⁢(2⁢n)=n, f⁢(2⁢n+1)=3⁢n+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 11 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:

#{nxk,fk(n)<n}=x+O(x1δ)\#\{n\leq x\mid\exists k,\,f^{k}(n)<n\}=x+O(x^{1-\delta})

for some δ\delta in (0,1)(0,1), and in fact even if we had O(1)O(1), 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 (un)n0(u_{n})_{n\geq 0} is said to be ultimately periodic if it is periodic for large enough indices, i.e., if there exist n00n_{0}\geq 0 and T1T\geq 1 such that, for all nn0n\geq n_{0} and for all k0k\geq 0, we have un+kT=unu_{n+kT}=u_{n}.), but there could be more than one loop. One can even refine this by making the above kk depend on nn (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 Sc:{nk,fk(n)<nc}S_{c}\coloneq\{n\mid\exists k,\,f^{k}(n)<n^{c}\} is of density 11 for c>0.8691c>0.8691. It was I. Korec who mentioned in 1994 in [7 I. Korec, A density estimate for the 3⁢x+1 problem. Math. Slovaca 44, 85–89 (1994) ] that this was pointed out by the referee of his paper. Korec improves the 0.86910.8691 value to log3/log4\log 3/{\log 4}, which is about 0.79250.7925 (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 33 and add 11, then divide by 22, or divide by 22, depending on the value modulo 22 of the starting integer”, by “multiply by mm and add a suitable residue in a complete system of fixed residues, then divide by dd, or divide by dd, depending on whether the starting integer is not or is divisible by dd”. The conjecture is then that there exists a function Φ\Phi such that if m<Φ(d)m<\nobreak\Phi(d), then all orbits are ultimately periodic and there is a finite number of possible periods, and if m>Φ(d)m>\Phi(d), 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 Φ(d)=dd/(d1)\Phi(d)=d^{d/(d-1)}. (Note that m=3m=3 is “just” under the threshold dd/(d1)d^{d/(d-1)} for d=2d=2.) 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 NN such that the conjecture is true for all integers nNn\leq N, nor to those which show that the number of elements of any possible period apart from (1,2)(1,2) for the orbits of the function ff is necessarily fantastically large.

An interesting theoretical question is: can we say anything about the integers nn for which there exists kk such that fk(n)=1f^{k}(n)=1? In other words, can we ask “how many” pre-images of 11 exist under the iterates of ff? Because our lack of understanding of this function ff, we cannot even say that this set has density 11. The best result obtained thus far is a lower bound of the type

#{nxk,fk(n)=1}>xd\#\{n\leq x\mid\exists k,\,f^{k}(n)=1\}>x^{d}

for sufficiently large xx, with one of the most recent values for dd being d=0.84d=0.84, see [8 I. Krasikov and J. C. Lagarias, Bounds for the 3⁢x+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 xp+yp=zpx^{p}+y^{p}=z^{p}, then xyz0modp)xyz\equiv 0\bmod p). Some results of this kind have been described above, in particular the one which states that the density of the set {nxk,fk(n)<nc}\{n\leq x\mid\exists k,\,f^{k}(n)<\nobreak n^{c}\} is equal to 11 for c>0.7925c>0.7925.

This last result can be expressed as follows: Almost all integers have in their orbit by ff an element smaller than the (0.7925)(0.7925)-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” BB could be obtained to replace ncn^{c} in the set {nk,fk(n)nc}\{n\mid\exists k,\,f^{k}(n)\leq n^{c}\}, while keeping the natural density of this set equal to 11. In other words, BB should be such that almost all integers nn have an element B(n)\leq B(n) in their orbits by ff. A caveat is necessary: as pointed out for example in Tao’s paper, one cannot “improve” nncn\to n^{c} by “iterating”. Indeed, even if it is true that, for almost all integers nn, there exists an element n=fk(n)n^{\prime}=f^{k}(n) with nncn^{\prime}\leq n^{c}, one cannot apply the result of “almost all” to nn^{\prime} to obtain an element n=f(n)n^{\prime\prime}=f^{\ell}(n^{\prime}) such that n(n)cn^{\prime\prime}\leq(n^{\prime})^{c}, and thus fk+(n)=f(n)=n(n)c(nc)c=nc2f^{k+\ell}(n)=f^{\ell}(n^{\prime})=n^{\prime\prime}\leq(n^{\prime})^{c}\leq(n^{c})^{c}=n^{c^{2}}, because nn^{\prime} could very well belong to the set of exceptions of the “almost all” and have no associated nn^{\prime\prime}. Let us also note that we do not know how to obtain B(n)=1B(n)=1, 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 BBany 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”, B(n)=loglogloglognB(n)=\log\log\log\log n. He summarises this in a figurative way, stating that we can take an “almost bounded” BB.

Definition. A set of integers ANA\subset\mathbb{N} is said to have a logarithmic density equal to δ\delta if the limit, when xx tends to infinity, of

1logxnx,nA1n\frac{1}{\log x}\smash[b]{\sum_{n\leq x,\,n\in A}\frac{1}{n}}

exists and equals δ\delta.

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 ff contain an almost bounded element. This means that, for any function BB which tends to infinity, the logarithmic density of the set {nk,fk(n)<B(n)}\{n\mid\exists k,\,f^{k}(n)<B(n)\} is equal to 11. 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 ff is classically equivalent to studying the function that Tao calls Syr. Let ν2(n)\nu_{2}(n) be the 22-adic valuation of the integer nn, that is ν2(n)=a\nu_{2}(n)=a if 2a2^{a} divides nn and 2a+12^{a+1} does not divide nn. We define the function Syr on odd integers by

if n is odd, thenSyr(n)=3n+12ν2(3n+1)=fν2(3n+1)(n).\textrm{if}\ n\ \textrm{is odd, then}\,\operatorname{Syr}(n)=\frac{3n+1}{2^{\nu_{2}(3n+1)}}=f^{\nu_{2}(3n+1)}(n).

Of course, the Syracuse conjecture is that, for any odd integer nn, there exists an integer kk such that Syrk(n)=1\operatorname{Syr}^{k}(n)=1. And Tao’s original statement is equivalent to: Let BB be a function defined on the odd integers that tends to infinity at infinity. Then, for almost all integers NN, there exists an integer kk such that Syrk(N)<B(N)\operatorname{Syr}^{k}(N)<B(N) (here “almost all integers” means that the set of odd integers for which the property is true, is of logarithmic density 1/21/2 in the set of all integers).

(2) How do we compute the iterates of Syr for an odd integer NN? Note that a1(N):ν2(3N+1)a_{1}(N)\coloneq\nu_{2}(3N+1), a2:ν2(3Syr(N)+1)a_{2}\coloneq\nu_{2}(3\operatorname{Syr}(N)+1), a3:ν2(3Syr2(N)+1)a_{3}\coloneq\nu_{2}(3\operatorname{Syr}^{2}(N)+1), etc. Clearly,

Syr(N)=(3N+1)2ν2(3N+1)=3.2a1(N)N+2a1(N),\displaystyle\begin{split}\operatorname{Syr}(N)&=(3N+1)2^{-\nu_{2}(3N+1)}\\ &=3.2^{-a_{1}(N)}N+2^{-a_{1}(N)},\end{split}
Syr2(N)=(3Syr(N)+1)2ν2(3Syr(N)+1)=32.2a1(N)a2(N)+3.2a1(N)a2(N)+2a2(N),\displaystyle\begin{split}\operatorname{Syr}^{2}(N)&=(3\operatorname{Syr}(N)+1)2^{-\nu_{2}(3\operatorname{Syr}(N)+1)}\\ &=3^{2}.2^{-a_{1}(N)-a_{2}(N)}+3.2^{-a_{1}(N)-a_{2}(N)}+2^{-a_{2}(N)},\end{split}
etc.\displaystyle\mathrel{\textrm{etc.}}

and therefore,

Syrn(N)=3n2a1(N)a2(N)an(N)N+Fn(a1(N),a2(N),,an(N)),\begin{split}\operatorname{Syr}^{n}(N)&=3^{n}2^{-a_{1}(N)-a_{2}(N)-\cdots-a_{n}(N)}N\\ &\qquad+F_{n}(a_{1}(N),a_{2}(N),\ldots,a_{n}(N)),\end{split}

where

Fn(a1(N),a2(N),,an(N)):3n12a1(N)a2(N)an(N)+3n22a2(N)a3(N)an(N)++312an1(N)an(N)+2an(N).\begin{split}&F_{n}(a_{1}(N),a_{2}(N),\ldots,a_{n}(N))\\ &\qquad\coloneq 3^{n-1}2^{-a_{1}(N)-a_{2}(N)-\cdots-a_{n}(N)}\\ &\qquad\qquad+3^{n-2}2^{-a_{2}(N)-a_{3}(N)-\cdots-a_{n}(N)}\\ &\qquad\qquad+\cdots+3^{1}2^{-a_{n-1}(N)-a_{n}(N)}+2^{-a_{n}(N)}.\end{split}

This formula can be compared with the one seen above for ff: fa(2an+j)=3α(a,j)n+fa(j)f^{a}(2^{a}n+j)=3^{\alpha(a,j)}n+f^{a}(j), which essentially says that we can estimate the values of successive images of an integer in a class modulo 2a2^{a} from the images of a representative of this class, until a number of iterations equal to aa (this number is thus of the order of the logarithm of the considered integer if we have chosen the representative in [0,2a)[0,2^{a})).

(3) Take as above aj(N)=ν2(3Syrj1(N)+1)a_{j}(N)=\nu_{2}(3\operatorname{Syr}^{j-1}(N)+1). Then, heuristically, for a “typical” odd integer NN large enough, and nn much smaller than logN\log N, the vector (a1(N),a2(N),,an(N))(a_{1}(N),a_{2}(N),\ldots,a_{n}(N)) behaves like a geometric random vector of size nn and parameter 1/21/2, i.e., an nn-tuple of independent random variables, all geometric with parameter 1/21/2. 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 XX and YY taking their values in the same discrete space RR is the total variation

rRP(X=r)P(Y=r).\sum_{r\in R}\lvert\mathbb{P}(X=r)-\mathbb{P}(Y=r)\rvert.

A proposition proved in Tao’s paper states that the heuristic property in italics at the beginning of step (3) is justified if NN is uniformly distributed modulo 2m2^{m} for mm slightly larger than 2n2n. This gives a good control of Syrn(N)\operatorname{Syr}^{n}(N) for almost all NN and for nn of the order of γlogN\gamma\log N with a small constant γ\gamma. Since one heuristically has an estimate like Syrn(N)(3/4)nN\operatorname{Syr}^{n}(N)\approx(3/4)^{n}N, in fact Syrn(N)=eO(n)(3/4)nN\operatorname{Syr}^{n}(N)=e^{O(\sqrt{n})}(3/4)^{n}N (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 Sc:{nk,fk(n)<nc}S_{c}\coloneq\{n\mid\exists k,\,f^{k}(n)<n^{c}\} is 11 for c>0.8691c>0.8691. 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 ff and Syr seen above. This “first passage” function Pass is defined as follows: for x1x\geq 1 and any odd integer NN, we write

Tx(N):inf{nNSyrn(N)x}T_{x}(N)\coloneq\inf\{n\in\mathbb{N}\mid\operatorname{Syr}^{n}(N)\leq x\}

with the usual convention that Tx(N):+T_{x}(N)\coloneq+\infty if Syrn(N)>x\operatorname{Syr}^{n}(N)>x for all nn. The first passage function is then defined by

Passx(N):SyrTx(N)(N).\mathrm{Pass}_{x}(N)\coloneq\operatorname{Syr}^{T_{x}(N)}(N).

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 ncn^{c} and (nc)c(n^{c})^{c}.

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 ff from the beginning seems to consist roughly of replacing nn every second time (when nn is odd) by approximately 3/2n3/2\cdot n, and of replacing nn every other time (when nn is even) by 1/2n1/2\cdot n; in other words, applying f2f^{2} amounts to multiplying nn approximately by 3/43/4. For example (with a “reasonably chosen” initial integer),

17f26f13f20f10f,17\stackrel{{\scriptstyle f}}{{\to}}26\stackrel{{\scriptstyle f}}{{\to}}13\stackrel{{\scriptstyle f}}{{\to}}20\stackrel{{\scriptstyle f}}{{\to}}10\stackrel{{\scriptstyle f}}{{\to}}\cdots,

that is to say

17f213f210f2.17\stackrel{{\scriptstyle f^{2}}}{{\to}}13\stackrel{{\scriptstyle f^{2}}}{{\to}}10\stackrel{{\scriptstyle f^{2}}}{{\to}}\cdots.

Thus the orbit of a typical integer seems to be obtainable approximately by a sequence of multiplications by 3/43/4. 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 3/43/4” 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 sequences.jean-paul.allouche@imj-prg.fr

  1. 1

    Let us recall that a sequence (un)n0(u_{n})_{n\geq 0} is said to be ultimately periodic if it is periodic for large enough indices, i.e., if there exist n00n_{0}\geq 0 and T1T\geq 1 such that, for all nn0n\geq n_{0} and for all k0k\geq 0, we have un+kT=unu_{n+kT}=u_{n}.

References

  1. J.-P. Allouche, Sur la conjecture de “Syracuse–Kakutani–Collatz”. In Sém. Th. Nombres, Bordeaux, CNRS, Talence, Exp. No. 9, 15 (1979)
  2. J. Bourgain, Periodic nonlinear Schrödinger equation and invariant measures. Comm. Math. Phys. 166, 1–26 (1994)
  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)
  4. L. Comtet, Analyse combinatoire. Tome I. Collection SUP: “Le Mathématicien”, Presses Universitaires de France, Paris (1970)
  5. C. J. Everett, Iteration of the number-theoretic function f⁢(2⁢n)=n, f⁢(2⁢n+1)=3⁢n+2. Adv. Math. 25, 42–45 (1977)
  6. E. Heppner, Eine Bemerkung zum Hasse-Syracuse-Algorithmus. Arch. Math. (Basel) 31, 317–320 (1978/79)
  7. I. Korec, A density estimate for the 3⁢x+1 problem. Math. Slovaca 44, 85–89 (1994)
  8. I. Krasikov and J. C. Lagarias, Bounds for the 3⁢x+1 problem using difference inequalities. Acta Arith. 109, 237–258 (2003)
  9. J. C. Lagarias, The ultimate challenge: the 3⁢x+1 problem. Amer. Math. Soc., Providence, RI (2010)
  10. H. Möller, F-Normalreihen. J. Reine Angew. Math. 289, 135–143 (1977)
  11. H. Möller, Über Hasses Verallgemeinerung des Syracuse-Algorithmus (Kakutanis Problem). Acta Arith. 34, 219–226 (1977/78)
  12. T. Tao, Almost all orbits of the Collatz map attain almost bounded values. arXiv:1909.03562 (2020)
  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)

Cite this article

Jean-Paul Allouche, T. Tao and the Syracuse conjecture. Eur. Math. Soc. Mag. 123 (2022), pp. 12–16

DOI 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.
Back to Issue 123