Lecture notes for Math 259: Introduction to Analytic Number Theory (Spring 200[6-]7)

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.

Jan.31: plan.pdf and intro.pdf: administrivia and philosophy/examples
The CA for Math 259 is Jeechul Woo, a graduate student in the mathematics department. The natural guess for his e-mail address is correct.

His sections will take place Thursdays, 6-7 PM in Room 109 of the Science Center.

Feb.2: elem.pdf: Elementary methods I: Variations on Euclid
Homework = Exercises 2, 5, 6. (Exercises 2,6 corrected Feb.4,5, thanks to J.Woo and S.Shah respectively.)

For many more examples of and references for elementary approaches to the distribution of primes and related topics, see Paul Pollack's Ross notes Not Always Buried Deep: Selections from Analytic and Combinatorial Number Theory.

Feb.5: euler.pdf: Elementary methods II: The Euler product for s>1 and consequences
(corrected Feb.5, to fix typo on page 1 [wrong equation number for zeta function, thanks to C.Davis], and to fix a silly typo [``nonlinear linear''] on page 6; and again Feb.8 to improve Exercise 2)
Homework = Exercises 2, 3, 4, 7.

Feb.7 and Feb.9: dirichlet.pdf: Dirichlet characters and L-series; Dirichlet's theorem under the hypothesis that L-series do not vanish at s=1
(Exercises 1,2,3 corrected Feb.8/9 [typos S for P in #1, ``L-series'' changed to ``Dirichlet series'' in #2, clarification for #3], thanks to S.Kominers, J.Lesieutre, S.Shah, and E.Udovina; two minor typos near middle of page 5 fixed Feb.13, thanks to N.Wage)
Homework due Feb.9 = Exercises 1, 3, 7.
Homework due Feb.16 = Exercises 5, 6, 8, 9, 10, 11.

February 21: chebi.pdf: Cebysev's method; introduction of Stirling's approximation, and of the von Mangoldt function \Lambda(n) and its sum \psi(x)
(corrected Feb.21 to fix sign errors on page 2 [the second derivative of log(y) is -1/y2, not 1/y2 -- fortunately this affects only the value of C], thanks to J.Woo; and Feb.22 to give the reference and some background for the Diamond-Erdos theorem mentioned in Exercise 2, thanks to Jeff Lagarias for the pointer)
Homework = Exercises 1, 4, 5, 7.

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: While it soon becomes infeasible to use this method to bring the bounds even closer to 1, one can obtain some noticeable improvements by having the computer optimize the bounds via a suitable linear programming problem. For example, if we use the sixty factors of 5040 instead of the eight factors of 30, we get a linear program with 5040 constraints on 60 variables, and lp_solve soon finds the lower bound 0.94171152000... on liminf(psi(x)/x) [compare with Cebysev's 0.92129202...] by applying Stirling to the sum of cdlog(floor(x/d)!), where d ranges over 41 of the factors of 5040 and the coefficients cd are as follows:
d 1 2 3 5 6 7 12 14 18 20 24 28 35 36 40 42 56 70 72 84 126 144 168 180 210 240 252 280 315 336 360 420 504 560 630 840 1008 1260 1680 2520 5040
cd 1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 1 1 -1 -1 3/2 1/2 -2 1 -1/2 1/2 1 -3/2 5/2 -3/2 1/2 1 -1 1/2 1 -1/2 5/2
Using instead the 120 factors of 55440=11*5040 we obtain a lower bound 0.9583827295956... even closer to 1, from a sum of 108 terms, many of them having more complicated coefficients such as c616=-69/32. Such ``complications'' appear sooner when we seek upper bounds; for instance the following 48 cd's (again with d|5040) yield a sum of cdlog(floor(x/d)!) that bounds limsup((psi(x)-psi(x/100))/x) above by 1.0426267587..., and thus (multiplying by 100/99) yields the upper bound 1.0531583422- on limsup(psi(x)/x) itself:
d 1 2 3 5 6 7 10 12 15 18 20 21 28 30 36 42 45 60 63 72 80 84 90 105 112 126 140 144
cd 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 -2 2 -1 -1 2 -1 -1 4/9 -1/2 37/18 -2 -1 1 -7/18 17/18

d 168 180 210 240 252 280 315 336 360 420 504 560 630 720 840 1008 1260 1680 2520 5040
cd -1/2 -55/18 4 -4/9 -3/2 1/3 13/9 1/6 1 -23/9 5/2 7/6 -31/18 -4/9 23/18 -2 -1/18 -5/3 -5/9 -13/6
I do not know the best bound using factors of 55440, but it seems to be a bit smaller than 1.04 -- at any rate I found one coefficient vector that yields a bound of 1.0393+.

To put all this in context: while these bounds come considerably closer to 1 than Cebysev's, they are only a bit better than what Sylvester announced back in 1892(!) 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 psi(x) or psi(x)-psi(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 |(psi(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 psi(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 \theta(x) and \psi(x). II'', Math. Comp. 30 #134 (1976), 337--360; MR0457375 (56 #15581c)).

February 23: psi.pdf: Complex analysis enters the picture via the contour integral formula for \psi(x) and similar sums
(corrected March 1 to fix an error noted by N.Wage: the estimate at the bottom of page 2 [and later text depending on it, including Exercise 1] neglected an error term T-1xc/(c-1) -- ouch!)
Homework = Exercises 1, 2, 3.

February 26: zeta1.pdf: The functional equation for the Riemann zeta function using Poisson inversion on theta series; basic facts about \Gamma(s) as a function of a complex variable s
(Exercises 6 and 9 corrected Feb.28 and March 7 [spurious factor of sqrt(Pi) in (8), missing factor of 1/i in Ex.9], thanks to E.Udovina; Formula (1) corrected March 10 -- J.Woo noted that the sum over cp had an incorrect start!; Formula (8) corrected March 15 -- Silas Richelson observes that the last exponent should be pi w2/u, not pi w2u)
Homework = Exercises 1, 2, 7 (Feb.26); 8, 9, 10 (Feb.28).

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.

March 2: gamma.pdf: More about \Gamma(s) as a function of a complex variable s: product formula, Stirling approximation, and some consequences
Homework = Exercises 1, 4, 6

Apropos Exercise 5: 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.

March 5: prod.pdf: Functions of finite order: Hadamard's product formula and its logarithmic derivative
(corrected March 10 to fix a typo noted by J.Woo: f0, not f, in the RHS of formula (3))
Homework = Exercises 1, 2, 3, 4

March 7: zeta2.pdf: The Hadamard products for \xi(s) and \zeta(s); vertical distribution of the zeros of \zeta(s).
(corrected March 20,21 to fix errors noted by J.Woo and T.Oey in the first line of the display at the top of page 5)
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 zeta(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 zeta(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(s,\chi4) 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.

March 9: free.pdf: The nonvanishing of \zeta(s) on the edge \sigma=1 of the critical strip, and the classical zero-free region 1-\sigma << 1/log|t| for \zeta(s)
Homework = Exercise 1

March 12: 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, 3

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 \pi(x).

[March 14: the closure of the image under zeta of a vertical line of real part greater than 1; applications: the infimum of |zeta| on such a line, and the supremum (=1.0339080723629239...) of real parts of lines on which zeta takes negative real values.]

March 16: lsx.pdf: L(s,\chi) as an entire function (where \chi is a nontrivial primitive character mod q); Gauss sums, and the functional equation relating L(s,\chi) with L(1-s,\bar\chi)
(Exercise 2 corrected March 21 to fix an error noted by E.Udovina; we certainly cannot expect to get in general an analytic function on the closed half-plane, because even if it does converge there it need not converge in any neighborhood...)
Homework = Exercises 1, 2, 3 (March 16); 4, 5, 12 (March 19)

March 21: pnt_q.pdf: Product formula for L(s,\chi), and ensuing partial-fraction decomposition of its logarithmic derivative; a (bad!) zero-free region for L(s,\chi), and resulting estimates on \psi(x,\chi) and thus on \psi(x, a mod q) and \pi(x, a mod q). The Extended Riemann Hypothesis and consequences.
Homework = Exercises 1, 2, 3

[March 23: the sign of quadratic Gauss sums, via the matrix for the discrete Fourier transform; some familiar and less-familiar connections between quadratic Gauss sums and Quadratic Reciprocity]

April 2: free_q.pdf: The classical region 1-\sigma << 1/log(q|t|+2) free of zeros of L(s,\chi) with at most one exception \beta; the resulting asymptotics for \psi(x, a mod q) etc.; lower bounds on 1-\beta and L(1,\chi), culminating with Siegel's theorem. [The fancy script L is {\mathscr L}, with \mathscr defined in the mathrsfs package.]
(corrected April 3 to remove a spurious phrase in the middle of page 2, improve exposition (and line breaks) in the middle of page 3, and most importantly to insert a missing factor chi(a) in formula (8) on page 5; and April 5, to insert the same factor in Exercise 2 and the word ``Hadamard'' in Exercise 4 [the last two answering questions from E.Udovina])
Homework = Exercises 1, 2 (April 4); Exercise 4 (April 6). [For the second part (``Use this argument...'') of Ex.2, compare with Ex.9 in the Dirichlet chapter.]

April 2: 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.)

April 9: sieve.pdf: The Selberg (a.k.a. quadratic) sieve and some applications
Homework = Exercise 1 (April 9) and Exercises 2 and 3 (April 11).

April 16: weyl.pdf: Introduction to exponential sums; Weyl's equidistribution theorem
Homework = Exercises 1, 2
[Exercise 1: S.Richelson notes that en already has a specific meaning in our context, so changed to dn]

April 18: 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
(Exercise 1 corrected April 25 and 26 to fix three typographical errors noted by E.Udovina: the integral is followed by ``='', not ``-''; the next sum is of 1/n, not 1/N; andin the sum over n' the denominator is just log(n'/n), not the iT power of that.)
Homework = Exercise 1 (April 18) and Exercises 2 and 3 (April 20).

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 23: vdc.pdf: The van der Corput estimates and some applications
Homework = Exercise 1, and your choice of either 2 or the first part of 3.

April 25: burgess.pdf: The Davenport-Erdös and Burgess bounds on short exponential sums, and some applications
Homework = Exercise 1

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 30: 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.

Here are some tables of curves of given genus over finite fields with many rational points, maintained by Gerard van der Geer and Marcel van der Vlugt.
May 7: kloos.pdf: An application of Weil's bound on Kloosterman sums.


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.