Proving A Proof Is A Proof
How to convince someone your proof is really a proof
Roger Apéry was a mathematician who solved a beautiful problem that had been open for hundreds of years. He was not an amateur in any sense, but because his result was so surprising there was initial doubt about its correctness. Even professional mathematicians have some of the same problems that amateurs do.
Today I want to talk about how to know if your proof is a proof. And further how to convince others your proof is a proof. I have no magic single insight, but I have a few suggestions that I find useful, perhaps you will too.
Apéry proved that is irrational. In general
is the value of the famous “zeta” function at . Leonhard Euler found a closed form for for any integer . This expression shows that for all integers , the value of is irrational—actually it is a transcendental number. For example,
Before Apéry ‘s work the status of was unknown. Then in June 1978 he gave a talk, during which he presented a proof that was indeed an irrational number.
Ron Graham told me a story about the talk. It seems likely Apéry had a proof, but his presentation style and some of his comments—jokes?—did not make the audience feel confident in his claim.
Apéry ‘s proof depended on the following identity
At the time no one had seen such an identity. It was new. And it seemed magical—even the factor is strange. Apparently someone in the audience asked Apéry how did he find this identity? Apéry answered,
They grow in my garden.
You can imagine the effect such a comment might have on a group of skeptical mathematicians. If he had said:
The identity follows by using shifted Legendre polynomials. I can prove that all
It would have been okay. But “they grow in my garden” caused, according to Ron, many to start to leave the talk. However, someone in the back of the room had a programmable HP calculator, and quickly wrote a tiny program to check the identity. They interrupted the talk and said that the identity checked to the allowed accuracy of the calculator. Ron says this got everyone’s attention, and people sat back down and listened to the rest of Apéry ‘s talk.
In the years after the talk other mathematicians found proofs that were based on Apéry ‘s work. They were done and explained in a more conventional manner, and is indeed irrational. See this for more discussion on the state of further work.
I have a small collection of suggestions on how to know your proof is a proof. The same suggestions can be used to convince others, so I will concentrate on convincing yourself. In my opinion the last way to convince yourself or anyone else is to use formal methods. I have seen some comments in our discussions on using this or that formal system. I think that they have a role in mathematics, but not in the checking of a new result. See this for my thoughts on this topic: it’s an old paper with Rich DeMillo and Alan Perlis on the nature of proof.
Calculate: Many of the great mathematicians were tireless calculators. Euler, Carl Gauss, Bernhard Riemann, and many others did extensive calculations of all kinds. It is even more remarkable they did this, when they did not even have calculators—let alone computers. Trying small examples, checking identities to high precision, and building tables is one of ways to get a feel for the problem at hand.
I am suggesting that this be used to check some of your “lemmas” and claims. This approach does require a caution. Nature, especially in number theory, often will not reveal her secrets in small cases. I have already discussed a classic theorem of John Littlewood that showed that calculations can be misleading. But calculations can disprove a claim, even if they cannot prove a claim.
I have more than once thought that a false X was true and tried to prove it. In one case, after trying quite a while to prove such an X, I asked Philippe Flajolet for help. Philippe is a world expert on such problems. He used a combination of a technical insight I did not know and Maple to show why I could not prove X. The simple difficulty was there is a counter-example to X.
Check Concrete Cases: A related idea to calculation is to check all lemmas and claims in small cases. For example, suppose you have “proved”
Lemma: For each integer , the Euclidean space has the red property.
I would suggest you check that and actually have this property. If you can show that the line and the plane have the red property, that will help. Even better is if your argument in these special cases is different from the general argument used to prove the lemma.
I have discussed before work I did on the Vector Addition Problem. One false claimed proof that the problem was decidable had a lemma like the above. The lemma stated some property of Euclidean space . The difficulty was that the property failed even for the one-dimensional case. My geometric intuition is terrible, but the authors should have checked that their lemma at least worked on the line. It did not—there was a simple counter-example.
Watch Case Arguments: The easiest error to make in any proof is to forget a case. This is especially true when there are many cases, or when the cases have sub-cases and so on. In geometry, for example, there are great paradoxes based on “proofs” that leave out a case.
A related issue is check any argument that handles a case X by saying: “the proof follows in the same way as case Y.” This is type of argument often relies on a symmetry between X and Y. But if the symmetry is missing, then X has not been proved. This happened years ago in a claimed proof that SAT needed super-polynomial size circuits. The claim was made by a world expert, and the bug was exactly of this type.
Know The Obstacles: If you have proved something that others could not, you should know the barriers they faced. Further you should be prepared to explain how you overcame those barriers.
Imagine if Grigori Perelman had claimed the Poincaré Conjecture based on the Ricci Flow methods of Richard Hamilton. Yet when asked how he handled the “cigar” singularity suppose he had said,
the what singularity?
That would have raised lots of doubt about Perelman’s work. If you solve a problem, even a much more modest problem than Poincaré, you should know the difficulties that others have faced. And be prepared to explain how you overcame them, went around them, or through them—in general how you avoided them.
What is Your New Idea? I have discussed this before here. I believe that anyone who solves an open problem needs to have some new idea. An idea that was missed by previous researchers. The idea can be small, but it is essential.
If someone says here is how I proved the Riemann Hypothesis: “it is a careful induction ” I wil be pretty pessimistic. If instead they say:
Say a set of complex numbers is a -set if it can be covered by lines. I eventually show that the zeroes of the zeta function are a set. First I show they are a -set for some finite . I noticed if this was false, then by
This sounds like it has a new idea, and while I need to see the details, I will listen. Even if the proof fails, there is some chance that the new ideas could be useful in solving other problems.
Don’t Prove Too Much: This is one of my favorite tools when I am searching for a proof. I have not heard it discussed before, but perhaps it is known.
Suppose I am trying to prove some statement X. I may see an outline that looks like it will eventually lead to a proof of X. Often there are lots of details that have to be checked and lots of work to be done. However, sometimes I can see that if my method can prove X it could also prove another statement Y. This is a kind of “meta” argument, but I often find if a method proves X it will prove a related Y.
The key is then what is Y? If the statement Y is known to be false, then my method must fail. In this case I have avoided a great deal of work, and can use my time to refine my approach to X. If the statement Y is open, but considered likely to be false, then I may still continue. But now I am much more careful.
Another possibility is that the statement Y is a major open problem. Of course if my method will work this is great news, but usually I view it as showing my method is suspect. This does not make me abandon my approach; it does again make me very careful about each step. Almost always I find that I have a hidden issue in my approach in this situation.
Explain It to Others: One way to see if your argument is reasonable is to try to explain it to others. The best situation is to try to do this to an interested and expert audience. This is not always possible. I have found, however, that even explaining your ideas to non-experts is quite useful. More than once in the middle of a detailed explanation of a “proof” I realized the “bug” myself. I think forcing one to say all the details forces you to see all the nooks and crannies where your proof could go wrong. It is a bit like reading text out loud to better proof-read it.
Work With Others: Yes Perelman worked alone. But even Andrew Wiles needed the help of Richard Taylor to finish his great proof of Fermat’s Last Theorem. Wiles rightly deserves the credit, but there are two papers that were needed to resolve this famous problem.
Most of the false claims of famous open problems—I believe—have been single authored papers. Perhaps that is a lesson for us all.
Harry S. Truman once said:
It’s amazing what you can accomplish if you do not care who gets the credit.
Did these suggestions help? Do you have some additional ideas to help check proofs?