## Number Theory: Lecture 14

In which we start to explore the distribution of the primes.

• We reminded ourselves of some examples of results that we have previously seen of the form “There are infinitely many primes congruent to a modulo n”, such as when $a = 1$, $n = 4$ and $a = 3$, $n = 4$.
• We noted that if $a$ and $n$ are not coprime, then this result clearly does not hold.
• Theorem 43 (Dirichlet): Let $n$ be an integer greater than 1, and let $a$ be coprime to $n$.  Then there are infinitely many primes congruent to $a$ modulo $n$.  We did not prove this!  But we saw a small hint of how one can prove it.
• Proposition 44: For any $x \geq 10$, we have $\sum_{p \leq x} \frac{1}{p} \geq \log \log x - \frac{1}{2}$, where the sum is over all primes $p \leq x$.  We proved this by first showing that $\prod_{p \leq x} (1-\frac{1}{p})^{-1} \geq \log x$, and then that $\log \left(\prod_{p \leq x} (1 - \frac{1}{p})^{-1} \right) - \sum_{p \leq x} \frac{1}{p}$ is bounded above by a constant (1/2, as it happens).
• Corollary 45: There are infinitely many primes.
• Proposition 46: There is a constant $c > 0$ such that $\pi(x) \geq c \log x$.  We proved this using an idea of Erdős, namely to write each $y \leq x$ as $y = m^2 p_1^{\alpha_1} \dotsm p_k^{\alpha_k}$, where the $p_i$ are the primes up to $x$ and each $\alpha_i$ is 0 or 1, and then to count the number of such expressions.

Wikipedia has a page with a couple of ways of thinking about $\sum_{p \leq x} \frac{1}{p}$.  Hardy and Wright (An introduction to the theory of numbers) tackles this problem and some related results (see section 22.7).  Erdős and Surányi (Topics in the theory of numbers) give a nice presentation of this material.  Davenport (Multiplicative Number Theory) discusses the sum of the reciprocals of the primes, and also gives a proof of Dirichlet’s theorem on primes in arithmetic progressions.  (Note that this is a different book by Davenport, not the one that I’ve recommended in previous posts!)

On a separate note, I spotted a new paper on the arXiv this morning about positive definite binary quadratic forms.   I haven’t looked beyond the abstract, but it does demonstrate that this is still very much a topic of current research.

#### Preparation for Lecture 15

Next time we shall move on to the Riemann zeta function, and how it is related to the distribution of the primes.   I might mention the Möbius $\mu$ function, which is defined on natural numbers.  If $n = p_1 p_2 ... p_k$, where the $p_i$ are distinct primes, then $\mu(n) = (-1)^k$.  If $n$ is not square-free (if it is not the product of distinct primes), then $\mu(n) = 0$.  And, just to be clear, $\mu(1) = 1$. Here are a couple of questions to get you started thinking about this function.

• Is $\mu$ a multiplicative function?
• Can you compute the sums $\sum_{d|n} \mu(d)$ for various $n$?  (The sum is over all divisors $d$ of $n$.)
• Can you make any conjectures about the approximate size of the sum $\sum_{n \leq x} \mu(n)$?  You might like to use a computer to help you collect some data, in addition to thinking about the function $\mu$.
• You might like to try to relate $\mu$ and the Euler totient function $\phi$ that we saw earlier in the course.