FOM: Probabilistic proofs

[Harvey Friedman]

This concerns the Fallis/Shipman thread.

I think this discussion of what does or does not count as "proofs" should
more deeply take into account what has actually transpired in the
mathematical literature.

I am not that familiar with this situation, and would like to raise some
questions and make some guesses.

1. What cases have occurred in the mathematical literature where an
interesting mathematical result has first (and perhaps only) appeared
documented by a probabilistic proof? Of course, one has, e.g., that some
specific large integer is prime, and the like. But that is not really an
interesting mathematical result, and normally is not in a mathematics
Journal (which may or may not be an interesting distinction).

2. In any case, consider such a mathematical result, interesting or not,
that has appeared in a scientific or engineering Journal. E.g., that a big
integer is prime. Won't it be the case that the documentation cited will be
its probabilistic proof, generally identified in some clear way so that it
is reproducible? Won't you never see "it has been proved that n is prime"?

3. So I am suggesting that probabilistic proofs and normal proofs are
clearly identified as such, and so the issue of whether probabilistic
proofs are in fact proofs is somehow never joined?

4. Obviously, if what I am suggesting is right, probabilistic proofs are
given some status far beyond "it appears likely that n is prime..." or
"there is evidence that n is prime" or "I think that n is prime" or
"prevailing opinion is that n is prime."

5. Also, obviously, if what I am suggesting is right, normal proofs are
given some distinguished status. The question may be: is the distinguished
status of normal proofs "beyond" or "higher" than that of probabilistic
proofs? It seems that maybe the literature is a little bit ambiguous on
this point. There is no question that the "proof" has to be labeled
"probabilistic" if it is, or else the referree and/or editor will demand a
change before publication.

6. Perhaps light can be shed on this matter when there is a probabilistic
proof and a normal proof. Which "proof" would normally be given? Or both?
Or what effort goes into replacing a probabilistic proof with a normal
proof, or vice versa? What kind of contribution is that considered to be?

7. It is difficult to understand what is happening with question 6 unless
there are sufficient examples of 1 to examine.

8. It is my own view that these probabilistic proofs have a certain kind of
underlying rigor - "even if their actual implementation is imperfect." This
phrase in quotes is a fancy way of saying, e.g., that we don't have perfect
random number generators, and in fact don't even know - or cannot even
define - what a perfect random number generator is. (Kolmogorov's
definition is so strong that one knows that one cannot prove that any
particular sequence is random). Or perhaps I am wrong - somebody does know
what a perfect random number generator is? But also that for the foreeable
future, people will not be able to pass these off as "proofs" in the actual
literature without calling them "probabilistic proofs."

9. Thus there remains the question of "what is a "correct" or "valid"
probabilistic proof?" Is that the real fruitful issue at the heart of this
thread?