## Graft product of species

Let $FB$ be the monoidal groupoid of finite sets and bijections, where the monoidal product is obtained by restricting the coproduct on the category of finite sets. Let $F, G: FB \to V$ be species valued in a bicomplete symmetric monoidal closed category $V$. The graft product $F \ast G$ is defined by the formula

$(F \ast G)[S] = \sum_{T \subseteq S} F[S/T] \otimes G[T]$

where $S/T$ denotes the pushout of $T \to 1$ along the inclusion $T \subseteq S$. This includes the degenerate case where $T = 0$; in this case $S/0$ is the result of freely adjoining a point to $S$.

The set $S/T$ has $T/T$ as distinguished basepoint, and if $U$ is complementary to $T$, we have a natural bijection $S/T \cong U + \{T/T\}$. It follows that

$\array{ (F \ast G)[S] & \cong & \sum_{U + T = S} F[U + *] \otimes G[T] \\ & \cong & \sum_{U + T = S} F'[U] \otimes G[T] \\ & \cong & (F' \otimes G)[S] }$

where $F' \otimes G$ refers to the usual Day convolution product, induced from the tensor product on $FB$. Since differentiation of species,

$V^{FB} \stackrel{- + *}{\to} V^{FB},$

is cocontinuous, and since Day convolution is cocontinuous in each of its arguments, we see that

$F \ast G \cong F' \otimes G$

is separately cocontinuous in each of its arguments $F$, $G$. We remark below on the fundamental implications of this observation.

For $V = Set$, a structure of species $F \ast G$ is given by three data:

• A tree obtained by grafting the root of a sprout (aka corolla) with leaf set $\tau$ to a leaf of another sprout with leaf set $\sigma$;
• An element of $F[\sigma]$;
• An element of $G[\tau]$.

### Lax monoidal structure of graft product

We note that the graft poduct is not associative up to isomorphism, but there is a lax associativity. Specifically, we calculate

$\array{ (F \ast G) \ast H & \cong & (F' \otimes G)' \otimes H \\ & \cong & F'' \otimes G \otimes H + F' \otimes G' \otimes H \\ & \cong & F'' \otimes G \otimes H + F \ast (G \ast H) }$

so that there is a noninvertible associativity (an inclusion)

$\alpha_{F G H}: F \ast (G \ast H) \to (F \ast G) \ast H$

which is natural in each of its arguments $F$, $G$, and $H$, and which satisfies an evident pentagon coherence condition. Additionally, there is a lax unit, defined as the species $X$ for which $X[S]$ is the monoidal unit of $V$ if $card(S) = 1$, else $X[S]$ is initial, for which we have evident natural maps

$\lambda_F: X \ast F \to F, \qquad \rho_F: F \ast X \to F$

The first map $\lambda_F$ is invertible, but the second is not: its component at a finite set $S$ is the codiagonal

$\nabla: S \cdot F[S] \to F[S]$

However, the standard unit coherence conditions for monoidal categories hold. We may call such a structure, relaxing the condition of invertibility of $\alpha$ and $\rho$ but retaining the naturality and coherence conditions, a lax monoidal category.

In the sequel, $F^{\ast n}$ will denote the iterated graft product defined recursively by

$F^{\ast 0} = X, \qquad F^{\ast (n+1)} = F^{\ast n} \ast F$

so that all parentheses in $F^{\ast n}$ are to the left. We have a partial coherence theorem:

###### Proposition

Any two maps

$F^{\ast m} \ast F^{\ast n} \to F^{\ast (m+n)}$

definable in the language of lax monoidal categories are equal. This map by $\alpha_{m n}$.

For $F$ a $Set$-valued species, an element of $F^{\ast n}$ is described by data as follows:

1. A structure of tree constructed from $n$ sprouts in a prescribed grafting order;

2. An element of $F[\sigma]$ for each sprout $\sigma$ used in the construction of the tree in 1.

Thus we expect some connection between the “geometric series” $\sum_n F^{\ast n}$ and the free operad on $F$. The only difference between the two is that the standard construction of free operads via trees is in no way dependent on grafting order. Thus, to obtain the free operad, we have to mod out by isomorphisms on $F^{\ast n}$ induced by “inessential” differences in grafting order. This will be described in detail in the section on trees and hierarchies.

## Trees and hierarchies

It is interesting to resolve $F^{\ast n}$ into a sum of monomials, each of which is a tensor product of derivatives of $F$. For example, we have

$\array{ F \ast F & \cong & F' \otimes F \\ (F \ast F) \ast F & \cong & F'' \otimes F^{\otimes 2} + F' \otimes F' \otimes F \\ F^{\ast 4} & \cong & F''' \otimes F^{\otimes 3} + 2 F'' \otimes F' \otimes F + F'' \otimes F \otimes F' \otimes F + F' \otimes F'' \otimes F^{\otimes 2} + (F')^{\otimes 3} \otimes F }$

There are in fact $(n-1)!$ monomial terms, each a tensor product of $n$ derivative terms, and each corresponding to a function $f: [2, n] \to [1, n]$ such that $f(k) \lt k$ for all $k \in [2, n]$. We call such an $f$ a hierarchy. In detail, if the $S^{th}$ derivative of a species $F$ is defined by $F^{(S)}[T] = F[S + T]$, we have

$F^{\ast n} = \sum_{f \in Hier(n)} F^{(f^{-1}(1))} \otimes F^{(f^{-1}(2))} \otimes \ldots \otimes F^{(f^{-1}(n-1))} \otimes F$

as may be proved by an easy induction.

Each $f \in Hier(n)$ endows the set $[1, n]$ with a rooted tree structure. A rooted tree structure on a set $S$ is precisely a function $f: S \to S$ with a fixed point $r$ (the root) such that for every $s \in S$, some finite iterate of $f$ takes $s$ to $r$, i.e., $f^{(k)}(s) = r$ for some $k$. (The function $f$ simply moves a vertex one step closer to the root along the unique path to the root.) Given a hierarchy $f: [2, n] \to [1, n]$, the corresponding rooted tree structure on $[1, n]$ is the extension of $f$ which fixes the point $1$. The well-ordering of the vertices $1 \lt \ldots \lt n$ serves to prescribe a grafting order on sprouts, starting from the sprout at the root $1$, grafting the sprout rooted at $2$ to a leaf of the initial sprout, and so on.

Somewhat more generally, given any finite well-ordered set $S = \{s_1 \lt \ldots \lt s_n\}$, a hierarchy on $S$ is a function $f: S - \{s_1\} \to S$ such that $f(s_i) \lt s_i$ for $1 \lt i \leq n$, and this also gives rise to a rooted tree structure. A rooted tree whose vertices are equipped with a well-ordering and whose tree structure arises from a hierarchy function will be called a hierarchical tree. The root $r$ is of course the initial element $s_1$.

Now by removing the root of a finite rooted tree $(S, f, r)$, we obtain a forest of finite rooted trees $S/s$ whose roots $s$ range over $f^{-1}(r)$. An isomorphism $\Phi$ of rooted trees $(S, f, r) \to (S', f', r')$ may be described recursively as consisting of

1. A bijection $\phi: f^{-1}(r) \to (f')^{-1}(r')$;

2. Isomorphisms of rooted trees $\Phi_s: S/s \to S'/\phi(s)$ where $s \in f^{-1}(r)$.

If $(S, f)$ is hierarchical, then the subtrees $S/s$ inherit hierarchical tree structures from $S$ by restricting both the well-ordering and $f: S \to S$ to a function $f|: S/s \to S/s$. Thus isomorphisms of hierarchical trees $S$ (defined to be isomorphisms of the underlying rooted trees) can also be described recursively.

If $(S = \{s_1 \lt \ldots \lt s_n\}, f)$ is a hierarchical tree and $F$ is a species, we define a species

$F_{S, f} = \bigotimes_{k=1}^{n} F^{(f^{-1}(s_k))}$

Observe that there is a well-defined isomorphism

$F_{S, f} \cong F^{(f^{-1}(r))} \otimes (\bigotimes_{s \in f^{-1}(r)} F_{S/s, f|})$

by permuting tensor factors. (The order of tensor factors on either side is fixed by the well-ordering of vertices.)

Now if $\Phi: (S, f) \to (S', f')$ is an isomorphism of hierarchical trees, we define by recursion a species isomorphism to be the composite of

$F^{(f^{-1}(s_1))} \otimes \bigotimes_{s \in f^{-1}(s_1)} F_{S/s, f|} \stackrel{F^{(\phi)} \otimes (\bigotimes_{s \in f^{-1}(s_1)} F_{\Phi_s})}{\to} F^{((f')^{-1}(r'))} \otimes (\bigotimes_{s' \in (f')^{-1}(r')} F_{S'/s', f'|})$

with factor-permuting isomorphisms

$F_{S, f} \cong F^{(f^{-1}(r))} \otimes (\bigotimes_{s \in f^{-1}(r)} F_{S/s, f|}) \qquad F^{((f')^{-1}(r'))} \otimes (\bigotimes_{s' \in (f')^{-1}(r')} F_{S'/s', f'|}) \cong F_{S', f'}$

on either side. The result is an isomorphism $F_\Phi: F_{S, f} \to F_{S', f'}$.

There is a groupoid consisting of hierarchical trees and isomorphisms between them. Let $Hier_n$ be the full subgroupoid whose objects are hierarchical tree structures on $[1, n]$. (The isomorphisms in $Hier_n$ can be thought of as permutations on $[1, n]$ that relabel vertices to give a new grafting order.) Given a $V$-species $F$, there is a functor

$Hier_n \to V^{FB}: (\Phi: ([1, n], f) \to ([1, n], g)) \mapsto F_{[1, n], f} \to F_{[1, n], g}$

which defines a diagram in the category of species. The colimit of this diagram is a certain quotient of

$F^{\ast n} = \sum_{f \in Hier(n)} F_{[1, n], f}$

which we will denote as $F^{\ast n}/Hier_n$. By taking this quotient, we eliminate dependence on a specified hierarchy or grafting order.

The constructions are made in view of the following result.

###### Theorem

The species

$\mathcal{O}(F) = \sum_{n \geq 0} F^{\ast n}/Hier_n$

is the underlying species of the free operad on $F$.

This will be explored further in the next section.

The notion of (permutative) $V$-valued operad may be formulated in terms of the graft product. Specifically, if $M$ is an operad, there is a natural map

$\psi: M \ast M \to M \circ M$

and whose unit is again $u: X \to M$. The structure of an operad $M$ may be described entirely in terms of $m: M \ast M \to M$, $u: X \to M$, and the notion of operad may be recast as appropriate $\ast$-monoids (with a slight extra twist).

The map $\psi$ is not hard to describe: the graft product $F \ast G$ may be alternatively described by the formula

$(F \ast G)[S] = \sum_k \sum_{1 \leq k \leq k} (F[k] \otimes \widehat{G}_j)[S]$

where $\widehat{G}_j$ is a tensor product of $k$ factors

$X \otimes \ldots \otimes G \otimes \ldots \otimes X,$

all factors being $X$ except for a single instance of $G$ as the $j^{th}$ tensor factor. If there is in addition a map $i: X \to G$ (for example, a unit map $u: X \to M$ of an operad), there is an induced map

$i_j = i \otimes \ldots \otimes 1_G \otimes \ldots \otimes i: \widehat{G}_j \to G^{\otimes k}$

and under these circumstances there is an induced map

$F \ast G \to \sum_k F[k] \otimes G^{\otimes k} \to \sum_k F[k] \otimes_{S_k} G^{\otimes k} = F \circ G$
• A multiplication $m: F \ast F \to F$;

• A unit $u: X \to F$

These must satisfy the following axioms:

1. $\array{ F \ast (F \ast F) & \stackrel{1 \ast m}{\to} & F \ast F & \\ \alpha \downarrow & & & \searrow m \\ (F \ast F) \ast F & \underset{m \ast 1}{\to} F \ast F & \underset{m}{\to} & F }$

commutes;

2. The two composites $F'' \otimes F^{\otimes 2} \to F$ named in

$F'' \otimes (F \otimes F) \stackrel{\overset{\sigma}{\to}}{\underset{1}{\to}} F'' \otimes (F \otimes F) \stackrel{i}{\to} (F \ast F) \ast F \stackrel{m(m \ast 1)}{\to} F$

commute. Here $i$ denotes the inclusion complementary to $\alpha: F \ast (F \ast F) \to (F \ast F) \ast F$, and $\sigma$ is the involution

$\sigma_1 \otimes \sigma_2: F'' \otimes F^{\otimes 2} \to F'' \otimes F^{\otimes 2}$

where $\sigma: F'' \to F''$ is the natural involution on the second derivative

$(-)'' = (- + 2)*: V^{FB} \to V^{FB}$

induced by the nonidentity involution $2 \to 2$, and $\sigma_2$ is the symmetry isomorphism $F^{\otimes 2} \to F^{\otimes 2}$.

###### Definition

A cyclic operad is a species $Y$ with $Y[0] = 0$ and equipped with a morphism

$\pi: Y' \otimes Y' \to Y$

satisfying two axioms:

1. Symmetry: $\pi \circ \sigma = \pi$ where $\sigma = \sigma_{Y', Y'}: Y' \otimes Y' \to Y \otimes Y'$ is the symmetry;

$Y'' \otimes Y' \hookrightarrow Y'' \otimes Y' + Y' \otimes Y'' \cong (Y' \otimes Y')' \stackrel{\pi'}{\to} Y'$

is a structure of operad $m: Y' \ast Y' \to Y'$ on $Y'$.

We observe that by the symmetry axiom, the composite

$\mu = (Y' \otimes Y'' \hookrightarrow Y'' \otimes Y' + Y' \otimes Y'' \cong (Y' \otimes Y')' \stackrel{\pi'}{\to} Y')$

is equal to

$\nu = (Y' \otimes Y'' \stackrel{\sigma_{Y', Y''}}{\to} Y'' \otimes Y' \stackrel{m}{\to} Y')$

so that $\pi'$ (and hence $\pi$) is uniquely determined by $m$.

Because $\pi$ is uniquely determined from $m$ under the $\mu = \nu$ condition, one could define a cyclic operad to be an operad $M$ together with a suitable identification $\phi: Y' \cong M$, so that it is the derivative $M$ (and not $Y$) that is the “operad” per se. In essence, this is what is usually done in the literature. But definition 1 seems simpler.

###### Example

Let $Y$ be the species of necklaces (or cyclic orders), where $s \in Y[S]$ is a permutation $s: S \to S$ of order ${|S|}$. We define a map

$\pi: Y' \otimes Y' \to Y$

where $\pi$ takes a pair of necklaces $(\alpha, \beta) \in Y[S + \ast] \times Y[T + \ast]$ to the necklace $\gamma$ on $S + T$ such that

1. For $s \in S$, $\gamma(s) = \beta(\ast)$ if $\alpha(s) = \ast$, else $\gamma(s) = \alpha(s)$;

2. For $t \in T$, $\gamma(t) = \alpha(\ast)$ if $\beta(t) = \ast$, else $\gamma(t) = \beta(t)$.

It is clear from the definition that $\pi$ is symmetric. Moreover, the derivative of $Y$ is $Assoc$, the operad for associative algebras, for which $Y'[S]$ is isomorphic to the species of linear orders on $S$ (if $\alpha$ is a necklace on $S + \ast$, then the corresponding linear order on $S$ has first element $\alpha(\ast)$ and last element $\alpha^{-1}(\ast)$, and the successor function on the linear order given by $\alpha$ itself).

###### Example

There is of course a unique cyclic operad structure on $Y = \exp(X)$, since $Y' = Y$.

Revised on April 5, 2013 at 21:24:41 by Todd Trimble