Prime Numbers and the Riemann Hypothesis Barry Mazur William Stein 1 Contents Preface 5 I The Riemann Hypothesis 11 1 Thoughts about numbers 12 2 What are prime numbers? 15 3 “Named” prime numbers 20 4 Sieves 22 5 Questions about primes 25 6 Further questions about primes 28 7 How many primes are there? 32 8 Prime numbers viewed from a distance 37 9 Pure and applied mathematics 39 10 A probabilistic first guess 41 11 What is a “good approximation”? 45 12 Square root error and random walks 47 13 What is Riemann’s Hypothesis? 49 14 The mystery moves to the error term 51 15 Ces`aro smoothing 52 16 A view of Li(X) π(X) 54 | − | 2 CONTENTS 3 17 The Prime Number Theorem 56 18 The staircase of primes 60 19 Tinkering with the staircase of primes 62 20 Computer music files and prime numbers 65 21 The word “Spectrum” 71 22 Spectra and trigonometric sums 73 23 The spectrum and the staircase of primes 75 24 To our readers of Part I 77 II Distributions 78 25 Slopes of graphs that have no slopes 79 26 Distributions 86 27 Fourier transforms: second visit 92 28 Fourier transform of delta 95 29 Trigonometric series 97 30 A sneak preview of Part III 99 III The Riemann Spectrum of the Prime Numbers 105 31 On losing no information 106 32 From primes to the Riemann spectrum 109 33 How many θ ’s are there? 114 i 34 Further questions about the Riemann spectrum 117 35 From the Riemann spectrum to primes 119 IV Back to Riemann 121 36 Building π(X) from the spectrum 122 37 As Riemann envisioned it 128 4 CONTENTS 38 Companions to the zeta function 135 Endnotes 141 Preface TheRiemannHypothesisisoneofthegreatunsolvedproblemsofmathematics, and the reward of $1,000,000 of Clay Mathematics Institute prize money awaits thepersonwhosolvesit. But—withorwithoutmoney—itsresolutioniscrucial for our understanding of the nature of numbers. There are several full-length books recently published, written for a general audience, that have the Riemann Hypothesis as their main topic. A reader of these books will get a fairly rich picture of the personalities engaged in the pursuit, and of related mathematical and historical issues.1 This is not the mission of the book that you now hold in your hands. We aim—instead—to explain, in as direct a manner as possible and with the least mathematical background required, what this problem is all about and why it is so important. For even before anyone proves this hypothesis to be true (or false!), just getting familiar with it, and with some of the ideas behind it, is exciting. Moreover, this hypothesis is of crucial importance in a wide range of mathematical fields; for example, it is a confidence-booster for computational mathematics: even if the Riemann Hypothesis is never proved, assuming its truth(andthatofcloselyrelatedhypotheses)givesusanexcellentsenseofhow long certain computer programs will take to run, which, in some cases, gives us the assurance we need to initiate a computation that might take weeks or even months to complete. 1See, e.g., The Music of the Primes by Marcus du Sautoy (2003) and Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics by John Derbyshire (2003). 5 6 CONTENTS Figure 1: Peter Sarnak Here is how the Princeton mathematician Peter Sarnak describes the broad impact the Riemann Hypothesis has had2: “TheRiemannhypothesisisthecentralproblemanditimpliesmany, many things. One thing that makes it rather unusual in mathemat- icstodayisthattheremustbeoverfivehundredpapers—somebody should go and count—which start ‘Assume the Riemann hypothe- sis3,’ and the conclusion is fantastic. And those [conclusions] would then become theorems ... With this one solution you would have proven five hundred theorems or more at once.” So, what is the Riemann Hypothesis? Below is a first description of what it is about. The task of our book is to develop the following boxed paragraph into a fuller explanation and to convince you of the importance and beauty of the mathematics it represents. We will be offering, throughout our book, a number of different—but equivalent—ways of precisely formulating this hypothesis (we display these in boxes). When we say that two mathematical statements are “equivalent” we mean that, given the present state of mathematical knowledge, wecanprovethatifeitheroneofthosestatementsistrue,thentheotheristrue. The endnotes will guide the reader to the relevant mathematical literature. 2Seepage222ofThe Riemann hypothesis: the greatest unsolved problem in mathematics byKarlSabbagh(2002). 3Technically,ageneralizedversionoftheRiemannhypothesis(seeChapter38below). CONTENTS 7 What sort of Hypothesis is the Riemann Hypothesis? Consider the seemingly innocuous series of questions: How many prime numbers (2, 3, 5, 7, 11, 13, 17, ...) are • there less than 100? How many less than 10,000? • How many less than 1,000,000? • Moregenerally,howmanyprimesaretherelessthananygiven number X? Riemannproposed, acenturyandhalfago, astrikinglysimple-to-describe “verygoodapproximation”tothenumberofprimeslessthanagivennum- ber X. We now see that if we could prove this Hypothesis of Riemann we wouldhavethekeytoawealthofpowerfulmathematics. Mathematicians are eager to find that key. Figure 2: Raoul Bott (1923–2005). Photograph by George M. Bergman, Cour- tesy of the Department of Mathematics, Harvard University. The mathematician Raoul Bott—in giving advice to a student—once said that whenever one reads a mathematics book or article, or goes to a math lecture, one should aim to come home with something very specific (it can be small, but should be specific) that has application to a wider class of mathematical problems than was the focus of the text or lecture. If we were to suggest some possible specific items to come home with, after reading our book, three key phrases—prime numbers, square-root accurate, and spectrum—would head the list. As for words of encouragement to think hard about the first of these, i.e., prime numbers, we can do no better than to quote a paragraph of Don Zagier’s classic 12-page exposition, The First 50 Million Prime Numbers: 8 CONTENTS Figure 3: Don Zagier “There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey nootherlawthanthatofchance,andnobodycanpredictwherethe next one will sprout. The second fact is even more astonishing, for itstatesjusttheopposite: thattheprimenumbersexhibitstunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision.” Mathematics is flourishing. Each year sees new exciting initiatives that extend andsharpentheapplicationsofoursubject,newdirectionsfordeepexploration— and finer understanding—of classical as well as very contemporary mathemat- ical domains. We are aided in such explorations by the development of more and more powerful tools. We see resolutions of centrally important questions. And through all of this, we are treated to surprises and dramatic changes of viewpoint; in short: marvels. And what an array of wonderful techniques allow mathematicians to do their work: framing definitions; producing constructions; formulating analogies re- lating disparate concepts, and disparate mathematical fields; posing conjectures, that cleanly shape a possible way forward; and, the keystone: providing unas- sailableproofsofwhatisasserted,theideaofdoingsuchathingbeingitselfone of the great glories of mathematics. Number theory has its share of this bounty. Along with all these modes of theoretical work, number theory also offers the pure joy of numerical experi- mentation, which—when it is going well—allows you to witness the intricacy of CONTENTS 9 numbers and profound inter-relations that cry out for explanation. It is strik- ing how little you actually have to know in order to appreciate the revelations offered by numerical exploration. Our book is meant to be an introduction to these pleasures. We take an exper- imental view of the fundamental ideas of the subject buttressed by numerical computations, often displayed as graphs. As a result, our book is profusely illustrated, containing 131 figures, diagrams, and pictures that accompany the text.4 There are few mathematical equations in Part I. This first portion of our book is intended for readers who are generally interested in, or curious about, math- ematical ideas, but who may not have studied any advanced topics. Part I is devoted to conveying the essence of the Riemann Hypothesis and explaining why it is so intensely pursued. It requires a minimum of mathematical knowl- edge, and does not, for example, use calculus, although it would be helpful to know—or to learn on the run—the meaning of the concept of function. Given its mission, Part I is meant to be complete, in that it has a beginning, middle, and end. We hope that our readers who only read Part I will have enjoyed the excitement of this important piece of mathematics. Part II is for readers who have taken at least one class in calculus, possibly a long time ago. It is meant as a general preparation for the type of Fourier analysis that will occur in the later parts. The notion of spectrum is key. Part III is for readers who wish to see, more vividly, the link between the placement of prime numbers and (what we call there) the Riemann spectrum. Part IV requires some familiarity with complex analytic functions, and returns to Riemann’s original viewpoint. In particular it relates the “Riemann spec- trum” that we discuss in Part III to the nontrivial zeroes of the Riemann zeta function. We also provide a brief sketch of the more standard route taken by published expositions of the Riemann Hypothesis. The end-notes are meant to link the text to references, but also to provide more technical commentary with an increasing dependence on mathematical backgroundinthelaterchapters. Referencestotheendnoteswillbeinbrackets. We wrote our book over the past decade, but devoted only one week to it each year (a week in August). At the end of our work-week for the book, each year, we put our draft (mistakes and all) on line to get response from readers.5 We 4WecreatedthefiguresusingthefreeSageMathsoftware(seehttp://www.sagemath.org). Completesourcecodeisavailable,whichcanbeusedtorecreateeverydiagraminthisbook (see http://wstein.org/rh). More adventurous readers can try to experiment with the pa- rameters for the ranges of data illustrated, so as to get an even more vivid sense of how the numbers“behave.” Wehopethatreadersbecomeinspiredtocarryoutnumericalexperimen- tation,whichisbecomingeasierasmathematicalsoftwareadvances. 5See http://library.fora.tv/2014/04/25/Riemann_Hypothesis_The_Million_Dollar_ Challengewhichisalecture—andQ&A—aboutthecompositionofthisbook. 10 CONTENTS thereforeaccumulatedmuchimportantfeedback,corrections,andrequestsfrom readers.6 We thank them infinitely. 6IncludingDanAsimov,BretBenesh,KerenBinyaminov,HaraldB¨ogeholz,Louis-Philippe Chiasson, Keith Conrad, Karl-Dieter Crisman, Nicola Dunn, Thomas Egense, Bill Gosper, Andrew Granville, Shaun Griffith, Michael J. Gruber, Robert Harron, William R. Hearst III, David Jao, Fredrik Johansson, Jim Markovitch, David Mumford, James Propp, Andrew Solomon,DennisStein,andChrisSwenson.