If you find a mistake, omission, etc., please let me know by e-mail.

The orange ball marks our current location in the course.

For an explanation of the background pattern, skip ahead to the end of the page.

These online lecture notes use MathJax. You might have to change browser for the formulas to look right. Safari seems to work.

The dictum “Much have I learned from my teachers, more from my colleagues, and most of all from my students” is from Tractate Taanit 7a of the Babylonian Talmud, quoting Rabbi Hanina.

[also: which if any of 8675309, 6060842, 6654321, and 7184981043 is prime, and how surprised might you be if one of them is prime, or half of a prime pair? Thanks to Jordan Ellenberg and David Farmer for noting the prime and prime pair respectively. (Turns out that I had already seen the twin-prime observation in the mouse-over text for xkcd comic #1047: Approximations.)]

[See also: OEIS Sequence A006880 ${} = \pi(10^n)$ for $0 \leq n \leq 22$, extended to $n \leq 29$ here. The last two terms (which are only a few years old) required both nontrivial algorithms and significant computational resources. The sequence $\{p_n\} = 2, 3, 5, 7, 11, \ldots$ itself is #40. The subsequence I put on the board is $$ 2, 3, 5, 7, 11, 13, 17, 19, \ldots, 113, 127, \ldots, 8675309, 8675311, \ldots, 2^{136279841} - 1, \ldots .] $$ The CA for Math 229 is Daishi Kiyohara.

My Office hours will be most Tuesdays, 8:00–9:30 PM in the Lowell House Dining Hall, starting September 15. Exception: there will be neither office hours nor a problem set due the week of September 22–26.

In each case we shall give explicit error estimates, e.g. for PNT we shall show $$ \pi(x) = \frac{x}{\log x} \bigl( 1 + E(x) \bigr) $$ for some explicit function $E$ such that $E(x) \to 0$ as $x \to \infty.$

We start by introducing some of our conventions, ideas, and tools in the context of more elementary partial results, starting with Euclid’s argument for $\pi(x) \to \infty$ as $x \to \infty.$ Note that for most $a,q$ even the fact that $\pi(x; a \bmod q) \to \infty$ as $x \to \infty,$ though classical, is much more recent than Euclid: it’s a celebrated theorem of Dirichlet that is not yet 200 years old.

Homework = elem Exercises 1, 6, and 7, and euler Exercises 4, 6, and 7, due September 15 at midnight (12:00 PM, not 0:00 AM).

For many more examples of and references for elementary approaches to the distribution of primes and related topics, see Paul Pollack’s book Not Always Buried Deep: A Second Course in Elementary Number Theory.

Here is XKCD’s haiku rendition of Euclid’s proof. (CW: b-word.) It’s not quite right — can you remove the last word and use those two syllables to fix the proof? — “But, hey, it’s a hallucination.”

September 16: dirichlet.pdf: Dirichlet characters and L-series; Dirichlet’s theorem under the hypothesis that L-series do not vanish at $s=1$

The introduction of powers of $i$ for $r=5$ (starting at the bottom of page 3) is similar to the trick of summing every fourth entry in the $n$th row of Pascal’s triangle by averaging $(1+1)^n$, $(1-1)^n$, $(1+i)^n$, and $(1-i)^n$. Generalizing this to summing every $k$th entry again leads naturally to roots of unity and Pontrjagin duality for finite groups.

What we call the “inverse [discrete] Fourier transform” in the middle of p.5 is sometimes called the plain “[discrete] Fourier transform”, possibly with the factor of $|G|^{-1}$ omitted or replaced by $|G|^{-1/2}$. (There is a similar diversity of terminology for Fourier series and Fourier transforms.) I don’t think that any choice is “correct”, or even so dominant in the literature as to make all others look “wrong”; I regard any such choice as acceptable as long as it is introduced explicitly and used consistently.

One (overly) fancy way to identify the dual of ${\bf Z}/m{\bf Z}$ with μ$_m$ is to extend the quotient map ${\bf Z} \to {\bf Z}/m{\bf Z}$ to a short exact sequence $0 \to {\bf Z} \stackrel{m}{\to} {\bf Z} \to {\bf Z}/m{\bf Z} \to 0$, with the second arrow being multiplication by $m$, and then dualize to identify the dual of ${\bf Z}/m{\bf Z}$ with the kernel of multiplication by $m$ on the dual of $\bf Z$; but the dual of $\bf Z$ is just the circle group, so the kernel in question is its $m$-torsion subgroup, which is indeed μ$_m$. But to justify that we would have to extend Pontrjagin duality beyond finite groups to infinite groups like $\bf Z$ (discrete but not compact) and the circle (compact but not discrete).

September 21: chebi.pdf: Cebysev’s method; introduction of Stirling’s approximation, and of the von Mangoldt function $\Lambda(n)$ and its sum $\psi(x)$

The inequality ${2x \choose x} \geq \prod_{x \lt p\leq 2x} p$ does not quite give $\psi(2x) - \psi(x) \lt x \log 2$ for $x \in \bf Z$, because it does account for the contributions to $\psi(2x) - \psi(x)$ of terms $\Lambda(n)$ with $n = p^k$ and $k \geq 2$. But our formula for $\log \lfloor x \rfloor !$ does give $\log {2x \choose x} \geq \psi(2x) - \psi(x)$, because each term $\Lambda(n) \, (\lfloor 2x/n \rfloor - 2 \lfloor x/n \rfloor)$ is nonnegative, and those with $n \lt x \leq 2n$ have $(\lfloor 2x/n \rfloor - 2 \lfloor x/n \rfloor) = 1$ and thus sum to $\psi(2x) - \psi(x)$.

Keith Conrad (who unlike me can read Russian, not just sound it out) writes that the trick of factoring $2n \choose n$ “was Erdos’s simplification to the proof of bounds on $\psi(x)$ […] Chebyshev never used binomial coefficients.” It still seems plausible that Chebyshev started with $2n \choose n$ but didn’t mention it in his 1852 paper (in French) because it not only gives worse bounds than he obtained using another combination of values of $\log (c_i n)!$ but also does not quite prove Bertrand’s postulate directly (though 80 years later Erdös did give a proof starting from the factorization of $2n \choose n$; this Wikipedia page gives a proof along these lines).

Here is a scan of Ralph B. Boas’ “spelling lesson”, from the College Math J. 15 #3 (June 1984), page 217.

*****************************************************************************************

So what’s with the whorls in the background pattern? They’re a visual illustration of an exponential sum, that is, $\sum_{n=1}^N \exp (i f(n))$. Even simple functions $f$ can give rise to interesting behavior and/or important open problems as we vary N. What function $f$ produced the background for this page? See here for more information.