[D66] Peculiar pattern found in ‘random’ prime numbers

[J.N.]

http://www.nature.com/news/peculiar-pattern-found-in-random-prime-numbers-1.19550

Peculiar pattern found in ‘random’ prime numbers

Last digits of nearby primes have ‘anti-sameness’ bias.

    Evelyn Lamb

14 March 2016


Prime numbers — not so randomly distributed?

Two mathematicians have found a strange pattern in prime numbers —
showing that the numbers are not distributed as randomly as theorists
often assume.

“Every single person we’ve told this ends up writing their own computer
program to check it for themselves,” says Kannan Soundararajan, a
mathematician at Stanford University in California, who reported the
discovery with his colleague Robert Lemke Oliver in a paper submitted to
the arXiv preprint server on 11 March1. “It is really a surprise,” he says.

Prime numbers near to each other tend to avoid repeating their last
digits, the mathematicians say: that is, a prime that ends in 1 is less
likely to be followed by another ending in 1 than one might expect from
a random sequence. “As soon as I saw the numbers, I could see it was
true,” says mathematician James Maynard of the University of Oxford, UK.
“It’s a really nice result.”

Although prime numbers are used in a number of applications, such as
cryptography, this ‘anti-sameness’ bias has no practical use or even any
wider implication for number theory, as far as Soundararajan and Lemke
Oliver know. But, for mathematicians, it’s both strange and fascinating.

Not so random

A clear rule determines exactly what makes a prime: it’s a whole number
that can’t be exactly divided by anything except 1 and itself. But
there’s no discernable pattern in the occurrence of the primes. Beyond
the obvious — after the numbers 2 and 5, primes can’t be even or end in
5 — there seems to be little structure that can help to predict where
the next prime will occur.

As a result, number theorists find it useful to treat the primes as a
‘pseudorandom’ sequence, as if it were created by a random-number generator.

But if the sequence were truly random, then a prime with 1 as its last
digit should be followed by another prime ending in 1 one-quarter of the
time. That’s because after the number 5, there are only four
possibilities — 1, 3, 7 and 9 — for prime last digits. And these are, on
average, equally represented among all primes, according to a theorem
proved around the end of the nineteenth century, one of the results that
underpin much of our understanding of the distribution of prime numbers.
(Another is the prime number theorem, which quantifies how much rarer
the primes become as numbers get larger.)

Instead, Lemke Oliver and Soundararajan saw that in the first billion
primes, a 1 is followed by a 1 about 18% of the time, by a 3 or a 7 each
30% of the time, and by a 9 22% of the time. They found similar results
when they started with primes that ended in 3, 7 or 9: variation, but
with repeated last digits the least common. The bias persists but slowly
decreases as numbers get larger.

The k-tuple conjecture

The mathematicians were able to show that the pattern they saw holds
true for all primes, if a widely accepted but unproven statement called
the Hardy–Littlewood k-tuple conjecture is correct. This describes the
distributions of pairs, triples and larger prime clusters more precisely
than the basic assumption that the primes are evenly distributed.

The idea behind it is that there are some configurations of primes that
can’t occur, and that this makes other clusters more likely. For
example, consecutive numbers cannot both be prime — one of them is
always an even number. So if the number n is prime, it is slightly more
likely that n + 2 will be prime than random chance would suggest. The
k-tuple conjecture quantifies this observation in a general statement
that applies to all kinds of prime clusters. And by playing with the
conjecture, the researchers show how it implies that repeated final
digits are rarer than chance would suggest.

At first glance, it would seem that this is because gaps between primes
of multiples of 10 (20, 30, 100 and so on) are disfavoured. But the
finding gets much more general — and even more peculiar. A prime’s last
digit is its remainder when it is divided by 10. But the mathematicians
found that the anti-sameness bias holds for any divisor. Take 6, for
example. All primes have a remainder of 1 or 5 when divided by 6
(otherwise, they would be divisible by 2 or 3) and the two remainders
are on average equally represented among all primes. But the researchers
found that a prime that has a remainder of 1 when divided by 6 is more
likely to be followed by one that has a remainder of 5 than by another
that has a remainder of 1. From a 6-centric point of view, then, gaps of
multiples of 6 seem to be disfavoured.

Paradoxically, checking every possible divisor makes it appear that
almost all gaps are disfavoured, suggesting that a subtler explanation
than a simple accounting of favoured and disfavoured gaps must be at
work. “It’s a completely weird thing,” says Soundararajan.
Mystifying phenomenon

The researchers have checked primes up to a few trillion, but they think
that they have to invoke the k-tuple conjecture to show that the pattern
persists. “I have no idea how you would possibly formulate the right
conjecture without assuming it,” says Lemke Oliver.

First proof that infinitely many prime numbers come in pairs

Without assuming unproven statements such as the k-tuple conjecture and
the much-studied Riemann hypothesis, mathematicians’ understanding of
the distribution of primes dries up. “What we know is embarrassingly
little,” says Lemke Oliver. For example, without assuming the k-tuple
conjecture, mathematicians have proved that the last-digit pairs 1–1,
3–3, 7–7 and 9–9 occur infinitely often, but they cannot prove that the
other pairs do. “Perversely, given our work, the other pairs should be
more common,” says Lemke Oliver.

He and Soundararajan feel that they have a long way to go before they
understand the phenomenon on a deep level. Each has a pet theory, but
none of them is really satisfying. “It still mystifies us,” says
Soundararajan.

    Nature
    doi:10.1038/nature.2016.19550