Mathematicians Discover Prime Conspiracy
A Timely Fix for a Grand Theory of Nature
A Hat Trick of Hat Puzzles
Michael Atiyah’s Imaginative State of Mind
After Black Holes Collide, a Puzzling FlashTwo mathematicians have uncovered a simple, previously unnoticed property of prime numbers — those numbers that are divisible only by 1 and themselves. Prime numbers, it seems, have decided preferences about the final digits of the primes that immediately follow them.
Among the first billion prime numbers, for instance, a prime ending in 9 is almost 65 percent more likely to be followed by a prime ending in 1 than another prime ending in 9. In a paper posted online today, Kannan Soundararajan and Robert Lemke Oliver of Stanford University present both numerical and theoretical evidence that prime numbers repel other would-be primes that end in the same digit, and have varied predilections for being followed by primes ending in the other possible final digits.
“We’ve been studying primes for a long time, and no one spotted this before,” said Andrew Granville, a number theorist at the University of Montreal and University College London. “It’s crazy.”
The discovery is the exact opposite of what most mathematicians would have predicted, said Ken Ono, a number theorist at Emory University in Atlanta. When he first heard the news, he said, “I was floored. I thought, ‘For sure, your program’s not working.’”
This conspiracy among prime numbers seems, at first glance, to violate a longstanding assumption in number theory: that prime numbers behave much like random numbers. Most mathematicians would have assumed, Granville and Ono agreed, that a prime should have an equal chance of being followed by a prime ending in 1, 3, 7 or 9 (the four possible endings for all prime numbers except 2 and 5).
“I can’t believe anyone in the world would have guessed this,” Granville said. Even after having seen Lemke Oliver and Soundararajan’s analysis of their phenomenon, he said, “it still seems like a strange thing.”
Yet the pair’s work doesn’t upend the notion that primes behave randomly so much as point to how subtle their particular mix of randomness and order is. “Can we redefine what ‘random’ means in this context so that once again, [this phenomenon] looks like it might be random?” Soundararajan said. “That’s what we think we’ve done.”
Prime Preferences
Soundararajan was drawn to study consecutive primes after hearing a lecture at Stanford by the mathematician Tadashi Tokieda, of the University of Cambridge, in which he mentioned a counterintuitive property of coin-tossing: If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses.
Waheeda Khalfan
Kannan Soundararajan, left, and Robert Lemke Oliver of Stanford University in February.
Soundararajan wondered if similarly strange phenomena appear in other contexts. Since he has studied the primes for decades, he turned to them — and found something even stranger than he had bargained for. Looking at prime numbers written in base 3 — in which roughly half the primes end in 1 and half end in 2 — he found that among primes smaller than 1,000, a prime ending in 1 is more than twice as likely to be followed by a prime ending in 2 than by another prime ending in 1. Likewise, a prime ending in 2 prefers to be followed a prime ending in 1.
Soundararajan showed his findings to postdoctoral researcher Lemke Oliver, who was shocked. He immediately wrote a program that searched much farther out along the number line — through the first 400 billion primes. Lemke Oliver again found that primes seem to avoid being followed by another prime with the same final digit. The primes “really hate to repeat themselves,” Lemke Oliver said.
Lemke Oliver and Soundararajan discovered that this sort of bias in the final digits of consecutive primes holds not just in base 3, but also in base 10 and several other bases; they conjecture that it’s true in every base. The biases that they found appear to even out, little by little, as you go farther along the number line — but they do so at a snail’s pace. “It’s the rate at which they even out which is surprising to me,” said James Maynard, a number theorist at the University of Oxford. When Soundararajan first told Maynard what the pair had discovered, “I only half believed him,” Maynard said. “As soon as I went back to my office, I ran a numerical experiment to check this myself.”
Lemke Oliver and Soundararajan’s first guess for why this bias occurs was a simple one: Maybe a prime ending in 3, say, is more likely to be followed by a prime ending in 7, 9 or 1 merely because it encounters numbers with those endings before it reaches another number ending in 3. For example, 43 is followed by 47, 49 and 51 before it hits 53, and one of those numbers, 47, is prime.
But the pair of mathematicians soon realized that this potential explanation couldn’t account for the magnitude of the biases they found. Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7. To explain these and other preferences, Lemke Oliver and Soundararajan had to delve into the deepest model mathematicians have for random behavior in the primes.
Random Primes
Prime numbers, of course, are not really random at all — they are completely determined. Yet in many respects, they seem to behave like a list of random numbers, governed by just one overarching rule: The approximate density of primes near any number is inversely proportional to how many digits the number has.
In 1936, Swedish mathematician Harald Cramér explored this idea using an elementary model for generating random prime-like numbers: At every whole number, flip a weighted coin — weighted by the prime density near that number — to decide whether to include that number in your list of random “primes.” Cramér showed that this coin-tossing model does an excellent job of predicting certain features of the real primes, such as how many to expect between two consecutive perfect squares.
Despite its predictive power, Cramér’s model is a vast oversimplification. For instance, even numbers have as good a chance of being chosen as odd numbers, whereas real primes are never even, apart from the number 2. Over the years, mathematicians have developed refinements of Cramér’s model that, for instance, bar even numbers and numbers divisible by 3, 5, and other small primes.
Related Articles:
Together and Alone, Closing the Prime Gap
Working on the centuries-old twin primes conjecture, two solitary researchers and a massive collaboration have made enormous advances over the last six months.Prime Gap Grows After Decades-Long Lull
A year after tackling how close together prime number pairs can stay, mathematicians have now made the first major advance in 76 years in understanding how far apart primes can be.After Prime Proof, an Unlikely Star Rises
Three years ago, Yitang Zhang was virtually unknown. Now his surprise solution to a major problem in number theory has catapulted him to mathematical stardom. Where does he go from here?
These simple coin-tossing models tend to be very useful rules of thumb about how prime numbers behave. They accurately predict, among other things, that prime numbers shouldn’t care what their final digit is — and indeed, primes ending in 1, 3, 7 and 9 occur with roughly equal frequency.
Yet similar logic seems to suggest that primes shouldn’t care what digit the prime after them ends in. It was probably mathematicians’ overreliance on the simple coin-tossing heuristics that made them miss the biases in consecutive primes for so long, Granville said. “It’s easy to take too much for granted — to assume that your first guess is true.”
The primes’ preferences about the final digits of the primes that follow them can be explained, Soundararajan and Lemke Oliver found, using a much more refined model of randomness in primes, something called the prime k-tuples conjecture. Originally stated by mathematicians G. H. Hardy and J. E. Littlewood in 1923, the conjecture provides precise estimates of how often every possible constellation of primes with a given spacing pattern will appear. A wealth of numerical evidence supports the conjecture, but so far a proof has eluded mathematicians.
The prime k-tuples conjecture subsumes many of the most central open problems in prime numbers, such as the twin primes conjecture, which posits that there are infinitely many pairs of primes — such as 17 and 19 — that are only two apart. Most mathematicians believe the twin primes conjecture not so much because they keep finding more twin primes, Maynard said, but because the number of twin primes they’ve found fits so neatly with what the prime k-tuples conjecture predicts.
In a similar way, Soundararajan and Lemke Oliver have found that the biases they uncovered in consecutive primes come very close to what the prime k-tuples conjecture predicts. In other words, the most sophisticated conjecture mathematicians have about randomness in primes forces the primes to display strong biases. “I have to rethink how I teach my class in analytic number theory now,” Ono said.
At this early stage, mathematicians say, it’s hard to know whether these biases are isolated peculiarities, or whether they have deep connections to other mathematical structures in the primes or elsewhere. Ono predicts, however, that mathematicians will immediately start looking for similar biases in related contexts, such as prime polynomials — fundamental objects in number theory that can’t be factored into simpler polynomials.
And the finding will make mathematicians look at the primes themselves with fresh eyes, Granville said. “You could wonder, what else have we missed about the primes?”
This is amazing and very curious! Prime numbers are really fascinating.
Thank you for this beautiful expository article. I wish I could write more in this comment, but I'm in a hurry because I'm now going to try to read the arXiv prepint!
this was not obvious before? even with small primes, you can notice some sort of weird pattern between the prime numbers themselves. one would have thought that mathematicians looked at these weird patterns once and once again…
They used the decimal system, right? How anthropomorphic. I conducted the same research using the binary system and discovered that primes larger than 10 have the probability of 110 0100% to have their last digit equal to 1. Surely this can't be random.
Does this have any impact on the algorithms used for encryption?
If one is seeking a subtle mix of randomness and order, one could do far worse than to have recourse to the concept of a * spin glass * ….
As I read the first paragraph, I wondered if the effect was an artifact of using 10 as the number representation base. Apparently not, as I soon found out.
Each prime, in isolation, is an object which seems to have no remarkable properties other than impoverished divisibility. But taken as a set, there seem to be strange patterns, or hints of patterns, or … some kinds of properties that only become apparent the more of them one has to play with. Of course, being a countably infinite set, we'll never have the whole lot at once, and so may never discover everything there is to be known about them. Or know whether we have or not!
So I wonder, if there are within the primes, links analogous to 'entanglement' between particles in quantum mechanics? This is an analogy, neither assertion or denial of any property of quantum mechanical systems! The Riemann hypothesis (if proved) would be an indication of some such link. I'll stay tuned.
This was noted for mod 4 quite a bit earlier https://www2.bc.edu/~ashav/Papers/ABGS-PrimePairsFinal.pdf. I'm surprised no one checked mod 10.
While we're on the subject of coy conspiracies, one cannot help but observe that — had he lived — today is the day on which Albert Einstein would have turned * 137 * — a number whose siren-song appeal for physicists* is a matter of long (and strange) standing, indeed.
* In addition to the speculated significance of its relationship to the fine-structure constant — of which line of "reasoning", I know but little (and understand less) — it also happens to be the number of the hospital room in which Wolfgang Pauli died!
If we accept the fact of "being prime number" as "probability event" in strict mathematical sense, then the above mentioned result is not surprising, because in the first case -A-( both consecutive primes ending with same digit ) is unconditional event and in the second case -B- ( prime ending with some digit (say 9)is followed by prime ending with same digit) we are dealing with conditional event and consequently with conditional probability for such event. Both probabilities can not be the same, unless both events are independent, and they are evidently not. I think that the catch is in proposition, that being prime number is " well defined " probabilistic event in some probability space. But on the other hand we can from such proposition ( because probabilities are in this case computable ) backward "compute" how much our probabilistic model correspond to real situation.
"But taken as a set, there seem to be strange patterns"
Of course. As the article says – primes are not random, they are fully determined.
However, the patterns for predicting that determination grow tremendously complex as the size of each prime increases, so the practicality, not the possibility, of calculating them by pattern becomes the obstacle.
How irritating! After spending months writing code and identifying this pattern (primes following other primes 9 after 3 etc.) I tried sharing it with a mathematician. He convinced me last summer that many people "smart than I am" have looked at this and I would never get anywhere. Because I didn't go to college and don't share his P.H.D. in math. I hope he hears about this news wherever he is now.
When will math people stop using the word "random"? There is no such thing. We don't have to redefine random. We have to understand that just because we can't tell or predict an outcome (due to our own limitations) doesn't make it random.
I'm 32, and I discovered this in middle school. It's too obvious!
Actually, Doug Smith, you'll find (tongue in cheek) that the Mathematician you spoke to got the idea from you, and published his study shortly thereafter. He had to use a pseudonym so you wouldn't realize that he got the idea from you.
I don't understand this paragraph:
—————
he found that among primes smaller than 1,000, a prime ending in 1 is more than twice as likely to be followed by a prime ending in 2 than by another prime ending in 1. Likewise, a prime ending in 2 prefers to be followed a prime ending in 1.
———-
"A prime ending in 2" ??? The only prime number that ends in 2 is 2. Every other number that ends in 2 is even and greater than 2 and therefore not prime… right?
Doug Smith : I was taking part in a 20 people IT project on my Technical University that lasted for three years. Our professor was acting as a leader in this project. During the first month of this 3 year journey I tried to raise how absurd our data-to-rdbms mapping is and how to make it better. Nobody was listening – as I was the student with lower grades than other that were taking part in this project.
After two years my professor announced that together with top-tier students he figured out a way to make our code/rdbms mapping better. It was EXACTLY what I was proposing 2 years before.
Great article — it's why I love this site
IT is a great discovery and research.Thanks to the patience and dedication of today's young mathematicians.
@Joe D: Earlier in the paragraph they explain that they did the test initially in base 3, that is, using only the digits 0, 1, and 2. Thus 3 and 4 in our decimal system would be written 10 and 11 and so forth.
Joe D: the passage you mention was describing the pattern under base 3.
As a few others have noted….how can a prime end in 2?????? No prime ends in 2 but 2.
Joe D wrote:
"A prime ending in 2" ??? The only prime number that ends in 2 is 2. Every other number that ends in 2 is even and greater than 2 and therefore not prime… right?
That's true in base 10, but not in base 3.
10 base 3 is 3 decimal (prime)
12 base 3 is 5 decimal (prime)
The reason you can tell by looking at the last digit whether a number written in base 10 is divisible by 2 or 5 is because those are the factors of the base (10). Since 3 doesn't have any factors, the last digit of a number written in base 3 doesn't tell you anything about any factors it might have (other than 3).
to: Joe D
I think prime final digits of 1 or 2 study you are referring to is for base 3. Yes, in base 3, a prime can have a final digit of 2. Example: 11 (base 10) equals 102 (base 3)
For Joe D –
When written in ternary (base 3), every prime, except 3,
ends in 1 or 2.
Ending in 1: 7, 13, 19, 31, etc
Ending in 2: 2, 5, 11, 17, 23, 29, etc
Joe D: He was talking about those numbers represented in base-3 (trinary). For instance, 12 (trinary) = 1*3 + 2*1 = 5 (decimal). Since all digit places have odd values (1, 3, 9, 27, etc), every increment to ANY digit flips the parity (evenness) of the number, so half the trinary numbers ending in 2 are even, and half are odd.
Joe D:
It's using base 3, so 11 in base 10 for instance becomes 102 in base 3. All numbers are going to end in 0,1, or 2 and anything ending in 0 would be divisible by 3, just how in base 10 ending in 0 would be divisible by 10. This would leave just 1 and 2 as potential endings for primes.
Joe D:
"A prime ending in 2" ??? The only prime number that ends in 2 is 2. Every other number that ends in 2 is even and greater than 2 and therefore not prime… right?
You've missed right above in the paragraph, where it says they're looking at primes written in BASE 3. Where 5 would be "12", 17 "32" etc.
Benfords Law. 65% sounds right for 4 possibilities. Correct me if I'm wrong.
I can not reproduce the claim about "counterintuitive property of coin-tossing" (try this at home). As I understand it you stated that Alice needed in average 4 coin tosses to see the sequence of Head, Tail and Bob needed 6 tosses to see Head, Head. This is really counterintuive to my beliefs, so I wrote a little python script to reproduce a similar result. The calculated relative probalities are approximately 1/4 which are not counterintuitive. So what did I wrong?
# begin script
import random
alice, bob = 0, 0
head = lambda x: x < 0.5
tail = lambda x: not head(x)
c1 = random.random()
N = 1000000
for _ in xrange(N):
c2 = random.random()
# head = < 0.5, tail >= 0.5
if head(c1) and tail(c2):
alice += 1
if head(c1) and head(c2):
bob += 1
c1 = c2
print(bob, alice)
print("relative probability bob=%f alice=%f" %(bob*1.0/N, alice*1.0/N))
# end script
It outputs:
(248930, 250123)
relative probability bob=0.248930 alice=0.250123
Some folks here are missing what the essence of being a prime means. Prime has to do with the geometry of the number. A number is prime if and only if there is no rectangular array for the number except 1 by something. Therefore the whether a number is prime or not is independent of the base in which it is written. For example, eleven is prime no matter which base it is written in.
The author simply used base 3 as a tool to explore this new, interesting property of primes.
Thanks for this well written article.
Been a long time since I've seen anything new about primes.
Joe D: They were talking about the base 3 expansion of the number. In base 3, a number ending in 2 is not necessarily even. For example, 5 written in base 3 is 12.
Joe D: That part is referring to primes expressed in base 3 – where every number ends in 0, 1, or 2.