<input onclick="this.value=this.value=='Episode Transcript (click to expand)'?'Hide Transcript':'Episode Transcript (click to expand)';" type="button" class="spoilerbutton" value="Episode Transcript (click to expand)">

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 proble