Guessing the Truth
How well are we at guessing the truth of open conjectures?
Warren Hirsch was a mathematician who started his career in the US Army, and much later retired as a professor emeritus of NYU’s Courant Institute of Mathematical Sciences. He is well known for many important results in diverse fields, from combinatorial algorithms, to mathematical models of epidemiology, to his famous geometric conjecture. The latter became widely known as the Hirsch conjecture.
Today I want to discuss how well we are at guessing the truth of mathematical conjectures. Hirsch’s famous one was recently disproved by the discovery of a counter-example. For a summary of the state-of-the-art until the recent result look at An update on the Hirsch conjecture by Edward Kim and Francisco Santos.
I often have conversations with colleagues on how well mathematicians do at guessing the truth of an open problem. My colleagues often claimed that they are pretty good guessers. I think that is not quite true; they certainly do not guess perfectly. One of my main beliefs is P=NP is could be possible, so is every one else a better guesser than myself? I guess so.
In one of Tom Cruise’s movies, A Few Good Men, in the climactic courtroom scene, he yells
“I want the truth!” to his opponent, Jack Nicholson, who answers, “You can’t handle the truth!”
I am interested in how well we can guess the truth—I am sure we can handle it.
Guesses and the Truth
The Guess: The great David Hilbert thought in 1900 that resolving whether the numbers
are transcendental would take a very long time. He thought such questions might be harder than the Riemann Hypothesis. This is his seventh problem, from his famous list of problems.
The Truth: All these numbers and more were proved to be transcendental in 1934; the proofs were found found independently by Aleksandr Gelfond and Theodor Schneider. The methods they used were clever, but were based on already known technology used by Charles Hermite in 1873 to prove is transcendental.
The Guess: David Hilbert also believed there might be a proof that arithmetic is consistent. He proved partial results, and it seemed that the problem might be resolved in the near future. This is his second problem, again from his famous list.
The Truth: Gödel’s results, especially his Second Incompleteness Theorem showed that this was impossible. Consistency is unprovable in arithmetic unless it is actually inconsistent.
The Guess: Warren Hirsch in a letter, dated 1957, to George Dantzig, the inventor of the simplex method for linear programming, first stated his conjecture. Hirsch conjectured a very sharp bound on the diameter of the edge-vertex graph of an -facet polytope in -dimension space. The bound was conjectured to be . For a very long time this was believed to be true, and most work was on getting better upper bounds. The best known to date is the beautiful quasi-polynomial bound due to Gil Kalai and Daniel Kleitman.
The Truth: In May 2010, Francisco Santos, from the University of Cantabria announced he had found a counter-example to the conjecture. Roger Brocket, a famous control theorist at Harvard, once told me:
It is hard to argue with a counter-example.
Santos’s result is big news, and hopefully will lead to further insights into the structure of polytopes.
The Guess: Subhash Khot conjectured that his Unique Games problem is NP-hard. A huge body of lower bounds have been built up on this beautiful conjecture. I have discussed it recently here.
The Truth: Sanjeev Arora, Boaz Barak, and David Steurer have proved that the conjecture is unlikely to be true. They have proved that all Unique Games can be solved in time
where . This shows that the Khot’s problem is not nearly as computationally hard as many have thought. Of course it does not rule out that Khot is right.
The Guess: Euclid stated his famous Fifth Postulate circa 300 BC. For almost two thousand years mathematicians, professional and amateur, searched for a proof of Euclid’s Fifth Postulate. They all believed it should be provable from his other axioms.
The Truth: For two millennia they searched for a proof that did not and could not exist. I just read a book on this problem and its history, by Jason Bardi. It is a quite fun read, and I would recommend it to you. One of the lessons of the search was that for a very long time none seriously thought that the postulate could be unprovable, and none believed looking at geometry without the fifth made sense. Even the great Carl Gauss was reluctant to announce results he had found on non-Euclidean geometry.
The Guess: The famous George Pólya conjectured that most numbers have an odd number of prime factors. He made this conjecture in 1919, and it is based on a very reasonable model of numbers.
The Truth: In 1958 Brian Haselgrove showed it was false below some of size around .
The Guess: Euler conjectured in 1769 that there were no positive solutions to the equations
when . This is essentially a generalization of the famous Fermat’s Last Theorem—set and , for example.
The Truth: Leon Lander and Thomas Parkin in 1966 found a counterexample for :
Later in 1986, Noam Elkies found one for :
The Guess: Virginia Ragsdale conjectured an upper bound to the number of possible arrangements of real algebraic curves embedded in the projective plane. She made this conjecture in the early 1900′s. This was again related to one of Hilbert’s problems—the sixteenth.
The Truth: In 1979 Ilya Itenberg and Oleg Viro produced counter-examples.
The Guess: Erik Zeeman conjectured that one cannot untie a knot on a four-sphere. I am not a topologist, but it seems like a reasonable conjecture.
The Truth: After trying to prove this for almost ten years, one day he worked on the opposite direction, and solved it in hours.
The Guess: John von Neumann conjectured that a topological group is not amenable if and only if contains a subgroup that is a free group on two generators. While von Neumann’s name is connected with this conjecture, not all agree he believed it to be true. In any event many people did believe this conjecture was true.
The Truth: The conjecture was disproved in 1980 by Alexander Ol’shanskii.
The Guess: The conventional wisdom was that bounded width programs could not compute the majority function, and many other functions. The rationale was that how could a constant number of bits “encode” the number of ‘s in the input?
The Truth: David Barrington’s famous theorem proved that bounded width computations can simulate , and thus compute the majority function. It is one of the big surprises in complexity theory. While not the hardest proof, it is one of the most surprising results. The brilliance of David was, I believe, two-fold: first looking for an upper bound not a lower bound, and second restricting the bounded width computations to use only group elements. I definitely guessed wrong and worked hard on the lower bound. Oh well.
The Guess: Most believed that nondeterministic logspace () is not closed under complement. It seemed very hard to show that a vertex is not connected to another vertex . The obvious way to demonstrate this is to find a “cut” that separates from , but a cut could be huge. Thus the conventional wisdom was that logspace did not have the power to show there is no path from to .
The Truth: Neil Immerman and Róbert Szelepcsényi proved that is closed under complement. They did not find a cut. Instead they showed that how to count the number of vertices reachable from by an inductive argument. A very clever result.
The Guess: P is not equal to NP.
The Truth: Who knows?
How well do you think we are at guessing the truth of an open problem? See this for Bill Gasarch’s view of this issue.
I have one specific question concerning the new counter-example to the Hirsch conjecture. Is there any hope to build an amplifier for Santos’s bad polytope? I mean can one take his polytope and “tensor” it together and get one of arbitrary dimension that also violates the conjecture? This is not my area so I apologize ahead if the idea is too silly, but as you may know I find the idea of amplifiers very intriguing.