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.

The Encounter

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 ${F(x)}$ could be approximated by a randomized algorithm ${A(x,\epsilon)}$. I was trying to prove that

$\displaystyle F(x) = A(x,\epsilon) + O(\epsilon),$

and that ${A(x,\epsilon)}$ runs in time polynomial in ${n}$ and ${1/\epsilon}$. 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 ${A(x,\epsilon)}$ did not appear to depend on the value of ${\epsilon}$. This seemed impossible; the algorithm used many approximations that depended on ${\epsilon}$ and other ${\delta}$‘s. How could its running time be independent from the value of ${\epsilon}$? 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 ${\epsilon}$ to tend to ${0}$. This would yield

$\displaystyle F(x) = A(x,\infty).$

But since the running time was independent of ${\epsilon}$, there had to be an algorithm so that

$\displaystyle F(x) = A'(x).$

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 ${n}$.

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?

Open Problems

Have any of your had a similar strange experience while working on a proof?

May 15, 2011 7:42 pm

Dr. Lipton: All of the time!

But the subtle difference between my close encounters and yours is that I realize after working hard on a particular approach that I have been silly the entire time. The most recent example I can think of is this: I asked myself what I thought was a natural generalization to solving systems of linear equations. The relationship between the number of unknown variables n and number of equations m characterizes the system (as determined, overdetermined or underdetermined – the number of solutions we are expected to have to said system). I asked my self “what if we know _some_ information about the known variables – can we characterize the number of solutions to a system of linear equations by the number of unknown bits j in m and n?” After working very hard on various approaches I discovered what would have been immediately obvious to anyone else: such a system with partial information about unknowns can be turned into an equivalent system of equations with all known bits pulled into constants.

Your aliens are of the Third Kind. Mine are the mean ones from Independence Day.

May 15, 2011 7:43 pm

Lots of typos in that last post. I hope the spirit of the message was communicated well.

May 15, 2011 8:41 pm

Ross,

Sorry for the typos. Sometimes we rush a post out.

May 16, 2011 12:36 am

Professor Lipton:

I’m sorry! I meant _I_ had a lot of typos. Your post was fine! I should have said, “Lots of typos in that last comment.” Another typo for my long list today!

2. May 15, 2011 8:42 pm

Our Quantum System Engineering Group had precisely the same experience, in which a code led us to a surprising result, that we eventually came to understand was a “trivial” result in Michael Spivak’s good sense of the word “trivial”:

Stokes’ Theorem shares three important attributes with many fully evolved major theorems: (1) It is trivial. (2) It is trivial because the terms appearing in it have been properly defined. (3) It has significant consequences.

Here the point is that whenever a computer code points us toward a startling theorem that is associated to a practically important problem, then that theorem is likely to prove trivial in Spivak’s sense … once we have carefully unwound the various definitions and proof strategies that the code knows (albeit implicitly), but we don’t.

Our codes pointed us to the trivial result that certain well-known conservation laws associated to quantum spin dynamics are exact not only on Hilbert spaces, but also on much larger classes of state-spaces (including classical state-spaces). To date, we have succeeded in unwinding the geometric/dynamical elements of the code’s capabilities … and the resulting theorems are helping us design cool new experiments and quantum spin imaging technologies. We are stoked at the trivial truths these codes are showing us!

But to date, we have been wholly unsuccessful unwinding the algebraic elements of the codes’ capabilities, which are equally mysterious (to us). We summarized these algebraic mysteries as a Math Overflow question: “Is an immersed Kronecker join always a multilinear variety on a Hilbert space?” … a question that so far has attracted 74 views, but no answers. So eventually we will offer a bounty on this question, but first we’re trying to find a more natural way to phrase it.

So algebraically at least, our experience has been that our computer codes sometimes are mysteriously smarter than we are.

• May 16, 2011 12:15 pm

As it turns out, Joseph Landsberg has written a very readable article titled Geometry and the complexity of matrix multiplication that goes far toward explaining why these algebraic/geometric/dynamic issues are challengingly deep … they’re intimately bound-up with topics that are of perennial interest here on Gödel’s Lost Letter and P=NP … see for example Dick’s essay of March 27, 2010 essay, titled Fast matrix products and other amazing results. Yes, these results are amazing … as are the surprising connexions among them! 🙂

3. May 15, 2011 10:56 pm

An amazing instance of a theorist conveying the gist of a result in terms intelligible to knowledgeable laymen!

May 15, 2011 11:23 pm

The way you reached that result is interesting, but now I’m very curious about what problem you proved was in P. Any hints?

May 16, 2011 12:03 pm

In the paper with Virginia on subcubic time reducibilities, initially we had a complicated reduction from Boolean Matrix Multiplication to Triangle Detection that made careful recursive calls on random subsets of a graph. Just analyzing the expected running time was a pain. After several attempts to understand what the algorithm was really doing, we found an embarrassingly simple deterministic reduction that looks like an undergraduate exercise!

6. May 16, 2011 2:21 pm

In a complex analysis class we were asked to show: “There is a function which is differentiable on a dense set and nondifferentiable on a dense set”. The “usual” answer involves Diophantine approximation theory but I had a hunch I could do it using computability theory instead, basically, using the fact that the Busy Beaver numbers outgrow all the computable functions. Eventually, I got it to work. But then I realized the way I had done it, the Busy Beaver numbers weren’t even necessary. I was able to eliminate them and get a wonderful elementary proof (which rather surprised the prof). I’ve written that up here: http://www.xamuel.com/densely-differentiable-and-densely-nondifferentiable/

May 16, 2011 11:40 pm

7. May 17, 2011 8:25 am

Informal evidence that P and NP are different perhaps …

8. May 18, 2011 3:10 am

I’m really looking forward to the result itself! Sounds like some quantum computation might be involved…

9. May 18, 2011 4:15 am

What a beautiful post! Totally enjoyable even for a math challenged person like me. Make that advanced math challenged.

May 29, 2011 9:10 am

Dr. Lipton, –

I think you’ve described a discovery of order in a problem, initially not apparent in it.

Additional order brings dimentionality down. Whenever our 3D location (x,y,z) is limited by some law, x^2+y^2+z^2=C say, we might actually be living on a sphere.

Not a matematician at all but a self-taught programmer, I once tried to solve the problem of approximating a smooth monotonic-curvature 2D curve (specifically, a clothoid) by a sequence of tangential arcs, with controlled precision (i.e. limiting the maximal deviation of arcs from the real curve).

I’ve explored it with an approximating solution, using as a unit component the so-called biarc – two G1-connected arcs touching at the real curve at their two end points. The connection point will be somewhere out, in general case, the ratio of two arcs lengths serving as an additional parameter.

After playing with it, computationally, I saw that parameter disappear and the two arcs of a biarc becoming one, when the deviation graph that I drew took on more and more regular shape, leading me to a discovery of certain principle – like your lemma – which allowed me to produce this symmetrical approximation directly, with one arc; moreover I could now prove to myself why it was so, and had a procedure defined to achieve the set value of precision directly.

So it’s kind of what you’ve described, only in a much less formal setting of CAD programming.