From: bs@gauss.mitre.org (Robert D. Silverman)
Subject: Re: Mathematical intuition (was: New Mersenne Prime)
Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
Date: Wed, 1 Apr 1992 18:53:22 GMT

In article <michaelg.702072266@Xenon.Stanford.EDU> michaelg@Xenon.Stanford.EDU (Michael Greenwald) writes:
:petry@pythagoras.math.washington.edu (David Petry) writes:
:
:>Probabilistic arguments can give insight into a problem without giving
:>a rigorous proof.  
:
:>Here's a very crude probabilistic argument that suggests that there are
:>infinitely many Mersenne primes.
:
:>The prime number theorem says roughly that the probability that a number of
:>size N picked at random is a prime is 1/log(N).  Then, roughly, the 
:>probability that a Mersenne number 2^k - 1 is prime is 1/k (ignoring a factor
:>of 1/log(2) ).  So the expected number of Mersenne primes is Sum[1..inf] 1/k.
:>Of course, the harmonic series diverges.
 
Uh, you should be using only k prime here. 

:
:Unfortunately, I don't think this will convince the original poster.
:S/He asked about whether you can have mathematical intuition about
:unprovable assertions.  I don't think the probabilistic argument above
:will be very compelling to that person, since it depends upon the
:listener knowing a lot of >other< assumptions and conjectures,
:unstated here.  To see what I mean, just note that the same argument
:would work to argue that there are an infinite number of primes of the
:form 2^k, or 3^k - 1, but in fact we know there is precisely 1 in each
:of those cases.  A more reasonable example would be: the same argument
:would imply an infinite number of primes of the form 2^k + 1.
 
Let me improve upon the argument using a different approach.

It is known (A THEOREM!) that any prime factor of 2^p - 1 is of the form
2kp+1 for some integer k >= 1. Now, if 2p+1 is prime, then it will divide
2^p-1 with probability 1/2. (Theorem! This arises from quadratic reciprocity
and the fact that 2 is a quadratic residue of 1/2 the primes). Similarly
one may argue that if 2kp+1 is prime, that it should divide 2^p-1 with
probability 1/2k. One should now ask what is the probability that no k
exists such that 2kp+1 divides 2^p-1 for any given p. This is about
1/2*3/4*5/6*...... up to 2kp+1 = sqrt(2^p-1), or k = sqrt(2^p-1)/2p. One
can estimate this product which essentially gives an estimate whether 2^p-1
is prime. This product up to k should be about O(1/log k). If one substitutes
the expression for k above one obtains O(1/p). That is to say the probability
that 2^p-1 is prime is proportional to 1/p. It is known that sum(1/p) diverges,
therefore one should expect an infinite number of Mersenne primes. In fact,
this leads to the following:

#{p < X; p prime and 2^p-1 is prime} = O(log log X).

One can get an explicit constant in the above expression. As it turns out,
the data we have so far seems to support this argument.

By the way, this is one of the major reasons why we would like to know
that we have ALL the Mersenne primes up to X when someone announces 2^X-1
is prime; If we were to obtain anomalous data, we would have to rethink
our arguments.

The argument I gave above leads to a result similar to that of the 
(more naiive) one previously posted, but does NOT have the same flaws.
One can not use it to imply that there are an infinity of primes of the
form 2^k for example.
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
Newsgroups: sci.math