Types of Papers
More to our fields than proofs
Imre Lakatos was a famous philosopher, who wrote a brilliant book called Proofs and Refutations.
Today I wish to talk about types of papers.
Lakatos’ book opposes the formalist view that a mathematical theorem is a one-shot entity whose meaning resides only in the symbols of its statement and proof. It presents mathematics as a transactional process, by which the concepts and statements themselves are selected according to human appreciation of growth and progress. The book itself is in dialogue formed around the famous formula
for planar graphs, due to Leonhard Euler. Lakatos is also known for focusing attention not on individual advances but on the idea of a research programme, advocating that the mathematical community’s collective first order of business should be to identify which programmes are `progressing’ and which are `degenerating.’
An Example? New Collatz Claim
Ken received e-mail today with an example of mathematics as a social process: a serious claimed proof of the Collatz conjecture by Gerhard Opfer, a professor in the Faculty of Mathematics, University of Hamburg, Germany. The Collatz conjecture states every natural number is reachable by a path from in the graph with edges from to and (if it exists and is odd) . Here is his paper, which was submitted on May 25 to the well-known journal Mathematics of Computation.
Some doubts and arguments over the proof in two discussion forums are linked from this June 1 announcement in the blog of John Cook. Cook includes an update noting the doubts and saying:
Perhaps the gap can be filled in, or perhaps an idea in the paper can be of use somewhere else.
The latter clause especially accords with Lakatos’ thinking. The Collatz conjecture itself, however, is a definite statement and not by itself part of a programme—so Lakatos’ ideas of how refutations shape changes in concepts seem not to apply. The statement is so simple that it can be represented by a Turing machine with binary alphabet and only seven-or-so states, the question being whether the machine halts for all inputs. We have not yet had time to give the new paper considered judgment.
Thus we return to the originally-drafted post, on types of papers and what they say about research programmes and the health of the field in general.
This is on my mind since I am currently working on the PC for this next year’s FOCS chaired by R.O. Sorry, I meant to say: Recall that I am currently working on the program committee (PC) for this year’s Foundations of Computer Science (FOCS) symposium chaired by Rafail Ostrovsky (R.O.).
As usual, the call for papers for FOCS had a long list of areas of papers that are relevant to the conference. Such a topic list is used by most conferences to control what kinds of papers are sent to the conference. A brilliant paper on a method to cure the common cold would probably not be accepted—or even be understood. So authors follow the topic list pretty closely.
Thus the call for the conference divides papers by topics, not by type. I have been wondering if we should also label papers with their type. You might ask, if you are still reading, what do I mean by type?
There are several types of papers, besides the obvious division into clear and unclear. This latter division I have always thought was more one of ownership: a paper is clear if I wrote it and unclear if someone else did. This has happened to me even within joint papers. My pass seemed crystal clear, but my co-authors’ next pass I could not follow. No, by type I mean something else. I mean a classification of papers based on what they do, not on what they do it to. For example, a paper that solves an open problem that is well known is one type. There are many others that I have been able to identify—see the next section for a list of some of them.
Examples of Types
Here is my preliminary list of types:
Open Problem: This is one of the most exciting types of papers. Even if the problem is not a Clay problem or on Steven Smale’s list, it is neat to be able to say: We solve the open problem of X and show that is a theorem. Such a paper is easy to pigeon-hole: if the open problem was well known, then the paper is easily seen to be important. Even if the open problem was only known to some, they will be excited—perhaps upset—but usually excited that the problem is solved.
Open Problem—Modified: This adds a restriction on the class of objects and proves a result. Prime examples are: make circuits monotone or non-commutative, make the algorithm have to handle only random inputs, and so on. This is very common, since many of our open problems seem to be extremely hard. Most of the results on lower bounds, for instance, are forced to use this method. There is nothing wrong with this type; one could argue that it is natural and reasonable when faced with impossible problems to try and attack modified or weaker versions of them. The long-term goal is to shed light on the real open problem, and perhaps yield insights that will allow us to eventually crack it.
Old Result—Enhanced: This takes a known result and improves the result on some dimension. If the previous result was an algorithm, then the new result may make it go faster, or use less or no randomness, or reduce its space usage. A canonical example is: The previous work of X showed how to solve on graphs in time , which we improve to . All types of results can be enhanced: bounds can be improved, restrictions can be removed, and so on.
Old Result—New Correct Proof: This type of result takes a published result and fixes the proof. According to Lakatos there are two ways a proof can fail to be correct. It can contain a local error—an error in a proof of a lemma or claim that is true—but the proof was deficient. Or the error could be a global error. This means that the lemma or claim was just plain wrong. The old result then needs major rework. This type of result is very important to the field, since leaving incorrect results around can damage future research. Also many times such results discover an assumption that seemed “obvious,” but was not. The discovery of this can be quite important and helpful in our understanding of what is happening.
No offense, but some areas of theory are more susceptible to this phenomenon; in particular cryptography seems to contain relatively more results of this type. I believe that some of this is due to the notions used in security being more subtle that those used in other areas.
Old Result—New Proof: This type of paper re-proves an old result by a new method. These papers can be the most important of all, since they enrich the field with new tools. These tools can then be used to solve, perhaps in the future, other results. Often the first proof of a result is clumsy and not clear; often it can be filled with technical details. Finding a new proof, especially a proof that is shorter and clearer, is potentially very valuable to the field. A canonical example is Irit Dinur’s new proof of the PCP Theorem, which even merited its own survey in the AMS Bulletin by Jaikumar Radhakrishnan and Madhu Sudan.
New Real Problem: These results try to model a practical problem and make it into a formal one. If this is the first result of the kind, the result may be relatively easy, but the problem can be quite important. Sometimes the model is interesting for its own sake—even if the model doe not exactly capture the real-world problem.
New Problem: This may or may not be driven by a practical problem, but may capture an important question. Even without a real-world justification, the problem can be very important. A good problem can help us discover new results that may not have been looked at before. I think this is hard to do, but when it does happen the payoff can be immense.
New Technique: Such papers can be extremely important. Sometimes the application that drove the authors to create the new technique is not as nearly as interesting as the technique. This happens frequently—I am not sure why—but it just does.
Computational Proof: This type uses actual computations to show that something is true. We get relatively few of these relatively, but we do see some of them in the theory area. One of the most famous is the original proof of the Four Color Theorem by Kenneth Appel and Wolfgang Haken. This gives us a chance to mention that there has been recent progress on improving the proof so that it is practically human-checkable, including this proof and better algorithm by Neil Robertson, Daniel Sanders, Paul Seymour, and Georgia Tech’s very own Robin Thomas.
We also acknowledge and thank commenters in this blog’s April 24 item on the 4CT who have continued noting the progress and discussion of other ideas that emanate from this theorem right up through this year. See comments at the bottom including some neat videos. We also note this January 2005 article by Keith Devlin saying the last doubts about 4CT were finally removed, almost thirty years after the original paper. Although there is nothing more formal than a computer proof, Imre Lakatos would have felt vindicated to see this process.
What are some other types of papers? Do you like this classification?
Is the Collatz proof correct? How can we help the social process of reviewing such claims?
[fixed Collatz statement with extra words "and is odd".]