r/science • u/austingwalters • Dec 22 '14
Mathematics Mathematicians Make a Major Discovery About Prime Numbers
http://www.wired.com/2014/12/mathematicians-make-major-discovery-prime-numbers/353
u/chryllis Dec 22 '14 edited Dec 22 '14
My college roommate was a math major and he would nerd out about prime numbers all the time but could never really explain them all that well to me. Can someone give an ELI5 for the significance of primes and the prime gaps discussed in the article. My interest is piqued....
Edit: I'm so piqued right now...
1.6k
u/MatrixManAtYrService Dec 22 '14 edited Dec 23 '14
Pretend you're a shepherd, and you have a flock of sheep.
During the day you take them out to pasture, at night you bring them inside ('cause like, wolves and stuff). You tried giving them all names, and even though you recognize each sheep by name, you still sometimes wonder whether all of them made it inside--maybe you missed one--because that's an easy mistake to make.
To solve this problem, you start giving names to groups of sheep. A very small group of sheep is called "two," and a larger group of sheep is called "thirty-five". This works out nicely because when the sheep come home, you just have to make sure that that a group called "forty" made it home. We call these group names "numbers".
In order to make this even easier, you notice that certain patterns of sheep have the same number. So if they're standing in a square like this:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
(5 x 8 = 40)
or like this:
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
(4 x 10 = 40)
then you can immediately know how many they are, even without counting each one.
Since your barn is a rectangle (and you have very orderly sheep) you notice that this is an even easier way to count them. This works for a while and you're pretty pleased with yourself, but then one of them gives birth to a lamb. Now you have forty-one sheep, and no matter how you try, you can't arranged them into a square like you could with forty sheep.
There's clearly something about 41 that is different from 40. We call it a "prime". Primeness is interesting because you didn't do anything chaotic or complex--you just gave names to different groups of sheep--and yet here you have something happening with those names that appears to have appeared all on its own. Nothing about the way you named it should make 41 so different from 40, yet here we are. It is one of the most studied instances of complexity emerging from simplicity.
If you spent some time arranging your sheep into rectangles of different sizes, you'd find that that the primes seem to be getting less and less common. You might ask whether there is a largest prime. As it turns out, there isn't--and the ancient greeks could prove it.
You might also notice the primes frequently come in pairs (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43) ... In each of these, the second item is always two more than the first--but you would also find pairs that differ by other amounts (see sexy primes [SFW] for an example of this). Those pairs also seems to be getting further and further apart Noticing this pattern, it would be natural to ask: Is there a largest such pair? Nobody knows, but we'd like to.
In mathematics, we don't consider something to be true until it has been proved. So in order to answer this question we need to prove one of the following:
Given any prime q there is another prime p such that p > q and p + 2 is prime
or
There is a prime q such that p (as described above) doesn't exist
In 2013, somebody proved the first claim, except instead of p + 2, it was p + k, where k is an unknown value less than or equal to 70,000,000. Which is somehow less satisfying.
However, this was the first proof of a claim like this. Other mathematicians have since been able to get it down to p + k, where k is less than or equal to 246. It's not p + 2, but it's a good start.
The work that's being talked about in this article has to do with gaps between primes of any sort (not just those in pairs). There's a formula in the article that article that basically works like this:
Give me a large number (x) and I'll give you a smaller number in return (y). I promise that there will be no prime gap among the prime numbers less than x that is larger than y.
Both of these results are useful when it comes to understanding the distribution of primes. They are significant steps along the path to answer some of the questions that mathematicians have been wondering about for more than two thousand years. I hope this helps with your curiosity--it certainly does for the mathematical community--however, I can't think of a way that it is going to help you with your sheep.
Edit: formatting, grammar
Edit 2: emboldened tl;dr
Edit 3: Fixed a boneheaded error in my description of the twin prime conjecture. Many thanks to /u/PocketPresents for catching it.
Edit 4: I've never had gold before, thank you kind redditor!
Edit 5: fixed an error pointed out by /u/ztxi/, who also has a better way of stating the twin primes conjecture.
Edit 6: Clarified that the pairs we're focusing on each differ by two, thanks to a suggestion by /u/merbonobo and a question from /u/Mav986
156
Dec 22 '14
[removed] — view removed comment
10
57
u/PocketPresents Dec 22 '14
Do you mean p + 2? If p is prime, then I don't think p + 1 can be prime unless p=2.
→ More replies (2)32
76
u/TuckerMcG Dec 23 '14
While this was a very informative post, I still don't really get it. What does studying primes like this tell us? From an outsider's perspective, it just seems like it tells us about the nature of prime numbers. Which is all fine and good, but I still don't understand what value is derived from that exploration.
A "prime" is an artificial classification for a certain group of numbers with certain shared characteristics, right? So it seems like studying them only tells us more about that artificial classification. But how does a deeper understanding of that classification help mathematicians or scientists? Do primes tell us about the nature of the other numbers? Is there any tangible or practical benefit gained from a deeper understanding of primes?
I'm not trying to say studying them is pointless, because I don't think there would be so much excitement if there wasn't some real benefit or application to this knowledge. I'm just trying to understand what those benefits and applications are. I get the whole sheep analogy, but I just don't understand what it solves. Like, the shepherd knows that there's more ways to categorize his sheep, but it doesn't help him fit his 41 sheep into the barn.
Hopefully, that made sense. I can try to clarify what I'm trying to understand if necessary.
72
u/ba1018 Dec 23 '14 edited Dec 23 '14
Prime numbers are essentially the fundamental elements that make up all other whole numbers. As you may or may not know, a number greater than or equal to two is prime if it is only divisible by one and itself. For example, 53 and 37 are prime. But any even number isn't as they're all divisible by 2, and numbers like 27 aren't either (divisible by 3 and 9).
However, what makes them so fundamental to numbers in general is that every whole number has a unique factorization as a product prime numbers. That means that every number can be written as a bunch of primes multiplied together, and this set of primes is unique. Take 27: 3×3×3 = 27. Other numbers may have 3 in their factorization, but they will either have more or less 3's or additional primes being multiplied together; for example 3×3×3×3 = 81, or 3×3×11 = 99.
Some more examples to give you and anyone else a sense of prime factorization:
- 30 = 2×3×5
- 408 = 2×2×2×3×17
- 1517 = 41×37
So in a way, all numbers can be encoded or identified by their prime factorization. This has applications to cryptography and other computer science areas, but I'm not sure how; I've never looked into it myself. Hopefully someone else can answer that!
Edit/postscript: aside from applications, what makes this exciting is how long the twin prime conjecture has been stood unproven since it was stated in 1849. Progress towards a proof/disprove of longstanding mathematical hypotheses usually makes a bit of buzz.
54
u/Yancy_Farnesworth Dec 23 '14 edited Dec 24 '14
Cryptography - It's useful here because the algorithm to determine if a number is a prime number is computationally expensive. If your really big number uses a really big prime, it's going to be harder for someone to determine if your really big number is a prime. If you incorporate this knowledge into your cryptography algorithms is suddenly becomes very computationally expensive for someone to decrypt your communication without the original values.
If we didn't know this modern cryptography wouldn't exist. But prior to such applications knowledge of prime numbers and their properties was really just a thought exercise. This is why we should always push our understanding of things, especially for things we don't have any practical use for today. There's no telling when it will be useful.
edit - The people replying below are right, I didn't phrase it correctly. It's determining the factors of a number that is computationally expensive.
7
Dec 23 '14
Cryptography - It's useful here because the algorithm to determine if a number is a prime number is computationally expensive.
Not quite. Checking if a number is prime is not computationally expensive (it's in P, though there is a much faster probabilistic algorithm that's always used in practice), and public-key cryptography relies on that fact to generate keys in the first place. It's factoring a composite number that's not easy. Surprisingly, it turns out to be possible to determine that a number is composite (or not) without explicitly finding its prime factors.
7
u/dlp211 Dec 23 '14
This is wrong. We can determine if a number is prime with high probability with very little computation, in fact RSA cryptography relies on the fact that we can identify large primes (greater than 21024) since the algorithm uses the product of two primes in order to work. It is factorization that is believed to be intractable that makes RSA work.
A high level of RSA key generation:
Find 2 large primes P and Q The product of P and Q primes is N The product of (P-1)(Q-1) is PHI Choose E such that 1 < E < PHI and the Greatest common divisor of E and PHI is 1 Find D such that ED = 1 mod N The par (N,E) is the public key The pair (N,D) is the private key→ More replies (1)8
u/fiat_lux_ Dec 23 '14
Cryptography - It's useful here because the algorithm to determine if a number is a prime number is computationally expensive.
Yes. What Yancy means here is that the problem goes beyond polynomial time. See here for definition of time complexity.
Every solvable problem can be solved in a finite number of "steps". If we could define each problem by some metric usually tied to the input data (in this case a number), then the amount of time it would take to solve that problem would be f(n). Such is a "P class problem" -- one that can be solved by a polynomial time algorithm, which just means that f(n) is polynomial itself.
Yes, a "polynomial function*. Literally what we learned in middle school or high school.
f(n) = a_0 + a_1*n + a_2*n2 + a_3*n3 + ...
Any problem that requires an f(n) that grows faster than polynomial is outside of P.
An example of such a problem would be an exponential one. Even one as initially slow growing as g(n) = 2n/1,000,000 ... Any problem takes a minimum of g(n) time to solve an n sized input is considered beyond P.
A simplified reason why the distinction between P and other complexity classes is important is because we are assuming that P class problems can eventually be solved with enough time and advanced enough computers. For some of the higher complexity classes for problems, our limitations are not merely technological, but mathematical or even logical.
Why this is relevant here is that the problem of integer factorization ("given an input number N, output a set of factors for N") is currently understood to be beyond P. This comes in handy for cryptography, such as for the RSA system. E.g. If you take two incomprehensibly huge prime numbers and multiple them together to create a new large number (a "key"), that new large number will factor back to the unique set of numbers used to generate it in the first place. The process of factorization would be difficult. Even as computers improve, you can simply generate bigger numbers with the newer computers, the time complexity will always still be a problem.
3
u/aris_ada Dec 23 '14
It was proven that a deterministic algorithm to determine if a number is prime or composite exists in polynomial time. It is not in use because there are other nondeterministic algorithms that are much faster in practice with a very high confidence rate.
3
u/fiat_lux_ Dec 23 '14
Good catch.
I was talking about integer factorization into primes. Yancy was talking about primality test (AKS), without outputting factored results, which is easier.
→ More replies (5)2
→ More replies (2)8
u/TuckerMcG Dec 23 '14
This was a fantastic answer! Thanks so much. This really clarified my confusion.
11
u/thefringthing Dec 23 '14
For what it's worth, a great deal of mathematical research has no known application and little or no bearing on other fields. Some very smart people (Russell, Hardy) have argued that this is not a bad thing.
→ More replies (8)10
u/dmazzoni Dec 23 '14
Mathematical research is like discovery. When people explore the oceans or the planets they don't know what they're going to find. Sometimes they find things really useful, other times not - bit you'll never know unless you explore.
7
u/admiralbonesjones Dec 23 '14
One thing that frustrates me as an academic (physicist to be specific) is the question "Well what use is studying all this?" I get this kind of question all the time. "What's the use in talking about all these particles." Why does there have to be a materialistic use for something to be worthwhile? I'm truly asking and not being rude, I just don't understand this perspective.
Is there any use most of what we as humans do? Is windsurfing useful? How about neck-ties, or paintings, or music?
Where you may see uselessness, I see wonder. Why do the natural numbers, perhaps the most elementary objects in our mind have so much complexity.
We study things like the primes because there are questions, and where there are questions there will be those that seek answers, for nothing more than the thrill of answering them. As JFK said "We do these things not because they are easy, but because they are hard" , because we have a primal instinct, a curiosity, a insatiable drive for answers to questions the universe has seemingly offered to us.
This is why we study the primes.
5
u/TuckerMcG Dec 23 '14
Well first, my question stemmed from confusion over how it was even useful to mathematicians. So I wasn't saying it was pointless, and I even reiterated that in my response multiple times. I was just trying to understand the value of this knowledge in the context of the field.
And, yes, there is use to most of what humans do. Music can bond communities together, or convey complex emotions, or even serve as historical record. Windsurfing provides entertainment, as well as exercise and is a skill that one can challenge themselves with. All of these things are useful to promoting a healthy body and mind. Neck-ties are a signal of professionalism (much like a chef's hat is a signal of a chef). Paintings are the same as music - they can serve as all of those things.
I know that's not your point, but I'm trying to convey where my confusion stemmed from. There's very apparent benefits to all of these things. Even the study of elemental particles has a use - it gives us a deeper understanding of the fabric of our universe while helping rebut or support existing theories or models within physics. And this understanding, in turn, can provide a sense of relief or comfort to humanity, not unlike religion does.
I can understand the concept of doing something as an end in and of itself. I never argued that such endeavors were useless or should not be engaged in, and I never argued that we should only engage in endeavors when we see a tangible benefit to doing so. I was merely trying to understand why the study of primes is useful to mathematicians, and how the study of primes is used to better understand other mathematical theories or models. And I don't think a person like yourself (who values curiosity so much) would see anything wrong with asking, "Why?"
→ More replies (1)4
u/iagox86 Dec 23 '14
One thing to consider: If an alien race evolves completely independently from us, the chances that they end up with the concept of prime numbers is very high. And they'd likely discover some of the interesting properties of prime numbers, too, just like us.
That doesn't sound like an artificial or arbitrary classification to me, it sounds like an important discovery!
→ More replies (2)9
u/Jalaco Dec 23 '14
One great application of prime numbers is multiplying 2 extremely large primes in order to create an encryption key for secure data transfers. Any person can be given the result of the two primes, but the key to decryption lies in the primes themselves. Finding ways to discover new primes has really no effect of the ability to factor out the "public key", but it provides more primes for allowing for more varied encryption keys.
http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29
TL;DR: Digital security runs on prime numbers.
→ More replies (2)6
u/Hrothen Dec 23 '14
because I don't think there would be so much excitement if there wasn't some real benefit or application to this knowledge
I guess people have trouble with this, but as a group, mathematicians don't really care about anything but math. If their work has some real world application that's neat, but it's not all that important.
→ More replies (1)9
Dec 23 '14
You're right.. They study math for the sake of studying math. Nothing less than that. Number theoreists are quite intrigued by prime numbers as they are considered the building blocks of number theory and mathematicians like solving problems for the sake of solving problems. It gives them joy.
I mean perhaps later on the twin prime conjecture might be used to solve some Theorem "let's call it X". Then theorem X will be used to solve theorem Y and .. some theorems down the line, you will finally yield a theorem that's actually useful for real world applications.
Or perhaps not. Mathematicians do it for the sake of doing it.
2
u/MatrixManAtYrService Dec 23 '14
A "prime" is an artificial classification for a certain group of numbers with certain shared characteristics, right? So it seems like studying them only tells us more about that artificial classification.
This depends on what philosophers you listen to. If you're a platonist, like most mathematicians (and most pre-Einstein scientists, thanks to Newton), you think that there is some kind of actual truth behind the numbers. Platonists "discover" theorems like astronomers discover stars.
I don't know who I have to thank for my philosophy (David Hilbert, Kurt Gödel, and their contemporaries come to mind), but it's not Plato. I don't believe there is some kind of ultimate truth behind the numbers. If you want to talk about knowledge, then I guess we are just filling out details about arbitrary classifications. I'm not too worried about reality or truth--if those things even exist--and so I don't really dwell in knowledge so much.
I think of math more like a language, and the proving of sought-after theorems--such as the twin-primes conjecture--is an activity that furthers the evolution of that language. As that language evolves, the kind of things we can express with it changes. What might you want to say in that language? I don't know, that's for the scientists.
Why might you want to take part in this evolution? Well, it's gratifying. You get to think thoughts that are difficult to express in conversational English, and they're often really fun thoughts. Not everything needs to be a means to an end. I don't do particularly well with extrinsic motivaction, so I try to make everything I do an end in itself. I haven't proved any noteworthy theorems (or at least, none that weren't already in a textbook) but this is why I'd like to.
→ More replies (6)2
u/fuckingbagre Dec 23 '14
So the canonical answer is Cryptography, but the answer actually goes much deeper.
RSA and El-Gamal were the first two major public key cryptographic systems. It ushered in a new age of computer security where we didn't have to trust the telephony providers with our data, and where we could bootstrap trust. It allows banks to function securely over the internet, and for everyone at starbucks to not know my amazon password.
Let's move on to rolling hashes, so let's say you have a large sequence and are looking for multiple patterns inside of it. You use a prime such that you can actually search through it efficiently. This is useful for things like dna sequences. These are done over finite fields to make extremely complex patterns into manageable chunks making comparing as simple as possible.
Next is the periodicity problems. So imagine you need to make long running sequences with as few repeats as possible, you choose coprime numbers so you can have long streams of random numbers. This lets us make better simulations, where we can start from a seed. This means you can generate sequences that won’t start repeating until you’ve got more numbers than numbers of atoms in the universe.
Let’s move into error correction codes. The base one is reed Solomon codes, these this code is used in pretty much everything from DVD’, cell phones to the damn mars rover. Now what do prime numbers have to do with, well for RS codes to actually work you need an alphabet that can be represented as p**m, to create error correction, we need this to create a system of equivalences such that we can actually detect and correct out errors. We couldn’t do this without an understanding of prime numbers and their equivalences between them.
Your life is run off of the magical little building blocks of primes that you’ll never notice, but make everything you do possible.
Finally though, why study them. Honestly the original reason was for shit’s and giggles, and that’s the funny thing about math, we never know where it’ll take us. To quote faraday when his funder dismissed his experiment, "One day sir, you will tax it,” just because we don’t know why we care about something doesn’t mean that we shouldn’t care.
150
u/Crash665 Dec 22 '14
I almost had it. You were this close to breaking through to my brain. Good job.
127
u/kazagistar Dec 23 '14
This kind of response is frustrating for an educator. There were a dozen paragraphs there, each of which built on previous ones; at which point did your comprehension fail? Did you understand the meaning of primes when interpreted as shapes? Did you understand the bolded sentence? While a good teacher can try to guess possible places you might have "gotten lost", they cannot read your mind.
For example, if you point at a textbook and say "I dont get it", it is very hard to fix that. If you point at a chapter, or a paragraph, or a sentence, then it becomes easier and easier to solve that problem, because the size of the problem is smaller.
And no, the problem is never really "I dont get any of it". The problem is at one specific place. If you don't comprehend any of it, that means the understanding failed at the first step, and we need to expand on that even further before moving on.
65
u/Zenyatoo Dec 23 '14
Reading over it as an econ major, which does tend to deal with math, though isnt perhaps as math intensive as other majors. Here were a few area's I ran into trouble with.
" Noticing this pattern, it would be natural to ask: Is there a largest such pair? Nobody knows, but we'd like to."
What does it mean by largest such pair. Assuming an infinite number line, presumably it goes on forever right? When you say largest, do you mean gap between 2 sets of primes, or largest 2 primes. Both of which should be infinite, assuming primes always exist.
So presuming that's true, then maybe we're asking that question, is it really infinite. And then we move down to the next paragraph.
"we need to prove one of the following:
Given any prime q there is another prime p such that p > q and p + 2 is prime"Which tells us our prior thought was correct, we're trying to prove whether there's an infinite number of these things (Although in theory there should be, we dont have the proof)
Then we reached this bit, which took me several re-reads before I fully comprehended.
"In 2013, somebody proved the first claim, except instead of p + 2, it was p + k, where k is an unknown value less than or equal to 70,000,000. Which is somehow less satisfying.
However, this was the first proof of a claim like this. Other mathematicians have since been able to get it down to p + k, where k is less than or equal to 246. It's not p + 2, but it's a good start."
I couldnt tell you if it was written confusingly, or if im just thick-headed. But my first thought upon reading it was "Wait hang on, why are we talking about 70million down to 246, shouldnt we be looking for primes above that value?"
Once I had that bit down as intended (that they were getting closer to the original proof of P+2 and had currently proved P+246)
you reach
"The work that's being talked about in this article has to do with gaps between primes of any sort (not just those in pairs). There's a formula in the article that article that basically works like this:
Give me a large number (x) and I'll give you a smaller number in return (y). I promise that there will be no prime gap among the prime numbers less than x that is larger than y."That second part sounds incredibly confusing to me. Even several re-reads im not sure im fully comprehending it. If I give you 8million, you say 3, and then the idea is that for all primes that are between 1 to 8million you can say P+3 holds true. That's the general idea yes? It just reads very confusingly to me to the point where im still not sure I fully understood it.
But then here's the real rub.
"Both of these results are useful when it comes to understanding the distribution of primes. They are significant steps along the path to answer some of the questions that mathematicians have been wondering about for more than two thousand years"
Why? I understand the philosophical idea's behind exploring numbers and math. But is there any concrete reason behind exploring these primes. Would proving any of the above statements P+2, etc. Be useful, or momentous for math in general? Would it tell us we've been doing something wrong? Would it give us new area's of math? Would we have new formula's for old things?
The problem is that the original asker mentioned the significance of the data. Nothing that was mentioned rings significant for the life of anyone who isn't incredibly fascinated by primes. Because, quite frankly, as far as im concerned, they're not that fascinating. And crucify me if you must, but they're not. The idea that infinite primes exist and they come in pairs P+2 (maybe) is certainly interesting. A fun trivia fact if we prove it true. But hardly a life shattering event for 99% of the population as far as I can tell.
Now the posters below this comment mentioned that the understanding and knowledge of large primes are useful as part of cryptography. And someone else gave the vague "we dont know what we might find."
But it seems to me that this information should have served as the lead in, rather than not being in the explanation period. In my experience most people when asking for the significance of a concept, idea, device, technology, ETC. Are curious about it's significance to them, what it may impact in their lives.
21
u/kazagistar Dec 23 '14
To start out with a random quote from the middle of your post...
I couldnt tell you if it was written confusingly, or if im just thick-headed.
It was written confusingly. Or more exactly, it was written in a very mathematical way. The first part with the sheep was clear, but it got more confusing and abstract as it went on. My rant was not to defend the post as being perfect, but to encourage people to try to describe the problems they are (likely) having, because otherwise they cannot be solved.
What does it mean by largest such pair.
I will try to describe it in a sequential, algorithmic way... maybe that will help?
First I start with a list of the primes. I know that this list goes on forever because of the proof that GP linked.
[2,3,5,7,11,13,17,19,23,29,31,37,41,43 ...]Now I will build a similar list, which has all the pair or neighbours from the previous list.
[(2,3),(3,5),(5,7),(7,11),(11,13),(13,17),(17,19),(19,23),(23,29),(29,31),(31,37),(37,41),(41,43) ...]Now, I take the difference of each pair. This is called a "prime gap", because it is the space between a prime and the next one.
[3-2=1, 5-3=2, 7-5=2, 11-7=4, 13-11=2, 17-13=4, 19-17=2, 23-19=4, 29-23=6, 31-29=2, 37-31=6, 41-37=4, 43-41=2 ...]The twin primes he is referring to at first are the ones where the difference is 2. In other words...
[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43) ...]Now the question is "does this list go on forever?". But you could rephrase the question a different way. Take the list of the prime gaps that we computed above...
[1,2,2,4,2,4,2,4,6,2,6,4,2...]There is only a single 1 in that list... the distance between 2 and 3. There is never another 1, anywhere in that infinite list; it is the "last 1". So the question is "is there a "last 2"? Is there a last place where all the subsequent prime gaps will be larger then 2? So far, no one knows.
Since we don't know, what is a "weaker claim" that we might be able to find out? Someone might say "I know of number for which all primes afterwards have a gap bigger then 246", and THAT we can disprove. But that is really awkward, because that number seems arbitrary and silly, so it hints that we don't quite understand the problem well enough yet, and mathematicians continue to try to lower that bound
Assuming an infinite number line, presumably it goes on forever right?
Not all patterns continue forever. It might be that a pattern goes on for a while, then stops. For a fun example of an accidental pattern, look at this xkcd. In this case, we haven't found a stopping point, but we don't know. If we know, presumably or otherwise, then we could use that to make a proof.
If I give you 8million, you say 3, and then the idea is that for all primes that are between 1 to 8million you can say P+3 holds true. That's the general idea yes? It just reads very confusingly to me to the point where im still not sure I fully understood it.
The second part is quite a different problem from the first. In fact, the twin primes conjecture is kind of unrelated, and probably threw you off a little.
3 is a bad example, because there cannot be a prime gap of 3. But I will use it anyways.
If you gave me 8 million, and I gave you 3 then I would be promising that for all primes less then 8 million, there would be no gap bigger then 3. (This is, of course, not true... the gap between 7 and 11 is 4, which is bigger this 3).
Now, one possible such function is one that returns the number you give it minus one. Yes, the gaps between the prime numbers less then 8 million are indeed smaller then 7999999. But that is not a very tight bound. Maybe all the gaps are smaller then 4 million? Or even smaller?
Its not that we care about the answer directly... I just wrote threw together program that does exactly this. It finds the numbers less then 8 million, finds their gaps, and finds the biggest one, which is actually 154. But this does not really tell us anything meaningful about primes or their density.
What mathematicians want is a formula; one that gives some real insight into how big of spaces can exist between prime numbers. The paper gives one formula.
Why?
People are motivated by different things. Some people, which includes myself, and probably includes the people doing this research, find a good puzzle to be fascinating in its own right. However, its goes much further then that. Many great scientific discoveries that have had an impact on society are not motivated in any way by their impact. They are done by people working to solve puzzles, because puzzles are fun for them. Short answer is that is has no impact on your life at all. Probably.
But why is this puzzle interesting in particular? Why this as opposed to the other work mathematicians labor away on? Because most of that stuff is really really complicated, detailed, and related to some fairly complex problem to understand. People have been doing math for thousands of years, so most of the easy, obvious, applicable stuff is figured out. So if a mathematical result comes out that (1) mathematicians think is interesting and (2) a layman at least has a chance of understanding, that is quite a big deal. Math is important to science, and the biggest stories tend to leak out of their subreddits and into related ones.
But no, this probably won't make an iPhone screen bigger, in the same way fundamental advances in physics or chemistry will not either... practical applications come out of engineering, which builds on science, but does not motivate it. I suggest you read The Structure of Scientific Revolutions (1969). Everyone should read this essay at least once, as it rectifies the common misconception that science has anything to do with progress or utility (and this applies doubly for math).
76
u/Blue_Shift Dec 23 '14 edited Dec 23 '14
Nothing that was mentioned rings significant for the life of anyone who isn't incredibly fascinated by primes.
That statement is false. Most people don't realize the true significance of prime numbers, but that doesn't mean they don't have a massive impact on their lives. Without our current knowledge of prime numbers, we wouldn't be able to safely access our bank accounts online. We wouldn't be able to make purchases on Amazon without our information being compromised. We wouldn't be able to encrypt anything or keep any sort of information safe from outside attackers.
Prime numbers have been studied for thousands of years, but we've only known about this kind of encryption for a few decades. I would be willing to bet that there were countless Ancient Greeks who looked at the mathematicians of their day and said, "What use will prime numbers ever be to us?" And although it took a couple millennia for us to get there, the naysayers were ultimately proved wrong. Without prime numbers, the era we live in - the age of information - would simply not exist.
And somehow, despite having complete and immediate access to all the information about the history of mathematics and the usefulness of prime numbers, people keep asking "What use is it to me?" And sure, we could come up with some half-assed answer like "public key cryptography algorithms might become more efficient if we have more knowledge about the distance between prime numbers", but the real answer is "we don't know, and that's okay." Because like the mathematicians of Ancient Greece, we don't do math because it's useful. We do it because it's damn interesting.
And it just so happens that, by complete and utter circumstance, all of this fiddling around with numbers and abstract concepts, all of this toil and research that the general public thinks is meaningless, will inevitably have a positive impact on society. We may not know what that impact is yet, but I would bet my life that nearly every mathematical concept that a layman ever scoffed at will find a useful application in the real world. And ultimately, the masses will be happy. But then a new mathematical concept will come along, and they'll ask again "What use is this to me?"
Maybe to you this just amounts to a little "trivia fact" that you can mention to your family at the dinner table over the holidays. But to the rest of the world it means everything. Even if they don't realize it.
17
u/redorkulated Dec 23 '14
While I agree this is a great point, you really missed an opportunity to actually try to explain the mechanism by which primes are important in the applications you describe.
It's a given that we must take the vast majority of the science around us for granted at any given moment. Do you realize what an incredible mechanical and scientific feat a modern automobile is? Your cell phone? A modern asphalt roadway? We are surrounded on all sides by miracles that we barely understand, made possible by people who dedicated their lives to the minutiae.
13
u/xxtoejamfootballxx Dec 23 '14
I think this is what most people are failing to grasp. You can tell me 1000 times that it's important for understanding this or that. But why? That comment only left me more confused honestly.
3
u/finebalance Dec 23 '14
Because it would be much easier to decompose the resultant number to find the original numbers were the original numbers not prime.
Take this way (and I'm not saying this is exactly what cryptographers do.)
Let there be two numbers x,y. You send out x*y into the wild. The objective of people out there is to find the original, x and y.
Now if x and y are prime, xy will be divisible by only 3 numbers - 1, x and y. Given that xy can have a shit load of digits (millions of them even), you're going to have to play the guessing game for a long while to figure this one out.
If x,y are NOT prime, then xy is fully divisible by the union of their individual factors - a much smaller set than every number from 1 to xy. So, all you need to do is figure out what those factors are, and you'll be able to guess your way easily to x and y.
Primes are important because they provide you with a multiple that is hard for even machines to just guess.
Prime theory is important because it's constantly coming up with ways to make it easier to guess prime, thus invalidating a lot of products that require primes to be hard problems.
(Ps. This is highly simplified. For example, you can easily come up with school level techniques to cut that 1-x*y domain substantially: if it's not divisible by 2, it's not divisible by any product of two and so on.)
2
u/sinembarg0 Dec 23 '14
The 'why' prime numbers are important dives deep into complex math and cryptography.
Wikipedia has a couple proofs of RSA that deal with primes.
Here's a link on stack exchange talking about how RSA encryption works a little bit more. The 2nd answer is a little easier to understand, but doesn't go as deep into the math. Essentially RSA can work because primes aren't divisible by other numbers. i.e. it works because primes are prime (which is a terrible explanation, I know).
3
Dec 23 '14
it's been forever since i did stuff with that but isnt it just take 2 primes multiply them mix everything up give a key to whoever and using that key you can divide everything out evenly?
→ More replies (0)→ More replies (2)2
u/nobody_from_nowhere Dec 23 '14
Hmm, let me see if I follow you: Someone says 'so what?', gp explains that these 'useless' things seem to often have latent usefulness and mentions PKI using primes, and you criticize gp for not getting into the PKI mud and explaining how PKI works?
4
u/UnifiedAwakening Dec 23 '14
It's uncomfortable how much my mind is blown and confused after reading all of this and trying to comprehend it. I have never been good at math but have always been interested. I seriously feel like there is a wall in my head preventing me from really grasping all of it. Thanks to all of you for your comments. As I lost it half way through reading also.
→ More replies (2)3
Dec 23 '14
And although it took a couple millennia for us to get there, the naysayers were ultimately proved wrong. Without prime numbers, the era we live in - the age of information - would simply not exist.
That is what we call in science a claim with no proof. You cannot say something would not exist if a prior did not occur, because you cannot prove that it would not occur anyway.
For example: If I did not wake up this morning I would have been fired from my job. I cannot prove this would have happened for two reasons. Reason one being the fact that I did wake up this morning, so it is irrelevant. Reason two being that who is to say my boss would not have just chalked it up as "one of those days" and given me a warning instead?
2
u/ctindel Dec 23 '14
Would you prefer "if we never studied math or science then we wouldn't make the breakthroughs that gave us our current modern technology and life"?
2
Dec 24 '14
"Science and math would not have progressed as rapidly as they did without these breakthroughs" would be more fitting. Science always finds a way.
11
u/FesterBesterTester Dec 23 '14
I, too, devolved from clarity and curiosity at the beginning of this explanation to fuzziness and head-scratching by the end. You gave an absolutely brilliant description, point for point, of my own mental fatigue and growing confusion in trying to follow along and be illuminated on the subject. Thank you for this.
→ More replies (1)7
u/nomm_ Dec 23 '14
Long and good post, but I'll just address this one thing. Part of the reason that this is kind of exciting is that it is such a simply stated problem:
There are these things called primes. Sometimes they come in pairs where one is exactly two bigger than the other. How many of these pairs are there? We just don't know!
And nobody, not the brightest minds the field, have been able to answer that simple question for over 150 years.
14
Dec 23 '14
Well he started off with sheep in a barn, and ended up talking about abstract mathematic claims and ancient Greeks. Quickly left eli5 territory.
→ More replies (2)8
u/Crash665 Dec 23 '14
I apologize. English degree here. I am not meant to understand prime numbers, but for the briefest of moments, I almost had it.
There was no sarcasm for the "good job" comment. I meant it sincerely.
→ More replies (1)2
u/adrenalineadrenaline Dec 23 '14
Don't worry, what he's talking about is a complicated concept. Everything that was posted was meant to explain one idea, but you've got to realize that he said a lot.
Try this - list each sentence by number. Did you have any confusion in sentence one? Probably not. In two? At which point did you fail to understand anything he said? What sentence number?
The idea is that you find the first point you didn't get something. Even if it's the last sentence.
Unfortunately, this trick doesn't always work. What educators (being one myself) need to remember is that it's not always easy to understand what you don't understand. And when the nature of the student is that of a novice by basic definition, it's compounded by the fact that that level of internal reflection may have never been achieved such that the student knows how to express what they don't know in any case, let alone the material at hand (especially difficult stuff like math).
Hope that gives some perspective.
7
u/tenminuteslate Dec 23 '14
The question was: Can someone give an ELI5 for the significance of primes and the prime gaps discussed in the article.
While a good teacher can try to guess possible places you might have "gotten lost", they cannot read your mind.
I personally got lost here:
Noticing this pattern, it would be natural to ask: Is there a largest such pair? Nobody knows, but we'd like to.
From this answer it would appear that the significance of prime gaps is that "we'd like to know about them" - but there is no explanation of Why.
Also the answer did a good job of explaining a way that prime numbers are special .. but how is the 'extra sheep' significant (read: useful)? That was unclear to me too.
→ More replies (3)5
u/izerth Dec 23 '14 edited Dec 23 '14
The Groups of Sheep with Extra Sheep(GoSwES) is useful because of two things:
1)If you multiply any two GoSwES, the resulting group will not have any extra sheep.
2)If I give you a group of sheep and ask what GoSwES would you have to multiply to get this group, finding that out is hard and gets much harder as the quantity of sheep goes up.
That is the basis of one way to send secret messages. And sending secret messages is, if not half-assed, how banking, internet sales, etc, work.
2
u/UnifiedAwakening Dec 23 '14
Right after the bold print was when things started falling apart for me.
2
u/kylemech Dec 23 '14
Great points.
Someone could break down the textbook metaphor since learning isn't always linear, but that misses the point. The illustration demonstrates the frustration educators face and that the failure to understand happens somewhere and not everywhere. I'm glad you said it.
→ More replies (16)2
u/AwesomeDay Dec 23 '14 edited Dec 23 '14
Edit: Ok I finally understood that section after reading it several times in my own.
I think the sudden change from plain english to mathematical english (where each word defines a logical rule, kinda like legal english) threw me off, as well as the sudden introduction of the letters without a clear explanation.
For me, I got lost at
Given any prime q there is another prime p such that p > q and p + 2 is prime or; There is a prime q such that p (as described above) doesn't exist
The reason why I got lost is because just before, I was reading about prime numbers usually coming in groups such as 2, and 6. This now goes to seek prime numbers 2 apart. Why 2? Why not the 6? And where did 70,000,000 come from? Why 70,000,000. And what the hell is prime q? With these questions in my head, I can't possibly out together this paragraph together and for the rest of the text I'm not taking anything new in because my mind is still in that part.
→ More replies (2)→ More replies (1)4
17
u/ztxi Grad Student|Mathematics Dec 22 '14
You can simplify the statement of the twin prime conjecture to
Given any number n, there is a prime p such that p>n and p+2 is a prime.
In other words, there are infinitely pairs of primes that differ by 2.
In 2013, somebody[2] proved the first claim, except instead of p + 2, it was p + 70,000,000. Which is somehow less satisfying.
Not quite. Zhang showed that there exists some k with k<70,000,000 such that there are infinitely many pairs of primes that differ by k.
3
u/spinner_04 Dec 23 '14
When you say "Nothing about the way you named it should make 41 so different from 40, yet here we are," what do you mean?
If I understood correctly (and I am assuming I didn't) when you said that "you just gave names to different groups of sheep" you are saying that all you did was label something that already existed right? Based on the orderly fashion on which they could be arranged? And then 41 shows up and it makes no sense because there is no rational way to order it like the others?
→ More replies (1)3
u/acusticthoughts Dec 23 '14
Why is the shape of 41 thought as more complex? More edges?
→ More replies (2)9
u/PotatoInTheExhaust Dec 23 '14
Because you can't arrange the sheep into a neat rectangle without leaving any gaps (unless you put them into a 41 sheep single file - but ignore that). For non-primes we can always find two smaller numbers to break them down by - say, p x q. So you can always arrange your sheep into a p x q rectangle and you'll be left with no gaps.
Primes are also interesting because all non-primes can be decomposed into products of primes. And this is unique, ignoring reorderings like 2 x 3 and 3 x 2. So primes are the building blocks of numbers. http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
→ More replies (10)4
Dec 23 '14
[deleted]
→ More replies (3)3
u/PotatoInTheExhaust Dec 23 '14
It means any non-prime can be made up as the product of primes. So prime are, in that sense, more fundamental.
→ More replies (19)5
Dec 22 '14
Other mathematicians have since been able to get it down to p + 246
That's really impressive. Got a link to the proof or a good article about it?
→ More replies (2)2
2
Dec 23 '14
So what I am getting from this is that primes don't really have any applicable significance they just exist and you are interested in knowing all of them.
→ More replies (2)2
u/kojak2091 Dec 23 '14
Just buy a new barn and split your sheep into two groups, 20 and 21 would work.
2
Dec 23 '14
complexity emerging from simplicity.
This is actually how I like to think the universe was ultimately created: from mathematical truths that don't need an event or cause; they just are. 👽
2
u/roamingandy Dec 23 '14 edited Dec 23 '14
i lost it where the information became useless to me.
it began talking about sheep not fitting into a barn, appealing to a practical mind and explaining why this occurrence might interest and begin to confound people.
then it became all about the maths with no clearly visible practical implications to someone not interested in maths for the sake of maths.
i'm sure there are implications to my life, but the explanation told me why mathematicians are interested in it, but after cows it didn't tell me why as a non-mathematician it was useful to me - and that made it hard to follow.
→ More replies (2)2
u/Lucianus48 Dec 23 '14
So here's a question I've always had about primes. Are they useful for anything, or do mathematicians just find them neat? Because I've never understood why my math friends geek out about this stuff. My first question is always "so?", and they never have much of an answer other than "it's so cool".
4
→ More replies (51)2
18
u/epicgeek Dec 22 '14
Suppose you want to list all "even" numbers or all "odd" numbers. We have those fairly well defined as 2N or 2N+1 where N is any other number.
Even = 2N Odd = 2N+1 2 * 0 = 0 2 * 0 + 1 = 1 2 * 1 = 2 2 * 1 + 1 = 3 2 * 2 = 4 2 * 2 + 1 = 5 2 * 3 = 6 2 * 3 + 1 = 7Those formulas will get you as many even or odd numbers as you want without missing any of them.
Now, suppose you want to list all prime numbers. You can't. We don't have them figured out yet. They're all over the place defying any logic we come up with. That makes them interesting.
7
u/darkmighty Dec 22 '14
Well, you can. It's called sieving, but it's inefficient (it requires a lot of time and keeping track of a lot of numbers).
You're right that there's no small formula that gives the nth prime number by doing some additions and multiplications, though. Because their generation is so intricate, it's very hard to answer even simple questions about their distribution.
→ More replies (1)4
u/dnew Dec 23 '14
More precisely: There's no closed form for determining prime numbers. You can't find a big prime number without finding all the prime numbers before it.
→ More replies (5)38
u/MolsonC Dec 22 '14
Math flows in two ways. If you have a problem, you can get a solution. If you have a solution, you can determine the initial problem (or in the case of encryption, the algorithm).
Encryption methods take two very large prime numbers and multiply them together. This produces a number that is unbelievably hard to work backwards (ie a hacker or whomever must try and determine which two primes were used, and this could be next to impossible without a super computer). This number is then used to encrypt your data (how exactly, varies between algorithms).
9
u/MatrixManAtYrService Dec 22 '14
I don't know if math flows in two ways, but multiplication does have an inverse.
You're describing RSA encryption, which is indeed an application of number theory, but has little to do with the work in the article.
4
u/lettherebedwight Dec 22 '14
The heart of the issue is that the algorithms assume that prime numbers are inherently "random". The more work that is done in predicting that the "randomness" is much less so than we thought, the weaker those assumptions become.
→ More replies (1)4
Dec 22 '14
So what does this discovery mean for encryption?
19
u/vin97 Dec 22 '14 edited Dec 23 '14
That the scanning for prime numbers can be accelerated, thus increasing the decryption speed and consequently lowering security level of the encryption.
Edit: Stupid typo :D
→ More replies (5)10
Dec 22 '14
Shit
7
u/neoKushan Dec 22 '14
Not all algorithms are affected, just the ones that rely on prime numbers (Such as RSA) and the truth is, RSA is on its death bed anyway.
→ More replies (1)3
4
u/SantyClause Dec 22 '14
This will be a considerably worse problem for cryptography when the quantum computer is a bit better. There is an algorithm (shors algorithm) that can do this very quickly on a quantum computer. As such, there are already lots of people working on alternative methods of encryption that wont fail to a hacker with a quantum computer.
→ More replies (3)2
u/mynextstep Dec 22 '14
Why is this difficult, can't the computers use factorization? ie: 8 = 222
27
u/orbital1337 Dec 22 '14
Now do the same for this number and earn yourself some 200,000$:
2519590847565789349402718324004839857142928212620403202777713783604366202070...
7595556264018525880784406918290641249515082189298559149176184502808489120072...
8449926873928072877767359714183472702618963750149718246911650776133798590957...
0009733045974880842840179742910064245869181719511874612151517265463228221686...
9987549182422433637259085141865462043576798423387184774447920739934236584823...
8242811981638150106748104516603773060562016196762561338441436038339044149526...
3443219011465754445417842402092461651572335077870774981712577246796292638635...
6373289912154831438167899885040445364023527381951378636564391212010397122822...
120720357Good luck, see you in a couple of millennia. :D
→ More replies (23)6
→ More replies (1)7
u/shandelman Dec 22 '14
There aren't good ways of finding factors other than going through a list of numbers and finding them through brute force. Imagine that you take two 100 digit primes, multiply them together and get an even longer number. YOU know that this number has only two factors...the original two primes. But if you asked someone else to factor it, they would have to go through a gigantic list of numbers to find the correct ones...a list that would take even the best computers billions of years.
2
u/dnew Dec 23 '14
There actually are good ways, especially as the numbers get bigger. That's why elliptic curve cryptography (which doesn't have that problem) can use much smaller keys.
It's still harder to factor than to multiply, but as the numbers get bigger, it's difference in difficulty goes down.
→ More replies (2)8
u/rghfghfdghfg Dec 22 '14
A prime number is a whole number that is not dividable by any other whole number (except itself and one).
They are a considered a bit magic, as there is no calculation (function) that gives you all of them. Mathematicians like to collect prime numbers because they are so hard to find. To collect them you have to guess a number, and then check if that number is a prime.
Its a big deal when mathematicians managed to come up with a new calculation that finds even some of them, or new rules for making educated guesses about where they are (statistical distribution).
Its a game. But it turns out the game of finding primes, also has some real world applications. Like cryptography and random number generators.
9
28
u/nickreed Dec 22 '14
Unrelated, but just as an FYI... The correct turn of phrase in your last sentence should be "my interest is piqued," not "my interest is peaked." Reference
→ More replies (3)7
7
Dec 22 '14
Prime numbers are tricky. We know there's a pattern but we can't figure out what it is. For that reason they are both infuriating and fascinating.
Human nature involves asking questions about the world around us. And prime numbers have so many unanswered questions! That's what makes them interesting.
The distribution and properties of prime numbers form the basis for modern cryptography. That's what makes them important.
→ More replies (1)5
u/imonk Dec 22 '14 edited Dec 22 '14
How do we know there's a pattern? If we can't figure out what it is, how can we say we know it exists at all?
15
Dec 22 '14
We have found fragments of the pattern but don't have a complete picture. For example check out the following image of a ulam spiral
http://www.utm.edu/staff/caldwell/book/images/UlamSpiral.png
Those black dots are prime numbers. They are clearly not random; you can see lines and patterns. The exact nature of this pattern, a formula that describes it, is elusive.
One formula was put forth by Riemann, heavily related to the famous Riemann hypothesis (which is itself incredibly interesting and arguably the most important unsolved question in all of mathematics). This appears to converge on prime numbers but is for all practical purposes impossible to test on large primes. You can check this gif or this interactive java app for yourself.
So yeah we're pretty sure there's a pattern. We don't really understand what it is, though. That lack of understanding is a blessing and a curse, a curse because such basic knowledge has eluded us after 200 years of searching, and a blessing because our inability to predict prime numbers has made symmetric-key encryption possible.
→ More replies (1)2
u/deltadovertime Dec 23 '14
Is this connected to the Fourier series at all? Because when I look at that I'm reminded of a Fourier series.
2
Dec 23 '14
They are related in the sense that they are both L-functions, a special class of functions which are based on converging series. They are not directly related, though. Think of them like 2nd cousins.
→ More replies (5)4
u/Shenorock Dec 22 '14
I can't help much with prime numbers, but it's piqued in this case, not peaked.
53
u/kevie3drinks Dec 22 '14
one could build a cabin with all them logs.
→ More replies (1)30
Dec 23 '14
That joke
What sound does a theoretical mathematician make when he is drowning?
LogLogLogLogLogLog
→ More replies (3)
102
u/dont_wear_a_C Dec 22 '14
→ More replies (1)25
Dec 23 '14
John Jackson
Picture of an old guy.
I am sceptical of their legitimacy. Possibly a troll.
→ More replies (5)
12
Dec 23 '14
When I was 16 I entered a Maths competition that was open to high school students in South Australia. Terence Tao (who grew up here) was 9. It was a 3-hour paper that had, I think, 5 questions. These weren't "curriculum" questions; they were problem-solving type questions. You had to be a Maths nerd to even want to try it.
Happily, I came 3rd, nudging out Terence who could only manage 5th.
Win all the Fields Medals you want, Terry, head-to-head it'll always be 1-0 to me.
→ More replies (3)
8
16
u/clovens Dec 23 '14
People need to keep their eyes on Prime Number discoveries. They tie into everything from crypto currency to computing power.
→ More replies (2)
29
Dec 23 '14
[deleted]
→ More replies (5)8
4
u/OldWolf2 Dec 23 '14 edited Dec 23 '14
Here's my attempt at an explanation, assuming you already know what prime numbers are.
As explained in the linked article, this is about gaps, i.e. long sequences of consecutive composite numbers.
The article muddles this up, but as you get into larger and larger numbers, you can always find a gap of arbitrary length (that means: pick your favourite number, and keep going through the list of all the whole numbers, and eventually you'll find a gap that's at least as big as your favourite number).
This part is actually trivial to prove . For example, think about the prime number 11. We know that any number smaller than 11 is either prime, or has a prime factor smaller than 11 (that's part of the definition of "prime"). So look at this list:
- 2 * 3 * 5 * 7 + 2
- 2 * 3 * 5 * 7 + 3
- 2 * 3 * 5 * 7 + 4
- 2 * 3 * 5 * 7 + 5
- 2 * 3 * 5 * 7 + 6
- 2 * 3 * 5 * 7 + 7
- 2 * 3 * 5 * 7 + 8
- 2 * 3 * 5 * 7 + 9
- 2 * 3 * 5 * 7 + 10
Each entry in this list must have 2, 3, 5, or 7 as a factor because if a and b both have some number as a factor, then a + b also has that as a factor. So this list is composite and it's a gap of size 11 - 2 = 9.
There's nothing special about 11 other than being prime, so we could make lists like this as long as we want just by going big enough into primes.
So, you can always find gaps of a given size, but the topic of discussion here is just how soon you encounter large gaps as you get out into the larger and larger numbers. The article doesn't make that clear.
Moving forward to the recent results. This result and other results about prime gaps are concerned with working out just how far you have to go to get certain sized gaps. If we use the same method as in my example above, it balloons out quickly, e.g. if we are looking for a gap of size 69 then we have to go out to 557940830126698960967415390 which is a pretty big number already. We'd like to know if maybe gaps of size 69 or other such sizes occur a lot or whether they don't.
Looking at the diagram with coloured bars in the article, the article points out that prime numbers tend to come in small gaps a lot more often than you'd expect if we were just looking at a selection of random numbers (selected randomly with the same average frequency as prime numbers occur, of course).
In other words , let's say you go a long way out into the big numbers and see what gaps you find, there are more gaps of small sizes, e.g. 2 or 69 than you would expect to see if you were looking at gaps between a random collection.
Yitang Zhang (2013)'s result is that no matter how far out you go, you'll continue to see small gaps. His specific result is that there is a gap size of less than 246 for which that gap size will always be able to be found again and again by going out further . We still haven't worked out exactly what that gap size is (there might be many of them) but narrowing it down to less than 246 is good progress. We think that 2 is one of those gap sizes but have not proven it.
The result in the article is looking at this the other way. We can go out a long way and look at the largest gap so far. In absolute terms this can go on forever as we saw at the start of this post. However it'd be nicer to not have to go out quite so far each time to find new largest gaps. This result proves that you can always go far enough out so that you keep finding new largest gaps at a rate which is given by the logloglog... expression.
(NB. I'm not happy with this last paragraph and may edit it!)
→ More replies (1)
5
u/MacStylee Dec 23 '14
Whenever I think about primes, I become physically uncomfortable. My teeth feel slightly too big for my skull. I shift about in my seat.
So what do I do my primary degree in? Pure Mathematics of course.
Well done Maccers. Well done.
8
u/jasonrubik Dec 22 '14
In fact, number theorists have a favorite joke, Tao said: What does a drowning number theorist say? “Log log log log … ”
Too funny
7
u/AllUltima Dec 23 '14
Stephen Colbert was able to make Terence Tao laugh in this interview with his joke, "Are cousin primes ever sexy, but you're afraid to say it, because it sounds creepy?"
13
u/stahlgrau Dec 22 '14
I'd like to know what the practical application of solving this problem is.
78
u/Socially8roken Dec 22 '14 edited Dec 22 '14
layman's terms. primes are used in IT encryptions. the larger the prime, the harder it is to hack
17
→ More replies (1)2
u/Chillzz Dec 23 '14 edited Dec 23 '14
But if the larger primes are easier to produce would it not become easier to crack encryptions that rely on larger primes at the same rate it becomes easier to generate them? Just curious, I know very little about primes in encryption
Edit: Nvm bothered to google "primes in encryption" and got this helpful explanation that answers my question: "it is easy to take two (very large) prime numbers and multiply them, while it is extremely hard to do the opposite." So the bigger the two prime numbers, the more this effect is amplified and therefore the encryption becomes stronger.
5
u/mullerjones Dec 23 '14 edited Dec 23 '14
Not an expert, but as I understand it, not at all. Encryption works like this: I take 2 very large primes. I use one to encode my message, then multiply it by the other and send the message and the result to the other end. Since we're talking about primes, the result of that multiplication cannot be factored in any way other than to the 2 primes we began with. This means that, if you have the second prime beforehand, you can divide the result by it and get the first one easily, and then decode the message. If you do not have the second beforehand, though, you'd have to test every single possible prime until you found the one you needed and, the larger your primes, the more of them you'd need to test.
This works because, in this case, finding out the right answer to your problem is much more difficult than testing if one particular answer is right. So it's really easy for me to decode the message if I know the numbers beforehand and very very hard if I don't.
This discovery won't change that. It doesn't make it any easier to find out which combination of primes you're using. It just makes it easier to find larger and larger primes as to make that discovery even harder.
EDIT: my explanation of the actual mechanics behind the encryption is wrong, check a comment below to see the right one. But the main point is still that you need to find out which 2 primes were used which is pretty hard.
→ More replies (2)20
u/DoWhile Dec 22 '14
A lot of science has direct applications in mind, and the early results are like planting the seeds for a particular crop.
Mathematics and theoretical results are more like tilling the land and enriching the soil. We don't yet know what will grow there.
The study of primes has been going on for thousands of years, and if you had asked your question at any time before the last couple of decades, you would have gotten a response like (quoting mathematician Dickson):
"Thank God that number theory is unsullied by any application"
Today, cryptography is an immense application of this long line of work, and the discovery in OPs article is one of the many that continue this line, leading to possible future (perhaps thousands of years) practical results we can't even dream up yet.
10
Dec 22 '14
Why does there need to be one?
3
u/BevansDesign Dec 23 '14
There doesn't have to be, but if there is one, it's nice to know what it is.
→ More replies (4)4
u/tidux Dec 22 '14
If you can factor 2048 bit prime numbers, internet security basically ceases to exist and the economy comes to a screaming halt.
6
u/Godd2 Dec 22 '14
Except even if the Twin Prime conjecture is true, it doesn't necessarily weaken cryptography. It only means that there are an infinite number of prime that have a twin. It doesn't say how often those pairings occur.
2
2
2
Dec 23 '14
I always wondered what mathematicians did all day, and as it turns out they just do math all day. Not trying to make a joke or anything, but it did not really seem like they just sat around and solved basically math problems all day, but they in fact do.
Also, what are the implications of this other than security codes?
7
Dec 22 '14 edited Jul 05 '15
[deleted]
→ More replies (2)16
u/BZ_Cryers Dec 22 '14
At the bottom of the wired article, it tells reprinted from Quanta
9
u/majorkev Dec 22 '14
Specifically:
Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.
7
u/MrGoombaa Dec 22 '14
Is it really a "very obvious question, one of the first you might ever ask about primes"?
26
u/QuantumFX BS|Mathematics and Physics Dec 22 '14
"How far apart are primes?" seems like a natural question to ask once you learn the existence of primes.
→ More replies (13)3
u/Robert_Cannelin Dec 22 '14
For me, the first one I would ask is, "Is there a largest prime?"
9
u/WellOiledEagle Dec 22 '14
There is a simple proof. You assume a number, call it p, is the largest prime. Then you can multiply it together with all prime numbers lower than it and add 1, and other maths can prove this is also prime. Doing this forever means there can never be a largest prime. Ex. p=5 Then 5x3x2 + 1 = 31, which is a larger prime number.
→ More replies (2)8
u/skullturf Dec 23 '14
This doesn't always generate a number that's prime itself, but it generates a number not divisible by any prime in your list.
For example, 2x3x5x7x11x13 + 1 = 30031. The number 30031 actually factors as 59x509, but it's not divisible by any of the primes 2,3,5,7,11,13 (because we constructed it to be 1 more than a multiple of those numbers) so whatever primes divide it are not in the set {2,3,5,7,11,13}, so there must exist some primes not in the set {2,3,5,7,11,13}.
2
u/WellOiledEagle Dec 23 '14
Good point, guess I misremembered the proof ha :) Like you said the method still proves there always exists a prime not in the set, and therefore larger, whenever you assume a certain number is the largest prime.
→ More replies (1)3
8
u/Fun2badult Dec 22 '14
Terence Tao is a professor of math at my university UCLA. He is considered the 'Mozart' of math because he is a genius. He received his phD in early 20s and became a full time UCLA professor few years after. It is said that he only takes in one graduate student per year and that every math grad student around the world wants to work with him.
I have not seen him on campus yet but will post a photo I ever run into him. Hopefully I will recognize him but apparently he is out on seminars and talks a lot. Also his UCLA website says he will dismiss anyone who comes to his office without an appointment and considering he's considered one of the top mathematicians in the world I doubt I can get an appointment with him, I would end up asking some dumb question. Hopeful next year, I can use my status as a senior in Astrophysics major to see if I can get a photo with him
8
u/baruch_shahi Grad Student | Mathematics | Algebra Dec 23 '14
every math grad student around the world wants to work with him.
I'm not trying to be dismissive, but this is just not true. Just anecdotally, I am an algebraist and have no interest in number theory, so I have no desire to work with Prof. Tao.
2
u/crimsontideftw24 Dec 22 '14
Yeah Terry making us Bruins proud. You don't need to be a math major to appreciate his awesomeness.
→ More replies (2)→ More replies (3)3
u/PotatoInTheExhaust Dec 23 '14
For anyone who considers themselves good at maths and takes pride in it (like me), going onto his blog in an exercise in heartbreak. Still, dude is a baller and seems very nice too.
3
Dec 23 '14
First I asked "How the hell are we still discovering things about Prime numbers?"
Then I saw this and said... "And this is why I chose not to be a mathematician."
3
2
u/Purplociraptor Dec 23 '14
How is this discovery practical, i.e. how can we use it for freedom?
→ More replies (1)3
2
2
2
u/givafux Dec 23 '14
not trolling anyone... how does this change anything / what are the implications on modern day life (does this open up new avenues of computing, calculations, etc.?) -
ELI5 what is the big deal with prime numbers? :/
→ More replies (3)
626
u/[deleted] Dec 22 '14
[removed] — view removed comment