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 
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!)
The Math Less Traveled 
Pingback: Conjectura lui Collatz | Isarlâk
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.
I’m sorry if it came off sounding arrogant, but it is simply the truth.
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
Great idea, but not for me. 😉
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?
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 !)
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.
> 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”?
Yes, you can find a description here.
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.
Yes, good point.
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,…}.
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.
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.
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).
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?
@Jasper: See http://arxiv.org/abs/math/0312309
@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.
Jasper, yes, there have even been published “proofs” of its unprovability such as
http://arxiv.org/abs/math/0312309
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… 🙂
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.
Pingback: Collatz-Vermutung vermutlich bewiesen
@ 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.
@Hamburger: You confuse Lemma and Corollary.
Lemma=Lemma
Theorem=Theorem or Satz
Corrolary=Korrolar
So basically its the same in German and English (being a Germanic language)
For the sake of “mathematical precision” (I’m afraid this is almost a pleonasm) please note or remember that in an international community – thinking and reasoning as it is in different mother tongues – confusion will readily ensue without adequate linguistic means of communication. For this reason, European academics used Latin (remember also that learning institutions were in the hands of the churches), from which the words quoted are – both in English and German – almost transliterations… and certainly non-Germanic! This point deserves stressing, since sharing a foreign language will at times imply a common adaptation of an originally different pattern of thought – a ‘feature’ usually welcomed by professional mathematicians, interested as they are in received standards of proof (though the criterion is obviously only necessary, not sufficient). In this frame of mind, I personally find that remembering the original (foreign) meanings of these words helps me keeping confusion at bay: the traditional “theorem”/”Theorem” comes to us from Greek (over Latin), meaning “matter of study/inquiry” in both Greek and Latin; “lemma”/”Lemma” comes from Greek (“proposition”) through Latin (there meaning “issue, subject, matter”); finally, “corollary”/”Korollar” comes from Latin (“little crown”, ‘crownlet’). I find the latter an especially helpful (and sweet) description of the originally intended function and position of a “lemma”/”Korollar” within a mathematical chain of reasoning. Of course, both the English and the German scientific/technological terminology originates (mostly) from Latin/Greek contexts, which according to certain estimates makes up an estimated 70 to 80% of the total vocabulary of modern English (you will find that even the sentence structure of modern English is decidedly Latin/French-oriented, not to mention the loss of inflexion – s. cases and conjugation patterns). Thinking ‘Germanic’ instead of Latin/French I often find rather detrimental to the ease of ‘navigation’ within the scientific and technological lingua franca that English(= the modern Vulgar Latin with Germanic loan words?) has become – an example from programming: the confusion arising from the German translation of the object-oriented terms “instantiate” and “instance” – “an “Instanz” is an “institution”, an (often governmental) “authority”, the last thing that comes up in your mind is an “example”… Could the confusion around Satz/theorem etc have originated within this context?
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…
Pingback: Anonymous
Pingback: Beweis(?) für das Collatz-Problem vorgelegt - Seite 2 - inQuake Forum
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!
Pingback: Top Posts — WordPress.com
Pingback: News on proving the Collatz Conjecture | MathBlog
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!
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.
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.
Pingback: Collatz conjecture: an apology | The Math Less Traveled
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.
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”.
Pingback: Wurde die Collatz Vermutung bewiesen? | The Hidden Engine Blog
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
Pingback: Zahlenrätsel: Mathematiker zweifeln am Beweis der Collatz-Vermutung | IlNeurone
News.
When you look at page 2 of Opfer’s preprint, you find an
addendum, added on June 17, 2011:
Click to access hbam2011-09.pdf
The text of the addendum reads:
> Author’s note:
> The reasoning on p. 11, that \The set of all vertices (2n; l) in all levels will
> contain all even numbers 2n 6 exactly once.” has turned out to be incomplete.
> Thus, the statement \that the Collatz conjecture is true” has to be withdrawn,
> at least temporarily.
> June 17, 2011
Congratulations to all those who had pointed just on this step
in Opfer’s try for a proof.
Ingo Althoefer.