{"id":299,"date":"2013-07-08T02:20:54","date_gmt":"2013-07-08T06:20:54","guid":{"rendered":"http:\/\/www.curtisbright.com\/bln\/?p=299"},"modified":"2013-07-08T02:20:54","modified_gmt":"2013-07-08T06:20:54","slug":"the-conditional-prime-number-theorem","status":"publish","type":"post","link":"http:\/\/localhost\/blog\/index.php\/2013\/07\/08\/the-conditional-prime-number-theorem\/","title":{"rendered":"The conditional prime number theorem"},"content":{"rendered":"

Previously<\/a>\u00a0I discussed the prime number theorem<\/em> and proved\u00a0Chebyshev’s weak form of it, namely that $\\pi(n)=\\Theta(n\/\\ln n)$. Chebyshev was also able to show the\u00a0conditional<\/em> result that if<\/p>\n

\\[ \\lim_{n\\to\\infty}\\frac{\\pi(n)}{n\/\\ln n} \\]<\/p>\n

exists, then its value is $1$. While this might seem to be quite close to the prime number theorem, there is no especially good reason why the limit should exist. In fact, in a sense this result makes the limit less likely to exist; after our previous proof all one knows is that the limit lies between $0.34$ and $4.16$ (supposing it exists), but now it can have only one possible value!<\/p>\n

Some new functions<\/h1>\n

Before proving this result, it is useful to introduce the\u00a0von Mangoldt function<\/em> defined by<\/p>\n

\\[ \\Lambda(n) := \\begin{cases}
\n\\ln p & \\text{if $n\\geq2$ is a perfect power of the prime $p$} \\\\
\n0 & \\text{otherwise}
\n\\end{cases} \\]<\/p>\n

and the\u00a0Chebyshev function<\/em> defined as the partial sums of the von Mangoldt function,<\/p>\n

\\[ \\psi(n) := \\sum_{m\\leq n}\\Lambda(m) .\u00a0\\]<\/p>\n

For each prime $p$ there are $\\lfloor\\log_p n\\rfloor$ perfect powers of $p$ less than or equal to $n$ and strictly greater than $1$, so an alternate way of writing this function is<\/p>\n

\\[ \\psi(n) = \\sum_{p\\leq n}\\lfloor\\log_p n\\rfloor\\ln p . \\]<\/p>\n

Upper bound on $\\psi(n)$<\/h2>\n

By removing the floor and using the logarithm change-of-base formula one gets an upper bound on $\\psi(n)$:<\/p>\n

\\[ \\psi(n) \\leq \\sum_{p\\leq n}(\\log_p n)\\ln p = \\sum_{p\\leq n}\\ln n = \\pi(n)\\ln n \\]<\/p>\n

In particular,\u00a0using the previously established $\\pi(n)=O(n\/\\ln n)$ this implies<\/p>\n

\\[ \\psi(n) = O(n) . \\tag{1} \\]<\/p>\n

Lower bound on $\\psi(n)$<\/h2>\n

By removing every term in the sum defining $\\psi(n)$ except when $m$ is a prime larger than $n’$, and using $\\pi(n’)=O(n’\/\\ln n’)$,\u00a0one gets a similar lower bound on $\\psi(n)$:<\/p>\n

\\begin{align*}
\n\\psi(n) &\\geq \\sum_{n'<p\\leq n}\\ln p \\\\
\n&\\geq \\sum_{n'<p\\leq n}\\ln n’ \\\\
\n&= \\ln n’\\bigl(\\pi(n)-\\pi(n’)\\bigr) \\\\
\n&= \\pi(n)\\ln n’ + O(n’)
\n\\end{align*}<\/p>\n

Now, this holds for all $n'<n$, so take $n’:=n\/\\ln n$ (it is actually not necessary to ensure that $n’$ is an integer). Then the lower bound becomes<\/p>\n

\\[ \\psi(n) \\geq \\pi(n)(\\ln n-\\ln\\ln n) + O\\Bigl(\\frac{n}{\\ln n}\\Bigr) = \\pi(n)\\ln(n) + O\\Bigl(\\frac{n\\ln\\ln n}{\\ln n}\\Bigr) . \\]<\/p>\n

Combining the bounds on $\\psi(n)$<\/h2>\n

Since the error term here is $o(n)$, combining with the upper bound $\\psi(n)\\leq\\pi(n)\\ln n$ we get the nice relation<\/p>\n

\\[ \\psi(n) = \\pi(n)\\ln n + o(n) . \\]<\/p>\n

Dividing by $n$, we find that<\/p>\n

\\[ \\frac{\\psi(n)}{n} = \\frac{\\pi(n)}{n\/\\ln n} + o(1) . \\tag{2} \\]<\/p>\n

This is a\u00a0very<\/em> strong asymptotic relation between $\\psi(n)\/n$ and $\\pi(n)\/(n\/\\ln n)$; it says that the difference between these functions goes to zero as $n$ increases. So as $n$ gets large, the functions essentially become identical.<\/p>\n

The first estimation of $\\ln(n!)$<\/h1>\n

The proof now proceeds by estimating the quantity $\\ln(n!)$ in two different ways. The first way is a weak form of Stirling’s approximation<\/a>:<\/p>\n

\\[ \\ln(n!) = n \\ln n + O(n) \\tag{3} \\]<\/p>\n

A simple proof of this proceeds by estimating $\\newcommand{\\d}{\\,\\mathrm{d}}\\int_1^n\\ln t\\d t$ by rectangles of width $1$:<\/p>\n

\"diagram\"<\/a><\/p>\n

Note that $\\ln(n!)=\\sum_{m=1}^\\infty \\ln m$, so\u00a0the area formed by the rectangles is exactly the quantity to estimate in (3).<\/p>\n

As shown in the diagram, this quantity is closely under-estimated by $\\int_1^n\\ln t\\d t$ (the dark green area); the amount of under-estimation is given by the light green area. Although this is difficult to evaluate exactly, by sliding the light green triangle-like shapes to the right they all fit inside the final rectangle, which has area $\\ln n$. Thus the dark green area under-estimates the area of the rectangles by at most $\\ln n$, and we have<\/p>\n

\\begin{align*}
\n\\ln(n!) &= \\int_1^n\\ln t\\d t + O(\\ln n) \\\\
\n&= \\bigl[t\\ln n – t\\bigr]_1^n + O(\\ln n) \\\\
\n&= n\\ln n \\mathbin- n + O(\\ln n)
\n\\end{align*}<\/p>\n

which is a stronger form of (3).<\/p>\n

The second estimation of $\\ln(n!)$<\/h1>\n

The second method of estimation relies on the prime factorization of $n!$. Recall<\/a>\u00a0we had already determined the exponent of $p$ in the prime factorization (also known as the $p$-adic order<\/a>) of $n!$ to be $\\nu_p(n!) := \\sum_{k=1}^\\infty\\lfloor n\/p^k\\rfloor$. Using this, we have:<\/p>\n

\\begin{align*}
\n\\ln(n!) &= \\ln\\Bigl(\\prod_{p\\leq n}p^{\\nu_p(n!)}\\Bigr) \\\\
\n&= \\sum_{p\\leq n}\\nu_p(n!)\\ln p \\\\
\n&= \\sum_{p^k\\leq n}\\biggl\\lfloor\\frac{n}{p^k}\\biggr\\rfloor\\ln p \\\\
\n&= \\sum_{m\\leq n}\\Bigl\\lfloor\\frac{n}{m}\\Bigr\\rfloor\\Lambda(m) \\\\
\n&= \\sum_{m\\leq n}\\Bigl(\\frac{n}{m} + O(1)\\Bigl)\\Lambda(m) \\\\
\n&= n\\sum_{m\\leq n}\\frac{\\Lambda(m)}{m} + O\\bigl(\\psi(n)\\bigr)
\n\\end{align*}<\/p>\n

<\/a>We can evaluate $\\sum_{m\\leq n}\\Lambda(m)\/m$ using a trick known as Abel’s summation formula<\/a>:<\/p>\n

\\begin{align*}
\n\\sum_{m\\leq n}\\frac{\\Lambda(m)}{m} &= \\sum_{m\\leq n}\\frac{\\psi(m)-\\psi(m-1)}{m} \\\\
\n&= \\sum_{m\\leq n}\\frac{\\psi(m)}{m} \\mathbin- \\sum_{m\\leq n-1}\\frac{\\psi(m)}{m+1} \\\\
\n&= \\sum_{m\\leq n-1}\\psi(m)\\Bigl(\\frac{1}{m}-\\frac{1}{m+1}\\Bigr) + \\frac{\\psi(n)}{n} \\\\
\n&= \\sum_{m\\leq n-1}\\psi(m)\\Bigl[-\\frac{1}{t}\\Bigr]_m^{m+1} + \\frac{\\psi(n)}{n} \\\\
\n%&= \\sum_{m\\leq n-1}\\psi(m)\\int_m^{m+1}\\frac{\\!\\d t}{t^2} + \\frac{\\psi(n)}{n} \\\\
\n&= \\sum_{m\\leq n-1}\\int_m^{m+1}\\frac{\\psi(t)}{t^2}\\!\\d t + \\frac{\\psi(n)}{n} \\\\
\n&= \\int_1^n\\frac{\\psi(t)}{t^2}\\!\\d t + \\frac{\\psi(n)}{n}
\n\\end{align*}<\/p>\n

Most of this is just algebra; the fact that $\\psi(m)=\\psi(t)$ for $t\\in[m,m+1)$ justifies pulling $\\psi(m)$ into the integral. Putting these together and using (1), we get our second estimate on $\\ln(n!)$:<\/p>\n

\\[ \\ln(n!) = n\\int_1^n\\frac{\\psi(t)}{t^2}\\!\\d t + O(n) \\tag{4} \\]<\/p>\n

Putting the estimates together<\/h1>\n

Combining (3) and (4) and dividing by $n$ we find that<\/p>\n

\\[ \\int_1^n\\frac{\\psi(t)}{t^2}\\!\\d t = \\ln n + O(1) . \\tag{5} \\]<\/p>\n

Using (5) to derive the result<\/h1>\n

Suppose that the limit in question exists and equals $1+\\epsilon$ for some $\\epsilon>0$. Then, taking the limit as $n\\to\\infty$ in (2), we have<\/p>\n

\\[ \\lim_{n\\to\\infty}\\frac{\\psi(n)}{n} = \\lim_{n\\to\\infty}\\frac{\\pi(n)}{n\/\\ln n} = 1 + \\epsilon . \\]<\/p>\n

It follows that there is some $N$ such that $\\psi(t)\/t\\geq 1+\\epsilon\/2$ for all $t\\geq N$. Now, $N$ only depends on the constant $\\epsilon$, so taking $N$ fixed as $n\\to\\infty$ we have
\n\\[ \\int_1^n\\frac{\\psi(t)}{t^2}\\d t \\geq \\int_N^n\\frac{\\psi(t)}{t^2}\\d t \\geq \\int_N^n\\frac{1+\\epsilon\/2}{t}\\d t = \\Bigl(1+\\frac{\\epsilon}{2}\\Bigr)\\ln n + O(1) . \\]<\/p>\n

This contradicts (5), since the coefficient on the leading term $\\ln n$ is larger than $1$; for example, this implies that $\\int_1^n\\psi(t)\/t^2\\d t-\\ln n=\\Omega(\\ln n)$, which is not $O(1)$ as given by (5).<\/p>\n

Similarly, if the limit in question exists and equals $1-\\epsilon$ for some $\\epsilon>0$ then we have $\\lim_{n\\to\\infty}\\psi(n)\/n\u00a0=\u00a01-\\epsilon$, so there exists some $N$ such that $\\psi(t)\/t\\leq1-\\epsilon\/2$ for all $t\\geq N$. Then as $n\\to\\infty$ we have<\/p>\n

\\[ \\int_1^n\\frac{\\psi(t)}{t^2}\\d t \\leq O(1) + \\int_N^n\\frac{1-\\epsilon\/2}{t}\\d t = \\Bigl(1-\\frac{\\epsilon}{2}\\Bigr)\\ln n + O(1) , \\]<\/p>\n

which contradicts (5), since this says that the coefficient on the leading term $\\ln n$ is less than $1$.<\/p>\n

Therefore, we conclude that if $\\lim_{n\\to\\infty}\\pi(n)\/(n\/\\ln n)$ exists it cannot be strictly larger than or strictly less than $1$, so it must be exactly $1$.<\/p>\n","protected":false},"excerpt":{"rendered":"

Previously\u00a0I discussed the prime number theorem and proved\u00a0Chebyshev’s weak form of it, namely that $\\pi(n)=\\Theta(n\/\\ln n)$. Chebyshev was also able to show the\u00a0conditional result that if \\[ \\lim_{n\\to\\infty}\\frac{\\pi(n)}{n\/\\ln n} \\] exists, then its value is $1$. While this might seem … 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\/299"}],"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=299"}],"version-history":[{"count":0,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/posts\/299\/revisions"}],"wp:attachment":[{"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=299"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/localhost\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}