On the subject of the Collatz conjecture (also known as the 3x+1 problem), Paul Erdos remarked: “Mathematics is not yet ready for such problems.” Shizuo Kakutani joked that the problem was a Cold War invention of the Russians meant to slow the progress of mathematics in the West. Richard Guy listed it in an article titled “Don’t try to solve these problems!” All of these warnings to the unwary have had the expected effect: A bibliography compiled by Jeffrey Lagarias cites 200 works on the Collatz conjecture, and there are hundreds of other papers that didn’t make the list. This past week brought one more preprint: a claimed proof of the conjecture by Gerhard Opfer of the University of Hamburg.
The Collatz conjecture can be stated in terms of this little recursive program:
procedure collatz(x)
if x=1 then halt
elseif even(x) then collatz(x/2)
elseif odd(x) then collatz(3*x+1);
The conjecture makes the following claim: If x is any positive integer, then the program eventually halts. For example, starting with x=3, the successive values of x are 3, 10, 5, 16, 8, 4, 2, 1—and on reaching x=1 the program halts. You could try a few other starting values for yourself; x=27 is a popular choice; x=319,804,831 is even better. But please remember Guy’s advice. Also note that the Collatz conjecture has been verified numerically by Tomás Oliveira e Silva for all x up to 20 × 258 . Thus if you’re searching for a counterexample, you may as well start somewhere north of 5,764,607,523,034,234,880.
The conjecture is named for Lothar Collatz (1910–1990), who investigated the curious properties of the 3x+1 iteration when he was a young student, circa 1930. Opfer, the author of the new proposed proof, was a Ph.D. student of Collatz in the 1960s. This conjunction suggests a novelistic storyline: A mathematician struggles all his life with an intractable problem, then hands it on to his student, who dedicates his own career to the task, finally achieving triumphant success some 80 years after the story began. But apparently that’s not how it happened. Collatz never returned to the 3x+1 problem after the 1930s; almost all of his mature work was in numerical analysis. Opfer is also a numerical analyst and only recently turned to the 3x+1 problem. There’s no grand saga of a multigenerational obsession here.
Much of Opfer’s paper is beyond my understanding, but I can piece together a crude guide to a few of the basic ideas. The proof begins with a mathematical change of venue. A problem originally posed in terms of the simplest kind of arithmetic on the natural numbers is transported to the realm of holomorphic functions on the complex plane. It’s like being swept up from a farm in Kansas and set down in the Land of Oz. The idea for this transformation comes from the work of Lothar Berg and Günter Meinardus in the 1990s, who established a direct connection between these two realms. They set up a certain system of equations for functions of a complex variable z, then showed that the Collatz conjecture is true if and only if the solutions of the equations all lie in a certain region. In the simplest case, the region is the open unit disc—the disc centered at the origin with |z| < 1. Who’d’ve thunk it? What we do in Oz has consequences back in Kansas!
How can those two very different problems be yoked together? As I (tenuously) understand it, the complex functions of Berg and Meinardus can be represented by formal power series whose integer coefficients encode information about the sequence of numbers generated in the Collatz iteration. The rest of the Opfer proof is all about those coefficients. Thus we click our heels and return from the Emerald City to the land of number theory.
At this point Opfer begins reasoning in terms of algorithms that generate sets of coefficients. I’m on much friendlier terms with algorithms than I am with holomorphic functions, but strangely enough this is where I begin to lose my footing as I try to follow Opfer’s steps. His aim is to show that all coefficients vanish except for those whose indices lie in a certain congruence class. (Specifically, he is seeking to prove that all coefficients ηj = 0 except those for which j = 3k–1, k ∈ 1, 2, 3, … .) He argues that his algorithms for generating the coefficients yield exactly this property. But this is where I get lost.
Opfer is not the first to announce a proof of the Collatz conjecture. The earlier attempts did not stand up to scrutiny, and in various corners of nerdom there’s already skepticism about this try, too. As for me, I can’t say whether there are gaps in Opfer’s proof because there are such wide gaps in my understanding of it. The paper has been submitted to Mathematics of Computation, which is certainly an appropriate journal for this work, and I’m content to wait and see what comes of the referreeing process.
Like many others, I first learned of the 3x+1 problem from Martin Gardner’s Scientific American column in the early 1970s. A decade later, when I briefly had a chance to fill Martin’s space in the magazine after his retirement, 3x+1 was one of the first subjects I wrote about (nearly illegible PDF—sorry; it’s my only copy). I’m delighted to have this opportunity to poke at the problem again. Even if the Opfer proof comes to nothing, it has given me an incentive to read some of the recent literature, including that illuminating trip to Oz courtesy of Berg and Meinardus. I would also like to recommend a book by Günther J. Wirsching, The Dynamical System Generated by the 3n + 1 Function (Springer, 1998). A version of at least one chapter is available online.
Jeffrey Lagarias also has a recent book: The Ultimate Challenge: The 3x+1 Problem (AMS, 2010), but I haven’t seen it yet. The volume reprints a number of survey articles and historical documents, including a 1985 American Mathematical Monthly article by Lagarias himself that is still the best starting point for those who want to ignore all good advice and dive into the problem. I am particularly eager to see another chapter: an English translation of the only paper in which Collatz discusses his work on 3x+1; it is an account in Chinese of a talk by Collatz at Qufu Normal University in 1986.
Update 2017-03-10: For the record, Gerhard Opfer withdrew his claim of a proof a few days after this essay was originally posted.