Number Theory - Help with a problem...

I’m working through William Leveque’s Fundamentals of Number Theory.

There is a problem put at the end of section 6.7 (Think it’s 5a, but I don’t have the text in front of me right now) which I’ve had some difficulty with (paraphrase; if anyone has the text please check that I’ve summarized correctly): “Prove that for any value e there are an infinite number of consecutive primes pn and pn+1 such that pn(1+e) > pn+1.”

Perhaps I’m misreading this, but usually I have little difficulty with the problems in this book (after a thorough reading of the chapter, of course), but this one has stumped me for several days. Thought I’d throw it out to the board and see if someone can help, or perhaps correct my mis-interpretation of the problem.

FYI: Section 6.7, “The true order of pi(x)”, details a proof of Chebyshev’s theorem:

along with a proof bounding the size of the nth prime and some improvements on the order of the summation of inverted primes (e.g. 1/2 + 1/3 + 1/5 + …).

Suppose not. Can you use the assumption that for all primes (larger than some finite prime p[sub]N[/sub]) p[sub]n/sub <= p[sub]n+1[/sub] to find bounds on the density of primes?

Ok, I hope this isn’t homework. :slight_smile:

Regardless, I’m not going to actually answer the problem. At least, not right now. (Because I’m not exactly sure how to do it. :wink: )

It seems like what you’re trying to prove is an analogue to the famous “prime skipping” problem. The one that I mean is: let N be a natural number, show that there exist a pair of consecutive primes p and q such that p > q + N.

It is easy to show that there is such a pair:
Let q be the largest prime smaller than (N+1)!+2 and p the smallest prime larger than (N+1)!+2. Now (N+1)!+2 is clearly not prime, because it is divisible by 2. Likewise, (N+1)!+n is divisible by n for any natural number n between 2 and N+1. Thus p-q > N. QED

Ok, now we can emend this statement to say that given any natural number N, there are infinitely many pairs of consecutive primes p and q such that p > q + N. This isn’t so hard and I’m not going to type it all out.

What was the point of all this? Well it seems like your problem is the multiplicative analogue. You’re trying to show that given any number greater than 1, there are infinitely many consecutive primes whose ratio is bigger than this number.

So, when I started typing this, I was going to suggest a straightforward constructive proof from first principles, like the above. Thinking about it a little further I think this may not work. I’ll try to look up the book this afternoon and give you any insight I may have. Until then, I would say that the reciprocal series might be a good thing to think about.


I agree with sinjin that thinking about what the reciprocal series would look like, if all but finitely many primes satisfied p[sub]n/sub <= p[sub]n+1[/sub], is an elegant route to the solution. (But still think about what this formula implies for the local density of primes, compared to the density implied by Chebyshev.)

sinjin, that would prove that primes can be locally sparse. It looks like what the OP wants is a proof that primes can be locally dense.

If it helps any, the OP’s result follows trivially from the Twin Prime Conjecture (because all pairs of twin primes greater than 2/e would satisfy the condition), but that is, of course, only a conjecture. There may be some weaker variant of it proven which would still be strong enough, though.

Actually, it didn’t take until afternoon. You don’t have to use the Chebyshev density equations or anything like that. If all but finitely many primes satisfied p[sub]n/sub <= p[sub]n+1[/sub] then you could contradict a well known theorem of Euler. I’ll spoiler it if you don’t want any more of a hint.

The theorem.

The harmonic series of primes diverges.

Why this matters.

If, after some point, p[sub]n[/sub]r <= p[sub]n+1[/sub] for some ratio r=(1+e)>1, then the tail of your series is bounded by a geometric series. And geometric series converge.

Thx Omphaloskeptic; that was exactly the nudge I needed.

Taking the assumption above, it’s easy to see using recursion that any prime p[sub]n/sub^k <= p[sub]n+k[/sub]. Inverting both sides gives 1/(p[sub]n/sub^k) >= 1/p[sub]n+k[/sub]. The sum all these prime reciprocals 1/p[sub]n+k[/sub] then must be less than 1/p[sub]n[/sub] times a geometric series in 1/(1+e), which means it’s finite. That contradicts the fact that this sum is divergent (it is ~ log log n).

On preview I see that sinjin makes a similar suggestion, thx. I also will take Omphaloskeptic’s advice and compare how the local density of primes pi(n)/n might contradict Chebyshev’s formula. I’m pretty sure (sketching out on a post-it) I see this now; again, just a nudge in the right direction helped (and would have saved me reams of notepaper had I thought of it sooner):slight_smile:

Chronos, I’m glad I’m not trying to do your exercises…

Problem 1: Prove that blah blah blah and so on and so forth.
Hint: You might try to show that there are infinitely many twin primes.

Problem 2: Let M be a closed, simply connected three manifold…


Well, I did say that there might be some weaker version which is proven. Like, the Twin Prime conjecture states that “there are an infinite number of pairs of primes P and Q such that Q - P = 2”. There might be some other statement which is proven, that says something like “there are an infinite number of pairs of primes P and Q such that Q - P < 10000000” (just as a hypothetical example; I don’t know if there are any such theorems). If there were such a theorem, then it would still be strong enough for the same sort of argument I used.

I didn’t realize that the sum of reciprocals of the primes diverged. I had done some puttering around with that on a computer, when I was younger, but I lost interest after the partial sums passed e and pi.

Proofs at Wikipedia if anybody cares.

If S(n) is the sum of the reciprocals of all primes less than n, it is possible to show:

log log n < S(n) < log log n + E + 1/(log n)^2

where E= ~0.2615 is the Meissel-Mertens constant.

Yeah, the sum of the reciprocals of primes diverging totally freaked me out when I first heard it. It just seems so… wrong.

I don’t know of any such results. Apparently (according to this MathWorld page) there’s a recent result that the minimum prime gap size (relative to its expected value ln p[sub]n[/sub]),
lim inf (p[sub]n+1[/sub]-p[sub]n[/sub])/ln p[sub]n[/sub] ,
is zero, meaning that the minimal gaps grow more slowly than ln n; but that doesn’t prove that constant-sized gaps continue.

It still surprises me how many primes there are. The logarithm grows very slowly.