Sunday, March 25, 2018

Getting the right answer ... much later

A whole lot of years ago, I was a poor student at the University of Colorado in Boulder. Having nothing better to do (like school work) I was wandering the halls of the upper floors of the Engineering Center, and one name tag caught my eye.  It said "S. Ulam".

Being a geek and having gone to high school in Los Alamos, I knew about Stanislaw Ulam. At least, I knew a bit about the work he had done during the Manhattan project at Los Alamos. And that he was among the greats of mathematics. But it seemed totally implausible that the person behind that door could really be Stanislaw Ulam. Ulam was a creature of myth to me. Not just from another generation, but practically from another world. There was no way that it could be him. No way.

So I had to find out.

I knocked.

And was invited in.

So I asked, "Are you Stanislaw Ulam?". He seemed amused. "Yes".  "Uh..." I said.

Just as a note to anyone meeting a god who steps down onto the earth to walk among us, I suggest you have a question figured out ahead of time because you aren't going to come up with anything very good in the moment. At least I couldn't. In a similar vein, figure out your three wishes ahead of time as well in case you meet a genie.

After a moment of hurried thought, I came up with "Could we talk?". Seriously. That is the best I could do.

He said that would be fine, but that he had about 20 minutes of work to do first. To keep me busy, he gave me a problem to work on during that time. Not surprisingly, that problem was a really good one for assessing my mathematical sophistication.

That sophistication was not very high (and really still isn't decades later) partly because of youth and partly because of attitude and partly because schools can't deal with students who learn quickly. My history with math was that during an explosive few weeks in the 8th grade I had gotten the bug and worked my way through all of the high school math curriculum including calculus. It was a wonderful time and didn't feel like learning so much as just remembering how things worked. But there wasn't much anything to be done beyond that because there wasn't much anybody to talk to who knew what lay past that because we lived on a military base in Germany. I could wander through books, but I didn't really have enough understanding to go much further than a bit of differential geometry and multivariate calculus. Later, when we moved to Los Alamos, there were all kinds of people I could have learned from but I was engrossed in electronics and computing and German and Russian.

The problem that he gave me was to prove a simple fixed point theorem. Given a set $S$ and a continuous function $f: S \rightarrow S$ such that $f$ is a contraction, show that $f$ has a fixed point in $S$. A contraction is a function that maps distinct points closer together, $x_1 \ne x_2 \implies \rho(x_1, x_2) > \rho(f(x_1), f(x_2))$ where $\rho$ is some metric on $S$.

As with all good math questions, the first response should always be clarifications to make sure that the problem is actually well understood. Even though it has been a very long time, I remember asking if I could assume that $S$ is compact and that $f$ is continuous. As I remember, I didn't actually finish a proof during the short time I had then, but I did sketch out an approach that started by noting that $\rho(x, f(x)) > \rho(f(x), f(f(x)))$. Unfortunately, I took a wrong turn at that point and thought about limits. That apparently didn't matter and I had some great talks with Professor Ulam and his friend Jan Micielski.

One of the cool things about mathematics is that questions like this wind up in the back of your head and can pop out at any time. That just happened as I was reading a review of the latest edition of Proofs From the Book. This looks like a great book with all kinds of interesting insights to be had, but I just looked at their wonderfully short proof of the fundamental theorem of algebra. That proof goes something like this

  1. Every real-valued function $f$ over a compact set $S$ has a minimum in $S$
  2. Every point $x$ such that a complex polynomial is non-zero, $|p(x)|>0$, has a nearby point $x'$ such that $|p(x')| < |p(x)|$
  3. Thus, the minimum of $|p(x)|$ exists, but all points $x$ such that $|p(x)|>0$ are not the minimum. Therefore, for some point $x_0$ we have $|p(x_0)|=0$
Point 2 takes a tiny bit of algebra, but overall this proof is stunningly simple and beautiful. But in the way that these things happen, after reading this proof I remembered the contraction theorem that I hadn't quite come up with so long ago and it occurred to me that this same trick would apply there. 

The outline is 
  1. For any fixed point $x^*$, we have $\rho(x^*,f(x^*)) = 0$
  2. For any other point $x$ we have $\rho(x, f(x)) > 0$
  3. The function $d(x) = \rho(x, f(x))$ is continuous and has a minimum in $S$
  4. For any point $x$ such that $d(x) \ne 0$, we have $d(x) > d(f(x))$ and thus $d(x)$ is not minimized at $x$
  5. Thus, there exists some point $x^*$ where $d(x^*)=0$, that is to say $x^*$ is a fixed point.
Isn't it just the way of the world that you think of the perfect answer just a little bit too late?