## Number Theory: Lecture 17

In which we gain some further insight into the distribution of the primes.

• Proposition 52 (Legendre‘s formula): For $x \geq 10$, we have $\pi(x) = \pi(\sqrt{x}) - 1 + \lfloor x \rfloor - \sum_{p \leq \sqrt{x}} \lfloor \frac{x}{p} \rfloor + \sum_{p_1 < p_2 \leq \sqrt{x}} \lfloor \frac{x}{p_1 p_2} \rfloor - \dotsb$.  We saw that this follows nicely from the inclusion-exclusion principle.
• Lemma 53:  For any natural number $n$, we have $\frac{2^{2n}}{2n} \leq \binom{2n}{n} < 2^{2n}$.  These are both easy bounds arising from the expansion of $(1 + 1)^{2n}$ or from counting subsets of $\{1, 2, \dotsc, 2n \}$.
Lemma 54: For any $x \geq 1$, we have $\prod_{p \leq x} p \leq 4^x$.  We proved this for natural numbers $x$ using induction.
• Theorem 55 (Bertrand‘s postulate): For any natural number $n$, there is a prime $p$ with $n < p \leq 2n$.  Our strategy was to show that the product $\prod_{n < p \leq 2n} p$ is strictly bigger than 1.  We noticed that this product divides the binomial coefficient $\binom{2n}{n}$, and found an upper bound for the remainder of the contribution.  Next time we’ll finish studying this upper bound in order to obtain the lower bound on $\prod_{n < p \leq 2n}p$ that we wanted.  In the meantime, I encourage you to try to finish the proof for yourself.

Erdős and Surányi (Topics in the theory of numbers) discuss Bertrand’s postulate and a number of other interesting results relating to the distribution of the primes.  There’s also a proof of Bertrand’s postulate in Hardy and Wright (An Introduction to the Theory of Numbers).

#### Preparation for Lecture 18

Of course, you should try to finish the proof of Bertrand’s postulate for yourself.

Then next time we’ll have another change of topic.  We’re going to think about approximating irrational numbers by rationals (Diophantine approximation).  The aim is to get a very good approximation by a rational with very small denominator.  How would you go about finding a good rational approximation to $\sqrt{2}$ or $\pi$, for example?  If you find a good approximation, can you be confident that it’s the best option?  (That is, could there be another rational with smaller denominator that gives a better approximation?)