Winding numbers and domain coloring

There's two things here, the main topic and the meta topic. The main topic is going to be this really neat algorithm for solving two-dimensional equations, things that have two unknown real numbers, or also those involving a single unknown which is a complex number. So for example, if you wanted to find the complex roots of a polynomial, or maybe some of those million dollar zeros of the Riemann zeta function, this algorithm would do it for you. And this method is super pretty, since a lot of colors are involved. And more importantly, the core underlying idea applies to all sorts of math well beyond this algorithm for solving equations, including a bit of topology, which I'll talk about afterwards. But what really makes this worth 20 minutes or so of your time is that it illustrates a lesson much more generally useful throughout math, which is try to define constructs that compose nicely with each other. You'll see what I mean by that as the story progresses.

To motivate the case with functions that have 2D inputs and 2D outputs, let's start off simpler with functions that just take in a real number and spit out a real number. If you want to know when a function f of x equals some other function g of x, you might think of this as searching for when the graphs of those functions intersect, right? I mean that gives you an input where both functions have the same output. To take a very simple example, imagine f of x is x squared, and g of x is the constant function 2. In other words, you want to find the square root of 2. Even if you know almost nothing about finding square roots, you can probably see that 1 squared is less than 2, and 2 squared is bigger than 2, so you realize, ah, there's going to be some solution in between those two values. And then if you wanted to narrow it down further, maybe you try squaring the halfway point, 1. 5. This comes out to be 2. 25, a little too high, so you'd focus on the region between 1 and 1. 5. And so on, you can probably see how this would keep going, you'd keep computing at the midpoint and then chopping your search space in half. Another way to think about this, which is going to make it easier for us once we get up to higher dimensions, is to instead focus on the equivalent question for when the difference between these two functions is zero. In those terms, we found a region of inputs where that difference was negative on one end, and it was positive on another end. And then we split it into two, and the half that we narrowed our attention to was the one where the outermost points had varying signs. And like this, we were able to keep going forever, taking each region with varying signs on the border, finding a smaller such region among its halves, knowing that ultimately we have to be narrowing in on a point which is going to be exactly zero.

In short, solving equations can always be framed as finding when a certain function is equal to zero, and to do that, we have this heuristic, if f is positive at one point and negative at another point, you can find someplace in between where it's zero, at least if everything changes smoothly with no sudden jumps. Now the amazing thing I want to show you is that you can extend this kind of thinking into two-dimensional equations, equations between functions whose inputs and outputs are both two-dimensional. For example, complex numbers are 2D, and this tool we're developing is perfect for finding solutions to complex equations.

Now since we're going to be talking about these 2D functions so much, let's take a brief side step and consider how we illustrate these. Graphing a function with a 2D input and a 2D output would require four dimensions, and that's not going to work so well in our 3D world on our 2D screens, but we still have a couple good options. One is to just look at both the input space and the output space side by side. Each point in the input space moves to a particular point in the output space, and I can show how moving around that input point corresponds to certain movements in the output space. All of the functions we consider will be continuous, in the sense that small little changes to the input only correspond to small little changes in the output, there's no sudden jumps. Another option we have is to imagine the arrow from the origin of the output space to that output point, and to attach a miniature version of that arrow to the input point. This can give us a sense, at a glance, for where a given input point goes, or where many different input points go by drawing the full vector field. And unfortunately when you do this at a lot of points it can get pretty cluttered, so here let me make all of the arrows the same size, and what this means is we can get a sense of the direction of each output point.

But perhaps the prettiest way to illustrate two-dimensional functions, and the one we'll be using most this video, is to associate each point in that output space with a color. Here we've used hues, that is where the color falls along a rainbow or a color wheel, to correspond to the direction away from the origin, and we're using darkness or brightness to correspond to the distance from the origin. For example, focusing just on this array of outputs, all of these points are red, but the ones closer to the origin are a little darker, and the ones farther away are a little brighter. And focusing just on this array of outputs, all of the points are green, and again, closer to the origin means darker, farther away means lighter. And so on, all we're doing here is assigning a specific color to each direction, all changing continuously. You might notice the darkness and brightness differences here are pretty subtle, but for this video, all we care about is the direction of outputs, not the magnitudes, the hues, not the brightness. The one important thing about brightness for you to notice is that near the origin, which has no particular direction, all of the colors fade to black.

So for thinking about functions, now that we've decided on a color for each output, we can visualize 2D functions by coloring each point in the input space based on the color of the point where it lands in the output space. I like to imagine many different points from that input space hopping over to their corresponding outputs in the output space, then getting painted based on the color of the point where they land, and then hopping back to where they came from in the input space. Doing this for every point in the input space, you can get a sense just by looking at that input space for roughly where the function takes each point. For example, this stripe of pink points on the left tells us that all of those points get mapped somewhere in the pink direction, that lower left of the output space. Also those three points which are black with lots of colors around them are the ones that go to zero. Alright, so just like the 1D case, solving equations of 2D functions can always be reframed by asking when a certain function is equal to zero. So that's our challenge right now, create an algorithm that finds which input points of a given 2D function go to zero.

Now you might point out that if you're looking at a color map like this by seeing those black dots, you already know where the zeros of the function are. So does that count? Well keep in mind that to create a diagram like this, we've had the computer compute the function at all of the pixels on the plane, but our goal is to find a more efficient algorithm that only requires computing the function at as few points as possible, only having a limited view of the colors, so to speak.

And also from a more theoretical standpoint, it'd be nice to have a general construct that tells us the conditions for whether or not a zero exists inside a given region. Now remember, in one dimension the main insight was that if a continuous function is positive at one point and negative at another, then somewhere in between it must be zero. So how do we extend that into two dimensions? We need some sort of analog of talking about signs. One way to think about what signs even are is directions. Positive means you're pointing to the right along the number line, and negative means you're pointing to the left. Two dimensional quantities also have direction, but for them the options are much wider, they can point anywhere along a whole circle of possibilities. So the same way that in one dimension we were asking whether a given function is positive or negative on the boundary of a range, which is just two points, for 2D functions we're going to be looking at the boundary of a region, which is a loop, and ask about the direction of the function's output along that boundary. For example, we see that along this loop around this zero, the output goes through every possible direction, all the colors of the rainbow, red, yellow, green, blue, back to red, and everything in between along the way. But along this loop over here, with no zeros inside of it, the output doesn't go through every color, it goes through some of the orangish ones, but never, say, green or blue. And this is promising, it looks a lot like how things worked in one dimension. Maybe in the same way that if a 1D function takes both possible signs on the boundary of a 1D region, there was a zero somewhere inside, we might hypothesize that if a 2D function hits outputs of all possible directions, all possible colors, along the boundary of a 2D region, then somewhere inside that region it must go to zero. So that's our guess, and take a moment to think about if this should be true, and if so, why? If we start thinking about a tiny loop around some input point, we know that since everything is continuous, our function takes it to some tiny loop near the corresponding output. But look, for most tiny loops, the output varies in color. If you pick any output point other than zero, and draw a sufficiently tight loop near it, the loop's colors are all going to be about the same color as that point. A tight loop over here is all bluish, yellowish, you certainly aren't going to get every color of the rainbow. The only point where you can tighten loops around it while still getting all the colors is the colorless origin, zero itself. So it is indeed the case that if you have loops going through every color of the rainbow, tightening and tightening, narrowing in on a point, then that point must in fact be a zero. And so, let's set up a 2D equation solver just like our one-dimensional equation solver. When we find a large region whose border goes through every color, split it into two, and then look at the colors on the boundary of each half. In the example shown here, the border on the left half doesn't go through all colors, there are no points that map to the orangish-yellowish directions, for example. So I'll grey out this area as a way of saying we don't want to search it any further. The right half does go through all the colors, spends a lot of time in the green direction, then passes through yellow-orange-red, as well as blue-violet-pink. Now remember, what that means is that points of this boundary get mapped to outputs of all possible directions. So we'll explore it further, subdividing again and checking the boundary for each region. The boundary of the top is all green, so we'll stop searching there. But the bottom is colorful enough to deserve a subdivision. And just continue like this. Check which subregion has a boundary covering all possible colors, meaning points of that boundary get mapped to all possible directions, and keep chopping those regions in half like we did for the one-dimensional case, eventually leading us to a zero over the func- Well, hang on a second. What happened here? Neither of those last subdivisions on the bottom right passed through all the colors, so our algorithm stopped because it didn't want to search through either of those, but it also didn't find a zero. Okay, clearly something's wrong here. And that's okay, being wrong is a regular part of doing math. If we look back, we had this hypothesis, and it led us to this proposed algorithm, so we were mistaken somewhere. And being good at math isn't about being right the first time, it's about having the resilience to carefully look back and understand the mistakes, and understand how to fix them. Now the problem here is that we had a region whose border went through every color, but when we split it in the middle, neither subregion's border went through every color, we had no options for where to keep searching next, and that broke the zero finder. Now in one dimension, this sort of thing never happened. Any time you had an interval whose endpoints have different signs, if you split it up, you know that you're guaranteed to get some subinterval whose endpoints also have different signs. Or, put another way, any time you have two intervals whose endpoints don't change signs, if you combine them, you'll get a bigger interval whose endpoints also don't change sign. But in two dimensions, it's possible to find two regions whose borders don't go through every color, but whose boundaries combine to give a region whose border does go through every color. And in just this way, our proposed zero-finding algorithm broke. In fact, if you think about it, you can find a big loop whose border goes through every possible color without there being a zero inside of it. Now that's not to say that we were wrong in our claims about tiny loops when we said that a forever narrowing loop going through every color has to be narrowing in on a zero. But what made a mess of things for us is that this does-my-border-go-through-every-color-or-not property doesn't combine in a nice, predictable way when you combine regions. But don't worry, it turns out we can modify this slightly to a more sophisticated property that does combine to give us what we want. The idea is that instead of simply asking whether we can find a color at some point along the loop, let's keep more careful track of how these colors change as we walk around that loop. Let me show you what I mean with an example. I'll keep a little color wheel up here in the corner to help us keep track. When the colors along a path of inputs move through the rainbow in a specific direction, from red to yellow, yellow to green, green to blue, or blue to red, the output is swinging clockwise. But on the other hand, if the colors move the other way through the rainbow, from blue to green, green to yellow, yellow to red, or red to blue, the output is swinging counterclockwise. So walking along this short path here, the colors wind a fifth of the way clockwise through the color wheel. And walking along this path here, the colors wind another fifth of the way clockwise through the color wheel. And of course that means that if you go through both paths, one after the other, the colors wind a total of two-fifths of a full turn clockwise. The total amount of winding just adds up, and this is going to be key, this is the kind of straightforward combining that will be useful to us. Now when I say total amount of winding, I want you to imagine an old-fashioned odometer that ticks forward as the arrow spins clockwise, but backwards counterclockwise. So counterclockwise winding counts as negative clockwise winding. The outputs may turn a lot, but if some of that turning is in the opposite direction, it cancels out. For example, if you move forward along this path, and then move backwards along that same path, the total amount of winding ends up being zero. The backwards movement literally rewinds through the previously seen colors, reversing all the previous winding, and returning the odometer back to where it started. For our purposes, we'll care most about looking at the winding along loops. For example, let's say we walk around this entire loop clockwise. The outputs that we come across wind around a total of three full clockwise turns. The colors swung through the rainbow, ROYGBIV, in order, from red to red again, and then again, and again. In the jargon mathematicians use, we say that along this loop, the total winding number is three. Now for other loops, it could be any other whole number, maybe a larger one if the output swings around many times as the input walks around a single loop, or it could be a smaller number if the output only swings around once or twice, or that winding number could even be a negative integer if the output was swinging counterclockwise as we walk clockwise around the loop. But along any loop, this total amount of winding has to be a whole number. I mean, by the time you get back to where you started, you'll have the same output that you started with. Incidentally, if a path actually contains a point where the output is precisely zero, then technically you can't define a winding number along that, since the output has no particular direction. Now this isn't going to be a problem for us, because our whole goal is to find zeros, so if this ever comes up, we just lucked out early. Alright, so the main thing to notice about these winding numbers

is that they add up nicely when you combine paths into bigger paths. But what we really want is for the winding numbers along the borders of regions to add up nicely when we combine regions to make bigger regions. So do we have that property? Well, take a look. The winding number as we go clockwise around this region on the left is the sum of the winding numbers from these four paths, and the winding as we go clockwise around this region on the right is the sum of the winding numbers from these four paths. And when we combine those two regions into a bigger one, most of those paths become part of the clockwise border of the bigger region. And as for those two paths that don't? Well, they cancel out perfectly. One of them is just the reverse, the rewinding of the other one, like we saw before. So the winding numbers along borders of regions add up in just the way we want them to. Also side note, this reasoning about oriented borders adding up nicely like this comes up a lot in mathematics, and it often goes under the name Stokes' theorem. Those of you who've studied multivariable calculus might recognize it from that context.

So now, finally, with winding numbers in hand, we can get back to our equation solving goals. The problem with the region we saw earlier is that even though its border passed through all possible colors, the winding number was actually zero. The outputs wound around halfway, through yellow to red, and then started going counterclockwise back the other direction, then continued going through blue and hitting red from the other way, all in such a way that the total winding netted out to be zero. But if you find a loop which not only hits every color, but has the stronger condition of a non-zero winding number, then if you were to split it in half, you're guaranteed that at least one of those halves has a non-zero winding number as well, since things add up nicely in the way we want them to. So in this way, you can keep going, narrowing in further and further onto one point. And as you narrow in onto a point, you'll be doing so with tiny loops that have non-zero winding numbers, which implies they go through all possible colors, and therefore, like I said before, the point they're narrowing in on must be a zero. And that's it! We have now created a two-dimensional equation solver, and this time, I promise, there are no bugs. Winding numbers are precisely the tool we need to make this work. We can now solve equations that look like where does f of x equal g of x in two dimensions just by considering how the difference between f and g winds around. Whenever we have a loop whose winding number isn't zero, we can run this algorithm on it and we're guaranteed to find a solution somewhere within it. And what's more, just like in one dimension, this algorithm is incredibly efficient. We keep narrowing in on half the size of our region each round, thus quickly narrowing in on the zeros, and all the while, we only have to check the value of the function along points of these loops, rather than checking it on the many points of the interior. So in some sense, the overall work done is proportional only to the search space's perimeter, not the full area, which is amazing.

Now once you understand what's going on, it's weirdly mesmerizing to just watch this in action, giving it some function and letting it search for zeros. Like I said before, complex numbers are two-dimensional, so let's apply it to some equation with complex numbers. For example, here's the algorithm finding the zeros of the function x to the fifth minus x minus one over the complex plane. It started by considering a very large region around the origin, which ended up having a winding number of five. Each time you find a loop with a non-zero winding number, you split it in half and figure out the winding number of the two smaller loops. Either one or both of them is guaranteed to have a non-zero winding number, and when you see this, you know there's a zero somewhere inside that smaller loop, so you keep going in the same way, searching the smaller space. We also stop exploring a region if the path we're computing along happens to stumble across a zero, which actually happened once for this example on the right half here. Those rare occurrences interfere with our ability to compute winding numbers, but hey, we got a zero. And as for loops whose winding number is zero, you just don't explore those further. Maybe they have a solution inside, maybe they don't, we have no guarantees. And letting our equation solver continue in the same way, it eventually converges to lots of zeros for this polynomial. By the way, it is no coincidence that the total winding number in this example happened to be five. With complex numbers, the operation x to the n directly corresponds to walking around the output's origin n times as you walk around the input's origin once.

So with the polynomial, for large enough inputs, every term other than the leading term becomes insignificant in comparison. So any complex polynomial whose leading term is x to the n has a winding number of n around a large enough loop. And in that way, our winding number technology actually guarantees that every complex polynomial has a zero. This is such an important fact that mathematicians call it the fundamental theorem of algebra. Having an algorithm for finding numerical solutions to equations like this is extremely practical, but the fundamental theorem of algebra is a good example of how these winding numbers are also quite useful on a theoretical level, guaranteeing the existence of a solution to a broad class of equations for suitable conditions, which is much more the kind of thing mathematicians like thinking about. I'll show you a couple more amazing applications of this in the context of topology in a follow-up video, which includes correcting a mistake from an old 3blue1brown video. Which one? Well, watch all of the videos, everything on this channel, and see if you can spot the error first.

The primary author of this video is one of the newest 3blue1brown team members, Sridhar Ramesh. Thank you for watching.