{"id":159,"date":"2013-03-18T07:22:25","date_gmt":"2013-03-18T11:22:25","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=159"},"modified":"2013-03-18T07:22:25","modified_gmt":"2013-03-18T11:22:25","slug":"a-weak-form-of-the-prime-number-theorem","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2013\/03\/18\/a-weak-form-of-the-prime-number-theorem\/","title":{"rendered":"A weak form of the prime number theorem"},"content":{"rendered":"

The function $\\pi(n)$ counts the number of primes $p$ in the range $1\\leq p\\leq n$. One of the most spectacular\u00a0theorems in mathematics is the so-called\u00a0prime number theorem<\/em>, which states that<\/p>\n

\\[ \\lim_{n\\to\\infty}\\Bigl(\\pi(n)\\Bigm\/\\frac{n}{\\ln n}\\Bigr) = 1 . \\]<\/p>\n

This is a strong condition on the asymptotic behaviour of $\\pi(n)$ as $n$ increases without bound—unlike some asymptotic results, even the base of the logarithm is significant here.<\/p>\n

Last year I worked through a proof of the prime number theorem. Two of the main results used were\u00a0Euler’s product<\/a> and Cauchy’s residue theorem<\/a>—it was breathtaking. It still hasn’t completely “coalesced” in my head, but I periodically revisit it. Today I want to prove a weaker form of the prime number theorem, namely that<\/p>\n

\\[ \\pi(n) = \\Theta\\Bigl(\\frac{n}{\\ln n}\\Bigr) . \\]<\/p>\n

This uses asymptotic notation<\/a>, and says that the growth rate of $\\pi(n)$ is eventually within a constant factor of $n\/\\ln n$.
\n<\/a><\/p>\n

The proof is by Chebyshev<\/a> and proceeds by finding the following bounds on the central binomial coefficient<\/a> $\\binom{2n}{n}$:<\/p>\n

\\begin{align}
\n2^n \\leq \\binom{2n}{n} &\\leq 4^n \\tag{1} \\\\
\nn^{\\pi(2n)-\\pi(n)} \\leq \\binom{2n}{n} &\\leq (2n)^{\\pi(2n)} \\tag{2}
\n\\end{align}<\/p>\n

Upper bound of (1)<\/h1>\n

Using the binomial theorem to expand $(1+1)^{2n}$ gives<\/p>\n

\\[ 4^n = 2^{2n} = (1+1)^{2n} = \\sum_{i=0}^{2n}\\binom{2n}{i} \\geq \\binom{2n}{n} \\]<\/p>\n

since all the terms in the sum are positive.<\/p>\n

Lower bound of (1)<\/h1>\n

However, note that the central term ($i=n$) in the sum is the largest (to go from term $i$ to term $i+1$ you multiply by $\\frac{2n-i}{i+1}$, which is greater than $1$ until $i\\geq n$), so we have:<\/p>\n

\\[ 4^n\u00a0= 2^{2n} = (1+1)^{2n} = \\sum_{i=0}^{2n}\\binom{2n}{i} \\leq (2n+1)\\binom{2n}{n}\u00a0\\]<\/p>\n

The required inequality follows after dividing by $2^n$ and using the fact that\u00a0$2n+1\\leq2^n$ (which holds for $n\\geq3$, however the required inequality may explicitly be checked to hold for $n<3$).<\/p>\n

Lower bound of (2)<\/h1>\n

Examining the prime factorization of\u00a0$\\binom{2n}{n}=(2n)!\/(n!)^2$, we see that it contains all the primes $p$ in the range $n<p\\leq 2n$, since they appear in the numerator but not in the denominator. There are\u00a0$\\pi(2n)-\\pi(n)$ primes in this range, and they are all larger than $n$, so it follows that:<\/p>\n

\\[ \\binom{2n}{n} \\geq \\prod_{n<p\\leq 2n} p \\geq n^{\\pi(2n)-\\pi(n)}\u00a0\\]<\/p>\n

Upper bound of (2)<\/h1>\n

<\/a>Note that there are $\\lfloor n\/p\\rfloor$ multiples of $p$ in the range $1\\leq p\\leq n$. We can use this fact to determine the exponent on $p$ in the prime factorization of $n!$. There will be $\\lfloor n\/p\\rfloor$ factors of $p$ in $n!$, but we also need to count the additional $\\lfloor n\/p^2\\rfloor$ factors of $p$ which are contributed by multiples of $p^2$, and in general an additional\u00a0$\\lfloor n\/p^k\\rfloor$ factors of $p$ contributed by multiples of $p^k$. The exponent of $p$ in the prime factorization of $n!$ is thus<\/p>\n

\\[ \\sum_{k=1}^\\infty \\biggl\\lfloor\\frac{n}{p^k}\\biggr\\rfloor , \\]<\/p>\n

where the sum is zero for $k>\\log_p n$. It follows that the exponent of $p$ in the prime factorization of $(2n)!\/(n!)^2$ is<\/p>\n

\\[ \\sum_{k=1}^{\\lfloor\\log_p(2n)\\rfloor} \\biggl(\\biggl\\lfloor\\frac{2n}{p^k}\\biggr\\rfloor – 2\\biggl\\lfloor\\frac{n}{p^k}\\biggr\\rfloor\\biggr) . \\]<\/p>\n

An interesting fact about the function $\\lfloor 2x\\rfloor-2\\lfloor x\\rfloor$ is that it is either $0$ or $1$ (plot it and you’ll see why), so this sum is actually at most $\\lfloor\\log_p(2n)\\rfloor$. Since $\\binom{2n}{n}$ only contains primes $p$ in the range $1\\leq p\\leq 2n$, it follows that:<\/p>\n

\\[ \\binom{2n}{n} \\leq \\prod_{1\\leq p\\leq 2n}p^{\\log_p(2n)} = \\prod_{1\\leq p\\leq 2n} 2n = (2n)^{\\pi(2n)} \\]<\/p>\n

Using the bounds<\/h1>\n

Putting both (1) and (2) together and taking logarithms yields the following bounds:<\/p>\n

\\begin{gather}
\nn\\ln 2 \\leq \\pi(2n)\\ln(2n) \\tag{3} \\\\
\n(\\pi(2n)-\\pi(n))\\ln n \\leq n\\ln 4 \\tag{4}
\n\\end{gather}<\/p>\n

The lower bound on $\\pi(n)$<\/h1>\n

From (3) we have that<\/p>\n

\\[ \\pi(2n) \\geq \\frac{\\ln2}{2}\\frac{2n}{\\ln(2n)} , \\]<\/p>\n

which is shows the required lower bound for even<\/em> numbers. But it can be slightly modified to work for odd numbers as well (note that\u00a0$\\ln(2n)\\leq\\ln(2n+1)$):<\/p>\n

\\[ \\pi(2n+1) \\geq \\pi(2n) \\geq \\frac{2n+1}{2n+1}\\frac{\\ln2}{2}\\frac{2n}{\\ln(2n)} \\geq \\frac{2n}{2n+1}\\frac{\\ln2}{2}\\frac{2n+1}{\\ln(2n+1)}\u00a0\\]<\/p>\n

Since $2n\/(2n+1)$ is lower bounded by a constant (e.g., $2\/3$) for all positive $n$, this shows that $\\pi(n)=\\Omega(n\/\\ln n)$.<\/p>\n

The upper bound on $\\pi(n)$<\/h1>\n

First we will show the required upper bound for powers of two<\/em>. That way we will be able to apply (4) not only on $n$ but also recursively\u00a0on half of $n$ until $n=1$ is reached. However, to get a nice telescoping sum we modify (4) by subtracting $\\pi(n)\\ln(n\/2)$ from both sides. After rearranging and simplifying with $\\ln n-\\ln(n\/2)=\\ln2$, we find<\/p>\n

\\[ \\pi(2n)\\ln n – \\pi(n)\\ln(n\/2) \\leq n\\ln4 + \\pi(n)\\ln 2 \\leq (3\\ln 2)n \\tag{5} \\]<\/p>\n

since $\\pi(n)\\leq n$ and $\\ln4+\\ln2=3\\ln2$.<\/p>\n

We now sum together (5) used on $n{,}~n\/2{,}~\\dotsc{,}~1$ to get<\/p>\n

\\[ \\sum_{i=0}^{\\log_2 n}\\biggl(\\pi\\Bigl(\\frac{n}{2^{i-1}}\\Bigr)\\ln\\Bigl(\\frac{n}{2^i}\\Bigr)-\\pi\\Bigl(\\frac{n}{2^i}\\Bigr)\\ln\\Bigl(\\frac{n}{2^{i+1}}\\Bigr)\\biggr) \\leq (3\\ln 2)\\sum_{i=0}^{\\log_2 n}\\frac{n}{2^i} . \\]<\/p>\n

However, by telescoping the left sum is equal to $\\pi(2n)\\ln n$ and by the formula for the summation of a geometric series the right sum is at most $(3\\ln2)2n$. In other words, when $n$ is a power of two we have<\/p>\n

\\[ \\pi(2n) \\leq (6\\ln2)\\frac{n}{\\ln n} , \\]<\/p>\n

and the required bound follows using\u00a0$\\frac{n}{\\ln n}<\\frac{2n}{\\ln(2n)}$, a consequence of the fact that\u00a0$\\frac{n}{\\ln n}$ is an increasing function (for $n\\geq3$, although the required bound still holds for $n<3$).<\/p>\n

As before, a slight modification shows the bound holds for all numbers, not just powers of two. Let $m$ be an arbitrary integer in the range $n\\leq m<2n$ where $n$ is a power of two. Then<\/p>\n

\\[ \\pi(m) \\leq \\pi(2n) \\leq (6\\ln 2)\\frac{n}{\\ln n} \\leq (6\\ln 2)\\frac{m}{\\ln m} \\]<\/p>\n

which shows that $\\pi(n)=O(n\/\\ln n)$.<\/p>\n","protected":false},"excerpt":{"rendered":"

The function $\\pi(n)$ counts the number of primes $p$ in the range $1\\leq p\\leq n$. One of the most spectacular\u00a0theorems in mathematics is the so-called\u00a0prime number theorem, which states that \\[ \\lim_{n\\to\\infty}\\Bigl(\\pi(n)\\Bigm\/\\frac{n}{\\ln n}\\Bigr) = 1 . \\] This is a … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"_links":{"self":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/159"}],"collection":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=159"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/159\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=159"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}