Episode 83 - Cihan Bahran

My Favorite Theorem

Evelyn Lamb: Hello, and welcome to My Favorite Theorem, the math podcast with no quiz at the end. I'm Evelyn Lamb, one of your co-hosts, coming to you from snowy Salt Lake City, Utah, where I feel like I've said that the past few times we've been taping. Which is great, because we really need the water. It is beautiful today, and I am ever so grateful that the life of a freelance writer does not require me to drive in conditions like this, especially as someone who grew up in Texas where conditions like this did not exist, and so I am extremely unconfident in snow and ice. So yeah, coming to you from the opposite side of the weather spectrum is our other host.
Kevin Knudson: I’m Kevin Knudson, professor of mathematics at the University of Florida. It's true. It's the opposite end of the spectrum, but hey, you know, I was putting up my Christmas tree the week before last and I was sweating. So this is my reality.
EL: Yeah.
KK: It’s hard to get in the mood, you know, you put on the Christmas music and you you get the tree out of the attic. And then I'm in, like, shorts and a t-shirt and sweating.
EL: You can sympathize with Australians, who have to deal with that every single year.
KK: That’s right. That's right. Yeah. So anyway, we're looking forward to a nice holiday. My son's going to come home after Boxing Day because he has a part time job at a bookstore in Vancouver and his boss said no one gets Boxing Day off.
EL: Yeah, that's that's a thing in some places.
KK: In the Commonwealth. I think it's a big thing. Right? So yeah, he'll be home on the 28th. So we're looking forward to that. But anyway, anyway, this will be after this will be after the holidays when people hear this anyway. So they'll go, gee, I wonder how that went?
EL: Yeah. Waiting with bated breath for updates about your son’s Boxing Day experience.
KK: That’s right. That's right.
Yes. Well, today we are very happy to have on the show Cihan Bahran, coming to us from I don't know what kind of weather. So yeah, could you introduce yourself and tell us about the local conditions?
Cihan Bahran: Yeah. Thanks for having me. I am joining you from Ankara, Turkey, which is the capital of Turkey in the middle. So it's a continental climate, I would say. But it has been rather mild. We haven't had any snow yet or really anything that close to freezing temperature. So yeah, it's chilly, but yeah, I like it.
EL: Yeah. And so what what kind of math are you interested in
CB: Right. So I am interested in representation theory, especially with functorial methods, and I am doing a postdoc here about that at this at this time. So actually, maybe I'm at a little bit of a disadvantage in that the theorem I will share is not necessarily directly from my expertise, so I'm not really, maybe on top of the literature or the methods, but I thought I would pick that because I find it really interesting.
EL: Sometimes, honestly, that could be a little better, because we are also not experts in that.
KK: That’s right. Yeah.
EL: But yeah, and you run a Twitter account, and I meant to look up the exact — is it called some theorems?
CB: Yeah, it's called some some theorems. The username is something like Cihan posts theorems [Editor’s note: It’s @CihanPostsThms] Okay, let me talk about that a bit. So I guess it goes back to maybe 2020 or something, not this account, so that was the pandemic time and for me, maybe psychologically a difficult time that I was seeking out somewhere to connect with the math world. And I found initially a Facebook page called Theorems. And it is it is still running, I guess. But I started posting there. And I had a lot of, like, some bits of knowledge about some interesting theorems that I would, like, share with my friends. And it became like, I was almost daily posting, like the group became dominated by my posts, to the point that people started asking, like, what are you really doing, et cetera. And then maybe since last year, I've been more on Twitter, and I posted some of these on my personal Twitter account. But then for some reasons, I had to make my personal account private. And at some point, I thought I might repost these things that I have had collected, because that group in Facebook was actually a private group, not everyone can see it before joining. And I thought I would post those on Twitter, and I find it, like, when it gets some responses, it's like a dopamine hit for me.
KK: Sure.
CB: And I was actually almost aggressively posting in the summer because I had all this sort of backlog. And at this point in time, I have posted most of the past stuff, and I post much less regularly. When I see something interesting, I post them to the to that account. And I suppose how that's how I am maybe known in math Twitter-verse.
EL: Yeah. And so as a person with with much knowledge and love for theorems, what is your favorite favorite zero?
CB: Okay, so I don't know if it's my favorite, but at least for this episode of My Favorite Theorem, the theorem I would like to share is the so-called — well, so there's this problem, and the theorem says that this is algorithmically undecidable. So what's the problem? The problem is called matrix mortality.
EL: Which is a really an inviting name.
KK: It’s a great name, right? It sounds like a video game or something. Yeah.
CB: Yeah. So, in the most general sense it asks, so the input is a finite list of square matrices of the same size. And the the the decision problem is whether a product of these things in some order, possibly with repetitions, could be ever zero or not. So, if an algorithm would say yes or no to each such collection. And I think at first this was shown to be undecidable for already 3 × 3 matrices in the 70s. And then there were some further developments as to because of course, if I give you one matrix, then matrix mortality becomes is this matrix nilpotent, and you can determine that by the characteristic polynomial, so that is decidable. So how few, how short can the list get and remain undecidable? I think for 3 × 3 matrices, it has been shown in 2014 or so that six 3 × 3 matrices, the problem is undecidable. So like A, B, C, D, E, F, F, that’s six 3 × 3 matrices. So that's like, what, like 54 entries of integers? These are all integer matrices, by the way.
KK: Okay. I was going to ask that.
CB: Snd then the question is, is some product ever zero or not? There can be no algorithm answering that for every possible input. And if you make the, if we allow the matrices to be a bit bigger, there is a version which says that when you make the size 15 × 15, it is undecidable for even two matrices. So just, like, two matrices of size 15, A and B, the decision problem, is ever a sequence of A's and B's equal to the zero matrix? And such an algorithm cannot exist, it's undecidable. It's rather striking.
EL: Yeah, I guess — I'm actually a little more upset about the six, 3 × 3 than the two 15 × 15’s. Because honestly, I just imagined trying to write down the entries of a 15 × 15 matrix, and I give up maybe 30% of the way through, I'll just, okay, whatever.
CB: Well, there is still a gap in knowledge. So let me talk a bit about what's known. For I think, two, 2 × 2 matrices, just two of them, it has been maybe recently shown that that is decidable. So but when the list is, when you have three or more matrices, I believe open. Also, I believe it's still open, whether if you're given, like, five, 3 × 3 or four the lowest boundary we know is six, although from from the development, you might — I would guess that it will remain undecidable for even two 3 × 3 matrices. But that's, I think, unknown at the moment.
KK: So once you show that it's undecidable for a certain, so for six, 3 × 3’s is undecidable, so that means it's undecidable for six of any size larger than 3 × 3, correct?
CB: Yeah.
KK: Because it sort of stabilizes, right? You can put those inside of the next size up by just sticking a one down on the lower corner with a block.
CB: Exactly, you can even you can even pad them by zeros, right?
KK: Sure. Sure.
CB: The mortality problem will not change once you've artificially made your 6 × 6 matrices into 10 × 10 matrices by writing zeros everywhere else.
KK: I see. So the question is for a fixed n, can you what's the minimal number k for which it's undecidable? Right?
CB: Yeah. So there are two parameters, how many matrices and the size of the matrices.
EL: But I guess there's a chance that it's three for 2 × 2 and two for everything else.
CB: Maybe. If I were to bet, I might bet that 2 × 2 is special and would be decidable always, and like the 3 × 3 introduces — but that's just a hunch. I don't really know much about how these things are done, because, like — I mean, I did look a bit to the into the two 2 × 2 matrices, and the algorithm is by computing some some eigenvalues or such, and I and 2 × 2 is so small that I would guess that is enough information somehow, but I don’t know.
KK: Now, I'm just thinking about this, right? This is sort of different from — so I would think of this in terms of the group generated by these matrices, but that's not at all what you're doing, right?
CB: Yeah, it's more like a monoid because it becomes zero. Also, I would like to, for people who know about the word problem, this this reminds people of the word problem for groups. And there is, of course, a relationship, but I would object to the argument that, “Oh, because the word problem is undecidable, that’s not so surprising.” And my objection is that we can always multiply the matrices. A specific instance is always decidable. We can just multiply them and see. For the word problem, there are even specific instances, which remain, like, is deciding whether a word is trivial can be made into a specific presentation and remain undecidable already there. It’s not like because you have maybe relations between the words, you don't know how to change your word into something. But with matrices, we can always, we can multiply like multiplications doable. But when you when we allow, is there ever zero among arbitrarily long multiplication that that is where the problem is. I think the word problem, the problem arises earlier than that.
KK: And that direct analogy with the word problem, you'd be looking for products where you get the identity, right, as opposed to zero. So I guess you don't want any of these matrices to be invertible. It's allowable, I imagine. But but if you have an invertible one, that’s not going to help.
CB: Yeah, I mean, the invertible ones, you can always — I guess, well…
KK: I don't know, though, maybe you need a permutation matrix to make some product work out correctly? I don't know. This is an interesting question. I like this question.
EL: Yeah.
KK: We’re not going to try to solve it on the spot.
CB: I’m not sure. Like, my first thought is that you can probably even, like, throw the invertible ones out. But now I'm not so sure. Maybe they might help in some way of arranging the zeros.
KK: So where did you come across this theorem? This is an interesting result.
CB: Yeah, well, undecidable problems always have fascinated me, and I guess I might have been looking at some of these, maybe it was, I don't know where I came across it. Maybe it was some survey paper of undecidable problems, or maybe a Math Overflow question. I'm not sure. But yeah, somewhere along those lines.
EL: But it's a nice one that's maybe a little more accessible to most people who have taken, you know, a few upper-level math classes than some of the undecidability things, which are just like, Okay, I need to climb this whole mountain to even understand this. You know, we all take linear algebra at some point, you know, if you're a math major or something, and so it's very concrete, you can immediately understand what it is if you’ve seen matrices.
CB: I agree. The description is rather elementary. You don't need to introduce Turing machines and halting arrays or some abstract presentations of groups and such. It's rather — the operations are ones that, as you said, any linear algebra student has seen before, but somehow the problem is already like, not even difficult, it's impossible in some sense.
EL: It is always really interesting to see, like, what are the limits, not just of our knowledge, but of what we can know about our possible knowledge.
KK: Right. Yeah. So the other thing we do on this podcast is we invite our guests to pair their theorem with something. So what pairs with this theorem that doesn't really have a name, but we'll call it the undecidability matrix theorem or something?
CB: Yeah, okay. So I'm not really a food person, so I didn't think of a food. What this — I would say that it pairs well with a decent table tennis service. Because it — there’s some, like, it’s not a killer service but decent, so you can have a decent back and forth, as we have just had, as to like, how small you can make it, how bad is it, that sort of thing. So that's what it reminds me of.
KK: Yeah. All right.
EL: Do you do you play table tennis?
CB: I like table tennis. I don't play as much as I would like to, but occasionally I do play it, and I like playing it.
KK: I’m much better on the Wii than I am in real life. The Wii table tennis is really fun.
CB: Ah, okay.
KK: In real life, not so much. I mean, I like it, but I'm not very good.
CB: I also heard people play on VR online. You can even like see a table.
KK: It’s not quite the same.
EL: I have not played since I was probably in sixth grade or something, when I think I was pretty capable of beating all of my opponents, who were my younger siblings. So, you know, at that age, you’ve kind of got just some advantage by being a little older. And so I tried to take advantage of that whenever I could, as the oldest sibling. You know, I really, we played two-on-one basketball sometimes, and I always kicked their butts at that because, you know, I was way taller. It helped a lot. I couldn't really play but like, against someone four or five years younger…
KK: My problem with all racket sports is that I played a lot of tennis when I was in high school. And so I play all racket sports like tennis. So you know, with big swings, so that doesn't work in table tennis. I's a much faster, yeah, just shorter.
CB: Much more of a wrist play than the whole arm.
KK: That’s right. Yeah. And racquetball is the same way. Like, I want the ball at my waist. I don't want to be reaching down to my ankles. I'm too tall. I can't get there. You know. So all these things were a challenge for me.
EL: Yeah, well, I do really like this pairing, because just like this theorem is sort of this meta- about, not just a specific case of matrices, but like, what we can know in general, given, you know, any set of information, your pairing was not just about the theorem, but was also about our discussion of the theorem.
CB: Yeah.
EL: So I think this was this was very elegant. I appreciate that.
CB: Thank you. I also like that we still have a gap in knowledge. I think that as, I don't know, like, teachers, we introduce — I remember being as a student, that that would really pique my interest, like, when teachers discover, you know, this is not known. And I think it offers a different landscape versus a completely furnished theory.
EL: Yeah, well, I know, when I was in college, I liked my math classes, but I didn't understand that math was still this active area of research. I was very naive about that kind of thing, and even now, you know, you've run into people who don't know what math research means. It's like, well, we know how to add and multiply numbers. We know how to do all of these things. Like, what else can there be to know? and this is something that doesn't take as much — you know, it's one of those examples that you can give.
CB: Right.
EL: You know, it has a lower, or, you know, a more basic way that you can enter this and like, understand, Oh, we're still trying to figure out this kind of thing. And so, I like that.
KK: Yeah.
CB: Also another thing I like, it's a bit upsetting that this is not decidable. I like those sorts of results. Actually, my account in Twitter has been referred to “the account that posts cursed math facts.” A lot of people say that, and that was not my intention, but it kind of fits with that.
EL: Yeah, well, that's very true because yeah, when I first saw it, I was just like, well, how can we not just, you know, just try all the ways to multiply it. At least in theory, you could do that, but not if it's arbitrarily long.
CB: Yeah.
EL: You're allowed to have as many as you like. Okay, if it was just one copy of each one, well, that's trivial. I mean, not trivial to actually do it, but it's trivial to know how to do it. But it's kind of funny that once you allow yourself multiple copies, it's just like, everything goes out the window.
CB: Yeah.
KK: All right. So you've already plugged your your popular Twitter account. We like to give our guests a chance to let us know where we might I find you online or anything else you're you're you're trying to promote or anything like that. It’s okay if you don’t.
CB: There’s my account. It’s called some theorems. So I think I can just put that in Twitter.
KK: Well for now.
CB: Yeah. I think I won’t add more to that.
KK: Okay. Well, Cihan, this has been great.
EL: Thanks so much for joining us.
CB: Yeah. Thank you for having me.
[outro]

On this episode, we were excited to talk with Cihan Bahran about the undecidability of the matrix mortality problem. Here are some related links you might enjoy:
Bahran's website and Twitter account, where he posts "cursed math facts"
The 2014 paper establishing the undecidability of the matrix mortality problem for, among other cases, six 3 × 3 matrices
The word problem in group theory

We recorded this episode before the devastating earthquake in Turkey and Syria. Our hearts go out to all who have been affected. If you would like to contribute to relief efforts, Doctors Without Bordersand Ahbap Derneği are two organizations doing work in the area.