The Collatz conjecture is safe (for now)

A few days ago John Cook reported a draft paper claiming to solve the Collatz conjecture. Of course, since the Collatz conjecture is so simple to state, it constantly attracts tons of would-be solvers, and most of the purported “proofs” they generate are not even worth mathematicians’ time to look at. So why should this one be different? Well, on the surface, it seemed to be a much more serious attempt than the vast majority. Of Scott Aaronson’s Ten Signs a Claimed Mathematical Breakthrough is Wrong, this paper exhibited only #6 (jumping straight into technical material without presenting a new idea) and #10 (using techniques that seem too wimpy). But #6 could just be due to poor organization of the paper, and #10 is not obvious until you get to the end.

But — and you knew this was coming — it is wrong. I’ve spent several hours over the past few days reading over the paper and came to this conclusion independenly — and then found several other people who had come to the same conclusion, for the same reason.

Consider the following “proof” of the Collatz conjecture. We consider running the Collatz function (call it $c$) “backwards”, to find out which number(s) could have preceded a given number in a Collatz sequence. We always have $c(2k) = k$, so from $k$ we can go backwards to $2k$. Also, $c((k-1)/3) = 3*(k-1)/3 + 1 = k$ when $(k-1)/3$ is an odd integer, that is, when $k$ is one more than an odd multiple of $3$. These are the only two possibilities. So, starting from $1$, we can go backwards to $2$; from $2$ we can go backwards to $4$; from $4$ we can go to $8$ or $1$; from $8$ we get $16$; from $16$ we get $32$ or $5$; and so on. In this way we can build up an infinite tree of numbers. But this tree contains every natural number since we can always work up the tree from $1$ until we find any number we want. Hence every number must reach $1$ when iterating the Collatz function.

Do you see the problem with this “proof”? Well, this is essentially what Gerhard Opfer’s “proof” boils down to as well (the details are not exactly the same, but the form is pretty much identical). There is a lot of stuff first about linear operators over complex functions, but for this part he is just relying on work that someone else already did anyway, and in the end he just ends up looking at coefficients of power series, which just boils down to some number theory. He builds a tree by inverting a certain function (not the Collatz function but a closely related one), and the whole argument rests on the fact that this tree contains every natural number — which he states but does not prove! And it seems clear to me that proving this would be no easier than proving the Collatz conjecture itself. In the end, for all the detailed argument and contortion, he has come back precisely to where he started.

(By the way, I am not interested in reading your supposed proof of the Collatz conjecture, so please do not post a link to it in the comments!)

This entry was posted in open problems, proof. Bookmark the permalink.

43 Responses to The Collatz conjecture is safe (for now)

1. Pingback: Conjectura lui Collatz | Isarlâk

2. Hans says:

Your post sounds very arrogant in the beginning. Sayings like “Of course, since the Collatz conjecture is so simple to state, it constantly attracts tons of would-be solvers, and most of the purported “proofs” they generate are not even worth mathematicians’ time to look at. So why should this one be different?” are just that, arrogant from the start to the beginning.

• Brent says:

I’m sorry if it came off sounding arrogant, but it is simply the truth.

• Ben says:

That is a killer phrase which is heavily used by (religious) fundamentalists. Here is some others that you might want to use for future posts. http://www.whatagreatidea.com/killerphrasecentral.htm

• Brent says:

Great idea, but not for me.

• Simon says:

One thing that the web has shown is how easy it is to do maths, physics and cosmology: amateur mathematicians knock off proofs of the Collatz conjecture; web pages routinely demonstrate flaws in General Relativity that professionals have missed, and these flaws are rarely of the subtle kind that arise in quantum-gravitational regimes. And the only serious work in cosmology is being done in amateur web forums.

Furthermore, most of the truly invaluable work in climate science, especially regarding anthropogenic global warming, has been done by lay “climate skeptics.” Thank goodness that alert members of the public were available to correct the horrific blunders in the IPCC reports!

Nor let us forget the superb work done (largely by the computer programmers, rather than biologists or geneticists) at the Institute for Creation Research and the Discovery Institute. Without these amateur contributions, we’d all still believe that the neo-Darwinian synthesis is a serious scientific theory!

I plan to back legislation that would allow anyone to apply for academic posts, fly an aeroplane, perform surgery or work as a structural or electrical engineer, regardless of their formal qualifications. In the particular case of academic positions, I can see no reason why blog posts should not replace (say) an honours or masters thesis.

The web has demonstrated that formal qualifications are an unnecessary impediment to lay-academics, lay-pilots, lay-surgeons and lay-engineers everywhere. Why should a lay-specialist be discriminated against, simply because they lack the (minimum) six-eight years of formal training that is currently required?

• Max says:

hahaha, +1 for the KFC joke (Killer PHrase Central) ! ;-D
And I’m sure even Brent will sooner or later use some of them (like #15 … ;-P !)

• ogerard says:

Hans says
arrogant from the start to the beginning.

So that’s “arrogant in only one point” !

More seriously, the Collatz conjecture is not only easy to state, it is easy to explore with most programming languages and it has been popularized widely, notably by Martin Gardner and A. Dewdney, several decades ago, then by many others.

3. Ingo Althoefer says:

> He builds a tree by inverting a certain function (not the Collatz function
> but a closely related one), and the whole argument rests on the fact that
> this tree contains every natural number — which he states but does not
> prove! And it seems clear to me that proving this would be no easier
> than proving the Collatz conjecture itself.

Is there a “simple” way to describe the construction of the “Opfer tree”?

• Brent says:

Yes, you can find a description here.

4. Martini says:

Nr 8 of Aaronson’s list is also met: Opfer takes time for trivial things.

- examples for Collatz sequences are given, with starting values 1, 2 and 7

- Theorem 2.1 is very simple. It should be called a lemma only. It seems strange that the first proven fact in a milestone work is called theorem, and is so very simple.

- in Lemma 2.2 he proves that the kernel of a linear map is a vector space. A real milestone.

- why these 18 pages of senseless tables of numbers in the end of the paper, without really explaining why they are important? I mean, such a list gives no real information.

• Brent says:

Yes, good point.

• Max says:

also some mixed-up notations about sets {4,2,1} and sequences (4,2,1,4,2,1,….).
Well, I admit that other authors use {…} to denote sequences (bad idea IMO, when not strictly monotonic), but if this is the author’s choice I can’t see why some end in {…4,2,1} and some in {…,4,2,1,…}.

5. Hamburger says:

I might clear up one of Martini’s points:

Often when papers are published within Germany, a “Satz” (theorem) is about something new to the paper, while a “Lemma” will be a (more or less direct) result of previously proven points.

Thus. the first proven point will regularily be a “Satz” although most often it will be a comparatively small preparation point, while the main topic of the paper will often be reduced to “Lemma” status, regardless of importance, since it directly follows from 4.7 in conjecture with 5.4 and 5.5 or suchlike.

• Martini says:

I have never seen anybody from any nation calling the main point in a paper a “lemma”, and the first thing to prove a “theorem”, only because it is the first thing that is proved.

• vonjd- says:

The usage is the same in German and English – a this paper is written in English anyway.

The problem is a general one in math: there is much confusion what a lemma is and what a theorem – in part because the import of something only becomes clear afterwards (think e.g. of Ito’s lemma).

6. I’m also intrigued by this; you’re obviously right.
It is clear that there is an equivalence between the Collatz theorem and this: ‘Every natural number can be formed by starting at 1, multiply it by 2 or if it’s minus 1 divisible by 3, you can add both this number and the multiplication by 2 to the list. In this way you can form any natural number’.

Formulated like that, it feels a natural candidate as an ‘unprovable’ statement -> Godel-incompleteness.

Have there been efforts to prove the fact that the Collatz theorem is not provable?

• herojoker says:
• Will Orrick says:

@herojoker: That preprint does not contain a proof of undecidability.

@Jasper: As mentioned in DS’s comment above, Conway has found some Collatz-like problems that are undecidable, but Collatz itself is not known to be undecidable. Both the MathWorld and Wikipedia pages on Collatz contain references to Conway’s paper and to more recent work along similar lines.

7. Edward Kmett says:

Jasper, yes, there have even been published “proofs” of its unprovability such as

http://arxiv.org/abs/math/0312309

8. Gottfried Helms says:

I cannot contribute some reasonable argument although I’ve tried to understand Opfer’s article; but I had some sceptic feeling for which you provided now more concrete words (#6 and #10). So “having” nothing on my own it seems, that at least my mathematical instincts are not completely off… at least: likely. Good to know…

9. Hans Wurst says:

You really should watch your arrogant tone. The man who drafted the paper is a reputable mathematician who was a student of Collatz, and not just some PhD student looking for attention. There may be flaws in the suggested proof, which is exactly why such papers are submitted for peer review.

10. Quaruk says:

@ Hamburger: that’s not right, the words “Lemma” and “Theorem” (Satz) are used in Germany as they are used everywhere else in the world. I’m a mathematician here.

• ASD says:

@Hamburger: You confuse Lemma and Corollary.

• vonjd says:

Lemma=Lemma
Theorem=Theorem or Satz
Corrolary=Korrolar

So basically its the same in German and English (being a Germanic language)

• JCarlos says:

• Thomas says:

Well, I think the german word “Satz” is a little bit weaker than “Theorem”. Therefore some german authors also use “Theorem” as a german word. Satz is maybe more like “Proposition” sometimes…

11. Pingback: Anonymous

12. DS says:

The paper by Opfer might possibly also satisfy Aaronson’s criterion number 3: the same methods imply an impossibly stronger theorem. In the case of the Collatz problem, several notorious generalizations have been discussed: the 5n+1 problem (or in fact, the An+1 problem) where A is any odd integer greater than 3. In this case, the heuristics predict that there are integers that interate off to infinity (not proven though), and it’s not clear to me how the given approach distinguishes this from the 3n+1 problem. A further generalization has been proposed by Conway that is algorithmically undecidable, and again one wonders how the approach would distinguish such problems from the one it proposes to prove. The more general a result, the more it is in danger to be false!

13. Pingback: Top Posts — WordPress.com

14. Fernando says:

It seems nowadays that it is not enough to find a problem in someone’s proof, there must be the subsequent ritual of humiliation of the author of the proof. Some blog posts about attempts at difficult problems (like the not-so-recent one about P and NP, that attracted much attention), and some of the comments left by readers just disgust me.

Why not write a big sign: “I wrote a wrong proof of Collatz’s conjecture”, and force the guy to carry it through his home town? I imagine that would be enough then. Nobody who breaks some of Scott Aaronson’s rules on how to write a breatkthrough paper should be spared public humiliation, I think!

• S says:

There’s a difference between “I broke a couple of guidelines for the format of writing up a proof formally” (if you actually read Brent’s post, you’ll see that he’s actually surprised how few of Aaronson’s rules were broken, and attacks the proof instead based on it, you know, not actually being a proof) and “My attempted proof is completely nonsensical and relies on asserting the main point without proof, and I threw it out for the world to see claiming that I was the only one clever enough to see this brilliant solution”.

I’m also not seeing the excessive humiliation that you claim is present – if you throw a proof out there and your proof fundamentally doesn’t work, people will say, “Hey, this proof doesn’t work”. That’s kind of how things are supposed to work. In fact, that’s the whole basis of peer review.

And no, the proof in the paper isn’t just a mostly valid proof that needs a bit of peer review to plug a couple of minor errors and make it perfect. It just rephrases the problem and then asserts that the conjecture is true in the new phrasing without proving this – in other words, it doesn’t make any noteworthy progress whatsoever.

• C says:

Hey S!

“There’s a difference between (blablabla) and (blablabla).” (cit. “S”)

and

“I’m also not seeing the excessive humiliation that you claim is present – if you throw a proof out there and your proof fundamentally doesn’t work, people will say, “Hey, this proof doesn’t work”. That’s kind of how things are supposed to work. In fact, that’s the whole basis of peer review.” (cit. “S”)

Just to stick with your way of argumentation: There’s also a difference between saying “Hey, this proof doesn’t work” (citated from “S”) and saying “it constantly attracts tons of would-be solvers, and most of the purported “proofs” they generate are not even worth mathematicians’ time to look at. So why should this one be different?” (citated from Brent). BTW, to answer the question: This one COULD be different, because it’s done by a mathematician (additionally, this is probably why Brent actually DID look at it).

I didn’t read the original paper, I am not even a mathematician (not even as a hobby), and the paper might actually be utter rubbish. Still (just from a very personal and non-scientific point of view, and just in case it interests you): Brent (and similar also “S”), if you have ever asked yourself the question (which I am sure you didn’t) why the ordinary mortal (i.e. the non-mathematician) tends to sometimes view mathematicians as a non-social nerds… Now you know why (in case you don’t: because of texts like Brents above).

Did you ever read “Fermats last Theorem” by Simon Singh? Very readable, but it depicts mathematicians as very social people, who sit together during teatime and very openly discuss mathematical problems (which I have to admit A. Wiles did NOT do, although probably just because the matter is SO complex, that no-one could’ve helped him anyway and would instead just have distracted him). I REALLY hope(d) reality is this way, and that Brent is the dropout.
Also: Thanks Fernando and “Hans Wurst” and others for helping me keep up my romantic image of the mathematical community.
Oh, and don’t bother to reply, I will certainly never return to this page (considering that Brent is probably not going to miss me, since I cannot follow Andrew Wiles’ proof for Fermats last Theorem).

Nerd-on, just as you like.

15. none says:

The 3n+1 problem cannot be PROVABLY undecidable, since if it’s undecidable, then it is TRUE. Of course you might be able to prove that 3n+1 is undecidable in some theory T, but the proof would be carried out in another theory T2, and you’ll have also proved (in T2) that the conjecture is true in all models of T2.

If it helps understand the situation, the person who wrote that “undecidability” proof also has released a number of proofs that P=NP (or maybe it was P!=NP) and other such important theorems.

• mathstribble says:

I am intrigued by this. Why should this be the case? Clearly if there is another cycle, then this is provable, but what about sequences that simply run to infinity? Is it not a priori conceivable that there exists a number n for which it is not provable that the sequence starting with n converges to infinity? (I am fairly ignorant about work on Collatz beyond its definition, so forgive me if there is some nontrivial mathematics here I am not aware of.)

Perhaps I also misunderstand your post, since “undecidable” usually means algorithmically undecidable in the usage I am familiar with, but I assume you mean “independent of some standard set of axioms such as ZFC”.

16. Frerich Raabe says:

Your blog article (as well as a few comments to it) has been mentioned in an article of the online flavor of the popular german “Spiegel” magazine: http://www.spiegel.de/wissenschaft/mensch/0,1518,768289,00.html

17. Ingo Althoefer says:

News.

When you look at page 2 of Opfer’s preprint, you find an
http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf