Don’t try to read this proof!

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.

This entry was posted in mathematics, problems and puzzles.

4 Responses to Don’t try to read this proof!

  1. Derek Jones says:

    A while back I did some analysis of source code submitted as answers to a 3n+1 problem in a programming contest.

  2. Fibonacci series as a Turing test? Interesting.

    Preliminary analysis of the algorithm requires that the numbers be integers. A simple division of an even fraction will only yield a smaller fraction, and the equation for the odd number test will only yield further odd numbered fractions. Zero is an even number, but it is a multiplicative identity and will never reduce to one, only more zeros. Negative even numbers have the problem that they will never divide down to a positive value unless the divisor is also negative. The even divisor is a positive two, therefore only positive even numbers. While the stated argument of the proof already eliminates these values, it’s good to eliminate them by simple inspection.

    Any positive power of two will always halt the algorithm. This is from a simple inspection.

    It’s the ODD numbers, or any even number that has an odd number as one of its factors that complicates analysis. Any any even number that has an odd number factor will always degenerate to that odd factor in the even number test of the algorithm. The test of this proof is will any odd number halt the algorithm. If it can be shown that any odd numbers fail to halt the algorithm, the conjecture fails.
    Any odd number can be defined by the equation 2a+1=n, where a is any arbitrary integer and n is the resulting odd number. A characteristic of odd numbers is that the product of any two is another odd number. And 1 + an odd number is always an even number (proofs omitted). The odd number test of the algorithm always feeds an even number back into the algorithm. Using the previous definition of an odd number and the algorithm itself, the real test of the conjecture is does collatz(3a+2) terminate?

    Sorry for the meandering. I’m liking this problem. I’m a math geek. I’m not even going to look at the other proofs. :)

  3. Hemant Verma says:

    Hi All,

    There are related mathematics and algorithms problem here, for those who love mathematics / algorithm problem solviing Mathalon , after all whats in mathematics without problems.

    -Hemant