Are there any Combinatoric proofs of Bertrand's postulate?

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
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?

Solution 1:

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)

Solution 2:

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.

Solution 3:

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)=\left\lfloor\frac{N}{p}\right\rfloor+\left\lfloor\frac{2N}{p^{2}}\right\rfloor+\left\lfloor\frac{2N}{p^{3}}\right\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 $\left\lfloor\frac{2N}{p^{j}}\right\rfloor=0$ when $j\geq t.$ By the lemma, we have $$v_{p}=\left(\left\lfloor\frac{2N}{p}\right\rfloor+\left\lfloor\frac{2N}{p^{2}}\right\rfloor+\cdots\right)-2\left(\left\lfloor\frac{N}{p}\right\rfloor+\left\lfloor\frac{N}{p^{2}}\right\rfloor+\cdots\right)=\sum_{i=1}^{t}\left\lfloor\frac{2N}{p^{i}}\right\rfloor-2\left\lfloor\frac{N}{p^{i}}\right\rfloor.$$ Since $\left\lfloor\frac{2N}{p^{i}}\right\rfloor-2\left\lfloor\frac{N}{p^{i}}\right\rfloor=0$ or $\left\lfloor\frac{2N}{p^{i}}\right\rfloor-2\left\lfloor\frac{N}{p^{i}}\right\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