# Species, derivatives of types and Gröbner bases for operads

In Algebra, Category theory, Combinatorics, Haskell, Mathematics, Operads and PROPs, Research.

This is a typed up copy of my lecture notes from the combinatorics seminar at KTH, 2010-09-01. This is not a perfect copy of what was said at the seminar, rather a starting point from which the talk grew.

Combinatorial species started out as a theory to deal with enumerative combinatorics, by providing a toolset & calculus for formal power series. (see Bergeron-Labelle-Leroux and Joyal)

As it turns out, not only is species useful for manipulating generating functions, btu it provides this with a categorical approach that may be transplanted into other areas.

For the benefit of the entire audience, I shall introduce some definitions.

**Definition**: A *category* C is a collection of *objects* and *arrows*
with each arrow assigned a *source* and *target* object, such that

- Each object has its own
*identity arrow*1. - Chains of arrows are associatively
*composable*, with 1 the identity of this composition.

**Examples**: Sets, Finite sets, k-Vector spaces, left and right
R-Modules, Graphs, Groups, Abelian groups.

[tex]\mathbb B[/tex]: finite sets with only bijections as morphisms.

**Examples**:

- Category of a monoid.
- Category generated by a graph
- Category of a group (groupoid version of the category of a monoid)
- Category of a poset
- Category of Haskell types and functions.

**Definition**: A *functor* F is a map of categories, in other words, a
pair of maps Fo on objects and Fa on arrows, such that the identity
arrow maps to identity arrows and compositions of maps map to
compositions of their images.

**Examples**:

Identity functor: sends objects and arrows to themselves.

Underlying set functor, free monoid/vector space/module/... functors.

**Definition**: A

*species of structures*is a functor [tex]\mathbb B\to\mathbb B[/tex].

The idea is a set gets mapped to the set of all structures labelled by
the elements in the original set. A bijection on labels maps to the
*transport of structures* along the relabeling.

**Examples**:

In enumerative combinatorics, the power of species resides in the association to each species a number of generating functions:

There are a number other in use for combinatorics, but for my purposes, this is the one I'll focus on.

## Operations on species

The real power, though, emerges when we start combining species, and carry over the combinations to actions on the corresponding power series.

### Addition

The number of ways to form either, say, a graph or a linear order on a set of labels is the sum of the numbers of ways to form either in isolation.

In the power series, we get [tex](F+G)(x) = F(x) + G(x)[/tex].

*shine*.

### Multiplication

*derangement*. Total number of permutations on n elements is

Thus, tricolorings are [tex]E\cdot E\cdot E[/tex] and permutations are [tex]S = E\cdot Der[/tex], where the set is that of fixed points, and the derangement captures the actual action of the permutation.

### Composition

Endofunctions of sets decompose in their actions on the points as cycles or directed trees leading in to these cycles.

Since a collection of disjoint cycles corresponds to a permutation, we can consider such endofunctions to be permutations decorated with rooted trees attached to points of the permutations; or even permutations of rooted trees.

To form such a structure on a set U, we'd first partition U into subsets, put the structure of a rooted tree on each subset, and then the structure of a permutation on the set of these subsets.

This corresponds to the power series [tex]S(A(x))[/tex], and we write, in general, [tex]F\circ G[U][/tex] for the species of F-structures of G-structures on subsets.

**Examples**:

### Pointing

Picking out a single point in a structure on n points can be done in precisely n ways.

In species, this process is called pointing.

In functional programming, Conor McBride related this construction to Huet's Zipper datatypes.

As it turns out, many of the constructions for species make eminent
sense outside the category [tex]\mathbb B[/tex]. In fact, species in
Hask are known to programming language researchers as *container
datatypes* and the whole calculus translates relatively cleanly.

Functional equations translate to the standard new data type definitions in Haskell.

**Examples**:

The species interpretation of [tex]\frac{\partial}{\partial x}[/tex] corresponding to leaving a hole in the structure carries over cleanly, so that [tex]\frac{\partial}{\partial x}T[/tex] is the type of T-with-a-hole.

## Two derivatives of lists

We can deal with [tex]\frac{\partial}{\partial x}L[/tex] in two different ways:

*virtual species*, and dealt with relatively cleanly — that

## Gröbner bases for operads

All of this becomes relevant to the implementation of Buchberger's algorithm on shuffle operads (see Dotsenko—Khoroshkin and Dotsenko—Vejdemo-Johansson) in the step where the S-polynomials (and thereby also the reductions) are defined. With a common multiple defined, we need some way to extend the modifications that take the initial term to the common multiple to the rest of that term.

For this, it turns out, that the derivative of the tree datatype used provides theoretical guarantees that only partially filled in trees of the right size, with holes the right size, can be introduced; and also provides an easy and relatively efficient algorithm for contructing the hole-y trees and later filling in the holes.