Sudden Progress on Prime Number Problem Has Mathematicians Buzzing
wired.com
wired.com
I was confused at the time, but it makes sense now.
- In math, an innovative "attack" (such as a technique to approach a problem) can result in years of subsequent research that progresses a field. Zhang deserves a lot of credit for his accomplishment!
- He shouldn't have had to work at subway. If only our society held intelligent people in the same regard as athletes. What we have right now (hoops to get tenure, publish or perish culture, etc.) is a joke. I review papers for some notable conferences in my subfield in CS. This week I read about a dozen papers. The ones that pained me the most were written by very smart people solving made up and artificial problems. But hey ... you need to publish this crap to graduate/get tenure/get next grant/whatever. How about a basic income for everybody with a PhD?
I am always amazed, how unsuccessful PhDs in life are. Myself included.
There are a lot of lazy and functionally useless PhDs out there.
2. He wasn't a cashier, he worked on the business side of a franchisee.
If intelligent people were treated like athletes, some would indeed benefit enormously. But it's not all roses. That "rat race" is still there. Intelligent people would be using their smarts to get money for education (just like now!) but the relationship would become much more exploitative, with the schools potentially making millions off of them without the student seeing any of that.
Afterwards, a small number of the most intelligent would have a shot at making millions, with most never making it, with most either having to find careers elsewhere, and the lucky ones leading unglorious lives in small towns making little money, always hoping to make it big but seeing that chance fade year after year.
Even those who are good enough to make millions have it thrust upon them with almost no preparation, as they get massive contracts based on their potential. Most of them, despite being intelligent, are not good with money and end up squandering their wealth.
And of course none of them are able to keep their positions for a very long time, since it's a young man's thing. They get ejected, used and abused and still fairly young, and if they haven't managed their money well then they are also broke.
Not that I'd at all mind being in Michael Jordan's position, but my point is that those are the exception rather than the rule, and despite the overall high regard for them, trying to be a professional athlete is not generally a particularly great proposition. Compared to academia, where you generally expect to reach a position where you'll have a good income until you die, or if you fail in academia you at least have useful skills that people will pay you for in the outside world, the world of sports seems downright cruel.
I suspect you're comparing top paid athletes with low-end PhDs. Which might not be a fair comparison - who gets paid more, Michael Jordan or the CEO of Genentech? It might be fairer to compare a low-end PhD with, some college high jump athlete. So keep that in mind when I use the labels "intelligent" and "athlete".
Why? Intelligence is an inward quality. What good does it do to have 100,000 smart people? Athletes, however, are valued for their outward quality - they entertain us with their skill. They provide marginal utility for a huge chunk of society; intelligence in and of itself, only provides a marginal utility for the self.
So, unless you're some sort of Ayn-Rand individualist, really the athlete does do more good (for the collective) than the intelligent, and therefore is compensated more.
Note this is from a qualitative standpoint. Athletes are somewhat absurdly highly compensated, but there are reasons for that, but it shouldn't be surprising that Athletes are more compensated than the intelligent.
Obligatory David Wong quote:
Let's say that the person you love the most has just been shot. He or she is lying in the street, bleeding and screaming. A guy rushes up and says, "Step aside." He looks over your loved one's bullet wound and pulls out a pocket knife -- he's going to operate right there in the street.
"OK, which one is the injured one?"
You ask, "Are you a doctor?"
The guy says, "No."
You say, "But you know what you're doing, right? You're an old Army medic, or ..."
At this point the guy becomes annoyed. He tells you that he is a nice guy, he is honest, he is always on time. He tells you that he is a great son to his mother and has a rich life full of fulfilling hobbies, and he boasts that he never uses foul language.
Confused, you say, "How does any of that fucking matter when my (wife/husband/best friend/parent) is lying here bleeding! I need somebody who knows how to operate on bullet wounds! Can you do that or not?!?"
Now the man becomes agitated -- why are you being shallow and selfish? Do you not care about any of his other good qualities? Didn't you just hear him say that he always remembers his girlfriend's birthday? In light of all of the good things he does, does it really matter if he knows how to perform surgery?
I hope this quote gets picked up and cited throughout future history
1. Write down the problem.
2. Think real hard.
3. Write down the solution.
Previous discussion here"Roughly speaking, a comb is admissible if there is no obvious reason why its teeth couldn’t point entirely to primes infinitely often as you move it along the number line"
Then: "A much more audacious conjecture called the prime k-tuple conjecture ... posits that any admissible comb will point entirely to primes infinitely often."
Isn't this just saying the prime-tuple conjecture states that admissible combs are admissible?
I suspect that "obvious reason" is being used as shorthand for some technical definition the article doesn't try to state. Any mathematician here that knows more?
Conversely, {n, n + 2, n + 6} is an admissible 3-tuple. There's no fixed integer that will always divide at least one of n, n + 2, and n + 6, so we believe that there are infinitely many n for which n, n + 2, and n + 6 are all prime.
One of the times it was specifically brought up in reference to a known mathematician. The takeaway being that getting in a relationship, or even married, automatically disqualifies you from achieving anything of great importance in the future....made me pretty sad that it's such a common pattern of thought.
But then, I started my family early. I didn't have much of an established pattern of productivity before. So my baseline comparison may be way off.
As Hume would point out, is is not ought.
[1] http://www.jrhenry.net/johnrhenry/erdos.htm [2] http://www.nndb.com/people/401/000032305/
If someone discovers a shortcut in factoring very large numbers, then it will have the attention of cryptographers.
Finding random primes is easy, especially if you don't mind using methods which allow an extremely tiny probability of error [1] -- this is standard practice in cryptography.
Finding random big primes p and q is easy. Multiplying them together into a product r = pq is easy. RSA cryptosystem picks p and q when generating the key, multiplies them, then throws away original p and q values. Only r is stored in the key.
Cracking the RSA algorithm itself [2] is basically equivalent to turning r back into p and q.
RSA is based on the hardness of factoring an integer into a product of primes. I don't think this conjecture will lead to practical improvements in cryptography / cryptanalysis, at least not with respect to cryptosystems that are currently widely used.
[1] http://en.wikipedia.org/wiki/Primality_testing#Probabilistic...
[2] Of course, there are many more attack vectors on specific implementations of the RSA algorithm, like trying to gain information on the secret key by measuring time taken to encrypt a message, measuring heat/power consumption/electronic noise, taking advantage of implementations that use a poor source of randomness, hacking into the system where the private key is stored, or bribing/threatening a human with legitimate access to the private key (as covered in http://xkcd.com/538/).
This has not been proven. RSA encrypts by taking C=m^e (MOD N). The normal way of decrypting is to take C^d (MOD N), where d can be efficiently computed if you know the factors of N. However, all you need to do to decrypt C is to take the e`th root (mod n). It has not been shown that the ability to do so allows you to factor N.
In fact, it appears (after a few minutes of research, so someone please correct me if I'm wrong), that their is evidence that breaking RSA is easier than factoring [1]
[1]http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf
For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big primes used in cryptography have fewer than 1000 bits, or about 300 digits. That is not what one (nowadays) calls 'large' in the field of finding the largest prime. There, one laughs at numbers of a million digits (the largest known prime has 17,425,170 digits)
You can generally repeat a probabilistic test with different parameters to make the probability of a "false positive" prime number very tiny -- like .000 000 000 001 -- while still staying within the computational budget manageable on an ordinary computer (obviously, a practical Internet security scheme should be able to complete its computations in a second or two on a typical desktop, laptop, server, and smartphone).
So probabilistic tests are good enough for practical purposes, but you need a non-probabilistic test to get the false positive probability all the way down to zero. And you need to use a method that has zero percent false positive chance to claim a world record. The EFF-administered monetary prize for a record-breaking prime number, for example, requires "the primality proof must be a deterministic proof..." [1] So you can't use probabilistic methods.
Or is o̅(log⁷·⁵(n)) just infeasible for those sizes of numbers?
The twin prime conjecture posits that the limit is 2, i.e you can never exhaust pairs of consecutive primes with the smallest possible separation size.
The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them.
It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing.
There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.
- Goldbach's weak conjecture (http://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture) - Harald Helfgott claims that he proved it
- Is factoring in P? (it is known that prime testing is in P; thus the factoring is in NP ∪ coNP) - if it were true, RSA would be broken immediately (and some expert that I talked to told me, he believes that such a factoring algorithm could probably be extended to break ECC, too)
- Riemann hypothesis (http://en.wikipedia.org/wiki/Riemann_hypothesis)
- Do for each even number n exist two prime numbers p > q such that n = p-q?
http://jointmathematicsmeetings.org/amsmtgs/2160_abstracts/1...
From http://jointmathematicsmeetings.org/meetings/national/jmm201...
http://michaelnielsen.org/polymath1/index.php?title=Bounded_...
Also, in mathematics, finding an example of a property isn't very difficult. The difficulty lies in proving a theorem that makes a universal statement about that property -- that's the real challenge.
If that answer wasn't clear, don't hesitate to ask a clearer question.
There are certainly prime gaps that exceed 600. In fact, the higher you up (in the number line), the higher these prime gaps tend to get.
http://en.wikipedia.org/wiki/Prime_gap
What's being said here is that despite of that, there will always be prime gaps smaller than 600. No matter how high you go, you can always find a pair of primes that are separated by less than 600. In other words, pick the biggest N you can ever dream of, and there will exist primes p1 and p2 such that they are both bigger than N and their difference is smaller than 600.
In light of that, I think the discussion and work revolves around discovering the smallest gap as the numbers themselves become larger and tend toward infinity. Obviously the very smallest prime gap is that between 2 and 3, i.e. 1, and there are a great number of primes separated by 2, and the Twin Prime Conjecture asserts that there will always be occasional pairs of primes separated by 2 no matter how large the numbers themselves become. The present work is in part meant to put that conjecture on a more analytical footing.
I would love to delete my original post.
Pick a number. Make it as large as you like. A billion to the power of a billion to the power of two billion? Just pick something.
Now whatever you pick, I can then proceed to find two prime numbers which are at most 600 apart. Maybe they're just slightly larger than the number you picked. Maybe they're vastly larger. But the point is, they exist.
We can repeat the procedure with you picking larger and larger numbers and I can always find a suitable pair that's bigger than what you pick.
(In theory. In practice, we may get to a point where it takes more time to locate the actual pair than we have time before the universe burns out or collapses. But we can prove that they exist, at least.)