For those who don't wish to read all the news fluff to hear about a mathematical discovery:[1]
Abstract. We show that there exists pairs of consecutive primes less than x whose difference is larger than t(1+o(1))(log x)(log log x)(log log log log x)(log log log x)⁻² for any fixed t. This answers a well-known question of Erdős.
Their "key proposition", as stated, is:[2]
Proposition 5. Fix δ > 0. Let m < Uz⁻¹(log₂ x)⁻² be even and let Iₘ ⊆ [x/2, x] be an interval of at least δ|ℝₘ| log x.
Then for x > x₀ (δ, C_U) there exists a choice of residue classes aₙ (mod n) for each prime n ∈ Iₘ such that
p ∈ ℝₘ ⇒ p ≡ aₙ (mod n) for some prime n ∈ Iₘ.
[1]: Here is the paper linked: http://arxiv.org/pdf/1408.5110v1.pdf (strangely, while the news article mentions two papers, both links go to the same one in both the original and Wired articles ...).
[2]: I changed all instances of q to n in this so that I could type most of the subscripts, but any errors are mine.
I took an analytic number theory course with one of the authors of one of papers, Kevin Ford, while a grad student at UIUC - he was hard on me as a student from what I remember.
Tao's comment on prime number problems are spot on - the study of prime numbers is perhaps the most raw and magical of all the areas of mathematics. Intuition usually gives very simple "guesses" (most mathematicians have superb intuition) on basic properties, but proving them often proves to be elusive, which is why it taunts mathematicians.
Just curious: has there been anything on patterns in primes? There are so many constraints that I even wonder how there could not be patterns in the distribution.
Eratosthenes sieve is a pattern of sorts, but one with many dependent variables that we are unsure how to make agnostic from the pattern back to its initial state.. essentially we are unable to find the nth prime number, but if we already ran the pattern up to the nth prime number, finding n+1 is possible with enough effort
.
mersenne primes are primes that all share the form of 2^p-1 and they appear all through out the momentum of prime numbers, but again, our problem is finding when the next one will occur and our best solutions boil down to rote testing..
.
one person involved in the discovery here reported has a theorem named after a colleague and himself that is more along a traditional pattern, they call it an arithmetic progression, here is one such example..
6,171,054,912,832,631 + 366,384 · 223,092,870 · n, for n = 0 to 24
each of the 24 numbers in that sequence will be prime
.
i came across this momentum sometime last week:
n**2-n+41
the first 40 values for n, 1..41, will produce primes.. after that the distribution of primes for whole values of n becomes erratic.. why? unsure and investigation quickly proved a difficult avenue of research so i let that distraction lie for another day
Edit: This is perfectly relevant to topic of discussion and informative. BOINC is a completely valid platform for distributed computing for many different areas of research including mathematics, medicine, molecular biology, climatology, environmental science, and astrophysics.
This website uses a 2048-bit key. 512-bit RSA keys are considered generally insecure and easy to crack. 2048 is the industry standard. Your point is probably still valid, but we don't know how high we can go.
One implication straight from the article (I am a mere mortal, unlike you who asked the question):
The new work has no immediate applications, although understanding large prime gaps could ultimately have implications for cryptography algorithms. If there turn out to be longer prime-free stretches of numbers than even Cramér’s conjecture predicts, that could, in principle, spell trouble for cryptography algorithms that depend on finding large prime numbers, Maynard said. “If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.”
“If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.”
Wouldn't it also mean that the first prime after such gaps will be selected more often, assuming a random starting point for prime searches? That might be a bigger problem than having to wait longer for the selection to finish.
Honestly, I wouldn't worry about either problem. The degree of "unlucky" required here is almost certainly below the noise threshold. Otherwise we would have noticed by now, because prime-based crypto is, after all, not a theoretical thing, but something extremely-widely deployed in the field, and in practice, we do not observe this problem. Since we do not observe this problem, we therefore are not observing this problem; QED.
(The "noise threshold" is provided by the fact that processors are not in fact 100% accurate, but do indeed have a low-but-non-zero error rate. When the probability of a randomized algorithm failing drops below the probability that the processor literally got the computation wrong, it ceases to matter in practice. And one could argue it ceases to matter even before that, but it certainly ceases to matter at that point. Hence I call it the "noise floor". It's so low we are used to just assuming it is zero, but in fact it is not.)
This is the kind of work that the NSA, had they known it decades ago, would have kept to themselves. They certainly have no shortage of mathematical talent working on the problem.
Hey wired, can you not recount the entire history of whichever field the story you are covering is a part of in every article? Also, when I hit the back button I expect to go back.
Abstract. We show that there exists pairs of consecutive primes less than x whose difference is larger than t(1+o(1))(log x)(log log x)(log log log log x)(log log log x)⁻² for any fixed t. This answers a well-known question of Erdős.
Their "key proposition", as stated, is:[2]
Proposition 5. Fix δ > 0. Let m < Uz⁻¹(log₂ x)⁻² be even and let Iₘ ⊆ [x/2, x] be an interval of at least δ|ℝₘ| log x.
Then for x > x₀ (δ, C_U) there exists a choice of residue classes aₙ (mod n) for each prime n ∈ Iₘ such that
p ∈ ℝₘ ⇒ p ≡ aₙ (mod n) for some prime n ∈ Iₘ.
[1]: Here is the paper linked: http://arxiv.org/pdf/1408.5110v1.pdf (strangely, while the news article mentions two papers, both links go to the same one in both the original and Wired articles ...).
[2]: I changed all instances of q to n in this so that I could type most of the subscripts, but any errors are mine.