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.

Comments

Good work

[wyvern5]

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.)

other patterns in prime numbers

[TerraFrost]

you can read about other patterns in prime numbers from mathworld... here:

here

Question of the Day

[crashnbur]

Is -3 a prime number?

Do negatives count? Or do 3 and -3 count as factors? And if this is so, then what stops a positive number from being composite when its factors can include its negative and -1?

Re:Question of the Day

[BitterOak]

Customarily we consider only the set of positive integers when discussing primality. However, primality can be defined in any ring (such as the integers) as follows: a number is prime if it is divisible only by itself, units, or products of itself and units. A unit in any element of a ring which has a multiplicative inverse. The only units in the ring of integers are thus 1 and -1. So a prime integer is an integer divisible only by itself, 1, -1, and -1*itself.

In the ring of polynomials with real coefficients, the units are the constants (zero-order polynomials), and so a polynomial like x+1 is considered "prime", although the term "irreducible" is usually used instead when talking about polynomials.

In the ring of rational numbers (which also happens to be a field), all non-zero numbers have multiplicative inverses, so all rational numbers are prime (in the rationals) making it a not very useful concept there!.

Re:Interesting?

[jointm1k]

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.

Buffon's Needle

[Flamesplash]

Indeed, take Buffon's Needle Problem for instance. whoda thunk it.

Boring?

[Battal Boy]

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

Prime Number Advances

[Effugas]

Mathematicians described the advance -- announced at a conference in Germany -- as the most important breakthrough in the field in decades.

Personally, I think the technique for provably determining the primality of an arbitrary number in polynomial time -- "PRIMES is in P" -- was a more unexpected result. It's always seemed like the probability of a twin prime occuring on the number continuum was a limit approaching but never quite reaching 0 -- an artifact of the number of previous primes already "exposed" approaching, but never reaching infinity. But actually sitting down and proving this -- excellent! Very cool.

--Dan

Re:Proof of twin primes

[j3110]

You can't use statistics or probabilities as proofs :)

I don't think you'll find anyone that will make a wager that there aren't an infinite amount of twin primes, but there is no definitive proof.

Basically, for all prime numbers less than the square root of the number between two primes, it's easy to see that it is possible that their multiples could add up to either be on this middle number or at least more than 3 or more away. Pretty much the theory is only going to show that numbers that are a multiple of 2 and 3 are possibly between 2 prime numbers. Pick any number not a multiple of 2 and 3 and a number on either side will either be divisible by 2 or 3. I would assume that a proof could be extended through this by saying that there would have to always be another multiple of a prime number that happens to land one away from a multiple of 2 and a multiple of 3 for every number 2^x*3^y (for all x,y where 2^x*3^y>Q and 2^x*3^y is prime there exists a number z such that z divides 2^x*3^y+1 or z divides 2^x*3^y-1).

This is a little trickier considering it has already been proven that there is no number > than some number I can't remember at the moment such that it is divisible by all prime numbers less than it's square root. (there are no numbers that have both factors > it's square root... easily proven :) )

With weird things like this going on with prime numbers it's hard to tell. Despite your obvious instincts that there should be a number x that happens to be a multiple of all prime numbers less than it's square root and still be large, it just isn't so.

Everytime you find something else about prime numbers, there is yet more questions about them. If this gets proven, the next logical step would be to prove that there are infinite number of prime numbers that are 2x apart from each other. If it gets disproven, we'll want to see exactly where it stops being true, and why. From there, we will only find more questions than answers :)

Re:Interesting?

[ghjm]

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

Why Only Number Theory?

[Jagasian]

I love mathematics (especially stuff like Category Theory, Lambda-calculi, etc...), but why does Slashdot always post number theory stories? You can try to view all of math through numbers, but you are missing out on allot of structure by doing so.

This article made bigger history

[rithvik]

I'm giving the direct link.
http://www.cse.iitk.ac.in/news/primality.ht ml