Date: Sat, 17 Jan 1998 13:40:00 -0600 (CST) From: Dave 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.