Who Gets The Credit—Not Facebook Credits
How partial results have helped solve some famous open problems
Richard Hamilton is not a computer theorist, but is a senior mathematician at Columbia University. He is a leading expert in geometric analysis, and the creator of the program that helped solve the Poincaré Conjecture. He is a winner of numerous awards including: the Veblen Prize in Geometry, a Clay Research Award, and most recently the AMS Steele Prize for Seminal Contribution to Research.
Today I want to talk about a question that has been raised here and elsewhere: should researchers share their ideas? Especially ideas that are not “complete.”
Well every time you talk to a friend about a result, give a talk, post a paper, publish a paper, you are sharing your ideas. Most would argue that this is the key to advancing science in all areas. Yet there is the issue of when do you share the ideas. Do you wait until they are completely worked out—and what does that mean anyway? No matter what your result is it is likely not be the last word on your area. At least you should hope not. The last paper is a bit like: would the last person to leave please turn out the lights.
On the other end of “when” is this advice from Harvard’s great computing pioneer:
“Don’t worry about people stealing an idea. If it’s original, you will have to ram it down their throats.” Howard Aiken
Fermat’s Last Theorem
The proof of this great theorem, after being unsolved for almost 350 years, is due to Andrew Wiles—with some key help from Richard Taylor. But Wiles would have never been able to even start working on the proof without an insight of Gerhard Frey.
Frey gave a public lecture—are there private lectures?—where he pointed out some strange consequences of a non-trivial solution to
for an odd prime. Frey stated that such a solution would “likely” violate known conjectures. The “likely” was made in a precise statement by Jean-Pierre Serre, which was then proved by Ken Ribet. The missing piece had been called the “epsilon conjecture,” but it was not because it was a trivial or small step.
The key to me is the community needed to solve the problem. Yes Wiles worked alone for almost a decade on his solution. But without Frey and then Serre and Ribert, he probably would not even have started. Frey’s ideas were a perfect example of the type of partial results that can drive us all toward the solution of great problems.
I cannot even attempt here, or anywhere, an outline of Wiles proof. I think I can give an idea of how Frey’s idea can be used in a more modest way. The essential idea will start out like his idea: if there is a solution, then we will create a strange mathematical object. This object in our case will be a simple quadratic equation—the same kind you probably studied in high school. But the equation is “strange” in a way that will eventually lead to a contradiction.
Suppose that there is a non-trivial solution to the cubic case of FLT. Let
Then there are rational and so that
and is non-zero. The simple idea is to construct a mathematical object that is too strange, in some sense, and then prove that it cannot exist. The object will be just a quadratic equation: consider the polynomial
Define . Then it is easy to check that the quadratic equation
has solutions . Therefore must be a rational number too. In other words has rational point. gives that , which must also have a rational point.
Okay so what does this do for us? The point is that the equation
is an elliptic curve: a class of curves that are very well studied. There is a well known, to the experts, theory that allows one to prove that the only rational points are in and , which translates to . Thus this proves FLT in the cubic case.
The proof of the Poincaré Conjecture by Grigori Perelman was one of the great results of mathematics. He carried forward to a conclusion a program that had been started by Richard Hamilton in 1982. Hamilton had proved a number of beautiful partial results, but the full proof needed Perelman.
Hamilton’s brilliant idea was to replace a static problem by a dynamic one. The standard statement of the conjecture is: Every simply connected, closed 3-manifold is homeomorphic to the 3-sphere. The “obvious” approach is to take such a manifold and try to prove that it is a sphere. All earlier attempts failed.
What Hamilton did was he introduced a flow, the so called Ricci flow, that changes a manifold over time. The idea of his method was to then prove that this flow made the manifold move toward a sphere over time. He could not prove this in general—he knew the behavior was more complex. But Hamilton did prove some important special cases. See the following figure for an example of the flow in action:
Note, how the manifold changes over time, and becomes closer to a sphere.
Unique Games Conjecture
The recent paper of Sanjeev Arora, Boaz Barak, and David Steurer (ABS) shows that the famous Unique Game Conjecture (UG) of Subhash Khot may not be correct. I have discussed the exact conjecture in some detail already. The rough notion is that a UG instance is a type of graph edge-coloring problem that Subhash conjectured cannot even be approximately solved in polynomial time. The usual statement is: given a UG instance that has a solution which satisfies edges, even finding an edge coloring that satisfies fraction of the edges is difficult. The conjecture has been used to prove that many other interesting problems also have no good approximation.
The paper of ABS proves that there is a sub-exponential time algorithm for every UG instance. This does not rule out Subhash’s conjecture, but does raise some issues. One possibility is that the conjecture is wrong; another is that the conjecture is true, but the reductions that would establish it are more complex than usual. We will see in time what happens.
Just like FLT and Poincaré there were papers and ideas that helped guide ABS to their terrific result. Could Arora be the first to win a “hat-trick” in Gödel Prizes?
Since this area is still in progress I cannot say anything as definitive as I could for the other problems. However, is clear that ABS built their paper and proof on previous work of a number of researchers. In their paper they thank, among others, Alexandra Kolla for an early copy of her manuscript. She proves some results that seemed to have pointed the way for ABS. Kolla’s main theorem is roughly the following: For every satisfiable instance of Unique Games that satisfies certain technical assumptions, one can find an assignment that satisfies more than 90 percent of the constraints in time that depends on the spectral profile of the game. She also shows how spectral methods can solve in quasi-polynomial time game instances that where previously thought to be hard, and how to solve Unique Games on expander graphs.
Should researchers be encouraged to share ideas earlier than we do now? What mechanisms are needed to be sure that proper credit is given out? Would you publish a partial result?
I must say that one thing I have tried here is to state approaches, conjectures, and ideas about many problems. I hope that this is helpful for the field, but would like to know what you think.