How Do Mathematicians Know Their Proofs Are Correct?

How can anyone speak with certainty about infinity? What can we really know about the mysterious prime numbers without knowing all of them? Just as scientists need data to assess their hypotheses, mathematicians need evidence to prove or disprove conjectures. But what counts as evidence in the intangible realm of number theory? In this episode, Steven Strogatz speaks with Melanie Matchett Wood, a professor of mathematics at Harvard University, to learn how probability and randomness can help establish evidence for the airtight arguments demanded of mathematicians..

Listen on Apple Podcasts, Spotify, Google Podcasts, Stitcher, TuneIn or your favorite podcasting app, or you can stream it from Quanta.

Transcript

Steven Strogatz (00:02): I’m Steve Strogatz, and this is The Joy of Why, a podcast from Quanta Magazine that takes you into some of the biggest unanswered questions in math and science today. In this episode, we’re going to be talking about evidence in mathematics. What kinds of evidence do mathematicians use? What leads them to suspect that something might be true, before they have a watertight proof?

(00:26) It might sound like a paradox, but it turns out that reasoning based on probability theory, the study of chance and randomness, can sometimes lead to what mathematicians are really after, which is certainty, not just probability. For example, in the branch of math known as number theory, there’s a long history of using randomness to help mathematicians guess what’s true. Now, probability is being used to help them prove what’s true.

(00:53) We’ll be focusing here on prime numbers. You probably remember prime numbers, right? You learned about them at school. A prime number is a whole number greater than 1 that can only be divided by 1 and itself. For instance, 7 or 11. Those are prime numbers, but 15 is not because 15 can be divided evenly by 3 or by 5. You could think of prime numbers as sort of like the elements in the periodic table of chemistry, in the sense that they are the indivisible atoms that make up all the other numbers.

(01:27) Prime numbers seem like they should be simple, but some of the biggest mysteries in math are questions about prime numbers. In some cases, questions that have been around for hundreds of years. There’s really something very subtle about primes. They seem to live in a borderland between order and randomness. My guest today will help us understand more about the nature of evidence in math, and especially how and why randomness can tell us so much about prime numbers, and why models based on probability can be so useful at the cutting edge of number theory. Joining me now to discuss all of this is Melanie Matchett Wood, professor of mathematics at Harvard University. Welcome, Melanie!

Melanie Matchett Wood (02:09): Hi, it’s good to talk to you.

Strogatz (02:11): It’s very good to talk to you, I’m a big fan. Let’s talk about math and science in relation to each other because the words often get used together, and yet the techniques that we use for coming to proof and certainty in mathematics are somewhat different than what we try to do in science. For instance, when we talk about gathering evidence in math, how is it the same or how is it different than gathering evidence by the scientific method in science?

Wood (02:38): A mathematical proof is an absolutely airtight, complete logical argument that some mathematical claim has to be that way and couldn’t be any other way. So unlike a scientific theory — which may be the best we have based on the evidence we have today, but we’ll get more evidence, you know, in the next 10 years and maybe there’ll be a new theory — a mathematical proof says that some statement has to be that way, we can’t possibly discover that it will be wrong in 10 years, or 20 years.

Strogatz (03:17): Well, what kinds of things do count as evidence in math?

Wood (03:19): So you might see that something is true in a lot of examples. And based on it being true in a lot of examples, which you could maybe say would be evidence for that fact, you might make a conjecture, what mathematicians would call a conjecture, a guess that something is true. But then, what mathematicians would want would be a proof that that thing that you saw worked out in so many examples would always work out the way that you claimed.

Strogatz (03:49): Right, very different from just the weight of the evidence. This is a statement that there’s a reason why something is going to be true forever, for all time, in every case.

Wood (03:58): And not just “oh well, I’ve looked at a million cases and it’s true in every single one of them.” Which is a reason to guess or conjecture that it’s always true. But in mathematics, we make a distinction between such a guess that could be based on a lot of cases or evidence, and having a theorem or a proof, an argument that tells you that it will work in every case, even the ones you haven’t tried.

Strogatz (04:25): Now, is it just that mathematicians are fastidious by nature, or are there cases where something that looked like it was true, up to some very large number of possibilities, ended up not being true beyond some other big number?

Wood (04:39): Oh, that’s, that’s a great question. Well, here’s an example I like, because I like the prime numbers. So as you go along through the prime numbers — 2, 3, 5, 7 — one of the things that you could do, you might look and say, “hey, are they divisible by 2?” And that turns out to be not very interesting. After 2, none of them are divisible by 2. They’re all, they’re all odd.

(05:10) And then you might think, “well, are they divisible by 3?” And of course, after 3, they can’t be divisible by 3 either, since they’re primes. However, you might notice that some of them, when you divide them by 3, you get a remainder of 1, that they’re 1 more than a multiple of 3. So things like 7, which is 1 more than 6, or 13, which is 1 more than 12. And some of those primes, like 11, or 17, which is 2 more than 15, they’ll have a remainder of 2 when you divide them by 3, because they’re 2 more than a multiple of 3.

(05:47) And so you could think of these primes in teams. Team 1 is all the ones that are 1 more than a multiple of 3 and Team 2 are all the ones that are 2 more than a multiple of 3. And as you go through the primes and you list the primes, you could list all the primes and you could tally up, and see how many are on Team 1, and how many are on Team 2. And if you did that tally up to 600 billion, at every point, every number up to 600 billion, you would find that there are more Team 2 primes than Team 1 primes. So, you might naturally conjecture, based on that evidence, that there will always be more Team 2 primes than Team 1 primes.

Strogatz (06:33): Sure. Totally sounds like it.

Wood: Turns out, at a number around 608-billion-something, I forget the exact number, it changes.

Strogatz (06:46): Oh, come on.

Wood: Yep, it really changes. And now all of a sudden, Team 1 is in the lead. So, that is a —

Strogatz (06:53): Wait a minute. Wait, but this is amazing. What — now, do they keep changing? Do we know what happens as you keep going? Do they keep changing?

Wood (07:01): Yeah, great question. So, indeed, it’s a theorem that they will change leads infinitely often.

Strogatz (07:07): Really?

Wood: So they will keep trading the leads. But it is a really great example to keep in the back of your mind when you’re studying prime numbers, that just because something was true for the first 600 billion cases doesn’t mean that it will always be true.

Strogatz (07:25): Oh, wow. Nice. Okay. So, like in general, how do you get from a conjecture to a proof?

Wood (07:31): It depends a lot on the case. I mean, there are many cases of mathematics where we have conjectures and we have no proofs. So there’s not some simple recipe to get from a conjecture to a proof, or we wouldn’t have so many famous open problems where, you know, there’s some — some conjecture that people think that something works a certain way, but we don’t know it for sure. But, you know, sometimes the conjecture might suggest reasons that something is true. Sometimes it’s just mathematical theory, that’s built upon more and more mathematical theory that people have been developing for hundreds of years, gives us enough tools and structure to work with to understand things that, that we come up with a proof. But it’s not that the conjecture necessarily leads to the proof. The conjecture might inspire people to try to find the proof, but the way the proof comes about may be entirely separate from, from the conjecture itself.

Strogatz (08:31): Yeah, I’m interested in kind of enumerating, or listing the kinds of evidence that fall short of a proof, that lead people to have the confidence that it’s worth trying to go for a proof.

Wood (08:41): Yeah, another thing we might call as evidence that isn’t just examples would be a heuristic. A heuristic might be something like an argument, except at a much lower standard of rigor. It’s just like, does that seem okay? Not “have I absolutely certainly established this fact beyond any shadow of a doubt?” but “does that — yeah, it seems pretty plausible.” So a heuristic might be a line of reasoning that seems pretty plausible, you know, but isn’t actually a rigorous argument. So that’s one kind of evidence.

(09:12) Sometimes one might have a model that we think captures the essential elements of the mathematical system we’re trying to understand, and so then you would conjecture that your system has the same behavior as your model.

Strogatz (09:30): Okay. At some point, I want to hear some examples of models and conjectures and, you know, to the extent to which they work or don’t work on some questions or not others, but, if you don’t mind, I’d like to go back just to a few little personal things, kind of, because we’re talking here about numbers, and you are a number theorist. People may not know many number theorists in their everyday lives. So, I wonder if you could tell us what is number theory, and also, why do you find it interesting? Why did you come to study it?

Wood (10:02) Well, number theory is the mathematical study of the whole numbers. So, think 1, 2, 3, 4, 5. And, in particular, one of the important things in the whole numbers are the prime numbers. As you explained, right at the very beginning, they’re the building blocks from which we can, through multiplication, build up all of the other numbers. So because number theory is concerned with all of those whole numbers, it’s also concerned with their building blocks, the prime numbers, and how other numbers factor into primes and how they’re built out — up out of primes.

Strogatz (10:37): So, number theory, for our purposes today, I guess, will be the study of the whole numbers, with a particular interest in prime numbers. That seems like a pretty good start. I suppose it’s more than that. But maybe that’s a good definition for us now. Do you think so?

Wood (10:50): That’s a good, that’s a good start. I mean, from there, one explores further things like, well, what if you start considering number systems that are more complicated than just the whole numbers? Like you start putting in other numbers, like the square root of 2, then what happens with primes and factorization? You get led to further questions. But honestly, there’s a lot of rich and beautiful mathematics just in the whole numbers and the primes.

Strogatz (11:16): So with that in mind then, why do you find it compelling? Why do you like the study of number theory? What drew you to it?

Wood (11:22): I think I like that the questions can be so concrete. You know, I go and talk to elementary school kids. And I can tell them about, you know, some of the things that — that I think about. So, it’s fun for me to work on something that on the one hand, the questions can be so concrete, but on the other hand, the puzzle of trying to solve it can be so difficult. I mean, people have been trying to answer questions about the whole numbers, about the primes for literally thousands of years.

(11:54) And there are a lot of branches of mathematics. One of the important parts of modern number theory is that to make progress on these stubborn old questions that people have been working on for so long, one needs to bring in new ideas, and needs to make connections with other parts of mathematics. So even though I would call myself a number theorist, I use mathematics from all different kinds of fields. From studying, you know, geometry and topology and the shapes of spaces to probability and studying randomness. I use all kinds of mathematics, but to try to say something about things like the whole numbers and prime numbers and factorization.

Strogatz (12:36): Yeah, I love that vision of math as this giant interconnected web of ideas, and you can want to live in a particular part of it that’s your favorite. But you’ve mentioned prime numbers as being a particular area of interest in number theory, the most fundamental part of it, really. What’s hard about them? It’s not clear yet, in our discussion, what’s so mysterious there? Like we’ve defined them, we could probably keep listing them, I suppose. What are some of those problems you’re referring to that are hundreds of years old?

Wood (13:05): Well, one of the biggest and most important questions, which is maybe about 120 years old or so, is, you said, “oh, you could list them. If you did that, how many would you find?” So let’s say you listed the primes, up to a hundred, or a thousand, or a hundred thousand, or a million, a billion. As you list primes up to larger and larger numbers, how many of those numbers that you go through will actually be prime? So understanding that quantity is really the heart of the Riemann hypothesis, which is one of the Clay Math Institute Millennium Prize Problems, there’s a million-dollar prize for an answer. It’s one of the most famous questions and we have no idea how to do it, and it really is just about the question of, when you list those primes, how many will you find?

Strogatz (13:58): Okay. It is funny, right? Because as you start making the list, even if someone just casually started listing the numbers that are prime up to 100 — you notice some funny things. Like, at first 11 and 13, they’re 2 apart. Fifteen, well, that doesn’t work, because it’s divisible by 5 and 3. Then 17, so there’s a gap of 4 now, between 13 and 17. But then 19 is close again. I don’t know, I mean, so the spacing between the primes can be kind of wonky. Like sometimes there’s a pretty big gap in there, and sometimes they’re right next to each other, just 2 apart.

Wood (14:31): Yeah, so understanding that spacing and those gaps has also been a big question of interest. There’s been remarkable progress in the last decade in understanding the spacing between the primes. But there’s still a really tantalizing, basic question that we don’t know the answer to. So you mentioned that these primes, 11 and 13, are just 2 apart. So such primes are called twin primes. We couldn’t expect primes to get any closer than 2 apart since after 2, they all have to be odd. Here is an open question in mathematics, meaning we don’t know the answer, and that’s: Are there infinitely many pairs of twin primes? And so here, there is a conjecture, the conjecture would be, yes. I mean, not only is there a conjecture that “yes, they should go on forever, and there should always be more of them,” but there’s even a conjecture about, sort of how many you’ll find as you go along. But that is completely open. As far as we know, it could be that once you get to a really big number, they just stop and you don’t find any more pairs of twin primes at all.

Strogatz (15:40): There’s something very poetic about that, poignant, that thought, like, that that could be the end of the line at some point. I mean, neither of us probably believe that. But it’s possible, I guess, it’s conceivable that there’s some last lonely pair of twins snuggling in the darkness, way out there, you know, on the number line.

Wood (15:57): Yeah, there could be. And, you know, as mathematicians, we would say, you know, we don’t know. Even if you could make a graph as you go along of how many you found, if you plot that graph, it looks like it’s just really definitely going up and up at a rate that would never — never turn around. But I guess that’s part of the difference between math and science is, we keep that skepticism and say, well, we don’t know. I mean, perhaps at some point, the graph just turns around, and there aren’t any more.

Strogatz (16:29): So, that — I like your image there of a graph, because I think everybody can relate to this idea, of making a chart, making some kind of graph. You know, thinking of the primes as kind of like data. And, and so I think this is maybe a good time for us to turn, to start talking about probability theory. And it seems a little weird to be talking about probability and statistics in connection with the primes because there’s no chance involved here. The primes are determined by the definition that we gave, that they’re not divisible. But yet mathematicians and number theorists, like you, have used statistical or probabilistic arguments in thinking about the primes. I wonder if you could sketch something like that for me using coin flipping, and back to the — what we were talking about at the beginning, odd numbers and even numbers.

Wood (17:14): Okay. So unlike the primes, we actually understand very well the pattern of odd and even numbers. They go odd, even, odd, even, of course. But suppose we didn’t understand that pattern. And we’re using this to understand how many odd numbers you might find if you looked at all the numbers up to a million. You could imagine, since there are two possibilities, a number could be odd or a number could be even, that maybe someone went along and flipped a coin for each number, and if the coin came up heads, the number was odd. And if the coin came up tails, the number was even. And so you could have your coin-flipping person sort of walking along the number line, flipping a coin at each number, and it comes up, say, to either declare that number odd or even.

(18:03) Now, on the one hand, that’s nonsense. On the other hand, the coin-flipping model will get some things right. For example, if you say, you know, roughly, how many of the numbers up to a million are even? We know that roughly the number of coin flips that will, say, come up tails, if you do a huge number of coin flips, like a million, is about half of them. And so, that model, as silly as it may be, still can make some predictions correctly. And I should say, that may sound silly, because we already know the answer to that question. The idea is that we build models for more complicated patterns, like where the primes appear among the numbers, instead of just where the odds appear.

Strogatz (18:55): Yeah. I mean, I think we need to underscore that — just how profoundly mysterious the primes are. There’s no formula for the prime numbers, the way there’s a formula for odd numbers. Like if you think, oh, come on, this is — we’re really talking about absurd stuff here, it’s actually very valuable to have these statistical models that can predict properties that are average properties. Like the analog of, half the numbers less than a big number are going to be odd. This is something that, in the case of primes, is a very serious, interesting question. What fraction of numbers less than a big number are prime? And, as you say, you can make a statistical model that gets that right. And then what, that same model can be used to then predict how many twin primes there would be less than a big number? Does the same model do a good job in that case?

Wood (19:41): So in the case of primes, if we were building a model — you know, and there’s a model mathematicians use called the Cramér model of the primes — if we were building a coin-flipping model of the primes where we imagine someone walking along the number line, and at each number, you know, flipping a coin, say, to decide if that number was prime or not prime, we would incorporate as much as we know about the primes into that model. So first of all, we know that big numbers are less likely to be prime than smaller numbers. So those coins would have to be weighted. And we’d — we’d have to try to put in precisely the weightings that we expect. And we know things like, you can’t have two primes next to one another, because one of them would have to be odd and one of them would have to be even. So we put that into the model. And then there’s more things we know about the primes.

(20:37) So the model is something that starts with this coin-flipping model, but then it’s modified by all these other rules, and all the other things that we know about the primes. And once you put all of those things that we do know into the model, you then ask this coin-flipping, you know, model, well, do you see, infinitely often, coins coming up prime just 2 apart? And the model tells you, oh, yes, we do see that. In fact, we see it at this very particular rate we can give you a formula for. And then, if you graph the number of actual twin primes, in the actual numbers, where there are no coins flipped, against what the model predicts, you see that the model gives you a very accurate prediction for the number of pairs of twin primes you’ll find as you go along. And so then you think, you know, maybe this model knows what it’s talking about.

Strogatz (21:31): That’s great. I mean, that’s kind of important, what we just got to there, that — you didn’t use the word computers yet. But I assume that you’re not doing this by hand. The people who are listing twin primes out to, I don’t know, what are we talking about? Trillion trillion trillion? I mean, these are big numbers we’re talking about, aren’t we?

Wood (21:49): Well, for the listing of the twin primes, that is — would be done by computer, absolutely. But for building this model and coming up with the formula that the model gives. You know, that’s done by hand, essentially, by mathematicians thinking about the model and figuring out with it.

Strogatz (22:07): That’s so cool. So that’s where the model is showing its stuff, that the model can actually predict what the computer sees. And it doesn’t require a computer to make that prediction. That can be done by hand, by people, and can actually lead to proofs. Except that it’s proofs of properties of the model, not necessarily yet proofs of the thing you’re interested in.

Wood (22:28): Right. And at some point, the computer stops. You know, there’s only so much computing power. But that formula that you would get, that the model would give you, that you could prove is true, again, about this model coin-flipping situation, that formula will keep going. You can put bigger and bigger numbers into that formula, much bigger than your computer could ever, ever compute with.

Strogatz (22:53): So you’ve been telling us a little about how randomness can help give models of interesting phenomena in number theory, and I’m sure it’s also true in other parts of math. Are there some cases where you can use randomness to provide actual proofs, not just models?

Wood (23:10): Absolutely. Another branch of mathematics is called probability theory. And in probability theory, they prove theorems about random systems and how they behave. And you might think that, well, if you start with, with something random, and you do something with it, you’ll always have something random. But one of the remarkably beautiful things that one finds in probability theory is that sometimes you can get something deterministic out of something random.

Strogatz (23:45): Well, how does that work? Like what?

Wood (23:48): Yeah. So you’ve seen the bell curve, or the normal distribution, mathematicians would call it. It appears all over the place in nature. Like it appears if you look at people’s blood pressures, or baby’s birth weights, or something. And you might think, oh, this bell curve, that this is a, it’s a fact of, of nature. But in fact, there’s a theorem, called the central limit theorem in probability theory, that tells you that actually, that this bell curve is in some sense, not a fact of nature, but a fact of mathematics. The central limit theorem tells you that if you combine a whole bunch of small random effects independently, that the output of that will always match a certain distribution. This shape, this bell curve. Mathematics, and the theory of probability, can prove that if you have — if you combine a lot of little independent random things, the outcome of all that combination will give you a distribution that looks like this bell curve. And so — even if you don’t know what the inputs were like. And that’s a really powerful theorem and a really powerful tool in mathematics.

Strogatz (25:05): Yes, it certainly is. And I liked your emphasis on that you don’t need to know what’s going on with the little effects. That that, somehow, that gets washed out. That information is not needed. The bell curve is predictable, even if you don’t know what the nature of the little effects is. As long as there’s a lot of them and they’re little. And they don’t affect each other, right, they’re independent, in some sense.

Wood (25:27): Yeah, absolutely. And so that is an idea, you know, sometimes it’s called universality in probability theory, that there are certain kinds of machines that if you put in a lot of random inputs, you can predict the output. Like, for example, that you would get this bell curve, or this normal distribution, even if you don’t know what you put in the machine. And that is incredibly powerful when there are things that we don’t understand very well, because —

Strogatz (25:56): But so, are you telling me — oh, I’m sorry to cut you off — but are you telling me this is happening in number theory now, too? That somehow we’re getting the idea of universality to show up in number theory? Or am I dreaming?

Wood (26:09): Well, to some extent, I would say that’s a dream of mine that is beginning. You know, we’re just, we’re taking the first steps to seeing it be realized. So it’s not just your dream, it’s my dream, too. Some of the work that I do today and that my collaborators and I work on is trying to make that kind of dream a reality so that, that some of these puzzling questions about numbers that we don’t know the answer to, maybe we could understand that there are patterns that come out, like a bell curve, like a normal distribution, that we can prove came out of the machine even if we don’t know what mysteries were put in.

Strogatz (26:55): Well, it’s a very inspiring, thrilling vision, actually, and I hope it all comes to pass. Thank you very much for talking to us today, Melanie.

Wood (27:03): Thank you. This was a lot of fun.

Announcer (27:06): If you like The Joy of Why, check out the Quanta Magazine Science Podcast, hosted by me, Susan Valot, one of the producers of this show. Also, tell your friends about this podcast, and give us a like or follow where you listen. It helps people find The Joy of Why podcast.

Strogatz (27:26): The Joy of Why is a podcast from Quanta Magazine, an editorially independent publication supported by the Simons Foundation. Funding decisions by the Simons Foundation have no influence on the selection of topics, guests, or other editorial decisions in this podcast or in Quanta Magazine. The Joy of Why is produced by Susan Valot and Polly Stryker. Our editors are John Rennie and Thomas Lin, with support by Matt Carlstrom, Annie Melchor and Leila Sloman. Our theme music was composed by Richie Johnson. Our logo is by Jackie King, and artwork for the episodes is by Michael Driver and Samuel Velasco. I’m your host, Steve Strogatz. If you have any questions or comments for us, please email us at [email protected]. Thanks for listening.