Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
Science

Another Breakthrough in Prime Number Theory 241

Posted by timothy from the brother-go-find-your-brother dept.
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.
This discussion has been archived. No new comments can be posted.

Another Breakthrough in Prime Number Theory More

Another Breakthrough in Prime Number Theory

Comments Filter:
  • Ok, so there are infinite twin prime numbers but what about secondary numbers? Have we just given up on them?

  • Patterns in primes? (Score:5, Funny)

    by TobiasSodergren ( 470677 ) on Sunday March 30, 2003 @01:38PM (#5626741)
    Here I thought the patterns-in-primes thing was already solved by Jodie Foster and Matthew McConaughey..

  • Good work (Score:4, Interesting)

    by wyvern5 ( 565676 ) on Sunday March 30, 2003 @01:38PM (#5626742)
    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.)
    • Although I've not read the paper, I do not think this is a puritarian proof. From the site -

      So Goldston picked off a more manageable piece of the problem: Can you always find prime numbers that may not be twins, but that are much closer together than average? Taking into account, of course, the fact that the bigger numbers get, the sparser primes become.

      Sounds more like its a proof through mathematical induction than anything else.
      • A proof through induction is a pure and valid proof for a property on countably infinite sets, which, being a real subset of natural numbers, prime numbers are.

        As far as I understand it, it is "just" a proof that the prime numbers are not evenly distributed, even for arbitrary large numbers.

  • Slashdotted? (Score:5, Funny)

    by cyb97 ( 520582 ) <cyb97@noxtension.com> on Sunday March 30, 2003 @01:39PM (#5626744) Homepage Journal
    Funny, I can't see their server getting slashdotted anytime soon...
  • Are there any?

    • Re:Practical benefits? (Score:5, Insightful)

      by suwain_2 ( 260792 ) on Sunday March 30, 2003 @02:10PM (#5626879) Journal
      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.
      • It was not my intention to sound like "Great, another useless scientific "discovery"". I was merely curious that are there any tangible benefits to be had from this right now.
  • Patterns! Maybe they should get Maximillian Cohen [pithemovie.com] involved!

    =Smidge=

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

    • Buffon's Needle (Score:4, Interesting)

      by Flamesplash ( 469287 ) on Sunday March 30, 2003 @02:29PM (#5626958) Homepage Journal
      Indeed, take Buffon's Needle Problem [angelfire.com] for instance. whoda thunk it.
    • 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.

      FYI, there's another version of that joke which ends on "philosophers".
    • Mathematics is art. A proof from The Book (Erds fans will know what I'm referring to) is as aesthetically appealing as a Renoir or a Van Gogh. There have been many instances where I've read a proof and been moved to tears of joy.

      I'm not a mathematician, but mathematics will always be my first love (which might explain the lack of success in <ahem> another area...) :-)

    • I think you're grossly overestimating how many people truly understand mathematics. I'll venture 'no one' as the true answer to that, and ask for any counter examples.
    • 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.


      And God created man (and all that other biology stuff) :)
  • 2^3-1 is prime! Now checking 2^3+1...

  • Moo (Score:5, Funny)

    by Chacham ( 981 ) on Sunday March 30, 2003 @01:52PM (#5626801) Homepage Journal
    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.

    • Re:Moo moo? (Score:5, Funny)

      by saskboy ( 600063 ) on Sunday March 30, 2003 @02:14PM (#5626906) Homepage Journal
      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?

      http://www.math.utah.edu/~cherk/mathjokes.html
      Several scientists were asked to prove that all odd integers higher than 2 are prime.

      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. ..."
      • How exactly does one hold on to frictionless bearings?

        Actually, after discovering the real answer of the square-root of two, I filtered some dirt, dehydrated some water, and desalinated some salt. I then came up with *exactly* what would hold them.
    • The number 2 is prime, and is indeed even. Don't quit your day job.

  • other patterns in prime numbers (Score:3, Interesting)

    by TerraFrost ( 611855 ) on Sunday March 30, 2003 @01:53PM (#5626806)
    you can read about other patterns in prime numbers from mathworld... here:

    here [wolfram.com]

    • I'd be interested in knowing if anyone has attempted to plot this as a fractal [triumf.ca]?

      BTW: there is a linux version of Fractint [dyndns.org] available. WooHoo!

      I remember waiting over 60 hours for a single screen to draw on some of the deep zooms of the Mandlebrot set when I was running a SOTA 33 Mhz 386. Timothy Leary would not have survived the 60s if he'd had a copy of Fractint and something to run it on at the time :-)

  • Before somebody asks the question... (Score:5, Insightful)

    by arvindn ( 542080 ) on Sunday March 30, 2003 @01:58PM (#5626828) Homepage Journal
    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.

    • Re:Before somebody asks the question... (Score:5, Informative)

      by coyote-san ( 38515 ) on Sunday March 30, 2003 @02:46PM (#5627018)
      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 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 [frenchfries.net] at existing factoring algotirthms.
      • I mean, it's not like it's trivial to break a composite number of the form p^2-1. :-)

        In fact it is trivial, but of course there is no need telling that, because every real geek would have figured that out long time ago.

        For those who don't know applied number theory, when factoring a number you first try the small primes

        In fact there is much more efficient ways to factor large numbers than by trying to divide with each and every prime.

        • Re:Before somebody asks the question... (Score:4, Informative)

          by Pseudonym ( 62607 ) on Sunday March 30, 2003 @06:23PM (#5628120)
          In fact there is much more efficient ways to factor large numbers than by trying to divide with each and every prime.

          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.

          • It's been a while since I studied RSA prime selection, but I'm sure someone will rush to correct my errors.... :-)

            With RSA, I thought you wanted "strong primes," not just primes. A strong prime p is one such that p = 2p' + 1, where p' is also prime. This means that Phi(pq) = (p-1)(q-1) = 4p'q'.

            Anyway, in practice this means that you'll go through a lot of primes before you find one suitable for use in an RSA key. That's why it takes so long to generate an RSA keypair....
            • 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 mod
        • It's not a question of efficiency. Even a 512-bit keypair has 256-bit factors, and it's just not practical to do that many trial divisions.

          My point, which seems to have been misunderstood, is that nobody should ever turn to the heavy factoring algorithms without first exhausting all of the trivial checks. A few hours spent on trial division, checking for close factors, etc., is nothing when held against the tremendous effort of cracking the numbers via ECD or whatever is the preferred factoring method to
      • 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. :-)

        Took me a minute to realize why this was marked funny...basically, the square root of your dual-prime composite is approximately p :-)

        --Dan
        • I'm not quite sure why it was marked 'funny' either, but it's not just a matter of the square root being "approximately" p.

          What you do is generate a sequence of small integers, square them, then add them to your composite number. You then check whether the result is a perfect square - I seem to recall there are efficient checks for this which don't involve actually computing the root, or you could just use Newton's method to determine the root.

          If, despite all odds, you find a perfect square then you know
          • No, it really is as simple as square roots :-)

            Here, lemme pull out Acme Software's BIC (basically, bc with prime functionality). 18409199 is the 100,000th twin prime.

            For those not proficient in bc, I've taken the liberty of illustrating when I type and when the computer responds. I'm basically setting variables; when there is no equality specified, the output is redirected to the screen. My typing is in bold.

            ===
            a=18409199
            b=a+2
            c=a*b
            c
            338898644639999
            d=sqrt(c)
            d
            18409199
            c/d
            18409201

            ===

            I tried
            • By definition, your sqrt() function is broken. Many programs wouldn't even try, since no number ending with '99' (base 10) can be a perfect square. (You would actually look at the last byte or word, of course.)

              Add 1, and the sum ends with '0000' and you can immediately see that any root has to end with '00'.

              But this somewhat misses the point - factor 338959063631117. You could factor it by enumerating small primes, or you could note that adding 1642^2 gives you 338959066327281, a perfect square. 18410

  • Question of the Day (Score:2, Interesting)

    by crashnbur ( 127738 )
    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 (Score:3, Insightful)

      by coreyb ( 125522 )
      Strictly speaking, negative numbers can be prime, however, -x is prime if and only if x is prime, so number theorists usually just deal with the positive ones.
      As for "counting as factors," one has to look at the definition. An irreducible is a number (well, non-unit element of a ring) such that every factorization has a unit as one of the factors. In the integers, 1 and -1 are the units.
      A prime is a number such that if it divides a product, it divides one of the factors. In the integers, these come down

    • Re:Question of the Day (Score:5, Informative)

      by BabyDave ( 575083 ) on Sunday March 30, 2003 @02:31PM (#5626967)

      Short answer: Yes, -3 is prime in the integers.

      Long answer:

      • If a and b are integers, we say that a divides b (and write a|b) if b = a*c for some integer c.
        So 3|6 because 6=3*2, and (-3)|6 because 6 = (-3)*(-2), and so on.
      • An integer p is called prime if for any pair of integers a, b we have that p|(a*b) implies p|a or p|b.
        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.)
      • It turns out that this definition of a "prime number" is the same as the usual one for integers.
      • We know (well, we can show) that 3 is prime. From this we can show that -3 is prime as well,
        since 3|a if and only if (-3)|a (Proof: Slashdot post is too small to contain it ...)
      /me goes back to avoiding revision ...
    • They were once only divisible by 1 and P. Now it turns out they're all divisible by -1 and -P as well. Dammit, all the textbooks are going to have to be changed!
    • 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 coef

  • > This work is a major step toward the
    > centuries-old problem of showing that there are
    > infinitely many 'twin primes':

    If the goal is indeed to prove that there are an infinite number of twin primes demonstrating the existence of any finite number of them, however large, is no step at all.
    • Now that I have been able to get through and read the article I see that what these guys have done is quite different and much more interesting than what the Slashdot blurb implies.
    • If the goal is indeed to prove that there are an infinite number of twin primes demonstrating the existence of any finite number of them, however large, is no step at all.

      This reminds me of a greasemonkey buddy of mine in high school. I was taking calculus at the time and he said "I've seen calculus. It's all bullshit, it's just a bunch of x's and y's."

  • Twin primes (Score:5, Informative)

    by DeadSea ( 69598 ) on Sunday March 30, 2003 @02:05PM (#5626859) Homepage Journal
    I wanted to offer some insight into why twin primes happen in the first place. If you are not familiar with the phenomenon, twin primes are pairs of primes which differ by two. The first twin primes are [3,5], [5,7], [11,13] and [17,19]. It has been conjectured (but never proven) that there are infinitely many twin primes. Very large twin primes have been found and these seem to occur consistently thoughout the known prime number.

    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.

    • Heh... I 'proved' this to myself a few years back in middle school.
      Since all primes come in the form 6k±1 (except 2, which is a special case), you can consider all primes to be either a 6k+1 or 6k-1. I ran Mathematica for a few days using a sieve taking advantage of this to come up 2 graphs of the distance between two consecutive primes of the same type. Both were consistent with the same logarithmic function, showing that both tend to grow at very nearly the same rate. Unless something catastrophic ha

  • Next step (Score:4, Funny)

    by pdan ( 624244 ) on Sunday March 30, 2003 @02:09PM (#5626877)
    Next step is to find prime numbers differing by 1.

    • Re:Next step (Score:5, Funny)

      by Yokaze ( 70883 ) on Sunday March 30, 2003 @02:19PM (#5626918)
      I'll start: 2 and 3. You'll have to find the next pair.

      • Re:Next step (Score:2, Funny)

        by jpkunst ( 612360 )

        OK: 1 and 2. You're next.

        • Sorry, 1 ain't a prime. A prime number has two unique divisors: 1 and itself. 1 only has one divisor, and is therefore a special case, neither prime nor composite.
          • While you're correct, and 1 is not a prime, it's not because of the reasons that you've stated; part of the formal definition of a prime element in a ring is that it cannot be a unit (i.e. an element that has a multiplicative inverse in the ring - which basically means an element that can be multiplied by another element to give 1). The only units of the integers are {-1, 1}, and so they are not considered primes.
          • Only on /. could you find an article about breakthroughs and discoveries regarding prime numbers...

            ...as well as people discussing (maybe even arguing) over whether the number "1" is or is not a prime.

        • As another poster mentioned, 1 is not a prime element of the integers. Basically, in algebra, we have the concept of a unit, which is an element that has a multiplicative inverse (i.e. which can be multiplied by another element to give 1). Part of the definition of being a prime is that you cannot be a unit.

          In the integers, it's easy to see that the only units are -1 and 1 (e.g. 5x = 1 has no integer solution, so 5 is not a unit). Because of this, 1 is not a prime element of the integers, and thus, not a p
  • Can anyone explain what either of these things signifies or what their impact is...for non-mathematicians?
  • Given that prime numbers are infinite, and given that the regularity with which they occur does not seem to have any set frequency, can we not say twin primes are also (likely) infinite?

    Obviously that is not at all rigorous but it strikes me as being true.

    --Joey

    • Re:Proof of twin primes (Score:3, Interesting)

      by j3110 ( 193209 )
      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 multipl
      • 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

        should have been

        for all x where 6x>Q there exists a number z such that z divides 6x+1 or z divides 6x-1

  • Boring? (Score:5, Interesting)

    by Battal Boy ( 544978 ) on Sunday March 30, 2003 @02:40PM (#5627001) Homepage
    You want boring? Then go and take a look at the PDF papers on this site [home.cern.ch].

    Are they boring? Yes, exruciatingly and mind numbingly so...
    Did they help us win the Second World War? err...yes

  • Prime Number Advances (Score:4, Interesting)

    by Effugas ( 2378 ) on Sunday March 30, 2003 @02:49PM (#5627030) Homepage
    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" [iitk.ac.in] -- 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:Prime Number Advances (Score:2, Informative)

      by Anonymous Coward
      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.

      You'd be wrong, though :). 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 n
  • I believe this is a link to the paper...
    ftp://ftp.msri.org/pub/publications/preprints/2000 /2000-014/2000-014abs.html
    Not too sure but looks like a preprint of the thing

  • You Smartasses Missed the Error (Score:5, Informative)

    by llywrch ( 9023 ) on Sunday March 30, 2003 @03:09PM (#5627120) Homepage Journal
    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
    • The man who did this -- Andrew Wiles -- spent about 30 years working on this, & succeeded only after a second try

      I was about to correct this but a quick look through Fermat's Last Theorem proves you're absolutely right: he first heard of the problem aged 10 and finally solved it after turning 40 having spent much of his life studying everything about it.
      That's a scary kind of dedication, especially for a problem which might not have been soluble.
    • No. The Fermat Conjecture was never considered the a terribly important question in number theory. he Riemann Hypothesis is much more important. One could also make the case for Golberg's Conjecture or the Twin-prime conjecture.
    • My wife's Grandfather believes he has a very elegant two-page proof...or at least close enough to a proof to be what Fermat was probably thinking about.

      The problem he has had is that no serious mathematician is willing to REALLY look at it beyond either dismissing the idea out of hand or saying "eh, looks kinda nice, maybe". (I'm not a serious mathematician so all I can say looking at it is "well, if these givens you assure me are true are so, then I can say that from each step to the next I think you're m

  • Nitty gritty without karma whoring, poor site /.ed (Score:5, Informative)

    by Anonymous Coward on Sunday March 30, 2003 @03:19PM (#5627164)
    Small gaps between consecutive primes

    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 := lim_inf(n -> +inf, (p_(n+1) - p_n) / log(p_n))) = 1

    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

  • Mis-statement (Score:2, Funny)

    by Ancil ( 622971 )
    smashed all previous records on the size of small gaps between prime numbers
    That record is held by the prime numbers 2 and 3, and it's a record not likely to be broken.

  • Why Only Number Theory? (Score:3, Interesting)

    by Jagasian ( 129329 ) on Sunday March 30, 2003 @09:24PM (#5628844)
    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.

  • His timing obviously relates to his kids age :-) (Score:3, Funny)

    by oren ( 78897 ) on Monday March 31, 2003 @06:22AM (#5630460)
    "A hint of his sense of humor can be found on his Web site, which features a photo of Goldston, seemingly dozing off, as two small kids climb on his back. He and his wife, Ryoko, have three children -- Shota, 7, Aiko, 5, and Makoto, 3."

    Can we can expect his next theorem to deal with prime triplets?

Slashdot Top Deals

The moon is made of green cheese. -- John Heywood

Close