The building blocks of the integers

The prime numbers have a way of popping up in crystallographic conversations, and the recent results[i] on the structure factor of the primes by Matthew de Courcy-Ireland, Fausto Martelli, Salvatore Torquato and Ge Zhang should remind us of the role number theory plays in crystallography. Torquato, for instance, found that the structure factor for primes is characterized by dense Bragg peaks, like a quasicrystal, but positioned at certain rational wavenumbers, like a limit-periodic point pattern.

A positive integer is prime if it is divisible only by 1 and itself; thus 101 is prime because it is divisible only by 1 and itself, while 106 is not prime (it is called composite) as it is divisible by 53 as well as 1 and 106. The first 25 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

Prime numbers have been around a very long time, and the Greeks recognized that the primes were the basic building blocks of the integers. The Fundamental Theorem of Arithmetic says that every composite number is uniquely expressible as a product of powers of primes, and is thus divisible only by the primes in that product. For example, 1,860,824 = 2³ x 7² x 47 x 101 is a product of only those prime powers and therefore is not divisible by any primes other than 2, 7, 47 and 101.

The fact that all positive integers are uniquely composed of prime powers, rather like species of molecules uniquely composed of atoms, has inspired much number theory. For example, if you try factoring large numbers on your pocket calculator you may notice that (1) primes are relatively rare among large numbers and (2) while a typical large number is composite, its largest prime factor is relatively large. (In fact, in 1993, John Kemeny proved that if n is very large, about 69% of the integers between 1 and n have a prime factor larger than √n.)

But a diffraction result suggests that crystallographers might be interested in stepping back and looking at the distribution of primes among the integers. Euclid proved that there are infinitely many primes: if there was a largest prime p, then p! = 1 x 2 x 3 x 4 x ··· x p is divisible by every prime, so p! + 1 is not divisible by any prime, so since every composite number is a product of primes (by the Fundamental Theorem), p! + 1 must itself be prime, contradicting the claim that p is the largest prime.

And in a sense, primes seem to be everywhere. J. P. G. L. Dirichlet proved that if the greatest common divisor of positive integers a and b is 1, then there are infinitely many primes in the infinite set {a + bn: n = 0, 1, 2, 3, 4, ...}. And as a consequence of the Prime Number Theorem - which I’ll get to in a moment - for any real number ε > 0, no matter how small, there exists a positive integer N such that if p > N is prime, then the next prime q satisfies q < (1 + ε)p: from a proportionate point of view, the gaps between successive primes shrink.

But while there are infinitely many primes, they seem to get increasingly sparser among larger and larger integers. For one thing, even if gaps between successive primes shrink in proportionate terms, in absolute terms there are larger and larger gaps between successive prime numbers: for any integer n, the integers n! + 2, n! + 3, ..., n! + n are all composite. And from a density point of view, the Prime Number Theorem of Jacques Hadamard and C. J. de la Vallée Poussin states that if the number of primes less than or equal to an integer n is π(n), then for very large n, π(n) is (proportionately) close to n/ln n.

The distribution of primes seems to be rather irregular, but there are some regularities. For example, in 2004, Ben Green and Terence Tao proved that there are arbitrarily long arithmetic progressions in the primes. Nine years later, Yitang Zhang announced that for some integer k < 70,000,000, there are infinitely many pairs of primes p, q such that q = p + k. The bound on k has been improved substantially since then, and some mathematicians are optimistic that there will soon be an answer to the Twin Primes Problem: are there infinitely many pairs of primes that differ by 2 (such as 3 and 5, 11 and 13, 101 and 103, etc.)? Or are there only finitely many such pairs?

The Twin Primes Problem is a special case of a question that Zhang et al. were concerned with: given a k-tuple of integers (0, a₂, a₃, ..., a_k), with a₂, a₃, ..., a_k > 0, do there exist infinitely many primes p such that p, p + a₂, p + a₃, ..., p + a_k are all prime? In fact, for a given usable k-tuple, are there enough such primes that they can be detected by diffraction (i.e. by a Fourier transform)? While this is impossible for some k-tuples [for any integer n, exactly one of n, n + 2, and n + 4 is divisible by 3, thus excluding (0, 2, 4) as a usable 3-tuple], for other k-tuples they might even be common enough to be detectable by diffraction.

Primes show up almost everywhere in mathematics, and there are many open problems concerning them. “We don’t understand primes very well,” said Paul Erdős (who is also alleged to have said, “It will be another million years, at least, before we understand the primes”). On the other hand, John von Neumann said, “In mathematics you don't understand things. You just get used to them.” That may make mathematicians like everybody else.

For further reading, one of the old warhorses of undergraduate number theory is Niven & Zuckerman’s Introduction to the Theory of Numbers. The grand old book of number theory is probably Hardy & Wright’s An Introduction to the Theory of Numbers. For computational applications, readers may be interested in Donald Knuth’s Art of Computer Programming, volume 2: Seminumerical Algorithms, or the even broader Concrete Mathematics by Graham, Knuth and Patashnik. And Neil Sloane launched an Online Encyclopedia of Integer Sequences, with information on many interesting sequences, from prime numbers to crystal coordination sequences.