FOM: Probabilistic proofs

Joe Shipman shipman at
Tue Sep 22 17:33:22 EDT 1998

Stephen Cook wrote:

> An adversarial mathematician might study a previously published table of
> physically generated random bits and use it  to devise an input for which the
> probabilistic algorithm gives a wrong answer, and hence publish a "proof"
> of a false theorem.   This may not be possible in the case of Rabin's test,
> but should be quite possible in the case of Schwartz' test. (Find nonsingular
> matrix of polynomials which is singular for all integer values given by the
> random bits on the part of the table used.)

Anyone who did this would be exposed immediately because the referees, in addition
to testing the
previously published random bits, would come up with their own independent ones.
This sort of
misconduct is similar to faking computer trace in a computer-aided proof: -- it can
be done but
doesn't invalidate the process because it is readily detectable.

More information about the FOM mailing list