[00:00] actually, but before I do, I want to lead with a spoiler, of complex numbers. given that the puzzle is going to be purely a discrete question.
[00:17] There's not a whiff of the imaginary or even continuity anywhere on the horizon. unreasonably useful for discrete math, to borrow a phrase.
[00:31] mathematicians understand prime numbers, you know, questions about how they're distributed, their density at certain regions, inputs and outputs are complex numbers.
[00:46] Basically, there's a specially designed function, and on the face of it, It's smooth, it's complex valued. you could ever want about those discrete prime numbers.
[01:02] And most importantly, certain questions about primes are easier to answer by analyzing this function than they would be by directly analyzing the primes themselves. is a lot more innocent than the Riemann hypothesis.
[01:16] But at the end of the video, I'll share how the techniques that we use to solve it, to the setup that leads to the Riemann hypothesis. And the prime number theorem and that whole circle of thoughts around it.
[01:34] Our puzzle for today comes from this book here by Titu Andreescu and Zuming Feng. the USA team for the International Math Olympiad. problem number 10 asks this seemingly innocent question.
[01:50] Find the number of subsets of the set 1 up to 2000, the sum of whose elements is divisible by 5. For example, something like the set 3, 1, 4, that would be a subset.
[02:05] And its sum, 3 plus 1 plus 4 is 8, so that wouldn't be considered. Whereas something like the set 2, 3, 5, also a subset, has a sum of 10.
[02:18] The preview animation that I had at the start is essentially It will iterate through all of the different possible subsets,
[02:30] finding the sum of each one along the way, and it increments a counter each time that And you know what, a nice warm-up question here would be to Forget this multiple of 5 stuff.
[02:44] How long will it take for this program to terminate? Many of you may know, the answer is 2 to the power 2,000. you have 2,000 different binary choices you can make.
[02:58] And all of those choices are independent of each other, so the total number of choices you have in constructing a subset is 2 times 2 times 2 And thinking about our program, that is a monstrously huge number.
[03:13] with all the physical resources the universe could conceivably provide, it wouldn't even come close, it wouldn't scratch the surface. And if you were to just guess what the answer should be, make a rough approximation,
[03:28] you'd probably guess, you know, it should be around a fifth of all the total subsets. There's probably a roughly even distribution of all these sums mod 5. But the heart of the question, the real challenge here, is to get a precise answer.
[03:42] but is the true answer a little bit more or a little bit less? What tactics could you possibly use to figure out that error?
[03:55] To be clear, this lesson is definitely much more about the journey than the destination. Almost certainly not, I wouldn't expect so. and navigating that challenge develops skills that are relevant to other sorts of
[04:12] For you and me, there are at least two very surprising and very beautiful twists and turns that the solution I'd like to share with you takes. I've already tipped my hand that complex numbers will make a surprise appearance,
[04:25] which is arguably even weirder and even more unexpected. and do what all good problem solvers should do, and start with a simpler example,
[04:38] If you were solving this problem with pencil and paper, you know, it's not a bad idea to simply list out all 2 to the 5 subsets. It's only 32, it's not that many.
[04:55] There's different ways that you might want to organize all of these in your mind, the natural thing to do would be to go through all of them one by one and so I'll cheat a little and show what all their sums are.
[05:11] organizing them suggestively into collections that all have the same sum. and they'll all sit in this little box, and the 3 subsets adding up to 10 will all
[05:25] And all in all, the ones that we care about, the subsets with a sum divisible by 5, have been put over here on the left, and it looks like there's a total of 8 of them. we consider its sum to be 0, and we consider that to be a multiple of 5.
[05:43] By the end, I hope you'll agree all of those are abundantly natural choices to make. Out of all 32 total subsets, a fifth of that would have been 6.4,
[05:55] so at least in this small example, the true answer is a little bit bigger than that. Okay, and this is the part of the video where, Personally, I like it when math feels like something you could have discovered yourself,
[06:12] I think there's all sorts of natural steps that you might take. or you play around with how these sums are distributed mod 5 at many different
[06:25] iterations for other small examples, and from that maybe you try to eke out some kind of When I shared an early version of this lesson with some patrons, All those are well and good, nothing wrong with those.
[06:37] But instead, my goal here is to teach you about something called a generating function. yeah, I get that this works, but how on earth would you have thought of that?
[06:49] There's a time in your life before you understand generating functions, and a time after, and I can't think of anything that connects them other than a leap of faith. I'm going to ask you to consider the polynomial 1 plus x times 1 plus x squared
[07:03] times 1 plus x cubed times 1 plus x to the fourth times 1 plus x to the fifth. What do polynomials have to do with things? What is the variable x even supposed to represent right now?
[07:17] The only reason that we've written a polynomial here is that the act of algebraically expanding it is going to completely mirror the act of constructing subsets. And, importantly, this grouping that we want, where subsets with the same
[07:32] sum are all bunched together, kind of happens automatically when you do this. When you expand out this expression, it basically Which term from each parenthetical do you choose?
[07:46] that will correspond to the empty set where we don't choose any of the elements. Whereas if I choose the x to the 1 term and then ones from everything else, that will correspond to the singleton set that just contains the number 1.
[08:02] that corresponds to the set just containing 2. Just choosing the x cubed term corresponds to the set just containing the number 3. 1 term and the x squared term and then ones from everything else.
[08:20] has 1 and 2 and nothing from everything else. But in the polynomial, the way it expands looks like x cubed. So we have two different x cubed terms, each of which came from a subset whose sum was 3.
[08:36] probably easiest if you just take the time to pause and think Essentially, every possible subset corresponds to one of the terms in this expansion.
[08:49] And then the critical point is that the exponent in the term that you get from that expansion equals the sum of that corresponding subset. kind of think it through yourself I think you can see what I mean.
[09:02] For example, when all of the dust settles and we collect all 32 terms here, three of those terms are x to the 10th, and each of those came from a choice of elements whose sum was equal to 10.
[09:14] Now normally when we write a polynomial, we collect together all like terms. we would just see the coefficient 3 in front of x to the 10th. the number of subsets with a particular sum.
[09:30] So this, like I said at the start, is an example of something called a generating function, where the idea is if you have some question with an answer associated with each positive integer, so in our case how many subsets add up to a particular value.
[09:43] When you construct a polynomial whose coefficients correspond to the answers to that question, you can get a surprising amount of insight from your original question by mathematically manipulating and analyzing the properties of this polynomial.
[09:56] but just to bring up one other one which is especially fun, So all the coefficients of this polynomial will be Fibonacci numbers,
[10:08] so I should really be calling it a power series. leave them up on the screen for anyone who's curious. each one being the sum of the previous two, can be expressed as an equation in terms
[10:25] That equation in turn lets you write that function in an alternate form. And then, and here's most of the details I'm skipping over, if you manipulate that, a little bit of geometric series power expansion there,
[10:41] you can get yourself an exact closed form expression for each individual Fibonacci I mentioned this really just to show the tip of the iceberg of the fact that this idea of a generating function goes way, way beyond our particular example.
[10:56] Now, in our particular problem, if we extend from the simple example with just 12345 to the big example with all the numbers up to 2000, our corresponding generating function involves these 2000 different binomial terms,
[11:09] you know, 1 plus x, 1 plus x squared, on and on, up to 1 plus x to the 2000. the coefficients tell us all the information we want. but it is helpful to keep in the back of your mind, in principle,
[11:25] For example, in principle, if you expanded it, you would find that the coefficient in front of the x to the 25th term happens to be 142. 142 distinct subsets that have a sum of 25.
[11:42] So the art of analyzing a generating function here will be to deduce facts about these coefficients without actually expanding the expression.
[11:55] So moving forward, I'm just going to write this expansion more abstractly, just a sum from n equals 0 up to capital N, where c sub n tells us the coefficients that All of that starts off as a black box to us.
[12:08] something where we plug in x, we see what the output is, and then we ask, For example, a very easy input would be to plug in something like x equals 0.
[12:21] In that case, importantly, we know how to evaluate it using the factored form above. If you plug in x equals 0 for everything, all of the terms look like 1, And in the expanded form, all of those terms involving an x will get killed,
[12:34] Now, in this case, that doesn't really tell us anything all that exciting. but we're just getting our feet wet.
[12:46] As the next example, take a moment to think about evaluating f at 1. when you plug in 1 for all of these x's, every term looks like a 2, so in total, On the other hand, in the expanded expression, if you plug in x equals 1,
[13:04] all of these powers of x go to 1, so we're essentially adding up all Just by evaluating the function at a single number, Now, again, in our particular example, it's not all that exciting,
[13:21] Remember, each coefficient counts how many subsets have a certain sum, which we know to be 2 to the 2,000.
[13:34] ask you to evaluate this function at negative 1. Take a moment to think about what that means. the factored expression up top, and here, all you need is to look at the first term.
[13:50] so the whole expression has to be 0. using all of the coefficients? And in the spirit of being as suggestive as possible of the strange
[14:04] various powers of negative 1 in this expression in terms of rotations. which we'll picture as a vector from 0 to 1.
[14:16] Then negative 1 to the first power is just negative 1 itself, which I want you to be thinking about as a 180-degree rotation away from that last term. Again, a 180-degree rotation.
[14:30] And in general, each successive term here looks like another rotation by 180 degrees. even coefficients and the odd coefficients, but keep the visual in the back of your mind.
[14:44] for our special generating function, we know that this value, this alternating sum, And a way you can interpret that is that it's telling you there's an equal balance between the even coefficients and the odd coefficients.
[14:59] these coefficients are encoding for us facts about subsets. So if there's an equal balance between all those even coefficients subsets have an even sum, and half of them have an odd sum.
[15:16] would show that, and with the generating function, it just kind of pops right out. let me rewrite this a little bit by taking the last two things we evaluated,
[15:31] add up those two, and then divide by one half. the even coefficients and killing all of the odd coefficients. So it becomes an especially clean way to write the fact that the sum of all
[15:45] total number of subsets with an even sum, will look like half of the total. This is, needless to say, tantalizingly close to the actual question we want to answer.
[15:57] What we would like to do is find some clever thing that we can do to the function f, the coefficients corresponding to multiples of 5. that will be answering our final question.
[16:12] That will be counting the total number of subsets whose sum is divisible by 5. where the successive powers of the input were rotating back and forth.
[16:25] we'd like them to somehow rotate with a period of 5. You see, up there we can find a value so that as we take successive powers of it,
[16:39] it will rotate by a fifth of a turn, giving us a process with a frequency of 5. that I'm asking you to think about complex numbers. but hopefully it's not all that wild.
[16:55] And again, the reason that I'm drawing things out to tee up the various strange turns in the solution is that they're actually not all that strange in the broader scheme of math. The trick we're about to apply has a heavy resemblance to many other instances
[17:08] of using complex numbers to better understand discrete questions of integers. So the more it feels like something that you could have discovered yourself, future problem in this circle of thoughts, you will discover it yourself.
[17:28] To be specific, the complex number that I care about is one that I'm going to label zeta, So its angle is 2 pi fifths radians, and its magnitude is one.
[17:42] we would write that number explicitly as e to the power 2 pi i divided by 5. you could think of it as something whose real part is the cosine of 72 degrees,
[17:56] 72 being a fifth of a full turn, and the imaginary part is the sine of 72 degrees. But to be honest, you don't actually need to think about the explicit value. Instead, the important thing to focus on is the property that powers of this number have.
[18:11] the magnitude of its square is also one, but it rotates a fifth of a turn around the unit circle, so it now sits two fifths of a turn around. you end up three fifths of a turn around, raise it to the fourth power,
[18:27] and you've gotten all the way back around to one. We get this cycling every five terms. These numbers have a special name, they're called the fifth roots of unity,
[18:43] essentially because they solve the equation z to the fifth equals one. If you just presented someone with this equation, they would probably say the answer is clearly z equals one.
[18:55] Four other numbers where when you raise them to the fifth, you get one, Remember that equation, it'll come back for us a little bit later.
[19:08] So in analogy with what we did earlier, where we added together f of what we're going to do is evaluate f at all five of these numbers, and then add them together, and hopefully we get some cancellation.
[19:23] That might seem kind of complicated, but let's just take a super simple example, In that case, when we add up these five terms, Zeta to the zero plus zeta to the one, on and on, up to zeta to the fourth.
[19:38] like vector addition with the tip to the tail. So zeta to the zero plus zeta will look like this, and then if I add on zeta squared, bringing the tail of that vector to the tip of the last one, we get this.
[19:52] Then similarly, if I bring the tail of zeta cubed over to the tip of that one, the overall sum actually loops back to be zero. these terms are evenly balanced around the number zero.
[20:08] Now it's helpful to think about a slightly less trivial example, if f of x was x squared. This is just a fancy way of saying the number one.
[20:22] So you might imagine this dot up here moving over to the zeta squared dot when we do it. You might imagine this dot moving over to zeta to the fourth.
[20:36] Zeta cubed moves to zeta to the sixth, which, because we loop around every five times, So this dot will move up here. And finally, zeta to the fourth squares to give us zeta to the eighth,
[20:50] which reduces to be the same as zeta cubed, which I might draw like this. especially with all the arrows I have drawn here, because the idea here is that when we square this,
[21:05] they have, the overall effect is to just shuffle those terms. so their sum is still going to be zero. Similarly, if you go through this exercise with x cubed, which I encourage you to do,
[21:21] you'll be able to see that when we cube these terms, when we take each one and we multiply the angle that it has by three, Same terms listed in a different order, unsurprisingly the same
[21:37] thing happens if our function was x to the fourth, but, critically, where things change is if we consider the function x to the fifth. In that case, when you raise zeta to the fifth power, by definition it goes to one.
[21:52] All of these go to one, they are the roots of unity, So in this case, when we apply the function and add them all up, we get a kind of constructive interference.
[22:08] All of them equal one, so their sum is equal to five. essentially this expression is something that will go to zero for powers of x which are not divisible by five, but it goes to something non-zero for powers of x which
[22:24] And that's exactly the kind of filter that we're looking for. power of x, essentially things play really nicely here because everything is linear.
[22:37] If f is some massive polynomial and we want to evaluate this big sum, where each time you really are just adding up powers of zeta, and in most cases all those powers cancel out with each other and you get zero,
[22:52] they constructively interfere and instead you get five times whatever the corresponding Deep in the weeds it's easy to forget why we're here in the first place,
[23:05] but remember each one of those coefficients tells us how many subsets add up to a certain value, and so what we want is to add up all of the coefficients that are multiples of five, and what we have right now is a way to explicitly do that.
[23:18] If we evaluate this function on these five different roots of unity, divide by five and it gives us the sum that we want. We have a question that's just about subsets, it's a discrete math problem,
[23:34] polynomial on some judiciously chosen complex numbers. because complex numbers have this bizarre relationship with discrete math,
[23:46] but it really is wonderful, there's no two ways about it. However, some of you might complain, the only way that this is useful is if we can actually evaluate this wild expression on our polynomial.
[23:58] Remember, the form of the polynomial we know, the one we're comfortable with, on and on, all the way up to one plus x to the two thousand. pushing around one hard problem into another,
[24:14] unless we can actually roll up our sleeves and do some honest calculation here. This is the final thrust in our argument, so step back, take a deep breath. It's actually not as bad as you might think, but let's start just by thinking about
[24:26] how you might evaluate just one of the roots of unity that we need, maybe zeta itself. So what that looks like is one plus zeta, times one plus zeta squared, Except, importantly, after those first five terms,
[24:39] everything starts repeating, because powers of zeta repeat. going to be a copy of this expression four hundred times. but it's way easier than multiplying out two thousand different terms.
[24:55] A way you might visualize this is that we're taking each one of those roots of unity, but basically adding one, we're shifting them all to the right. intuition for the numerical answer that we might expect.
[25:08] The thing that we want is the product of these five different complex numbers, And if you know a thing or two about complex numbers, since these come in conjugate pairs, all we really need is to multiply the lengths
[25:21] For example, that dot furthest to the right corresponds to one plus zeta to the fifth, which in the diagram I'm labeling as zeta to the zero plus one. both just fancy ways of writing the number two.
[25:36] Next to that, we have the values one plus zeta and one plus zeta to the fourth, both of which have the same magnitude, the lengths of these lines are the same. So we need to multiply two different copies of that length, L1 squared.
[25:51] Similarly, the remaining two values, zeta squared plus one and zeta cubed plus one, So let's just call that length L2. So our product needs to include two copies of that L2.
[26:04] you might notice that L1 is a length that's something a little bit longer than one, So the final answer here probably comes to something around two-ish,
[26:17] To turn this into an exact answer, we could just expand out the full expression. It's honestly not that bad, there's only 32 different terms.
[26:33] Okay, you've hung with me for a long time now, and I know that it's getting to be a lot. our last step much simpler than you might think it should be. So we started with this question asking us, count the number
[26:49] We then constructed this polynomial whose coefficients tell us how many subsets have a particular sum for each value n. So what we want is to add up every fifth coefficient of that polynomial.
[27:04] Then we saw how evaluating this polynomial as a function on all of the fifth roots of unity, then adding them up, ends up giving us exactly this filter that we want. which essentially comes down to a product of five complex numbers.
[27:20] As a super slick way to actually evaluate that product, here's the final trick. They solve the equation z to the fifth equals one. roots of the polynomial z to the fifth minus one.
[27:36] Now what that means is we can factor the polynomial z to the fifth minus one to look like this, where there's one factor corresponding to each one of the roots. This expression is kind of magical when you think about all of the crazy
[27:51] but it is true and it's super useful for us right now, because the expression on the right hand side looks almost identical to the It basically just has minus signs where we wish there were plus signs.
[28:07] If you do that, you essentially have the negative of what we want. If you multiply it by negative one, notice how the left hand side here, which started out as negative one minus one or negative two, that just becomes two.
[28:23] And then the right hand side turns into the thing that we want to evaluate. not only is the answer around two, the answer quite magically turns out to be That is actually super nice and very lovely, because it means this bigger
[28:40] the different roots of unity, we know its value on the first root of unity. Essentially identical reasoning shows that its value on the next
[28:52] because remember when you take powers of zeta squared or zeta cubed, you get the same list of numbers that are just shuffled in a different order. The only one that's different is when we evaluate it as zeta to the zero.
[29:06] and we know how to evaluate this at one. All of these parentheticals turn into two, so it looks like taking two multiplied by itself two thousand times.
[29:20] honest answer to our counting question. To add up all of these coefficients which are divisible by five, which, remember, is a way of counting how many total subsets have a sum divisible by five,
[29:35] which we just computed to be two to the two thousand plus four different copies And here you might want to do just a quick sanity
[29:47] For example, if you do it in the smaller case with the set one two three four five, it tells you that the answer is one fifth of two to the fifth,
[30:01] the total number of subsets, plus four times two to the one in this case, And if you'll remember when we explicitly looked at them all, that was in fact the answer.
[30:17] solve a hard problem, it's also worth taking some time to reflect on it. What do you get out of this?
[30:29] how the dominant part is indeed one fifth of all the total subsets like quite destructive interference in a massive combination of roots of unity. it's the way that we solved it, namely taking a discrete sequence that we want to
[30:48] understand and treating it as the coefficients on a polynomial, Both of those steps are probably highly unexpected at the outset, but both of those steps relate to some very general and powerful techniques that you'll
[31:03] For example, at the top of the lesson, I promised that the technique that we would use would be similar in spirit to the way that primes are studied, and the set of ideas that leads up to the Riemann hypothesis and things like that.
[31:16] little criminal to cram some kind of rushed version into the end here. a while back about the zeta function, take the time, do it right.
[31:30] But if you're curious, and if you'll allow me to throw some things up on the screen parallel. Just like our subsets puzzle, the way that Riemann studied primes involved a discrete
[31:43] sequence we want to understand, something carrying information about prime numbers, and then considering a function whose coefficients are the terms in that sequence. related structure known as a Dirichlet series,
[31:58] or Dirichlet series depending on who you ask, but it's the same essential idea. Then the way to suss out information about those coefficients comes from studying how this function behaves with, you guessed it, complex valued inputs.
[32:12] after all Riemann was a pioneer in complex analysis, but the fact remains extending your domain beyond real numbers like this offers you, the mathematician, a lot more power in making deductions about the coefficients.
[32:28] For some viewers this all might leave the lingering question of why exactly complex numbers are so unreasonably useful in this way. It's a hard question to answer exactly, but if you think about our puzzle,
[32:40] everything we just did, as soon as we were in this situation where plugging it's sort of like the more inputs you can work with the better, so you might as well open yourself up to a richer space of numbers like the
[32:54] But there is a more specific intuition that I want you to come away with here. In our puzzle the relevant fact that we wanted, the sum of every fifth coefficient, was a kind of frequency question, and the real reason the complex numbers as
[33:08] opposed to some other structure proved to be useful for us is that we could find a value so that successive products have this cycling behavior. particular to suss out frequency information is extremely fruitful.
[33:24] It is almost impossible to overstate how helpful that idea is. in the 1990s Peter Shor found a way for quantum computers to factor large numbers way And if you go in and you look at the details of how what we now
[33:41] call Shor's algorithm works, the idea is essentially this, the use of roots of unity to detect a kind of frequency information. Fourier series and the infinite swell of topics that follow from those.
[33:56] we've really only just scratched the surface here, and if you want to learn more I highly recommend this kind of hilariously And I'll also leave up a few fun puzzles on the screen here
[34:10] for anyone who wants to flex their muscles a bit with the idea.