APA Blogging: Rabin

28 12 2005

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).




2 responses

5 01 2006

One would also need to think more carefully about the notion of “transfer” of a classical mathematical proof, before applying it to such probabilistic proofs. In reality, a mathematician A who discovers (or creates) a proof for some claim does not simply transfer it to another mathematician B. Rather, person B attempts to reproduce the proof in his/her own mind, sometimes step by tiny step, and only when B is completely satisfied that he/she understands all the steps AND agrees with all of them, that the proof can be said to be transferred.

There are many anecdotes about mathematicians failing to convince others of particular steps (subsidiary claims) in a proof, and thus failing to convince them that the overall claim is true. Sometimes (as with Wiles’ Proof of the Wiles-Fermat Theorem), this leads mathematician A back to the drawing board, aiming to fill in the missing steps, which he/she eventually does. Sometimes, mathematician A cannot do this, and the proof fails to convince B. B, and other mathematicians, may accept the proof nonetheless, may reject it, or may themselves look to fill the missing steps.

In other words, I don’t accept that there is some simple process of “transfer” of mathematical proofs. The process of inter-subjective agreement between mathematicians over claims and their proofs is much closer to the notion of reproduction of scientific experiments that you mention than it is to a handover of anything.

5 01 2006

I suppose that’s true – for a lot of the reasons mentioned by Fallis in my earlier post on incomplete proofs, it seems that people don’t just receive proofs as complete objects. There are almost always many gaps to fill in, and they may not even be filled in in the same way by different mathematicians.

But there’s still a relevant difference it seems, even if the standard case isn’t as close to actual transfer as Rabin seemed to suggest. Proofs are generally complete enough that an expert in the relevant field can very quickly verify each of the steps, whether this is just following along, using a standard justification for a common claim, or making a slightly clever use of a standard method. However, these steps are equally convincing whether one comes up with them oneself, or reads them in print.

With randomness it’s different – no matter how detailed the written account, the proof is no good unless one believes the numbers involved were generated randomly. One can accept every step in the proofs that they aren’t witnesses and yet doubt their randomness. To fill in this gap oneself, one would have to essentially generate the whole proof from scratch, and not just a few steps. One has to generate numbers randomly, and then do all the same calculations for these numbers, unless a couple of them happen to be included in the author’s set.

This seems to be a difference of degree that might result in a difference of kind. In the standard case, a more complete than usual proof requires a smaller percentage of reverification on the part of the reader. With the randomized proof, there’s no way to bring the amount needed to be reproduced below the whole length of the proof.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: