Research Life-Stories: Russell Impagliazzo

Next story on our project from Russell Impagliazzo

———————

It was my first semester at Wesleyan University. I was shuffling down the path crossing the main lawn in front of the administrative building in a jacket that was not warm enough. I had decided to astound my German professor by actually putting in a half hour or so in the language lab before class, but I was thinking about a math problem and not really paying attention to my surroundings.  My forward progress got slower and slower, until I stopped completely and took out a notebook and pen.

Peripherally, I saw someone approaching across the grass, a bearded student like myself, but with a more energetic pace. I didn’t really pay attention to him, lost in my own thoughts. I was surprised when he addressed me by name, asking “Are you Russell?”.

I looked around to see if there was another Russell on the path, but I was alone.  “Yes” I answered hesitantly.

“I’ve been wanting to meet you. ” the stranger said, “The word in the Math lounge is that you can prove anything by transfinite induction.”

I don’t know what shocked me more: that faculty gossipped about me, or that this guy was in on their gossip.  He was too young to be a grad student, let alone a prof. But the mention of transfinite induction put me on surer ground.  He used the words in an everyday tone, like he knew what they meant, and was not just parrotting something he heard.  So I decided to plunge right in.

“Well, uh,  I guess it’s kind of a lazy habit.  I, um,  just like to be able to well-order every set in sight.  It makes the arguments more concrete.”

“More algorithmic,” the strange student agreed, with an air that he had just made a subtle point. “So I take it that you’re a true believer in the Axiom of Choice?”

“Well, the Xorn’s Lemma version is counter-intuitive, but I can’t see how the product of non-empty sets could be empty”, I replied with a chuckle.  “The way I see it, if any logically equivalent formulation of an axiom  is self-evident, then we should accept it, even if other formulations are less clear.”

“Plus, it’s relatively consistent, so if set theory is consistent, so is set theory with Choice.” Here, he was showing himself to have knowledge beyond my level.

“Really?  How do you prove that?”  This came across as a challenge, but I was really just excited to think that this kind of statement was actually formally provable.

“I’m not sure.  But Kevin should cover it in logic next semester.  I assume you’re taking that class.” He said this as if someone  would have to be crazy not to.

“I haven’t really looked at the course catalog yet, but that sounds great.  Who’s Kevin?”  Not only didn’t I address faculty by their first names, I was only dimly aware they had them.

“Kevin Compton is the closest we have to a theoretical computer scientist in the department.   He’s really a logician, but he also works on recursion theory and computational complexity.  You know, P = NP .”

“I did see P=NP mentioned in some class’s syllabus, but it didn’t make sense to me.  I take it P and N aren’t just variables, because that equation isn’t really worth discussing.”

“No, P vs. NP is the most important problem in mathematics, because it captures the essential difficulty of doing mathematics.   Working on the P vs. NP problem is what brought me back into computer science. That, and the FFT.”

Somewhat disappointed because I’d hoped that he was a mathematician like myself, I replied, “Um, I’m taking CS right now, and I have to say I really hate it.  It’s so subjective.  I have to tell my roommate how to solve every problem, but he still gets better grades than me, because they say I have poor “style” and don’t  “document”.”

“You just have a bad teacher.  I’ve never met someone mathematically competent who wasn’t also a talented programmer.  Anyway, you looked deep in thought when I approached you just now.  What were you thinking about?”

“Geometry, but it’s sort of related to logic.   I was thinking about what we would need to add to the definition of metric space to get an actual geometry, and that got me thinking about how  our concepts of numbers and geometry are related. Euclid gave us the idea of proving theorems from axioms, but to make sense of his axioms, you need to already know what a number is.  But we’ve also gotten our idea of number from geometry, with our idea of real number being a consequence of distances like the hypoteneuse of a right triangle with equal sides being irrational.  So there’s kind of a circularity, and maybe we’re jumping to conclusions both about possible geometries and possilbe kinds of numbers.  So what I want to do is make axioms for both geometry and the concept of number that can be used for stuff like distances, areas, and so on, and see what other types of `numbers’ could be used in a geometry.” I illustrated my comments by pointing to the diagrams and equations I had been writing in my notebook when he approached.

The stranger seemed able to absorb my ideas even if they came out of my mouth in a kind of incoherent jumble. It had started to snow lightly, and a dusting of fresh snow covered the path we stood on.  The computer science student  didn’t have a jacket, and was keeping warm by doing some kind of dance move exercise that involved shifting balance in complex ways. I had been standing stock still while talking,  and sprinkles of snow covered  my hair and coat.

“Anyway,” I continued, “ I was thinking that “numbers”, whatever they are, should have an ordering, so we can talk about greatest or smallest distances, and an operation, so we can talk about the sum of distances.”

My new friend said, “Like a group operation?”

“I think so.  It should be commutative and associative.  Is that what a group is?  I haven’t taken Abstract Algebra yet, so my only knowledge is from this book I skimmed for a high school math project.”

“What was the project?”

“It turned out to have nothing to do with Abstract Algebra.  I was just looking at the way we define addition as repeated adding one, and multiplicaction as repeated addition, exponentiation as repeated multiplication, and generalizing.”

“Oh, you mean the Ackerman functions.  Yes, I’ve been thinking about what happens if you extend the Ackerman functions to the cardinal numbers.”

“Oh, someone’s looked at them already?  And don’t you mean extend them to the {\em ordinals} , not the {\em cardinals}?”

The stranger took mild offense at this suggestion.  “I’m like Alice.  I say what I mean.  I think it would be interesting to extend them to the {\em infinite cardinals}. ”

“But the successor operation for ordinals is so simple and for cardinals, it’s not really understood.”

The argument continued for a  while.  When I looked at my watch, German class was almost over. I was also getting very cold.  So I suggested we continue the conversation back at my dorm. As we neared the top floor, his nose crinkled. The bottom three floors of Harriman Hall had been converted to classrooms, but the top floor, where I lived, had been spared largely because my room had a great view of the playing field.  Whenever there was a football or baseball game, my room, the room opposite, and the corridor in between, were unofficially converted to extra stadium seating for the alumni.  We didn’t charge admission, but we did sell them booze at a mark-up, and the dorm still stank of cheap booze from the last game, especially my room.  My roommate Kimo was playing pop songs on his new electronic keyboard and singing along in his cracked voice at full volume. When I thought to introduce Kimo to the new student, I realized I hadn’t asked his name.  It would be embarrassing to ask now.  Bringing my new friend here was a serious mistake, and we wouldn’t even be able to continue our conversation.

Then Taco, the Japanese economics student next door, walked in. He looked up at the computer science student and exclaimed, “Digit!”  It turned out that they had gone to the same prep school, and began reminiscing happily.    So I had a name to call my new friend, even if it was a nerdy nickname even I was somewhat embarrassed to use.  (Of course, Takeshi was OK with calling himself “Taco”, and he called me “Scruffy”, so his standards for nicknames were pretty low.)

Taco had come by to challenge me to a game of Othello.  The whole dorm had undergone a fad for this strategy game, and Taco was the reigning champ. “Digit” encouraged us to play (in Taco’s room), and kibitzed during our game, that “Othello is an OK game, but it’s really just a simplification of go.” Taco agreed with this assesment, but claimed not to be smart enough to handle go.  “What’s go?” I asked, shocking Digit completely. “Go is mathematics and computer science put into a boardgame.  It’s boardgame complete! I’ll have to teach you; I know you’re going to be crazy about it. I learned it as part of a plan to seduce my  now-girlfriend Julia, but she quit go after I beat her in our third game. Fortunately, the seduction worked anyway.    Since then, I’ve ordered a complete set of go textbooks from Japan. They read like math books- Lemma! Pow! Theorem! Pow! QED! ” This reminded Digit that Julia was expecting him for dinner, so he left while we were still playing.

I think of that meeting as the time I became a mathematician.  Of course, I was interested in math before then, and even starting to have my own ideas.  But until then, I was just learning and thinking about mathematics for myself. After that, I had someone to share my ideas with.   The extent to which they would interest “Digit” (who was now known as “Steven Rudich” to all but high school friends) became my standard for judging my mathematical ideas. Before, every idea was equal.  Now, I had to be able to explain and justify my interests to Steven.  Before, novelty was judged by solely by whether I knew it already.  After, I had to be prepared to deal with anything Steven might know, and Steven knew a lot already. Mathematics moved from a purely intellectual activity to how mathematicians actually do mathematics, as a social activity.  Steven and I are still frequent collaborators.  He’s my intended audience whenever I’m thinking of new mathematical ideas.

Thanks to Steven Rudich and Beth Dugan for suggestions on an earlier version.