Episode 10 - Mohamed Omar

Kevin Knudson: Welcome to My Favorite Theorem. I’m your host Kevin Knudson, professor of mathematics at the University of Florida. And I’m joined by my cohost.

EL: I’m Evelyn Lamb, a freelance math and science writer in Salt Lake City, Utah.

KK: Welcome home.

EL: Yeah, thanks. I just got back from Paris a week ago, and I’m almost back on Utah time. So right now I’m waking up very early, but not 3 in the morning, more like 5 or 6.

KK: Wait until you’re my age, and then you’ll just wake up early in the morning because you’re my age.

EL: Yeah. I was talking to my grandma the other day, and I was saying I was waking up early, and she said, Oh, I woke up at 4 this morning.

KK: Yeah, that’s when I woke up. It’s not cool. I don’t think I’m as old as your grandmother.

EL: I doubt it.

KK: But I’m just here to tell you, winter is coming, let me put it that way. We’re pleased today to welcome Mohamed Omar. Mohamed, why don’t you tell everyone a little bit.

MO: Great to be on the podcast. My name is Dr. Mohamed Omar. I’m a professor at Harvey Mudd College. My area of specialty is algebra and combinatorics, and I like pure and applied flavors of that, so theoretical work and also seeing it come to light in a lot of different sciences and computer science. I especially like working with students, so they’re really involved in the work that I do. And I just generally like to be playful with math, you know, have a fun time, and things like this podcast.

KK: Cool, that’s what we aim for.

EL: And I guess combinatorics probably lends itself to a lot of fun games to play, or it always seems like it.

MO: Yeah. The thing I really like about it is that you can see it come to life in a lot of games, and a lot of hobbies can motivate the work that comes up in it. But at the same time, you can see it as a lens for learning a lot of more advanced math, such as, like, abstract algebra, sort of as a gateway to subjects like that. So I love this diversity in that respect.

KK: I always thought combinatorics was hard. I thought I knew how to count until I tried to learn combinatorics. It’s like, wait a minute, I can’t count anything.

MO: It’s difficult when you have to deal with distinguishability and indistinguishability and mixing them, and you sort of get them confused. Yeah, definitely.

KK: Yeah, what’s it like to work at Harvey Mudd? That always seemed like a really interesting place to be.

MO: Harvey Mudd is great. I think the aspects I like of it a lot are that the students are just intrinsically interested and motivated in math and science, and they’re really excited about it. And so it really feels like you’re at a place where people are having a lot of fun with a lot of the tools they learn. So when you’re teaching there, it’s a really interactive, fun experience with the students. There’s a lot of active learning that goes on because the students are so interested in these things. It’s a lot of fun.

KK: Very cool. So, Mohamed, what’s your favorite theorem?

MO: First of all, my favorite theorem is a lemma. Actually a theorem, but usually referred to as a lemma.

KK: Lemmas are where all the work is, right?

MO: Exactly. It’s funny you mention combinatorics because this is actually in combinatorics. It’s called Burnside's Lemma. Yeah, so I love Burnside's Lemma a lot, so maybe I’ll give a little idea of what it is and give an idea in light of what you mentioned, which is that combinatorics can be quite hard. So I’ll start with a problem that’s hard, a combinatorial one that’s hard. So imagine you have a cube. A cube has six faces, right? And say you ask the naive question how many ways are there to paint the faces of the cube with colors red, green, and blue.

KK: Right.

MO: You think, there are six faces, and the top face is either red, or green, or blue, and for every choice of color I use there, another face is red or green or blue, etc. So the number of colorings should be 3x3x3x3x3x3, 3^6.

EL: Right.

MO: But then, you know, you can put a little bit of a twist on this. You can say, how many ways are there to do this if you consider two colorings to be the same if you take the cube and rotate it, take one coloring, rotate the cube, and get another coloring.

EL: Right. If you had the red face on the left side, it could be on the top, and that would be the same.

MO: One naive approach that people tend to think works when they first are faced with this, is they think, OK, there are 6 faces, so maybe I can permute things 6 ways, so I divide the total number by 6.

KK: Wrong.

MO: Exactly. There are a lot of reasons. One is sort of the empirical reason. You said the answer was 3^6 if we’re not caring about symmetry. If you divide that by 6, there’s a little bit of a problem, right?

EL: Yeah.

MO: You can kind of see. If you have a painting where all the faces are red, no matter how you rotate that, you’re going to end up with the same coloring. But as you mentioned, if you color one face red and the rest green, for instance, then you get six different colorings when you rotate this cube around. So you’ve got to do something a little bit different. And Burnside's lemma essentially gives you a nice quick way to approach this by looking at something that’s completely different but easy to calculate. And so this is sort of why I love it a lot. It’s a really, really cool theorem that you can sort of explain at a maybe discrete math kind of level if you’re teaching at a university.

KK: So the actual statement, let’s see if I can remember this. It’s something like the number of colorings would be something like 1 over the order of the group of rotations times the sum of what is it the number of elements in each orbit, or something like that? I used to know this pretty well, and I’ve forgotten it now.

MO: Yeah, so something like that. So a way to think about it is, you have your object, and it has a bunch of symmetries. So if you took a square and you were coloring, say, the edges, this is an analogous situation to the faces of the cube. A square has 8 symmetries. There are the four rotations, but then you can also flip along axes that go through opposite edges, and then axes that go through opposite vertices.

So what Burnside's lemma says is something like this. If you want to know the number of ways to color, up to this rotational symmetry, you can look at every single one of these symmetries that you have. In the square it’s 8, in the cube it turns out to be 24. And for every single symmetry, you ask yourself how many ways are there to color with the three colors you have where the coloring does not change under that symmetry.

KK: The number of things fixed, essentially, right.

MO: Exactly. The number of things fixed by the symmetries. So like I mentioned, the cube has 24 symmetries. So let’s take an example of one. Let’s say you put a rod through the center of two opposite faces of the cube.

KK: Right.

MO: And you rotate 90 degrees along that. So you’re thinking about the top face and the bottom face and just rotating 90 degrees. Let’s just think about the colorings that would remain unchanged by that symmetry. So you’re free to choose whatever you’d like for the top and bottom face. But all the side faces will have to have the same color. Because as soon as you get another face. Whatever was in that face is now rotated 90 degrees as well. So if you count the number of colorings fixed by that rotation about the rod through the opposite faces, you get something like, well you have three choices for those side faces. As soon as you choose the color for one, you’re forced to use the same color for the rest. And then you have freedom in your top and bottom faces. So that’s just one of the symmetries. Now if you did that for every single symmetry and took the average of them, it turns out to be the number of ways to color the faces of the cube up to rotational symmetry in general.

So it’s kind of weird. There’s sort of two things that are going on. One is why in the world would looking at the symmetries and counting the number of colorings fixed under the symmetry have anything to do with the number of colorings in total up to symmetry in general? It’s not clear what the relationship there is at first. But the real cool part is that if you take every single symmetry and count the number of colorings, that’s a systematic thing you can do without having to think too hard. It’s a nice formula you can get at the answer quite quickly even though it seems like a complicated thing that you’re doing.

EL: Yeah. So I guess that naive way we were talking about to approach this where you just say, well I have three choices for this one, three choices for that one, you almost kind of look at it from the opposite side. Instead of thinking about how I’m painting things, I think about how I’m turning things. And then looking at it on a case by case basis rather than looking at the individual faces, maybe.

MO: Exactly. When I first saw this, I saw this as an undergrad, and I was like, “What?!” That was my initial reaction. It was a cool way to make some of this abstract math we were learning really come to life. And I could see what was happening in the mathematics physically, and that gave me a lot of intuition for a lot of the later things we were learning related to that theorem.

EL: Was that in a combinatorics class, or discrete math class?

MO: It was actually in a standalone combinatorics class that I learned this. And now another reason I really like this lemma is that I teach it in a discrete math course that I teach at Harvey Mudd, but then I revisit it in an abstract algebra course because really, you can prove this theorem using a theorem in abstract algebra called the orbit stabilizer theorem. So orbits are all of these different, you take one coloring, spin it around in all possible ways, you get a whole bunch of different ones, and stabilizers you can think of as taking one symmetry and asking what colorings are fixed under that symmetry. So that’s in our example what those two things are. In abstract algebra, there’s this orbit stabilizer theorem that has to do with more general objects: groups, like you mentioned. And then one of the things I really like about this theorem is that it sets the stage for even more advanced math like representation theory. I feel like a lot of the introductory concepts in a representation theory course really come back to things you play with in Burnside’s Lemma. It’s really cool in its versatility like that.

KK: That’s the context I know it in. So I haven’t taught group theory in 10 years or so, but it was in that course. Now I’m remembering all of this. It’s coming back. This is good. I’m glad we’re having this conversation. I’m with you. I think this is a really remarkable theorem. But I never took a combinatorics course that was deep enough where we got this far. I only know it from the groups acting on sets point of view, which is how you prove this thing, right? And as you say, it’s definitely leads into representation theory because, as you say, you can build representations of your groups. You just take a basis for a vector space and let it act this way, and a lot of those character formulas really drop out of this.

MO: Exactly.

KK: Very cool.

EL: So it sounds like you did not have a hard time choosing your favorite theorem. This was really, you sound very excited about this theorem.

MO: The way I tried to think about what my favorite theorem was what theorem to I constantly revisit in multiple different courses? If I do that, I must like it, right? And then I thought, hey, Burnside's Lemma is one that I teach in multiple courses because I like all the different perspectives that you can view it from. Then I had this thought: is Burnside's Lemma really a theorem?

KK: Yeah, it is.

MO: I felt justified in for the following reason, which is I think this lemma’s actually due to Frobenius, not Burnside. I thought, since the Burnside part is not really due to Burnside, then maybe the lemma part really is a theorem.

EL: I must say, Burnside sounds like it should be a Civil War general or something.

MO: Definitely.

EL: So what have you chosen to pair with your theorem?

MO: So I thought a chessboard marble cake would be perfect.

KK: Absolutely.

EL: OK!

MO: So first of all, I had a slice of one just about a few hours ago. It was my brother’s birthday recently, and I’m visiting family. There was leftover cake, and I indulged. But then I thought yeah, one of the prototypical problems when playing around with Burnside's Lemma is how many ways are there to color the cells of a chessboard up to rotational symmetry? So when I was eating the cake, I thought, hey, this is perfect!

EL: That’s great.

KK: How big of a chessboard was it?

MO: 8x8.

KK: Wow, that’s pretty remarkable.

MO: It was a big cake. I had a big piece.

KK: So when you sliced into it, was it 8x8 that way, or 8x8 across the top?

MO: Across the top.

KK: I’m sort of imagining, so my sister in law is a pastry chef, and she makes these remarkably interesting looking things, and it’s usually more like a 3x3, the standard if you go vertical.

EL: I’ve never tried to make a chessboard cake. I like to bake a lot, but anything that involves me being fussy about how something looks is just not for me. In baking. Eating I’m happy with.

MO: I’m the same. I really enjoy cooking a lot. I enjoy the cooking and the eating, not the design.

KK: Yeah, I’m right there with you. Well this has been fun. Thanks for joining us, Mohamed.

EL: Yeah.

MO: Thank you. This has been really enjoyable.

KK: Take care.

MO: Thank you.

[outro]

Show notes (click here)