Section 1.3 Corollaries
Subsection 1.3.1 Primes between consecutive squares
Exercise 1.3.2.
What does the PNT say about this problem?We get:
\begin{align*}
\pi((n+1)^2) - \pi(n^2) \amp \sim \frac{(n+1)^2}{\log(n+1)^2} - \frac{n^2}{\log n^2} \\
\amp \approx \frac{n}{\log n}
\end{align*}
Before we continue, let us justify the approximation in the last step. Let \(f(x) = \frac{x^2}{\log(x^2)} = \frac{x^2}{2 \log x}\text{.}\) By the Mean Value Theorem, \(f(n+1) - f(n) = 1 \cdot f'(x) \) for some \(n \lt x \lt n+1\text{.}\) We have
\begin{equation*}
f'(x) = \frac{4x \log x - 4}{4(\log x)^2}
= \frac{x}{\log x} - \frac{1}{(\log x)^2} \text{.}
\end{equation*}
Since \(\frac{1}{(\log x)^2} \to 0 \) we get the approximation.
Since \(\pi((n+1)^2) - \pi(n^2) \approx \frac{n}{\log n} \to \infty\text{,}\) there should be primes between \(n^2\) and \((n+1)^2\text{.}\) So, why doesn’t this answer the question?
The problem is the error term in the PNT. Suppose the error in the approximation \(\pi(x) \approx \frac{x}{\log x}\) is of the order \(\sqrt{x}\text{.}\) In this case, around \(n^2\) and \((n+1)^2\) we would end up with errors of order \(n\text{;}\) our approximation would be something like \(\pi((n+1)^2) - \pi(n^2) \approx \frac{n}{\log n} \pm n\text{,}\) which is not informative. We need better control of errors in the PNT!
Subsection 1.3.2 Pairs that add up to primes
Theorem 1.3.3.
(Greenfield–Greenfield, 1998) For \(n \geq 1\) the set \(\{1,2,\dotsc,2n\}\) can be partitioned into \(n\) pairs \(\{a_1,b_1\}, \dotsc, \{a_n,b_n\}\) such that each \(a_i+b_i\) is prime.Proof.
By induction on \(n\text{.}\) For \(n = 1\text{,}\) our set is \(\{1,2\}\text{.}\) There is one pair, with \(1+2=3\text{,}\) prime. For \(n \gt 1\text{,}\) let \(p\) be a prime such that \(2n \lt p \leq 4n\text{.}\) In fact it must be \(p \lt 4n\text{.}\) Write \(p = 2n+m\text{,}\) where \(1 \leq m \lt 2n\text{.}\) Here \(m\) is odd. We can form pairs:
\begin{equation}
\{2n,m\}, \{2n-1,m+1\}, \{2n-2,m+2\}, \dotsc,
\{n + \lceil \frac{m}{2} \rceil, n + \lfloor \frac{m}{2} \rfloor\}\text{.}\tag{1.3.1}
\end{equation}
Each of these pairs adds up to \(p\text{.}\) They take care of all the numbers \(m,m+1,\dotsc,2n\text{.}\) What’s left is \(\{1,2,\dotsc,m-1\}\text{.}\) Since \(m\) is odd, \(m-1\) is even, and so this remaining set can be paired off inductively.
Subsection 1.3.3 Explicit bounds for the PNT
Another corollary of our work so far gives explicit bounds for the PNT.
Corollary 1.3.4.
There are constants \(c, C \gt 0 \) such that for all \(x \geq 2\text{,}\)
\begin{equation}
c \frac{x}{\log x} \leq \pi(x) \leq C \frac{x}{\log x} \text{.}\tag{1.3.2}
\end{equation}
Proof.
First, the upper bound. We have
\begin{equation*}
\prod_{p \leq x} p \leq 4^x \text{.}
\end{equation*}
There are \(\pi(x) - \pi(\sqrt{x})\) primes in the interval \((\sqrt{x},x]\text{,}\) and they are greater than \(\sqrt{x}\text{,}\) so
\begin{equation}
\sqrt{x}^{\pi(x) - \pi(\sqrt{x})} \leq \prod_{p \leq x} p \leq 4^x \text{.}\tag{1.3.3}
\end{equation}
Taking logarithms,
\begin{equation*}
(\pi(x) - \pi(\sqrt{x})) \log \sqrt{x} \leq x \log 4
\end{equation*}
so
\begin{align*}
\pi(x) \amp \leq \log 4 \frac{x}{\log \sqrt{x}} + \pi(\sqrt{x}) \\
\amp = 2 \log 4 \frac{x}{\log x} + \pi(\sqrt{x}) \\
\amp \leq 2 \log 4 \frac{x}{\log x} + \sqrt{x} \\
\amp \leq 4 \frac{x}{\log x}
\end{align*}
for all \(x \geq 2\text{.}\) This gives an upper bound with \(C = 4\text{.}\)
Exercise: Find the maximum value of \(f(x) = \frac{\log x}{\sqrt{x}} + 2 \log 4\) for \(x \geq 2\text{,}\) and show that it is strictly less than \(4\text{.}\) Use \(\frac{\log x}{\sqrt{x}} + 2 \log 4 \lt 4\) to get
\begin{equation*}
2 \log 4 \frac{x}{\log x} + \sqrt{x} \lt 4 \frac{x}{\log x} \text{.}
\end{equation*}
The lower bound is more difficult. Let \(x \geq 2\text{,}\) and let \(2n\) be the least (smallest) even integer not less than \(x\text{,}\) so \(2n-2 \lt x \leq 2n\text{.}\) First of all, \(2n \lt x+2\text{.}\) Second, \(\pi(2n) \leq \pi(x)+1\text{:}\) there is at most one extra prime \(x \lt p \leq 2n\) counted by \(\pi(2n)\) but not by \(\pi(x)\text{,}\) namely \(p = 2n-1\) if it is prime and \(x \lt 2n-1\text{.}\) So \(\pi(x) \geq \pi(2n)-1\text{.}\)
Let \(p_1,\dotsc,p_\ell\) be all the primes dividing \(\binom{2n}{n}\text{.}\) They are all less than or equal to \(2n\text{,}\) so \(\pi(2n) \geq \ell\text{.}\) We can write
\begin{equation}
\binom{2n}{n} = \prod_{i=1}^{\ell} p_i^{\nu_{p_i}(\binom{2n}{n})}
\leq \prod_{i=1}^{\ell} 2n = (2n)^\ell\text{.}\tag{1.3.4}
\end{equation}
Therefore \(\log \binom{2n}{n} \leq \ell \cdot \log 2n \text{,}\) or \(\ell \geq \frac{\log \binom{2n}{n}}{\log 2n} \text{.}\) This shows
\begin{equation}
\pi(x) \geq \pi(2n)-1 \geq \ell-1 \geq \frac{\log \binom{2n}{n}}{\log 2n} - 1\text{.}\tag{1.3.5}
\end{equation}
Now use the inequality
\begin{equation}
\binom{2n}{n} \geq \frac{4^n}{2n} = \frac{2^{2n}}{2n}
\geq \frac{2^x}{2n} \gt \frac{2^x}{x+2}\tag{1.3.6}
\end{equation}
to get
\begin{align*}
\pi(x) \amp \geq \frac{\log\left( \frac{2^x}{x+2} \right)}{ \log(x+2) } - 1 \\
\amp = \frac{(\log 2) x - 2 \log(x+2)}{\log(x+2)} \\
\amp \geq \frac{ \left( \frac{\log 2}{2} \right) x }{ \log(x+2)}
\end{align*}
where the last inequality holds when \(\left( \frac{\log 2}{2} \right) x \geq 2 \log(x+2) \text{.}\) Exponentiating both sides, this is equivalent to \(2^x \geq (x+2)^4 \text{.}\) By trying some values of \(x\) (or plotting a graph) we find that this last inequality is valid for \(x = 17\text{.}\) (Exercise: Find \(2^{17} - 19^4\text{.}\) Is this number prime?) Exercise: Show that \(\frac{\log 2}{2} \geq \frac{2}{x+2}\) for \(x \geq 17\text{,}\) so \((((\log 2)/2) x)' \geq (2/\log(x+2))'\text{.}\) This implies the last inequality is valid for all \(x \geq 17\text{.}\)
So for \(x \geq 17\) we have
\begin{align*}
\pi(x) \amp \geq \left(\frac{\log 2}{2} \right) \frac{x}{\log(x+2)} \\
\amp = \left(\frac{\log 2}{2} \right) \frac{x}{\log x} \frac{\log x}{\log(x+2)} \\
\amp \geq \left(\frac{\log 2}{4} \right) \frac{x}{\log x} \text{,}
\end{align*}
where the last inequality holds when \(\frac{\log x}{\log(x+2)} \geq \frac{1}{2} \text{.}\)
Exercise: Factor \(x^2-x-2\) and show that \(\frac{\log x}{\log(x+2)} \geq \frac{1}{2}\) for all \(x \geq 2\text{.}\)
This shows \(\pi(x) \geq \left( \frac{\log 2}{4} \right) \frac{x}{\log x} \) for all \(x \geq 17 \text{.}\) Here \(\frac{\log 2}{4} = 0.173286795139986\ldots\text{.}\)
To find a lower bound value \(c\) that works for all \(x \geq 2\) we might need to use a slightly smaller \(c\text{.}\)
