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.

September 2: plan.pdf and intro.pdf: administrivia and “philosophy”/examples

[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.

The CA for Math 229 is~~Yihang Zhu~~~~Adrian Zahariuc~~Tom Lovering. His e-mail address is what you’d guess given that there are~~six~~eight letters before the @.“

faculty legislation requires all instructors to include a statement outlining their policies regarding collaboration on their syllabi” [but apparently does not require us to be all that careful about singular/plural grammar …] — as stated in plan.pdf:for homework, “as usual in our department, you are allowed — indeed encouraged — to collaborate on solving homework problems, but must write up your own solutions.”For the final project or presentation, work on your own even if another student has chosen the same topic. (As with theses etc. it is still OK to ask peers to read drafts of your paper, or see dry runs of your presentation, and make comments.)In all cases, acknowledge sources as usual, including peers in your homework group.

Homework = Exercises 2, 5, 6, due September 11 at 5PM.

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

September 7:
**NO CLASS:**
**UNIVERSITY HOLIDAY** (Labor Day)

September 9:
euler.pdf:
Elementary methods II: The Euler product for *s*>1 and consequences

To make ≪ and ≫ in TeX, writeHomework = Exercises 2, 3, 4, 7, due September\lland\ggrespectively. Pleasedo notwrite<<and>>(which will produce < < and > >)!

September 11:
chebi.pdf:
Cebysev’s method; introduction of Stirling’s approximation,
and of the von Mangoldt function Λ(n) and its sum ψ(x)

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

Homework = Exercises 1, 3, 5, 7, 9, 11 (as it happens),
due September ~~18~~ 21 at 5PM
(may postpone one till September 25).

The introduction of powers ofSeptember 18: psi.pdf: Complex analysis enters the picture via the contour integral formula for ψ(x) and similar sumsiforq=5 (starting at the bottom of page 3) is similar to the trick of summing ever fourth entry in thenth row of Pascal’s triangle by averaging thenth powers of 1+1, 1−1, 1+i, and 1−i. Generalizing this to summing everykth entry again leads naturally to roots of unity and Pontrjagin duality for finite groups.The (overly) fancy way I suggested for identifying the dual of

with Z/mZis to extend the quotient map μ_{m}to a short exact sequence Z→Z/mZ0 → , with the second arrow being multiplication byZ→Z→Z/mZ→ 0m, and then dualize to identify the dualof with the kernel of multiplication byZ/mZmon the dualof ; but the dualZof is just the circle group, so the kernel in question is itsZsubgroup, which is indeed m-torsion. But to justify μ_{m}thatwe would have to extend Pontrjagin duality beyond finite groups to infinite groups likeZ(discrete but not compact) and the circle (compact but not discrete).

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−ζ'/ζ writes (−ζ'/ζ( s)) /sas the Mellin transform of ψ( (evaluated at −x)sif we go by Wikipedia’s normalization), and the inversion formula for recovering ψ(x) would be precisely our contour integral if we were allowed to integrate all the way fromto c−i∞without worrying about convergencr and error estimates. The Laplace inversion formula is in turn closely related with the more familiar formula for inverting the Fourier transform. c+i∞

September 21:
zeta1.pdf:
The functional equation for the Riemann zeta function
using Poisson inversion on theta series;
basic facts about Γ(*s*)
as a function of a complex variable *s*

**Corrected** Oct.4 to fix a typo noted by Nick Jameson:
*u*) > 0 *right* half-plane,
not the upper one [which is the domain of definition for the
associated modular form *u*/*i*)**Corrected** Sep.26 to fix a typo noted by Mark Sellke
[denominator (kk'(k+k'))² was (kk'(k+k')²)].

Euler already guessed the functional equation in some sense: you’ve probably run across the “identity”September 23: More about Poisson summation1 + 2 + 3 + 4 + … = −1/12 (that he may have derived from1 − 2 + 3 − 4 + … = 1/4 , though according to the1 + 2 + 3 + 4 + … page it is not clear whether Euler ever stated the −1/12 version), and −1/12 agrees with the value ofζ(−1) ; he likewise “computed” alternating sums that correspond to(1−2 for other small integers^{1+n}) ζ(−n)n≥0, finding numbers equivalent to ζ(− n) = −1/2, −1/12, 0, 1/120, 0, −1/252,0, 1/240, 0, −1/132, 0, 691/32760, 0 for— and the appearance of 691 surely suggested (if he didn’t notice this earlier) a connection with the values of n= 0, 1, 2, …, 12ζ( that Euler had already obtained. Euler then proved this connection; he even chosen+1)cos(π for then/2)4-periodic fudge factor, which turns out to be right for all complexn! But Riemann was still the first to give a formula for ζ(s) for complexsand to prove the functional equation in this setting.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.

If you like “distributions”, you can express Poisson summation as “a row of deltas∑ is its own Fourier transform” (inner product of any function_{m∈Z}δ_{m}fwith the “row of deltas” is the sum of the values offover the integers; now use Parseval for Fourier transforms).Our special case of the Gaussian works also for complex

u, giving rise to the value atiuof a modular form of weight ½. The “sanity check” for the resulting transformation formulas turns out to be basically equivalent with Quadratic Reciprocity!Even for real

uthere’s more to be said. The functional equation for θ says nothing about θ(1) [which remarkably turns out to beπ ] but does yield the ratio^{¼}/Γ(¾)θ'(1) = −θ(1)/4 , which in turn gives the approximationexp π ≈ 8π − 2 by ignoring all terms of sizeexp(−3π) and smaller. This, together with the Archmiedean approximationπ ≈ 22/7 , explains the first run of 9s inexp(π) − π = 19.999099979… .Another neat example of Poisson summation: if

f(x) = 1 / (x (some constant^{2}+ c^{2})c>0 ), then the Fourier transform of is(π/c) exp(-2πc|y|) (a standard exercise in contour integration, which can also be done by Fourier inversion since the Fourier transform ofexp(-2πc|y|) is an elementary integral); hence the sum of1 / (n over integers n is readily evaluated as^{2}+ c^{2})(π/c) (e using the formula for summing a convergent geometric series. Subtracting the n=0 term^{2πc}+1) / (e^{2πc}−1)f(0) = 1/c and letting c approach zero, we recover Euler’s formula^{2}ζ(2) = π . The^{2}/6c terms in the Laurent expansion of^{2}, c^{4}, c^{6}, etc.(π/c) (e about c=0 then yield the values of^{2πc}+1) / (e^{2πc}−1)ζ(s) fors=4, 6, 8, etc. as rational multiplesof π .^{s}Poisson summation works in the general setting of locally-compact abelian groups: if

fis “any” function on such a groupG, andHis a closed subgroup, then the integral offoverHis (appropriately scaled) the integral of the Fourier transform offover the annihilator ofH. In standard Poisson,G=R,H=Z(which is its own annihilator), and the “integrals” overZare just sums. Tate’s thesis gives a proof of the functional equation of the zeta function of any number fieldKby usingKas the subgroup of the adèles ofK. We won’t gotherein Math 229x, but will note the generalization from( toG,H) = (R,Z)( whereG,H) = (R^{n},L)Lis some lattice inR; the annihilator ofLis then its dual lattice (a.k.a. the “reciprocal lattice” in crystallography).

September 25: Functional equation for ζ(*s*)
[actually ξ(*s*)] cont’d;

review of
more about the Gamma function
as a function of a complex variable
(product formula, Stirling approximation).

Homework = `zeta1` Exercises 1, 2, 8; `gamma` Exercise 5.
(Due 5PM next Friday, October 2. In `zeta1` #1, of course
“analytic continuation” = with the simple pole at *s*=1.)

To spell out the argument suggestd in the previous handout (p.2) that Γ has no zeros: it is enough to showΓ( fors) ≠ 0Re( ; if there were such a zero, we could conclude from the formula fors) > 0B( that ifs_{1},s_{2})(with both s_{1}+s_{2}=sin the right half-plane) then either s_{1},s_{2}Γ( ors_{1}) = 0Γ( , and that would make Γ identically zero by analytic continuation — contradiction. (Alternatively, use Bohr-Mollerup to establish the product formula fors_{2}) = 0Γ( on the positive real axis, and then invoke analytic continuation.)s)

September 28: Functions of finite order (prod.pdf): Hadamard’s product formula and its logarithmic derivative (and a prelude/interlude on the Lindelöf hypothesis, on which see also the “further remarks” on page 4 of the next handout)

Apropos Exercise 5 for the Γ(s) handout: here’s a graph offor S(x) =x−x^{2}+x^{4}−x^{8}+x^{16}−x^{32}+ − …xin [0,0.9995]. (Apply the “magnifying glass” to the top right corner to see the first few oscillations.) The fact thatS(0.995) = 0.50088… > 1/2, together with the functional equation(from which S(x) =x−S(x^{2})S(x) =x−x^{2}+S(x^{4}) >S(x^{4})), suffice to refute the guess thatS(x) approaches 1/2 asxapproaches 1.

September 30:
zeta2.pdf:
The Hadamard products for ξ(*s*) and ζ(*s*);
vertical distribution of the zeros of ζ(*s*).

The notes use (but possibly could state more explicitly) the following facts about the real part, call it, of the (multiplicative) inverse of a complex number r=x/ (x^{2}+y^{2})with x+iyx>0:ris always positive;ris bounded away from zero ifyis bounded andxis in a fixed interval such as [1,2] with both endpoints positive; and for largey(say| ),y| ≥ 1rdecays as1 / asy^{2}| (again assuming thaty| → ∞xis in say [1,2]).

This picture appears without explanation on the web page for John Derbyshire’sPrime Obsession. It is a plot of the Riemann zeta function on the boundary of the rectangle [0.4,0.6]+[0,14.5]iin the complex plane. Since the contour winds around the origin once (and does not contain the points=1, which is the unique pole of ζ(s)), the zeta function has a unique zero inside this rectangle. Since the complex zeros are known to be symmetric about the line Re(s)=1/2, this zero must have real part exactly equal 1/2, in accordance with the Riemann hypothesis.It is known that this first “nontrivial zero” of ζ(

s) occurs ats=1/2+itfort=14.13472514... The pole ats=1 accounts for the wide swath in the third quadrant, which corresponds tosof imaginary part less than 1.Here’s a similar picture for L(

s,χ_{4}) on [0.4,0.6]+[0,11]i. Without a pole in the neighborhood, this picture is less interesting visually. We see the first two nontrivial zeros, with imaginary parts 6.0209489... and 10.2437703...

October 2: free.pdf:
The nonvanishing of ζ(*s*) on the edge σ=1 of the
critical strip, and the classical zero-free region

Homework = `prod` Exercises 1, 7; `zeta2` Exercises 1, 2;
and `free` Exercise 1. All due 5PM next Friday, October 9.

The coefficients 3, 4, 1 of the inequalityOctober 5: pnt.pdf: Conclusion of the proof of the Prime Number Theorem with error bound; the Riemann Hypothesis, and some of its consequences and equivalent statements.3 + 4 cos(θ) + cos(2θ) ≥ 0 may seem “random”/mysterious, but they’re basically just the fourth row1, 4, 6, 4, 1 of Pascal’s triangle, as you can see by writing2 (3 + 4 cos(θ) + cos(2θ)) as a linear combination ofexp( withinθ). n= −2, −1, 0, 1, 2

Homework = Exercise 1

Here’s an expository paper by B. Conrey on the Riemann Hypothesis, which includes a number of further suggestive pictures involving the Riemann zeta function, its zeros, and the distribution of primes.Here’s the Rubinstein-Sarnak paper “Chebyshev’s Bias” (

Experimental Mathematics, 1994).Here’s a bibliography of fast computations of π(

x).

October 7 and 9: lsx.pdf:
*L*(*s*, χ) as an entire function
(where χ is a nontrivial primitive character mod *q*);
Gauss sums, and the functional equation relating
*L*(*s*, χ)*L*(1−*s*, \bar{χ})

[I tried to do the proper HTML thing to get \bar{χ}, but
χ
sets too high a bar…]

Homework = Exercises 1, 2, 3, 6, 11 (this and `pnt` Exercise 1
due Oct.16 at 5PM)

October 12:
**NO CLASS:**
**UNIVERSITY HOLIDAY** (Columbus Day)

October 14: `lsx`, cont’d; pnt_q.pdf:
Product formula for L(s,χ), and ensuing partial-fraction
decomposition of its logarithmic derivative; a (bad!) zero-free
region for L(s,χ), and resulting estimates on ψ(x,χ)
and thus on
ψ(x, a mod q) and π(x, a mod q).
The Extended Riemann Hypothesis and consequences.

October 16 and 19:
free_q.pdf:
The classical region 1−σ ≪ 1/log(q|t|+2)
free of zeros of L(s,χ) with at most one exception β;
the resulting asymptotics for `{\mathscr L}`,
with `\mathscr` defined in the `mathrsfs` package.]

If you were expecting the complex conjugate of χ(*a*)
in formulas 7, 8 (top of page 5), rather than
*a*)

Homework = Exercises 1, 2 of `pnt_q`, 1, 4 of `free_q`;
due Oct.23 at 5PM

October 23:
l1x.pdf:
Closed formulas for L(1, χ) and their relationship with
cyclotomic units, class numbers, and the distribution of
quadratic residues.

Homework = Exercises 1, 2, 3, and the cases *m*=2,3 of Exercise 4;
due Oct.30 at 5PM

[October 26: Outline of possible final projects]

October 28 and 30:
sieve.pdf:
The Selberg (a.k.a. quadratic) sieve and some applications

Concerning the note to Exercise 4:
the *k*=1 case of Schinzel’s conjecture was
stated explicitly by Bunyakovsky as early as 1857.

Homework = Exercises 1, 2 (except the last sentence), 3 due November 6.

November 2:
weyl.pdf:
Introduction to exponential sums; Weyl’s equidistribution theorem;
interlude on “little *o*” notation;
Kuzmin’s bound (from the start of
kmv.pdf,
the rest of which we’ll cover next week)

November 4:
vdc.pdf:
The van der Corput estimates and some applications

Homework = `weyl` Exercises 1, 3, 4, and `vdc` Exercises 2 and 3,
due November 13.

November 9: kmv.pdf: estimates on the mean square of an exponential sum, culminating with the Montgomery-Vaughan inequality (which this year’s edition of Math 229 will state but not prove)

Apropos Beurling's function: here's MathWorld's take on, including a graph on B(x)[−3,3] ; this PDF version of the graph also shows the comparison with sgn(x).In dimension >1, good analogs of β

_{±}that minorize or majorize the characteristic function of a box and have Fourier supports in another box (and likewise for balls) are still quite mysterious.

11/11: Beurling etc., cont’d;
short.pdf:
Start on the Davenport-Erdös bound and the distribution of
short character sums, with some applications

**Correction** (19 November) Nicholas Triantafillou notes a typo in
Exercise 4: the hypothesis should have
*T*_{2}−*T*_{1}**Z**δ^{−1}**Z**δ

For the characterization of the Gaussian distribution by its moments: suppose more generally that μ is a probability measureon . We say that μ has “exponential decay” if there existsR^{n}c>0 such that for allR>0 the complement of theabout the origin has measure R-ball. Then the Fourier transform of μ [which takes any vector O(exp(−cR))yto∫ ] extends to an analytic function on a neighborhood_{Rn}e(⟨x,y⟩) dμ(x)of R^{n}in . Hence if μ and μ' are two probability measures with exponential decay, all of whose moments agree, then the Fourier transform of μ−μ' is an analytic function that vanishes together with all its derivatives at the origin, and is thus identically zero — whenceC^{n}μ−μ' = 0 soμ = μ'. In fact it is sufficient for just μ to have exponential decay, because exponential decay can be detected from the moments. Assume for simplicity

n=1. Then for evenrtherth moment is≪ ∫ , and thus_{R}xexp(−^{r}c|x|)≪ Conversely, if this bound holds for all evenr! /c.^{r}rthen the complement of theabout the origin has measure R-ball≪ for all evenr! / (cR)^{r}r; takingwe find that this measure is r=cR+O(1)≪ , which yields the desired exponential decay with any coefficient less thanR^{½}exp(−cR)c. The same argument works in dimensionn(with the exponent ofRbeingn/2 in that generality).In particular, Gaussian distributions on

RandCare characterized by their moments, as claimed.WARNING Without the condition of exponential decay, it is

nottrue thateveryprobability distribution with finite moments is characterized by those moments. Indeed there are real-valued functionsf, not identically zero, such that∫ for each_{R}x(^{r}fx)dx= 0; we can thus write some multiple of r= 0, 1, 2, …faswith f_{+}−f_{−}and f_{±}> 0∫ , and then_{R}f_{±}(x)dx= 1and f_{+}dxare two different distributions on f_{−}dxRwith the same moments.

November 13: Davenport-Erdös bound and applications, cont’d

Homework = `kmv` Exercises 1, 3, 4, and `short` Exercise 1,
due November 20. (Note the correction above for Exercise 4.)

November 16 and 18:
burgess.pdf:
The Burgess bound on short exponential sums

**Error** near the bottom of page 3: restricting *d* to primes
is not quite enough even when *n*_{0} = 0*h*/*d* = *h'*/*d'**d* and *d'**n*_{0}

Interlude on one reason that we care about small “nonquadratic residues”: given a large primep, finding a singlenwith( is equivalent (modulon/p) = −1factors) with extracting arbitrary square roots mod O(log^{C}p)p. Hence square roots modpcan be extracted in “random polynomial time” (so “RP”), but aren’t yet known to be doable in deterministic polynomial time. Under ERH for the DirichletL-series , the minimal L(s,(·/p))nis, but unconditionally the best we have is O(log^{2}p)for some O(p^{θ})θ > 0 . Currently the smallest such θ is1 / (4 , and this uses the Burgess bounds via an argument given in short.pdf (Proposition 1).e^{½}) + εWrite

p− 1 = 2^{e}qwithqodd. To get the essential equivalence between solving( and extracting square roots modn/p) = −1p: given the latter, extract square rootse−1 times starting from −1 to obtainn, which is a primitive root of unity oforder 2 . Conversely, given^{e}n, we may assumenis a root of unity oforder 2 by replacing it by^{e}n(note that exponentiation mod^{q}pcan be done in polynomial time by repeated squaring); then, to findD^{½}when it exists, writewith D=D_{1}D_{2}D_{1}andD_{2}roots of unity of orderqand 2^{e}respectively (not necessarily primitive; this uses the Euclidean algorithm, which is again polynomial time), and thenD_{1}is the square of its( power so we need only deal withq+1)/2D_{2}. By raising suitable residuesn^{ν}D_{2}to powers (p−1)/2, (p−1)/4, (p−1)/8, …, (p−1)/2^{e}=q(again this is polynomial-time), we can identifyD_{2}with a power ofn, sayn^{α}; the exponent α is even by assumption, and thenn^{α/2}is a square root ofD_{2}so we’re finally done.Here’s a PDF plot of the Burgess exponents

(1 − 1/ forr) θ + (r+1)/4r^{2}, and also the enveloping parabola r= 2, 3, 4, 5, 6, 8, 12, 24−1/16 + 3θ/2 − θ ^{2}= θ − (θ − 1/4) ^{2}= 1/2 − (θ − 3/4) (highlighted on^{2}θ ∈ [1/4, 3/4] ) and the exponents θ and 1/2 corresponding respectively to the trivial and Pólya-Vinogradov bounds (and to Burgess forand r= 1). [For the PostScript source, change the suffix r→ ∞.psin the URL.]Here’s another recent take on the Burgess bounds (by Liangyi Zhao, as part of these notes from a seminar on various classical and modern exponential sum estimates. There are some minor errors here (e.g. the final expression in the third display on page 3 cannot be right since it is identically zero), but this writeup does recite the proof of the key estimate (3.5) on complete character sums starting from Weil’s theorem (RH for curves over finite fields).

November 20:
kloos.pdf:
An application of Weil’s bound on
Kloosterman sums.

**Correction** (29 November) Hannah Larson notes two typos in
Exercise 5:
In the displayed formula for *S _{n}*,
the coefficient

Here are the plots of x y == 256 mod 691 and x y == 691 mod 5077, illustrating the asymptotically uniform distributions studied in this chapter (and also illustrating a bit of mathematical PostScript trickery, as you can see from the source files for the plots for p=691 and p=5077).November 23: many_pts.pdf: How many points can a curve of genus

Final homework =

many_pts_0.pdf: Some explanation (following and somewhat extending the lecture) for the possibly mysterious argument on the bottom of p.3 of themany_ptshandoutHere are some tables of curves of given genus over finite fields with many rational points.

Let

M(_{k}g) be the maximal number of rational points of agenus- curve over the finite fieldgk. Themany_ptshandout cites[Serre 1982-1984] for the theorem that for eachkthe limsup overgofis positive. The result that for each M(_{k}g)/gkthe liminfofis also positive is contained in the paper: M(_{k}g)/gN.D.Elkies, E.W.Howe, A.Kresch, B.Poonen, J.L.Wetherell, and M.E.Zieve: Curves of every genus with many points, II: Asymptotically good families,

Duke Math. J.122#2 (2004), 399-422 (math.NT/0208060 on the arXiv).(This is actually easier than the limsup proof, though it assumes the limsup result as almost a black box — “almost” because we need a somewhat stronger result that the limsup can be attained by a sequence of curves

Cwhose genera are spaced closely enough that there exists some finite_{n}Rwithfor each g(C_{n+1}) /g(C) <_{n}Rn.)

November 30 and December 2:
disc.pdf:
Stark’s analytic lower bound on the absolute value of the discriminant
of a number field (assuming GRH).

**Somewhat expanded, with several typos corrected, December 1 and 2.**

Here are some tables of number fields, compiled by Henri Cohen.

The LMFDB (“

L-functions,ModularForms, and related objectsDataBase”) has much more extensive tables of tables of number fields which contain the PARI database and are complete in some directions; if you find a number field that “should” be contained in the LMFDB (e.g. because the database contains a field of the same degree, signature( , and ramified primes, but withr_{1},r_{2})| larger than yours), send it in for the next revision.D|According to Wikipedia’s article on number-field discriminants, the lowest known root-discriminants of an infinite family of number fields are still the records of about 92.4 for totally imaginary fields

( , and 1059 for totally real onesr_{1}= 0)( , both by Martinet (r_{2}= 0)Invent. Math.1978); but a generation later Hajir and Maire lowered the first bound to under 83.9 (Compositio Math.128(2001) #1, 35-53), and wrote that “it has long been conjectured” thathas an infinite class field tower, which would yield an upper bound of Q(√−1365)√5460 < 73.9 (see the end of this paper, published at about the same time in the Proceedings of the 2000 European Congress of Mathematics).

December 4:
muff.pdf:
Illustration of the
“parity problem”
for Selberg’s sieve, using the function field case for which the
Möbius-function sums greatly simplify thanks to the zeta function
having no zeros. `muff`” =
“μ and `f`unction
`f`ield”.)

So **what’s with the whorls** in the background pattern?
They’re a visual illustration of an *exponential sum*,
that is,
*i* *f*(*n*),
*n* = 1…*N*).*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.