Sign up ×

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and $(\prod_p p) + 1$ (Euclid's theorem).

I was trying to prove one by the Sieve on this grid

    1     2     3     4 ... p
  p+1   p+2   p+3   p+4 ... 2p
 2p+1  2p+2  2p+3  2p+4 ... 3p
p^2+1 p^2+2 p^2+3 p^2+4 ...

but it did not work.

Do any good arguments like this exist? I don't expect anything as strong as Prime Number Theorem or even Bertrand, but surely a direct combination proof can prove that there are lots of primes?

share|cite|improve this question
I'm not sure exactly what counts as a combinatorial argument, but it's certainly a phrase I associate with the work of Erdos. So I will note that Erdos, at a very young age, gave a new proof of Bertrand's Postulate. You might want to check that out and see if it is "combinatorial enough" for your purposes or tastes. – Pete L. Clark May 13 '11 at 18:47
To add a reference to @Pete's comment: An extremely nice exposition of Erdős's argument can be found in Aigner and Ziegler's book Proofs from THE BOOK (which I heartily recommend to anyone liking beautiful and outstandingly clever mathematics, which is in addition written and exposed with great care for details). The title refers to a phrase of PE about which you can find out on his Wikipedia page in case you're interested. – t.b. May 13 '11 at 23:47
Chebyshev said/And I say it again/There's always a prime/Between $n$ and $2n$. – Gerry Myerson May 14 '11 at 1:46

3 Answers 3

Interesting idea to use a grid. I doubt it will work for this question, since writing things in that grid format in a sense splits into arithmetic progressions modulo $p$, and usually saying things about the primes in a progression is harder.

However, I cannot help but mention that using a grid like that was applied brilliantly by Maier to prove a counter-intuitive result, (using the Prime Number Theorem for Arithmetic Progessions) and the idea is now called the Maier Matrix Method.

(A small digression, but it is interesting!)

The Maier Matrix Method

There are questions regarding primes in short intervals, and we can ask ourselves what does $$\pi(x+y)-\pi(x)$$ look like? To say anything meaningful, $y$ cannot be too small, but here lets suppose $y=\log^B(x)$ for some $B>2$. Selberg proved that under the Riemann Hypothesis, we have $$\pi(x+y)-\pi(x)\sim \frac{y}{\log x}$$ as $x\rightarrow \infty$ for almost all $x$. (A set with density $\rightarrow 1$) It was then conjectured that this asymptotic must hold for all $x$ which are sufficiently large. (This conjecture was made for several reasons, one of which is that it is true under Cramer's probabilistic model)

In a surprising turn of events, Maier showed it was false, and that there exists $\delta>0$ and arbitrarily large values of $x_1$ and $x_2$ such that both $$\pi(x_1 +\log^B (x_1))-\pi (x_1)> (1+\delta)\log^{B-1}(x_1)$$and $$\pi(x_2 +\log^B (x_2))-\pi (x_2)< (1-\delta)\log^{B-1}(x_2)$$hold, despite the fact that the asymptotic holds for a set of density $1$.

He proved this using a method which is now called the "Maier Matrix Method." Essentially, it is just drawing a grid which is similar to the one above, and then applying a clever combinatorial argument. The columns are arithmetic progressions, and by PNT4AP, we can easily say things about them to understand the number of primes in the grid. There is a little trick with oscillation of the Dickman Function, but then basically by the pigeon hole principle the question is solved.

I definitely think you might find this expository article by Dr.Andrew Granville to be interesting. (It is quite readable, and gives an a more in depth, and very clear explanation)

share|cite|improve this answer

Here is an elementary argument which shows that there are "lots" of primes. Consider the number of numbers in the interval $[1, n]$. On the one hand, this is $n$. On the other hand, by unique factorization every such number can be uniquely written in the form $\prod_{i=1}^{\pi(n)} p_i^{e_i}$. It follows that $n$ is equal to the number of non-negative integer solutions to

$$e_1 \log p_1 + ... + e_{\pi(n)} \log p_{\pi(n)} \le \log n.$$

This is easily seen to be at most $\left( \log_2 n \right)^{\pi(n)}$, hence

$$n \le (\log_2 n)^{\pi(n)}$$

from which it follows that

$$\pi(n) \ge \frac{\log n}{\log \log_2 n}.$$

It might be possible to extract a weak form of Bertrand's postulate from this argument.

share|cite|improve this answer
It tells us there are at least 4 primes below 100000? edit: this is better than Euclids proof which gives $\pi(n) \ge \log(\log(n))$. – quanta May 13 '11 at 18:06
Well, there are! – Qiaochu Yuan May 13 '11 at 18:20

Edited: Here is a very relevant link on Robin Chapman's page. It is the combinatorial proof which Erdos originally used to prove Bertrands postulate. (Mentioned in Pete L. Clark's comment)

The PDF is very similar to the proofs I mentioned here, (and here) and is based entirely on the primes dividing the central binomial coefficient.

I will leave in the proof regarding a lower bound for $\pi(x)$, since it is still relevant.

What follows is a proof Chebyshev's Theorem based on the primes dividing the central binomial coefficient. First, two well known facts:

Fact 1: Let $r(n,p)$ denote the highest power of a prime $p$ that divides $n!$. Then $$r(n,p)=\lfloor\frac{N}{p}\rfloor+\lfloor\frac{2N}{p^{2}}\rfloor+\lfloor\frac{2N}{p^{3}}\rfloor+\cdots$$

Fact 2: For every integer $N\geq1$ we have that $$\frac{4^{N}}{2N}\leq\binom{2N}{N}.$$

Theorem: We have that $$\pi(x)\geq\ln(2)\frac{x}{\ln x}-2.$$

Proof. Consider $\binom{2N}{N}.$ For each prime $p$, let $v_{p}$ denote the number of times it divides $\binom{2N}{N}$. Hence $$\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}.$$ Let $t=\log_{p}(2N)$ so that $\lfloor\frac{2N}{p^{j}}\rfloor=0$ when $j\geq t.$ By the lemma, we have $$v_{p}=\left(\lfloor\frac{2N}{p}\rfloor+\lfloor\frac{2N}{p^{2}}\rfloor+\cdots\right)-2\left(\lfloor\frac{N}{p}\rfloor+\lfloor\frac{N}{p^{2}}\rfloor+\cdots\right)=\sum_{i=1}^{t}\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor.$$ Since $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=0$ or $\lfloor\frac{2N}{p^{i}}\rfloor-2\lfloor\frac{N}{p^{i}}\rfloor=1$ for each $i$ we see that $v_{p}\leq t.$ Hence if $p^{r}$ divides $\binom{2N}{N}$ we must have $p^{r}\leq2N.$ Consequently $$\binom{2N}{N}=\prod_{p\leq2N}p^{v_{p}}\leq\prod_{p\leq2N}(2N)=(2N)^{\pi(2N)}.$$Applying the other lemma we get $\frac{4^{N}}{2N}\leq(2N)^{\pi(2N)}$and upon taking logarithms we find$$N\ln4-\ln(2N)\leq\pi(2N)\ln(2N)$$and hence $$\frac{2N\ln2}{\ln2N}\leq\pi(2N)+1.$$Since this holds for every even integer, and there is at most one prime between even integers we get

$$\frac{x\ln2}{\ln x}-2\leq\pi(x)\ \text{for all } \ x\geq2,$$ as desired.

share|cite|improve this answer
A very similar proof can be used to give a similar upper bound; it can be found, for example, in Apostol's Introduction to Analytic Number Theory (the section is titled something like "elementary results"). – Qiaochu Yuan May 14 '11 at 2:53
See also:… – Eric Naslund Oct 12 '13 at 13:32

Your Answer


