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.

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

Like this:

Be the first to like this post.

This entry was posted on November 14, 2011 at 12:14 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Number Theory: Lecture 17”

Number Theory: Lecture 18 « Theorem of the week Says:
November 16, 2011 at 12:36 pm
[...] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 17 [...]
garrymoore Says:
November 26, 2011 at 11:21 am
hi to all theoremoftheweek.wordpress.comers this is my first post and thought i would say hi –
speak soon
garry

Theorem of the week