Theory and Applications of Categories, Vol. 25, No. 15, 2011, pp. 394–425.

THE FAÀ DI BRUNO CONSTRUCTION

J.R.B. COCKETT AND R.A.G. SEELY

Abstract. In the context of Cartesian differential categories [BCS 09], the structure of the first-order chain rule gives rise to a fibration, the “bundle category”. In the present paper we generalise this to the higher-order chain rule (originally developed in the traditional setting by Faà di Bruno in the nineteenth century); given any Cartesian differential category 𝕏, there is a “higher-order chain rule fibration” Faà(𝕏) ⟶ 𝕏 over it. In fact, Faà is a comonad (over the category of Cartesian left (semi-)additive categories). Our main theorem is that the coalgebras for this comonad are precisely the Cartesian differential categories. In a sense, this result affirms the “correctness” of the notion of Cartesian differential categories.

Introduction

Francesco Faà di Bruno (1825-1888) was an Italian of noble birth, a soldier, a mathematician, and a priest. In 1988 he was beatified by Pope John Paul II, apparently for his charitable work teaching young women mathematics. As a mathematician he studied with Cauchy in Paris. He was a tall man with a solitary disposition who spoke seldom and, when teaching class, not always successfully. Perhaps his most significant mathematical contribution concerned the combinatorics of the higher-order chain rules. These results were the cornerstone of “combinatorial analysis”: a subject which never really took off. It is the combinatorics underlying the higher-order chain rule which is of interest to us here. [OR 97, L 09]

The paper is a sequel to our work on Cartesian differential categories [BCS 09]. In that paper we established that from any Cartesian left additive category one could construct a “bundle” fibration in which the fibres were additive, and where the composition had the same form as the chain rule; moreover the existence of a left additive section of this fibration provided an operator which already satisfies many of the axioms of a differential operator. We pointed out in that paper that all the axioms could be generated by a similar fibrational analysis involving the higher-order chain rule. Presenting the details of that claim is the main aim of the present paper.

After some combinatorial preliminaries, we give the definition of the Faà di Bruno category over a Cartesian left additive category 𝕏. The most complicated aspect of the definition is the composition, which we shall see corresponds to the higher-order chain rule. Most of the paper is devoted to proving that the Faà di Bruno construction is in fact a comonad over the category of left additive categories. Finally, we show that the coalgebras of this comonad are exactly Cartesian differential categories.

Received by the editors 2010-09-10 and, in revised form, 2011-09-15.

Transmitted by Robert Paré. Published on 2011-09-19.

2000 Mathematics Subject Classification: 18D10, 18C20, 12H05, 32W99.

Key words and phrases: Higher-order chain rule, Cartesian differential categories, bundle fibration, coalgebras.

\begin{matrix}c \\ ◯ \end{matrix} J.R.B. Cockett and R.A.G. Seely, 2011. Permission to copy for private use granted.

1. Some combinatorics of symmetric trees

Counting trees of various shapes and sizes is a deeply combinatoric subject. It is also an issue which is of no small algebraic and analytic interest as these combinatoric numbers occur as coefficients in formulae such as the higher-order chain rule. Our current preoccupation is not so much with the bald numbers as with the structural relationships which cause these numbers to become important. We start this appreciation by introducing the combinatorial structures which underlie the chain rule.

1.1. Symmetric trees A symmetric tree of height n ≥ 0 and of width m > 0, in variables V = {x_{1}, …, x_{m}}, is defined inductively by:

• The only symmetric tree of height 0 has width 1 and is a variable y;

• A symmetric tree of height n ≥ 1, of width m, in the variables {x_{1}, …, x_{m}}, is an expression •_{r}(t_{1}, …, t_{r}) where each t_{i} is a symmetric tree of height n−1 in the variables V_{i}, where ⨆_{i=1}^{r} V_{i} = V.

Here, the operation • is symmetric (so we are really considering equivalence classes), as indicated in the discussion below.

Note that the inductive step involves splitting the variables into r disjoint non-empty subsets. The combinatorics of this step are classical: Stirling numbers, of the second kind, are precisely the number of ways of partitioning a set with n elements into r non-empty partitions and are often written S(n, r). Thus, we may already begin to see how combinatorics enters into our subject matter.

We may regard these trees in various ways. For what follows an important perspective will be to regard them as algebraic expressions: in this view the operations at the nodes are symmetric, or commutative, thus

•_{r}(t_{1}, …, t_{r}) = •_{r}(t_{σ(1)}, …, t_{σ(r)})

for any permutation σ ∈ S_{r}. One can also regard these expressions as trees (in the graph theoretic sense) in which the leaves are uniquely labeled (as the root or by one of the variables) but in which no other node or edge is labeled. Two symmetric trees are the same if graph theoretically they are isomorphic in a way which respects the leaf labeling.

Here are two representations of the same symmetric tree:

[figure: x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{7}; •; •; •; •; •; •; •; •; x_{7}; x_{6}; x_{2}; x_{1}; x_{4}; x_{5}; x_{3}; •; •; •; •; •; •; •; •]

An important way to regard a symmetric tree of height n and width m is as a chain of surjective maps:

V = V_{0} ⟶ V_{1} ⟶ … ⟶ V_{n−1} = 1

in which V is the set of variables, |V | = m (the width of the tree), |V_{n−1}| = 1, and V_{i} represents the nodes at the i^{th}-level. This way of viewing a symmetric tree suggests a rather compact notation, representing the nodes as equivalence classes of the variables and then equivalence classes of these etc. Thus, a tree of height n can be represented as an element of P^{n}(V), where V is the (non-empty) set of variables and such that the iterated union is of these subsets is just the set of variables. This allows us to represent the height 3 tree above as:

{{{x_{1}, x_{2}}}, {{x_{3}}, {x_{4}, x_{5}}}, {{x_{6}, x_{7}}}}

If one wishes to generate all the symmetric trees of a given height and width one is presented by a combinatoric problem as one must avoid generating trees which are already represented. In fact, as we shall see, there is a simple method for generating these trees. Meanwhile here is a classification of the first few symmetric trees separated by height and width:

width  width  width
1  2  3

hgt

[figure: 1; \begin{matrix}x_{1} \\ • \end{matrix}; x_{1}; x_{2}; •; x_{1}; x_{2}; x_{3}; •]

hgt

[figure: 2; \begin{matrix}x_{1} \\ • \\ • \end{matrix}; x_{1}; x_{2}; •; •; x_{1}; x_{2}; •; •; •; x_{1}; x_{2}; x_{3}; •; •; •; x_{1}; x_{2}; x_{3}; •; •; •; x_{1}; x_{3}; x_{2}; •; •; •; x_{1}; x_{2}; x_{3}; •; •; •; •; x_{1}; x_{2}; x_{3}; •; •]

1.2. The differential of symmetric trees The differential of a symmetric tree τ of height n and width r produces a bag of m trees of height n and width r + 1, where m is the number of nodes of τ. The new trees of the differential are produced by picking a node and adding a “limb” to the new variable. The limb consists of a series of unary nodes applied to the new variable: these unary nodes are necessary in order to retain the uniform height of the tree.

For example the differential (introducing x_{2}) of the tree below is a pair of trees:

\begin{matrix}x_{1} \\ • \\ • \end{matrix} [figure: ∂_{x_{2}}] x_{1} x_{2} • • •  x_{1} x_{2} • •

while the differential, introducing x_{3}, of the following tree (which is the first tree of the derivative above) is three trees:

[figure: x_{1}; x_{2}; •; •; •; ∂_{x_{3}}; x_{1}; x_{2}; x_{3}; x_{1}; x_{3}; x_{2}; •; •; •; •; •; •; •; x_{1}; x_{2}; x_{3}; •; •; •]

1.2.1. Proposition. Every symmetric tree of height h and width d can be obtained as a member of the d^{th}-derivative of the unary tree of the height h, denoted ι_{h}.

Proof. To see this it is perhaps easier to think of the process in reverse: that is of reducing a tree by stripping out the limb of the tree whose leaf is the last introduced variable: that is the leaf and all the unary nodes below that leaf. Notice this process retains the height of the tree but at each step reduces the width by 1. Eventually any tree of height h can be reduced to the unique tree, ι_{h}^{x_{1}}, of the height h and width 1 (on variable x_{1}). Reversing the process thus generates all the trees of the required width and height.

Furthermore, this process never generates the same tree twice. If at some step the same tree had been generated then stripping out the last limb shows that the previous step had also had a tree represented more than once. This means one can preserve the presence of repetition back to the starting point. As, in this case, we started with a single tree, ι_{h}^{x_{1}}, we know there can be no repetitions.

Notation: Recall that ι_{2}^{x_{1}} is the (unique) height 2 width 1 tree with variable x_{1}; by

T_{2}^{V} = T_{2}^{x_{1},...,x_{r}} = ∂_{x_{2},...,x_{r}}(ι_{2}^{x_{1}})

is meant the bag of trees obtained by formally deriving ι_{2}^{x_{1}} r-times with respect to the given variables V = {x_{1}, …, x_{r}}. By the above discussion of the combinatorics of trees we know this is the set of all symmetric trees of height 2 and width r.

2. Faà di Bruno Bundle Categories

Given a Cartesian left additive category, 𝕏, we shall construct two categories which we shall refer to as the Faà di Bruno (bundle) categories, BFaà(𝕏) and a full subcategory Faà(𝕏). The objects of the category BFaà(𝕏) are pairs of objects of the original category (A, X). The objects of Faà(𝕏) are those such pairs where X = A. We shall define the maps in a moment, but it might be worth pausing to remark on the choices of these objects. The more general pairs (A, X) will prove to be unsuitable when we come to our main theorem (characterizing Cartesian differential categories as coalgebras for the comonad Faà), but otherwise the constructions to get us there work most transparently if we keep quite separate the two roles the object A plays (which is why we prefer to take the objects as pairs (A, A) rather than as simply objects A). The more general construction BFaà(𝕏) seems actually to be more natural, and this is an indication that the construction has more general forms which we shall not explore here. In the meantime, at the very least it will help both writers and readers to keep track of variables in positions where they should be additive (where we use A) or not necessarily additive (where we shall use X). That will be apparent immediately, as we define the maps of the categories.

The maps or arrows f: (A, X) ⟶ (B, Y) of the category consist of infinite sequences of maps

f = (f_{∗}, f_{1}, f_{2}, …): (A, X) ⟶ (B, Y)

As the notation suggests the first map in this sequence is of a slightly different nature than the remainder. We require simply that f_{∗}: X ⟶ Y is a map in 𝕏. For r > 0 we require

f_{r}: \underbrace{A × … × A}_{r} ×X ⟶ B

is a symmetric form. This means that it is additive in each of the first r arguments and symmetric in these arguments. (The reader might think of this as f_{r}: A^{⊗^{r}}/r! × X ⟶ B, apart from the unfortunate fact that 𝕏 need not have the tensor ⊗.) It will soon become apparent that the intended interpretation of f_{n} is they will be summands in the expression for higher order differential term. (See the remark following Proposition 2.2.3.)

The difficulty is, of course, to define a composition for these arrows, which is where the Faà di Bruno convolution is used.

2.1. Faà di Bruno convolution The description of the composition fg of two maps in BFaà(𝕏) is our next objective. The easy part is the composition in the first coordinate which is just, as expected, given by the composition in 𝕏. The description of the composition on the remaining coordinates is more involved.

First suppose τ is a symmetric tree of height 2 and width r on the variables V = {x_{1}, …, x_{r}}. This means that τ ∈ T_{2}^{V}. Furthermore, suppose f: (A, X) ⟶ (B, Y) and g: (B, Y) ⟶ (C, Z) in BFaà(𝕏), then by the component of the composite at τ:

(f ⋆ g)_{τ}: \underbrace{A × … × A}_{r} ×X ⟶ C

is meant the map obtained by substituting all the layer one nodes of arity i with f_{i} and the (one) node of τ at layer two with the function g_{j}, where j is the appropriate arity. Thus when τ is the following tree

[figure: x_{1}; x_{2}; x_{4}; x_{3}; •; •; •]

then

(f ⋆ g)_{τ} = g_{2}(f_{1}(x_{3}, x), f_{3}(x_{1}, x_{2}, x_{4}, x), f_{∗}(x)): \underbrace{A × … × A}_{4} ×X ⟶ C.

[figure: x_{1}; x_{2}; x_{4}; x_{3}; x; f_{3}; f_{1}; f_{∗}; g_{2}]

We may replace the single tree τ by any bag T of trees in T_{2}^{V} in which case we simply sum the components

(f ⋆ g)_{T} = ∑_{n·τ∈T} n · (f ⋆ g)_{τ}

The Faà di Bruno convolution composition of f and g is then

(fg)_{r} = (f ⋆ g)_{T_{2}^{x_{1},...,xr}}

which is well-defined as the result is clearly a symmetric form as permuting the variables of any τ ∈ T_{2}^{x_{1},...,x_{r}} either leaves τ fixed or produces a new tree which still has the same height and therefore is in T_{2}^{x_{1},...,x_{r}}. Thus we take this convolution to be the composition in the Faà di Bruno category. We have:

2.1.1. Proposition. For any Cartesian left additive category 𝕏, BFaà(𝕏) (and so Faà(𝕏)) as defined above are Cartesian left additive categories.

Proof. It is quite easily checked that this composition has as identity maps 1 = (1, π_{0}, 0, …): (A, X) ⟶ (A, X). That the composition is associative follows immediately from the fact that the composition is given by summing over all the trees of height 2 (and appropriate width). A threefold composition is then just the sum over all trees of height 3 (and appropriate width) and so immediately associative.

The additive structure on the homsets is given pointwise:

f + g = (f_{∗}, f_{1}, f_{2}, …) + (g_{∗}, g_{1}, g_{2}, …) = (f_{∗} + g_{∗}, f_{1} + g_{1}, f_{2} + g_{2}, …)

This composition is left additive as clearly, with respect to point-wise addition,

(f ⋆ (g + g′))_{τ} = (f ⋆ g_{1})_{τ} + (f ⋆ g_{2})_{τ}

as the underlying category is left additive and it immediately follows that this also holds for bags of such terms.

Furthermore the category has additive products: the product of (A, X) and (B, Y) is (A × B, X × Y), given f: (C, Z) ⟶ (A, X) and g: (C, Z) ⟶ (B, Y) we define ⟨f, g⟩ as (⟨f_{i}, g_{i}⟩)_{i=0}^{∞}. The projections are π_{i} = (π_{i}, π_{0}π_{i}, 0, 0, …) for i = 1, 2 and the diagonal Δ = (Δ, π_{0}Δ, 0, 0, …). These are additive as the first level of the Faà di Bruno category is the bundle fibration.

Clearly we may truncate BFaà(𝕏) to any given number of levels to obtain a left additive category, BFaà_{n}(𝕏), as the composition at any given level always only involves maps from that and lower levels. As mentioned above BFaà_{1}(𝕏) is the more standard bundle fibration of 𝕏 [BCS 09].

Our aim now is to show that the obvious functor

ε: BFaà(𝕏) ⟶ 𝕏 : \begin{matrix}(A, X) & ↦ & X \\ (f_{∗}, f_{1}, f_{2}, …) & ↦ & f_{∗} \end{matrix}

is also a fibration, (and similarly for Faà(𝕏)). Toward this end first note that ε is clearly a left additive functor which preserves the Cartesian structure on the nose. Now consider

[figure: (C.Z); (fg,f_{1},f_{2},...); (f,f_{1},f_{2},...); (A, X); (g,π_{0},0,0); (B, Y); ε; Z; f; X; g; Y]

It is easily checked that the map sitting above f is uniquely determined. Thus we have:

2.1.2. Proposition. For any Cartesian left additive category 𝕏

ε: BFaà(𝕏) ⟶ 𝕏

is a strict Cartesian left additive functor which is a fibration. Similarly, ε: Faà(𝕏) ⟶ 𝕏 is a strict Cartesian left additive functor and a fibration.

The additive maps in a fiber are precisely those of the form (1, f_{1}, 0, 0, …) which above the second component vanish. This means that the fibers are far from being additive.

The maps in the Faà di Bruno category should be thought of as higher-order symmetric forms. When a differential is already present, as for ordinary differential equations, they will not, in general, be realizable as the differential forms of a function. However, what is true - and is the subject of the next section – is that a differentiable function gives rise such a form so that these forms should be viewed as abstract differentiable functions.

2.2. Functorial properties of the Faà di Bruno construction It is worth noting that the Faà di Bruno construction is functorial on the category of Cartesian left additive categories, CLAdd, where the functors are taken to preserve addition and the product structure on the nose:

2.2.1. Lemma. The Faà di Bruno constructions are functors.

BFaà: CLAdd ⟶ CLAdd Faà: CLAdd ⟶ CLAdd

Proof. That these are functors is clear provided we are assured that additivity in an argument is preserved by Cartesian left additive functors, as in that case forms are carried to forms. The fact that this is true relies on the fact that f: A × X ⟶ B is additive in its first argument in a left additive category if and only if ((π_{0} + π_{1}) × 1)f = (π_{0} × 1)f + (π_{1} × 1)f. This property is clearly preserved by the Cartesian left additive functors. We then define:

BFaà: CLAdd ⟶ CLAdd: \xymatrix{𝕏 \ar[d]_{F} \\ 𝕐} ↦ \xymatrix{BFaà(𝕏) \ar[d]^{BFaà(F)} \\ BFaà(𝕐)}

where BFaà(F)(f_{∗}, f_{1}, f_{2}, …) = (F (f_{∗}), F (f_{1}), F (f_{2}), …). Faà is handled the same way (just restrict to the appropriate subcategories).

It is also clear that ε = ε_{𝕏}: BFaà(𝕏) ⟶ 𝕏 is a natural transformation (natural in 𝕏). However, more is true: there is a functor δ = δ_{𝕏}: BFaà(𝕏) ⟶ BFaà(BFaà(𝕏)), introduced below, natural in 𝕏, such that:

2.2.2. Theorem. (BFaà, ε, δ) is a comonad on CLAdd, as is the restriction to Faà.

The remainder of this section is given over to proving this theorem, which we shall do for BFaà, leaving the restriction to Faà to the reader. But first, in order to describe the functor δ: = δ_{𝕏} for some Cartesian left additive category 𝕏, it will be useful to develop some conventions and fix notation. First for f ∈ BFaà(𝕏) we write f = (f_{∗}, f_{1}, f_{2}, …): (A, X) ⟶ (B, Y) where

f_{∗}: X ⟶ Y ; x ↦ f_{∗}(x)
f_{n}: A^{n} × X ⟶ B ; (a_{∗1}, …, a_{∗n}, x) ↦ f_{n}(x) · a_{∗1} · . . . · a_{∗n}

Notice that we have “highlighted” the additive arguments by writing them as if they were simple multipliers. This should seem very familiar to the reader familiar with the term calculus for Cartesian differential categories from [BCS 09]; this is intended, of course.

We then define δ: BFaà(𝕏) ⟶ BFaà(BFaà(𝕏)) as follows: on objects, δ takes (A, X) to ((A, A), (A, X)). On arrows, f ↦ δ(f) = (f, f^{[1]}, f^{[2]}, …) by setting

f_{∗}^{[n]}: A^{n} × X ⟶ B : (a_{∗1}, …, a_{∗n}, x) ↦ f_{n}(x) · a_{∗1} · . . . · a_{∗n}
f_{r}^{[n]}: (A^{n} × A)^{r} × (A^{n} × X) ⟶ B :

( \begin{matrix}a_{11} … a_{1n} & a_{1∗} \\ ⋮ & ⋮ \\ a_{r1} … a_{rn} & a_{r∗} \\ a_{∗1} … a_{∗n} & x \end{matrix} ) ↦ ∑_{\begin{matrix}s ≤ n & s ≤ r \\ & ramp_{r,n}^{s}(α | γ) \end{matrix}} f_{r+n−s}(x) · a_{α_{1}1} · . . . · a_{α_{n}n} · a_{γ_{1∗}} · . . . · a_{γ_{r−s ∗}}

where ramp_{r,n}^{s}(α | γ) is a condition defined as follows. α is an injection {1, 2, …, n} ⟶ {∗, 1, 2, …, r} (which we shall denote n ⟶ r∪∗ for brevity), with the property that the inverse image α^{−1}({∗}) of ∗ has size r − s. γ is an injection r − s ⟶ r, whose image is disjoint from that of α (meaning no α_{i} can equal any γ_{j}). The effect of this is to assign s linear arguments of the form a_{ij}, n − s arguments of the form a_{∗j}, and r − s arguments of the form a_{j∗} in such a way that the selected linear arguments will include just one from each column and just one from each row (including the bottom row and the right column, but not = x, which is not linear).

Another way to express this is to say that there is an equality of bags:

ramp_{r,n}^{s}(α | γ) iff ⟅ α_{1}, …, α_{n}, γ_{1}, …, γ_{r−s}⟆ = ⟅(n − s) · ∗, 1, …, r⟆

This is a little complicated, so we shall look at this several ways. First let us explicitly develop some of these terms. First consider f^{[0]}: this is just f as the ramp condition forces all the action into the indices for the a_{i∗} and so there is no choice. We shall display this sequence in the term logic as follows:

( \overline{x} ) ↦ f_{∗}(x)
( \frac{a_{1∗}}{x} ) ↦ f_{1}(x) · a_{1∗}

( \begin{matrix}a_{1∗} \\ a_{2∗} \\ x \end{matrix} ) ↦ f_{2}(x) · a_{1∗} · a_{2∗}
…

Now consider f^{[1]}:

( \overline{a_{∗1} x} ) ↦ f_{1}(x) · a_{∗1}
( \begin{matrix}a_{11} & a_{1∗} \\ a_{∗1} & x \end{matrix} ) ↦ \begin{matrix}f_{2}(x) · a_{∗1} · a_{1∗} \\ +f_{1}(x) · a_{11} \end{matrix}

( \begin{matrix}a_{11} & a_{1∗} \\ a_{21} & a_{2∗} \\ a_{∗1} & x \end{matrix} ) ↦ \begin{matrix}f_{3}(x) · a_{∗1} · a_{1∗} · a_{2∗} \\ +f_{2}(x) · a_{21} · a_{1∗} \\ +f_{2}(x) · a_{11} · a_{2∗} \end{matrix}
…

Notice how the domain is specified as a product with 2 components, then 4 components, then 6 components, … Here are the first few terms of f^{[2]}:

( \overline{a_{∗1} a_{∗2} x} ) ↦ f_{2}(x) · a_{∗1} · a_{∗2}
( \begin{matrix}a_{11} a_{12} & a_{1∗} \\ a_{∗1}a_{∗2} & x \end{matrix} ) ↦ \begin{matrix}f_{3}(x) · a_{∗1} · a_{∗2} · a_{1∗} \\ +f_{2}(x) · a_{11} · a_{∗2} \\ +f_{2}(x) · a_{∗1} · a_{12} \end{matrix}

( \begin{matrix}a_{11} a_{12} & a_{1∗} \\ a_{21} a_{22} & a_{2∗} \\ a_{∗1} a_{∗2} & x \end{matrix} ) ↦ \begin{matrix}f_{4}(x) · a_{∗1} · a_{∗2} · a_{1∗} · a_{2∗} \\ +f_{3}(x) · a_{21} · a_{∗2} · a_{1∗} \\ +f_{3}(x) · a_{∗1} · a_{22} · a_{1∗} \\ +f_{3}(x) · a_{11} · a_{∗2} · a_{2∗} \\ +f_{3}(x) · a_{∗1} · a_{12} · a_{2∗} \\ +f_{2}(x) · a_{11} · a_{22} \\ +f_{2}(x) · a_{21} · a_{12} \end{matrix}

…

We may visualize this as a combinatoric process in which we start with a symmetric tree with one node with variables at the base level 0 and either adding a completely new dotted branch to an a at the current level or turn one of the existing solid branches into a dotted branch while attaching it to the new variable at the current level corresponding to its original variable:

[figure: a_{∗1}; a_{∗2}; a_{∗2}; •; ↦; a_{∗1}; a_{∗2}; a_{∗3}; a_{1∗}; •; a_{11}; a_{∗2}; a_{∗3}; •; a_{∗1}; a_{12}; a_{∗3}; •; a_{∗1}; a_{∗2}; a_{13}; •]

The next step then has two dotted branches entering each node. Here are the results of applying this process to two of the trees produced above:

[figure: a_{∗1}; a_{∗2}; a_{∗3}; a_{1∗}; •; ↦; a_{∗1}; a_{∗2}; a_{∗3}; a_{1∗}; a_{2∗}; •; a_{∗1}; a_{22}; a_{∗3}; a_{1∗}; •]

[figure: a_{∗1}; a_{22}; a_{∗3}; a_{1∗}; •; a_{∗1}; a_{∗2}; a_{23}; a_{1∗}; •]

[figure: a_{11}; a_{∗2}; a_{∗3}; •; ↦; a_{11}; a_{∗2}; a_{∗3}; a_{2∗}; •; a_{11}; a_{22}; a_{∗3}; •; a_{11} a_{∗2} a_{23} •]

As before we then clothe these trees with the particular forms:

[figure: a_{∗1}; a_{22}; a_{∗3}; a_{1∗}; x; f_{4}]

to obtain the expressions for f^{[n]} as described above.

The ramp condition can also be described by selecting partial isomorphisms from r to n, and thereby selecting certain entries from the following ‘augmented’ r by n variable base:

( \begin{matrix}a_{11} … a_{1n} & a_{1∗} \\ ... & ⋮ \\ a_{r1} … a_{rn} & a_{r∗} \\ a_{∗1} … a_{∗n} & x \end{matrix} )

The selection process involves choosing a partial isomorphism σ between the top r rows and leftmost n columns, that is to say choosing places in the array subject to the following rules:

• At most one variable must be chosen from each of the top r rows (one cannot choose from the bottom row);

• At most one variable may be chosen from each of the leftmost n columns (one cannot choose from the rightmost column).

(We call this a “scatter set”.) Here is an example when n = 4 and r = 5: σ is given by

( \begin{matrix}a_{11} a_{12} a_{13} a_{14} & a_{1∗} \\ a_{21} a_{22} a_{23} a_{24} & a_{2∗} \\ a_{31} a_{32} a_{33} a_{34} & a_{3∗} \\ a_{41} a_{42} a_{43} a_{44} & a_{4∗} \\ a_{51} a_{52} a_{53} a_{54} & a_{5∗} \\ a_{∗1} a_{∗2} a_{∗3} a_{∗4} & x \end{matrix} ) ⇝^{σ}  ( \begin{matrix}a_{11} a_{12} a_{13} a_{14} & a_{1∗} \\ a_{21} a_{22} a_{23} a_{24} & a_{2∗} \\ a_{31} a_{32} a_{33} a_{34} & a_{3∗} \\ a_{41} a_{42} a_{43} a_{44} & a_{4∗} \\ a_{51} a_{52} a_{53} a_{54} & a_{5∗} \\ a_{∗1} a_{∗2} a_{∗3} a_{∗4} & x \end{matrix} )

This selection can now can be “clothed” as above to represent the term f^{σ}:

( \begin{matrix}a_{11} a_{12} a_{13} a_{14} & a_{1∗} \\ a_{21} a_{22} a_{23} a_{24} & a_{2∗} \\ a_{31} a_{32} a_{33} a_{34} & a_{3∗} \\ a_{41} a_{42} a_{43} a_{44} & a_{4∗} \\ a_{51} a_{52} a_{53} a_{54} & a_{5∗} \\ a_{∗1} a_{∗2} a_{∗3} a_{∗4} & x \end{matrix} ) ↦ f^{σ} = f_{6}(x) · a_{11} · a_{52} · a_{∗3} · a_{34} · a_{2∗} · a_{4∗}

The function f_{6} is selected since if s coordinates are selected one needs n + r − s linear arguments. In this case three coordinates were selected so n + r − s = 4 + 5 − 3 = 6 linear arguments are required. The linear arguments of f are determined by putting in the selected arguments and arguments from the bottom row and rightmost column corresponding to the rows and columns not containing a selected argument.

In general, given a partial isomorphism σ: r ⟶ n, let

σ_{∗} = σ ∪ {(x, ∗) | x ∈ r \ π_{1}σ} ∪ {(∗, y) | y ∈ n \ π_{2}σ}

Note that the set σ_{∗} has r + n − |σ| elements. Then we set f^{σ} = f_{m}(x) •_{(i, j) ∈ σ_{∗}} a_{i,j}, where m = n + r − |σ|.

Then it is clear that the term f_{r}^{[n]} is then mapped under δ to the sum of the clothed scatter sets for the r by n augmented argument matrix with which we started:

2.2.3. Proposition.

f_{r}^{[n]} = ∑_{σ∈ParIso(r,n)} f^{σ}

This perspective suggests a symmetry between f_{r}^{[n]} and f_{n}^{[r]} by transposition; of course this is only possible if the types A and X are the same.

Remark: It might help the reader if, at this stage, we recall that the intended interpretation of f_{r}^{[n]} is the differential term

\frac{d^{r}f(x) · a_{1∗} · · · · · a_{n∗}}{d(x, a_{1∗}, …, a_{n∗})} (a_{1∗}, …, a_{n∗}, x) · (a_{11}, …, a_{1n}, a_{1∗}) · · · · · (a_{r1}, …, a_{rn}, a_{r∗})

We shall return to this point when we consider coalgebras later.

2.2.4. Lemma.

(i) f_{r}^{[n]} is an additive symmetric form in its first r arguments;

(ii) (f + g)_{r}^{[n]} = f_{r}^{[n]} + g_{r}^{[n]};

(iii) For any Cartesian left additive functor F, BFaà(F)(f^{[p]}) = (BFaà(F)(f))^{[p]};

Proof.

(i) Recall that f_{r}^{[n]} has the following form:

f_{r}^{[n]}: (A^{n} × A)^{r} × (A^{n} × X) ⟶ B :

( \begin{matrix}a_{11} … a_{1n} & a_{1∗} \\ ⋮ & ⋮ \\ a_{r1} … a_{rn} & a_{r∗} \\ a_{∗1} … a_{∗n} & x \end{matrix} ) ↦ ∑ ; \begin{matrix}s ≤ n & s ≤ r \\ & ramp_{r,n}^{s}(α | γ) \end{matrix}f_{r+n−s}(x) · a_{α_{1}1} · . . . · a_{α_{n}n} · a_{γ_{1∗}} · . . . · a_{γ_{r−s ∗}}

we must show that this term is additive in (a_{i1} … a_{in} a_{i∗}) (i > 0). However, note that in each term there is only one occurrence of a variable from any i^{th}-level when i > 0. This makes the term additive in that variable and thus the whole term is additive in the whole level.

(ii) This is immediate as the “differential” in this second sense clearly preserves addition.

(iii) We have:

BFaà(F)(f^{[p]}) = (F (f_{∗}^{[p]}), F (f_{1}^{[p]}), F (f_{2}^{[p]}), …)
= (F (f)_{∗}^{[p]}, F (f)_{1}^{[p]}, F (f)_{2}^{[p]}, …)
= BFaà(F)(f)^{[p]}

where the penultimate step uses the fact that a left-additive functor preserves all the structure used to construct f_{r}^{[n]}.

Our first objective is to show why the following is true:

2.2.5. Proposition. δ: BFaà(𝕏) ⟶ BFaà(BFaà(𝕏)) is a functor which is (as a transformation δ_{𝕏}) natural in 𝕏.

Of course, this is not so easy as δ itself involves some combinatorics and the composition in the Faà di Bruno categories is also combinatoric. In fact, just the composition in BFaà(BFaà(𝕏)) is a small challenge to understand. This is what we discuss next.

A map in BFaà(BFaà(𝕏)), f: ((A, X), (A′, X′)) ⟶ ((B, Y), (B′, Y′)) is a doubly indexed array

f_{∗,∗} f_{1,∗} f_{2,∗} f_{3,∗} f_{4,∗} …
f_{∗,1} f_{1,1} f_{2,1} f_{3,1} f_{4,1} …
f_{∗,2} f_{1,2} f_{2,2} f_{3,2} f_{4,2} …
f_{∗,3} f_{1,3} f_{2,3} f_{3,3} f_{4,3} …
f_{∗,4} f_{1,4} f_{2,4} f_{3,4} f_{4,4} …

…

where the columns are maps in BFaà(𝕏):

f_{∗} = (f_{∗,∗}, f_{∗,1}, …): (A′, X′) ⟶ (B′, Y′); x ↦ f_{∗}(x)
f_{n} = (f_{n,∗}, f_{n,1}, …): (A, X)^{n} × (A′, X′) = (A^{n} × A′, X^{n} × X′) ⟶ (B, Y);
(a_{1}, …, a_{n} | x) ↦ f_{n}(x) · a_{1} · . . . · a_{n}

so that the individual maps look like:

f_{∗,∗} : X′ ⟶ Y′; x ↦ f_{∗,∗}(x)
f_{∗,n} : A′^{n} × X′ ⟶ B′; (a_{∗1}, …, a_{∗n} | x) ⟶ f_{∗,n}(x) · a_{∗1} · . . . · a_{∗n}

f_{n,∗} : X^{n} × X′ ⟶ Y; ( \begin{matrix}a_{1} \\ … \\ a_{n} \\ x \end{matrix} ) ↦ f_{n,∗} ( \begin{matrix}a_{1} \\ … \\ a_{n} \\ x \end{matrix} )

f_{n,m} : (A^{n} × A′)^{m} × (X^{n} × X′) ⟶ B;

( \begin{matrix}a_{11} & … & a_{1m} & a_{1} \\ & … \\ a_{n1} & … & a_{nm} & a_{n} \\ a_{∗1} & … & a_{∗m} & x \end{matrix} ) ↦ f_{n,m} ( a_{1} ; ⋮ ; a_{n} ; x ) · ( a_{11} ; ⋮ ; a_{n1} ; a_{∗1} ) · . . . · ( a_{1m} ; ⋮ ; a_{nm} ; a_{∗m} )

The first difficulty is to describe what a composition in BFaà(BFaà(𝕏)) looks like; to show that δ preserves composition we shall need a very concrete description of this composition. The composition in BFaà(BFaà(𝕏)) has two levels: the first step is a convolution over trees clothed from BFaà(𝕏): but the compositions in these trees must then, in turn, be translated out into convolutions. We shall now describe the effect of this in one step by describing (fg)_{i,j} as

(fg)_{i,j} = ∑_{τ∈T_{2}^{i}} ∑_{τ′∈T_{2}^{j}}(f ⋆ g)_{(τ×τ′)}

To explain this we must, in turn, unravel the notation (f ⋆ g)_{(τ×τ′)}. To do this we first need to explain what the tree τ × τ′ looks like. For this it is convenient to view a tree, τ, of height n, as being given by a chain of surjective maps:

X = X_{0} ⟶ X_{1} ⟶ … ⟶ X_{n−2} ⟶ X_{n−1} = 1

where X_{0} is the set of variables and X_{i}, for 0 < i < n are the symmetric operations. If τ′ is another such tree of height n

Y = Y_{0} ⟶ Y_{1} ⟶ … ⟶ Y_{n−2} ⟶ Y_{n−1} = 1

then their product, τ × τ′ is the tree:

X × Y = X_{0} × Y_{0} ⟶ X_{1} × Y_{1} ⟶ … ⟶ X_{n−2} × Y_{n−2} ⟶ X_{n−1} × Y_{n−1} = 1

Note that in this tree each operation h = (h_{1}, h_{2}) ∈ X_{i} × Y_{i} has a matrix of arguments whose two dimensions are the number of arguments of h_{1} and the number of arguments of h_{2}. Consider the two height 2 trees:

τ_{1} = •_{2}(•_{2}(a_{1}, a_{3}), •_{2}(a_{2}, a_{4})) and τ_{2} = •_{2}(•_{3}(a_{1}, a_{2}, a_{4}), •_{1}(a_{3}))

the product tree may be presented as

τ_{1} × τ_{2} = •_{2,2} ( \begin{matrix}•_{2,3} ( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,4} \\ a_{3,1} & a_{3,2} & a_{3,4} \end{matrix} ) & •_{2,1} ( \begin{matrix}a_{1,3} \\ a_{3,3} \end{matrix} ) \\ •_{2,3} ( \begin{matrix}a_{2,1} & a_{2,2} & a_{2,4} \\ a_{4,1} & a_{4,2} & a_{4,4} \end{matrix} ) & •_{2,1} ( \begin{matrix}a_{2,3} \\ a_{4,3} \end{matrix} ) \end{matrix} )

As before we must clothe the tree to form (f ⋆g)_{(τ_{1}×τ_{2})} where this time f, g ∈ BFaà(BFaà(𝕏)). Recall that this means each of f and g are specified by infinite dimensional arrays and each f_{i,j} has an i + 1 by j + 1 dimensional argument list (as opposed to i by j dimensional shown above). Thus we need to fill in the “fringes” which is accomplished as follows:

(f ⋆ g)_{(τ_{1}×τ_{2})} = g_{2,2} ( \begin{matrix}f_{2,3} ( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,4} & a_{1} \\ a_{3,1} & a_{3,2} & a_{3,4} & a_{3} \\ a_{∗,1} & a_{∗,2} & a_{∗,4} & x \end{matrix} ) & f_{2,1} ( \begin{matrix}a_{1,3} & a_{1} \\ a_{3,3} & a_{3} \\ a_{∗,3} & x \end{matrix} ) & f_{2,∗} ( \begin{matrix}a_{1} \\ a_{3} \\ x \end{matrix} ) \\ f_{2,3} ( \begin{matrix}a_{2,1} & a_{2,2} & a_{2,4} & a_{2} \\ a_{4,1} & a_{4,2} & a_{4,4} & a_{4} \\ a_{∗,1} & a_{∗,2} & a_{∗,4} & x \end{matrix} ) & f_{2,1} ( \begin{matrix}a_{2,3} & a_{2} \\ a_{4,3} & a_{4} \\ a_{∗,3} & x \end{matrix} ) & f_{2,∗} ( \begin{matrix}a_{2} \\ a_{4} \\ x \end{matrix} ) \\ f_{∗,3} ( a_{∗,1} a_{∗,2} a_{∗,4} x ) & f_{∗,1} ( a_{∗,3} x ) & f_{∗,∗} (x) \end{matrix} )

This then explains what the composition is in BFaà(BFaà(𝕏)).

Proof (of 2.2.5) Our objective is to show that δ preserves composition, thus that δ(f)δ(g) = δ(fg). We show that each is the sum of the same set of composites; formally, the proof is given by the following equations.

δ(f)δ(g) = ∑_{τ_{1},τ_{2}}(δ(f) ⋆ δ(g))_{τ_{1}×τ_{2}}  (1)

= ∑_{τ_{1},τ_{2}} (( ∑_{σ:i⟶j} f^{σ})_{ij} ⋆ ( ∑_{σ′:k⟶l} g^{σ′})_{kl})_{τ_{1}×τ_{2}}  (2)

= ∑_{τ_{1},τ_{2}} (∑_{σ′} g^{σ′}) ( ∑_{σ_{ij}:α_{i}⟶β_{j}} f^{σ_{ij}} )_{ij}  (3)

= ∑_{τ_{1},τ_{2}} ∑_{σ′} g^{σ′} (∑_{σ_{ij}} f^{σ_{ij}} )_{ij}  (4)

= ∑_{τ_{1},τ_{2}} ∑_{σ′} g^{σ′} (∑_{σ_{ij}} f^{σ_{ij}} )_{ij∈σ′}  (5)

= ∑_{τ_{1},τ_{2}} ∑_{σ′,σ_{ij},ij∈σ′} g^{σ}(…, f^{σ_{ij}}, …)  (6)
= ∑_{σ:n⟶m} ∑_{τ∈T_{σ∗}}(f ⋆ g)_{τ}^{σ}  (7)
= δ(fg)  (8)

Equations (1 – 3), and (8) are definitional; (4 – 6) are consequences of additivity; the combinatorial heart of the proof rests with equation (7), which amounts to the following lemma.

2.2.6. Lemma. There is an equivalence between the following two sets of data:

• Partitions τ_{1} = (α_{1}, …, α_{k}), τ_{2} = (β_{1}, …, β_{l}) and partial isomorphisms σ′: k ⟶ l and σ_{ij}: α_{i} ⟶ β_{j} for (i, j) ∈ σ′

• Partial isomorphism σ: n ⟶ m and a partition τ of σ_{∗}

where n is the set partitioned by τ_{1}, m the set partitioned by τ_{2}, and σ is the union of the σ_{ij}.

Proof (of 2.2.6) In this proof, we shall represent a partial isomorphism as the set of pairs (i, j) where i ↦ j. To start with, we suppose we are given partitions τ_{1} = (α_{1}, …, α_{k}), τ_{2} = (β_{1}, …, β_{l}) and partial isomorphisms σ′: k ⟶ l and σ_{ij}: α_{i} ⟶ β_{j} for (i, j) ∈ σ′ We must construct τ, a partition of σ_{∗}.

Recall that for a partial isomorphism σ: n ⟶ m,

σ_{∗} = σ ∪ {(x, ∗) | x ∈ n \ π_{1}σ} ∪ {(∗, y) | y ∈ m \ π_{2}σ}

and that |σ_{∗}| = n + m − |σ|. In addition, we shall write σ_{i} = ⋃_{j} σ_{ij} and σ_{j} = ⋃_{i} σ_{ij} (and similarly for σ_{i∗}, σ_{j∗}).

We define a partition τ on σ_{∗} as

τ = {σ_{ij∗}}_{(i,j)∈σ′} ∪ {((α_{i} \ π_{1}σ_{i}) × {∗}) \ σ_{i∗}}_{i∈k} ∪ {({∗} × (β_{j} \ π_{2}σ_{j})) \ σ_{j∗}}_{j∈l}

This means that pairs from the same σ_{ij∗} end up in the same partition, and pairs with a ∗ end up in the same partition if the “other” elements come from the same α_{i} or β_{j} (and aren’t already in some σ_{ij∗}).

This completes one direction of the equivalence.

Example:

τ_{1} = ((1, 3), (2, 5), (4, 6))
τ_{2} = ((1, 2, 4), (3), (5)) (so k = l = 3)
σ′: 3 ⟶ 3 = {(1, 3), (3, 1)} (so e.g. (2, 2) is not in σ)
σ_{13}: {1, 3} ⟶ {5} = {(3, 5)}
σ_{31}: {4, 6} ⟶ {1, 2, 4} = {(4, 4), (6, 1)}

Then σ = ⋃_{ij} σ_{ij}: 6 ⟶ 5 = {(3, 5), (4, 4), (6, 1)} and n = 6, m = 5, |σ| = 3

Furthermore we have

σ_{∗} = {(3, 5), (4, 4), (6, 1), (1, ∗), (2, ∗), (5, ∗), (∗, 2), (∗, 3)}
σ_{13∗} = {(3, 5), (1, ∗)}
σ_{31∗} = {(4, 4), (6, 1), (∗, 2)}

and so

τ = (((4, 4), (6, 1), (∗, 2)), ((3, 5), (1, ∗)), ((2, ∗), (5, ∗)), ((∗, 3)))

Before proceeding to the other direction, let’s consider what’s going on. The given partitions and partial isomorphisms amount to this selection from a variable base:

( \begin{matrix}( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,4} \\ a_{3,1} & a_{3,2} & a_{3,4} \end{matrix} ) & ( \begin{matrix}a_{1,3} \\ a_{3,3} \end{matrix} ) & ( a_{1,5} ; a_{3,5} ) \\ ( \begin{matrix}a_{2,1} & a_{2,2} & a_{2,4} \\ a_{5,1} & a_{5,2} & a_{5,4} \end{matrix} ) & ( \begin{matrix}a_{2,3} \\ a_{5,3} \end{matrix} ) & ( \begin{matrix}a_{2,5} \\ a_{5,5} \end{matrix} ) \\ ( \begin{matrix}a_{4,1} & a_{4,2} & a_{4,4} \\ a_{6,1} & a_{6,2} & a_{6,4} \end{matrix} ) & ( \begin{matrix}a_{4,3} \\ a_{6,3} \end{matrix} ) & ( \begin{matrix}a_{4,5} \\ a_{6,5} \end{matrix} ) \end{matrix} )

and it’s clear that what both sets of data are defining is the following term from the sums that define δ(f)δ(g) and δ(fg):

g_{4}(x) · (f_{3}(x) · a_{44} · a_{61} · a_{∗2}) · (f_{2}(x) · a_{35} · a_{1∗}) · (f_{2}(x) · a_{2∗} · a_{5∗}) · (f_{1}(x) · a_{∗3})

Now we turn to consider the other direction of the equivalence:

Suppose we are given a partial isomorphism σ: n ⟶ m and a partition τ of σ_{∗}. We must construct partitions τ_{1} = (α_{1}, …, α_{k}), τ_{2} = (β_{1}, …, β_{l}) and partial isomorphisms σ′: k ⟶ l and σ_{ij}: α_{i} ⟶ β_{j} for (i, j) ∈ σ′, of appropriate sizes.

Since τ is a partition of a matrix, we easily obtain partitions τ_{1}, τ_{2} of the rows and columns: define π′_{i}γ = π_{i}γ \ {∗}, and let τ̂ = (γ_{1}, …, γ_{p}); then define τ_{1} = (π′_{1}γ_{i})_{i} and τ_{2} = (π′_{2}γ_{i})_{i}

We can also construct partial isomorphisms from τ, by ignoring the pairs with ∗s, and taking the remaining pairs from each partition: let τ_{1} = (α_{1}, …, α_{k}) and τ_{2} = (β_{1}, …, β_{l}) and then define σ′ = {(i, j) | (α_{i}×β_{j})∩σ_{∗} ≠ ∅} and, for (i, j) ∈ σ′, define σ_{ij} = (α_{i}×β_{j})∩σ_{∗}. Note that by this construction, σ is the union of these partial isomorphisms, as required.

This completes the other direction of the equivalence; that these processes are inverse is clear from their construction.

Example: Let’s take the σ of the previous example, with a new τ:

σ: 6 ⟶ 5 = {(3, 5), (4, 4), (6, 1)}
so σ_{∗} = {(3, 5), (4, 4), (6, 1), (1, ∗), (2, ∗), (5, ∗), (∗, 2), (∗, 3)}
τ = (((3, 5)), ((4, 4), (6, 1)), ((1, ∗), (2, ∗), (∗, 3)), ((5, ∗), (∗, 2)))

Then we obtain

τ_{1} = ((3), (4, 6), (1, 2), (5)) and τ_{2} = ((5), (4, 1), (3), (2))

(note k = l = 4, and n = 6, m = 5 as required).

Then σ′ = {(1, 1), (2, 2)} (since {(3, 5)} is a pair from σ_{∗} coming from the first partition in τ_{1} and the first partition in τ_{2}, and {(4, 4), (6, 1)} are pairs in σ_{∗} coming from the second partition in τ_{1} and the second partition in τ_{2}). Also σ_{11} = {(6, 1)} and σ_{22} = {(4, 4), (3, 5)}, whose union is the σ: 6 ⟶ 5 = {(3, 5), (4, 4), (6, 1)} we started with.

Again, one might wonder what’s going on.

This time we have the following selection from the variable base:

( \begin{matrix}( a_{3,5} ) & ( a_{3,4} a_{6,3} ) & ( a_{3,3} ) & ( a_{3,2} ) \\ ( \begin{matrix}a_{4,5} \\ a_{6,5} \end{matrix} ) & ( \begin{matrix}a_{4,4} & a_{4,1} \\ a_{6,4} & a_{6,1} \end{matrix} ) & ( \begin{matrix}a_{4,3} \\ a_{6,3} \end{matrix} ) & ( \begin{matrix}a_{4,2} \\ a_{6,2} \end{matrix} ) \\ ( \begin{matrix}a_{1,5} \\ a_{2,5} \end{matrix} ) & ( \begin{matrix}a_{1,4} & a_{1,1} \\ a_{2,4} & a_{2,1} \end{matrix} ) & ( \begin{matrix}a_{1,3} \\ a_{2,3} \end{matrix} ) & ( \begin{matrix}a_{1,2} \\ a_{2,2} \end{matrix} ) \\ ( a_{5,5} ) & ( a_{5,4} a_{5,1} ) & ( a_{5,3} ) & ( a_{5,2} ) \end{matrix} )

and the common function term corresponding to this is

g_{6}(x) · (f_{1}(x) · a_{35}) · (f_{2}(x) · a_{44} · a_{61}) · (f_{2}(x) · a_{1∗} · a_{2∗}) · (f_{1}(x) · a_{5∗}) · (f_{1}(x) · a_{∗3}) · (f_{1}(x) · a_{∗2})

Figure 1: A 3-D scatter set

It is clear that δ preserves identities and that it is natural, as is evident from its combinatorial construction, completing our proof of 2.2.5.

It is also easy to see that δε = F and δBFaà(ε) = 1_{BFaà(𝕏)}. It remains to show that the comultiplication is associative:

Proof (of 2.2.2) To show it is a comonad we need to show that δ(δ(f)) = BFaà(δ)(δ(f)). We know that δ(δ(f)) is defined to be a “matrix” (δ(f)_{r}^{[n]})_{rn}, where δ(f)_{r}^{[n]} = ∑_{σ:r⟶n} δ(f)^{σ},

in this case, the sum being a sum of “vectors”

δ(f)^{σ} = f^{[|σ_{∗}|]}(x) •_{i∈σ} a_{i,σ(i)} •_{i∉π_{1}σ} a_{i,∗} •_{j∉π_{2}σ} a_{∗,j}

where the a_{i,j} (etc.) are vectors of terms; notice that we have a 3-D variable base matrix here.

Look at the m^{th} coordinate of f^{[|σ_{∗}|]}: f_{m}^{[|σ_{∗}|]} = ∑_{σ′:(n+r−|σ|)⟶m} f^{σ′}. Regard the a_{i,j}, a_{i,∗}, a_{∗,j} as

columns in a 3-D matrix. It is from these column-positions that σ picks out a scatter set, and σ′ picks (from each column) a “height” (including “height 0” if it doesn’t choose one). No two columns can have the same chosen “height” (other than 0). An illustration of such a situation may be seen in Figure 1, where the rows and columns with 0s in their entries are removed from the sides of the cube, and where the partial isomorphisms are indicated by shading the columns (σ) and indicating their heights (σ′: note that two selected columns have 0 height, and so are not picked by σ′).

With this intuition (in which we have replaced ∗ by 0), we can regard the situation as a three dimensional infinite array of maps f_{r,n,m} where the domain of the map is given by a three dimensional matrix of variables:

(a_{i,j,k})_{\begin{matrix}i = 0 … p \\ j = 0 … q \\ k = 0 … r \end{matrix}}

The components of f_{r,n,m} are given by choosing a “scattered” subset

σ ⊂_{sc} {(i, j, k) | i = 0 … r, j = 0 … n, k = 0 … m}

where being scattered means that:

• For each (i, j, k) ∈ σ at least two of i, j, and k are non-0 (i.e. not ∗);

• If (i, j, k), (i′, j′, k′) ∈ σ then either they are equal or i ≠ i′, j ≠ j′ and k ≠ k′.

To each scattered subset we can associate a term f_{σ} where

f_{σ} = f_{l}(x) • \{a_{i,j,k} | \begin{matrix}(i, j, k) ∈ S \\ ∨(j = k = 0 ∧ (i, , ) ∉ S) \\ ∨(i = k = 0 ∧ ( , j, ) ∉ S) \\ ∨(i = j = 0 ∧ ( , , k) ∉ S) \end{matrix} \}

(where l = m + n + r − (| σ | + | σ′ |)), and then

f_{r,n,m} = (a_{i,j,k}) ↦ ∑_{σ} f_{σ}

The point is that BFaà(δ)(δ(f)) chooses exactly the same sort of 3-D scatter set, the term above being the natural 3-D generalization of σ_{∗}, albeit possibly making the choice in a different order, and so produces the same sum, and so equals δ(δ(f)).

We have arrived at the point now where we want to take the subfibration Faà as our main focus. We want to show that a coalgebra for this comonad, i.e. a Cartesian left additive category 𝕏 with a functor D: 𝕏 ⟶ Faà(𝕏) such that Dε = 1 and DFaà(D) = Dδ, in fact consists of a Cartesian left additive category 𝕏 with a differential combinator D, making 𝕏 a Cartesian differential category.

First let us observe what happens on objects. Setting D(X) = (D_{0}(X), D_{1}(X)) and using the first coalgebra equation gives X = ε(D(X)) = ε(D_{0}(X), D_{1}(X)) = D_{1}(X) so that we have D_{1}(X) = X. Using the second coalgebra equation we have:

(DFaà(D))(X) = Faà(D)(D(X)) = Faà(D)(D_{0}(X), X) = ((D_{0}(D_{0}(X)), D_{0}(X))(D_{0}(X), X))

(Dδ)(X) = δ(D_{0}(X), X) = ((D_{0}(X), D_{0}(X)), (D_{0}(X), X))

so that D_{0}(D_{0}(X)) = D_{0}(X), that is D_{0} is an idempotent on objects. But in Faà(𝕏), the objects were pairs (A, A), rather than the more general (A, X). So in fact, since D_{0}(X) = D_{1}(X) = X, D_{0} is more than idempotent: it is the identity on objects.

The fact that we have a functor into the Faà di Bruno category means we have a functor into the ordinary bundle category and this immediately means that [CD.1]-[CD.5] [BCS 09] hold for the combinator

{A ⟶^{f} B \atop A × A ⟶_{D[f] = f^{(1)}} B}

where we write D(f) = (f, f^{(1)}, f^{(2)}, …), the first entry being forced to be the original function f by the unit equation for coalgebras. The second coalgebra equation, DFaà(D) = Dδ, then equates two different tables of functions:

Faà(D)(D(f)) = ( \begin{matrix}f & f^{(1)} & f^{(2)} & f^{(3)} & f^{(4)} & … \\ f^{(1)} & (f^{(1)})^{(1)} & (f^{(2)})^{(1)} & (f^{(3)})^{(1)} & (f^{(4)})^{(1)} & … \\ f^{(2)} & (f^{(1)})^{(2)} & (f^{(2)})^{(2)} & (f^{(3)})^{(2)} & (f^{(4)})^{(2)} & … \\ f^{(3)} & (f^{(1)})^{(3)} & (f^{(2)})^{(3)} & (f^{(3)})^{(3)} & (f^{(4)})^{(3)} & … \\ f^{(4)} & (f^{(1)})^{(4)} & (f^{(2)})^{(4)} & (f^{(3)})^{(4)} & (f^{(4)})^{(4)} & … \\ … \end{matrix} )

δ(D(f)) = ( \begin{matrix}f & D(f)_{∗}^{[1]} & D(f)_{∗}^{[2]} & D(f)_{∗}^{[3]} & D(f)_{∗}^{[4]} & … \\ f^{(1)} & D(f)_{1}^{[1]} & D(f)_{1}^{[2]} & D(f)_{1}^{[3]} & D(f)_{1}^{[4]} & … \\ f^{(2)} & D(f)_{2}^{[1]} & D(f)_{2}^{[2]} & D(f)_{2}^{[3]} & D(f)_{2}^{[4]} & … \\ f^{(3)} & D(f)_{3}^{[1]} & D(f)_{3}^{[2]} & D(f)_{3}^{[3]} & D(f)_{3}^{[4]} & … \\ f^{(4)} & D(f)_{4}^{[1]} & D(f)_{4}^{[2]} & D(f)_{4}^{[3]} & D(f)_{4}^{[4]} & … \\ … \end{matrix} )

If these are in fact equal, i.e. if 𝕏, D form a coalgebra, then in particular (f^{(1)})^{(1)} = D(f)_{1}^{[1]}, which when it is unravelled says:

( \begin{matrix}a_{11} & a_{1} \\ a_{∗1} & x \end{matrix} ) ↦ (f^{(1)})^{(1)} ( \begin{matrix}a_{1∗} \\ x \end{matrix} ) · ( \begin{matrix}a_{11} \\ a_{∗1} \end{matrix} ) = f^{(2)}(x) · a_{∗1} · a_{1∗} + f^{(1)}(x) · a_{11}

which yields [CD.6] by setting a_{∗1} = 0

(f^{(1)})^{(1)} ( \begin{matrix}a_{1∗} \\ x \end{matrix} ) · ( \begin{matrix}a_{11} \\ 0 \end{matrix} ) = f^{(1)}(x) · a_{11}

and [CD.7] as

(f^{(1)})^{(1)} ( \begin{matrix}a_{1∗} \\ x \end{matrix} ) · ( \begin{matrix}0 \\ a_{∗1} \end{matrix} )

= f^{(2)}(x) · a_{∗1} · a_{1∗}
= f^{(2)}(x) · a_{1∗} · a_{∗1}
= (f^{(1)})^{(1)} ( \begin{matrix}a_{∗1} \\ x \end{matrix} ) · ( \begin{matrix}0 \\ a_{1∗} \end{matrix} )

We have now proven:

2.2.7. Proposition. Every coalgebra of the Faà di Bruno comonad Faà is a Cartesian differential category.

It is worth noticing that we have in fact proved more: the coalgebra is in the following sense determined by the differential combinator of the Cartesian differential category: each f^{(n)} is in fact determined by D[f] = f^{(1)}. For, as we have just seen,

D(f)_{1}^{[1]} ( \begin{matrix}0 & a_{1} \\ a_{∗1} & x \end{matrix} ) = (f^{(1)})^{(1)} ( \begin{matrix}a_{1∗} \\ x \end{matrix} ) · ( \begin{matrix}0 \\ a_{∗1} \end{matrix} )
= f^{(2)}(x) · a_{∗1} · a_{1∗} + f^{(1)}(x) · 0
= f^{(2)}(x) · a_{∗1} · a_{1∗} + 0
= f^{(2)}(x) · a_{∗1} · a_{1∗}

In this manner, we can reconstruct f^{(2)} from (f^{(1)})^{(1)}, and similarly (by induction) f^{(n+1)} from (f^{(n)})^{(1)}.

3. Higher-Order Differentials and Chain Rules

Our objective is now to show that for any Cartesian differential category the differential supplies a coalgebra structure map into the Faà di Bruno category:

D: 𝕏 ⟶ Faà(𝕏); \begin{matrix}A & ↦ & (A, A) \\ f & ↦ & (f, f^{(1)}, f^{(2)}, …) \end{matrix}

which is a section of the fibration ε: Faà(𝕏) ⟶ 𝕏, where the f^{(n)} are the higher-order derivatives defined below, based on the combinator D. The existence of this functor is the structural generalization of Faà di Bruno’s original result on the higher differentials.

The technical details in this section require us to link the Faà di Bruno convolution composition to the higher-order chain rules. This involves some calculations for which we shall use the term logic [BCS 09].

In the notation of the previous section, our specific goal is to show, by induction on j, that D(f)_{j}^{[i]} = (f^{[i]})^{(j)}, and hence that the two tables representing Faà(D)(D(f)) and δ(D(f)) are equal. (The other coalgebra equation is obvious from the definition of D(f).)

3.1. Higher-order derivatives First we define the higher-order derivatives recursively by:

\frac{d^{(1)}t}{dx} (p) · u = \frac{dt}{dx} (p) · u
\frac{d^{(n)}t}{dx} (p) · u_{1} · . . . · u_{n} = \frac{d\frac{d^{(n−1)}t}{dx} (x) · u_{1} · . . . · u_{n−1}}{dx} (p) · u_{n}

Note that it is immediate from this definition that the n^{th}-order derivative is additive in each u_{1}, …, u_{n} thus the higher differentials define symmetric forms.

In order understand higher-order derivatives it is useful to start with some basic observations:

3.1.1. Lemma.

(i) \frac{dt[x+s/y]}{dx} (0) · u = \frac{dt}{dy} (s) · u , x not free in s

(ii) \frac{d \frac{dt}{dx} (x)·u_{1}}{dx} (s) · u_{2} = \frac{d \frac{dt}{dx} (x)·u_{2}}{dx} (s) · u_{1} that is \frac{d^{(2)}t}{dx} (s) · u_{1} · u_{2} = \frac{d^{(2)}t}{dx} (s) · u_{2} · u_{1}, x not free in u_{1}, u_{2}

(iii) \frac{d^{(n)}t}{dx} (s) · u_{1} · . . . · u_{n} = \frac{d^{(n)}t}{dx} (s) · u_{σ(1)} · . . . · u_{σ(n)} for any σ ∈ S_{n}.

Remark: Item (ii) is actually equivalent to [Dt.7] [BCS 09], and is a more direct translation of [CD.7].

Proof.

(i)

\frac{dt[x + s/y]}{dx} (0) · u = \frac{dt}{dy} (s) · (\frac{d(x + s)}{dx} (0) · u) because x + s[0/x] = 0 + s = s
= \frac{dt}{dy} (s) · (\frac{dx}{dx} (0) · u + \frac{ds}{dx} (0) · u)
= \frac{dt}{dy} (s) · u

(ii) The problem in this calculation is that in order to swap u_{1} and u_{2} we need to differentiate with respect to variables not involved in the position of the differential. The first part of the lemma allows us to arrange this - but we have to use it twice:

\frac{d\frac{dt}{dx} (x) · u_{1}}{dx} (s) · u_{2} = \frac{d\frac{dt}{dx} (x′) · u_{1}}{dx′} (s) · u_{2}
= \frac{d\frac{dt[x_{1}+x′/x]}{dx_{1}} (0) · u_{1}}{dx′} (s) · u_{2}
= \frac{d\frac{dt[x_{1}+x′/x]}{dx_{1}} (0) · u_{1}[x_{2} + s/x′]}{dx_{2}} (0) · u_{2}
= \frac{d\frac{dt[x_{1}+x_{2}+s/x]}{dx_{1}} (0) · u_{1}}{dx_{2}} (0) · u_{2}
= \frac{d\frac{dt[x_{1}+x_{2}+s/x]}{dx_{2}} (0) · u_{2}}{dx_{1}} (0) · u_{1} by [Dt.7]
= \frac{d\frac{dt}{dx} (x) · u_{2}}{dx} (s) · u_{1}

(iii) The result is trivially true for n = 1 and the previous result proves it for n = 2. Assuming it true for n + 1 we show it is true for n + 2 by showing how we can exchange u_{n+1} and u_{n+2}:

\frac{d^{(n+2)}t}{dx} (s) · u_{1} · . . . · u_{n+1} · u_{n+2} = \frac{d\frac{d^{(n+1)}t}{dx} (x) · u_{1} · . . . · u_{n+1}}{dx} (p) · u_{n+2}

= \frac{d^{\frac{d \frac{d^{(n)}t}{dx} (x)·u_{1}·...·u_{n}}{dx}} (x) · u_{n+1}}{dx} (p) · u_{n+2}

= \frac{d^{\frac{d \frac{d^{(n)}t}{dx} (x)·u_{1}·...·u_{n}}{dx}} (x) · u_{n+2}}{dx} (p) · u_{n+1}
= \frac{d^{(n+2)}t}{dx} (s) · u_{1} · . . . · u_{n+2} · u_{n+1}

This demonstrates that the second-order differential gives rise to a symmetric form and whence that the n^{th}-order differential gives a symmetric form.

A useful fact to note is that differentiating a higher-differential with respect to one of its linear components satisfies the generalization of [Dt.6]:

3.1.2. Corollary. In any Cartesian differential category

\frac{d\frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · x · . . . · u_{n}}{dx} (s′) · u_{r} = \frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · u_{r} · . . . · u_{n}

Proof. We use symmetry to move the variable into the last place at which point the linearity of the differential can be used:

\frac{d\frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · x · . . . · u_{n}}{dx} (s′) · u_{r}

= \frac{d\frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · u_{r−1} · u_{r+1} . . . · u_{n} · x}{dx} (s′) · u_{r}

= \frac{d^{\frac{d \frac{d^{(n−1)}s}{dt} (u_{1}·...·u_{r−1}·u_{r+1}...·u_{n})·}{dz}} (z) · x}{dx} (s′) · u_{r}
= \frac{d\frac{d^{(n−1)}s}{dt} (u_{1} · . . . · u_{r−1} · u_{r+1} . . . · u_{n}) ·}{dz} (z) · u_{r}
= \frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · u_{r−1} · u_{r+1} · . . . · u_{n} · u_{r}
= \frac{d^{(n)}t}{dz} (s) · u_{1} · . . . · u_{r} · . . . · u_{n}

3.2. Chain rules Let us start by explicitly calculating the second-order chain rule. We do this by first proving a lemma which tells us how to differentiate differentials with respect to variables not in the term. We shall then generalize this calculation to obtain the general form of the higher order chain rule in a Cartesian differential category.

3.2.1. Lemma. When y ∉ t we have

\frac{d\frac{dt}{dx} (p) · u}{dy} (p′) · u′ = \frac{d^{(2)}t}{dx} (p[p′/y]) · u[p′/y] · (\frac{dp}{dy} (p′) · u′) + \frac{dt}{dx} (p[p′/y]) · (\frac{du}{dy} (p′) · u′)

Proof.

\frac{d\frac{dt}{dx} (p) · u}{dy} (p′) · u′

= \frac{d\frac{dt}{dx} (a) · b}{d(a, b)} (p[p′/y], u[p′/y]) · (\frac{dp}{dy} (p′) · u′, \frac{du}{dy} (p′) · u′)
= \frac{d\frac{dt}{dx} (a) · u[p′/y]}{da} (p[p′/y]) · (\frac{dp}{dy} (p′) · u′) + \frac{d\frac{dt}{dx} (p[p′/y]) · b}{db} (u[p′/y]) · (\frac{du}{dy} (p′) · u′)
= \frac{d^{(2)}t}{dx} (p[p′/y]) · u[p′/y] · (\frac{dp}{dy} (p′) · u′) + \frac{dt}{dx} (p[p′/y]) · (\frac{du}{dy} (p′) · u′)

We may apply this to get the second-order chain rule:

\frac{d^{(2)}f(g(x))}{dx} (p) · u_{1} · u_{2} = \frac{d\frac{df(g(y))}{dy} (x) · u_{1}}{dx} (p) · u_{2}

= \frac{d\frac{df(z)}{dz} (g(x)) · (\frac{dg(y)}{dy} (x) · u_{1})}{dx} (p) · u_{2}
= \frac{d^{(2)}f(z)}{dz} (g(p)) · (\frac{dg(y)}{dy} (p) · u_{1}) · (\frac{dg(x)}{dx} (p) · u_{2})

+\frac{df(x)}{dx} (g(p)) · (\frac{d^{(2)}g(x)}{dx} (p) · u_{1} · u_{2})

With each function [x ↦ f(x)] in a differential category we can associate a series of functions:

f^{(1)}(z) · u_{1} = \frac{df(x)}{dx} (z) · u_{1}
f^{(2)}(z) · u_{1} · u_{2} = \frac{d^{(2)}f(x)}{dz} (u_{1} · u_{2}) ·
…
f^{(n)}(z) · u_{1} · . . . · u_{n} = \frac{d^{(2)}f(x)}{dz} (u_{1} · . . . · u_{n}) ·
…

This allows us in a Cartesian differential category, given a sequence of functions

X_{1} ⟶^{f_{1}} X_{2} ⟶^{f_{2}} X_{3} ⟶ … ⟶^{f_{n}} X_{n+1}

and a symmetric tree τ of height n and width r with variables U = {u_{1}, …, u_{r}} (which we should think of as the leaves of a tree) to define the meaning of (f_{1} ⋆ … ⋆ f_{n})_{τ}(z) inductively by:

• Variables ( )_{ι_{0}^{u_{i}}} = u_{i} become variables. (Recall ι_{0}^{u_{i}} is defined in Proposition 1.2.1 as the unique tree of height 0, width 1, and leaf or variable u_{i}.)

• Given a chain of one or more maps we define

(f_{1} ⋆ … ⋆ f_{n+1})_{•_{m}(τ_{1},...,τ_{m})}(z)

= \frac{d^{(m)}f_{n+1}(x)}{dx} (f_{n−1}(…, f_{1}(z) …)) · (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z) · . . . · (f_{1} ⋆ … ⋆ f_{n})_{τ_{m}}(z)

For T a bag of trees we define:

(f_{1} ⋆ … ⋆ f_{n+1})_{T} (z) = ∑_{τ∈T}(f_{1} ⋆ … ⋆ f_{n+1})_{τ}(z)

Examining the second-order chain rule we see that it is:

f^{(2)}(z) · (g^{(1)}(z) · u_{1}) · (g^{(1)}(z) · u_{2}) + f^{(1)}(z) · (g^{(2)}(z) · u_{1} · u_{2}))

which is precisely (f ⋆ g)_{T_{2}^{2}}(z) relating the higher-order chain rules to these symmetric trees. We now have the following key result:

3.2.2. Proposition. In any Cartesian differential category:

(i) The first differential of a composite of functions is given by :

\frac{df_{n}(…, f_{1}(x) …)}{dx} (z) · u = (f_{1} ⋆ … ⋆ f_{n})_{ι_{n}^{u}}(z)

(ii) For any bag of trees, T, of height n and width r on variables {u_{1}, …, u_{r}}

\frac{d(f_{1} ⋆ … ⋆ f_{n})_{T} (x)}{dx} (z) · u_{r+1} = (f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}T (x)}(z)

420  J.R.B. COCKETT AND R.A.G. SEELY

Proof.

(i) We may use the ordinary chain rule to prove the result. First note that for n = 0 the

result holds as:

( )_{ι_{0}}^{u}(z) = u = \frac{dz}{dz} (z) · u

Suppose now the result holds for n then:

\frac{df_{n+1}(f_{n}(… f_{1}(x) …)}{dx} (z) · u = \frac{df_{n+1}(x)}{dx} (f_{n}(… f_{1}(z) …)) · \frac{df_{n}(… f_{1}(z) …)}{dz} (z) · u
= \frac{df_{n+1}(x)}{dx} (f_{n}(… f_{1}(z) …)) · (f_{1} ⋆ … ⋆ f_{n})_{ι_{n}^{u}}(z)
= (f_{1} ⋆ … ⋆ f_{n} ⋆ f_{n+1})_{ι_{n+1}^{u}}(z)

(ii) The differential of a variable \frac{d(⋆)_{u_{i}}(x)}{dz} (z) · u_{r+1} = 0. The differential of (f_{1} ⋆ … ⋆ f_{n+1})_{•_{r}(τ_{1},...,τ_{r})}(z) is

\frac{d(f_{1} ⋆ … ⋆ f_{n+1})_{•_{r}(τ_{1},...,τ_{r})}(z)}{dz} (z) · u_{r+1}

= \frac{d\frac{d^{(r)}f_{n+1}(x)}{dx} (f_{n}(… f_{1}(z) …)) · (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z) · . . . · (f_{1} ⋆ … ⋆ f_{n})_{τ_{m}}(z)}{dz} (z) · u_{r+1}
= \frac{d\frac{d^{(r)}f_{n+1}(x)}{dx} (x) · x_{1} · . . . · x_{r}}{d(x, x_{1}, …, x_{r})} ( \begin{matrix}f_{n}(… f_{1}(z) …), \\ (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z), \\ …, \\ (f_{1} ⋆ … ⋆ f_{n})_{τ_{r}}(z) \end{matrix} ) · \begin{matrix}(\frac{df_{n}(... f_{1}(z)...)}{dz} (z) · u_{r+1})· \\ (\frac{d(f_{1}⋆...⋆f_{n})_{τ_{1}}(z)}{dz} (z) · u_{r+1})· \\ . . . · \\ (\frac{d(f_{1}⋆...⋆f_{n})_{τr} (z)}{dz} (z) · u_{r+1}) \end{matrix}

= \frac{d\frac{d^{(r)}f_{n+1}(x)}{dx} (x) · x_{1} · . . . · x_{r}}{d(x, x_{1}, …, x_{r})} ( \begin{matrix}f_{n}(… f_{1}(z) …), \\ (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z), \\ …, \\ (f_{1} ⋆ … ⋆ f_{n})_{τ_{r}}(z) \end{matrix} ) · \begin{matrix}((f_{1} ⋆ … ⋆ f_{n})_{ι_{n}}(z)· \\ ((f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{1}}(z)· \\ . . . · \\ ((f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{r}}(z)) \end{matrix}

= \frac{d \frac{d^{(r)}f_{n+1}(x)}{dx} (x)·(f_{1}⋆...⋆f_{n})_{τ_{1}}(z)·...·(f_{1}⋆...⋆f_{n})_{τr} (z)}{dx} (z) · (f_{1} ⋆ … ⋆ f_{n})_{ι_{n}}(z)

+^{\frac{d \frac{d^{(r)}f_{n+1}(x)}{dx} (f_{n}(...f_{1}(z)...))·x_{1}·(f_{1}⋆...⋆f_{n})_{τ_{2}}(z)·...·(f_{1}⋆...⋆f_{n})_{τr} (z)}{dx_{1}}} (z) · (f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{1}}(z)

+ …
+^{\frac{d \frac{d^{(r)}f_{n+1}(x)}{dx} (f_{n}(...f_{1}(z)...))·(f_{1}⋆...⋆f_{n})_{τ_{1}}(z)· ... ·x_{r}}{dx_{r}}} (z) · (f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{r}}(z)
= \begin{matrix}\frac{d^{(r+1)}f_{n+1}(x)}{dx} ((f_{1} ⋆ … ⋆ f_{n})_{ι_{n}}(z)) · (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z) · . . . · (f_{1} ⋆ … ⋆ f_{n})_{τ_{r}}(z) \\ +\frac{d^{(r)}f_{n+1}(x)}{dx} (f_{n}(… f_{1}(z) …)) · (f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{1}}(z) · (f_{1} ⋆ … ⋆ f_{n})_{τ_{2}}(z) · . . . \\ . . . · (f_{1} ⋆ … ⋆ f_{n})_{τ_{r}}(z) \\ + … \\ +\frac{d^{(r)}f_{n+1}(x)}{dx} (f_{n}(… f_{1}(z) …)) · (f_{1} ⋆ … ⋆ f_{n})_{τ_{1}}(z) · . . . · (f_{1} ⋆ … ⋆ f_{n})_{∂_{u_{r+1}}τ_{r}}(z) \end{matrix}

= (f_{1} ⋆ … ⋆ f_{n})_{∂_{ur} τ}(z)

where we have used the first result and inductively the result on trees of lesser height.

We have (obviously) proved the generalization of Faà di Bruno’s result: 3.2.3. Corollary. In any Cartesian differential category:

\frac{d^{(n)}g(f(x))}{dx} (z) · u_{1} · . . . · u_{n} = (f ⋆ g)_{T_{2}^{\{u_{1},...,un\}}}(z)

Furthermore

\frac{d^{(m)}f_{n}(f_{n−1}(… (f(x)) ⋯))}{dx} (z) · u_{1} ⋯ u_{m} = (f_{1} ⋆ f_{2} ⋆ ⋯ ⋆ f_{n})_{τ_{n}^{m}}(z)

This means that for any Cartesian differential category 𝕏 there is a functor

D: 𝕏 ⟶ Faà(𝕏); f ↦ (f, f^{(1)}, f^{(2)}, …)

We are now in a position to show this gives a coalgebra. 3.2.4. Theorem. A Cartesian differential category is exactly a coalgebra for the Faà di Bruno comonad. Proof. We just need to show that these are equal:

Faà(D)(D(f)) = ( \begin{matrix}f & f^{(1)} & f^{(2)} & f^{(3)} & f^{(4)} & … \\ f^{(1)} & (f^{(1)})^{(1)} & (f^{(2)})^{(1)} & (f^{(3)})^{(1)} & (f^{(4)})^{(1)} & … \\ f^{(2)} & (f^{(1)})^{(2)} & (f^{(2)})^{(2)} & (f^{(3)})^{(2)} & (f^{(4)})^{(2)} & … \\ f^{(3)} & (f^{(1)})^{(3)} & (f^{(2)})^{(3)} & (f^{(3)})^{(3)} & (f^{(4)})^{(3)} & … \\ f^{(4)} & (f^{(1)})^{(4)} & (f^{(2)})^{(4)} & (f^{(3)})^{(4)} & (f^{(4)})^{(4)} & … \\ … \end{matrix} )

δ(D(f)) = ( \begin{matrix}f & D(f)_{∗}^{[1]} & D(f)_{∗}^{[2]} & D(f)_{∗}^{[3]} & D(f)_{∗}^{[4]} & … \\ f^{(1)} & D(f)_{1}^{[1]} & D(f)_{1}^{[2]} & D(f)_{1}^{[3]} & D(f)_{1}^{[4]} & … \\ f^{(2)} & D(f)_{2}^{[1]} & D(f)_{2}^{[2]} & D(f)_{2}^{[3]} & D(f)_{2}^{[4]} & … \\ f^{(3)} & D(f)_{3}^{[1]} & D(f)_{3}^{[2]} & D(f)_{3}^{[3]} & D(f)_{3}^{[4]} & … \\ f^{(4)} & D(f)_{4}^{[1]} & D(f)_{4}^{[2]} & D(f)_{4}^{[3]} & D(f)_{4}^{[4]} & … \\ … \end{matrix} )

which in turn essentially means we need to show that D(f)_{j}^{[i]} = (f^{(i)})^{(j)}, which we shall do by induction on j. The case j = 0 is clear: D(f)_{∗}^{[i]} = f^{(i)} = (f^{(i)})^{(0)}. So we shall suppose that D(f)_{j−1}^{[i]} = (f^{(i)})^{(j−1)} is true, and prove the corresponding equation for j.

First

(f^{(i)})^{(j)} = \frac{d^{(j)} \frac{d^{(i)}f(z)}{dz} (x) · a_{1} ⋯ a_{i}}{d(a_{1}, …, a_{i}, x)} (a_{∗1}, …, a_{∗i}, x) · (a_{11}, …, a_{1i}, x_{1}) ⋯ (a_{j1}, …, a_{ji}, x_{j})

= \frac{d^{\frac{d^{(j−1)} \frac{d^{(i)}f(z)}{dz} (x)·a_{1}···a_{i}}{d(a_{1},...,a_{i},x)}} (a_{1}, …, a_{i}, x) · (a_{11}, …, a_{1i}, x_{1}) ⋯ (a_{j−1 1}, …, a_{j−1 i}, x_{j−1})}{d(a_{1}, …, a_{i}, x)}
(a_{∗1}, …, a_{∗i}, x) · (a_{j1}, …, a_{ji}, x_{j})

= \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{1} & … & a_{i} & x \end{matrix} )}{d(a_{1}, …, a_{i}, x)} (a_{∗1}, …, a_{∗i}, x) · (a_{j1}, …, a_{ji}, x_{j})

= \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{1} & … & a_{∗i} & x \end{matrix} )}{da_{1}} (a_{∗1}) · a_{j1}

+ …

… + \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{∗1} & … & a_{i} & x \end{matrix} )}{da_{i}} (a_{∗i}) · a_{ji} (⋆)

+ \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{∗1} & … & a_{∗i} & x \end{matrix} )}{dx} (x) · x_{j}

where, in the sum (⋆), in each term the bottom row of the variable base matrix consists of “starred” variables a_{∗k} except in one position where one has a_{m}, m = 1, …, j − 1, with the j^{th} term having x instead of x, (the sum being over all such terms).

To facilitate the calculation of D(f)_{j}^{[i]}, we recall a bit of notation. In particular, Proposition 2.2.3 expressed δ in terms of partial isomorphisms (or “scatter sets”):

f_{j}^{[i]} = ∑_{σ∈ParIso(j,i)} f^{σ}

We regard ParIso(j − 1, i) ⊆ ParIso(j, i), and for any σ ∈ ParIso(j, i), π_{1}σ (respectively π_{2}σ) is the set of indices appearing in the domain (respectively codomain) of σ. Note that

ParIso(j, i) = ParIso(j − 1, i) ∪ {σ′ ∪ (j, k) | σ′ ∈ ParIso(j − 1, i), k ∉ π_{2}σ′}

THE FAÀ DI BRUNO CONSTRUCTION  423

and

Df_{j}^{[i]} = ∑_{σ∈ParIso(j,i)} Df^{σ} and Df_{j−1}^{[i]} = ∑_{σ′∈ParIso(j−1,i)} Df^{σ′}

so that

∑_{σ∈ParIso(j,i)} Df^{σ} = ∑_{σ′∈ParIso(j−1,i)} Df^{σ′} + ∑_{\begin{matrix}σ′ ∈ ParIso(j − 1, i) \\ 0 ≤ k ≤ i \\ k ∉ π_{2}σ′ \end{matrix}} Df^{σ′∪(j,k)}

= ∑_{σ′} \frac{dDf^{σ′}[a_{∗1}/a_{1}, …, a_{∗i}/a_{i}]}{dx} (x) · x_{j} +

∑_{σ′,k} \frac{dDf^{σ′}[a_{∗1}/a_{1}, …, { \atop a_{∗i}/a_{i}}, …, x/x]}{da_{k}} (a_{∗k}) · a_{jk}

(where as usual, the hat indicates a term suppressed). 3.2.5. Lemma. For σ′ ∈ ParIso(j − 1, i),

\frac{dDf^{σ′}[a_{∗1}/a_{1}, …, a_{∗i}/a_{i}]}{dx} (x) · x_{j} = Df^{σ′}

\frac{dDf^{σ′}[a_{∗1}/a_{1}, …, { \atop a_{∗i}/a_{i}}, …, x/x]}{da_{k}} (a_{∗k}) · a_{jk} = \{ \begin{matrix}0 if k ∈ π_{2}σ′ \\ Df^{σ′∪(j,k)} otherwise \end{matrix}

Proof. (of the lemma) Some notation: for σ′ ∈ ParIso(j − 1, i), we shall write Df^{σ′} = Df^{(i+s)}(x) •_{r ∉ π_{1}σ′} x_{r} •_{(l, k) ∈ σ′} a_{lk} •_{m ∉ π_{2}σ′} a_{m}

Then note that:

\frac{dDf^{σ′}[a_{∗1}/a_{1}, …, a_{∗i}/a_{i}]}{dx} (x) · x_{j}

= Df^{(i+s+1)}(x) · x_{j} · x_{r} · a_{lk} · a_{∗m}
= Df^{σ′}

\frac{dDf^{σ′}[a_{∗1}/a_{1}, …, { \atop a_{∗i}/a_{i}}, …, x/x]}{da_{k}} (a_{∗k}) · a_{jk}

= \{ \begin{matrix}0 if k ∈ π_{2}σ′ since a_{k} does not occur \\ Df^{(i+s)}(x) •_{r ∉ π_{1}σ′} x_{r} •_{(l, w) ∈ σ′} a_{lw} •_{m ∉ π_{2}σ′, m ≠ j} a_{∗m} · a_{jk} \\ = Df^{σ′∪(j,k)} otherwise \end{matrix}

which proves the lemma

Finally, to complete the proof of Theorem 3.2.4, we just sum these terms to get the same sum (⋆) for D(f)_{j}^{[i]} as we got for (f^{(i)})^{(j)}:

D(f)_{j}^{[i]} = ∑_{σ∈ParIso(j,i)} Df^{σ}

= ∑_{σ′} \frac{dDf^{σ′}[a_{∗1}/a_{1}, …, a_{∗i}/a_{i}]}{dx} (x) · x_{j}

+ ∑_{k=1}^{i} ∑_{σ′} \frac{dDf^{σ′}[a_{∗1}/a_{1}, …, { \atop a_{∗i}/a_{i}}, …, x/x]}{da_{k}} (a_{∗k}) · a_{jk}

= \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{∗1} & … & a_{∗i} & x \end{matrix} )}{dx} (x) · x_{j}

+ ∑_{k=1}^{i} \frac{dD(f)_{j−1}^{[i]}( \begin{matrix}a_{11} & … & a_{1i} & a_{1} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{j−1 1} & … & a_{j−1 i} & a_{j−1} \\ a_{∗1} & … a_{k} … & a_{∗i} & x \end{matrix} )}{da_{k}} (a_{∗k}) · a_{jk}

Finally, these constructions establish the following equivalence.

3.2.6. Theorem. The category of coalgebras for the comonad Faà is equivalent to the category of Cartesian differential categories and Cartesian differential functors (Cartesian left additive functors which preserve the differential combinators).

Conclusion

The Faà di Bruno construction was a complete surprise to us. It meant, in particular, that Cartesian differential categories were as common as left additive categories. For, given any left additive category 𝕏, Faà(𝕏) is always a Cartesian differential category and, furthermore, the cofree one on 𝕏. Initially our motivation was simply to give ourselves assurance that the axiomatization of Cartesian differential categories was correct and we thought to add something about higher-order chain rules as an appendix to [BCS 09]. However, as the combinatorics of the higher-order chain rules began to unfold before us, it was clear that this was something of quite independent interest. Still we did not expect to be staring at a combinatorial comonad which governed differentiation.

Not only is this construction a rich potential source of models of differential algebras (such as differential combinatory algebras and λ-calculi) but also it is clear that this structure is an integral part of what it means to be differentiable. This poses questions not only for our original setting of differential categories [BCS 06], but also for the on-going development of notions of differentiability: for example the work (with Crutwell and Gallagher) on differential restriction categories (partial map categories) and on tangential structure for manifold categories. It also raises a broader question of whether there are other closely related comonads which determine interesting subvarieties of differential structure. For example, there is a subcomonad given by the sequences which eventually vanish: these abstractly capture “polynomial” differentiability. Is it possible to capture other notion of differentiability using the same coalgebraic techniques: e.g. can differentiability given by Taylor expansion be so described?

After distributing an earlier version of this paper, we learned of two earlier works treating the combinatorics of Faà di Bruno algebraically (as a Hopf algebra). Although they are not directly relevant to our approach, the reader might wish to consult them as well [EP 10, FG 05].

References

[BCS 06] R.F. Blute, J.R.B. Cockett, R.A.G. Seely. “Differential Categories”. Mathematical Structures in Computer Science 16 (2006), 1049–1083.

[BCS 09] R.F. Blute, J.R.B. Cockett, R.A.G. Seely. “Cartesian differential categories”. Theory and Applications of Categories 22 (2009), 622–672.

[CCG 10] G. Crutwell, J.R.B. Cockett, and J. Gallagher. “Differential restriction categories”. (in preparation)

[EP 10] K. Ebrahimi-Fard and F. Patras. “Exponential Renormalization”. Annales Henri Poincare 11 (2010) 943–971.

[FG 05] H. Figueroa, J.M. Gracia-Bondia. “Combinatorial Hopf algebras in quantum field theory I”. Reviews in Mathematical Physics 17 (2005), 881–976.

[OR 97] J.J. O’Connor, E.F. Robinson. “Francesco Faà di Bruno”. MacTutor History of Mathematics (1997), School of Mathematics and Statistics, University of St An-

    drews, Scotland. http://www-history.mcs.st-andrews.ac.uk/Biographies/Faa_
    di_Bruno.html

[L 09] Paul Linehan. “Francesco Faà di Bruno”. The Catholic Encyclopedia 5. New York:

    Robert Appleton Company, 1909. http://www.newadvent.org/cathen/05740a.htm

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/25/15/25-15.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors

Clemens Berger, Université de Nice-Sophia Antipolis, cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it

Valeria de Paiva: valeria.depaiva@gmail.com

Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Glasgow, Tom.Leinster@glasgow.ac.uk Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca