Mathematicians Make a Major Discovery About Prime Numbers(wired.com)
wired.com
Mathematicians Make a Major Discovery About Prime Numbers
https://www.wired.com/2014/12/mathematicians-make-major-discovery-prime-numbers/
31 comments
The article is a repost from https://www.quantamagazine.org/20141210-prime-gap-grows-afte...
Which was discussed here: https://news.ycombinator.com/item?id=8731040
Terry's own announcement of the new top result: http://terrytao.wordpress.com/2014/12/16/long-gaps-between-p...
The new bound cuts one of the logloglog factors from the denominator. At least that makes the formula slightly neater :)
The original discovery this recent news pertains to: https://news.ycombinator.com/item?id=6784383 , https://news.ycombinator.com/item?id=6766097
Yes, it's been a relatively prime year for number theory.
What, we wonder will 2017 bring?
Pun intended?
Edit: http://en.wikipedia.org/wiki/Relative_prime
Edit: http://en.wikipedia.org/wiki/Relative_prime
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.
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.
depends on your definition of patterns..
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..
.
i came across this momentum sometime last week:
(i) http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(ii) http://en.wikipedia.org/wiki/Mersenne_prime
(iii) http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem
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
.
i came across this momentum sometime last week:
n**2-n+41
(i) http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(ii) http://en.wikipedia.org/wiki/Mersenne_prime
(iii) http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem
There is Ulam's Sprial for example.
http://en.wikipedia.org/wiki/Ulam_spiral
http://en.wikipedia.org/wiki/Ulam_spiral
Prime is the pattern?
This is very interesting. Also Primecoin seems to be helpful in the prime numbers field.
http://primecoin.io/
https://en.wikipedia.org/wiki/Primecoin
https://en.wikipedia.org/wiki/Cunningham_chain
https://en.wikipedia.org/wiki/Bi-twin_chain
http://primecoin.io/
https://en.wikipedia.org/wiki/Primecoin
https://en.wikipedia.org/wiki/Cunningham_chain
https://en.wikipedia.org/wiki/Bi-twin_chain
Looks like it's a better proof of work than a meaningless hash.
I'm more sympathetic to using big amount of calculation to actually doing something useful, like calculating prime sequences.
I wonder what other kind of (useful) work could be used as payloads for virtual currencies
I'm more sympathetic to using big amount of calculation to actually doing something useful, like calculating prime sequences.
I wonder what other kind of (useful) work could be used as payloads for virtual currencies
Gridcoin uses the Berkeley Open Infrastructure for Network Computing as a way of obtaining useful work for cryptocurrency.
http://www.gridcoin.us/
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.
http://www.gridcoin.us/
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.
It's meaningless for a reason.
https://download.wpsoftware.net/bitcoin/asic-faq.pdf
Large primes are pretty useless. Everyday crypto generally uses 512-bit primes, which can be generated very easily and quickly on the fly.
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.
512 bit primes lead to an RSA key length of 1024 bits, since the key length is the length of the product of two primes.
It's not about finding a large prime, it's finding prime densities, gaps, sequences, etc
So great that Tao turns out to be a protege of Paul Erdõs.
What are the implications of this?
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.”
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.
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.)
(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.
Wired is not a mathematics journal, so probably not. "Know your audience." That's perfectly fine for a "general audience" medium.
But a broken Back button? Yeah, they should fix that.
But a broken Back button? Yeah, they should fix that.
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.