[Search] |

ABOUT:
[Introduction]POINTERS:
[Texts]## 11: Number theory |

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***/n***Z**
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
*x ^{a}-y^{b}=*1
in integers; the Four Squares Theorem -- every natural number is the sum of
four integer squares -- simply asserts that

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/2^{s} + 1/3^{s} + 1/4^{s} + ...;
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.

- Weil, André: "Number theory, An approach through history", Birkhäuser Boston, Inc., Boston, Mass., 1984 ISBN 0-8176-3141-0
- Ore, Oystein, "Number theory and its history", Dover Publications, Inc., New York, 1988. 370 pp. ISBN 0-486-65620-9
- 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

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

- 11A: Elementary number theory, including continued fractions. For analogues in number fields, see 11R04
- 11B: Sequences and sets (including Fibonacci,...)
- 11C: Polynomials and matrices
- 11D: Diophantine equations. Includes Fermat's Last Theorem
- 11E: Forms and linear algebraic groups See also 19GXX. For quadratic forms in linear algebra, See 15A63
- 11F: Discontinuous groups and automorphic forms See also 11R39,11S37, 14-XX, 22EXX, 14GXX, 14KXX, 22E50, 22E55, 30F35, 32NXX; for relations with quadratic forms, See 11E45
- 11G: Arithmetic algebraic geometry (Diophantine geometry), see also 11DXX, 14-XX, 14GXX, 14KXX
- 11H: Geometry of numbers For applications in coding theory, see 94B75
- 11J: Diophantine approximation, transcendental number theory (including Pi). See also 11K60
- 11K: Probabilistic theory: distribution modulo 1; metric theory of algorithms
- 11L: Exponential sums and character sums (For finite fields, see 11T)
- 11M: Zeta and L-functions: analytic theory
- 11N: Multiplicative number theory
- 11P: Additive number theory; partitions (e.g. Waring's problem)
- 11R: Algebraic number theory: global fields. For complex multiplication, see 11G15. For Galois theory see also 12-XX.
- 11S: Algebraic number theory: local and p-adic fields For Galois theory see also 12-XX.
- 11T: Finite fields and commutative rings (number-theoretic aspects)
- 11U: Connections with logic
- 11Y: Computational number theory, including factorization and primality testing. See also 11-04
- 11Z05: Miscellaneous applications of number theory

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.

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
- 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
- and of course we would be remiss not to suggest Gauss's
*Disquisitiones Arithmeticae*(1801)

Some distinctive resources:

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

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.

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

- Highly recommended: the
**Number Theory Web**. Select the most appropriate site for you: Brisbane, Australia; University of Georgia, USA; Università di Roma Tre, Rome, Italy. - Algebraic Number Theory Preprint server (Illinois)
- Here are the AMS and Göttingen resource pages for area 11.

- Review of classification categories in number theory before 1985
- Listing of open questions with cash rewards offered by Erdös.
- Yet another open Erdös problem.
- Other open questions worth money.
- Why is exp(pi*sqrt(163)) so close to an integer?
- The joys of the number 239
- Fun examples of the "law of small numbers"
- More examples of the "Law of Small Numbers"
- Even more examples of the "Law of Small Numbers"
- A mixed bag of number-theoretic experiments from a recent issue of Mathematics of Computation
- Easy pattern to generate only prime numbers! (ha ha)
- A number theory question was the "hardest IMO problem, ever": When is (a^2+b^2)/(ab+1) an integer?

Last modified 2006/07/02 by Dave Rusin. Mail: