Lecture notes for Math 229: Introduction to Analytic Number Theory (Spring 200[9-]10)

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.


January 25: plan.pdf and intro.pdf: administrivia and philosophy/examples
The CA for Math 229 is Ana Caraiani, a graduate student in the mathematics department. The natural guess for her e-mail address is correct.

January 27: elem.pdf: Elementary methods I: Variations on Euclid
Homework = Exercises 2, 5, 6, due February 1 in class.

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.

January 29: euler.pdf: Elementary methods II: The Euler product for s>1 and consequences
Homework = Exercises 2, 3, 4, 7, due February 8 in class.

February 1 and February 3: dirichlet.pdf: Dirichlet characters and L-series; Dirichlet's theorem under the hypothesis that L-series do not vanish at s=1
Homework due February 8 = Exercises 1, 3, 7.
Homework due February 17 = Exercises 5, 6, 8, 9 [, 10, 11]. [February 15 is a University holiday, “Presidents' Day”.]

February 5: chebi.pdf: Cebysev's method; introduction of Stirling's approximation, and of the von Mangoldt function \Lambda(n) and its sum \psi(x)

click here For Erdos' simplification of Cebysev's proof of the “Bertrand Postulate”: there exists a prime between x and 2x for all x>1. Adapted from Hardy and Wright, pages 343-344.

Apropos Exercise 2: Already in 1892 Sylvester announced bounds within 4.4% of the PNT using nothing more than log tables, extensive hand computation with factors of 30030 = 2*3*5*7*11*13, and (the crucial ingredient) more detailed analysis of the errors left over when comparing a sum of cdlog(floor(x/d)!) with ψ(x) or ψ(x)-ψ(x/m). His paper is “On arithmetical series, II”, Messenger of Math. (2) 21 (1892), 87--120, and fortunately this volume can be found in the basement of the Science Center library. The bounds [.95694, 1.04423] are claimed towards the end (page 119), after deriving the bounds [.922, 1.0765] (page 99) and [.946,1.0552] (page 106) from similar analysis mod 210 and 2310. Almost a century later N. Costa Pereira combined such ideas with digital computation (again without linear programming) to report a series of bounds culminating with |(ψ(x)/x)-1| < 1/2976 (!) for large enough x, giving the explicit bound 1011 for “large enough” (page 327 of his paper “Elementary estimates for the Chebyshev function psi(x) and the Möbius function M(x)”, Acta Arithmetica 52 (1989), 307-337). One could come arbitrarily close to 1 via the analytic formula for ψ(x) that we'll develop in the next few weeks, but the closest explicit bounds I've seen using that approach are still a bit above 1/1000 (L.Schoenfeld, “Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II”, Math. Comp. 30 #134 (1976), 337--360; MR0457375 (56 #15581c)).

February 8: psi.pdf: Complex analysis enters the picture via the contour integral formula for \psi(x) and similar sums
Homework = Exercises 1, 2, 3.

February 10: 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
Homework = Exercises 1, 2.

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.

Another neat example of Poisson summation: if f(x) = 1 / (x2 + c2) (some constant 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 of exp(-2πc|y|) is an elementary integral); hence the sum of 1 / (n2 + c2) over integers n is readily evaluated as (π/c) (e2πc+1) / (e2πc-1) using the formula for summing a convergent geometric series. Subtracting the n=0 term f(0) = 1/c2 and letting c approach zero, we recover Euler's formula ζ(2) = π2/6. The c2, c4, c6, etc. terms in the Laurent expansion of (π/c) (e2πc+1) / (e2πc-1) about c=0 then yield the values of ζ(s) for s=4, 6, 8, etc. as rational multiples of πs.

February 15 and 17: gamma.pdf: More about Γ(s) as a function of a complex variable s: product formula, Stirling approximation, and some consequences; prod.pdf: Functions of finite order: Hadamard's product formula and its logarithmic derivative
Homework = Gamma 4,5, Hadamard 4

Apropos Exercise 5 for the Γ(s) handout: here's a graph of
S(x) = x - x2 + x4 - x8 + x16 - x32 + - ...
for x in [0,0.9995]. (Apply the “magnifying glass” to the top right corner to see the first few oscillations.) The fact that S(0.995) = 0.50088... > 1/2, together with the functional equation
S(x) = x - S(x2)
(from which S(x) = x - x2 + S(x4) > S(x4)), suffice to refute the guess that S(x) approaches 1/2 as x approaches 1.

February 19: zeta2.pdf: The Hadamard products for ξ(s) and ζ(s); vertical distribution of the zeros of ζ(s).
Homework = Exercises 1, 2

This picture appears without explanation on the web page for John Derbyshire's Prime Obsession. It is a plot of the Riemann zeta function on the boundary of the rectangle [0.4,0.6]+[0,14.5]i in the complex plane. Since the contour winds around the origin once (and does not contain the point s=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 at s=1/2+it for t=14.13472514... The pole at s=1 accounts for the wide swath in the third quadrant, which corresponds to s of imaginary part less than 1.

Here's a similar picture for L(s4) 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...

For more pictures along these lines, see Juan Arias de Reyna's manuscript “X-Ray of Riemann's Zeta function”, Part 1 and Part 2.

February 22: free.pdf: The nonvanishing of ζ(s) on the edge σ=1 of the critical strip, and the classical zero-free region 1-σ ≪ 1/log|t| for ζ(s)
Homework = Exercise 1

February 24: 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.
Homework = Exercises 1, 2

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" (in PostScript, from the journal Experimental Mathematics where the paper appeared in 1994).

Here's a bibliography of fast computations of π(x).

February 26 and March 1: 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,χ) with L(1-s,\barχ)
Homework = Exercises 1, 2, 3 (March 3); 4, 5, 12 (March 12)

March 3: 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.
Homework = Exercises 1 and your choice of Exercise 2 or 3

March 5: 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 ψ(x, a mod q) etc.; lower bounds on 1-\beta and L(1,χ), culminating with Siegel's theorem. [The fancy script L is {\mathscr L}, with \mathscr defined in the mathrsfs package.]
Homework = Exercises 1, 2, 4 [For the second part (“Use this argument...”) of Exercise 2, compare with Exercise 9 in the Dirichlet chapter.]

March 10: l1x.pdf: Closed formulas for L(1,chi) and their relationship with cyclotomic units, class numbers, and the distribution of quadratic residues.
Homework = Exercises 1 and 4. (For the second part of 4, do at least m=2 and m=3.)

[March 12: Efficient numerical computation of series such as ζ(s) via Euler-Maclaurin summation; applications to products and sums such as Πp(p2-2)/p2) and Σp(1/ps). The closure of the image under zeta of a vertical line of real part greater than 1; applications: the infimum of |ζ| on such a line, and the supremum (=1.0339080723629239...) of real parts of lines on which ζ takes negative real values.]


March 22: sieve.pdf: The Selberg (a.k.a. quadratic) sieve and some applications
(corrected March 24: in the third line of text from the bottom of p.3, Q is a sum over factors e of D, not d)
Concerning the note to Exercise 4: I recently learned that the k=1 case of Schinzel's conjecture was stated explicitly by Bunyakovsky as early as 1857.
Homework = Exercises 1,2,3 due March 26. (For the last part of Exercise 2 it may be useful to have notes for the lecture of March 12.)

March 26: weyl.pdf: Introduction to exponential sums; Weyl's equidistribution theorem
Homework = Exercises 1, 2 due March 32. April Fool's... Make that March 36, er, April 5. (For the end of Exercise 1, cf. Exercise 12 in the notes on L(s,χ) and Gauss sums.)

March 29: kmv.pdf: Kuzmin's inequality on sum(e(c_n)) with c_n in a nearly arithmetic progression; 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)
(corrected March 31 to fix a typo (missing 1/(m+z)2 in the next-to-last line of text on page 4)
Homework = Exercises 1, 3, 5, due April 5.

Apropos Beurling's function: here's MathWorld's take on B(x), including a graph on [-3,3]; this PDF version of the graph also shows the comparison with sgn(x).

April 2: vdc.pdf: The van der Corput estimates and some applications
Homework due April 12 = Exercise 1, and your choice of either 2 or the first part of 3.

April 7: kloos.pdf: An application of Weil's bound on Kloosterman sums.
Homework = Exercise 3

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.

April 9: short.pdf: The Davenport-Erdös bound and the distribution of short character sums, with some applications
corrected April 18 to fix a typo noted by J.Booher: in the footnote on page 2, “χ(p)=-1” should have been (and now is) “χ(-1)=-1”
Homework = Exercise 1

April 14: burgess.pdf: The Burgess bound on short exponential sums
corrected April 18 to a typo noted by J.Booher: missing exponent 2r in the second display of page 4 (in |Sχ(m,m+H)|2r);
Exercises added April 19 (with the Remarks on p.5 edited accordingly)

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

April 19: many_pts.pdf: How many points can a curve of genus g have over the finite field of q elements? The zeta function of a curve over a finite field; the Weil and Drinfeld-Vladut bounds, and related matters.
Homework = Exercise 1 (first part) and 2

Here are some tables of curves of given genus over finite fields with many rational points.
disc.pdf: Stark's analytic lower bound on the absolute value of the discriminant of a number field (assuming GRH).
Here are some tables of number fields, compiled by Henri Cohen.
poincare.pdf: Proof of the bound O(nk-1/4+ε) on the coefficients of a PSL2(Z) cusp form of weight 2k, using Poincaré series and bounds on Kloosterman sums

THE END

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

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