I think I have a proof for the following theorem, and I would like to make sure the proof is correct, but before I do that, I'd like to make sure that the following theorem isn't obvious in some way I'm not missing:

Looking at the theorem, I should probably phrase it,

given any real number r> 1, there are an infinite number of integer n that satisfy...

just to make it more clear

Apply the theorem with n ' =r n to get p(r² n)-p(r n) £ 1. Do this k times and add to get p(r^k n)-p(n) £ k. In other words, p(r^k n) £ k+p(n).

(Actually, this step is slightly dodgy because r n, r² n, etc.might not be integers. I don't think this will matter though.)

This would give that p(r^k n)=O(k) (do you know about big-O notation?). But we know that this isn'ttrue because of the prime number theorem (p(n) ~ n/log(n)).

An elementary proof might be nicer though, since I appealed to the prime number theorem to prove that.

I hope I haven't made any mistakes, I'd feel very silly.

I'd certainly be very interested to see your proof - this doesn't look at all obvious to me (though it is certainly obvious if you replace > with ³ ). Here is one way though. It is easy to see that your condition being false would imply the existence of a positive constant A such that p_n ³ Arⁿ where p_r is the rth prime - so in fact your result follows from the (reasonably well known) fact that the sum of the reciprocals of the primes is divergent. This fact is derived by using the result (1-1/p₁)(1-1/p₂)¼ = 0 (which is proved by considering Euler's product for the zeta function). My guess is that your proof will also use this in one form or other.

Note, we can get a stronger result using the prime number theorem (the prime number theorem states p(n) ~ n/logn but the proof of this theorem is very difficult). The prime number theorem implies that p(r n)-p(n)®¥ as n®¥ for any fixed r > 1. I think it is easy to show that for any fixed r > 1, p(r n)-p(n) can be made arbitrarily large, using the same technique as above, but proving the difference tends to infinity is probably quite hard without PNT. One consequence of the fact that p(r n)-p(n)®¥ as n®¥ is that not only is your statement true for infinitely many n, it is actually true for sufficiently high n. I'd be very interested to see a first-principles proof of this fact, but it will certainly be very hard, since this result implies asymptotic Bertrand which is itself hard to prove. It would also be interesting to know exactly how high n has to be, for each r for your inequality to hold - this is one question PNT certainly won't be able to answer!

Here's the proof:

if f^-1(n+1)-f^-1(n) £ g(n) for an infinite number of n and there are only a finite number of exceptions to this inequality, then

¥ å n=1

af(n)/g(f(n))

converges for 0 £ a < 1.

Proof: assume a to be in the interval 0 to 1. Then

0 <

¥ å n=1

af(n)/g(f(n))=

¥ å m=1

t(m)am/g(m)

(i)

where t(n) is the number of integer x that satisfy [f(x)]=n, where [x] is the floor of x. We've required that f^-1(n+1)-f^-1(n) £ g(n), where the inequality is broken only a finite number of times. Assume that we are currently not dealing with one of those times; where the inequality is satisfied

[f^-1(n+1)]-éf^-1(n)ù £ g(n) (1),

where I'm using éxù to represent the roof of x (smallest integer not less than x).

As x=éf^-1(n)ù is the smallest integer to satisfy [f(x)]=n, for f(f^-1(n))=n, and therefore, f([f^-1(n)]) £ n, which implies that [éf^-1(n)ù] is the smallest integer to satisfy that relation. And, by the same logic, x=[f^-1(n+1)] is the largest integer to satisfy [f(x)]=n. And, because f is monotonically increasing, all integers between these two numbers satisfy this requirement,

t(n)=[f^-1(n+1)]-[éf^-1(n)ù].

Thus, by (1), there are only a finite number of integers such that t(n) is greater than g(n), and so, (i) is less than or equal to

C+

¥ å n=1

an

where C is a finite constant composed of all the terms where (1) doesn't hold.

As this is convergent, our original sum is convergent.

I've never seen this theorem, but the theorem is pretty obvious and relatively natural, if you think about it using an example. Also, in the theorem, I haven't said anything about the function always being defined, which is necessary, if only trivially.

Alright, using this theorem, let a=1/r, f(n)=[log_r (p_n)], and g(n)=C (note that r > 1). Then the sum is

1/C

¥ å n=1

1/pn

,

which isn't convergent. As the inverse of f is p(r^n+b), where b is less than 1, we are given, by the contrapositive of the theorem,

p(r^n+a+1) > C+p(r^n+b),

where both a and b are less than 1 for an infinite number of n. This implies that

p(r² rⁿ) > C+p(rⁿ),

for an infinite number of n. The theorem in my original post then follows by replacing rⁿ with x, r² with w, with w > 1.

We can use theorem 1 again to prove an asymptotic version of Bertrand's postulate (actually, wouldn't it be an asymptotic version of a stronger theorem than Bertrand's postulate?), it someone can find a slow enough function that diverges to infinity.

Brad

Thanks for the explanation - it looks about the same as my proof, but I'm a bit confused by the start. You imply that the domain and range of f and g is some subset of the integers, yet you write [f(x)], which would seem to indicate f can be real valued. Also you write g ' ³ 0 implying that the domain of g is more than the integers - by this do you just mean g is increasing?

I think I like your proof better, though. If nothing else, it takes about 30 less lines to explain!

Using theorem 1, still assign f(n)=[log_r(p_n)], but now, assign g(n)=ln(f^-1(n))/4, so that g(f(n))=ln(n)/4. We know from theorem 1, if

¥ å n=1

1/(rf(n)g(f(n)))

is divergent, what we want follows. First off,

¥ å n=1

1/rf(n) g(f(n)) >

¥ å n=1

4/(pnln(n))

.

We also know (the above sum from N+1 to 2N)

4/(p_N+1ln(N+1))+4/(p_N+2ln(N+2))+¼+4/(p_2Nln(2N)) > 4N/(p_2Nln (2N)) (A)

Here comes the part where I ask for help. Can someone prove, in an elementary fashion, that the nth prime is less than the nth square past some given n? This is obvious with the prime number theorem, but I haven't had much luck without the prime number theorem. Go ahead and assume this result though. Then 4N² > p_2N, which implies 4N/(p_2Nln(2N)) > 1/(Nln(2N)). It's fairly easy to prove that

å

1/(nln(n))

is divergent, and therefore,

¥ å n=1

1/( rf(n)g(f(n)))

is divergent, and what we want to prove follows rather easily. By theorem 1, p(r n)-p(n)®¥!

But, this only works if someone can prove there are only a finite number of exceptions to N² > p_N. There seems to only be 1.
Brad

By the way, and then I have to work on more school work, it's easy to prove that there are an infinite number of numbers satisfying N² > p_N , otherwise the sum of the reciprocals of primes would converge. It ends up it's a lot harder to make this statement more exact, though.

I've just realized my 3:09 post is complete idiocy. In it, I'm summing from N+1 to 2N, for all N, and assuming this is the same as summing all N. Please ignore it.

Brad

Define Q_[r,s](x) as the number of n, such that n £ x, not divisible by any prime p_m where p_s £ p_m £ p_r. Note that we can write x as n=a²b, where b contains no squared factor. We only want b where , and all the quote/s are 0 or 1. That gives us possibilities for . Also, . So there are not more than possibilities for . Putting these together,par/ (1).par/ Also, the number of numbers under that are divisible by a th prime where is between or equal to and would be, first, and second, not more than . Thuspar/ ,par/ and sopar/ (2).par/ Now consider the partial sumpar/ par/ where the last two steps are justified by (2), then (1). Note that is independent of . Set , such that . Therefore, each partial sum is greater than or equal to , and so the sum of the partial sums is divergent, and thus the sum is divergent, and thus, by the logic in the very first and very last post of my 3:09 post,par/ for .

Brad: it isn't true that

¥ å n=1

1/(pn lnn)

diverges. By PNT, p_n ~ nlnn, and

¥ å n=1

1/(n(lnn)2)

is a convergent series (just form an estimate for the difference between the 2^kth and 2^k+1th partial sums).

Have you noticed that what we're trying to prove (p(an)-p(n)®¥ for all a > 1) is equivalent to p_n+1/p_n® 1? Here is why:

p_n+1/p_n® 1 as n®¥

Û for all natural k, p_n+k/p_n® 1 as n®¥

Û for all natural k and a > 1, p_n+k/p_n £ a for n sufficiently high

Û for all natural k and a > 1, p(ap_n)-p(p_n) ³ k for n sufficiently high

Û for all a > 1, p(ap_n)-p(p_n)®¥ as n®¥

Û for all a > 1, p(an)-p(n)®¥ as n®¥

I see your proof of convergence, and it can be made even more rigorous by using Tchebychef's theorem (I doubt that's how you spell it, sorry), but I still don't catch where my proof goes awry.

There is a simple proof that p_n+1/p_n® 1, though:

lim n®¥

an+1/an < 1

implies

¥ å n=1

an

is convergent, so

¥ å n=1

an

divergent implies

lim n®¥

an+1/an ³ 1

. Putting a_n=1/p_n, we get

lim n®¥

pn/pn+1 ³ 1

. As the limit is obviously not greater than 1, it must be equal to 1.

It's not that simple. I agree that if p_n+1/ p_n does tend to a limit as n®¥, then this limit must be 1, but how do you know it converges to anything at all? What you can prove esaily is

inf

pn+1/pn=1

- in other words p_n+1/p_n gets arbitrarily close to 1. This is easily shown to be equivalent to the statement you make in the first paragraph, that is p(w a_n)-p(a_n)®¥ for some sequence a_n®¥. The stronger result p_n+1/p_n® 1 is equivalent to showing that p(w n)-p(n)®¥, and it is this that seems very hard without PNT.

I just read your proof of the 26 April, that

¥ å n=1

1/(pnlnn)

diverges. It has some very good ideas in it - especially the way you used combinatorial techniques to get an estimate for sums involving the primes. I think the problem simply comes in the final inequality at the last stage - I think it's the wrong way round.

To be fair, the concept isn't an entirely original idea, Hardy and Wright use a similar concept to prove that the sum of reciprocals of primes diverges.

I still don't see why the last inequality should be the other way around though. We have

and dividing by x then adding one should give the required result.

Brad