Episode 20 - Francis Su

My Favorite Theorem

Evelyn Lamb: Hello and welcome to My Favorite Theorem. I’m your host Evelyn Lamb. I’m a freelance math and science writer in Salt Lake City, Utah. And this is your other host.
Kevin Knudson: Hi, I’m Kevin Knudson, professor of mathematics at the University of Florida. How are you doing, Evelyn?
EL: I’m all right. I am hanging in there in the winter as a displaced Texan.
KK: It’s not even winter yet.
EL: Yeah, well, somehow I manage to make it to the end of the season without dying every year outside of Texas, but yeah, the first few cold days really throw me for a loop.
KK: Well my son’s in college now, and they had snow last week.
EL: Well the south got a bunch of snow. Is he in South Carolina, is that right?
KK: North Carolina, and he’s never driven in snow before, and we told him not to, but of course he did. No incidents, so it was okay.
EL: So we’re very glad to have our guest today, who I believe is another displaced Texan, Francis Su. Francis, would you like to tell us a little bit about yourself?
Francis Su: Hi, Evelyn and Kevin. Sure. I’m a professor of mathematics at Harvey Mudd College, and that’s a small science and engineering school in southern California, and Evelyn is right. I am a displaced Texan from a small town in south Texas called Kingsville.
EL: Okay. I grew up in Dallas. Is Kingsville kind of between Houston and Beaumont?
FS: It’s between Houston and the valley. Closer to Corpus Christi.
EL: Ah, the other side. Many of us displaced Texans end up all over the country and elsewhere in the world.
FS: That’s right. I’m in California now, which means I don’t have to deal with the winter weather that you guys are wrestling with.
KK: I’m in Florida. I’m okay.
EL: Yeah. And you’re currently in the Bay Area at MSRI, so you’re not on fire right now.
FS: That’s right. I’m at the Math Sciences Research Institute. There’s a semester program going on in geometric and topological combinatorics.
KK: Cool.
EL: Yeah, that must be nice. Is this your, it’s not too long after your presidency of the Mathematical Association of America, so it must be nice to be able to not have those responsibilities and be able to just focus on research at MSRI this semester.
FS: That’s right. It was a way of hopping back into doing research after a couple of years doing some fun work for the MAA.
EL: So, what is your favorite theorem? We would love to hear it.
FS: You know, I went around and around with this because as mathematicians we have lots of favorite theorems. The one I kept coming back to was the Brouwer fixed point theorem.
KK: I love this theorem.
FS: Yes, so the Brouwer fixed point theorem is an amazing theorem. It’s about a hundred years old. It shows up in all sorts of unexpected places. But what it loosely says is if you have a continuous function from a ball to itself—and I’ll say what a ball means in a minute—it must have a fixed point, a point that doesn’t move. And a ball can be anything that basically has no holes.
EL: So anything you can make out of clay without punching a hole in it, or snaking it around and attaching two ends of it together. I’m gesturing with my hands. That’s very helpful for our podcast listeners.
KK: Right.
FS: Exactly.
KK: We don’t even need convexity, right? You can have some kind of dimpled blob and it still works.
FS: That’s right. It could be a blob with a funny shape. As long as it can be deformed to something that’s a ball, the ball has no holes, then the theorem applies. And a continuous function would be, one way of thinking about a continuous function from a ball to itself is let’s deform this blob, and as long as we deform the blob so that the blob stays within itself, then the blob doesn’t move. A very popular way of describing this theorem is if you take a cup of coffee, let’s say I have a cup of coffee and I take a picture of it. Then slosh the coffee around in a continuous fashion and then take another picture. There is going to be a point in the coffee that is in the same spot in both pictures. It might have moved around in between, but there’s going to be a point that’s in the same spot in both pictures. And then if I move that point out of its original position, I can’t help but move some other point into its original position.
EL: Yeah, almost like a reverse diagonalization. In diagonalization you show that there’s a problem because anything you thought you could get on your list, you show that something else, even if you stick it on the list, something else is not on the list still. Here, you’re saying even if you think, if I just had one fixed point, I could move it and then I wouldn’t have any, you’re saying you can’t do that without adding some other fixed point.
FS: That’s right. The coffee cup sloshing example is a nice one because you can see that if I take the cup of coffee and I just empty it and pour the liquid somewhere else, clearly there’s not going to be a fixed point. So you sort of see the necessity of having the ball, the coffee, mapped to itself.
KK: And if you had a donut-shaped cup of coffee, this would not be true, right? You could swirl it around longitudinally and nothing would be fixed.
FS: That’s right. If you had a donut-shaped coffee mug, we could. That’s right. The continuity is kind of interesting. Another way I like to think about this theorem is if you take a map of Texas and you crumple it up somewhere in Texas, there’s a point in the map that’s exactly above the point it represents in Texas. So that’s sort of a two-dimensional version of this theorem. And you see the necessity of continuity because if I tore the map in two pieces and threw east Texas into west Texas and west Texas into east Texas, it wouldn’t be true that there would be a point exactly above the point it represents. So continuity is really important in this theorem as well.
KK: Right. You know, for fun, I put the one-dimensional version of this as a bonus question on a calculus test this semester.
FS: I like that version. Are you referring to graphing this one-dimensional function?
KK: Right, so if you have a map from a unit interval to itself, it has a fixed point. This case is nice because it’s just a consequence of the intermediate value theorem.
FS: Yes, that’s a great one. I love that.
KK: But in higher dimensions you need a little more fire power.
FS: Right. So yeah, this is a fun theorem because it has all sorts of maybe surprising versions. I told you one of the popular versions with coffee. It can be used, for instance, to prove the fundamental theorem of algebra, that every polynomial has a root in the complex numbers.
EL: Oh, interesting! I don’t think I knew that.
KK: I’m trying to think of that proof.
FS: Yeah, so the idea here is that if you think about a polynomial as a function and you’re thinking of this as a function on the complex plane, basically it takes a two-dimensional region like Texas and maps it in some fashion back onto the plane. And you can show that there’s a region in this map that gets sent to itself, roughly speaking. That’s one way to think about what’s going on. And then the existence of a zero corresponds to a fixed point of a continuous function, which I haven’t named but that’s sort of the idea.
EL: Interesting. That’s nice. It’s so cool how, at least if I’m remembering correctly, all the proofs I know of the fundamental theorem of algebra are topological. It’s nice, I think, for topology to get to throw an assist to algebra. Algebra has helped topology so much.
FS: I love that too. I guess I’m attracted to topology because it says a lot of things that are interesting about the existence of certain things that have to happen. One of the things that’s going on at this program at MSRI, as the name implies, geometric and topological combinatorics, people are trying to think about how to use topology to solve problems in combinatorics, which seems strange because combinatorics feels like it just has to do with counting discrete objects.
EL: Right. Combinatorics feels very discrete, and topology feels very continuous, and how do you get that to translate across that boundary? That’s really interesting.
FS: I’ll give you another example of a surprising application. In the 1970s, actually people studied this game called Hex for a while. I guess Hex was developed in the ‘40s or ‘50s. Hex is a game that’s played on a board with hexagonal tiles, a diamond-shaped board. Two players take turns, X and O, and they’re trying to construct a chain from one side of the board to the other, to the opposite side. It turns out that the Brouwer fixed-point theorem, well you can ask the question: can that game ever end in a draw configuration where nobody wins? For large boards, it’s not so obvious that the game can’t end in a draw. But in a spectacular application of the Brouwer fixed-point theorem it can’t end in a draw using the Brouwer fixed-point theorem.
EL: Oh, that’s so cool.
KK: That is cool. And allegedly this game was invented by John Nash in the men’s room at Princeton, right?
FS: Yes, there’s some story like that, though I think it actually dates back to somebody before.
KK: Probably. But it’s a good story, right, because Nash is so famous.
EL: So was it love at first sight with the Brouwer fixed-point theorem for you, or how did you come across it and grow to love it?
FS: I guess I encountered it first as an undergraduate in college when a professor of mine, a topology professor of mine, showed me this theorem, and he showed me a combinatorial way to prove this theorem, using something known as Sperner’s lemma. There’s another connection between topology and combinatorics, and I really appreciated the way you could use combinatorics to prove something in topology.
EL: Cool.
KK: Very cool.
KK: You know, part of our show is we ask our guest to pair their theorem with something. So what have you chosen to pair the Brouwer fixed-point theorem with?
FS: I’d like to pair it with parlor games. Think of a game like chess, or think of a game like rock-paper-scissors. It turns out that the Brouwer fixed-point theorem is also related to how you play a game optimally, a game like chess or rock-paper-scissors optimally.
KK: So how do you get the optimal strategy for chess from the Brouwer fixed-point theorem?
FS: Very good question. So the Brouwer fixed-point theorem can’t tell you what the optimal strategy is.
KK: Just that it exists, right, yeah.
FS: It tells you that there is a pair of optimal strategies that players can play to play the game optimally. What I’m referring to is something known as the Nash equilibrium theorem. Nash makes another appearance in this segment. What Nash showed is that if you have a game, well there’s this concept called the Nash equilibrium. The question Nash asked is if you’re looking at some game, can you predict how players are going to play this game? That’s one question. Can you prescribe how players should play this game? That’s another question. And a third question is can you describe why players play a game a certain way? So there’s the prediction, descriptions, and prescription about games that mathematicians and economists have gotten interested in. And what Nash proposed is that in fact something called a Nash equilibrium is the best way to describe, prescribe, and predict how people are going to play a game. And the idea of a Nash equilibrium is very simple, it’s just players playing strategies that are mutually best responses to each other. And it turns out that if you allow what are called mixed strategies, every finite game has an equilibrium, which is kind of surprising. It suggests that you could maybe suggest to people what the best course of action is to play. There is some pair of strategies by both players, or by all players if it’s a multiplayer game, that actually are mutual best replies. People are not going to have an incentive to change their strategies by looking at the other strategies.
KK: The Brouwer fixed point theorem is so strange because it’s one of those existence things. It just says yeah, there is a fixed point. We tend to prove it by contradiction usually, or something. There’s not really any good constructive proofs. I guess you could just pick a point and start iterating. Then by compactness what it converges to is a fixed point.
FS: There is actually, maybe this is a little surprising as well, this theorem I mention learning as an undergrad, it’s called Sperner’s lemma, it actually has a constructive proof, in the sense that there’s an efficient way of finding the combinatorial object that corresponds to a fixed point. What’s surprising is that you can actually in many places use this constructive combinatorial proof to find, or get close to, a proposed fixed point.
KK: Very cool.
FS: That’s kind of led to a whole bunch of research in the last 40 years or so in various areas, to try to come up with constructive versions of things that prior to that people had thought of as non-constructive.
EL: Oh, that’s so cool. I must admit I did not have proper appreciation for the Brouwer fixed-point theorem before, so I’m very glad we had you on. I guess I kind of saw it as this novelty theorem. You see it often as you crumple up the map, or do these little tricks. But why did I really care that I could crumple up the map? I didn’t see all of these connections to these other points. I am sorry to the Brouwer fixed-point theorem for not properly appreciating it before now.
FS: Yes. I think it definitely belongs on a top ten list of top theorems in mathematics. I wonder how many mathematicians would agree.
KK: I read this book once, and the author is escaping me and I’m kind of embarrassed because it’s on the shelf in my other office, called Five Golden Rules. Have you ever seen this book? It was maybe 10 or 15 years ago.
EL: No.
KK: One of the theorems, there are like five big theorems in mathematics, it was the Brouwer fixed-point theorem. And yeah, it’s actually of fundamental importance to know that you have fixed points for maps. They are really important things. But the application he pointed to was to football ranking schemes, right? Because that’s clearly important. College football ranking schemes in which in essence you’re looking for an eigenvector of something, and an eigenvector is a fixed point with eigenvalue 1, and of course the details are escaping me now. This book is really well-done. Five Golden Rules.
EL: We’ll find that and put it in the show notes for sure.
FS: I haven’t heard of that. I should look that one up.
KK: It’s good stuff.
FS: I’ll just mention with this Nash theorem, the basic idea of using the Brouwer fixed-point theorem to prove it is pretty simple to describe. It’s that if you look at the set of all collections of strategies, if they’re mixed strategies allowing randomization, then in fact that space is a ball.
KK: That makes sense.
FS: And then the cool thing is if players have an incentive to deviate, to change their strategies, that suggests a direction in which each point could move. If they want to deviate, it suggests a motion of the ball to itself. And the fact that the ball has a fixed point means there’s a place where nobody is incentivized to change their strategy.
EL: Yeah.
KK: Well I’ve learned a lot. And I even knew about the Brouwer fixed-point theorem, but it’s nice to learn about all these extra applications. I should go learn more combinatorics, that’s my takeaway.
EL: Yeah, thanks so much for being on the show, Francis. If people want to find you, there are a few places online that they can find you, right? You’re on Twitter, and we’ll put a link to your Twitter in the show notes. You also have a blog, and I’m sorry I just forgot what it’s called.
FS: The Mathematical Yawp.
EL: That’s right. We’ll put that in the show notes. I know there are a lot of posts of yours that I’ve really appreciated, especially the ones about helping students thrive, doing math as a way for humans to grow as people and helping all students access that realm of learning and growth. I know those have been influential in the math community and fun to read and hear.
Show notes (click here)