Michael Rabin started his talk by mentioning that the traditional picture of proof says that in principle a proof is formalizable, can be verified in an automated way, is reproducible, publishable, and can be transferred (that is, if I have a proof, then I can give it to you and then you will have a proof). In practice, this isn’t entirely correct, because actual proofs are rarely formalized, and are normally checked by a social process rather than an automated one. Apparently there have been case studies showing that even restricting attention to the Hilbert problems, a large number of results have been “proven” once, and then years later reproven in a way showing that the initial proof was incorrect.
He argued that with the rise of new methods of proof (some of which I discussed earlier), there are even more differences – now, there can be proofs that are non-transferrable and non-publishable.
The basic idea is as mentioned in my earlier post – to probabilistically prove that a certain number n is prime, randomly generate 100 integers less than it, and show that none are witnesses to compositeness. If n is composite, then more than 3/4 of the integers less than it are witnesses to compositeness, so this procedure has a false positive rate of less than 1/4100, which is negligible compared to the chance that one is only hallucinating the act of proving, rather than actually doing it.
However, to trust this result, one must trust that the integers were chosen randomly and independently – thus, such a proof is not transferrable. If I carry out such a proof and convince myself that n is prime, and then show my calculations to you, then you can be justly skeptical and wonder if I just chose my (seemingly random) 100 numbers in a clever way. After all, if n is much greater than 400, then I will generally be able to do this.
[To clarify a point that people brought up last time I discussed this issue, note that the process involved here is in fact a (not completely infallible) method of proof of primality, and not a (completely infallible) proof of some related fact. The idea can’t be that we have given a deductive proof that n is probably prime – because either n is or isn’t prime, there’s no probability about that. And to myself I’ve done something more than just prove that these 100 numbers aren’t witnesses – I’ve also shown that n is likely to be prime, because these numbers were chosen randomly. That is exactly the part of the proof that can’t be transferred, so in some public sense all I’ve done is proven that these particular numbers aren’t witnesses, but in some private sense I’ve convinced myself that n is prime.]
Rabin then went on to describe several other proofs that work in this way, in addition to probabilistic primality. There are probabilistic proofs of polynomial identities. In addition, there are interactive proofs and zero knowledge proofs and probabilistically checkable proofs, all of which allow one to convince someone else that you have a (correct) proof of some statement, without them having to check through your proof completely.
At the end I pointed out that this procedure guarantees a low conditional probability of a positive result, given that the correct result is negative (and a guarantee of a positive result if the correct result is positive). However, this doesn’t necessarily translate into a high posterior probability of the positive case. His response seemed to be that the number we are proving to be prime is not to be thought of as random, but rather as given – the randomness is only involved in the checking procedure. I’m not totally convinced by this response, but there may be something to it in cases where the number really is given by some external process.
Another question I would have liked to ask but didn’t get a chance was about whether such proofs really are non-transferable and non-publishable. When an experimental scientist publishes some result, she bases her claims on a lot of data. However, the data are useless unless they are actually given by the experimental process she describes. This is why scientists often try to reproduce surprising results produced by others. Similarly, if I probabilistically prove that some number is prime, the sequence of checks I give is no good unless they were really generated randomly. So other mathematicians should attempt to reproduce the results by also generating checks randomly and convincing themselves. So the readers of the journal can just trust that I carried out the procedure as I described (just as most readers do with journals of experimental science), and referees and very interested readers can try to reproduce the results themselves, and challenge me if it doesn’t work out right. Of course, in experimental science, data do occasionally get falsified, and it would be nice not to have that possibility in mathematics. But in many cases, we just can’t get any better than a probabilistic proof (just by virtue of the extremely limited number of deterministic proofs that are available to us, of any given length).