6,000,000 and Abel Prize - Numberphile

JAMES GRIME: It's maths news. We all love maths news, right? So recently the Abel Prize was announced. The Abel Prize is like the Nobel Prize for mathematics. So the winner of this year's Abel Prize was Endre Szemeredi. And he's a Hungarian mathematician. It's in recognition of a career in mathematics. And so, for that he has won six million Norwegian krone. That's about $1 million. So for this video-- and we always like to attach a number to our video-- we're going to use the number 6,000,000. DAVID HODGE: The prize itself only started in 2003. But it's now being seen as the mathematics Nobel Prize. There was a prize called the Fields Medal for mathematics, which has been around much longer. JAMES GRIME: There's the Fields medal which is really for young mathematicians. Young mathematicians, for us, is under 40. The Abel Prize has no restriction like that. So it is more directly comparable to the Nobel Prizes. DAVID HODGE: There is a fair amount of publicity about it. So it's awarded in Norway, and some people fly over for the ceremony. JAMES GRIME: There is no Nobel Prize for mathematics. There are some stories about that, and maybe I'll save those to the end. I like to end with an anti-climax. DAVID HODGE: So surname Szemeredi-- S-Z-E-M-E-R-E-D-I, first name Endre-- so quite difficult to pronounce, like many of the Hungarian mathematicians. He's now in his 70s. He's published over 200 papers in a wide variety of areas. In particular, lots of applications to graph theory, and applications to number theory, and including computer science, sorting algorithms. I'll talk today about some of the applications in what sounds a bit like number theory to do with counting sets of integers with certain properties. So I'm going to talk about what's now called Szemeredi's theorem, though it used to be called the Erdos-Turan conjecture, which stood for 30 or 40 years. And, because of the importance of the result, and the ways in which Szemeredi proved it, the result has now taken on his name. JAMES GRIME: One of his big theorems is now named after Szemeredi, so it's Szemeredi's theorem. And it's about finding structure in randomness. So this is what we're going to look at. We're going to look at something called arithmetic progressions. DAVID HODGE: Integers-- we're thinking about patterns within integers. So suppose I take a list of integers. I'll try and list a few of them. 1, 6, 7-- there, I've chosen six numbers. But, unfortunately, what's happened is I've chosen them in such a way that 1, 4, 7, 10 form what's called an arithmetic progression. So it's a progression where the gaps between the numbers is the same at every step. What we're going to try and do now is we're going to try to choose the numbers, and avoid these patterns. So I'm going to choose some numbers between 1 and 15. Let's focus just on patterns of length three. So a pattern where you've got a number, a second number, and a third number, where the gap between the first and second number is the same as the gap between the second and third number. Like 1, 4, 7 or 4, 7, 10. So I'll choose 1. I'll choose 2. Now, I can't choose 3, because I'd have a pattern immediately. So let's choose 4. I can't choose 6, because then we'd have 2, 4, 6, which forms a pattern of three in a row with the same difference. So I can't have 6. Can I have 5? Yes, I'll have 5. I can't have 7, because 1, 4, 7 would be a pattern. And I'm starting to struggle to find numbers. I have to start going to 8. So I go to 8. Have I managed it? Oh, no, I've already failed. I tried, but I failed, because 2, 5, 8 was a pattern. It's actually quite difficult to choose numbers without avoiding certain patterns. We're going to try to move towards what Szemeredi's theorem says. So let's try and avoid 3. So let's choose k. That's going to be equal to 3. That's the length of a sequence I'm going to try and avoid. And the rules are, we're going to have to choose numbers from the list 1, 2, 3, up to some enormous number, n-- very large number, n-- for example, 1,000,000. So we're going to try and choose numbers from 1 to a million, just like we chose numbers before. And we're going to try and avoid having any three somewhere which have got a common difference. Now, obviously we're not going to do that now, because there are far too many numbers to choose from. But what Szemeredi said is, actually, it's surprisingly few numbers that you're allowed to choose before you're forced to have a pattern. One way to describe his theorem is, I ask you for some percentage, and you give me 1%. 1% is going to be what percentage of the numbers I'm going to offer you, that you're going to have to choose. Let's go more advanced. Let's choose k is 4. That means we're going to have to try and avoid having four numbers in the sequence, somewhere, which have all got a common difference-- like 10, 20, 30, 40, or 100, 1,000, 1,900, 2,800. I could also put in 45, 50, 55, and 60. And I've messed up. And what Szemeredi said-- so here's Szemeredi. He comes along and gives us some completely insanely large number, which might be 10 to the 10 to the 10. This is going to be how many numbers you get to choose from. So I'm now going to give you the exercise. You've got to choose 1% of the numbers from this list, and try and avoid a sequence of length 4. You won't manage it. Szemeredi's cleverly-- his theorem says that if you chose any percentage, and any k, he can come back with a number that says, if you choose even 1% of those numbers, you will have accidentally, at some point, chosen four numbers in your list with a common difference between them. So you probably say, this is all very well, but 1% maybe was too many. And k equals 4-- that was quite a short list to try and avoid. Actually, even if you'd given me a ludicrous percentage-- if you'd given me a tiny percentage-- 0.001%. So at the end of this game, I'm going to give you a list of numbers, and you can choose 0.001% of them-- that's very, very few of them. And even if we'd then chosen k to be something else, something much larger-- say k is 100. k is 100 means all you've got to do is avoid having 100 numbers where the common difference is the same all the way along. Now, you'd think that was really easy to avoid. You'd think you could manage that. Szemeredi says, OK, give me your percentage. Give me your k. He'll go away, come back from his theorem, and he's going to give you another number on the end. His number's going to be even larger-- some completely insane number. But it's a number. You won't manage to avoid this-- what seems like a very unlikely thing. And this is true for any percentage and for any k. MALE SPEAKER (OFFSCREEN): Did Szemeredi come up with an equation that you could plug that number into, and that number into, to give you that number? Is there an equation? DAVID HODGE: If only. No. So, a lot of the results in this area have this strangely non-constructive proof to them. So the actual proof, itself, doesn't even give you the number. It purely says, there must be a number. MALE SPEAKER (OFFSCREEN): You said if I came up with any percentage, and any k, Szemeredi would come back to me with a number. Are you now saying Szemeredi, actually, he couldn't give me a number. He could just tell me a number exists. DAVID HODGE: He could tell you a number exists. There have been results since his work for which people have managed to give an upper band on this number. In which case, they could, now, give you a number. MALE SPEAKER (OFFSCREEN): The one thing that troubles me here is, there are an infinite number of numbers, aren't there? DAVID HODGE: Yep. MALE SPEAKER (OFFSCREEN): So I could have told you that no matter what you put there, and no matter what you put there, there'll be a number there eventually, because there are an infinite number of numbers that could go there. So why has Szemeredi been clever? DAVID HODGE: So suppose you took all the numbers. Suppose we go 1, 2, 3-- now this list goes on forever. So this is all the integers you know. What Szemeredi's result tells us is that if you gave me a percentage-- so, again, let's choose a percentage. This time we'll go for something slightly bigger-- 0.01%. If I asked you to choose a list of integers, it's going to be a very long list, because you've got to choose 0.01%. You're still going to have to choose infinitely many, but you're going to choose about 1 in 10,000 of all the numbers. What Szemeredi's result tells you is you are going to accidentally create progressions, lists of all lengths-- not just length 4, and 100, but any possible length will appear in your list if all you did was choose numbers, to arrange to choose about a 10,000th of them. JAMES GRIME: So what I really liked about this, though, is that this theorem was used to prove another result-- pretty much similar-- but about prime numbers. Now, the prime numbers are actually quite rare. They're unpredictable and rare. So they have density zero. Now, you can't use Szemeredi's theorem to prove the same result with the prime numbers, because Szemeredi's theorem was about things that had greater than zero density. But you could use his theorem in the proof of this statement-- the prime numbers have arithmetic progressions. So let's take the list of prime numbers. We know the prime numbers. They're 2, and 3, and 5. They go on forever. They're rare and unpredictable. But still you can find sequences, like the arithmetic progressions, of length 100, of length 1,000,000, whatever you want. And that is surprising. There is structure in the randomness of the prime numbers. An arithmetic sequence in the prime numbers. Let's pick-- I'm going to start with 5-- that's a prime number. And I'm going to add on 6. That's 11. I'm going to add on 6 again. That is 17. That's a prime number. Add on 6 again. That's 23. Add on 6 again-- that's 29. And that is an arithmetic progression of length five just using prime numbers. The common difference is six. In this case, they are called sexy primes. We're going to talk about that, aren't we? Now, the theorem doesn't guarantee what the common difference will be. You can't specify it. It doesn't tell you where to start it. It doesn't even tell you how to find them. But what I can guarantee you is that I can give you a progression of any length. I can give you a progression of length a million-- a billion, even. MALE SPEAKER (OFFSCREEN): But you can't tell me what the gap is? JAMES GRIME: I can't tell you what the gap is. But imagine a progression of a billion, just using prime numbers, where they have the common difference the same all the way through. MALE SPEAKER (OFFSCREEN): And that's there? JAMES GRIME: And that is in there. And that is guaranteed to be in there. I can't tell you what it is, but it's guaranteed to be in there. MALE SPEAKER (OFFSCREEN): Who figured that out? JAMES GRIME: Oh, who figured that out? Oh, the prime number version? Sorry. That was figured out by a Cambridge mathematician called Tim Gowers. And he's around here somewhere. He'll be in one of these offices. MALE SPEAKER (OFFSCREEN): Really? JAMES GRIME: Yeah. MALE SPEAKER (OFFSCREEN): Well, let's go ask him. JAMES GRIME: Yeah. MALE SPEAKER (OFFSCREEN): Is this just crosswords and Sudoku? Is this just mathematicians being unimaginably clever? Or is there a practical reason for Szemeredi to do this? DAVID HODGE: So some of the final results-- like this result-- it's not obvious this has any particular applications. But what's definitely true is that in order to get to these results, Szemeredi, himself, proved particularly one famous result-- what's called Szemeredi's regularity lemma, which is now being used in a number of different areas of maths, not just this fairly small area of trying to count progressions. That's particularly one of the reasons why he's been recognized. It's not just because he's done one big thing. But he's done a number of big things. And even to prove those big things, he's developed a whole new area of theory, which has been used by many people since him. JAMES GRIME: So there is no Nobel Prize for maths. Now, the story that is told in maths departments around the world is that Nobel, he didn't give a Nobel Prize for mathematics-- or didn't set one up-- because he hated mathematicians, and because his wife ran off with a mathematician. And that's the story that is told in math departments all over. The only problem is, he wasn't married. And it's not true. It's not true. He, I guess, though-- Nobel-- didn't appreciate mathematics enough to give it a prize. He was interested in physics and chemistry. There isn't a Nobel Prize for biology, either. So it's that reason. It's less exciting. I told you I wanted to end with an anti-climax.