Slashdot Mirror
Another Breakthrough in Prime Number Theory
Battal Boy writes "From aimath.org: Dan Goldston and his Turkish colleague Yalcin Cem Yildirim have smashed all previous records on the size of small gaps between prime numbers. This work is a major step toward the centuries-old problem of showing that there are infinitely many 'twin primes': prime numbers which differ by 2, such as 11 and 13, 17 and 19, 29 and 31,...I am especially proud of this achievement as Yalcin is a close friend of mine from way back! You may also want to check out the Mercury News Article and Dan Goldston's home page where you can see a photo of Dan's back being slowly but surely broken by two of his children ..." Finding patterns in primes seems to be all the rage.
Here I thought the patterns-in-primes thing was already solved by Jodie Foster and Matthew McConaughey..
This is certainly a signficant advance in mathematics... prime numbers are one of the most enigmatic, yet useful aspects of number theory. What I'm really curious to see is whether or not this will help the efforts to find a more efficient algorithm for factoring a number into its prime factors. (A multiple of two very large primes is an integral part of RSA encryption, as well as other schemes.)
-- Apple: Where Microsoft wants to go today.
Funny, I can't see their server getting slashdotted anytime soon...
Any research that can make dealing with prime numbers easier can make cracking RSA asymmetric encryption (the most widely used atm) easier, and thus directly affect your privacy.
Apart from that, of course it's extremely boring, but so is everything, until you think of the applications.
Daniel
Carpe Diem
There's a small joke that goes around in the academic world
Biologists like to think they are chemists. Chemists like to think they are physicists. Physicists like to think they are mathematicians. And mathematicians like to think they are god.
Seriously, think of how much of what we learn boils down to our understanding of numbers, systems, and patterns within them. Mathematics, whether you like it or not, is really a beautiful and elegant subject that very few truly understand.
I was waiting for a better time to break this, but I guess now is good to. I have made a groundbreaking discovery in prime numbers.
No prime numbers can be divided by any number that falls inbetween the number one and the number itself! And, even more exciting, a rule that applies to all prime numbers. All prime numbers can be factored with the number one, but none can be divided by zero.
I hope none of you had anything important "encrypted" with PGP. Just stick to padless one-time pads for *real* security.
After I get the National Math Foundation to classify two as an odd number (and it is really odd considering it's the only even prime number) I'll have my third discovery that all prime numbers are odd validated.
I'd love to post more, but I really must get back to working on my perpetual motion machine. I was so close before, but recently I seem to have lost my bearings. Once I'm done I'll be heralded as the greatest man in the realm of science friction.
Have you read my journal today?
Conversely, having knowledge of more prime numbers also means that new encryption tech can be based on those new theories and enhance privacy. It's kinda a double edge sword...
This has nothing to do with encryption, nothing to do with RSA, nothing to do with practical applications at all. Factoring and cryptography is only a small part of the ocean that is number theory. Please don't automatically assume that anyting about number theory or prime is related to encryption and practical applications. This one certainly isn't. This is about twin primes: the authors have proven that the gaps between consecutive primes are small, asymptotically smaller than the logarithm of the number. This *might* lead to attacks on the twin prime conjecture. Nothing is known yet. This is highly theoretical work. Appreciate pure mathematics, with its beauty, for its own sake.
One reason that it is intuitivly possible that there are an infinite number of twin primes is that it is possible to generate numbers that are relativily prime. For example, multiply the first three primes: 2,3, and 5. You get 30. Add or subtract one from 30 and you will get a number that is relatively primet to 2, 3, and 5. In this case you get 29 and 31. Both happen to be prime numbers. We've found a twin.
The hard part of proving there are an infinite number of twins is finding a way of showing that your relatively prime numbers are truely prime. IE, in this case that neither is divisible by a higher prime such as 7, or 11.
Next step is to find prime numbers differing by 1.
When prime numbers were first discovered, don't you think everyone initially thought "Great... Who cares about these numbers that have no other factors?" In fact, if I was around when they were first discovered, I bet I would have thought it was a completely meaningless discovery. Who would have thought that later on, prime numbers would become a vital part of encryption? Anyway, my point is that although right now this seems to be of little practical value, who knows what future 'breakthroughs' will be based upon it? Perhaps someone will be inspired by this and come up with a revolutionary way allowing RSA to be cracked in microseconds? And even if no practical use is discovered any time soon, it's still one more thing better understood.
________________________________________________
suwain_2
How exactly does one hold on to frictionless bearings? Do you use [http://www.archive.org/movies/details-db.php?id=2 74]Johnson & Johnson plastic wraps to stick to them?
Several scientists were asked to prove that all odd integers higher than 2 are prime.
..."
http://www.math.utah.edu/~cherk/mathjokes.html
Mathematician: 3 is a prime, 5 is a prime, 7 is a prime, and by induction - every odd integer higher than 2 is a prime.
Physicist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is an experimental error, 11 is a prime. Just to be sure, try several randomly chosen numbers: 17 is a prime, 23 is a prime...
Engineer: 3 is a prime, 5 is a prime, 7 is a prime, 9 is an approximation to a prime, 11 is a prime,...
Programmer (reading the output on the screen): 3 is a prime, 3 is a prime, 3 a is prime, 3 is a prime....
Biologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 -- results have not arrived yet,...
Psychologist: 3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime but tries to suppress it,...
Chemist (or Dan Quayle): What's a prime?
Politician: "Some numbers are prime.. but the goal is to create a kinder, gentler society where all numbers are prime... "
Programmer: "Wait a minute, I think I have an algorithm from Knuth on finding prime numbers... just a little bit longer, I've found the last bug... no, that's not it... ya know, I think there may be a compiler bug here - oh, did you want IEEE-998.0334 rounding or not? - was that in the spec? - hold on, I've almost got it - I was up all night working on this program, ya know... now if management would just get me that new workstation tha just came out, I'd be done by now... etc., etc.
Saskboy's blog is good. 9 out of 10 dentists agree.
I don't think this will help cracking RSA in anyway. I even believe this will even strengthen the RSA encryption. RSA is based upon the fact that it is very difficult (as in there is no trivial way) to factor a composit number into two primes. And these new theories won't help factorization. Ofcourse, if there is indeed a usufull pattern, it may help to find the primes---that are required for factorization---faster, but the person who uses the RSA-technique can do this too. This will allow the this person to find even bigger primes faster then usuall, so even if the cracker can find possible usufull primes faster, he has to try a whole lot more to facter the composite number. And since trying out a factor to see if the is part of the composite takes much longer time, I only see benefits for the RSA encryption scheme.
You know it makes sense, a little reminder from jointm1k.
this joke?
An engineer, physicist, and mathematician are all challenged with a problem: to fry an egg when there is a fire in the house. The engineer just grabs a huge bucket of water, runs over to the fire, and puts it out. The physicist thinks for a long while, and then measures a precise amount of water into a container. He takes it over to the fire, pours it on, and with the last drop the fire goes out. The mathematician pores over pencil and paper. After a few minutes he goes "Aha! A solution exists!" and goes back to frying the egg.
Sequel: This time they are asked simply to fry an egg (no fire). The engineer just does it, kludging along; the physicist calculates carefully and produces a carefully cooked egg; and the mathematician lights a fire in the corner, and says "I have reduced it to the previous problem."
riding round the world on an old motorcycle
Short answer: Yes, -3 is prime in the integers.
Long answer:
So 3|6 because 6=3*2, and (-3)|6 because 6 = (-3)*(-2), and so on.
As an example of this, 48 = 6*8. 3|48, so for 3 to be prime, we would need either 3|6 or 3|8.
Since 3|6, it passes the test in this case (but remember, the condition has to be true for all pairs of integers.)
since 3|a if and only if (-3)|a (Proof: Slashdot post is too small to contain it
You want boring? Then go and take a look at the PDF papers on this site.
Are they boring? Yes, exruciatingly and mind numbingly so...
Did they help us win the Second World War? err...yes
A cynic is what an idealist calls a realist...
How about calculating the rate of ring growth in trees as well?
One per year.
See you in stockholm!
Fleur de Sel
From the Mercury News:
``Mathematicians described the advance -- announced at a conference in Germany -- as the most important breakthrough in the field in decades."
Oh, & proving Fermat's Last Theorem in 1995 was just another undergraduate exercise?
(For the non-math-nerds, proving true Fermat's Theorem -- that the formula a^n * b^n = c^n was insolveable where n is greater than 2 -- was considered for three _centuries_ to be _the_ principal challenge in mathematics. The man who did this -- Andrew Wiles -- spent about 30 years working on this, & succeeded only after a second try.)
Geoff
I think I see a trend here. Maybe for them it really would be easier to muzzle the entire internet than to produce p
Small gaps between consecutive primes
:= lim_inf(n -> +inf, (p_(n+1) - p_n) / log(p_n))) = 1
Recent work of D. Goldston and C. Yildirim
What are the shortest intervals between consecutive prime numbers? The twin prime conjecture, which asserts that p_(n+1) - p_n = 2 infinitely often is one of the oldest problems; it is difficult to trace its origins.
In the 1960's and 1970's sieve methods developed to the point where the great Chinese mathematician Chen was able to prove that for infinitely many primes p the number p + 2 is either prime or a product of two primes. However the well-known ``parity problem'' in sieve theory prevents further progress.
What can actually be proven about small gaps between consecutive primes? A restatement of the prime number theorem is that the average size of p_(n+1) - p_n is log(p_n) where p_n denotes the nth prime. A consequence is that
delta
In 1926, Hardy and Littlewood, using their ``circle method'' proved that the Generalized Riemann Hypothesis (that neither the Riemann zeta-function nor any Dirichlet L-function has a zero with real part larger than 1/2) implies that delta = 2/3. Rankin improved this (still assuming GRH) to delta = 3/5. In 1940 Erdös, using sieve methods, gave the first unconditional proof that delta 1. In 1966 Bombieri and Davenport, using the newly developed theory of the large sieve (in the form of the Bombieri - Vinogradov theorem) in conjunction with the Hardy - Littlewood approach, proved delta = 1/2 unconditionally, and then using the Erdös method they obtained delta = (2 + sqrt(3))/ 8 = 0.46650... . In 1977, Huxley combined the Erdös method and the Hardy - Littlewood, Bombieri - Davenport method to obtain delta = 0.44254. Then, in 1986, Maier used his discovery that certain intervals contain a factor exp(gamma) of more primes than average intervals. Working in these intervals and combining all of the above methods, he proved that delta = 0.2486, which was the best result until now.
Dan Goldston and Cem Yildirim have a manuscript which advances the theory of small gaps between primes by a quantum leap. First of all, they show that delta = 0. Moreover, they can prove that for infinitely many the inequality
p_(n+1) - p_n (log(p_n))^(8/9)
holds.
Goldston's and Yildirim's approach begins with the methods of Hardy-Littlewood and Bombieri - Davenport. They have discovered an extraordinary way to approximate, on average, sums over prime k-tuples. We believe, after work of Gallagher using the Hardy-Littlewood conjectures for the distribution of prime k-tuples, that the prime numbers in a short interval [N, N + lambda log(N)] are distributed like a Poisson random variable with parameter lambda. Goldston and Yildirim exploit this model in choosing approximations. They ultimately use the theory of orthogonal polynomials to express the optimal approximation in terms of the classical Laguerre polynomials. Hardy and Littlewood could have proven this theorem under the assumption of the Generalized Riemann Hypothesis; the Bombieri - Vinogradov theorem allows for the unconditional treatment.
This new approach opens the door for much further work. It is clear from the manuscript that the savings of an exponent of 1/9 in the power of log(p_n) is not the best that the method will allow. There are (at least) two possible refinements. One is in the examination of lower order terms that arise in his method. Can they be used to enhance the argument? The other is in the error term Gallagher found in summing the ``singular series'' arising from the Hardy-Littlewood k-tuple conjecture. There is reason to believe that this error term can be improved, possibly using ideas in recent work of Montgomery and Soundararajan (``Beyond Pair - Correlation''.)
It is not clear just how far this method can be pushed and what other problems might be attacked using his new ideas; at this point we can't rule ou
new encryption tech can be based on those new theories
And the terrorists will win! Quick, ban math!
Not so fast with the assumption that people protecting information can just automatically make use of new techniques. The idea with encryption is that you transmit your information over an insecure channel. This means that the bad guys already have copies of your information, encrypted using the techniques you used. If new techniques become available, you can't go back and use them on your old data, because it's already been transmitted. Therefore, in an arms race where cryptography and cryptanalysis proceed at equal rates, all the information you already own becomes increasingly vulnerable.
People (or agencies) holding a portfolio of critically sensitive information that has already been transmitted (and therefore probably intercepted in encrypted form) have a vital and sustaining interest in research into prime numbers. In many case their interest is in having such research stopped. It will be interesting to see what happens to super-smart but real-world-naive math Ph.D candidates if and when high efficiency factoring techniques become the subject of dissertations....
-Graham
There is a small missunderstanding here. The smallest gap between two primes is 1 (between 2 and 3). But there is only this one pair of primes (2, 3) with such a small gap. But the next smallest gap 2 happens several times, between 3 and 5, 5 and 7, 11 and 13, 17 and 19 etc.pp.
So the question is: Does this happen at very large primes too? Are there primes between 10^50 and 10^55 which are just 2 apart? Note that the primes get more and more seldom, if you move at higher numbers.
The mathematic society knows since a long time that the distance between two neighbouring primes p(n) and p(n+1) is smaller than log(p(n)). But log(p(n)) grows also steadily, even much more slowly than p(n).
The mathematic society knows also that surprisingly small gaps between prime numbers happen von time to time. So the best number known until now was that there is an infinite number of primes p(n), where p(n+1) - p(n) was smaller than log(p(n)) * 0,22... (which grows also, but very, very slowly...)
The breaking news is, that now the factor 0,22... got improved to 0, which doesn't grow at all.
That means: there is an infinite number of primes, for which (p(n+1) - p(n))/log(p(n)) is quite close to 0.
This means: There are infinite often pairs of primes whose difference is quite small... It could easily be that the difference is 2 for an infinite number of pairs, which is not proved yet, but at least the minimal distance of two neighbouring primes does not grow beyond a very low number.