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

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

Note, we can get a stronger result using the prime number theorem (the prime number theorem states $\pi (n)~n/\log n$ but the proof of this theorem is very difficult). The prime number theorem implies that $\pi (rn)-\pi (n)\to \infty$ as $n\to \infty$ for any fixed $r>1$. I think it is easy to show that for any fixed $r>1$, $\pi (rn)-\pi (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 $\pi (rn)-\pi (n)\to \infty$ as $n\to \infty$ 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)\le g(n)$ for an infinite number of $n$ and there are only a finite number of exceptions to this inequality, then $\sum _{n=1}^{\infty }{a}^{f(n)}/g(f(n))$ converges for $0\le a<1$.

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

$0<\sum _{n=1}^{\infty }{a}^{f(n)}/g(f(n))=\sum _{m=1}^{\infty }t(m)a^m/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)\le 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)]-\lceil f^{-1}(n)\rceil \le g(n)$ (1),

where I'm using $\lceil x\rceil$ to represent the roof of $x$ (smallest integer not less than $x$).

As $x=\lceil f^{-1}(n)\rceil$ is the smallest integer to satisfy $[f(x)]=n$, for $f(f^{-1}(n))=n$, and therefore, $f([f^{-1}(n)])\le n$, which implies that $[\lceil f^{-1}(n)\rceil ]$ 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)]-[\lceil f^{-1}(n)\rceil ]$.

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+\sum _{n=1}^{\infty }{a}^n$

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\sum _{n=1}^{\infty }1/p_n$,

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

$\pi (r^{n+a+1})>C+\pi (r^{n+b})$,

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

$\pi (r^2{r}^n)>C+\pi (r^n)$,

for an infinite number of $n$. The theorem in my original post then follows by replacing $r^n$ with $x$, $r^2$ 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\text{'}\ge 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 $\sum _{n=1}^{\infty }1/(r^{f(n)}g(f(n)))$ is divergent, what we want follows. First off,

$\sum _{n=1}^{\infty }1/r^{f(n)}g(f(n))>\sum _{n=1}^{\infty }4/(p_n\ln (n))$.

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

$4/(p_{N+1}\ln (N+1))+4/(p_{N+2}\ln (N+2))+\dots +4/(p_{2N}\ln (2N))>4N/(p_{2N}\ln (2N))$ (A)

Here comes the part where I ask for help. Can someone prove, in an elementary fashion, that the $n$th prime is less than the $n$th 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^2>p_{2N}$, which implies $4N/(p_{2N}\ln (2N))>1/(N\ln (2N))$. It's fairly easy to prove that $\sum 1/(n\ln (n))$ is divergent, and therefore, $\sum _{n=1}^{\infty }1/(r^{f(n)}g(f(n)))$ is divergent, and what we want to prove follows rather easily. By theorem 1, $\pi (rn)-\pi (n)\to \infty$!

But, this only works if someone can prove there are only a finite number of exceptions to $N^2>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\le x$, not divisible by any prime $p_m$ where $p_s\le p_m\le p_r$. Note that we can write $x$ as $n=a^{2}b$, where $b$ contains no squared factor. We only want $b$ where

$\iff$ for all $\alpha >1$, $\pi (\alpha n)-\pi (n)\to \infty$ as $n\to \infty$

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\to 1$, though:

$\underset{n\to \infty }{lim}{a}_{n+1}/a_n<1$ implies $\sum _{n=1}^{\infty }{a}_n$ is convergent, so $\sum _{n=1}^{\infty }{a}_n$ divergent implies $\underset{n\to \infty }{lim}{a}_{n+1}/a_n\ge 1$. Putting $a_n=1/p_n$, we get $\underset{n\to \infty }{lim}{p}_n/p_{n+1}\ge 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\to \infty$, then this limit must be 1, but how do you know it converges to anything at all? What you can prove esaily is $inf{p}_{n+1}/p_n=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 $\pi (w{a}_n)-\pi (a_n)\to \infty$ for some sequence $a_n\to \infty$. The stronger result $p_{n+1}/p_n\to 1$ is equivalent to showing that $\pi (wn)-\pi (n)\to \infty$, and it is this that seems very hard without PNT.

I just read your proof of the 26 April, that $\sum _{n=1}^{\infty }1/(p_n\ln n)$ 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