Tag Archives: Maths

Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between \(1\) and \(n\) is roughly \(n/\log n\). This estimation gets more and more accurate as \(n\to \infty\). We use \(\pi(n)\) to denote the number of primes between \(1\) and \(n\). So, mathematically, Gauss’s conjecture is equivalent to the claim

\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1\]

This conjecture (currently known as the Prime Number Theorem) is notoriously difficult to prove. The first proof appeared almost a century after it was stated.

However, there are much simpler methods to bound \(\pi(n)\) above and below. Today I shall show such a bound that gives the correct order of magnitude for \(\pi(n)\) up to some constants. In particular, I shall prove that

\[(1+2\log 4)\frac{n}{\log n}\ge \pi(n)\ge \frac{\log 2}{2}\frac{n}{\log n}\]

for \(n\ge 12\). This proof technique is originally due to nineteenth century mathematician Pafnuty Chebyshev. He used a more complicated version of this technique to show that

\[1.1\frac{n}{\log n}\ge \pi(n)\ge 0.92\frac{n}{\log n}\]

for sufficiently large \(n\)s.

The Lower Bound

Suppose \(n\) is even, ie. \(n=2k\). Let us consider the prime factorization of \(\binom{2k}{k}\). All of its prime factors are between \(1\) and \(2k\). Therefore,

\[\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}\]

Claim: For every prime \(p_i\), \(p_i^{a_i}\leq 2k\)

Proof: We shall use this very simple identity \[\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\leq1\]

It is well-known that the largest exponent of a prime dividing \(r!\) is

\[\left\lfloor\frac{r}{p_i}\right\rfloor+\left\lfloor\frac{r}{p_i^2}\right\rfloor+\cdots\]

Since \(\binom{2k}{k}=\frac{(2k)!}{(k!)^2}\), we have the following relationship

\begin{align}
a_i=&\left\lfloor\frac{2k}{p_i}\right\rfloor-2\left\lfloor\frac{k}{p_i}\right\rfloor+\left\lfloor\frac{2k}{p_i^2}\right\rfloor-2\left\lfloor\frac{k}{p_i^2}\right\rfloor+\cdots \\
&\leq 1+1+\cdots
\end{align}

Now there are as many \(1\)s as there are powers of \(p_i\leq 2k\). Hence, \(p_i^{a_i}\leq 2k\).

(Q.E.D)

So, we can conclude,

\[\binom{2k}{k}=p_1^{a_1}\cdots p_{\pi(2k)}^{a_{\pi(2k)}}\leq (2k)^{\pi(2k)}\]

It is easy to prove \(\binom{2k}{k}\ge 2^k\), hence

\[(2k)^{\pi(2k)}\ge 2^k\implies \pi(2k)\ge \frac{\log 2}{2}\cdot\frac{2k}{\log 2k}\]

The same bound can be derived for \(n=2k+1\) using \(\binom{2k+1}{k+1}\).  Therefore, the lower bound is

\[\boxed{\pi(n)\ge \frac{\log 2}{2}\cdot\frac{n}{\log n}}\]

The Upper Bound

Claim: For all \(n\ge 2\), \[\prod_{p\leq n\\ p\ \text{prime}}p\leq 4^n\]

Proof: We induct on \(n\). The base case trivially holds. \(n=2k-1\to 2k\) also holds because the product on the left hand side does not increment. So, we only need to prove \(n=2k\to 2k+1\)
\begin{align}
\prod_{p \leq 2k+1\\ p\ \text{prime}}p &= \prod_{p \leq k+1\\ p\ \text{prime}}p \cdot\prod_{k+2\leq p \leq 2k+1\\ p\ \text{prime}}p\\
&\leq 4^{k+1}\cdot \binom{2k+1}{k}\quad (1)
\end{align}
The first part of the product is \(\leq 4^{k+1}\) because of the inductive hypothesis. The second part is just the product of all the primes in between \(k+2\) and \(2k+1\). It’s easy to see that they all divide \(\binom{2k+1}{k}\), hence their product is \(\leq \binom{2k+1}{k}\).

It’s easy to show \(\binom{2k+1}{k}<4^k\). Substituting this bound back to (1) gives us

\[\prod_{p \leq 2k+1\\ p\ \text{prime}}p \leq 4^{k+1}\cdot 4^k=4^{2k+1}\quad (\text{Q.E.D.})\]

Now take a number \(2\leq m\leq n\). Consider the primes that are between \(m\) and \(n\). There are \(\pi(n)-\pi(m)\) of them, each of which is \(\ge m\). Consequently,

\[m^{\pi(n)-\pi(m)}\leq \prod_{m\leq p \leq n\\ p\ \text{prime}}p\leq \prod_{1\leq p \leq n\\ p\ \text{prime}}p\leq 4^n\]

Now take log of both sides

\[(\pi(n)-\pi(m))\log m\leq n\log 4\]

Rewrite this as

\[\pi(n)\leq \pi(m)+\frac{n\log 4}{\log m}\leq m+\frac{n\log 4}{\log m}\]

Set \(m=\frac{n}{\log n}\) and simplify the expression

\[\pi(n)\leq \frac{n}{\log n}\left(1+\frac{\log 4\cdot\log n}{\log(n/\log n)}\right)\]

Easy to show \(\frac{\log n}{\log(n/\log n)}\leq 2\) for \(n\ge 12\). (In fact you can show much tighter bound for sufficiently large \(n\).) Hence, the upper bound is

\[\boxed{\pi(n)\leq \left(1+2\log 4\right)\frac{n}{\log n}}\]

A Special Case of Zsigmondy’s Theorem

Theorem (Zsigsmondy): 

  1. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) for all positive integers \(k< n\) with the following exceptions:
    • \(n = 2\) and \(a+b\) is a power of two.
    • \(n=6, a=2, b=1\).
  2. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) for all positive integers \(k< n\) with the following exception:
    • \(n=3, a=2, b=1\).

This theorem is very helpful in solving many olympiad number theory problems. However, its use is often frowned upon, as this theorem is quite hard to prove using only elementary mathematics. (I am aware of the proof using Cyclotomic Polynomials, but that’s not “elementary enough” in my opinion.)

In olympiad mathematics, one can get away in most of the cases by just using this theorem for a fixed pair of \(n\) and \(k\). This modification allows us to provide a very simple proof using LTE. Here I’ll restate this particular case, and then prove the first part. The second part can be proven analogously.

Theorem (Zsigsmondy Special Case): 

  1. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) with the following exception:
    • \(n = 2, k=1\) and \(a+b\) is a power of two.
  2. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) with the following exception:
    • \(n=3, k=1,a=2, b=1\).

Proof of 1:

Suppose \(a^n-b^n\) and \(a^k-b^k\) share same set of prime divisors. This implies \(a^n-b^n\) and \(a^{\gcd(n,k)}-b^{\gcd(n,k)}\) also share same set of prime divisors. Assuming \(A=a^{\gcd(n,k)}\) and \(B=b^{\gcd(n,k)}\), we could follow the rest of this argument and get to a contradiction. So, without loss of generality, we may assume \(k=1\).

Now we consider two cases:

Case 1: \(n\) is a power of \(2\).
If \(n=2\) and \(a+b\) is a power of two, we arrive at one of the listed exceptions. Now note that,
\(\begin{align*}&\gcd(a+b, a^2+b^2)\\
=&\gcd(a+b, (a+b)^2-a^2-b^2)\\
=&\gcd(a+b,2ab)\\
=&\gcd(a+b,2)\end{align*}\)
This implies both \(a+b\) and \(a^2+b^2\) can’t be powers of two unless \(a+b=2\implies a=b=1\). Hence at least one of them must have an odd prime divisor. Furthermore, this prime divisor does not divide \(a-b\) since \(\gcd(a-b, a^2+b^2)=\gcd(a-b,2)\) (following the previous steps). However, if \(n>2\), then \(a^2+b^2|a^n-b^n\), implying that odd prime will divide \(a^n-b^n\). This is a contradiction.

Case 2: \(n=2^md\) with \(d>1\) being odd.
Without loss of generality, we may assume \(n>1\) is odd, since \(a^d-b^d|a^n-b^n\) and it is sufficient to show that \(a^d-b^d\) has a prime divisor that does not divide \(a-b\).  From LTE, \(v_p(a-b)+v_p(n)=v_p(a^n-b^n)\) for each odd prime \(p|a-b\). Furthermore, \[\frac{a^n-b^n}{a-b}\equiv na^{n-1}\equiv 1\pmod 2\] implying \(v_2(a-b)=v_2(a^n-b^n)\). Therefore, we can conclude \[\frac{a^n-b^n}{a-b}=\prod_{p|\gcd(n,a-b)}p^{v_p(n)}\leq n\] which is impossible for \(n>1\). This raises another contradiction and we are done.