Date: Sat, 17 Jan 1998 13:40:00 -0600 (CST)
From: Dave Rusin <rusin>
To: tim@maths.tcd.ie
Subject: Re: Supply of primes infinite in all even subsets, Friedlander, Iwaniec, Peterson
Newsgroups: sci.logic,sci.math

Your reasoning is fine but the application faulty.

In article <69qmqh$ldp@graves.maths.tcd.ie> you write:

>If the sequence gets larger faster than n log n,
>it is rather unlikely that there will be an infinity of primes in it,
>eg n^2 + 1, n^3 - n + 3, etc.

It is conjectured that ther _are_ infinitely many primes of the form n^2+1.
OTOH, a sequence such as  2^(2^n)+1  is sufficiently sparse for your arguments
to apply: The cutoff is that we must have a sequence which grows faster than
exponentially in order to have an expectation that there are few such primes.

>Roughly speaking, the probability of n being prime is 1/log n

Yes

>so the expected number of primes in a sequence f(n) is sum f(n)/log n .

No. The probability the  n-th term in your sequence is prime is about
1/log(f(n)), so the pivotal question is the convergence of the sum
sum 1/log(f(n)).  For the sequence  f(x)=n^2+1, this sum is on the order of
N/log(N), that is, we expect about that many primes up to  N^2+1. and
in particular we expect infinitely many. The infinitude of the Mersenne
primes is similar but a little less convincing as the harmonic series
diverges so slowly. Primes of the form  2^(n^2+1) - 1  are likely to be
finite in number but arguably there should be quite a few; primes of the
form  2^(2^n) - 1 will also be finite in number and the possibility that there
be _any_ more than we know about seems unlikely.

People have looked for primes of the form  n^n + 1, say -- rather a pointless
sequence IMHO, but an interesting test case here: the number of these among
the first  N  which I would expect to be prime is on the order of 
sum(1/ nlog(n) )  which is about  log(log(N)). In particular, this grows
to infinity (leading us to expect infinitely many such primes) but grows
VERY slowly. The list of values of  n  for which   n^n+1  is prime probably
looks like a set of numbers each of which has two or three times as many
_digits_ as the one before! Compare this to the list of  n  for which
2^n-1  is prime -- that list grows (apparently without bound) but we seem
to get a few such  n  of each possible number of digits.

>If this converges, the number of primes is likely to be finite.
... understanding, of course, that all this talk of "probability" is
essentially useless, notwithstanding the comfort it may provide us.

dave

PS. I don't know why you bother responding to AP. He's constantly mistaken,
unwilling to listen, and increasingly tending to abuse. IMHO better to 
ignore him.