 [Search][Subject Index][MathMap][Tour][Help!] # 11: Number theory

## Introduction

Number theory is one of the oldest branches of pure mathematics, and one of the largest. Of course, it concerns questions about numbers, usually meaning whole numbers or rational numbers (fractions).

Elementary number theory involves divisibility among integers -- the division "algorithm", the Euclidean algorithm (and thus the existence of greatest common divisors), elementary properties of primes (the unique factorization theorem, the infinitude of primes), congruences (and the structure of the sets  Z/nZ  as commutative rings), including Fermat's little theorem and Euler's theorem extending it. But the term "elementary" is usually used in this setting only to mean that no advanced tools from other areas are used -- not that the results themselves are simple. Indeed, a course in "elementary" number theory usually includes classic and elegant results such as Quadratic Reciprocity; counting results using the Möbius Inversion Formula (and other multiplicative number-theoretic functions); and even the Prime Number Theorem, asserting the approximate density of primes among the integers, which has difficult but "elementary" proofs. Other topics in elementary number theory -- the solutions of sets of linear congruence equations (the Chinese Remainder Theorem), or solutions of single binary quadratic equations (Pell's equations and continued fractions), or the generation of Fibonacci numbers or Pythagorean triples -- turn out in retrospect to be harbingers of sophisticated tools and themes in other areas.

The remaining parts of number theory are more or less closely allied with other branches of mathematics, and typically use tools from those areas.

For example, many questions in number theory may be posed as Diophantine equations -- equations to be solved in integers -- without much preparation. Catalan's conjecture -- are 8 and 9 the only consecutive powers? -- asks for the solution to  xa-yb=1  in integers; the Four Squares Theorem -- every natural number is the sum of four integer squares -- simply asserts that  x² + y² + z² + w² = n   is solvable for all n. But the attempt to solve these equations requires rather powerful tools from elsewhere in mathematics to shed light on the the structure of the problem. (Even the possibility of analyzing Diophantine equations -- Hilbert's tenth problem -- suggests the use of mathematical logic; Matijasevic's negative solution of that problem guarantees number theorists will never find a complete solution to their analyses!)

We can try to subdivide number theory according to those other tools used. Naturally there is significant overlap, and a single question from elementary number theory often requires tools from many branches of number theory.

"Combinatorial Number Theory" involves the number-theoretic study of objects which arise naturally from counting or iteration. This includes a study of many specific families of numbers -- the binomial coefficients, the Fibonacci numbers, Bernoulli numbers, factorials, perfect squares, partition numbers and so on -- which can be obtained by simple recurrence relations, say, or as values of polynomials. One asks for their factorizations, their congruence properties, their densities, etc. It is very easy to state conjectures in this area which can often be understood without any particular mathematical training, but which can be very difficult to solve; Erdös has left many conjectures of this sort.

"Algebraic Number Theory" extends the concept of "number" to mean an element of some ring, usually the ring of integers in a finite algebraic extension of the rational number field. These arise naturally even when considering elementary topics (e.g. the representation of an integer as a sum of two squares is tantamount to its factorization in the ring  Z[i]  of Gaussian integers) but are also interesting in their own right. In this setting, the familiar features of the natural numbers (e.g. unique factorization) need not hold. The virtue of the machinery introduced -- class groups, discriminants, Galois theory, field cohomology, class field theory, group representations and  L-functions -- is that it allows a reconstruction of some of that order in these new settings.

A key feature of some problems in number theory is the extent to which the behaviour of the problem in integers is reflected in its behaviour modulo p for all primes p, and its behaviour in the real line. The correct construction for the investigation of this phenomenon is usually a local ring such as the p-adic integers. These fields provide an opportunity for unusual forms of analysis (e.g. series converge iff their terms converge to zero -- the calculus student's dream!) Local analysis usually arises as a part of algebraic number theory.

"Analytic Number Theory" involves the study of the Riemann zeta function and other similar functions such as Dirichlet series. The zeta function may be defined on half the complex plane as the sum 1 + 1/2s + 1/3s + 1/4s + ...; its connection with number theory results from its factorization as a product Prod(1 - 1/p^s )^(-1), the product taken over all primes p. Thus for example the distribution of the primes among the integers can be deduced from a good understanding of the behaviour of zeta(s). The Riemann Hypothesis states that zeta(s) is never zero except along the line Re(s)=1/2 (or at the negative even integers). This is arguably the most important open question in mathematics. There are other related functions, useful either for studying the Riemann zeta function or for making similar conclusions about other sets; for example, one may use them to prove the infinitude of primes in candidate linear progressions.

Other areas of number theory are also quite analytical. For example, "additive number theory" asks about ways of expressing an integer N as a sum of integers a_i in a set A. If we set f(z) = Sum exp(2 pi i a_i z), then f(z)^k has exp(2 pi i N z) as a summand iff N is a sum of k of the a_i. This in turn can be deduced from some integration (the integral of exp(a z) around a circle is 0 or not depending on whether a is zero). Thus analytical techniques are used to approach Waring's problem, for example (representing integers as sums of squares, cubes, etc.), and to address other questions with exponential sums. Since these computations are equivalent to work in the rings Z/nZ, there is an interest in the structure of these rings.

One may include in this analytic category the parts of number theory connected with forms (e.g. quadratic forms are quadratic polynomials in several variables). Broadly speaking the goal here is to analyze the possible equivalence classes of functions under groups of symmetries. Even when few analytic tools are used for the analysis of the functions themselves, the groups of interest (e.g. the discontinuous groups acting on the complex upper half-plane) are well understood in areas of analysis.

Also, ideas from analysis (measure theory, dimension) can be used in "probabilistic number theory", in which one studies almost-periodic, pseudo-random, or fractal behaviour of number-theoretic functions.

Finally, a significant amount of analysis is also used in Sieve methods, and other aspects of multiplicative number theory. Here one generalizes the sieve of Eratosthenes to investigate the presence of, say, prime pairs (Brun's sieve) or solutions to the Goldbach conjecture (every even number is a sum of two primes).

"Transcendental number theory" considers proofs of transcendence or algebraicity of numbers, and the extent to which numbers can be approximated by algebraic numbers (say). This has a direct bearing on other fields such as Diophantine equations, for example, since the unsolvability of a Diophantine equation can be deduced from the observation that it would require rational numbers which approximate a real number "too well". Well-known results in this area include the transcendence of pi, which in turn shows the impossibility of squaring the circle.

"Geometric number theory" incorporates all forms of geometry. The classical Geometry of Numbers due to Minkowski begins with statements of Euclidean geometry on lattices (A convex body contains a lattice point if its volume is large enough); by extension this becomes the study of quadratic forms on lattices, and thus a method of investigating regular packings of spheres, say. But one may also investigate algebraic geometry with number theory, that is, one may study varieties such as algebraic curves and surfaces and ask if they have rational or integral solutions (points with rational or integral coordinates). This topic includes the highly successful theory of elliptic curves (where the rational points form a finitely generated group) and finiteness results (e.g. Siegel's, Thue's, or Faltings's) which apply to integral or higher-genus situations.

"Computational number theory" studies the effectiveness of algorithms for computation of number-theoretic quantities. Considerable effort has been expended in primality-testing and integer factorization routines, for example -- procedures which are in principle trivial, but whose naive solution is untenable in large cases. This field also considers integer quantities (e.g the class number) whose usual definition is nonconstructive, and real quantities (e.g. the values of zeta functions) which must be computed with very high precision; thus this overlaps both computer algebra and numerical analysis.

## Applications and related fields

Clearly the separate parts of number theory overlap with other areas of mathematics.

"Combinatorial number theory", of course, overlaps quite a bit with 05: Combinatorics. While here we consider number-theoretic topics involving the binomial coefficients, partitions, and so on, in combinatorics one might be interested in these numbers as real-number sequences, or as tools for counting sets of some type.

Questions in algebraic number theory often require tools of Galois theory; that material is mostly a part of 12: Field theory (particularly the subject of field extensions).

The algebraic structure of the ring of integers is similar to that of other commutative rings such as rings of polynomials. (Most material on polynomials is on the Galois Theory page.)

The sets of solutions in rational numbers to algebraic equations may be viewed as algebraic varieties, and thus studied with tools of 14: Algebraic Geometry. This is particularly true with single equations in two variables (which lead to curves); such equations when of degree 3 (or 4) lead to elliptic curves.

The theory of lattices is arguably one of quadratic forms, which are considered in more detail within Linear Algebra. (Note that these are essentially unrelated to the lattices studied along with Ordered Sets.)

Sequences and series of integers may be viewed as series and sequences of real numbers, and hence studied with tools of analysis.

Lattices can be used to determine patterns for sphere-packing; consult the sphere FAQ.

There is current interest in factoring large integers (and primality testing), in part because of relationships with 94: cryptography.

The discipline of computing numerical answers to problems (e.g. locating the roots of a polynomial) is not number theory at all but Numerical Analysis. Other fields with some overlap as seen in the diagram are areas 20 (Group Theory), 81 (Quantum Theory), 22 (Topological groups), 58 (Global Analysis), 01 (History), 68 (Computer Science), 52 (Convex Geometry), 65 (Numerical Analysis), 03 (Logic), 33 (Special Functions). The diagram manages to show that some parts of number theory are related to fields of algebra (in red), while others involve more discrete mathematics (in purple) or analysis (green).

## Subfields

This is one of the larger fields in the Math Reviews database. Articles in Number Theory were classified with area 10 until 1985, when then subfields were substantially reorganized. (It has more sub-fields than almost any other area!). From 1985-1990 there was a section 11Q: Other arithmetic-analytic topics; that material is now usually classified with fields of analysis. There have been several re-divisions of the overlap of this area with section 12: Field Theory (wholly subsumed in Number Theory until 1959, for example).

Browse all (old) classifications for this area at the AMS.

## Textbooks, reference works, and tutorials

There are many textbooks at all levels, although it is difficult to find texts covering most of the subfields listed above; texts for those smaller areas are of course shown on their pages.

A few suggestions for texts which illustrate some of the breadth of number theory:

• Hardy, G. H.; Wright, E. M.: "An introduction to the theory of numbers", The Clarendon Press, Oxford University Press, New York, 1979. 426 pp. ISBN 0-19-853170-2 and 0-19-853171-0.
• Serre, Jean-Pierre: "A course in arithmetic", Springer-Verlag, New York-Heidelberg, 1973. 115 pp. (A humbling title!)
• Cohn, Harvey: "Advanced number theory", Dover Publications, Inc., New York, 1980. 276 pp. ISBN 0-486-64023-X
• Weil, André: "Number theory, An approach through history", Birkhäuser Boston, Inc., Boston, Mass., 1984 ISBN 0-8176-3141-0
• Ireland, Kenneth F.; Rosen, Michael I.: "A classical introduction to modern number theory", Springer-Verlag, New York, 1990.389 pp. ISBN 0-387-97329-X
• Niven, Ivan; Zuckerman, Herbert S.; Montgomery, Hugh L.: "An introduction to the theory of numbers", John Wiley & Sons, Inc., New York, 1991.529 pp. ISBN 0-471-62546-9

The historically inclined may prefer some basic texts of yesteryear:

• Landau, Edmund, "Vorlesungen über Zahlentheorie" and "Handbuch der Lehre von der Verteilung der Primzahlen", reprinted by Chelsea Publishing Co., New York
• Davenport, Harold, "The higher arithmetic -- An introduction to the theory of numbers", Dover Publications, Inc., New York, 1983. 172 pp. ISBN 0-486-24452-0
• Kronecker, Leopold, "Vorlesungen über Zahlentheorie", Springer-Verlag, Berlin-New York, 1978. 509 pp. ISBN 3-540-08277-8
• Ore, Oystein, "Number theory and its history", Dover Publications, Inc., New York, 1988. 370 pp. ISBN 0-486-65620-9

Some distinctive resources:

• Dickson, Leonard Eugene: "History of the theory of Numbers", Carnegie Institution of Washington publication. no. 256, 1919: a three-volume history and literature review through early 20th century
• "Reviews in number theory, 1940-1972", six volumes (2931 pages!) edited by William J. LeVeque. American Mathematical Society, Providence, R.I., 1974
• "Reviews in number theory, 1973-1983", six volumes (3573 pages!) edited by Richard K. Guy. American Mathematical Society, Providence, RI, 1984. ISBN 0-8218-0218-6
• (A "Reviews in number theory, 1984-1996" is now also available; further information not available right now).
• Guy, Richard K.: "Unsolved problems in number theory", Springer-Verlag, New York, 1994. 285 pp. ISBN 0-387-94289-0 (2nd edition)

Among other resources we should mention a mailing list NMBRTHRY; archives are available.

## Software and tables

Nigel Smart has written a brief survey of the key packages for the Sept. 1995 issue of the LMS Newsletter; those packages mentioned include

• KANT, a system for "Computational Algebraic Number Theory"
• SIMATH, especially designed for number theoretic purposes.
• Pari, a program library and/or calculator for number theory and elliptic curves (d'après H. Cohen)
• Lidia, a C++ library with number-theoretic functions, your choice of underlying multiprecision kernel (freelip, gmp, libI, ...)
• The Magma system is well suited to number-theoretic and other algebraic structures.
The general-purpose programs he mentions (Maple, Mathematica) are discussed in 68Q40: Symbolic computation.

A selection of software for primes

See also section 11Y: Computational number theory for issues regarding the current limits of computability in number theory (especially regarding factorizations and primality testing).