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.

September 28:
finish Dirichlet handout; then
psi.pdf: Complex analysis enters the picture via the contour integral formula for $\psi(x)$ and similar sums (a.k.a. Perron’s formula);
start zeta1.pdf: The functional equation for the Riemann zeta function using Poisson summation on theta series; basic facts about Γ(s) as a function of a complex variable s

The contour-integral formula can be regarded as an instance of the formula for inverting the Laplace transform, in the Laplace transform’s guise as the Mellin transform. Indeed partial summation of the Dirichlet series for $-\zeta' / \zeta$ writes $-\frac{\zeta'}{\zeta}(s) / s$ as the Mellin transform of $\psi(x)$ (evaluated at $-s$ if we go by Wikipedia’s normalization), and the inversion formula for recovering $\psi(x)$ would be precisely our contour integral if we were allowed to integrate all the way from $c - i\infty$ to $c + i\infty$ without worrying about convergence and error estimates. The Laplace inversion formula is in turn closely related with the more familiar formula for inverting the Fourier transform.

Euler already guessed the functional equation in some sense: you’ve probably run across the “identity” 1 + 2 + 3 + 4 + … = −1/12 (that he may have derived from 1 − 2 + 3 − 4 + … = 1/4, though according to the 1 + 2 + 3 + 4 + … page it is not clear whether Euler ever stated the −1/12 version), and −1/12 agrees with the value of $\zeta(-1)$; he likewise “computed” alternating sums that correspond to $(1 - 2^{1+n}) \zeta(-n)$ for other small integers $n \geq 0,$ finding numbers equivalent to $\zeta(-n) = -1/2, -1/12, 0, 1/120, 0, -1/252, 0, 1/240, 0, -1/132, 0, 691/32760, 0$ for $n = 0, 1, 2, 3, \ldots$ — and the appearance of 691 surely suggested (if he didn’t notice this earlier) a connection with the values of $\zeta(n+1)$ that Euler had already obtained. Euler then proved this connection; he even chose $\cos(\pi n/2)$ for the 4-periodic fudge factor, which turns out to be right for all complex $n$ ! But Riemann was still the first to give a formula for $\zeta(s)$ for complex $s$ and to prove the functional equation in this setting.

To spell out the argument suggested on p.2 that $\Gamma$ has no zeros: since $s \Gamma(s) = \Gamma(s+1)$ for all $s$, it is enough to show $\Gamma(s) \neq 0$ for ${\rm Re}(s) \gt 0;$ if there were such a zero, we could conclude from the formula for $B(s_1,s_2)$ that if $s_1 + s_2 = s$ (with both $s_1, s_2$ in the right half-plane) then either $\Gamma(s_1) = 0$ or $\Gamma(s_2) = 0,$ and that would make $\Gamma$ identically zero by analytic continuation — contradiction. (Come to think of it, we already get $\Gamma(s) \neq 0$ from Euler’s reflection formula $\left[B(s,1-s) = \right] \Gamma(s) \Gamma(1-s) = \pi \, / \sin (\pi s)$, whose right-hand side surely has no zeros. Alternatively, use Bohr-Mollerup to establish the product formula for $\Gamma(s)$ on the positive real axis, and then invoke analytic continuation.)

You can find David Wilkins’ transcription and English translation of Riemann’s fundamental 1859 paper here. A conjecture equivalent to what we now call the Riemann Hypothesis appears in the middle of page 4 of the translation (numbered 5 in the PDF file because the title appears on page 0); note that in the previous page Riemann set $s=(1/2)+ti.$

Riemann’s proof of $\xi(s) = \xi(1-s)$ (and generalizations such as those we shall develop for Dirichlet L-functions) illustrate the versatile technique of studying an infinite sum by converting it to a definite integral. A few more exotic examples from my own contributions to Mathoverflow and Math Stack Exchange include the evaluation of $\sum_{n=0}^\infty \frac{n! \, (2n)!}{(3n+2)!}$ (MSE 516263) and the asymptotic analysis of $\sum_{k=0}^n {n \choose k} (-1)^k \sqrt{k}$ as $n \to \infty$ (MSE 368212) and $\sum_{n=0}^\infty (-x)^n / n^n$ as $x \to \infty$ (MO 109160).

If you like “distributions”, you can express Poisson summation as “a row of deltas $\sum_{m \in {\bf Z}} \delta_m$ is its own Fourier transform”: the inner product of any function $\,f$ with the “row of deltas” is the sum of the values of $\,f$ over the integers; now use Parseval for Fourier transforms.

Our special case of the Gaussian works also for complex $u$, giving rise to the value at $iu$ of a modular form of weight $1/2$. The “sanity check” for the resulting transformation formulas turns out to be basically equivalent with Quadratic Reciprocity!

Even for real u there’s more to be said. The functional equation for $\theta$ says nothing about $\theta(1)$ [which remarkably turns out to be $\pi^{1/4} / \Gamma(3/4)$] but does yield the ratio $\theta'(1) / \theta(1) = -1/4,$ which in turn gives the approximation $e^\pi \approx 8 \pi - 2$ by ignoring all terms of size $\exp(-3\pi)$ and smaller. This, together with the Archimedean approximation $\pi \approx 22/7$, explains the first run of 9s in $e^\pi - \pi = 19.999099979\ldots$ (see Exercise 10 and XKCD 217).

Another neat example of Poisson summation: if $f(x) = 1 / (x^2+c^2)$ (some constant $c \gt 0$), then the Fourier transform of $\,f$ is $(\pi/c) \exp(-2\pi c |y|)$ (a standard exercise in contour integration, which can also be done by Fourier inversion since the Fourier transform of $\exp(-2\pi c|y|)$ is an elementary integral); hence $\sum_{n\in\bf Z} 1/(n^2+c^2)$ is readily evaluated as $(\pi/c) (e^{2\pi c} + 1) \, / \, (e^{2\pi c} - 1)$ using the formula for summing a convergent geometric series. Subtracting the $n=0$ term $f(0) = 1/c^2$ and letting $c \to 0$, we recover Euler’s formula $\zeta(2) = \pi^2/6$. [This is Exercise 11 in zeta1.] The $c^2, c^4, c^6$, etc. terms in the Laurent expansion of $(\pi/c) (e^{2\pi c} + 1) \, / \, (e^{2\pi c} - 1)$ about $c=0$ then yield the values of $\zeta(s)$ for $s=4, 6, 8,$ etc. as rational multiples of $\pi^s$.

Poisson summation works in the general setting of locally-compact abelian groups: if $\,f$ is “any” function on such a group $G$, and $H \subseteq G$ is a closed subgroup, then $\int_H f$ is (appropriately scaled) the integral of the Fourier transform $\hat f$ of $\,f$ over the annihilator of $H$. In standard Poisson, $G = \bf R$, $H = \bf Z$ (which is its own annihilator), and the “integrals” over $\bf Z$ are just sums. Tate’s thesis gives a proof of the functional equation of the zeta function of any number field $K$ by using $K$ as the subgroup of the adèles of $K$. We won’t go there in Math 229x, but will note the generalization from $(G,H) = ({\bf R}, {\bf Z})$ to $(G,H) = ({\bf R}^n, L)$ where $L$ is some lattice in ${\bf R}^n$; the annihilator of L is then its dual lattice (a.k.a. the “reciprocal lattice” in crystallography). See Exercise 12 in zeta1.

Starting October 7:

NEWSFLASH: OpenAI’s hundreds of new mathematical results include an upper bound of 7/8 on the real part of all zeros of Dirichlet L-series.

Thre is also a much shorter paper showing that a a “Siegel-Landau zero” (of which more anon) must exceed $1 - c/\log q$ for some effective $c > 0$, a much weaker result but still enough to advance or solve many classical problems.

We shall still develop the classical theory, which for now is still needed in many important analogous settings (starting with zeta functions and L-functions for arbitrary number fields), and in any case gives the context for these new developments assuming that they hold up and are eventually absorbed into human understanding of analytic number theory.

The announcement reports that “Over the course of the evaluation, the model was posed approximately 4,000 problems”. We can probably assume that it was asked practically every sufficiently important open problem. In particular it probably tried, and so far failed, to make progress on the Gauss circle problem, Lindelöf conjecture, “etc.”.

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

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.