What is an Operad? Part 2
Last week we introduced the definition of an operad: it's a sequence $\mathcal{O}(1),\mathcal{O}(2), \mathcal{O}(3),\ldots$ of sets or vector spaces or topological spaces or most anything you like (whose elements we think of as abstract operations), together with composition maps $\circ_i\colon \mathcal{O}(n)\times\mathcal{O}(m)\to\mathcal{O}(n+m-1)$ and a way to permute the inputs using symmetric groups. We also defined an algebra over an operad, which a way to realize each abstract operation as an actual operation. Now it's time for some examples!
The Associative and Commutative Operads
Suppose $V$ is a vector space over a field $\mathbb{k}$. For each $n\geq 1$, define Assoc$(n)$ to be the 1-dimensional vector space generated by the tree with $n$ leaves. And let's not worry about permuting the leaves---there's no action of the symemtric group $S_n$ here. (Such operads are called non-symmetric operads.)
The $\circ_i$ composition is tree grafting, as introduced last time For example, to describe the compositions $$\circ_i\colon \text{Assoc}(2)\times \text{Assoc}(2)\to \text{Assoc}(3), \qquad i=1,2$$ it's enough to say where 𝖸$\circ_1$𝖸 and 𝖸$\circ_2$𝖸 land. Here, I'm using 𝖸 to depict the 2-to-1 operation that generates $\text{Assoc}(2)$. But there's only one option! Up to a scalar multiple, there's only one 3-to-1 tree in $\text{Assoc}(3)$! In other words, the following trees must be equal
Now, what's an algebra over this operad? As we saw last time, it's a collection of maps $\varphi\colon \text{Assoc}(n)\to\text{End}_V(n)$ for each $n=1,2,\ldots$ that's compatible with the $\circ_i$. Let's define $m:=\varphi(𝖸)\colon V\times V\to V$ to be the image of the 2-to-1 operation 𝖸. Compatibility tells us that the first and third equalities hold: $$\varphi(𝖸)\circ_1\varphi(𝖸)=\varphi(𝖸\circ_1 𝖸)=\varphi(𝖸\circ_2 𝖸)=\varphi(𝖸)\circ_2\varphi(𝖸)$$ while the second equality holds from the picture above. This amounts to the statement that $$m(m(v_1,v_2),v_3)=m(v_1,m(v_2,v_3))$$ for all $(v_1,v_2,v_3)\in V^3$, or writing $v_1\cdot v_2$ instead of $m(v_1,v_2)$, $$(v_1\cdot v_2)\cdot v_3= v_1\cdot(v_2\cdot v_3).$$ This shows that $m$ is an associative product on $V$! In other words, an algebra over the operad Assoc is an associative algebra.
We didn't consider a symmetric group action, but if we do, and if we define it to be trivial (i.e. $\sigma f=f$ for all $\sigma\in S_n$ and all $n$-ary operations $f$) then $v_1\cdot v_2= v_2\cdot v_1$ for all $v_1,v_2\in V$ since the two trees on the left must be equal. This operad is called the Comm operad, and an algebra over it is a commutative algebra.
The Associahedra Operad
The associahedra are a sequence of polytopes that encode operations that are associative up to homotopy. Let's look at an example. Suppose $X$ is a topological space and let $a,b\colon I\to X$ be loops based at point in $X$. (That is, $a$ and $b$ are continuous functions, both of which send $0,1\in I$ to the same point in $X$.) The product $a\cdot b$ gives us a new loop by "going around $a$ and $b$ each at twice the original speed." We can think of traversing $a$ in the first half-second, then traversing $b$ in the second half. This gives us a 2-to-1 operation $\Omega X\times \Omega X\to \Omega X$ where $\Omega X$ denotes the space of all based loops of $X$.
Is this operation associative? Well, if we have three loops $a,b$ and $c$, there are two options:
Here, $(a\cdot b)\cdot c$ means "do $a$ on the first quarter of the interval, and do $c$ on the second half," while $a\cdot(b\cdot c)$ means "do $a$ on the first half of the interval and do $c$ on the last quarter." These two loops are not equal, so this "multiplication" is not associative. But we can get from one loop to the other simply by adjusting the speed at which we traverse $a$ (and $c$)! In other words, we can go from $(a\cdot b)\cdot c$ to $a\cdot(b\cdot c)$ continuously by traveling around $a$ a little slower and traveling around $c$ a little faster. This defines a homotopy between the two loops, which we can represent as a line segment, called $K_3$, joining two points.
The vertices represent the two loops $(a\cdot b)\cdot c$ and $a \cdot(b\cdot c)$, and every point in between represents an intermediate loop. For example, the midpoint represents the loop $a\cdot b\cdot c$ in which $a, b$ and $c$ are all traversed in equal time.
Now what happens if you want to take the product of four loops $a,b,c,d$?! There are five ways to parenthesize four letters, so we have five different vertices. Some of these can be connected by edges using a homotopy, which gives us the boundary of a pentagon. Now it turns out that you can get from $((ab)c)d$ to $a(b(cd))$ via one of two homotopies, depicted as the red and blue paths below. What's more, you can get from any point on the blue path to a point on the red path in a continuum of ways. In short, we get a continuum of paths between the red and blue paths, which sweeps out the face of the pentagon! So the gray region is really a homotopy between homotopies. All the ways you can multiply four loops is captured by this 2-dimensional polytope, which we call $K_4$.
Now the next polytope $K_5$ has one vertex for each of the 14 ways way you can parenthesize five letters. There are 21 edges (corresponding to homotopies) and 9 faces (homotopies between homotopies) and 1 solid interior (a homotopy between the homotopies between the homotopies)!
And the list goes on. The polytopes $K_2,K_3,K_4,\ldots$ form an non-symmetric operad (where $K_1=\varnothing$) with composition being the inclusion of faces. Each $K_n$ is $n-2$-dimensional and the vertices represent the ways of putting parentheses around $n$ letters.
An algebra over this operad is called an $A_\infty$ space, first introduced by Jim Stasheff in the early sixties. (Take note of the word "space!" unlike our previous examples, the $n$-ary operations form a topological space* rather than a vector space!) The "A" stands for "associative" and the infinity reminds us of the infinite string of homotopies between homotopies between homotopies between homotopies between.... And the associahedra are of algebraic, geometric, and combinatorial interest, too! For instance, take a look at this survey by J. L. Loday.
The Little k-Cubes Operad
Closely related to the associahedra is the little $k$-cubes operad, where $k>0$ is a fixed integer. In this example, the set $\mathcal{O}(n)$ of $n$-ary operations forms a topological space---it's the space of all labeled configurations of $n$ $k$-dimensional rectangles within the unit $k$-cube. For example, when $k$=2, here's a picture of a point in $\mathcal{O}(5)$.
So $\mathcal{O}(5)$ is the topological space of all such configurations. That is, if we move the rectangle #4 just a little bit, the new picture we get is a new point in the space $\mathcal{O}(5)$. The $\circ_i$ composition is given by insertion of one picture into the $i$th rectangle of the other, then relabeling. For example
This operad appears** in a seminal paper by topologist Peter May called The Geometry of Iterated Loop Spaces. In short, May answered the question, "Does a topological space have a particular structure if and only if it is (weakly homotopy equivalent to) a $k$-fold loop space?" The answer is
- Yes! When $k=1$, the structure is that of an algebra over the associahedra oeprad.***
- Yes! When $k>1$, the structure is that of an algebra over the little $k$-cubes operad.
In other words, an algebra over the little $k$-cubes operad and a $k$-fold loop space are the same in the eyes of a homotopy theorist. So if you're interested in homotopy theory,**** you'll want to get acquainted with the little cubes operad!
The Simplex Operad
Did you know that topological simplices form an operad?
The standard $n-1$-simplex is defined as $$\Delta^{n-1}=\{(p_1,\ldots,p_n)\in \mathbb{R}^{n}:\sum_{i=1}^np_i=1 \text{ and } 0\leq p_i\leq 1\}.$$ And we can think of each point $p=(p_1\ldots,p_n)$ in $\Delta_n:=\Delta^{n-1}$ as a probability distribution on a discrete set $X=\{1,2,\ldots,n\}$. For example, the point $p=(\frac{1}{2},\frac{1}{2})$ in $\Delta_2$ can represent the distribution of a fair coin toss, while $q=(\frac{1}{6},\ldots,\frac{1}{6})$ in $\Delta_6$ might represent the distribution of rolling a six-sided die.
What's the composition $\circ_i\colon \Delta_n\times\Delta_m\to\Delta_{n+m-1}$? As an example, suppose $m=6$ and $n=2$ with $p$ and $q$ given as above. To compute $p\circ_2 q$, first multiply each of the entries of $q$ by $\frac{1}{2}$, then stick the result in the second entry of $p$.
Notice, the sum of the entries on the right-hand side add up to 1! So we get a bona fide point in $\Delta_{7}$. More generally, I like to think of $p$ as a $n$-ary tree whose leaves are labeled by the $p_i$. Then $p\circ_i q$ is obtained by "painting" the leaves of $q$ with "$p_i$" and then grafting the result onto the $i$th leaf of $p$. For example, the above composition can be pictured as
Convex subsets of $\mathbb{R}^n$ are one example of an algebra over this operad, and this plays a very cool role in information theory. In a wonderful 2011 paper, John Baez, Tobias Fritz, and Tom Leinster used the simplex operad to provide a categorical/topological characterization of Shannon entropy. Baez has a nice summary of their work in this blog post, and Leinster outlined their use of the simplex operad in a recent talk at CIRM.
Other Examples
We've only looked a few examples of operads, but there are tons more! There are cyclic operads (think: Frobenius algebras), modular operads (think: moduli spaces), cacti operads (think: string topology), a phylogenetic operad (think: biology), and even a swiss cheese operad. And hey, why stop at operations with only one output? If we consider $n$-to-$m$ operations, we get something called a properad. For example, Riemann surfaces of genus $g$ with $n$ holes for inputs and $m$ holes for outputs form a properad. And an algebra over this properad is a conformal field theory. And we might even consider the disjoint union of such $n$-to-$m$ operations--called a PROP. And algebra over that gadget is a topological quantum field theory. The list goes on!
Interested in reading more? Here are a few places to start:
- What is... An Operad? by Jim Stasheff (part of the AMS Notices' excellent "What is...?" series)
- Homotopy + Algebra = Operad by Bruno Vallette (p. 37ff contains a long list of examples/applications from algebra, deformation theory, quantum algebra, noncommutative geometry, algebraic topology, differential geometry, algebraic geometry, mathematical physics, and computer science.)
- Algebraic Operads by Bruno Vallette and Jean-Louis Loday
- Operads in Algebra, Topology, and Physics by Martin Markl, Steve Shnider, and Jim Stasheff
- Koszul Duality for Operads by Victor Ginzburg and Mikhail Kapranov
Enjoy!
*But there is an algebraic analogue! We can view each $K_n$ as a CW complex and consider the cellular chain complex of each. These chain complexes assemble into a new operad which is algebraic in nature---each collection of $n$-ary operations forms a differential graded algebra. This operad is called the $A_\infty$ operad and an algebra over it is an $A_\infty$-algebra. For more on $A_\infty$-algebras, check out Homotopy + Algebra = Operad by Bruno Vallette and Introduction to $A$-infinity Algebras and Modules by Bernhard Keller.
**(Added 12/10/17) Here's some history: May coined the word "operad" in his 1972 Iterated Loops Spaces paper, but the concept originated with Joachim Lambek in his 1969 paper Deductive Systems and Categories II. Lambek used the term 'multicategory' which is a generalization of an operad. Also, the little $n$-cubes first appeared in John Michael Boardman's and Rainer Vogt's 1968 Homotopy-everything $H$-spaces, which is cited by May. They also prove the recognition principle (which is the formal name for what I call "May's question" above), although their proof is a bit different than May's.
Sincerest thanks to Prof. Donald Yau for pointing out these historical remarks!
***There's a sense in which the associahedra operad and the little $1$-cubes operad (a.k.a the little intervals operad) are the same.
****Already doing homotopy-things? Be sure to say hi to the folks over at MathOverflow's homotopy chat room!
In this series:
