Episode 66 - Érika Roldán

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. I am 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, Evelyn?
EL: I’m all right. It's been raining a little here, which is very good, because we are in a perhaps somewhat historic drought and every bit of moisture we can get is fantastic. Probably not very close to your experience in Florida right now.
KK: It’s been pretty dry. But yeah, it's not really an issue for us. I mean, it’s actually really lovely right now, and I'm looking forward to kayaking some this week.
EL: Oh, fun.
KK: And my son graduates college in two weeks. And yeah, all kinds of fun stuff on the horizon for us. So anyway, let's talk math, though.
EL: That is exciting. Yes. We are very happy today to have Érika Roldan joining us. So yes, Érika, would you like to introduce yourself?
Érika Roldán: Yeah, thank you. Thank you very much for the invitation. I'm super happy to be here. And, well, I'm a postdoc right now. I finished my PhD thesis in 2018. And then I started jumping here and there, from Mexico to the states and now Europe. I’m at Munich, Technical University of Munich, and École polytechnique fédérale de Lausanne in Switzerland is my co-host. And yeah, I have this fellowship, the Marie Curie fellowship, for 11 more months, and then jumping again. Yes.
EL: Yeah. Well, that's very exciting. And what is your field of research?
ÉR: Well, it's stochastic topology and topological and geometric data analysis. I think most of the time, most of the brain time, goes to that. But also, there is something that is related because it gives extremal examples — you will never see them typically when you're using kind of random processes — but these extremal examples allow is to contrast with random ones, so I also do extremal topological combinatorics a bit.
EL: Okay, and I also am familiar with some work that you've done in recreational mathematics, which I guess might have to do with this extremal combinatorics too. And so if I can self-promote and Érika-promote a little bit, a couple of the puzzles that Érika has worked on appeared in the mathematics-themed calendar that I put together a couple years ago, which is still available for purchase through the bookstore of the American Mathematical Society and which is not specific to a year, so you can still enjoy this calendar whatever year it is when you are listening to this episode. So anyway, yeah, you did a couple of fun puzzles. I don't know if you want to talk about any of those. I am actually blanking right now on there's one with like, polyomino things, right?
ÉR: Yes. So there are two. One of them actually has a very special place in my heart because it was my first paper, and I wrote it for the Gathering for Gardner, this meeting that is every two years in Atlanta. It is a wonderful meeting. It is the first mathematical community, research community, that I got in contact with. And yeah, I did a complete analysis and characterization of a type of puzzles with colored cubes, and you have to stack them, and you have to do a tower and have some interesting coloring properties. And the most famous one is called Instant Insanity, just to give you the name. The name has a little bit of a clue of how interesting it is to try to solve them by trial and error. And yeah, I guess I did some computations and everything to characterize all possible different kinds of puzzles like this. And, yes, that's one of the of the entries of the calendar, this this wonderful calendar. Thank you for sending it to me. I enjoy it very much. And yes, and the other one was about maximally many holes with polynomials.
EL: Yes, that’s right.
ÉR: And for sure, we're going to go back to polynomials. Because it's related with the story that I want to talk about today about my favorite theorem.
EL: Yes. And you've provided the perfect segue now. What is your favorite theorem?
ÉR: Yes. Well, first of all, I want to say that I was thinking, and I changed my mind different times during the past two weeks. And I decided that I wanted to talk today about my favorite theorem, choosing it in particular for my mother to be able to follow the podcast. So today's the 10th of May. And, yes, because of the corona crisis, I think a lot of people have not been able to travel, and I haven't seen my mother for more than, almost a year and a half. And this is a way of sending her all my love and appreciation. So my favorite theorem, okay, so one of the things that my mom used to do, or does still very, very well, is shuffling cards. So every time that we gather together with my grandma, and in Mexico, this is very common that you gather with your family very often. It doesn't matter what, you always want to be in a huge crowd, just eating and playing. And yeah, she's a very good shuffler of cards. And my favorite theorem is a theorem by Perci Diaconis, the theorem for today is by Persi Diaconis, where he proves, and actually there is like a set of different papers that have different ways of modeling this shuffling, the usual shuffling that we know, and they prove how many shuffles you need to do to be a sampling from a fairly uniform distribution from all possible ways of having 52 cards of a deck in a certain order.
KK: This is a very famous result, and it's a surprising number, you're gonna tell us the number, right?
ÉR: Actually, it depends. It depends on the distribution that we use. And then this depends on the algorithm. And but yes, it's a very famous theorem. And it's very well-appreciated by by mathemagicians. Persi Diaconis is one of the most well-known mathemagicians.
KK: I have to say, I'm not surprised this is your favorite theorems. I've been at various TDA [topological data analysis] conferences with you. And topologists like to play fast and loose with distributions, and you are always quizzing us about which distribution we're trying to use. It's always “Wait a minute, wait a minute, what's the distribution?”
EL: So,
KK: Go ahead, Evelyn.
EL: Yeah. Um, so for someone who has not thought about card shuffling a whole lot, what do you mean by different distributions?
ÉR: So let me withdraw the word “distributions” for the first part.
EL: Okay.
ÉR: So you want to play poker or any other game, and you want to shuffle the cards in such a way that you feel comfortable betting $100. So, I have the deck of cards. And let's say that I decide to shuffle like this: I take the uppermost card, I take it, and then I put it in one of the possible positions that is not on top, or could be on top actually. And I choose where to put it uniformly randomly. That means I select one of the possible 51 spots, 52 spots, and I put it there. And let's say that I do this five times. Question for both of you: Will you bet $100 with me in this poker game?
KK: Uh, no.
EL: Probably not.
KK: It doesn’t feel very well-shuffled.
ÉR: Exactly. And I think no one will do it. Like, it doesn't matter if you know or not probability. We have a sense of when things are shuffled, even if we haven't heard the word “probability.” And so, let me just tell you that actually, for doing this, if I do this 10 minutes, you will start getting more and more comfortable, right?
EL: Yeah.
ÉR: At some point, you can say, “Okay, let's play.” That's enough after an hour, right? And the solution, or roughly the number from starting from which you feel comfortable and theoretically can be proven that is the kind of right stopping time, is around 200 shuffles.
EL: So this is not a very efficient way to shuffle, in case that wasn't already clear to everyone. One card at a time. Not so good.
ÉR: Yeah, well, in a Mexican family it will be okay, because everyone will be talking everything. No one will get, just, bored. But perhaps if you are there just for playing, it's not the right way to go. Now, in general, I want to say here, the right rate. In general, if you have n cards, with this shuffling you have to wait nlogn time. So n times logn is the rate that with this kind of shuffle will give you a uniform distribution as a convergence, and when you start to feeling that yeah, it is uniformly sampled. Now let's compare these to the actual way that my mom shuffles the cards. And this is commonly referred to as a riffle shuffle. So you take the deck of cards, and then you kind of try to cut it in into two packs, half perhaps. And then what you do is you hold each one of the packets with each one of your hands. And then you make — I’m trying to generate a mental image that everyone knows — and then you start with your hands, like, trying to put one after the other one, alternating from the packets from one and the other one. And there are different things to do here to convince you that this is for sure a different way of shuffling than the first one. That is one thing, and the other thing is, so if I do it one time, perhaps you will not be very happy. But whenever we're playing with friends usually is what? Five times, six times.
EL: Yeah.
KK: It depends on how many times I drop them. You know, when you do it, you do it the down and then you do that little flip where you reverse the cards to get that little “shhhh” sound. It took me for—I was an adult before I could finally ever do that. But then a few cards always go flying, right?
ÉR: And this is one of the things that I love seeing my mom doing because I think she has some secrets that she doesn't tell us because she does it so well. Like amazingly well.
KK: My mom was good at that too, actually. That's interesting. Okay.
ÉR: We have these two different ways of shuffling. And we we kind of feel that, or we're comfortable with saying a riffle shuffle shuffles faster than the other way. And so now I want to use to use this shuffling perspective to go and shuffle other mathematical structures. Because what happens is that I ended up using this way of shuffling objects, or mathematical entities, in my research. And that was a very pleasant outcome of my PhD thesis. Yeah.
EL: So you're saying that like with these polyominoes with holes and stuff, there's some way to think about shuffling polyominoes, or do you shuffle entire configurations of them?
ÉR: Yes, exactly. Yes. It's super fun. So okay, let me start with Tetris.
EL: Okay.
ÉR: I think if we start with Tetris, everyone who's listening to us will go directly to the picture, the image of what is a polyomino.
EL: Oh, that's right. Yeah, we didn't actually say what a polyomino is. So in Tetris, you know that each picture is made up of four blocks. And so that's a tetromino is. So it's like a polyomino, I guess, is something that's made up of any number of these blocks.
ÉR: Yes, yes. Exactly. So. I think my, my favorite definition of a polyomino was the first mathematical definition given by Solomon Golomb when he was a PhD student. He gave a talk, and he said, well, a polyomino is a rook-wise, connected subset of squares of the infinite checkerboard.
EL: Okay.
KK: Rook-wise.
ÉR: So you can imagine you select a finite number of squares, and then you place a rook in any one of the squares, and you have to be able, with only rows and column moves, to go and visit any other square of the structure. So rook-wise connected.
EL: Yup.
ÉR: Yeah. And with Tetris, what happens is that we — let's now come back to to the mindset of sampling. And when we're playing Tetris, there is some entity that is giving us one polyomino after another one. Question: I don't know if people have thought about this. But it's a fun thing to do. I did one morning, and I was like, “I don't know.” Yes. So how is this done? How does the game decide how to give you the next polyomino?
KK: It’s not just random?
EL: Yeah, I guess I assumed it was — there was a however many Tetris pieces there are. I actually can't think off the top of my head, but six or seven, maybe different pieces?
ÉR: Seven.
EL: Okay, then just so a 1/7 chance of each one, is that not the case?
ÉR: Well, you soon will be able to play the game that you're describing, because I'm programming a version with uniform distribution, just to make people really mad and upset.
EL: Okay.
KK: I can see, actually, now that I think about it, if it were just random, uniform, that would be bad. You’d lose pretty quickly, right? I mean, now that I think about it, often you'll get that long, the straight four in a row right when you need it, right? And and if it were uniform, you wouldn't necessarily expect that to happen.
ÉR: It could, you could have bad luck. Yeah. You could have had as long as you want bad luck.
KK: Right? Sure. That's right.
ÉR: Right. So the algorithm is very interesting. What they do is, they take the seven, the possible seven polyominoes with four squares that they give, and then they shuffle these seven in a way that you have a one over seven factorial, each one of the possibilities of the order has one over seven factorial, that means it’s a uniformly distributed sample. Okay, so what what can happen? Well, the worst that you can wait for that “I” shape is that if you have at the beginning of a set of seven, and then in the next set of seven, you have it at the end. That’s the worst that can happen in terms of these wonderful pieces that allow you to kill four rows.
KK: Interesting. Okay, so they're just choosing a random shuffle. Oh, wow. Well, that is better.
ÉR: It is for playing.
EL: I guess with, like, computer games like this. We, as you're saying earlier, Kevin, we don't actually want it completely random because we don't want to get, you know, five squares in a row or something like this, which can definitely happen when you play it randomly. Especially when you're me and my brother when we were, like seven and nine years old, always going in and playing for two hours to try to erase the other ones’ high scores.
KK: I still remember, so when I was in graduate school, I had a Nintendo Gameboy. My mother gave me one of these, and I played Tetris. And I can still hear that song. The music that went along with it, and I would go to sleep at night picturing these damn pieces just falling. I can hear this song over and over and over my head.
ÉR: That is a thing I think that happened when we were doing a PhD because I was always with my Nintendo playing Tetris and procrastinating, beautifully procrastinating. And it turns out.
EL: I have a question. How do you — like, did you find how Tetris is programmed? Or did you just do some — Like, how did you figure out that this is how Tetris works?
KK: Yeah.
ÉR: Well, so I started reading about it. But first of all, I started playing, and I started noticing this pattern, right? This pattern, because you never see — I think, I think what what tells you immediately that it cannot be a random distribution, uniform random period, is that you will never see three times the the same shape.
EL: Okay, you could see two in a row, if it happened, right at the end and then the beginning, but you can't see three in a row.
ÉR: You can’t see three in a row! So this is one of the immediate signs. So whenever you don't see three in a row, and you have a decently small set — and we're going to go back on the size of the set, because it plays a role. So it plays a role, the distribution that you have in the set, and it plays a role also the size of the set. And so in this case, because it's such a small set, not seeing three in a row is like, uh-uh, something fishy is happening here. This cannot be the uniform distribution, period. Yes.
EL: Okay.
ÉR: Yeah, and this is with four squares. And now imagine that we three get a very nice contract by a company that tells us, I want you to build a very nice Tetris, but it has to be for any number of tiles. And then we start discussing, okay, so let's see, one of the things that we need to do is to extend, or just to apply perhaps this algorithm, but it has to work for any n, any number of squares, let's say 57 squares, right? So, first step, go and find all polyforms with 57 squares.
KK: That’s a lot.
EL: Yeah.
ÉR: That’s a lot. Yes. And I kind of, yeah, I kind of, in purpose, choose 57. Because 57 is the first amount of squares that we as humans, don't know how many polyominoes there are with 57 squares.
EL: Okay.
KK: All right.
EL: It’s just too too many for for us to have sorted them out somehow.
ÉR: It’s too many for the patience that people and computers and computer time have. Like, 56, I think was two years.
EL: Wow.
KK: So there's some algorithm but it is not super-efficient.
EL: It hasn't stopped yet.
ÉR: It’s a little bit worse. Because even even if we wanted to say, Okay, let's cut at 56 because we know how many there are, or up to 56 and we deliver the game like this, right? So the problem is that this algorithm can count them. But this algorithm cannot really store the pieces or actually look at them, which is something that is possible to do. This is one of the magics of mathematics and computer science, that we can say something about something that we cannot see. And then we know up to 28 tiles, Tomás Oliveira e Silva in in 2015, was able to look at them and, for example, say the symmetries that they have because it's unknown, really, how many of them are going to have which kind of symmetries and so on and so forth, all the geometric and topological properties that you can have with polyominoes. And yes, so I guess we have to talk to the manager and say to the manager, we have a problem here. I don't think we can create Tetris for any amount of tiles.
EL: Yeah. Plus, I mean, it would be — I bet a lot of these tiles, as they get more pieces in them, have holes in the middle that you can just never plug. Because you can you can have rook-wise moves that will sort of surround this hole. Which I am thinking of because of your puzzle from the calendar. So I guess, do you happen to know like, at what size Tetris stops being fun?
KK: Eight.
ÉR: There is the answer. Well, with eight, perhaps not yet. Because almost all of them will not have holes.
KK: Right. But you’re still going to get that one with a hole every once in a while. And then you're done. Well, not yet. But it's, it's gonna cause problems.
ÉR: Super difficult.
EL: Yeah.
ÉR: Yes. And that is a very, very good observation, because actually, one of the things that is a mathematical truth is that most polyominoes have holds.
KK: Sure.
EL: Okay.
ÉR: Meaning with probability one, as n goes to infinity, if you take a polynomial at random, it will have most likely a linear amount of holes with respect to the number of tiles.
KK: Okay.
ÉR: And this is one of the topics that I started studying in my PhD, is how does the number of holes grow with respect to the number of tiles? And because we're asking a question upon a set that we don't know how many there are, and we don't know how to actually look at all of them. Right?
EL: Yeah.
ÉR: So the only way that we can say something is, for example, to have actual numbers, is sample. Sample and tell me. Sample them. Yeah, but we have another problem. How do you sample from a set that you don’t know?
EL: Yeah, that doesn't seem easy.
ÉR: Yeah. And that is huge. That is humongous. Because it’s — the number of polyforms is growing exponentially fast with respect to the number of tiles.
KK: Right? That's what I was going to say. I mean, even, you know, if you're up to, like, 10, the number is probably so large that you can't construct a reasonable game out of it, right? Yeah. So I mean, so Tetris is — so I have this game with blocks called Katamino, where they’re pentominoes, right? And that's fun, and challenging enough. Yeah. Okay. So now I understand why you're interested in stochastic topology, this feels very, if you're looking for holes in these things, you've set up some rules. And now the question is when do the Betti numbers change and things like that.
ÉR: Yes, yes. And now that you mention polyominoes, I also like like putting here and there one puzzle, so that people, perhaps even build it in their homes or something. So when Matthew Kahle was in Mexico visiting for my candidacy exam, we exchanged puzzles, and one of the puzzles that we exchanged is you take an eight by eight, a chess board, a usual eight by eight chess board. And then you have and then you break it on the head — no. And then the story in Diedonne’s book, it goes like this, that there were two royal persons playing chessboard, one loses, and then breaks the chessboard on the head of the other one, and then you get pieces. And these pieces are the 12 pieces that you were referring to, Kevin, the pentominoes, plus the two by two square. And then one of my favorite puzzles, and now so because Matt did this, built this puzzle with bamboo, with a very, very thin bamboo material, and he gave it to me as an exchange of the puzzles that we had. We actually had a night of puzzles and games back there.
KK: That’s fun.
ÉR: A lot of polynomials in my mathematical life.
KK: Very cool.
EL: Yeah. So, another thing we like to do on this podcast is asks our mathematicians to pair their theorem or example or their mathematics with something else. And so, what would you like to pair with this theorem about shuffles? And it may be even with the applications to all of these polyomino puzzles.
ÉR: I will say that is drawing and 3D modeling.
EL: Okay.
ÉR: One of the things that I like is to run these run some of these algorithms for generating poly-cubes in 3D, and different algorithms. And then to get these 3D crazy structures, and I like doing the modeling. So I guess, is the is a way of I, I think, it’s random art?
KK: Sure. Sure.
EL: And what programs do you use to actually draw those? ÉR: Oh, well, here, and this is one of the things that I have been really into it ,is there is a program called Maya. And it’s for doing 3D modeling and rendering. But it can be combined with Python.
KK: Okay.
EL: Okay. So do some other math with it, and then put it into Maya?
ÉR: Yes. And so I found someone to give me some classes on Maya. And then this person was always like, “But how do you manage to do 1000 cubes and decide where to put them?” And no, like, I just click and play, and I have an algorithm that decides to go all the way to 1000. So I guess it was a very interesting combination, knowing the kind of fast-track things that we do as mathematicians, and then mixing that with art. I like digital art. Yes.
EL: Nice.
KK: Very cool. Okay, so so we also like to give our guests a chance to plug anything, or where can we find you on the internet, or anything else you want to tell us let people know.
EL: Yeah, if people want to play anything that you made, or where they can find this frustrating Tetris game that you'll be coding once you make it.
ÉR: Yes. That is going to be available very soon. But also, because I’ve been developing these apps with a computer science collaborator, and one of the apps that I have, and that I will provide a link for people to play, is for finding polyforms formed by squares and triangles. So you can also play this in the infinite the triangle tessellation of the plane, or you can play this with any tessellation. You could play it even in hyperbolic spaces, you could play it in higher-dimensional spaces, but the app that I’m going to share stays with the square and the triangular grid. So, you will be able to find polyforms with maximally many holes and it will tell you if you are actually reaching the maximum number of holes that you can for that amount of tiles, so it has that property. And I guess another another random way that I have for for producing these random polygons is like a cell growth model. And what you do is you start with a cell, and then you add uniformly random one of the cells that are neighboring, so you can imagine this is a cell colony growing. And there is a huge area of research called first passage percolation that has been analyzing these kind of models. But what I do is I study the topology of this other way of randomly generating polyforms. And I have an app that I will also provide here so that people can think about it and perhaps come up with some conjectures that later, they can see in one of my papers with Benjamin Schweinhart and Fedor Manin.
EL: Okay, great.
KK: That’s fun.
EL: So, you’ll get homework after this episode, but it's not a quiz. So it's still okay.
KK: All right. Well, this has been a lot of fun, Érika. I always like to hear about these sorts of questions, even though I'm no good at them. I always like to talk to people who are good at counting and these kinds of things. So it's been it's been great fun talking to you. Thanks for joining us.
ÉR: Yeah. Thank you so much for the invitation. And yes, looking forward for seeing you in the USA soon.
EL: Yes. Bye.
ÉR: Bye.
[outro]

On this episode of My Favorite Theorem, we had the pleasure of talking with Érika Roldán, a Marie Curie fellow at Technical University Munich and École Polytechnique Fédérale de Lausanne, about shuffling cards and Tetris pieces.

To read about the mathematics of riffle shuffles, this article by Persi Diaconis is a good place to start. To get a copy of the American Mathematical Society page-a-day calendar, click here. (If you already have a calendar, check out Dr. Roldan's puzzles on August 28 and October 12.)

Dr. Roldán shared some other links to and explanations of some of the apps and videos she mentioned in the episode:

The COVID crisis has allowed me to start developing digital material for my research, teaching, and outreach on mathematics and its applications. It has also allowed me to collaborate as a developer of digital material (in Germany) with artists whose projects promote gender equality, and diversity & inclusiveness awareness. Here, I share some of the links to explore this digital playground (new digital material created will be posted soonish at my website: http://www.erikaroldan.net/):
1) https://000612693.deployed.codepen.website
Follow the link above to find Extremal Animals, that is, polyforms with maximally many holes. A polyform is built by gluing together squares or triangles (in the case of this app) by their edges. And a hole in a polyform (that mathematicians call the first Betti number in this 2D case) is a finite connected component of the complement of the polyform. To get some intuition, just build a polyform with squares with 7 tiles and one hole, or a polyiamond with 9 triangles and one hole. Could you create one hole with less tiles in any of these two cases?
Have a look at these papers for the maths behind this (Extremal Topological Combinatorics) puzzle of finding polyforms with maximally many holes:
https://arxiv.org/pdf/1807.10231.pdf
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i2p56/pdf
https://arxiv.org/abs/1906.08447v1
2) https://000612976.deployed.codepen.website
Here a link to an app that has a model to generate a random polyform by a cell growth process called The Eden Model. Pay attention to how the holes are created and destroyed as time (the number of tiles) evolves. Do you have any conjectures about how the number of holes is changing concerning time? Have a look at this link to see if your conjectures are stated and/or proved in this paper:
https://arxiv.org/abs/2005.12349
3) My first proto-game with Unity was developed for the Film “Broken Brecht” directed and produced by Caroline Kapp and Manon Haase, for the Brechtfestival Augsburg, Germany (Mar 2021). This is a project that will be extended during 2021! Here some links to the festival, the proto-game, and an extract from the film that happens within the proto-game.
Brecht Festival
https://brechtfestival.de/brokenbrecht/
Extract from Broken Brecht
https://vimeo.com/542287814
Link to the 3 min Archive Video Game
https://simmer.io/@ErikaRoldanRoa/~56f30f68-048c-c027-7aa0-aeaca82508fc
4) Some 3D models created with Python & Maya to explore (random) cubical complexes.
https://sketchfab.com/erikaroldan