Newton Fractals

As soon as I’m done teaching today, I’m heading on the road to scenic Tyler, TX for the Conference on Representation Theory, Quantum Field Theory, Category Theory, Mathematical Physics and Quantum Information Theory. And so something light, that I actually presented to my students last week.

Many of you may be familiar with this from calculus, but at least it’s more interesting than L’Hôpital’s rule. For those who haven’t seen it, this post is outside the main line. Accordingly, I’m willing to leave some of the calculus unmotivated and unexplained.

Newton’s Method is an attempt to find a point where for some function . The basic idea is that we pick a point near where we think there’s a zero of the function and assume that the graph of the function is sort of sloping towards the zero. Functions on their own are sort of hard to work with, but we know how to deal with linear functions pretty well. We’ll try to pretend the function is just linear and work from there.

So if we start at the point we have the point on the graph above it. Then we draw a straight line that just touches the graph at that point. Calculus tells us that this line has the equation . Now we want to find the where this line crosses the -axis. That is: . Some algebra tells us that .

Now I’m not saying that is our desired zero, but hopefully it’s closer. Then we just run this again. If we define we can write . And then we continue by writing , where the exponent means we evaluate the function twice. This goes on, defining an infinite sequence of points , and the hope is that this will zoom in on a zero of the function.

Well, zeroes of the function are fixed points of this map. Indeed, if then . We have other tools that tell us a fixed point of a function will attract nearby points if . And here, . Since , we see that , so near these fixed points the map does indeed pull points closer.

But there’s a problem. What happens when ? Then the function is undefined, and the method breaks down. Almost as bad, near those points the tangent line is almost flat, and so the next point in the sequence ends up very far away, possibly nearer a different zero than the one we were trying to find.

Here’s a picture to show how complicated this can get. In this picture, we’re moving from calculus over the real numbers to calculus over the complex numbers, but the mechanics of Newton’s Method work the same. We consider the function , so we’re trying to find the three points on the complex plane that have cube . We know that one is itself, and the other two are situated a third of a rotation around the unit circle in either direction.

We get the picture by picking a complex number to start with, and running the method until we’re within some very small distance of one of our zeroes, so we know we’re going to get to that one in the limit. If we end up at , we color the point blue. The points which go to the other two zeroes we color green and red, respectively. We color a point darker if it takes longer to get near one of the zeroes.

We’d hope that starting at a given point would land us at the closest of the three zeroes, but borders here are tricky. We can never have a boundary between two of these basins of attraction without having the third one there too. So along the line separating the blue basin from the red one we have a chain of green islands. Similarly, we have red islands between blue and green, and blue islands between red and green. And then along the boundary a green island shares with the big blue basin we have a chain of smaller red islands, and so on. The upshot is that every boundary point looks like the point at where all three basins touch each other, leading to the famous self-similarity that is characteristic of fractal geometries.

More on Kernels and Cokernels

The best-known abelian categories are categories of modules over various rings. And as modules, these objects are structured sets. Now, even though we’re willing to elide the difference between a hom-group and a hom-set, we would at least like to avoid talking about the objects as sets, and the morphisms as functions. So let’s try to focus on studying the morphisms and use them to understand the properties of the category. Luckily, in an abelian category we know a lot about morphisms.

For one thing, let’s consider an object and the set of all the arrows coming into . We can put the structure of a preorder on this set by saying if there is with . It’s straightforward to show that this relation is reflexive and transitive. Then, as usual we can symmetrize this relation to get an equivalence relation: if and only if and . When we pass to the equivalence classes, the preorder becomes a partial order, which we’ll also call . In particular, this includes all monomorphisms, which we know as subobjects.

Similarly, we can construct another preorder of all the arrows leading out of with if there is an with . We can also turn this into a partial order, which includes the partial order of all quotient objects of .

Now for every arrow from pick a kernel and for every to pick a cokernel. Then and live in , while and live in . And we have three equivalent statements:

• 
• 
• 

Now the partial orders and can be considered as categories, as any partial order can be. And the maps and reverse these orders, so they are contravariant functors. So let’s flip the order on ( instead of ) and instead consider them as covariant functors and .

The above equivalence now reads . That is, we have an adjunction. The identities satisfied by the unit and counit read, in this case:

• 
• 

Properties of Ab-Categories

There are a number of things we can say right off about the -categories we defined last time. As is common practice, we’ll blur the distinction between an abelian group and its underlying set.

First of all, any -category has zero morphisms. That is, there’s a special morphism between any two objects that when composed with any other morphism gives the special morphism in the appropriate hom-set. In fact, since each hom-set is an abelian group it has an additive identity . Then for any we have , which composition must send to . The zero morphisms are exactly the zero morphisms!

Given any object the hom-set is already an abelian group. But the composition puts the structure of a monoid onto this set as well, and the linearity condition says these two are compatible, making the endomorphism monoid into an endomorphism ring. In fact, every ring is an endomorphism ring. Way back when we first defined categories we noted that a category with one object was the exact same thing as a monoid. And a ring is just an abelian group with a compatible monoid structure on it. So an -category with a single object is the exact same thing as a ring! In fact, a lot of the study of -categories can be seen as extending ring theory from that special case to the more general one. Incidentally, you should see right off that when we consider rings and as categories like this, a ring homomorphism from to is the same thing as an -functor between the categories.

Remember when we talked about direct sums of modules over a given ring? Well the same thing happens here. We define the “biproduct” of the finite collection of objects to be an object along with two families of arrows:

• 
• 

satisfying the relations

• if
• 
• 

From the same arguments as in our coverage of direct sums we see that a biproduct satisfies the universal properties of both a categorical product and coproduct, and conversely that a categorical product or coproduct implies the existence of the biproduct arrows. Note that we’re making no statement whatsoever that such a biproduct actually exists in our category, but when it does it’s both a product and a coproduct.

As a special case, we can consider the biproduct of an empty collection of objects. This will be both a product and a coproduct of an empty collection of objects, if it exists, and will thus be a zero object. Of course, it may or may not exist.

Even if there is no zero object in our category, we still have the above zero morphisms, and so we can still talk about kernels and cokernels. The kernel of a morphism is the equalizer , and its cokernel is the coequalizer . In fact, life is even better now that we’re enriched over : every equalizer is a kernel and every coequalizer is a cokernel. Indeed, and similarly for coequalizers. Again, we’re saying nothing about whether such kernels or cokernels actually exist.

Together, these facts say a lot about the behavior of limits in -categories. Biproducts tell us about finite products and coproducts, while kernels of morphisms tell us about all different equalizers. And then The Existence Theorem for Limits tells us that every finite limit can be constructed from finite products and equalizers, while every finite colimit can be constructed from finite coproducts and coequalizers. So if our -category has all biproducts, all kernels, and all cokernels, then it has all finite limits whatsoever!

Let’s add one more little property that will simplify our life. We know that kernels are monomorphisms, and that cokernels are epimorphisms. If we assume on top of having all biproducts, kernels, and cokernels that every monomorphism is actually the kernel of some arrow in our category, and that every epimorphism is actually the cokernel of some arrow, then we will call our -category an abelian category.

You should verify that given any ring the category of all left -modules satisfies all these properties, and thus is an abelian category. These are the abelian categories that started the whole theory of homological algebra, which is to a large extent the study of general abelian categories.

Ab-Categories

Now that we’ve done a whole lot about enriched categories in the abstract, let’s look at the very useful special case of categories enriched over — the category of abelian groups.

We know that is a monoidal category, with the tensor product of abelian groups as its monoidal structure and the free abelian group as the monoidal identity. Even better, it’s symmetric, and even closed. That is, for any two abelian groups and we have an isomorphism , and there is a natural abelian group structure on the set of homomorphisms satisfying the adjunction .

Further, is complete and cocomplete. All together, this means it’s a great candidate as a base category on which to build enriched categories. Of course, these will be called -categories.

So let’s read the definitions. An -category has a collection of objects, and between objects and there is an abelian hom-group .

For each object we have a homomorphism of abelian groups which picks out the “identity morphism” from to itself at the level of the underlying sets. Remember that we’re no longer thinking of an abelian group as having elements — only its underlying set has elements anymore, and the underlying set of an abelian group is the set of abelian group homomorphisms .

Given three objects we have a “composition” arrow in : . This is associative and the identity morphism acts as an identity in the sense that the appropriate diagrams commute. Of course, since the composition arrows are morphisms in they are linear functions in each input.

An -functor between -categories and is defined by a function from the objects of to the objects of , and for each pair of objects a homomorphism of abelian groups . Two diagrams are required to commute, saying that these linear functions preserve the composition and identity functions.

An -natural transformation is one of two forms. In one we’re given two -functors and . Then a natural is a collection of linear functions making one diagram commute. In the other we’re given an object and a bifunctor . Then is a collection of linear functions making another diagram commute.

Together, -categories, -functors between them, and -natural transformations (of the first kind) form a 2-category. We can pair off -categories and to get the product category (in fact we already did once above) and we can take the opposite category . Thus -categories form a symmetric monoidal 2-category with a duality involution.

There’s a whole lot of structure here, but ultimately it boils down to “the hom-sets all have the structure of abelian groups, and everything in sight is -linear”. And that’s the usual definition given, that I decided to forgo back when I started in on enriched categories.

Free Enriched Categories

Now we’re going to assume that our monoidal category is also cocomplete. In particular, we’ll assume that it has all small coproducts.

This is enough to ensure that the “underlying set” functor has a left adjoint that sends a set to the coproduct of a bunch of copies of indexed by . The adjunction says that is naturally isomorphic to . That is, a function from to the underlying set of is the same as an -indexed collection of elements of the underlying set of .

It’s straightforward from here to verify that this adjunction interchanges the cartesian product on and the monoidal structure on . That is, and .

And now the 2-functor has a left 2-adjoint . Starting with an ordinary category (with hom-sets) we get the “free -category” with the same objects as , and with the hom-objects given by . Compositions and identities for this -category are induced by the above exchange of cartesian and monoidal structures. The actions of this 2-functor on functors and natural transformations are straightforwardly defined.

For example, when , we just replace each hom-set by the free abelian group on . We extend the composition and identity maps from the ordinary category by linearity. In particular, if has only one object — if it’s a monoid — then is the free ring on .

To finish off, let be a small category, so is a small -category. Then we can define functor categories and functor -categories. Verify that by the above 2-adjunction.

The Strong Yoneda Lemma

We gave a weak, “half-enriched” version of the Yoneda Lemma earlier. Now it’s time to pump it up to a fully-enriched version.

Given a -functor and an object , then the functor defines a -natural map . We also have the (ordinary) adjunction

and under this adjunction we find corresponding to a -natural transformation . Now the strong form of the Yoneda Lemma says that this family is actually the counit of the end , so by the definition of the functor category we have an isomorphism in :

So, how do we verify that is the end in question? Consider any other -natural family . Now we run the above adjunction backwards to get a -natural family . But this is now a -natural transformation from the functor represented by to the functor , and so the weak form of the Yoneda Lemma tells us that for a unique . Running this back through the adjunction says that , and the universal property is satisfied.

Let’s hit this isomorphism with the underlying set functor to get a bijection . This sends an arrow to , which is a -natural family with components given by . But this is exactly the bijection asserted by the weak form of the Yoneda Lemma, so the weaker form is implied by the stronger one.

If we consider the special case where our functor is representable, we find that

When exists, we can convert the functor to a functor by the exponential adjunction in . By the case of representable functors given above, this Yoneda embedding is fully faithful. From this -functor we can establish that the Yoneda isomorphism is -natural in and .

New Blaths

Here are a couple new blaths (I’m going to popularize that term if it kills me) to hit the intarwobs. First off is the latest Fields-Medalist-cum-blatherer, Timothy Gowers.

More interesting to me is Rigorous Trivialities, which is being sporadically written by a new graduate student at UPenn. I wonder if Isabel put him up to it. Either way, this means we’re only one seminar invitation from having three Ivy-league-educated math bloggers in one room (hint, hint).

Functor Categories as Exponentials

The notation we used for the enriched category of functors between two enriched categories gives away the game a bit: this will be the exponential between the two categories.

First off, the arrows that we used to read off the -component of a natural transformation turn out to fit into a more general structure. As we might hope there’s an “evaluation” functor that takes a -functor from to and evaluates it on an object of to give an object of . The partial functors are and . That this is actually a -functor follows yet again from that litany of naturalities we keep referring to.

Now the -functor induces an ordinary functor . Remember here that is a 2-category — a category enriched over ordinary categories — so each hom-object is a category, and an arrow from one hom-object to another is a functor. In particular, given a functor we get a functor . And then we compose with the evaluation functor to get a functor . It turns out that this functor is an isomorphism of categories.

This means that every functor is of the above form for some unique . Let’s look at the partial functors of and .

• 
• 

The first of these equations completely determines the functor in that must assign to an object of . The second uniquely determines the action of on hom-objects because is the counit of an end, and it comes with a universal property. Thus the above map is bijective on objects. But since it’s a functor we also need it to be bijective on morphisms — natural transformations in this case.

So, if we’ve got functors and from to , with images and from . Now we need to check that every -natural is of the form for some unique -natural . But by the equation above between the second partial functors, this says that . Thus is the -natural transformation .

We now have a 2-natural isomorphism (natural isomorphism enriched over ): . Equivalently, this means that is 2-natural in each variable. Using this naturality it’s straightforward to show that given and we get a -functor by composing functors.

All of this fits together to say that the 2-functor has a right adjoint when exists for all . At this point, the existence tends to hinge on a lot of smallness technicalities. The 2-category of all -categories is thus “partially closed”, in a similar way to the 2-category of all ordinary categories. However, if we restrict to small -categories we actually do have a symmetric, monoidal, closed 2-category.

In either case, partial closedness together with the Fubini theorem is enough for us to get the standard isomorphisms and . This latter holds in the sense that either side exists if the other one does.

Functor Categories

Let’s consider two categories enriched over a monoidal category — and — and assume that is equivalent to a small category. We’ll build a -category of functors between them.

Of course the objects will be functors . Now for functors and we need a -object of natural transformations between them. For this, we will use an end:

This end is sure to exist because of the smallness assumption on . Its counit will be written .

An “element” of this object is an arrow . Such arrows correspond uniquely to -natural families of arrows , which we know is the same as a -natural transformation from to . We also see that at this level of elements, the counit takes a -natural transformation and “evaluates” it at the object .

Now we need to define composition morphisms for these hom-objects. This composition will be inherited from the target category . Basically, the idea is that at each object a natural transformation gives a component morphism in the target category, and we compose transformations by composing their components. Of course, we have to finesse this a bit because we don’t have sets and elements anymore.

So how do we get a component morphism? We use the counit map ! We have the arrow

which we can then hit with the composition . This is a -natural family indexed by , so by the universal property of the end we have a unique arrow

Similarly we get the arrow picking out identity morphism on as the unique one satisfying

So is a -category whose underlying ordinary category is that of -functors and -natural transformations between the -categories and . That is, it’s the hom-category in the 2-category of -categories.

Ends II

We continue our discussion of ends by noting that the process of taking an end (if it exists) is functorial in a sense.

More specifically, let’s say we have two functors and from to , a -natural transformation , and that both of and have ends. Then we can compose with the transformation to get a -natural transformation from the end of to . By the universal property of there is then a unique arrow so that .

Now let’s consider a functor so that the end exists for each object . That is, we have arrows natural in for each . There is now a unique way of making into a functor so that is also natural in .

First, we note that is an end for . Indeed, we have

On the other hand, we have

and

By the universal property of the end , there is a unique arrow so that . These — along with the behavior of on objects — form a functor because they are -natural, and we can see this naturality from the litany of naturalities.

Now let’s consider a functor . If each end exists, then it they are the values of a -functor .

Further, every family that is -natural in factorizes uniquely into the composite of and . Again by our litany of naturalities, is -natural in if and only if is. Then since is natural in and separately if and only if it is natural in the pair , we deduce the “Fubini Theorem”: if every exists then

and either side exists if and only if the other side does.

Then, since we have the “interchange of ends” theorem: if every and every exists then

and either side exists if and only if the other side does.

It’s this formal, semantic similarity between the process of taking an end and the process of integration (which some of you may have heard of) that leads us to write an end as if it were an integral. We have bound variables ranging over categories, occurring covariantly and contravariantly, pairing off, and different variables do this essentially independently of each other.