A blessed man's formula for holey containers
I love the way derivatives of types tell you about holes in containers. It works the other way too and holes can give insight into derivatives.
Suppose S and T are containers so that S(X) and T(X) are containers of elements of type X. Then S(T(X)) is an S-container of T-containers of X's. If we draw S as a square (rectangle actually) and T as a triangle then we can draw a picture of an example of such a thing:
Taking the nth derivative of a type gives the type with (an ordered sequence of) n holes. Here's that previous container with 3 holes made in it:
As the holes have an ordering I've numbered them from 1 to 3.
An S-container of T-containers with holes is essentially an S-container containing both ordinary T-containers, and some T-containers with holes. If we excise the T-containers with holes, we're left with an S-container containing just T-containers, and some holes. Here's a picture of that:
But there are a couple of problems with that. Once we've excised the holey sub T-containers we don't know which S-holes to plug them back into and we don't know how to reconstruct the original numbering of the holes. We need to keep a tiny bit more information. That's the set I wrote down: {{1,3},{2}}. Call each element of this set a block. I've written the elements of the blocks in ascending order and I've written the blocks in ascending order of their lowest elements. The first block corresponds to hole 1 in the S-container and the second block corresponds to hole 2. Similarly, we write the elements of the blocks into the holes in the T-containers. And that allows us to reconstruct the original ST-container.
Think about the general case. We make n holes in an ST-container. So up to n of the T-containers acquire holes. Let's say it's m holes. We can think of the S-container having m holes and these holes being filled by T-containers with b1, b2,...,bm holes where the sum of the bi is n. We're essentially just partitioning the original n holes {1,2,...,n} into m sets. So each ST-container with n holes gives a partition of {1,...,n}, an S-container with n holes, and m T-containers where the ith has bi holes. Writing containers with n holes as nth derivatives we get
Note that the equality above isn't just a numerical equality, it's an isomorphism of types. In fact, it's the type version of the 'combinatorial form' of the Faà di Bruno formula. Although that wikipedia page describes the formula as 'forbidding', if I've done my job right then I think the above picture make it seem almost trivial. I find it much easier to think of this version of the chain rule in terms of holes.
And the explanation for the title of this post: in 1988 Pope John Paul II beatified Faà di Bruno.
Suppose S and T are containers so that S(X) and T(X) are containers of elements of type X. Then S(T(X)) is an S-container of T-containers of X's. If we draw S as a square (rectangle actually) and T as a triangle then we can draw a picture of an example of such a thing:
Taking the nth derivative of a type gives the type with (an ordered sequence of) n holes. Here's that previous container with 3 holes made in it:
As the holes have an ordering I've numbered them from 1 to 3.
An S-container of T-containers with holes is essentially an S-container containing both ordinary T-containers, and some T-containers with holes. If we excise the T-containers with holes, we're left with an S-container containing just T-containers, and some holes. Here's a picture of that:
But there are a couple of problems with that. Once we've excised the holey sub T-containers we don't know which S-holes to plug them back into and we don't know how to reconstruct the original numbering of the holes. We need to keep a tiny bit more information. That's the set I wrote down: {{1,3},{2}}. Call each element of this set a block. I've written the elements of the blocks in ascending order and I've written the blocks in ascending order of their lowest elements. The first block corresponds to hole 1 in the S-container and the second block corresponds to hole 2. Similarly, we write the elements of the blocks into the holes in the T-containers. And that allows us to reconstruct the original ST-container.
Think about the general case. We make n holes in an ST-container. So up to n of the T-containers acquire holes. Let's say it's m holes. We can think of the S-container having m holes and these holes being filled by T-containers with b1, b2,...,bm holes where the sum of the bi is n. We're essentially just partitioning the original n holes {1,2,...,n} into m sets. So each ST-container with n holes gives a partition of {1,...,n}, an S-container with n holes, and m T-containers where the ith has bi holes. Writing containers with n holes as nth derivatives we get
dn(F(G(X))/dXn = sum over each partition P of {1,...,n} of d|P|F/dG|P| times the product over each block B in P of d|B|F/dX|B|
Note that the equality above isn't just a numerical equality, it's an isomorphism of types. In fact, it's the type version of the 'combinatorial form' of the Faà di Bruno formula. Although that wikipedia page describes the formula as 'forbidding', if I've done my job right then I think the above picture make it seem almost trivial. I find it much easier to think of this version of the chain rule in terms of holes.
And the explanation for the title of this post: in 1988 Pope John Paul II beatified Faà di Bruno.
posted by sigfpe at Saturday, June 28, 2008
4 Comments:
Haven't you got the numbering wrong in the last diagram?
Paul.
Paul,
I think I have a scheme that gives a 1-1 correspondence between terms and partitions.
In the last diagram, the numbering of the holes for each container must go from 1 to n as a holey container contains no more information about the holes beyond their order.
So {1,3} is the first element (block) of the partition. It pairs with the first holey triangle. The first element of the block, 1, goes into the hole in the triangle marked '1'. The second element of the block, 3 goes into the hole in the triangle marked '2'. And now that triangle goes into the hole marked '1' in the rectangle. And so on.
I had to spend the last week reading the Conor McBride paper (it would have taken less time if I didn't have two kids) so that I could come back here to see what you were talking about. Thanks for the reference! I hope you're pleased that you can inspire so much dedication in your readers.
Did you notice that McBride cited his dad's Ph.D. thesis in the bibliography?
Mark,
I didn't spot the citation but I'm not hat surprised from what Conor has said to me.
Glad you were inspired to follow up on holes in types because I think they're the neatest thing I've come across in years.
Post a Comment
<< Home