Episode 47 - Judy Walker

My Favorite Theorem

Kevin Knudson: Welcome to My Favorite Theorem, a podcast about mathematics and all kinds of crazy stuff, and I have no idea what it's going to be today. It is a tale of two very different weather formats today. So I am Kevin Knudson, professor of mathematics at the University of Florida. Here's your other host.
Evelyn Lamb: Hi, I'm Evelyn Lamb. I'm a math and science writer in Salt Lake City, Utah, where I am using the heater on May 28.
KK: Yes, and it's 100 degrees in Gainesville today, and I'm miserable. So this is bad news. Anyway, so today, we are pleased to welcome Judy Walker. Judy, why don't you introduce yourself?
Judy Walker: Hello. Thank you for having me. I'm Judy Walker. I'm a professor of mathematics at the University of Nebraska.
KK: And what else? You're like—
JW: And I am Associate Vice Chancellor for faculty and academic affairs, so that’s, like, Vice Provost for faculty.
KK: That sounds—
EL: Yeah, that does sound very official!
JW: It does sound very official, doesn't it?
KK: That’s right. Like you're weighing T & P decisions in your hands. It's like, you're like Caesar, right? With the thumbs up and the—
JW: I have no official power whatsoever.
KK: Right.
JW: So yes.
KK: But, well, your power is to make sure procedures get followed, right?
JW: Yes. And I have a lot of I have a lot of influence on other things.
KK: Yeah. Right. Yeah. That sounds like a very challenging job.
JW: And for what it's worth, I will add that it is cloudy and windy today. But I think we're supposed to be, like, 67 degrees. So right in the middle.
KK: All right. Great.
EL: Okay, perfect.
KK: So if we could see the map of the US, there'd be these nice isoclines. And here we are. Right. So we're, my mine is very hot. Mine's red. So we're good. Anyway, we came to talk about math. You’re excited to talk about math for once, right?
JW: Exactly. I guess I'm kind of going to be talking about engineering, too. So—
EL: Great.
KK: That’s cool. We like it all here. So what's your favorite theorem?
JW: So my favorite theorem is the Tsfasman-Vladut-Zink theorem.
KK: Okay, that's a lot of words.
JW: It is—well, it’s a lot of names. It's three names. And it's a theorem that is in error-correcting codes, algebraic coding theory. And it's my favorite theorem, because it solves a problem, or maybe not solves a problem, but shows that something's possible that people didn't think necessarily was possible. And the way that it shows that it's possible is by using some pretty high-powered techniques from algebraic geometry, which had not previously been brought into the field at all.
EL: So what is the basic setting? Like what kind of codes can you correct with this theorem?
JW: Right. So the codes are what does the correcting. We don't correct the codes, we use the codes to correct. So I used to tell my — actually, my advisor told me and then I've told all my PhD students — that you have to have a sentence that you start everything with. And so my sentence is: whenever information is transmitted across a channel, errors are bound to occur. So that is the setting for coding theory. You've got information that you're transmitting. Maybe it's pictures from a satellite, or maybe it's just storing things on a computer, or whatever, but you're storing this information. Or you're transmitting this information, and then on the other end, or when you retrieve it, there's going to be some mistakes. And so it's the goal of coding theory to add redundancy in such a way that you can find those mistakes and fix them. Okay?
And we don't actually consider it an error if you fix the mistake. So an error is when so many mistakes happened in the transmission or in the storage and retrieval, that what you think was sent was not what was actually sent, if that makes sense.
KK: Sure. Okay.
JW: So that's the basic setting for coding theory, and coding theory kind of started in 1948 with Shannon's theorem.
KK: Right.
JW: So Shannon's theorem says that reliable communication is possible. So what it says really, is that whatever your channel is, whether it's transmitting satellite pictures, or storing data, or whatever—whatever your channel is, there is a kind of maximum efficiency that's possible on the channel. And so what Shannon’s theorem says is that for any efficiency up to that maximum, and for any epsilon greater than zero, you can find a code that is that efficient has less than epsilon probability of error, meaning the probability that what you sent is not what you think was sent at the end. Okay?
So that's Shannon's theorem. Right? So that's a great theorem.
EL: Yeah.
JW: It’s not my favorite theorem. It’s not my favorite theorem because it actually kind of bothers me.
KK: Why does it bother you?
JW: Yeah, so the reason that bothers me are — there are two reasons it bothers me. One is that it doesn't tell us how to find these codes. It says good codes exist, but it doesn't tell us how to find them, which is kind of useless if you're actually trying to transmit data in a reliable way. But it's actually even worse than that. It's a probabilistic proof. And so it doesn't just say that good codes exists, it says they're everywhere, but you can't find them. Right? So it's like it's taunting us. So I just—. So yeah. So that's Shannon's theorem. And that's why it's not my favorite theorem. But why it's a really great theorem is that it started this whole field. So the whole field of coding theory has been — or of channel coding, at least, which is what we've been talking about is to find those codes, and not just find them, but find them along with efficient decoding algorithms for them. And so that's Shannon's challenge is to find the good codes with efficient decoding algorithms for those good codes. That's 1948, that that started. Right? Okay.
So just as a digression, let me say that most mathematicians and engineers will agree that at this point in time — so a little more than 70 years after Shannon's theorem, that Shannon's challenge has been met, so that we can find these good codes. They're not going to agree on how it's been met. But they'll all agree that it has been met. So on the one hand, in the late ‘90s — mid-to-late 90s — engineers found turbo codes, and they rediscovered low-density parity check codes. And these are codes that in simulations come very, very close to meeting Shannon's challenge. The theory around these codes is still being developed. So the understanding of why they meet Shannon challenge is still try to be solved. But the engineers will say that it's solved, that Shannon's challenge is met because they've got these simulations, and they're so confident about it, that these codes are actually being used in practice now.
EL: So I have a naive question, which is, like, does the existence of us talking over the internet on on this call, sort of demonstrate that this has been met? Like we we are hearing each other — I mean, not with perfect fidelity, but we're able to transmit messages. Is that? Or is that just not even in the same realm?
JW: No, that's exactly exactly what we're talking about, exactly what we're talking about. And not only that, but I don't know if you've noticed, but every once in a while, Kevin gets a little glitchy, and he doesn't move for a while. That's the code catching up and fixing the errors.
KK: Yeah, that's the irony is this this call has been very glitchy for me.
JW: Right.
KK: Which is why we each record our own channel.
EL: Yeah.
JW: Exactly. So in fact, low-density parity-check codes and turbo codes are being used now in mobile phones, in satellite communications, in digital TV, and in Wi-Fi. So that's exactly what we're using.
EL: Okay.
JW: But the mathematicians will say, “Well, it's not really—we’re not really done. Because we don't know why. We don't really understand these things. We don't have all the theoretical underpinnings of what's going on.” A lot of work has been done a lot, and a lot of that is there. But it's still a work in progress. About 10 years ago, kind of on the flip side, polar codes were discovered. And polar codes are the first family of codes to provably achieve capacity. So they actually provably meet Shannon's challenge. But at this moment, they are unusable. There's just still a lot of work to understand how we can actually use polar codes. So the mathematicians say, “We've met the challenge, because we've got polar codes, but we can't use them.” And the engineers say, “We've met the challenge because we've got turbo codes and LDPC codes, but we don't know why.” Right? And that's an oversimplification, but that's kind of the current state. And so different people are working on different things now. And of course, there are other kinds of coding that that aren’t — that isn't really channel coding. There are still all kinds of unsolved problems. So if anybody tells you that coding theory is dead, tell them they're wrong.
EL: Okay!
JW: It’s still very much alive. Okay, so we talked about Shannon's theorem from 1948. And we talked about the current status of coding theory. And my favorite theorem, this Tsfasman-Vladut-Zink, is from 1982. So in the middle.
EL: Halfway in between.
JW: Yes, yes. Just like my weather being halfway in between. Yes. So around this time, in the early ‘80s, and and preceding that, the way that mathematicians were approaching Shannon's challenge was through the study of linear codes. So linear codes are just subspaces, and we might as well think of—in a lot of applications, the data is zeros and ones. But let's go to Fq instead of F2, so q is any prime power.
KK: Okay, so we're doing algebraic geometry now, right?
JW: We’re not yet. Right now, we’re just talking about finite fields.
KK: Okay.
JW: We will soon be be doing algebraic geometry, but not yet. Is that okay?
EL: You’re just trying to transmit some finite set of characters.
JW: Yes, some finite string of characters. Order matters, right? So it's a string. And so the way that we think about it, we can think about it as a systematic code. So the first k characters are information, and then we're adding on n−k redundancy characters that are computed based on the first k.
KK: Okay.
JW: So if we're in a linear setting, then this collection of code words that include the information and the redundancy, that collection of code words is a subspace, say it's a k-dimensional subspace, of Fqn. So that's a linear code. And we can think about that ratio, k/n, as a measure of how efficient the code is.
KK: Right.
JW: Because it's the number of information bits divided by the total number of bits, or symbols, or characters. So, let's call that ratio, R for rate, right? k/n, we’ll call it R. And then how many errors can the code correct? Well, if you look at that Hamming distance—so that's the number of characters and number of positions in which to code words differ—then the bigger that distance, the more errors you can make and still be closest to the code word that was sent. So then that's not really an error. Right? So maybe we say the number of mistakes goes up.
EL: Yeah. So again, let's normalize that minimum distance of the code by dividing by the length of the code. So we have a ratio, let's call that ∂. So that's our relative minimum distance for the code. So one way to phrase this is if we want a certain error-correcting capability, so a certain ∂, how efficient can the code be? How big can R be? Okay, so there are a lot of bounds relating R and ∂, our information rate and our error-correcting capability, or our relative minimum distance. So one that I want I tell you about is that Gilbert-Varshamov bound.
So the Gilbert-Varshamov bound is from 1952. And it says that there's a sequence of codes, or a family of codes if you want, of increasing length, increasing dimension, increasing minimum distance, so that the rate converges to R and the minimum distance to converges to ∂. And R is at least 1−Hq(∂), where Hq is this entropy function. So you may have heard of the binary entropy function, there's a q-ary entropy function, that's what Hq(∂) is. So one such sequence is the so-called classical Goppa codes, and I want to say that that's from, 1956, so just a little bit later. And those codes were the best-known codes from this point of view for about 30 years. Okay, so let me just say that again. So the Gilbert-Varshamov bounds says that there's a sequence of codes with R at least 1−Hq(∂). The Goppa codes satisfy r=1−Hq(∂). And for 30 years, we couldn't find any codes with R greater than.
EL: That were better than that.
JW: Right. That were greater than this 1−Hq(∂).
KK: Okay.
JW: So people at this point were starting to think that maybe the Gilbert-Varshamov bound wasn't a bound as much as it was the true value of how good can R be given ∂, how efficient can codes be given given their relative minimum distance. So this is where this Tsfasman-Vladut-Zink theorem comes in. So in 1978—and Kevin, now we can talk about algebraic geometry. I know you’ve been waiting for that.
KK: All right, awesome.
JW: Yes. Right. So in 1978, Goppa defined algebraic geometry codes. So the way that definition works: remember, a code is just a subspace of Fqn, right? So how are we going to get a set of space of Fqn? Well, what we're going to do is we're going to take a curve defined over Fq that has a lot of rational points, Fq-rational points, right? So we're going to take one of those points and take a multiple of it and call that our divisor on the curve. And then we're going to take the rest of them. And we're going to take the rational functions in this space L(D). D is our divisor, right? So these are the functions that only have poles at this chosen point of multiplicity, at most the degree that we've chosen.
KK: Okay.
JW: And we're going to evaluate all those functions at all the rest of those points. So remember, those functions form a vector space, and evaluation is a linear map. So what we get out is a vector space. So that's our code. And if we make some assumptions, so if we assume that that degree of that divisor, so that multiplicity that we've chosen, is at least twice the genus minus 2, twice the genus of the curve minus 2, then Riemann-Roch kicks in, and we can compute the dimension of L(D). But if we also assume that that degree is less than the number of points that we're evaluating at, then the map is injective. And so we have exactly what the dimension of the code is. The dimension of the code is the degree of the divisor, so that multiplicity that we chose, plus 1 minus the genus. And the minimum distance, it turns out, is at least n minus the degree of the divisor. So lots of symbols, lots of everything.
EL Yeah, trying to hold this all in my mind, without you writing it on the board for me!
JW: I know, I’m sorry. But when you put it all together, and you normalize out by dividing by the length, what you get is that if you have a family of curves with increasing genus, and an increasing number of rational points, then we can end up with a family of codes, so that in the limit, R, our information rate, is at least 1−∂—that’s that relative minimum distance—minus the limit of the genus divided by the number of rational points. Okay. So g [the genus] and n are both growing. And so what's that limit? So that's that was Goppa’s contribution. I mean, not his only contribution. But that's the contribution of Goppa I want to talk about, just that definition of algebraic geometry code. So it's a pretty cool definition. It’s a pretty cool construction. It’s kind of brand new in the sense that nobody was using algebraic geometry in this very engineering-motivated piece of mathematics.
EL: Right.
JW: So here is algebraic geometry, here is a way of defining codes, and the question is, are they any good? And it really depends on what—how fast can the number of points grow, given how fast the genus is growing? So what Drinfeld and Vladut proved—so this is not the TVZ theorem, not my favorite theorem, but one more theorem to get there—Drinfeld and Vladut proved that if you take, if you define Nq(g) to be the maximum number of Fq-rational points on any curve over Fq of genus g, then as you let g go to go to infinity, and for a fixed q, the limit superior, the lim sup, of the ratio g/Nq(g), is at most 1/√(q−1). Okay, fine. Why do we care? Well, the reason we care is that the Tsfasman-Vladut-Zink theorem, which is again my favorite theorem, it says—so actually, my favorite theorem is a corollary of the Tsfasman-Vladut-Zink theorem. So the Tsfasman-Vladut-Zink theorem says that if q is a square prime power, then there's a sequence of curves over Fq of increasing genus that meets the Drinfeld-Vladut bound.
EL: Okay.
JW: Okay, so the Drinfeld-Vladut bound said you can be at most this good. And Tsfasman-Vladut-Zink says, hey, you can do that.
EL: Yeah, it's sharp.
JW: So if we put it all together, then the Gilbert-Varshamov bound gave us this curve, right? So it was a concave-up curve that intersects the vertical axis, which is the R-axis, at 1 and the horizontal axis, which is the ∂-axis, at 1−1/q. So it's this concave-up thing that's just kind of curving out. Then the Tsfasman-Vladut-Zink line—the theorem gives you a line that looks like R=1−∂−1/√(q−1). Right? So it's just a line of slope −1, right, with y-intercept 1−1/√(q−1). So the question is, does that line intersect that curve? And it turns out that if you have q, a square prime power q at least 49, then the line intersects the curve in two points.
EL: Okay.
JW: So what that is really doing for us is it's telling us that in that interval between those two points, we have an improvement on the Gilbert-Varshamov bound. We have better codes than we thought were possible for 30 years.
EL: Wow!
JW: Yes. So that's my, that's my favorite theorem.
KK: I learned a lot.
EL: And where did you first encounter this theorem?
JW: In graduate school? Okay, in graduate school, which was not in 1982. It was substantially after that, but it was said to me by my advisor, “I think there's a connection between algebraic geometry and coding theory, go learn about that.”
KK: Oh.
JW: And I said, “Okay.”
KK: And so two years later.
JW: Right. Right, right. Actually, two years later, I graduated.
KK: Okay. All right. So you’re much faster than I am.
JW: Well, there was four years before that of doing other things.
EL: So was it kind of love at first sight theorem?
JW: Very much so. Because I mean, it's just so beautiful, right? Because here's this problem that nobody knew how to solve, or maybe everybody thought was solved. Because nobody had any techniques that could get any better than the Gilbert-Varshamov bound. And then here's this idea, just way out of left field saying, hey, let's use algebraic geometry to find some codes. And then, hey, let's look at curves with many points. And hey, that ends up giving us better codes than we thought were possible. It's really, really pretty. Right? It's why mathematicians are better than electrical engineers.
EL: Ooh, shots fired!
JW: Gauntlet thrown. I know.
EL: But it does make you wonder how many other things in math will eventually find something like this, like, will will find for these problems—you know, factoring integers or things like this— that we think are difficult, will someone swoop in with some completely new thing and throw it on its head?
JW: Yes. Exactly. I mean, I don't know anything about it. Maybe you do. But the idea that algebraic topology, right, is useful in big data.
KK: Yeah, sure. That's what I've been working on lately. Yeah. Right.
JW: I love that.
KK: Yeah. Sure.
JW: I love that. I don't know anything about it. But I love it.
KK: Well, the mantra is data has shape. Right? So let me just, you know, smack the statisticians here. So they want to put everything on a straight line, right? But a circle isn't a straight line. So what if your data’s a circle? So topology is very good at finding circles.
JW: Nice.
KK: Well, that's the mantra, at least. So yeah. All these unexpected connections really do come up. I mean, it's really—that’s part of why we keep doing what we're doing, right? I mean, we love it. But we never know what's out there. It's, you know, to boldly go where no one has gone before. Right?
JW: Exactly. And Evelyn, it's funny that you should bring up factoring integers, because you know that the form of cryptography that we use today to make it safe to use our credit cards on the internet, that’s very much at risk when quantum computers are developed.
EL: Right.
JW: And so, it turns out that algebraic geometry codes are not being used in practice, because LDPC codes and turbo codes are much more easily implementable. However, one of the very few known so far unbreakable methods for post-quantum cryptography is based on algebraic geometry codes.
KK: Excellent.
EL: Nice.
JW: So even if we can factor integers,
KK: I can still buy dog food at Amazon. Right?
JW: You can still shop at Amazon because of algebraic geometry codes.
EL: Yeah, the important things.
KK: That’s right.
EL: Well, so another thing we like to do on this podcast is invite our guests to pair their theorem with something, the way we would pair food with fine wines. So what have you chosen for this theorem?
JW: So that was very hard. Yeah. I mean, it's just kind of the most bizarre request.
EL: Yeah.
JW: So I mean, I guess the way that I think about this Tsfasman-Vladut-Zink theorem, I was looking for something that was just, you know, unexpected and exciting and beautiful. But I couldn't come up with anything. And so instead, what I'm going with is lemon zest.
KK: Okay.
EL: Okay.
JW: Which I guess can be unexpected and exciting in a dessert, but also because of the way that you just kind of scrape it off that curve of the lemon. And that's what the Tsfasman-Vladut-Zink theorem is doing, is it’s scraping off a little bit of that Gilbert-Varshamov curve.
KK: This is an excellent visual. I've got it. I zest lemons all the time. I understand now. This is it.
EL: Yeah.
JW: There you go.
KK: So all right. Well, we also like to give our guests a chance to plug anything. You wrote a book once. Is that still right? I have it on my shelf.
JW: Yeah. I did write a book once. So that book actually was—Yeah, so I wasn't going to plug anything, but I will plug the book a little bit, but more I'm going to plug a suite of programs. So the book is called, I think, Codes and Curves.
KK: That sounds right.
JW: You would think I would know that.
KK: I’d have to find it. But it is on my shelf.
JW: Yes. It's on mine too, surprisingly, which is right behind me, actually, if you have the video on.
So that book really just a grew out of lecture notes from lectures I gave at the program for women and mathematics at the Institute for Advanced Study. Okay, so I will take my opportunity to plug something to plug that program, to plug EDGE, to plug the Carleton program, and to plug the Smith post-bac program, and to plug the Nebraska conference for undergraduate women in mathematics. So what do all these programs have in common they have in common? They have in common two things that are closely related. One is that they are all programs for women in mathematics. And the other is that they were all the subject of study of a recent NSF grant that I had with Ami Radunskaya and Deanna Haunsperger and Ruth Haas that studied what are the most important or effective aspects of these programs and how can we scale them?
EL: Oh, nice.
JW: Yes. And some of the results of that study, along with a lot of other information, are on our website. That is women do math.org?
EL: I will be visting it as soon as we get off this phone call.
JW: Right. Awesome. I hope it's functioning
KK: And because Judy won't promote herself, I will say, you know, she's been a significant leader in promoting programs for women in mathematics through the University of Nebraska’s math department there. There's a picture of her shaking Bill Clinton's hand somewhere.
JW: Well, that's also on my shelf. Okay. Yeah, I think it's online somewhere, too.
KK: Right. Their program won a national excellence award from the President. Really excellent stuff there at the University of Nebraska. Really a model nationally.
EL: Yeah, I’m familiar with that as one of the best graduate math programs for women.
JW: Thank you.
EL: Yeah. Great job!
EL: Yeah, well, we'll have links to all of those programs on the website. So if you didn't catch one, and you're listening, you can to the website for the podcast and find all those. Yeah. Well, thank you so much for joining us, Judy.
JW: Thank you for the opportunity.
KK: Yeah, this has been great fun. Thanks.
JW: All right. Thank you.
On this episode, we were happy to talk with Judy Walker, who studies coding theory at the University of Nebraska. She told us about her favorite theorem, the Tsfasman-Vladut-Zink theorem. Here are some links to more information about topics we mentioned in the episode.

Goppa (algebraic geometry) code

Hamming distance

Gilbert-Varshamov bound

Judy Walker’s book Codes and Curves

The Program for Women and Mathematics at the Institute for Advanced Study

EDGE

The Carleton Summer Mathematics Program for women undergraduates

The Smith College post-baccalaureate program for women in math

The Nebraska Conference for Undergraduate Women in Mathematics (Evelyn will be speaking at the conference in 2020)

WomenDoMath.org