# Winding numbers and domain coloring

There’s two things here, the main topic, and the meta topic.
The main topic is a neat algorithm for solving many two-dimensional equations.
That is, equations with two unknown real numbers, or perhaps those involving a single unknown
which is a complex number.
So for example, if you want to find the complex roots of a polynomial, or some of those million
dollar zeros of the Riemann zeta function, this algorithm will do it for you.
This method can be super pretty, since there is a lot of color involved, and the core underlying
idea applies to all sorts of math beyond this algorithm for solving equations, including
a bit of topology, which I’ll talk about afterwards.
But what really makes this worth the 20 minutes or so of your time is that it illustrates
a lesson much more generally useful throughout math, which is to try to define constructs
which 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 one function, f(x), equals another function, g(x), you might think
of this as searching for when the graphs of these functions intersect.
Right?
That tells you the input where both functions have the same output.
To take a very simple example, say f(x) is x2, and g(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 probably see quickly that
12 is less than 2 and 22 is bigger than 2, and so you realize “Ah, there’s a solution
somewhere between 1 and 2”.
And then if you wanted to narrow it down further, you might try squaring the halfway point,
1.5.
This comes out at 2.25, a bit too high, so now you focus on the region between 1 and
1.5.
And so on.
You can keep computing at the midpoint and chopping your search space in half.
Another way to think about this, which will make it easier once we get up to higher dimensions,
is to instead focus on the equivalent question of when the difference between the two functions
is 0.
We found a region of inputs where this was negative at one end, and positive at the other.
And then we split this region in two, narrowing our attention to a half whose outermost points
again produced varying signs.
We were able to keep going forever in this way, taking each region with varying signs
on its border and finding a smaller such region among its halves, knowing that ultimately,
we had to be narrowing in on a point where we would hit exactly zero.
In short, solving equations can always be framed as finding when a certain function
is 0.
And to do that, use the we use the heuristic “If f is positive at one point, and f is
negative at another point, then we can find some place in between where it’s zero (…at
least, if everything changes smoothly, with no sudden jumps)”.
The amazing thing I want to show you is how to extend this kind of thinking to two-dimensional
equations; to equations between functions whose inputs and outputs are both two-dimensional.
For example, complex numbers are two-dimensional, and the tool we develop here is perfect for
finding solutions to complex equations.
Since we’re going to be discussing 2d functions so much,, let’s take a brief side-step to
consider how we illustrate them.
Graphing functions with 2d inputs and 2d outputs would require 4 dimensions, which won’t
work so well in our 3d world on our 2d screens, but we still have a few good options.
One is just to look at at both the input and 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 the input point corresponds to certain movements in the output space.
All the functions we consider will be continuous, in the sense that small changes in input cause
small changes in output, without any sudden jumps.
Another option is to think of the arrow from the origin of the output space to the output
point, and 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 a full vector field.
(Unfortunately, this can also be a bit cluttered; here, let me make all these arrows the same
size, so we can more easily get a sense of just the direction of the output at each point.)
But perhaps the prettiest way to illustrate 2d functions, and the one we’ll use most
in this video, is to associate each point in the output space with a color.
Here, we’ve used different “hues” (that is, where the color falls along a rainbow
or color wheel) to correspond to the direction away from the origin, while we’ve used darkness
or brightness to correspond to distance from the origin.
For example, focusing just on this ray of outputs, all these points are red, but the
ones closer to the origin are a little darker and the ones further away are a little lighter.
And focusing just on this ray of outputs, all the points are green, and again, closer
to the origin we get darker and further away we get lighter.
And so on, we’ve just assigned a color to each direction, all changing continuously.
(The darkness and brightness differences here can be quite subtle, but for this video all
we will care about is the directions of outputs, and not their magnitudes; the hue, not the
brightness.
The only important thing about brightness is just that near the origin, which has no
particular direction, our colors will fade to black.)
Now that we’ve decided on colors 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 points from the input space hopping over to the output space, which
is basically one big color wheel now, getting painted, and then hopping back to where they
came from.
This gives a way, just by looking at the input space, to understand roughly where the function
takes each point.
For example, this stripe of pink points on the left tells us that all those points get
mapped to the pink direction, the lower left of the output space.
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 an equation of two-dimensional equations can
always be reframed as asking when a certain function equals 0.
So that’s our challenge right now: Create an algorithm that finds which input points
a given 2d function takes to 0.
Now, you might point out that if you’re looking at a color map like this, by seeing
these black dots you know where the zeros of the function are...so, does that count?
Well, keep in mind that to create this diagram we’ve had the computer compute the function
at all these pixels on the plane.
But part of our goal here is to find a more efficient algorithm that only requires computing
the function on as few points as possible; only having limited view of the colors of
the plane, so to speak.
Also, from a more theoretical standpoint, it’d be nice to have a general construct
which gives us conditions for whether or not a zero even exists inside a given region.
Now, in 1-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 0.
How do you extend to two dimensions?
You need some analog of talking about signs.
Well, one way to think about what signs are is as directions; positive means pointing
right along a number line, and negative means pointing left along that number line.
Two-dimensional quantities also have directions, although for them, the options are wider:
they can point anywhere along a whole circle of possibilities.
So in the same way that for 1d functions, we were asking whether a given function was
positive or negative on the boundary of a range, which is just two points; for 2d functions
we will want to look at the boundary of a region, which will be some loop, and ask about
the direction of the function’s output along that boundary.
For example, we see that on 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 on this loop over here, with no zeros inside, the output doesn’t go through every
color; it only goes through some orangish colors, but never, say, green or blue.
This is promising; it looks a lot like how things worked in 1d.
Maybe, in the same way that if a 1d function takes both possible signs on the boundary
of a 1d region, there’s a zero somewhere between, we might hypothesize that if a 2d
function hits outputs of all possible directions, all possible colors, on the boundary of a
2d region, somewhere inside that region it must go to zero.
Here, take a moment to really think about if this should be true, and if so, why.
If we start by thinking about a tiny loop around some input point, we know, since everything
is continuous, that our function takes it to some tiny loop near the corresponding output.
But look: most tiny loops of outputs barely vary in color.
If you pick any output point other than zero, and draw a sufficiently tight loop near it,
the loop’s colors will all be about the same as the color of that point.
A tight loop here will be all blue-ish; a tight loop here will be all yellow-ish, etc.
You certainly won’t get every color of the rainbow.
The only point you can tighten loops around while still going through all the colors of
the rainbow 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 and narrowing in on a point, then that point must in fact be
a zero.
…And so we can set up our 2d equation solver just like our 1d equation solver: when we
find a large region whose border goes through every color, split it in two, and look at
the colors on the boundary on each half.
In the example shown here, the border of the left half doesn’t go through all colors;
there are no points that map to the orange and yellow directions, so we grey this area
out as a way of saying we don’t want to search it further.
The right half does go through all colors, spending a lot of time in the green direction,
then passing yellow-orange-red, as well as blue-violet.
Remember, that means points of this boundary get mapped to outputs of all possible directions,
so we’ll explore it further, subdividing again and checking the boundary colors of
each subregion.
The boundary of that top right 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 colors, meaning points of that boundary
get mapped to all possible directions, and keep chopping those subregions in half like
we did in the 1d case.
...Except...wait a minute...what happened here?
Neither of those last subdivisions on the bottom right passes through all colors...so
our algorithm stopped without having found a zero…
So being wrong is a regular part of doing math.
We had this hypothesis that led us to a proposed algorithm, and clearly we were mistaken somewhere.
Being good at math is not about being right the first time, it’s about having the resilience
to carefully look back and understand our mistakes, and how to fix them.
The problem here was that we had a region whose border went through every color, but
when we split it down the middle, neither subregion’s border went through every color.
We had no options for where to keep searching next, breaking our zero-finder.
In 1d, this sort of thing never happened: any time you had an interval whose endpoints
had different signs, when you split it, you knew you were guaranteed to get some sub-interval
Put another way, any time you have two intervals whose endpoints don’t change sign, when
you combine them, you get a bigger interval whose endpoints don’t change sign.
But in 2d, you can take two regions whose borders don’t contain every color, and combine
them into a region whose border DOES contain every color.
And in just this way, our proposed zero-finder can break down.
In fact, you can have a big loop whose border goes through every color, without there being
any zeros inside
We weren’t wrong in our claims about tiny loops; when we said that forever-narrowing
loops that go through every color had to be narrowing in on a zero.
But what made a mess for us is that, the “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 nicely, giving us what we want.
Instead of simply asking whether we find every color at some point along a loop, let’s
keep track more carefully of how those colors change as as we walk along the loop.
Let me show what you I mean with some examples.
I’ll keep a little color wheel here in the corner to help us keep track.
When colors along a path of inputs move through the rainbow from red to yellow, or yellow
to green, green to blue, or blue to red, the output is swinging clockwise.
On the other hand, when 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.
Of course, this means that if we go through both paths, one after another, the colors
wind a total of two-fifths of a full turn clockwise.
The total amount of winding just adds up; this is the kind of straightforward combining
that will be useful to us.
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 ticks backward as the arrow spins counterclockwise.
So counterclockwise winding counts as negative clockwise winding.
The output may turn and turn a lot, but if some of that turning is in opposite directions,
it cancels out.
For example, if you move forward along a path, and then move backward along that same path,
the total winding number will end up being zero: the backwards movement will literally
“re-wind” through all the previously seen colors, reversing all the previous winding
and returning the odometer to where it started.
We can look at winding along loops, too.
For example, if we walk around this entire loop clockwise, the outputs we come across
wind around a total of three full turns clockwise: the colors swung through the rainbow, in ROYGBIV
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.
In the case of this loop, the winding number was three.
For other loops it could be any other whole number.
Large ones, if the output swings around many times as the input walks along a loop.
Smaller ones, if the output only swings around once or twice.
Or the winding number could even be a negative integer, if the output loops around counterclockwise
as we walk clockwise around the loop.
But along any loop, it will be a whole number, because by the time we return to where we
started, we have to get back to the same output we started with.
(Along paths that don’t end back where they start, we can get fractions of turns, as we
saw earlier, but whenever you combine these into a loop, the total will be a whole number)
Incidentally, if a path actually contains a point where the output is precisely zero,
then we can’t define the winding number along it, since the output has no particular
direction anymore.
This won’t be a problem for us, though.
Our whole goal is to find zeros, so if this ever comes up, we’ve just lucked out early.
Alright, so winding numbers add up nicely when you combine paths into bigger paths,
but what we really want is for winding numbers around the borders of regions to add up nicely
when you combine regions into bigger regions.
Do we have this property?
Well, take a look!
The winding number as we go clockwise around this region is the sum of the winding numbers
from these paths.
And the winding as we go clockwise around this region is the sum of the winding numbers
from these paths.
When we combine those two regions into this bigger region, most of those paths become
part of the clockwise border of the bigger region.
And as for the parts that don’t?
They cancel out; one is just the other in reverse, the “re-winding” of the other,
as we saw before.
So winding numbers along borders of regions add up just the way we want them to!
(As a side note, this reasoning about borders adding up this way comes up a lot in mathematics,
and is often called “Stokes’ Theorem”; those of you who have studied multivariable
calculus may recognize it from that context…)
And 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 colors, the winding number was 0.
The outputs wound around halfway, through yellow to red, then started going counterclockwise
back through blue and hitting red from the other direction, then wound clockwise again
in such a way that the total winding netted out to be zero.
But if you find any loop with a nonzero winding number and split it in half, at least one
of the halves is guaranteed to have a nonzero winding number, since things add up nicely.
And in this way, we can keep going, narrowing in further and further on a point…
As we narrow in on that point, we’ll be doing so using tiny loops with nonzero winding
number, which must be tiny loops which go through every color, and therefore, as we
discussed before, that point must be a zero.
And that’s it!
We have now created our 2d equation solver, and this time, I promise, there are no bugs.
“Winding numbers” are precisely the tool we needed to make this work.
We can now solve equations “Where does f(x) = g(x)?” in 2d 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 are guaranteed to find a solution somewhere within it.
And what’s more, just as in 1d, our equation solver is remarkably efficient; we keep narrowing
in to half the size of our region each round, thus quickly narrowing in on our 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 all the many, many points inside.
So in some sense the overall “work” we do is proportional only to our search space’s
perimeter, not its area.
Which is amazing!
It is weirdly mesmerizing to watch this in action; just giving it some function and letting
search for zeros.
Like I said before, complex numbers are 2d, so we can apply this algorithm to equations
between functions from complex numbers to complex numbers.
For example, here’s our algorithm finding all the zeros of the function x5 - x - 1 over
the complex numbers, starting by considering a very large region around the origin.
Each time you find a loop with nonzero winding number, you split it in half, and figure out
the winding numbers of the two smaller loops.
Either one or both of the smaller loops will have nonzero winding number; when you see
this, you know there is a zero to be found in that loop, and so you keep going in the
same way in that smaller search space.
As for loops whose winding number is zero, you don’t explore those further inside.
(We also stop exploring a region when we stumble directly across a zero point inside it, right
on the nose, as happened once on the right half here; these rare occurrences interfere
with our ability to compute winding numbers, but hey, we get
a zero!).
And letting our equation solver continue in this same way, it eventually converges on
lots of zeros of this polynomial.
Incidentally, it’s no coincidence that the overall winding number came out to 5 in this
example.
With complex numbers, the operation xn directly corresponds to winding around n times as we
loop around the origin, and for large enough inputs, every term in a polynomial other than
the leading term becomes insignificant in comparison.
So any complex polynomial of degree n has a winding number of n around a large enough
loop.
In this way, our winding number technology actually guarantees us that every complex
polynomial has a zero; mathematicians call this the Fundamental Theorem of Algebra.
Having an algorithm for finding numerical solutions to equations like this is extremely
practical, but I should say that we’ve left out a few details on how you’d implement
it.
For example, to know how frequently you should sample points, you’d want to know how quickly
the direction of the output changes, we’ve left some more details in the description.
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 zero for a
broad class of functions under suitable conditions.
We’ll see a few more amazing applications of this in a follow-up video, including correcting
a mistake from an old 3blue1brown video!
(Which one?
Rewatch all of our videos, everything we’ve ever made, 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, and with the last video on the Basel problem you’ve already seen the work of
the other new addition Ben Hambrecht.
I did a little Q&A session with both of them, which you can find on the Patreon page, and
where you can have fun laughing at how bad we are with live action filming and lighting.
Sridhar and Ben are both incredibly smart and talented, and additions like these will
be crucial for covering all the topics I’d like to with this channel.
The fact is, a lot of time and care goes into each of these videos.
There’s taking the time to explore which topics have are most likely to deepen people’s
relationship with math; and even once you have that, any of you who write know how many
iterations can go into putting together clear and engaging storyline for a given topic.
Obviously creating the visuals to best clarify an idea in math takes serious time, and quite
often involves writing the more general code for fundamentally different types of visuals.
What’s neat is that unlike similar products, such as movies or college courses, we’re