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

Interesting?

[ChaoticChaos]

Zzzzzzzzzzzzzzzzzzzzzzzzz.

How about calculating the rate of ring growth in trees as well? How about the speed that paint will dry at various temperatures? ;-)

Re:Interesting?

[Epistax]

Don't make fun of this. This is vitally important. Finally we'll know.. wait what are we doing again? Prime number theory? Fuck it gimmie a beer

Re:Interesting?

[ChaoticChaos]

Epistax and ChaoticChaos clink the glasses together...

Re:Interesting?

[KDan]

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

Re:Interesting?

[wyvern5]

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?

Re:Interesting?

[LostCluster]

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

Re:Interesting?

[TopShelf]

Oh come on... enlighten us, you tease!

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.

Re:Interesting?

[chimpo13]

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

Re:Interesting?

[Squareball]

It's posts like these that make me wish there was a mod option of "What the??" I am lost lol ;)

Re:Interesting?

[giblfiz]

Zzzzzzzzzzzzzzzzzzzzzzzzz.

How about calculating the rate of ring growth in trees as well? How about the speed that paint will dry at various temperatures? ;-)

This is slashdot, not CNN. Its news for nerds, most of us here find math interesting, just because of its meticulous nature. For that matter, I would be very interested if someone came up with non-obvious insights into how fast trees grow, or the nature of paint drying.

Re:Interesting?

[matt4077]

How about calculating the rate of ring growth in trees as well?

One per year.

See you in stockholm!

Re:Interesting?

[base2op]

Apart from that, of course it's extremely boring, but so is everything, until you think of the applications.

As a physics undergrad, I resent that. : (

Re:Interesting?

[CableModemSniper]

just because of its meticulous nature

Seems like an odd reason to enjoy math. Do you sit down and write out the Fibonacci sequence for kicks? Not that I am saying I don't think math is interesting (it is) but I don't think its interesting *because* of its meticulous nature, and even if it is for some, I seriously doubt its *just* because of its meticulous nature. Joking about the fibonacci thing, btw.

Re:Interesting?

[telstar]

"Fuck it gimmie a beer"

• Beer ... the cause of - and solution to - all life's problems.
• 
  
  -Homer Simpson
  
  Maybe we can use it to figure out this prime number thingy.

Re:Interesting?

[isorox]

new encryption tech can be based on those new theories

And the terrorists will win! Quick, ban math!

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

Re:Interesting?

[You're All Wrong]

What complete bullcrap. This has no implications for RSA or cryptography at all.

The story is a misrepresentation anyway - no "records" have been "smashed". This is simply a new asymptotic improvement in some particular feature of prime number distribution. (There are an infinitude of consecutive primes whose gap between them satisfies some relation based on teh size of the prime.)

There used to be an big-Oh relation and now it's a little-oh relation, so it's far more significant than the simple multiplicative-constant improvements that have been achieved over the last 80 years or so.

There are no numeric embodiments of this analytic improvement, so there are no "records" to "smash". The proved theorems are all _so_ far away from the real distribution that these models are practically useless.

i.e. Moderate parent down.

For prime number information, start at http://primepages.org/
For relevant prime distribution background info, your best bet is to google for "Chen" and "Vinogradov", but my betting is that the best links will be the ones to Mathworld.

YAW

Re:Interesting?

[Hater's Leaving, The]

Don't worry - the reason you don't follow what he's saying is because he's
karma-whoring and trying to spout something theat looks vaguely mathematical.
e.g.:
"""
Ofcourse, if there is indeed a usufull pattern, it may help to
find the primes---that are required for factorization---faster,
"""

Which is patent nonsense. Finding non-trivial primes is in no way required
for factorisation.

It's not required for trial-division (they're all trivial), pollard rho,
pollard P-1 (all trivial), williams P+1 (all trivial), ECM (all trivial),
shanks' squfof, the Quadratic sieve (all trivial), or the Number Field Sieve
(all trivial). Have I missed any? Oh yes I have - it's also not required for
Euler's algoritm, Legendre's algoritm, Fermat's algorithm, or Lehman's
algorithm. Nor for the Continued Fraction algorithm. There are some more
esoteric ones (Bach's cyclotomic technique, gaussian rings, hyperelliptic
curves etc) too, and they don't require it either.

All techniques apart from trial-division simply have the factors drop out
using a GCD of the composite number and the _difference between two elements_
in the ring of residues. The difference in the techniques is how you
generate the two elements that you are taking the difference of. You don't
actually generate the prime factor that will drop out at all.

THL.

Re:Interesting?

[gspira]

You're missing half of what makes a system computationally secure. If a cryto system is computationally secure, then:

a) the cost to break it should exceed the value of the information it protects

and importantly

b) the time to break it should exceed the useful lifespan of the information it protects

So, hopefully, as the information that has already been transmitted over an insecure network becomes more vulnerable, it *should* also become less valuable because, quite simply, it's becoming old and useless. Ultimately, almost all cryto can be broken given the right amount of time. This is a given, and should be taken into consideration from the start.

Re:Interesting?

[KDan]

As a physics grad, I tell you you shouldn't resent it. That's the point of physics :-) To apply all this boring mathematical stuff to the world, and figure out all sorts of cool stuff from it.

Daniel

Re:Interesting?

[t0ny]

the sqare of the prime inversion of water to sunlight ratio will give you the mean rate at which grass grows

Re:Interesting?

[aarondyck]

I certainly find mathematics interesting. As a high school student I calculated (by hand) trig values for various angles just to keep myself amused in a grade twelve math class. Of course, it only took a few days, and after that I had to come up with something new to figure out...but that's the life of intelligent nerds. If only there was some way to combine the wasted time of all nerds into one super-project...maybe we could figure out the exact odds of Bush or Blair getting another term in office!

Re:Interesting?

[trotski]

What? Think of the hundreds of thousands of practical applications.... like, um.... well....maybe, no wait... no....

Look thats not the point, the point is that this will change you're life. Trust me, it just will.

Re:Interesting?

[donkiemaster]

Like he said, Zzzzzzzzzzzzzzzzzzzzzzzzz.

Are there secondary numbers?

[eenglish_ca]

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

Patterns in primes?

[TobiasSodergren]

Here I thought the patterns-in-primes thing was already solved by Jodie Foster and Matthew McConaughey..

Re:Patterns in primes?

[loucura!]

That was a pattern in Pi, not a pattern in primes.

Damn, Gnu hippies, always shoving RMS, and ESR into everything.

Re:Patterns in primes?

[Anonymous Coward]

You'd probably be correct if you were referring to this movie instead of this one.

Re:Patterns in primes?

[loucura!]

No, I'm refering to Contact the book, not Contact the movie.

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

Re:Good work

[ChaoticChaos]

While the importance of what you're saying can't be overstated, I guarantee you there is no application of this finding that will impact John Carmack's work on the next Doom engine. ;-)

Re:Good work

[Anonymous Coward]

Even if that had shown that there are an infinite number of twin primes, that would still have absolutely no application to factoring.
At all.

Re:Good work

[metlin]

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.

Re:Good work

[Yokaze]

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?

[cyb97]

Funny, I can't see their server getting slashdotted anytime soon...

The first

[Timesprout]

sentient robot will probably die laughing when it reads this research

Practical benefits?

[10Ghz]

Are there any?

Re:Practical benefits?

[suwain_2]

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.

Re:Practical benefits?

[cayfer]

I am sure that someone has asked the same question when Mr. Bool first established the Boolean Arithmetic looong time ago. It is certain that your kids or grandkids will benefit from this. Just be patient...

Re:Practical benefits?

[Kid Brother of St. A]

Hmm... 7 and 11 are both prime... maybe you're on to something here.

Re:Practical benefits?

[10Ghz]

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?

[Smidge204]

Patterns! Maybe they should get Maximillian Cohen involved!

=Smidge=

Appreciate the beauty of mathematics, for petesake

[neuro.slug]

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.

This just in...

[yellowstone]

2^3-1 is prime! Now checking 2^3+1...

Moo

[Chacham]

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.

other patterns in prime numbers

[TerraFrost]

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

here

Re:other patterns in prime numbers

[zeugma-amp]

I'd be interested in knowing if anyone has attempted to plot this as a fractal?

BTW: there is a linux version of Fractint 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 :-)

Interesting?

[rugwuk]

This is more interesting than watching paint dry actually! I am waiting for the the paint to dry in my kitchen and i'm reading this instead :-)

Before somebody asks the question...

[arvindn]

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

[AndroidCat]

If they discover interesting patterns in prime numbers, this could affect the t-shirt industry. Remember what happened when fractals became popular! :^P

Re:Before somebody asks the question...

[coyote-san]

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

Re:Before somebody asks the question...

[apankrat]

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

Re:Before somebody asks the question...

[kasperd]

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

[Pseudonym]

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.

Re:Before somebody asks the question...

[Effugas]

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

Re:Before somebody asks the question...

[coyote-san]

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

To me, it's a lot like the time "wasted" putting on and taking off my seat belt when I get in my car. I, and everyone I know, has taken thousands of trips without nneding them. But all it takes is one hit to make the effort worthwhile.

Re:Before somebody asks the question...

[coyote-san]

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 from basic algebra that your two factors are r +/- n, where 'r' is the root of the perfect square and 'n' is the small integer.

Two examples:

35 + 1 = 36 = 6^2, factors 6-1,6+1.

77 + 4 = 81 = 9^2, factors = 9-2, 9+2.

Re:Before somebody asks the question...

[Effugas]

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 this for a couple twin primes -- it seems to always work. I've had a nagging suspicion that sums of square roots will eventually do something interesting for factorization, but I highly doubt the above process is at all novel.

--Dan

Re:Before somebody asks the question...

[coyote-san]

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. 18410841 +/- 1642 gives you the two primes.

These numbers are still small enough that you can simply do trial division with small primes, but try it with 11489663619628510761447969341629.

(3389690632633463 and 3389590633733483, in case I mistyped a digit or three.)

Re:Before somebody asks the question...

[kasperd]

nobody should ever turn to the heavy factoring algorithms without first exhausting all of the trivial checks.

That depends on wether it is worth the effort. If you know the generating algorithm and it does not have any flaws, it is not worth the effort. But of course since your chance of finding the factorization is so small already, the chance of the factorization being generated by an idiot insisting on using an unsafe approach might very well be larger. (Without proof I will claim that the fraction of idiots in this world is larger than one in a billion.)

Re:Before somebody asks the question...

[Effugas]

The sqrt optimization only works for twin primes, coyote-san. I'm actually starting to worry this method is mildly novel.

It ends up truncating after the decimal point. So:

===
scale=20
sqrt(c)
18409199.999999972839667 12296
===

This is, interestingly enough, essentially numerical error -- the actual square root appears to approach but never quite reach p. sqrt((p-1)(p+1)) is the kind of operation that math professors tend to kindly point out has undefined output, since addition and multiplication don't generally play nice together, but this is a curious exception -- there's a very small range within which the resulting value can lie:

==
sqrt(5*7)
5.91607978309961604256
sqrt(7*9)
7.93725393319377177150
sqrt(18409199*18409201)
18409199.99999997283966712296
==

Neat :-)

--Dan

Re:Before somebody asks the question...

[coyote-san]

Even if you know it's an RSA modulus, you don't know how competently the prime factors were chosen. The odds that two 512-bit primes are close enough for this technique to work are vanishingly small, but it doesn't take long to eliminate the possibility.

BTW, the last time I looked at the code for one of the more sophisticated approaches (rho-something, it's been a long time and this isn't my main focus) the software performed a number of these checks before dropping into the main routine.

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

[coreyb]

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 to the same thing.

Re:Question of the Day

[BabyDave]

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

Re:Question of the Day

[pfafrich]

Is -1 prime? If so -3 = -1 * 3.

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:Question of the Day

[shfted!]

No. Nor is 1 prime (as it's only divisible by one number, not exactly two numbers which is required for primality).

Re:Question of the Day

[b0rken]

It turns out that this definition of a "prime number" is the same as the usual one for integers.

You mean "is equivalent to the usual one for positive integers", leaving the other poster's concern about 0 and 1 out of the picture. But "is equal to 2" is equivalent to the regular definition of primes for even natural numbers, so why isn't it a fallacy to claim that this shows for all integers that only integers equal to 2 are prime?

Anyway, the proof that x|a <=> -x|a seems to be fairly simple. x|a <-> a = kx (k integer). Let k' = -k. (-k'=k). Then a = -k'x -> -a = k'x -> -x|a.

Re:Question of the Day

[crashnbur]

Excellent! A response like this was what I was hoping for when I raised the question. Good job. :-)

Re:Question of the Day

[H*(BZ_2)-Module]

This isn't exactly correct... hence, the replies.
Definition: Let R be a ring. Let p be a nonzero, nonunit element of R. Then p is said to be prime if whenever p divides a product of elements of R, p divides one of the factors.
Notes: The definition is specialized to that of "prime number" which is considered to be a prime >1 in the integers.
Q: Is -3 a prime number?
A: no. It is however a prime element of the integers.
Q: Is 0 a prime?
A: No 0 is not non-zero.
Q: Is 1 or -1 a prime integer?
A No, 1 and -1 are both units in the integers.
Q: Eric Weisstein says that a prime has to be an integer > 1.
A: EWW gives this as a definition of a "prime number". There is another entry for "prime element" which coincides with the definition given above. The astute reader will notice that these entries contradict one another. The lesson is of course that mathworld contains errors, and probably should not be relied upon for accurate mathematical information.
Q: Are there other ways to define a prime element?
A: yes. Look in Lang or Hungerford.

My 2 is bigger than your 2.

[ChaosMagic]

...have smashed all previous records on the size of small gaps between prime numbers

The size of small gaps? For a start they couldn't really "smash" the size of small gaps because then by definition they would no longer be small ones. But secondly how exactly can you smash all previous records on the size of the small gaps between the prime numbers when it is set to (and the whole theory based around) the gap being "2".

I'm not an expert by any means, but surely if what the story means is they have found more of these pairs (1000928397 and 1000928399 or something -- and no, I just made them up)... then, so what? Sure it's an achievement of sorts, but it doesn't really help? To really help then a proof that this does or doesn't go on to infinity is what is needed.

Re:My 2 is bigger than your 2.

[Sique]

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.

No Step At All

[John Hasler]

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

Re:No Step At All

[John Hasler]

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.

Re:No Step At All

[russellh]

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

[DeadSea]

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.

Re:Twin primes

[burns210]

Would it be safe to say that there an infinite amount of [pattern1]s in a even more infinite amount of all real numbers? There are an infinite amount of odds, evens, there are an infinite amount of primes in a large enough set of numbers. Why would twin primes be any different, in a large enough set of numbers(gazillions :)), ofcourse there are gonna be a lot of them!

Re:Twin primes

[stuffman64]

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 happens somewhere above the values I tested to (like all 6k+1 disappear), it only seems logical twin primes are endless.

Of course, as you notice, this is NOT a mathematical proof, but something I did to try to convince myself that there are in fact endless twin primes. Also, what seems right in my head most likely makes no sense to others. If you don't agree, tell me why my reasoning is flawed so I don't make the same mistake again.

Re:Twin primes

[nivedita]

Actually, it's known that if you take the number of primes in the sequence a*k+d (k varying) that are smaller than n, it's asymptotically the same for any difference d that is relatively prime to a (this condition is necessary for there to be more than a finite number of such primes).

Re:Twin primes

[Rares Marian]

I tend to look at primes like this:

The sieve is irregular because there are few cases (though regularly) where a previously sifted number comes up to the chopping block. The leftover set looks like the result of subtracting incresing frequencies out of a waveform.

Now take into account that we are talking about factors.

This in ways only the Lord knows suggests looking at the pattern of gaps thusly:

General
1. Read the pattern of gaps beginning with every square integer.

2. Read the pattern of gaps beginning with every odd square.

Variation: Dependent on n^2
1. Read n^2 + 2, n^2 + 4, skip 2n.

I imagine you might find:
1. Repeating patterns
2. Repeating patterns increasing in length.
3. Rotated patterns
4. Patterns that repeat from a simple offset away from n^2

Or all that but with regard to n^2, (n+1)^2, (n+k)^2

Because the sieve is remove multiples of x beginning with 2x, I think prime numbers are not random but only seem that way because each step is out of sync, kind of like scrambled cable signals.

Next step

[pdan]

Next step is to find prime numbers differing by 1.

Re:Next step

[Yokaze]

I'll start: 2 and 3. You'll have to find the next pair.

Re:Next step

[Paradise Pete]

31 and 41 yawn

Maybe if you weren't so sleepy you'd be able to play better.

Re:Next step

[jpkunst]

OK: 1 and 2. You're next.

Re:Next step

[Galvatron]

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.

Re:Next step

[jpkunst]

OK, I always thought 1 was prime ("divisible by 1 and itself"), I didn't know that "1" and "itself" should be different numbers.

Re:Next step

[Cuthalion]

I think the definition of primality has been kind of deliberately written to exclude 1, since if you do include one, you break a lot of the rest of number theory - for instance, every number has an infinite number of prime factors.

Re:Next step

[vorpal22]

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.

Re:Next step

[vorpal22]

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 prime number.

Explanation?

[Hobobo]

Can anyone explain what either of these things signifies or what their impact is...for non-mathematicians?

Re:Explanation?

[Nick_dm]

as it's been said already, primes have a huge part to play in cryptography (RSA encryption and such), but this particular bit (moving towards proving that there are infinitely pairs of primes differing by 2) probably won't have a huge influence on encryption. Mainly its important though because its something that seems pretty plausible, so would be all the more satisifying to see it proved, applications are the boring bits really :)

Allright

[Anonymous Coward]

There is an infinite number of twin primes. Can we go blame Microsoft now?

Re:Moo moo?

[saskboy]

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

Proof of twin primes

[Joey7F]

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

[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:Proof of twin primes

[j3110]

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

Buffon's Needle

[Flamesplash]

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

Re:Moo moo?

[Chacham]

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.

Re:Another Breaktrhough in Barometric Building Hei

[Dylan Zimmerman]

Drop it and time it's fall. Be sure to account for the speed of sound or light depending on how you detect it breaking.

You can also go to the owner of the building and say, "I'll give you this barometer if you tell me how tall your building is."

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

The Cube

[Viking of the north]

Will ths in any way help me get out of The Cube?

Re:Another Breaktrhough in Barometric Building Hei

[WegianWarrior]

"I'll give you this barometer if you tell me how tall your building is."
Someone has been reading Strata...

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:Prime Number Advances

[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 number theorists have been working on since the early 1900's. It seems to be a much deeper theoretical technique.

Link to the paper??

[watzinaneihm]

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

[llywrch]

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

Re:You Smartasses Missed the Error

[La Temperanza]

I think they mean the field of prime number theory, not mathematics in general.

Re:You Smartasses Missed the Error

[mav[LAG]]

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.

Re:You Smartasses Missed the Error

[Chymaera]

It's a^n + b^n != c^n for non-zero interger values of x, y, and z where n>2, not a^n * b^n, silly.

Re:You Smartasses Missed the Error

[Elwood P Dowd]

Everything is soluble, given enough water.

Re:You Smartasses Missed the Error

[stud9920]

If that's what you wonder about, you probably never had

Re:You Smartasses Missed the Error

[YU Nicks NE Way]

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.

Re:You Smartasses Missed the Error

[Thunderbear]

Mathematicians consider this to be a different field than the one dealing with the Fermat theorem (which primary was interesting because nobody could say whether Fermat was right or wrong - not because the actual theorem as such was particularily interesting)

Re:You Smartasses Missed the Error

[Phrogz]

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 making a logical conclusion.")

Anyone know how an unpublished layman could get something like this seriously examined and/or published?

Re:You Smartasses Missed the Error

[Skwinx]

The best option, I think, is to submit it to the sci.math newsgroup. While the AMS would send a polite rejection notice and your local math dept. would at best inform you of where the first error occurs, the denizens of the newsgroup spend their time voluntarily reading through this sort of stuff and are quite able (and often willing) to explain, sometimes at length, what has gone wrong.

Alternatively but unlikely to be as helpful is the AMS (www.ams.org) (or your nation's mathematical society); they publish at least one journal and likely get all sorts of unsolicited mail for review.

Of course, even if the result is true and the reasoning essentially correct the proof may be so illegible that the referee cannot accept it, but only recommend that it be accepted after revision. So the math department of your local university may be better: they also get mail of this type all the time and may even have someone designated to respond to some of it.

The last of the options which should not be recommended is web-publishing. It is unlikely anyone would even see unless one of the above courses is taken with direction to the site.

Re:You Smartasses Missed the Error

[Rocky]

Unless, of course, your wife's grandfather's name is James Harris...

Nitty gritty without karma whoring, poor site /.ed

[Anonymous Coward]

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

On a odd note the first 8 digits of my SSAN is...

[mrmeval]

Yea, linux is great, run factor on common numbers. If I remove the last digit from my SSAN, it's a prime number! Add the last digit and it's a fizzle. SO! All you perl, sed, gawk, gasp, list, C, C++ hax0rs get busy, I need something that takes a number and runs many permutations on it factoring each! Removing an the ending digits, one by one and factoring them. The beginning digits... Hey, we could have our on Bibble code! Stir in a laddling of The code of Hammurabi, KJV Gute, K, cOs, rederered into mumbers of course and we will answer all, I mean all of the questions.

Re:Appreciate the beauty of english; for Pete's sa

[neuro.slug]

The topic character limit prevented that. or so it seemed.

Biology -- Mathematics

[netkgb]

If they were all tied together, would this mean that the structure of living creatures could be explained with mathematics? (in theory of course)

Re:Biology -- Mathematics

[LPetrazickis]

Yes. There is no "if" about it.

So i guess you'd call those...

[Anonymous Coward]

Partners in Prime ;)

Translation

[doru]

Large prime numbers tend to form Beowulf clusters.

Re:Appreciate the beauty of mathematics, for petes

[Some Dumbass...]

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

From the "I'm about to burn Karma Dept."-

[Soko]

Boring? (Score:3, Interesting)

Congrats. You have the first oxymoronic post title on Slashdot.

Having your score as the second prime was just icing on the cake.

Soko

Re:Appreciate the beauty of mathematics, for petes

[Goalie_Ca]

I think you meant to say that "Engineers are GOD!", that is to say that we are the closest thing since no god actually exists.

Re:Appreciate the beauty of mathematics, for petes

[Quixote]

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

Mis-statement

[Ancil]

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.

Re:Mis-statement

[Tharsis]

Really?
I pick 2 and 2.

Honestly...

[Chymaera]

Everyone's talking about the practical value or lack thereof of this discovery wrt crypto, but can't we just appreciate this for the beauty of its contribution to number theory? I'm no mathematician, but new disoveries in number theory rank higher on the interesting scale to me than the average /. article...How is this in any way 'boring'?

Re:a little birdie told me: we know this.

[Elwood P Dowd]

NEWSFLASH! There are infinitely many numbers in the universe! Current research held thaat numbers only went up to a few hundred trillion, but scientists have recently discovered that numbers continue FOREVER! ...

Wow. You just disproved my theory that everyone with a userid under 10,000 is worth reading.

Now you've screwed up all the primes

[Slur]

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!

The timing is impeccable

[calags]

It can't be a coincidence that his kids' ages are all twin primes. Can it?

Re:Buffoon's needle...

[canajin56]

Ummm, those piValue's are there because sin takes an argument in RADIANS. If Math.sin used degrees instead, that lines would be

deltaX = needleLength*Math.sin(360*Math.random()-180);

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

9999 end

in Fortran programs and assumed that meant that on September 9th, 1999, all the Fortran code would stop working!

Wrong

[stomv]

Prime numbers are defined to be both integers and positive.

At least, that's what Eric Weisstein thinks.
So do The Prime Pages

Gotta be positive, por favor.

He has 3 kids with their ages prime

[BStorm]

It is interesting to note that the ages of his three kids are all consective primes:

3, 5 and 7.

Re:Buffoon's needle...

[TheMidget]

If you can calculate a sine, you can calculate pi much faster than the buffoon. So, if you want to show off an algorithm calculating pi, better avoid usage of any trigonometric functions (or worse: their inverse), or else it will look like an exercise in triviality.

The only way Buffoon's algorithm makes sense is if you actually physically throw the needle. If you just simulate the throw, it becomes ridiculous, as the simulation itself needs knowledge of pi, or of one of its derivatives.

Ok, so they were two years and two days off, and Dubya hit the trifecta.

Perfect numbers

[xihr]

I just want to know whether there are any odd perfect numbers.

Re:Buffoon's needle...

[canajin56]

Good point. I think the simulation is just to show off that if you DID throw them physically, you would get a valid result, which is, in of itself, nifty. Random algorythms are no good anyways, because you only have a good chance that the result is even anywhere NEAR right, whereas a normal algorythm can gurantee a certain epsilon after howevermany iterations.

In highschool physics we did a lab which involved putting 50 pins in a peatry (sp?) dish, with part of the dish wall coloured in. We were to shake it, remove all of the pins pointing at the coloured part, and repeat. Then we calculated the half-life of the pins. Neat stuff. What I did for fun, because my group finished early, was to measure the circumference of the dish, and the arc length of the coloured area. I then assumed that the pins would be aranged in a perfectly random direction, and that a percentage would be pointing at the coloured part eqaul to the percentage of the arc length to the total circumference. My calculations were exactly the same as the observed results for the first 5 (of a total 6) itterations.

What is the point of that story? Well, I think it shows that the assumption that throwing/shaking pins around gives a random direction vector is a fairly good assumption. Either that or two bad assumption canceled. I hate it when that happens ;)

Re:Appreciate the beauty of mathematics, for petes

[Surt]

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.

By your definition both 0 and 1 are primes

[Cryogenes]

0 does not divide anything, so the implication
0|(a*b) => 0|a or 0|b
is vacuously true (even if you consider that 0|0 is true, the implication still holds since a*b=0 => a=0 or b=0).

Similarly, for p = 1:

1|(a*b)
=> a*b != 0
=> a != 0 or b != 0
=> 1|a or 1|b

Re:By your definition both 0 and 1 are primes

[You're All Wrong]

Nope, because before the definition of a prime comes a definition of a ring, and the definition of a unit. Both of these were elided, but they take care of 0 (ring definition) and 1 (unit definition) before you even get to look at the definition for primes. However, the definition for prime should include a rider that it doesn't refer to zeros or units.

YAW.

Knowledge is NOT a bad thing

[CracktownHts]

I shouldn't be replying to a reply to a reply to a reply, especially since I don't know enough math to really understand the significance of this paper, but there's a whiff of "knowledge is dangerous" ideology in this thread and I can't keep my mouth shut on this one ;)

The same argument for the development of the atom bomb holds true for crypgology. If "super-smart but real-world-naive" researchers don't do the research and publish it, the NSA, DARPA or some similarly real-world-non-naive researcher is going to do the research, and the results will be classified.

Somebody will always be looking for a way to gain power over somebody else. This somebody can be "the good guys", "the bad guys", or whatever term you want to use.

Re:Appreciate the beauty of mathematics, for petes

[haystor]

And you understand mathematics well enough to judge that others do or don't understand mathematics?

Re:Appreciate the beauty of english; for Pete's sa

[Pharmboy]

Is it supposed to be "for Pete's sake" (i.e. for the sake of Pete who is stupid) or is "petesake" a real expression?

im pretty sure its "Pete's sake". There was a movie named that too. Barbara S. invests in pork bellies. Thats all I remember of it since I don't like her.

Oh, please!

[WheelDweller]

[Sarcasm] I want to start a process where I prove that all even numbers are, in fact 'even' or divisible by two. I'll need a worldwide network of computers to set about to prove this....all the way to the last number! [/Sarcasm] Balls. Scan for anomalous radio signals. Study the growth patterns of wheat over the last 100 years, use it to win the lottery. There's not much less useful that that old saw, factoring prime numbers, sorting prime numbers, using prime numbers in wallpaper patterns, or brushing one's teeth with prime numbers. See also 'Chaos theory': Measure some activity transacted with infinite precision, measure it in only 8-digit precision, and then look like an ape when you can't predict what's going to happen...."it's chaos".... C'mon, guys- start using that intellect and curiosity for real-world stuff.

Re:Appreciate the beauty of mathematics, for petes

[Scooter]

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

Oddly enough, you're wrong.

[still_sick]

The number 2 is prime, and is indeed even. Don't quit your day job.

ACK! Forget it...

[still_sick]

I only skimmed your post before replying, didn't notice the qualifier you had. Sorry!

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.

Another Breakthrough

[beaverbrother]

There are also no prime number triples besides the first one: 3,5,7

Is this proof correct?

[slothman32]

You take all the primes currently and multiply them together to get x. X+1 and x-1 are bot prime and therefore twinprimes. I know x+1 is prime but why wouldn't x-1 also not be prime?

Re:Is this proof correct?

[thesilverbail]

hold it there, why exactly is X+1 prime? See, just because you've multiplied all the primes you know, doesnt mean X is a factor of every prime there is.(In fact there's no such thing as 'every prime there is'). X+1 could conceivably be a factor of a prime greater than the ones you multiplied to get X. see?

Re:Is this proof correct?

[slothman32]

I meant to say all the primes up to some number. Then x+1 will not be divisible by any of them. Nor should x-1. I.e. 2*3*5*7*11+1=2311 I know (this is why there are infinite primes) that 2311 would therefore be prime and it is. Why wouldn't 2309, or any number in it's place, be prime? Plus if x+1 is a factor then it could still be prime.

Re:Is this proof correct?

[thesilverbail]

X+1 wouldnt be divisble by any the primes you used, but it could be divisible by some other prime greater than the highest prime you used but still lesser than X. In fact i think one of the other replies had a counter-example.
Did I say factor? I meant multiple.

Re:Is this proof correct?

[thesilverbail]

Now I see why you're confused. You're thinking of the infinite prime number proof. See there we assume that there are a finite number of primes and we multiply all of them to get X. Now that there are no more primes, there cant be a factor for X+1. This leads to a contradiction and blah blah blah.... Now we know there's always another prime. So X+1 might possibly have a factor. QED

Re:Appreciate the beauty of mathematics, for petes

[xombo]

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 programmers like to think they are engineers as seen today on /.

Re:WHAT?

[An Onerous Coward]

And erm, proving that there's an infinite number of them? How will you know when you're done?

I know you're just trolling, with your "wake me up when I can buy one at Comp-U-Hut" attitude. Honestly, you can go back to Mothers Against Boomerangs for all I care. But regardless of the sincerity of the question, you've posed a fun one.

The key words here are "mathematical proofs." To look at a much simpler example, how do we know that there are an infinite number of prime numbers? The proof was actually discovered by (dead Greek dude) Euclid himself.

First, assume that there are only a finite number of prime numbers, and that you have a complete list of them. To disprove your original assumption and prove that another prime number exists, multiply all the numbers on the list together into one gargantuan number. This number is divisible by every number on the original list.

Now, add 1 to that number. Suddenly, the new number cannot be divided by any number on the list but 1. So the new number is either prime itself, or a composite number made up of at least two primes not on the original list.

Step 5 : Add new prime(s) to list, and start from step 1.
Step 6 : ???
Step 7 : Profit!

If the "twin primes" conjecture is ever proven, it will be done through a proof, not by checking every number between zero and infinity.

Unfortunately, I'm just getting started on discrete mathematics, so I can't point to any non-encrypting applications for prime number theory. It may be useful in helping prove the Reimann Hypothesis, which I've heard would be helpful in physics and telecommunications. But that exhausts the sum of my knowledge on the subject.

Why I like Slashdot...

[cr0sh]

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.

Even worse than that

[coyote-san]

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

Re:Even worse than that

[kasperd]

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.

Re:Even worse than that

[coyote-san]

One minor nit about the probabilistic primality tests: you also need to check whether the number is a "weak" prime - composite numbers which falsely pass those tests. Fortunately they're easily enumerated.

Re:Even worse than that

[kasperd]

"weak" prime - composite numbers which falsely pass those tests.

If you use Miller-Rabin it can be proven that for any composite number at least 75% of the possible values for the random choice will reveal that it is a composite number. The actual probability can depend on the composite number, but no composite number can give an error probability above one fourth. In other words if your n-bit prime candidate can pass the Miller-Rabin test n times, the error probability is negligible. Of course this means you need a large number of random bits. I wonder if there are ways you can safely do the test with a smaller amount of random bits.

um... what's wrong with this proof

[JM_the_Great]

If you multiply all primes up to any prime, and the add or subtract 1, both resulting numbers are prime. Since there are infinitely many primes, there must be an infinite number of twins.

For instance, (2*3)-1 = 5 and (2*3)+1 = 7.

(2*3*5)-1 = 29
(2*3*5)+1 = 31

(2*3*5*7)-1 = 209
(2*3*5*7)+1 = 211

Re:um... what's wrong with this proof

[eardrum]

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.

Applications to AI Development

[trotski]

This actually has incredable reprucussions on the world of computer AI. Many AI engines these days make great use of prime numbers, as well as twin prime members to develop decision trees. As an AI developer, my work would be impossible without the knowledge of twin prime numbers. Most software you have ran into these days with AI depends upon the use of twin prime numbers.

This is an incredable development to the AI community, as we now know for sure that we have an infinate number of twin prime numbers.

Re:Ummm what about the envirorment?

[jackal!]

There are also no prime number triples besides the first one: 3,5,7 Okay. Where's your proof?

Twin Prime Conjecture Proven (among others)

[bearnol]

http://www.bearnol.pwp.blueyonder.co.uk/Math/index .html

surprised

[MoFoQ]

I read it in the paper a while ago and was surprised to see anything of that magnitude come out of my school...especially from the building known to the students as the "Insane Asylum" (quite a few math instructors and professors have....well..."issues." Hell all of the calc professors had all unique "issues" [one, who was manic-depressive, was cool])

Oh well....I'm sure this will help future algorithms.

His timing obviously relates to his kids age :-)

[oren]

"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?

This article made bigger history

[rithvik]

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

Re:Ummm what about the envirorment?

[smaughster]

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)

Um - what about 1 and 2?

[Xavier000]

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.

So what about the gap between the two prime numbers 1 and 2? It would seem that there is not only one pair of primes with such a small gap.

Remind me not to get you to do my encryption.

Re:Um - what about 1 and 2?

[Sique]

Very easy. 1 is not a prime number. So the gap between 1 and 2 is irrelevant.

Slight variation on joke

[DoctorNathaniel]

Engineer: 3 is prime, 5 is prime, 7 is prime, 9 is prime, 11 is prime, 13 is prime, 15 is prime.....

Re:Appreciate the beauty of mathematics, for petes

[Surt]

Yes. I understand mathematics well enough to be confident that no one has but the tiniest fraction of a grasp on the whole. There are a tiny, tiny number of people (probably less than a million worldwide) who know math perhaps one thousand times better than I do at most, and even that doesn't begin to touch true understanding. It's a 'the more you know, the more you realize you don't know' situation. Seriously, ask any mathematics PHD if they feel like they are even aware (much less understand) half of what has been proven in mathematics.

Take the limit, coyote-san.

[Effugas]

As much as I'd love to have come up with something novel, this really isn't.

Take the limit as p approaches infinity of sqrt((p-1)(p+1)). It basically reduces to sqrt(p*p) = sqrt(p^2) = p.

So as p reaches infinity, the impact of those +- 1's goes to 0. The limit is p. p doesn't even need to be prime:

a=9845769847569845645692837498235
b=a+2
sqrt(a *b)
9845769847569845645692837498235.9999999999999 99999 99

You of course need all the other tricks for non-twin primes :-)

--Dan

Re:Take the limit, coyote-san.

[coyote-san]

Huh?

We're dealing with naturals (or integers), and "approximations" and "limits" just don't matter. Either a number is a perfect square, or it's not. There's no digits to the right of the decimal place, et.c

The final value will be close to the average of the two primes, but that's meaningless. Indeed, the square root of a composite number with two prime factors will always be (close to) the geometric mean of the factors, by definition.

Re:Take the limit, coyote-san.

[Effugas]

coyote,

Strange how meaningful that meaningless square root is.

The point isn't that it's just close; it's that the integer value to the left of the decimal point will _always_ equal the lesser of the two primes. Thus the relevance of the limit.

--Dan

Re:Appreciate the beauty of mathematics, for petes

[DonkeyJimmy]

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 likes to think he's a biologist.

or

Computer scientists like to think they killed god.

Re:Appreciate the beauty of mathematics, for petes

[omynous]

Mathematics, whether you like it or not, is really a beautiful and elegant subject that very few truly understand.

Worse, there are those who believe that if there is difference between the mathematical model and experimental data, the experiment is wrong.

Now, there are cases where an experiment is flawed, or, in the case of measuring things like the mass of the neutrino, the value is so small, experiments have grand difficulty getting any accuracy, but, overall, REALITY is real, not someones mathematics. Mathematics is a model, a contrived one at that. No real surprise that there are elegant things to be found.

I have this argument with a physicist friend of mine about once a year. He always presumes the math is right. He is usually proven wrong months later by yet another discovery.

Sigh.

Shannon Mann.