Close Encounters of The Proof Kind
A strange experience proving a theorem
Steven Spielberg directed Close Encounters of the Third Kind. He is also famous for directing many other wonderful movies such as Jaws, E.T. the Extra-Terrestrial, the Indiana Jones series, Jurassic Park, Schindler’s List, and Saving Private Ryan. He has won two Oscars for Best Director to date.
Today I want to report a strange encounter that I just had. Very strange.
I recall one of the early scenes in Close Encounters that takes place in the Air Traffic Control Center in Indianapolis, Indiana. We only see the controllers and their radar screen, and only hear them talking to the pilots of two commercial flights: TWA 517 and Aireast 31. The main speakers are Harry the controller at the screen and the nameless pilots of the flights. At the end of the encounter, after an exciting near collision between the two flights and a brilliantly bright object, the team coordinator of the center tells Harry to ask, do they want to report officially?
Harry: Aireast 31 roger, report level Flight level three-one-zero. TWA 517, do you want to report a U.F.O.?
TWA 517: Negative. We don’t want to report.
Harry: Aireast 31, do you wish to report a U.F.O.?
Aireast 31: (after a beat also) I wouldn’t know what kind of report to file.
Clearly pilots get in trouble for reporting strange events, so I hope that theorists are not under the same rules. I hope that no one will think I am silly for reporting this close encounter.
My encounter was not that strange. I did not get beamed up into a U.F.O., nor did I have an out-of-body vision. I did have a very strange experience while trying to prove a theorem.
Last week I was writing up a proof of a theorem that I had been trying to prove for quite a while. The exact theorem does not affect this story, so I will leave out the full details. Also it is joint work and we are still polishing it, so I feel I need to be general. I hope that is okay.
In any event I was trying to show that a certain function could be approximated by a randomized algorithm . I was trying to prove that
and that runs in time polynomial in and . The proof was quite complex and involved a fair amount of geometric calculations: the algorithm was operating with vectors from a high-dimensional space.
After about six pages of detailed TeX I was pleased, since I seemed to have a correct proof. It is always hard to check your own work, but the proof seemed to be there. My next step was to send the TeX file to my co-authors and let them check the correctness. And fix all the typos and poor writing.
Then I noticed something strange. This was my strange encounter. I noticed that the running time of the algorithm did not appear to depend on the value of . This seemed impossible; the algorithm used many approximations that depended on and other ‘s. How could its running time be independent from the value of ? But after lots of checking I realized that the running time was indeed independent.
The reason this was so strange is that I could now allow to tend to . This would yield
But since the running time was independent of , there had to be an algorithm so that
This was strange to me. How could an approximation algorithm yield an exact algorithm? This was not a rigorous argument, but seemed to have only one consequence: there had to be an exact algorithm with polynomial running time in only .
So I threw away the TeX file—just put it aside in case I was wrong—and began to try to find the exact algorithm. After a short time I found the algorithm, which was extremely simple and depended on a surprising lemma. I looked at the lemma. It seemed hard to believe that it was true, but I tried some small cases and it worked. Then I sat down and quickly found a short proof that the lemma was true, and therefore the exact algorithm worked, and now I could really throw away the old TeX file.
The final point is there is no way that I would have guessed the key lemma. I only discovered it because of the approximation method that I was trying to prove. I wouldn’t have guessed it, but it was the type of result that once guessed was quite easy to prove. An interesting encounter—no?
Have any of your had a similar strange experience while working on a proof?