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.
Both of those are solved problems. Differential equations can model them well... Yes, I know that wasn't your question, but you know the joke about the mathematician in the burning building, right?
-- Apple: Where Microsoft wants to go today.
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.
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
Well... if your two primes are p-1 and p+1 you could use them as the primes in the RSA algorithm. I mean, it's not like it's trivial to break a composite number of the form p^2-1. :-)
(For those who don't know applied number theory, when factoring a number you first try the small primes, then assuming two large factors of the form (p-n)(p+n) = p^2-n^2.)
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
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
(For those who don't know applied number theory, when factoring a number you first try the small primes, then assuming two large factors of the form (p-n)(p+n) = p^2-n^2.)
For those who don't know applied number theory, here is somewhat better look at existing factoring algotirthms.
3.243F6A8885A308D313
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
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.
Ummm, those piValue's are there because sin takes an argument in RADIANS. If Math.sin used degrees instead, that lines would be
All it is doing is psedurandomly generating an ANGLE and taking the sine of it to determine the X component of the needle's direction vector.Your comment reminds me of the people who saw
in Fortran programs and assumed that meant that on September 9th, 1999, all the Fortran code would stop working!ASCII stupid question, get a stupid ANSI
In principle, yes. It depends why you want to try to factor the number, though.
To a first approximation, for numbers n-bits long, roughly every nth number is prime. (To a second approximation, it's every n*ln(2).) If you're trying to find a random prime or near-prime in some range (e.g. for RSA key generation), then you will have to reject a few numbers before you get there.
Most of those rejected numbers will fail the "small primes" test, where you pick all primes smaller than some number (e.g. less than 1000) and try dividing. This, I believe, is what the poster meant by "first try[ing] the small primes". If your number passes the "small primes" test, then you can apply some algorithmically more expensive tests (e.g. Fermat testing).
Of course, if your number is not random, and have reason to believe that your number will pass the small primes test (e.g. if it's an RSA modulus), then this probably won't help you.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Personally, I think the technique for provably determining the primality of an arbitrary number in polynomial time -- "PRIMES is in P" [iitk.ac.in] -- was a more unexpected result.
:). We've known since Atkin-Goldwasser-Morain how to *provably* determine the primality of an arbitrary number in randomised polynomial time. AKS succeeds in derandomising this problem and is a very clever accomplishment. But the present paper represents a quantum leap in understanding in an area that number theorists have been working on since the early 1900's. It seems to be a much deeper theoretical technique.
You'd be wrong, though
With RSA, I thought you wanted "strong primes," not just primes.
In general I don't think that is the case, but some special uses of RSA makes that requirement. The "safe primes" are harder to find because there is not that many of them.
But finding primes is a different task than factoring numbers. The algorithms for finding primes is a lot more efficient than factoring, if they weren't RSA wouldn't make much sense. There is an algorithm that will find a prime and a proof it is a prime, with a minor modification it will produce "safe primes". The proof basically consits of a factorization of p-1 together with a recursive proof that the factors are primes. The reucursion ends when you reach the prime 2, because p-1 will then be 1 and has the empty set as its prime factorization. There is a litle more to the proof than this, but in fact if you are just given a list of all the primes involved in the primality proof you can easilly reconstruct the entire proof.
But usually you don't need a proof, so instead you use a probabilistic algorithm for veryifying primality. You can write a very efficient algorithm that gives sufficiently small probability of ending up with a non-prime. If the probability that one of your "primes" is not a prime is as small as the chance of the attacker finding your prime by his first random guess, that is not a problem.
Do you care about the security of your wireless mouse?
Here is a counterexample for your 'proof':
(2*3*5*7*11*13)-1 = 30029 is prime
(2*3*5*7*11*13)+1 = 30031 = 509*59 (composite)
If q is the product of a set of primes P, then q+1 and q-1 are relatively prime to each p_i, i.e.
(q+1) % p_i = 1, and (q-1) % p_i = p_i - 1. However there are no guarantees about the relative primality of q with respect to some prime p not in P.
If the p_i in P are consecutive starting with 2, then we do know that Q+-1 must either by prime itself, and thus larger than any prime in P, or a composite of 2 or more primes, each of which is larger than any prime in P.
Given the set of all known primes, we can always generate a new unknown prime, thus expanding our set, and therefore guaranteeing the set of all primes is infinite.
Every triple of that form contains at least one number that can be divided by 3. If you want all numbers to be prime, the number 3 itself has to be among the three numbers, hence the triple 3,5,7, is the only one. (short idea of the proof, the full one would require a few more lines of text)
I intend to live forever, so far so good.