Universitext - The World Scientific

ContentsixPart BVII The Arithmetic of Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Quadratic Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2The Hilbert Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3The Hasse–Minkowski Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4Supplements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .291291303312322324325VIII The Geometry of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Minkowski’s Lattice Point Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Proof of the Lattice Point Theorem; Other Results . . . . . . . . . . . . . . . .4Voronoi Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Densest Packings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Mahler’s Compactness Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .327327330334342347352357360362IXThe Number of Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Finding the Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Chebyshev’s Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Proof of the Prime Number Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . .4The Riemann Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Generalizations and Analogues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Alternative Formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7Some Further Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .363363367370377384389392394395398XA Character Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Primes in Arithmetic Progressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Characters of Finite Abelian Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Proof of the Prime Number Theorem for Arithmetic Progressions . . .4Representations of Arbitrary Finite Groups . . . . . . . . . . . . . . . . . . . . . .5Characters of Arbitrary Finite Groups . . . . . . . . . . . . . . . . . . . . . . . . . .6Induced Representations and Examples . . . . . . . . . . . . . . . . . . . . . . . . .7Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10 Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .399399400403410414419425432443444

xContentsUniform Distribution and Ergodic Theory . . . . . . . . . . . . . . . . . . . . . . .1Uniform Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Discrepancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Birkhoff’s Ergodic Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Additional Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .447447459464472483488490492XII Elliptic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Elliptic Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2The Arithmetic-Geometric Mean . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Elliptic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4Theta Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Jacobian Elliptic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6The Modular Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .493493502509517525531536539XIII Connections with Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1Sums of Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3Cubic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4Mordell’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5Further Results and Conjectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Some Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7Further Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8Selected References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .541541544549558569575581584586XINotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592

Preface to the Second EditionUndergraduate courses in mathematics are commonly of two types. On the one handthere are courses in subjects, such as linear algebra or real analysis, with which it isconsidered that every student of mathematics should be acquainted. On the other handthere are courses given by lecturers in their own areas of specialization, which areintended to serve as a preparation for research. There are, I believe, several reasonswhy students need more than this.First, although the vast extent of mathematics today makes it impossible for anyindividual to have a deep knowledge of more than a small part, it is important to havesome understanding and appreciation of the work of others. Indeed the sometimessurprising interrelationships and analogies between different branches of mathematicsare both the basis for many of its applications and the stimulus for further development. Secondly, different branches of mathematics appeal in different ways and requiredifferent talents. It is unlikely that all students at one university will have the sameinterests and aptitudes as their lecturers. Rather, they will only discover what theirown interests and aptitudes are by being exposed to a broader range. Thirdly, manystudents of mathematics will become, not professional mathematicians, but scientists,engineers or schoolteachers. It is useful for them to have a clear understanding of thenature and extent of mathematics, and it is in the interests of mathematicians that thereshould be a body of people in the community who have this understanding.The present book attempts to provide such an understanding of the nature andextent of mathematics. The connecting theme is the theory of numbers, at first sightone of the most abstruse and irrelevant branches of mathematics. Yet by exploringits many connections with other branches, we may obtain a broad picture. The topicschosen are not trivial and demand some effort on the part of the reader. As Euclidalready said, there is no royal road. In general I have concentrated attention on thosehard-won results which illuminate a wide area. If I am accused of picking the eyes outof some subjects, I have no defence except to say “But what beautiful eyes!”The book is divided into two parts. Part A, which deals with elementary numbertheory, should be accessible to a first-year undergraduate. To provide a foundation forsubsequent work, Chapter I contains the definitions and basic properties of variousmathematical structures. However, the reader may simply skim through this chapter

xiiPrefaceand refer back to it later as required. Chapter V, on Hadamard’s determinant problem,shows that elementary number theory may have unexpected applications.Part B, which is more advanced, is intended to provide an undergraduate with someidea of the scope of mathematics today. The chapters in this part are largely independent, except that Chapter X depends on Chapter IX and Chapter XIII on Chapter XII.Although much of the content of the book is common to any introductory workon number theory, I wish to draw attention to the discussion here of quadratic fieldsand elliptic curves. These are quite special cases of algebraic number fields and algebraic curves, and it may be asked why one should restrict attention to these specialcases when the general cases are now well understood and may even be developedin parallel. My answers are as follows. First, to treat the general cases in full rigourrequires a commitment of time which many will be unable to afford. Secondly, thesespecial cases are those most commonly encountered and more constructive methodsare available for them than for the general cases. There is yet another reason. Sometimes in mathematics a generalization is so simple and far-reaching that the specialcase is more fully understood as an instance of the generalization. For the topicsmentioned, however, the generalization is more complex and is, in my view, morefully understood as a development from the special case.At the end of each chapter of the book I have added a list of selected references,which will enable readers to travel further in their own chosen directions. Since theliterature is voluminous, any such selection must be somewhat arbitrary, but I hopethat mine may be found interesting and useful.The computer revolution has made possible calculations on a scale and with aspeed undreamt of a century ago. One consequence has been a considerable increasein ‘experimental mathematics’—the search for patterns. This book, on the other hand,is devoted to ‘theoretical mathematics’—the explanation of patterns. I do not wish toconceal the fact that the former usually precedes the latter. Nor do I wish to concealthe fact that some of the results here have been proved by the greatest minds of the pastonly after years of labour, and that their proofs have later been improved and simplifiedby many other mathematicians. Once obtained, however, a good proof organizes andprovides understanding for a mass of computational data. Often it also suggests furtherdevelopments.The present book may indeed be viewed as a ‘treasury of proofs’. We concentrateattention on this aspect of mathematics, not only because it is a distinctive featureof the subject, but also because we consider its exposition is better suited to a bookthan to a blackboard or a computer screen. In keeping with this approach, the proofsthemselves have been chosen with some care and I hope that a few may be of interesteven to those who are no longer students. Proofs which depend on general principleshave been given preference over proofs which offer no particular insight.Mathematics is a part of civilization and an achievement in which human beingsmay take some pride. It is not the possession of any one national, political or religiousgroup and any attempt to make it so is ultimately destructive. At the present timethere are strong pressures to make academic studies more ‘relevant’. At the same time,however, staff at some universities are assessed by ‘citation counts’ and people arepaid for giving lectures on chaos, for example, that are demonstrably rubbish.

PrefacexiiiThe theory of numbers provides ample evidence that topics pursued for their ownintrinsic interest can later find significant applications. I do not contend that curiosityhas been the only driving force. More mundane motives, such as ambition or thenecessity of earning a living, have also played a role. It is also true that mathematicspursued for the sake of applications has been of benefit to subjects such as numbertheory; there is a two-way trade. However, it shows a dangerous ignorance of historyand of human nature to promote utility at the expense of spirit.This book has its origin in a course of lectures which I gave at the VictoriaUniversity of Wellington, New Zealand, in 1975. The demands of my own researchhave hitherto prevented me from completing it, although I have continued to collectmaterial. If it succeeds at all in conveying some idea of the power and beauty of mathematics, the labour of writing it will have been well worthwhile.As with a previous book, I have to thank Helge Tverberg, who has read most of themanuscript and made many useful suggestions.The first Phalanger Press edition of this book appeared in 2002. A revised edition,which was reissued by Springer in 2006, contained a number of changes. I removedan error in the statement and proof of Proposition II.12 and filled a gap in the proofof Proposition III.12. The statements of the Weil conjectures in Chapter IX and of aresult of Heath-Brown in Chapter X were modified, following comments by J.-P. Serre.I also corrected a few misprints, made many small expository changes and expandedthe index.In the present edition I have made some more expository changes and haveadded a few references at the end of some chapters to take account of recent developments. For more detailed information the Internet has the advantage over abook. The reader is referred to the American Mathematical Society’s MathSciNet(www.ams.org/mathscinet) and to The Number Theory Web maintained by KeithMatthews (www.maths.uq.edu.au/ krm/).I am grateful to Springer for undertaking the commercial publication of my bookand hope you will be also. Many of those who have contributed to the production ofthis new softcover edition are unknown to me, but among those who are I wish to thankespecially Alicia de los Reyes and my sons Nicholas and Philip.W.A. CoppelMay, 2009Canberra, Australia

IThe Expanding Universe of NumbersFor many people, numbers must seem to be the essence of mathematics. Numbertheory, which is the subject of this book, is primarily concerned with the propertiesof one particular type of number, the ‘whole numbers’ or integers. However, thereare many other types, such as complex numbers and p-adic numbers. Somewhat surprisingly, a knowledge of these other types turns out to be necessary for any deeperunderstanding of the integers.In this introductory chapter we describe several such types (but defer the study ofp-adic numbers to Chapter VI). To embark on number theory proper the reader mayproceed to Chapter II now and refer back to the present chapter, via the Index, only asoccasion demands.When one studies the properties of various types of number, one becomes awareof formal similarities between different types. Instead of repeating the derivations ofproperties for each individual case, it is more economical – and sometimes actuallyclearer – to study their common algebraic structure. This algebraic structure may beshared by objects which one would not even consider as numbers.There is a pedagogic difficulty here. Usually a property is discovered in one contextand only later is it realized that it has wider validity. It may be more digestible toprove a result in the context of number theory and then simply point out its widerrange of validity. Since this is a book on number theory, and many properties werefirst discovered in this context, we feel free to adopt this approach. However, to makethe statements of such generalizations intelligible, in the latter part of this chapter wedescribe several basic algebraic structures. We do not attempt to study these structuresin depth, but restrict attention to the simplest properties which throw light on the workof later chapters.0 Sets, Relations and MappingsThe label ‘0’ given to this section may be interpreted to stand for ‘0ptional’. We collecthere some definitions of a logical nature which have become part of the common language of mathematics. Those who are not already familiar with this language, and whoare repelled by its abstraction, should consult this section only when the need arises.W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext,DOI: 10.1007/978-0-387-89486-7 1, Springer Science Business Media, LLC 20091

2I The Expanding Universe of NumbersWe will not formally define a set, but will simply say that it is a collection ofobjects, which are called its elements. We write a A if a is an element of the set Aand a / A if it is not.A set may be specified by listing its elements. For example, A {a, b, c} is the setwhose elements are a, b, c. A set may also be specified by characterizing its elements.For example,A {x R : x 2 2}is the set of all real numbers x such that x 2 2.If two sets A, B have precisely the same elements, we say that they are equal andwrite A B. (If A and B are not equal, we write A B.) For example,{x R : x 2 1} {1, 1}.Just as it is convenient to admit 0 as a number, so it is convenient to admit theempty set , which has no elements, as a set.If every element of a set A is also an element of a set B we say that A is a subsetof B, or that A is included in B, or that B contains A, and we write A B. We saythat A is a proper subset of B, and write A B, if A B and A B.Thus A for every set A and A if A . Set inclusion has the followingobvious properties:(i) A A;(ii) if A B and B A, then A B;(iii) if A B and B C, then A C.For any sets A, B, the set whose elements are the elements of A or B (or both) iscalled the union or ‘join’ of A and B and is denoted by A B:A B {x : x A or x B}.The set whose elements are the common elements of A and B is called the intersectionor ‘meet’ of A and B and is denoted by A B:A B {x : x A and x B}.If A B , the sets A and B are said to be disjoint.BABAA BA BFig. 1. Union and Intersection.

0 Sets, Relations and Mappings3It is easily seen that union and intersection have the following algebraic properties:A A A,A B B A,(A B) C A (B C),(A B) C (A C) (B C),A A A,A B B A,(A B) C A (B C),(A B) C (A C) (B C).Set inclusion could have been defined in terms of either union or intersection, sinceA B is the same as A B B and also the same as A B A.For any sets A, B, the set of all elements of B which are not also elements of A iscalled the difference of B from A and is denoted by B\A:B\A {x : x B and x / A}.It is easily seen thatC\(A B) (C\A) (C\B),C\(A B) (C\A) (C\B).An important special case is where all sets under consideration are subsets of agiven universal set X . For any A X , we have A A,X A X, A ,X A A.The set X\A is said to be the complement of A (in X ) and may be denoted by A c forfixed X . Evidently c X,X c ,A Ac X, A Ac ,(Ac )c A.By taking C X in the previous relations for differences, we obtain ‘De Morgan’slaws’:(A B)c Ac B c , (A B)c Ac B c .Since A B (Ac B c )c , set intersection can be defined in terms of unions andcomplements. Alternatively, since A B (Ac B c )c , set union can be defined interms of intersections and complements.For any sets A, B, the set of all ordered pairs (a, b) with a A and b B is calledthe (Cartesian) product of A by B and is denoted by A B.Similarly one can define the product of more than two sets. We mention only onespecial case. For any positive integer n, we write An instead of A · · · A for the setof all (ordered) n-tuples (a1 , . . . , an ) with a j A (1 j n). We ca

The book is divided into two parts. Part A, which deals with elementary number theory, should be accessible to a first-yearundergraduate. To provide a foundation for subsequent work, Chapter I contains the definitions and basic properties of various mathematical structures.