Prime numbers have intrigued and fascinated us since antiquity, perhaps because they are within us, if Karen Wynn's 1992 experiment with babies aged five to seven months is to be believed. From early infancy, the concept of number seems to be embedded in the human brain.
One object, then a second,
are placed behind
a screen which, when removed,
does indeed reveal two objects.
The baby expects this outcome:
its attention does not remain
focused for long.
This experiment is similar
to the previous one, except that before
removing the screen, the experimenter
discreetly takes away
one of the two objects;
so only one remains.
The baby's attention then remains fixed
for several dozen seconds.
Among the natural numbers are the primes—numbers such as 2, 3, 5, 7 and 2017 that are divisible by no others. Addressing his fellow physicists in 1922, Godfrey Hardy put it this way:
> "It is the mathematician who has the most direct contact with reality. […] 317 is a prime number, not because we think so, or because our minds are constituted in a certain way, but because it is so, because mathematical reality is made that way."
The earliest results on prime numbers are due to Euclid (around 300 BCE): every integer can be expressed as a product of primes. Prime numbers can therefore be seen as the elementary building blocks from which all other integers are made. Furthermore, an integer's decomposition into prime factors is unique; indeed, this is why, by convention and for convenience, 1 is excluded from the list of prime numbers. Finally, Euclid proved that there are infinitely many primes.
-
Counting, a human activity
-----------------------------
The sequence of prime numbers fascinated Paul Erdős throughout his life. He was born on the banks of the Danube, in Budapest, on 26 March 1913, when his two older sisters, Magda and Clara, died of scarlet fever. Erdős was educated largely at home by his mother, Anna, a mathematics teacher. He remained extraordinarily close to her throughout his life.
His scientific output was exceptional: more than 1,500 papers written with over 500 collaborators, spanning number theory, combinatorics, graph theory, the geometry of numbers, probability, mathematical analysis and set theory. Erdős was not only curious about everything but also exceptionally generous in sharing his ideas; in his eyes, mathematics was a common good.
Erdős had a particular gift for distilling the full difficulty of a general problem into a specific formulation. Even today, it is astonishing to discover that both his results and the methods he devised—even for apparently highly specific problems—are in fact extraordinarily profound and fruitful. He died alone in a hotel room in 1996, a final paradox for someone who was always surrounded by fellow mathematicians.
At the age of 18, Erdős began his research under Leopold Fejér (1880–1959). He studied the following problem—the famous Bertrand's postulate, posed by Joseph Bertrand in the mid-19th century: is there always a prime number between an integer n and its double, 2n? In 1850, Pafnuty Chebyshev confirmed the conjecture with a technically difficult proof. In 1931, Erdős gave a simpler, direct proof. It was the very young mathematician's first spectacular success.
One of the great questions in number theory is this: how many prime numbers are less than a given number x > 0? Let p(x) denote this number. Since no exact, usable formula could be found, more modest attempts were made to approximate p(x).
On the basis of heuristic observations, Adrien-Marie Legendre (1752–1833) and Carl Friedrich Gauss (1777–1855) conjectured that p(x) is "close" to x / ln(x), where ln denotes the natural logarithm (see our feature on logarithms in this issue). This yields a quantitative law describing how primes become scarcer.
In 1896, the conjecture was finally proved independently by Jacques Hadamard (1865–1963) and Charles-Jean de La Vallée-Poussin (1866–1962). Both proofs, however, relied on complex analysis. This raised an important question: could an "elementary" proof of the result be found—one confined to real analysis, without ever invoking complex numbers?
In 1949, Paul Erdős and Atle Selberg gave such a proof, thereby clarifying the respective status of complex and real analysis: although one may still say with Hadamard that "the shortest path between two real quantities necessarily passes through the complex plane", this does not establish a hierarchy between the two theories.
-
The emergence of probability
-----------------------------
In 1934, the young Erdős left Hungary for Cambridge. There he met Hardy and discussed the results Hardy had obtained in 1917 with the Indian prodigy Srinivasa Ramanujan (1887–1920). Hardy and Ramanujan had studied the prime factorization of an integer "chosen at random." How many prime factors does such an integer have? One would expect a number "chosen at random" to be divisible by 2 half the time, by 3 one-third of the time, by 5 one-fifth of the time… Such an integer will be called normal. In particular, a normal integer is neither a square nor a prime number.
In 1917, Hardy and Ramanujan published a paper that may be regarded as marking the birth of probabilistic number theory. It contains the following result: on average, an integer has ln(ln n) prime factors. Moreover, this average is also the typical value. In other words, statistically, the number of prime factors of an integer "chosen at random" depends only on its size—its order of magnitude. This is truly spectacular, and counterintuitive to say the least!
Five years after meeting Hardy, Erdős was in Princeton, New Jersey, in 1939. There he met Marc Kac (1914–1984), a Polish-born mathematician convinced that the Hardy–Ramanujan result was concealing a Gaussian distribution: in his view, the number of prime factors of an integer "chosen at random" should follow a Gaussian distribution (see Tangente 149). A few months later, Erdős and Kac proved this result. More precisely, if F(n) denotes the number of prime factors of n, and F denotes the Gaussian cumulative distribution function, defined by
then the probability that F(n) is less than t approaches F(t) as n increases. Erdős and Kac revealed a Gaussian pattern using integers alone! Natural numbers thus exhibit behavior that can be described by classical probability distributions introduced in contexts far removed from number theory…
This prompts the question of which probabilistic phenomena can be modeled solely from the multiplicative structure of the integers. Brownian motion, which can be described, to a first approximation, as the motion through a fluid of a particle subjected only to collisions with the fluid's small molecules, is a fundamental probabilistic object. It too can be modeled using the distribution of the divisors of integers.
The quantity
measures the area
under the famous
bell-shaped curve.
Simulation
of Brownian
motion.
-
Ideas with striking modern relevance
--------------------------------
In 1946, Erdős obtained another astonishing result, again by studying the prime factorization of a normal integer n. Writing n = p1 p2 … *pk, where p*1 ≤ p2 ≤… ≤ *pk are the prime factors, ln(ln pj ) is "close" to j (for 1 ≤ j ≤ k). It is almost unbelievable: why should the twelfth prime factor of a normal integer n be "close" to ln (ln 12)? Thus the fine multiplicative structure of n* depends statistically only on its size!
The probabilistic ideas arising from the Hardy–Ramanujan and Erdős–Kac results have informed research in probabilistic number theory ever since. The famous—and still open—twin prime conjecture, which states that there are infinitely many prime numbers p such that p + 2 is also prime, has recently been shaken up. In a masterly 2013 paper, Yitang Zhang proved (see Tangente 153) that there are infinitely many pairs of primes (p, q) such that the difference | p – q | is less than 70,000,000. A few months later, James Maynard and, independently, Terence Tao simplified the proof. The collaborative Polymath8 project then reduced the bound from 70,000,000 to 246… still a long way, however, from the conjectured value of 2—which there is reason to believe will remain out of reach until further ideas emerge.
