The Ultimate Challenge: The $3x+1$ Problem

As the title asserts, this book is a thorough account of an open and challenging problem. The $3x+1$ problem is the following conjecture: ``Start with any positive integer number $x_1$ (called seed) and form the sequence: $x_{n+1}=x_n/2$ if $x_n$ is even, $x_{n+1}=3x_n+1$ if $x_n$ is odd. Then there is some $N$ such that $x_N=1$’’. This property has been tested for seeds up to $5\times 10^{18}$, but yet there is no proof of it.

The origins of the problem are not completely clear. It is generally attributed to Lothar Collatz, who circulated it orally at the International Congress of Mathematicians in Cambridge, US, in 1950. He came to it by his study of the graphs associated to iterative procedures on the integer numbers. Another claimant to have originated the conjecture is Bryan Thwaites, who asserts he came up with the problem in 1952. The $3x+1$ problem receives many names in the literature: Collatz conjecture, Syracuse problem, Hasse’s algorithm, Kakutani’s problem or Ulam’s problem.

Despite of the simplicity of its formulation, many mathematicians simply think that mathematics is not ready for solving it. Paul Erdös said “Mathematics is not yet ripe for such question” and Richard Guy puts it in his list “Don’t try to solve these problems”.

The first papers on the $3x+1$ problem date from the 60s. Since then, more than 300 papers have appeared in print. This book is an extensive account of the work carried out in relation to it. The book is edited by Jeffrey C. Lagarias, who is well-known by his interest and work in the conjecture. It contains the following material:

a) An introduction consisting of an overview of the problem with historical remarks, and with many generalizations of it, which is written by Lagarias himself.

b) A collection of survey papers, written by different authors. Let $T$ be the Collatz map in the positive integers, so $x_{n+1}=T(x_n)$. This generates a dynamical system. As such, the orbit of a point can have three possible behaviors: 1) to hit $1$ and then enter in the cycle $4,2,1$; 2) to enter into a different cycle; 3) to escape to infinity. The conjecture says that only possibility 1) occurs. The main lines of research for studying this are:
- Number theory. The question deals with integers, and it is easily seen to be related to congruences. For instance, with an equation of the type $T^k(y)=y$, it may be proved that the length of a possible cycle satisfying 2) is at least $10^{10}$.
- Dynamical systems. The dynamical properties of the $3x+1$ function are of interest. Extending the problem to other sets of numbers (like the 2-adic numbers), $T$ has several ergodic properties. However ${\mathbb Z}$ is of measure zero in ${\mathbb Z}_2$, so this is not of much help.
- Stochastic models. One tries to measure the set of integers which eventually land in $1$. It is necessary that for any $x$, and iteration satisfies $T^k(x) \lt x$. It is proved that the set of integers satisfying this is of full density. However, this is not enough even to prove that the set of seeds satisfying 1) above is of full density. It can be proved that the latter set is of logarithmic asymptotic measure $0.84$ (i.e. $T^{0.84}$ numbers $x\n [1,T]$ satisfy the conjecture for $T$ large). This is compared against the similar $5x+1$ problem, in which most orbits are expected to escape to infinity, but not for a single one this has yet been proved.
- Empirical verification of the $3x+1$ conjecture has been undertaken with the implementation of efficient algorithms in computers during long periods of time. The conjecture holds for $x_1$ up to $5.76 \times 10^{18}$. Many other properties of growth of the iterations are checked empirically.
- Computability. The map $T$ behaves as a computer program. John Conway has studied natural generalizations of this problem, iterative maps $T(x) = (k_i x + r_i)/d$, for $x\equiv i$ (mod $d$), as machines in the theory of computability. He has even developed a language (Fractran) which simulates Turing machines. The striking result is that some of these problems are undecidable (one cannot say if the iterations will end in a particular number), simply because they simulate universal machines. The range of iterative maps for which undecidability happens does not cover the $3x+1$ function. Of course, one expects that the Collatz conjecture is true, but it should not be easy to explain for which reason this problem is not undecidable when similar ones are.

c) The book ends with 75 pages commenting all bibliography on the problem until 1999. The author keeps annotated bibliography from 2000 onwards in

Vicente Muñoz
Book details

The $3x+1$ problem, or Collatz problem, concerns the following seemingly innocent arithmetic procedure applied to integers: If an integer $x$ is odd then "multiply it by three and add one", while if it is even then "divide it by two". The $3x+1$ problem asks whether, starting from any positive integer, and repeating this procedure over and over, we will eventually reach the number $1$. Despite its simple appearance, this problem is unsolved. Generalizations of the problem are known to be undecidable, and the problem itself is believed to be extraordinarily difficult.




User login