Frederic Green posted the following comment a while back:
Have you heard any buzz from your mathematical collegues
on the alleged
disproof of the Riemann Hypothesis.
Later comments indicated that the mathematician was not that good. When should you believe a math announcement? Which of the following would you believe? Would you bother downloading the paper?
-
Karp claims to have shown P = NP. P \ne NP.
-
Shelah claims to have shown P=NP. P\ne NP.
-
Widgerson claims to have shown P=BPP. P\ne BPP.
-
Bill Gates claims his group has shown P=NP and the binaries are available but not the source code.
-
The Free Software Foundation claims to have shown P=NP and of course the source code is available.
-
An undergraduate math major who is really sharp claims to have solved the the Collatz Conjecture) (also called the 3x+1 conjecture).
Whether to believe a claim is based on several variables.
-
G: How good is the person who claims to have solved it. Hard to measure. (number of STOC/FOCS papers :-) ) For someone new this might be even harder to access.
-
B: How believable is the result? We'd believe P\ne NP more than P=NP. But we may believe that if a proof was found now it would be that P=NP. I've heard that Riemann Hypothesis will probably be solved in the next 50 years.
-
H: How hard is the problem?
-
W: How good is the writeup? Is there one?
-
If the problem is outside of your area then you may have to take other people's word for some of G,B,H, or W. How good are the people telling you about the problem? This may lead to a recursive formula.
Green's Conjecture: There is a constant C such that
If G*B*W/H > C then the result is worth looking into.
If you claimed to prove Green's Conjecture then I could use Green's Conjecture to to see if your proof is worth downloading.
Now I want to know what the word is for the syndrome in which people define variables for all sorts of unquantifiable numbers and then put them together into meaningless formulae. "Scientism" maybe? It's pandemic in the soft sciences but I hope it doesn't spread here...
ReplyDeleteOk, I realize it's a joke, a mildly amusing joke at that, and that behind it is a serious point that we're more likely to pay attention when someone we think reliable does something. But I still want to know what the right word is.
I'd take any of them seriously, though it'd take some serious consensus before I'd believe them without reading the paper.
ReplyDeleteOnly for Widgerson proving P=BPP would I be seriously surprised to not find an error. On the other hand, only for the FSF would I be absolutely shocked if the writeup were correct modulo trivia.
As I see it, if someone comes up with a legitimately correct proof of P!=NP or whatever, someone will read it. If that someone finds it convincing, they'll point it out to someone else they know. Eventually that net.kook proof becomes the net.kook proof that [G=high] finds interesting.
A junior US student in my class claimed yesterday that he had a polynomial time algorithm for the TSP problem. He couldn't describe it mathematically nor had a proof, but claimed that he had a program which always works. He compared his P-program with a brute-force program and claimed that the P-program always finds the optimal solution. Unfortunately, when n is large, it takes too much time for the brute-force program to find the optimal solution (for him to compare).
ReplyDeleteAfter a few rounds of communication, I found a counterexample for his algorithm (which is a simply greedy method). But then he claimed that that was not really his idea and his P-program can find the optimal solution for my counterexample.
Only for Widgerson proving P=BPP would I be seriously surprised to not find an error.
ReplyDeleteFunny, I feel the exact opposite.
By the way, it's Wigderson.
Funny, I feel the exact opposite.
ReplyDeleteThe crucial thing is that this is really a question of (perceived) conditional probability, specifically comparing the likelihood of a correct proof with the likelihood of coming up with an incorrect proof that lasts long enough that it even gets posted.
If you happen to be correcting your own name, it only strengthens that position.
"Only for Widgerson proving P=BPP would I be seriously surprised to not find an error."
ReplyDeleteFor everybody else proving everything else you would be surprised to find an error? But especially for Wigderson only you'd not expect to stumble on no error?
David, you DO know who Avi Wigderson is, right?
ReplyDeleteOK I have a degree in CS but I am no longer doing research. I just created a game that is as hard as integer factorization an you can play it online:
ReplyDeletehttp://87zero.com/SCT/hanamarugame.html
Do you believe my claim or not :-)
... would you believe a paper by Bill Gasorch claiming to prove a n^{\Omega(1)} communication lower bound for the intersection function in the k-party NOF model?
ReplyDeleteYargh, too many negatives. You'd have to be some sort of idiot to think what I said (being the exact opposite of what I meant), thus my response to anon2. :-)
ReplyDeleteI would read papers by any of those guys, on any topic, period. There's a point not yet addressed, though, which is this: such a paper by a top mathematician would almost certainly not "claim to solve P/NP" as a major point of the title or abstract. The paper would be about a new methodology of approaching problems, prove some major theorems, and the nonrelativized separation of complexity classes would fall out of those theorems as a corollary. The papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc. This is because those authors are blinded by their hope for fame and cannot see the importance of method.
ReplyDeleteThe papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc.
ReplyDeleteI see; you mean that they're likely worth looking at so long as they aren't titled something like "PRIMES is in P" or "RL is in SC"...
What's an example of a similar problem that was settled recently? How did people react?
ReplyDeleteI'm vaguely surprised de Branges and his resolving the Bieberbach Conjecture haven't come up yet.
ReplyDeleteWhy don't those people publish their work in peer-reviewed journals?
ReplyDeleteWhat's an example of a similar problem that was settled recently? How did people react?
ReplyDeleteOne example of a problem which I can think of is the complexity of primality testing, which Agrawal, Kayal and Saxena showed to be in P. As yes, the paper was indeed titled "Primes is in P" - the first version of the paper, as well as the one published in Annals of Mathematics. And also I don't agree with the viewpoint that "The papers you have to watch out for (the ones that waste your time) have titles like "The Riemann Hypothesis," "P does not Equal NP," etc.", after all "Primes is in P" is indeed a perfect counterexample to this. It was not that the authors of the primality paper did not recognize the importance of their method. Their algorithm uses techniques like automorphism of finite fields, which are quite powerful and can possibly be used to derandomize other randomized algorithms as well. Probably the authors chose this name for the paper since it was a long standing open problem, and they did succeed in successfully solving the problem.
I see; you mean that they're likely worth looking at so long as they aren't titled something like "PRIMES is in P" or "RL is in SC"...
ReplyDeleteThese problems (especially the second one) are not in the same status as that of P vs. NP, and even BPP vs. P.
Dear Anon 12: Thank you for pointing out that exception, but you miss the trend if you focus on the counterexample. Can you match the following results to the following papers?
ReplyDelete1. Resolution of the Poincare Conjecture.
2. Unsolvability of Diophantine equations.
3. Incompleteness Theorem
a. The entropy formula for the Ricci flow and its geometric applications.
b. The connection between Hilbert’s Tenth Problem and systems of equations between words and lengths.
c. On Formally Undecidable Propositions in Principia Mathematica and Related Systems.
As you may know, the matching is 1a, 2b, 3c. My point is that (a) is not "I just won a million dollars," (b) is not "Hilbert was wrong again" and (c) is not "Hilbert's program is smashed."
FYI: Of note is that *Agrawal* has publicly stated on many occasions that he agrees with Anon 17, that PRIMES was already solved to everyone's contentment except his own and that of a few theoreticians, not a major result, etc. To my mind, this points to his high quality as a person. Still, I've skimmed hundreds of articles on the arxiv, and perhaps 90% of the ones that have "NP" in the title contain proofs I consider dubious or false.
I hope this helps.
I'm starting to see the reason for Lance leaving the blog. I might be wrong about this, but it might have to do with the bad vibes in the comments. Too much hostility...
ReplyDeleteMy point is that (a) is not "I just won a million dollars," (b) is not "Hilbert was wrong again" and (c) is not "Hilbert's program is smashed."
ReplyDeleteA title like "P \neq NP" is not in the same category as a title like "I just won a million dollars" or a title that puts down other people...
I apologize if I'm writing too vaguely to be properly understood. Consider the following examples also:
ReplyDelete1. Resolution of Fermat's Last Theorem.
2. Special Theory of Relativity
3. NPSPACE=co-NPSPACE
a. Modular Elliptic Curves and Fermat's Last Theorem
b. On the Electrodynamics of Moving Bodies
c. The Method of Forcing for Nondeterministic Automata.
There really is a pattern here.
Method-focused titles for big results are much more common than results-focused titles. Of course, both exist. In addition to "Primes in P" as an example, an alternative to (c) is the title of Immerman's paper, "Nondeterministic Space is Closed Under Complement."
The real contrast, though, comes when you examine, for instance, the papers on Stas Busygin's excellent P/NP page. 100% of those papers claiming to resolve P/NP feature the problem statement prominently in their titles, with the methods attempted receiving little or no mention.
I don't wish to be "hostile," but I am trying to convey something useful that took me many hours to learn: in the limited time you have to read papers by writers who are unknown (at least to you), it is my experience that the proof is more likely to go through if the author(s) is very clear about the proof techniques used, up front, and explains how these techniques can be used to solve other problems.
18: Only your first example demonstrates the "trend" you've noticed. The other two titles state the problem that has been solved (or proved to be unsolvable); they don't refer to the technique used. They are analogous to naming your paper "P \ne NP" or "P = BPP". And in your next three examples, I see you conveniently chose Szelepcsnyi's paper to help make your point, since Immerman's contemporaneous "Nondeterministic Space is Closed Under Complementation" states the problem and its solution.
ReplyDeleteFunny thing is, I actually thought you were right before you started posting examples!
While I appreciate the feedback, I think this discussion is too focused on why I'm wrong, vs. seriously dealing with Bill G and Fred G's question. In that spirit:
ReplyDelete#1: this is the last comment I will post in this thread, as this will be my fourth.
#2: Anon 19, please consider re-reading my last comment, as what you wrote seems to indicate you did not notice that I included the title of Immerman's paper. Perhaps you skimmed and misunderstood my point.
#3: The real issue at hand here is "When should we believe an open problem is closed?"
If Karp, Immerman, Shelah, Wigderson, Agrawal, wrote a paper titled "P!=NP" then hell, yeah, I'm going to read it. But they have a long track record of deep theorems. However, if you run acorss a paper with the same title written by someone you've never heard of, then what are you going to do? Read it? Read all of them?
If you don't like my research criteria, OK, what are yours, and why are they better?
I go out of my way to read "unknown"/non-STOC-FOCS authors. I need a way to prioritize my time. It is true I came off strong in my earlier comments. That is because people who keep posting and reposting the same false proofs are doing all the rest of us a disservice. If a significant percentage of arxiv papers are lousy (and they are) it makes those of us who are busy more likely to read "safe" papers.
That in turn leads to what is called "mafioso" behavior. Read S. Arora's responses to accusations of a STOC/FOCS mafia. He basically said, "No, man, we're just busy!"
If an unknown author demonstrates, in title and abstract, that by reading the paper I will learn a new method or application, I am much more likely to read that paper. You don't have to agree with me, but if you want to comment on what I've said, please talk about a better way to read "non-big-name" papers.
(APOLOGIES- NOT ON TOPIC, BUT
ReplyDeleteIMPORTANT WARNING- this blog
is set up so that if someone
links to it, it automatically
links back. Usually thats great,
BUT the link to Bill Gates
blog at bottom of the comments
is probably a phishing site-
DO NOT go to it. I'm looking into
how to remove it. DO not respond
to this, please resume your
on-topic comments.
Bill Gasarch
Ah, so THIS is how you get your name attached to a conjecture! By having little or nothing to do with it! Say, Bill -- "naming theorems and conjectures after people" -- subject for another post?
ReplyDelete(Of course, you may have meant another Green, in which case who? I mean, how many of us are there? :-)
Now, roughly speaking, this was the motivation of my original question: How many (good) people, if any, were paying attention to the claimed result?
So, following Bill's theme, given a paper purporting to prove a major theorem, how much attention A_N will you (the Nth reader of the paper) pay to it? Surely A_N is proportional to B and inversely proportional to H, but it's also proportional to the total attention that others have already payed to it, and how good (G_i) and articulate (W_i) those individuals were. This gives a possible recurrence relation (pardon the tex):
A_1 = G_1*B_1*W_1/H
A_N = (B/H)*(1/(N-1))\sum_{i=1}^{N-1} G_i*W_i*A_{i-1}.
And if A_N > C, you should read the paper. Of course I introduced this for one and only one reason: To name it Gasarch's Conjecture.
Here is another title that, like "Primes is in P", needs only four words to claim a major mathematical result:
ReplyDeleteN. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four colour theorem, J. Combin. Theory Ser. B. 70 (1997), 2-44.
So today's puzzler is, what is the shortest mathematical title that claims a major result? Is there one in three words or fewer?
As a followup to the above, it seems that Appel and Haken used six words to describe their original (computer assisted) proof of the Four-Color Theorem.
ReplyDeleteK. Appel and W. Haken, Every planar map is four colorable, Contemporary Math. 98 (1989).
I still know of no three-word (or shorter) title claiming a major result ... but I am pretty confident that such titles are out there!
T. Hales. The Kepler Conjecture.
ReplyDeleteOK, this is not entirely fair since it was preceded by a sequence of papers, but they had short titles like "Sphere Packing III".
The best I can find on the Riemann paper via Googling are some mid-April comments by Bernhard Kroetz at the bottom of this March 24 Ars Mathematica item. He writes "Lemma 1 is correct" then "All Lemmas are correct." Terence Tao seems not to have a mention of it on his homepage or blog. Can someone take this further?
ReplyDeleteA comment relevant to both the matter at hand and to blog dynamics: Penelope Smith had titled her Navier-Stokes claim paper "Immortal Smooth Solution of the Three Space Dimensional Navier-Stokes System" (and another paper similarly noun, not process). She has a link to C. Sormani at CUNY, who in turn links to this article on how Peter Woit's "Not Even Wrong" blog focused the review and eventual deconstruction of the paper. I'd be curious to know of cases where blog discussion did paper construction as well. Overall I don't think the comments in this thread are hostile, and the long "anonymous" poster has some data and interesting things to say.
Anyone reading the Computational Complexity postings on the ArXiv can get at least a monthly chance at triage of this sort...
ReplyDeleteOne doesn't need to rely on author names. There is a simple test to see if one should read on in a paper claiming some answer to a question like P vs NP:
The minimal standard is that the authors explain why their approach avoids the known pitfalls in the literature to answering the question such as: having an argument that relativizes, or using a natural proof argument. Any paper by reputable authors would discuss these issues.
am I the only one who noticed that the variables that Bill chose happened to be the initials of Bush Senior?
ReplyDeleteFYI: The hotel reservation deadline for FCRC (includes STOC, Complexity) is today.
ReplyDeleteThe Pati paper is incorrect, due to a circular choice of parameter definitions. On page 10 equations (10), (11), t is defined in terms of delta, and delta defined in terms of A_*, where A_* is to be defined "in the sequel". On page 13 equation (20), A_* is defined in terms of t. One cannot make all of these definitions simultaneously.
ReplyDelete