What are some mathematical proofs which appear to be correct, but are actually incorrect?
The most fiendish false proofs are not proofs of incorrect assertions. They are faulty proofs of correct assertions.
When someone offers a proof of an incorrect assertion, you know that at some point in their chain of reasoning they must say something that’s wrong. Find that something, and you’ll see immediately where the proof fails.
But when someone “proves”, incorrectly, a correct statement, demonstrating the incorrectness of the proof can be anywhere from easy to extremely hard. The assertions made in the steps of the proof may, for all we know, all be correct: it’s the implications that are broken.
When students learn the idea of proofs, this is a point well worth emphasizing, and one of the tools is the study of incorrect proofs. It’s not used often enough, and that’s a shame. There’s much to be learned.
Here are some of the best examples I know.
The first example is a faulty proof by none other than Srinivasa Ramanujan. Now, granted, rigor in proofs was never Ramanujan’s forte; his breakthroughs were almost universally discoveries and conjectures, not proofs, which were supplied by others (sometimes decades after his death). But it’s interesting to study this case because this proof, or variations of it, still show up all the time.
In 1911, Ramanujan published the following problem in the Journal of the Indian Mathematical Society: Evaluate the nested radicals
\displaystyle \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}}
\displaystyle \sqrt{6+2\sqrt{7+3\sqrt{8+4\sqrt{\cdots}}}}
The practice of publishing problems and asking for solutions by readers is still common, and when no solutions are offered the proposer is often expected to submit their own. Ramanujan published 58 such problems between 1911 and 1919, many of which are deep and fascinating. A wonderful survey of these problems is in this paper[1] by Berndt, Choi and Kang.
Ramanujan’s own solution of these nested radicals runs as follows (we’ll do the first one; the other one is similar). Observe that
\displaystyle n+2 = \sqrt{1+(n+1)(n+3)}
Consequently, if we define f(n)=n(n+2) then
\displaystyle f(n) = n\sqrt{1+f(n+1)}
but then the same formula can be applied to the inner f(n+1), yielding
\displaystyle f(n) = n\sqrt{1+(n+1)\sqrt{1+f(n+2)}}
and this can be repeated indefinitely, yielding an infinite nested radical. Finally, setting n=1 yields
\displaystyle f(1) = \sqrt{1+2\sqrt{1+3\sqrt{\cdots}}}
which is the desired nested radical, and of course f(1)=3, so the answer is 3.
This seems both clever and convincing, but it’s incorrect – or at least, incomplete. Here’s the problem: we’ve managed to find one particular expression which, when repeatedly expanded, yields a sequence of nested radicals which approaches the desired one. But what if someone finds some other particular expression which also produces the same infinite nested radical, but with a different value?
Indeed, this can actually be done. For example:
4 = \sqrt{1+2(15/2)} = \sqrt{1+2\sqrt{1+3(221/12)}}=\ldots
this can also be pushed further indefinitely, and it seems to say that the value of the same nested radical is 4! (I stole this example from Herschfeld’s paper “On Infinite Radicals[2]”).
Which is it then?
The situation may remind you of similar traps which come up with other infinite expressions. For example, when evaluating
\displaystyle x = \sqrt{2}^{\sqrt{2}^{\sqrt{2}^\cdots}}
people often say that clearly x = \sqrt{2}^x, and this is satisfied by x=2 so the answer is 2. But the problem is that x=\sqrt{2}^x is also satisfied by x=4, so which is it?
Part of the problem, of course, is that we need to carefully define what those infinite expressions even mean. This is typically done by declaring them to be limits of finite prefixes of themselves. Then, to evaluate them, we need to first prove that the limit exists, and then determine its value.
Sometimes pinpointing the value can be done by studying fixed points of the iteration, as is the case with the infinite tower of \sqrt{2}'s. Ramanujan’s radical is more subtle since the iteration keeps changing. A complete and correct proof that the value is indeed 3 can be found in Herschfeld’s paper, and I think there’s also a question about this on Quora.
The Cayley-Hamilton theorem (in its matrix formulation) states that if A is a square matrix (over some field) and p_A(t)=\det(A-It) is its characteristic polynomial then p_A(A)=0.
This is not a terribly difficult theorem, but it’s not quite straightforward either. Most courses on linear algebra present one of the correct proofs, and the students move on.
However, few teachers pause to show the following incorrect argument: we want to show that p_A(A)=0. Well, what’s p_A(t)? Why, it is \det(A-It) where I is the identity matrix of the appropriate size. Ok, so what’s p_A(A)? Obviously, it is \det(A-IA) = \det(A-A)=0. Done, QED.
Here’s the thing: if any teacher actually walked their class through this “argument”, with a poker face and a confident attitude, I guarantee you nobody would raise their hand to protest. It seems clear, easy, obvious and straightforward. Doesn’t it? And furthermore, what it proves is actually true, so nobody can find a counterexample. This is most definitely a proof which “appears to be correct”.
It’s a really good exercise to ponder this “argument” and see why it fails. There’s actually a relatively easy howler here, created by our poor notation.
Ask yourself, what is “0"?
Wait, what do you mean “what is 0"? Seems like a silly question. Well, look again at the statement p_A(A)=0. A careful teacher would write p_A(A) = \mathbf{0}, a bold zero denoting the zero matrix. Indeed, what the Cayley-Hamilton theorem says it that if you calculate c_0I+c_1A+c_2A^2+\ldots+c_nA^n where c_i are the coefficients of the characteristic polynomial, then you get the zero matrix. You get a matrix, not a number.
On the other hand, our “proof” ended with \det(A-A)=0, the number zero. The number zero is not the matrix zero. Our “proof”, whatever it shows, only concludes that a certain number is zero. This isn’t what the theorem says.
Whenever I teach the C-H theorem to anyone I make a point of showing this silly non-proof. It’s actually not silly. It stresses the meaning of the theorem and lets students see how misleading proofs can be if we don’t pay careful attention.
Famously, in 1879, Alfred Kempe published a proof of the 4-color theorem using the (very clever) idea of flipping colors along what are now known as Kempe Chains. The proof stood and was accepted for 11 years before Heawood found a critical error, in 1890.
Briefly, the proof runs as follows. Assume that the 4-color-theorem is false, and pick a minimal counterexample: a planar graph which is not 4-colorable. We may assume that the graph is that of a triangulation, and using Euler’s formula we show that the graph must contain a vertex v of degree \le 5. If we remove vertex v (and its incident edges), the leftover graph can be colored with 4 colors, since we picked a minimal counterexample. Our goal is to show that we can still use just 4 colors even if we put that vertex back.
If v has degree 3 or less, that’s obvious: at worst, three colors are unavailable for our vertex, so we can use a fourth one.
If v has degree 4, we may assume that the coloring of the leftover graph uses all four colors for its neighbors, let’s say Blue, Red, Green and Yellow as you walk around the vertex. Put yourself at the Blue vertex and attempt to walk all the way to the Green one only using Blue/Green vertices. Either you can or you can’t.
If you can’t, good news: flip all the colors along your walk from Blue to Green. Now our vertex sees only Red, Yellow and two Greens, so it can be colored Blue.
If you can complete the walk, the flipping doesn’t help, of course, because the Green became Blue but the Blue became Green. But now repeat the argument with the Red-Yellow vertices. It’s impossible for two closed loops to form, one Blue-Green and the other Red-Yellow, because planar graphs can’t have two such non-intersecting loops. This proves the reduction for the degree-4 case.
Everything up to this point is perfectly valid.
Kempe then moved on to repeat the argument for degree 5, which is where he subtly tripped up. He considered a coloring around v going R-B-R-G-Y, and worked with similar chains as before. If both the R vertices are surrounded by blocking chains, he attempted to create a R-G chain and a R-Y chain and simultaneously flip them; but this can’t work because the flips may clash with each other.
The error is subtle, but the proof is unfixable. It took over 80 years to produce a correct proof of 4CT, relying on extensive computer calculations. The basic logical structure of the proof can be traced back to Kempe’s original idea: we work with minimal counterexamples and “unavoidable configurations”, which for Kempe were simply vertices of degree at most 5, and we show that they can be “reduced”, meaning they can always be recolored with fewer colors. But the details of the eventual proof were much more complicated than Kempe believed.
Finally, let’s recall that “proofs which appear to be correct” can be extremely serious and difficult affairs.
In 1993, Andrew Wiles had a proof of Fermat’s Last Theorem which he was completely confident in. He is a very, very careful mathematician, and quite shy; “coming out” with such a sensational proof was a difficult step, but he did it because he knew he had it. He presented the proof in a series of lectures, and submitted a full write-up for publication.
Nick Katz[3] began the monumental task of reviewing Wiles’ paper. Few people were even capable of doing that, but Katz had both the immense knowledge and the meticulous nature required to comprehend and check everything very, very carefully. He wrote to Wiles whenever something was unclear, and Wiles always responded with clarifications. Until that one time when he couldn’t. They discussed the point back and forth over weeks, and it became clear that there was a problem, and it was not a trifle, and then it became deep, and then it became an irreversible flaw that demolished the entire proof.
It wasn’t even directly something in Wiles’ proof, as far as my understanding goes: it was an issue with a construction by Flach[4], then a young researcher, now himself a renowned mathematician at Caltech (we should hold none of that against him – these things happen). Wiles had to go back to the proverbial drawing board, now under immense pressure knowing that his edifice is out and the whole world is chasing the elusive proof. It was a terrible time.
Eventually, he made a dramatic breakthrough: the very thing that blocked Flach’s construction from working turned out to resurrect a completely different approach to the proof which Wiles abandoned years earlier. He rebuilt the whole thing, recruiting Richard Taylor for a difficult ring-theoretic argument, and successfully published a complete and correct proof in 1995.
His 1993 proof certainly “appeared to be correct” to his audience and the first round of readers, and most of all, to himself. It was incorrect, but from its ashes emerged the correct proof, one of the greatest mathematical breakthroughs of the 20th century.
Footnotes
[1] The Problems Submitted by Ramanujan to the Journal of the Indian Mathematical Society