## Number Theory: Lecture 17

In which we study Legendre’s formula and Bertrand’s postulate.

• Proposition 52 (Legendre’s formula): Let $x \geq 10$ be a real number.  Then $\pi(x) = \pi(\sqrt{x}) - 1 + N(x, \sqrt{x})$.  Moreover, $\displaystyle N(x, \sqrt{x}) = \lfloor x \rfloor - \sum_{i \in P_{\sqrt{x}}} |A_i| + \sum_{\substack{i_1, i_2 \in P_{\sqrt{x}} \\ i_1 < i_2}} |A_{i_1} \cap A_{i_2}| - \sum_{\substack{i_1, i_2, i_3 \in P_{\sqrt{x}} \\ i_1 < i_2 < i_3}} |A_{i_1} \cap A_{i_2} \cap A_{i_3}| + \dotsb + (-1)^{\pi(\sqrt{x})} |\bigcap_{i \in P_{\sqrt{x}}} A_i|$.  We saw that this was basically the inclusion-exclusion principle.
• Lemma 53: For any natural number $n$, we have $\displaystyle \frac{2^{2n}}{2n} \leq \binom{2n}{n} < 2^{2n}$.  This came from considering $(1+1)^{2n}$.
• Lemma 54: Let $x \geq 1$ be real.  Then $\displaystyle \prod_{p \leq x} p \leq 4^x$.  We proved this by induction (having established that it suffices to prove the result for natural numbers $x$), using the key point that $\displaystyle \prod_{k+2 \leq p \leq 2k+1} p \leq \binom{2k+1}{k+1} \leq 2^{2k+1}$.
• Theorem 55 (Bertrand‘s postulate): Let $n$ be a natural number.  Then there is a prime $p$ with $n < p \leq 2n$.  We started the proof by writing $\binom{2n}{n}$ as a product of three things.  We can get upper bounds for two of them, and our aim is to show that the third part is greater than $1$.  We’ll finish this next time.

#### Understanding today’s lecture

You could use Legendre’s formula (well, inclusion-exclusion) to practise computing $\pi(n)$ for some small values of $n$.

Can you finish the proof of Theorem 55?  You could put together the ingredients we’ve collected so far to see where it gets you.

I mentioned that there is a field of study called sieve theory.  In addition to the Wikipedia page, you might also like to look at this blog post by Terry Tao.

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?)