FOM: Friedman/Odlyzko

[Harvey Friedman]

Here is some brief correspondence between myself and Andrew Odlyzko.
*****

>Date: Mon, 21 Sep 1998 02:44:24 +0100
>To: Andrew Odlyzko <amo at research.att.com>
>From: Harvey Friedman <friedman at math.ohio-state.edu>
>Subject: probabilistic proofs

>...About probabilistic proofs. ... The issue of the rigor of probabilistic
>proofs often comes up. (See www.math.psu.edu/simpson/fom/index.html for
>info if you are interested).
>
>My quesiton is this. Is there a favorite example of a theorem that has
>been established using probabilistic reasoning but where there is no known
>conventional proof? E.g., some giant number is prime would do, but isn't
>really interesting, unless the actual number is really interesting.
>
>What about the frequency of twin primes among primes? Thus I assume that
>we have a probabilistic proof of this kind that with high probability the
>frequency of twin primes among primes < 10^100 is very low. But is this
>the sort of thing that we aren't able to give a standard proof of? If this
>is a decent example, then what is the best statement of it? I.e., what
>probability, what frequency, and 10^n for which n, should best be used to
>state this properly?

>Date: Thu, 8 Oct 1998 07:29:24 -0400 (EDT)
>From: Andrew Odlyzko <amo at research.att.com>
>To: friedman at math.ohio-state.edu
>Subject: Re: probabilistic proofs

>...As far as your
>question is concerned, I don't know of any serious theorem
>that has been established using probabilistic reasoning but
>where there is no known conventional proof.  Even in primality
>proving, deterministic proofs (some randomized, so we do not
>know a priori that they will work efficiently, but at the
>end we do get a rigorous proof) are not all that much slower
>than probabilistic ones, and so can be applied just about
>any time one cares about a result.
>
>Something with a similar flavor, but perhaps not quite what
>you were after, is the Riemann Hypothesis for Hawkins primes.
>Hawkins defined an interesting collection of sets of integers
>that mimic primes in many ways.  (Regular primes are one of
>those sets.)  It is known that most sets do satisfy the RH.
>Unfortunately this does not say anything about the ordinary
>RH.