Tag Archives: asymptotics

A Bound on the Prime Counting Function

The idea for this post arose from this quora answer.

Let \pi(n) denote the number of primes up to n. It is well-known that

\displaystyle\pi(n)\sim\frac{n}{\log n},

which is the celebrated prime number theorem. Although “elementary” proofs exist, most proofs of the prime number theorem are technical. Nevertheless, we can obtain some simple bounds as follows.

Let p_1,\ldots,p_k denote fixed prime numbers \leq n. By the inclusion-exclusion principle, the number of positive integers \leq n not divisible by any of the p_i is

\displaystyle\begin{aligned}&n-\sum_{i}\left\lfloor\frac{n}{p_i}\right\rfloor+\sum_{i<j}\left\lfloor\frac{n}{p_ip_j}\right\rfloor-\sum_{i<j<k}\left\lfloor\frac{n}{p_ip_jp_k}\right\rfloor+\cdots\\&< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)+2^{k-1}.\end{aligned}

Therefore, we have the following (rather weak) bound for the prime-counting function \pi(n):

\boxed{\displaystyle \pi(n)< n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}}.

This implies the following result.

Theorem. \displaystyle\lim_{n\to\infty}\frac{\pi(n)}{n}=0.


For example, let’s say we want to find all n such that at least 20% of the natural numbers below n are prime. Then

\displaystyle\pi(n)\geq\frac n5.

If p_1,\ldots,p_k are the prime numbers \leq n, then this means that

\displaystyle n\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right) + k + 2^{k-1}>\frac n5
\displaystyle\iff n\left(\frac 15-\frac{\phi(p_k!)}{p_k!}\right)<k+2^{k-1}.

The left-hand side is positive for k=6, for which the inequality has the solution n<6041035/1657\approx 4638.78. Trying the values in this range we obtain the following set of solutions

n\in[2,330]\cup[331,335]\cup[337,340]\cup[349,350]\cup[353,355]\cup[359,360].


In general, if we want to find all n such that \pi(n)\geq\varepsilon n, then we start by finding the least k such that the k-th prime p_k satisfies

\displaystyle\left(1-\frac{1}{p_1}\right)\cdots\left(1-\frac{1}{p_k}\right)=\frac{\phi(p_k!)}{p_k!}<\varepsilon.

(Note that such a k is guaranteed to exist since the left-hand side approaches 0 as k\to\infty, since the harmonic series diverges.) Then we can bound n using

\displaystyle n<\frac{k+2^{k-1}}{\varepsilon-\frac{\phi(p_k!)}{p_k!}}.

(Observe also that \displaystyle\frac{\phi(n!)}{n!}<\frac{\phi((n-1)!)}{(n-1)!}\Leftrightarrow n is prime.)

Leave a comment

Filed under Number Theory

An Asymptotic Property of the Divisor Counting Function

Let \tau(n) be the number of positive divisors of the positive integer n and let \phi(n) be Euler’s function. Then it is easily seen that

\phi(n)+\tau(n)\le n+1

for each n. So

\displaystyle\frac{\phi(n)}{n}+\frac{\tau(n)}{n}\le 1+\frac 1n

holds for all n.

Since there are infinitely many primes,

\displaystyle\limsup_{n\to\infty}\frac{\phi(n)}{n}=\lim_{n\to\infty}\frac{n-1}{n}=1.

So it follows that

\displaystyle\limsup_{n\to\infty}\frac{\tau(n)}{n}=0.

Therefore, by the sandwich theorem,

\displaystyle\lim_{n\to\infty}\frac{\tau(n)}{n}=0,

i.e., \tau(n)=o(n) as n\to\infty. In layman’s terms, this is saying that the number of divisors of n is small compared to n when n is large. The following plot of \tau(n)/n against n for 1\le n\le 500 captures this nicely.

Screenshot 2015-06-26 03.46.54

So this means, for example, that there are only finitely many positive integers n with more than n/2015 divisors, which I think is pretty neat!

Leave a comment

Filed under Number Theory

A Nice Result on Arithmetic Progressions

Let \mathbb N_0 denote the set of the non-negative integers. For a subset S\subseteq\mathbb N_0, we can define the “counting function”

\pi_S(x):=|\{n\in\mathbb N_0\cap S:n\le x\}|

i.e. \pi_S(x) is the number of elements in S that are at most x. Then we can define the (asymptotic) density of S as

\displaystyle \delta(S):=\lim_{x\to\infty}\frac{\pi_S(x)}{x}

when this limit exists.

For example, the set of the even (resp. odd) numbers has density 1/2. More generally, any arithmetic progression a+d\mathbb N_0:=\{a+dn:n\in\mathbb N_0\} has density 1/d. Another example is the set of prime numbers, which has density 0 by the prime number theorem. From this it also follows that the set of composite numbers has density 1.

Theorem. If a finite union of arithmetic progressions of positive integers has density 1, then it contains all sufficiently large positive integers.

Proof. Let

\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)

be a finite union of arithmetic progressions such that \delta(A)=1. Note that (this is the main trick) we can write:

\displaystyle A=\bigcup_{i=1}^k(a_i+d_i\mathbb N_0)=\bigcup_{j=1}^l(b_i+d\mathbb N_0)

for some b_1,\dots,b_l, where d is the least common multiple of d_1,\dots,d_k.

Why can we do this? Consider for example (1+2\mathbb N_0)\cup(2+3\mathbb N_0). We can write this as

\displaystyle \underbrace{(1+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{1+2\mathbb N_0}\cup \underbrace{(2+6\mathbb N_0)\cup (5+6\mathbb N_0)}_{2+3\mathbb N_0}

\displaystyle =(1+6\mathbb N_0)\cup (2+6\mathbb N_0)\cup (3+6\mathbb N_0)\cup (5+6\mathbb N_0)

And this idea works for any finite union of arithmetic progressions.

It is then clear that \{b_1,\dots,b_l\} has to be a complete set of residues modulo d, because otherwise A would have density strictly less than 1. Therefore A has to contain all positive integers \ge\max\{b_1,\dots,b_l\}. \square

We get the following nice corollary:

Corollary. The set of all composite numbers cannot be expressed as a finite union of arithmetic progressions of positive integers.

Proof. Otherwise by the above theorem all sufficiently large positive integers would be composite, contradicting the fact that there are infinitely many primes. \square

Leave a comment

Filed under Combinatorics, Number Theory