In week239 of This Week’s Finds, read about the n-Category Café, the resignation of the editorial board of Topology, the open access movement, Freeman Dyson’s 1951 lecture notes, the origins of mathematics in little clay figures called “tokens”:
and - leaping straight from 8000 BC to the twentieth century - Koszul duality for L∞-algebras!
TrackBack URL for this Entry: http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/929
Urs writes:
I was chatting with Dr. Doctrine over at another table in our café. Is Dr. Operad also around? I am suffering from some operad amnesia!
I’m sorry, Dr. Operad is operating on a patient right now.
However, Dr. Doctrine knows all about this stuff, since operads are yet another example of a doctrine! And, he’s on a coffee break - I see him over there! So, I’ll call him over and let him explain it all.
[Exit the waiter JB.]
[Enter Dr. Doctrine, who looks suspiciously similar, but with a doctor’s gown hastily thrown on.]
So, what’s ailing you now?
I have read a couple of things, and forgot two thirds of it again. I can sort of give the definition of an operad - mainly because I know it’s just a way of not admitting that one is talking about a multicategory, which is an entirely obvious and natural concept.
You’re almost right. Frank Adams and Saunders Mac Lane invented PROs and PROPs, and later Mac Lane invented monoidal and symmetric monoidal categories; Peter May invented operads, and Joachim Lambek invented multicategories. They are all very similar things.
They’re all just ways of generalizing categories to have morphisms with a list of input objects:
or else a list of input objects and a list of output objects:
We can compose these multimorphisms or operations in ways that are evident from thinking of them as black boxes with a bunch of input wires and a bunch of output wires: we hook up the outputs of some boxes to the inputs of others. Of course the objects need to match when we do this, or we’ll blow a fuse.
Besides whether we allow many outputs or not, we also have a choice about whether we get to permute the inputs and outputs.
Here are the four main options:
(Just to confuse you, sometimes people call an operad a symmetric or permutative operad, and call a multicategory a planar or nonpermutative operad.)
But what precisely again is an algebra for an operad??
In every case, these “algebras” are just what you and I wish people would call “representations” or “actions”: it’s a thing where the abstract operations of our operad get mapped to actual operations on sets, compatible with all the ways of composing operations and permuting inputs.
(Here I’m talking about algebras in the symmetric monoidal category of sets - we could also do vector spaces, or chain complexes, etcetera.)
Back in week191 I drew a bunch of pictures to explain operads. So, let’s look at those.
In what follows I’m talking about untyped operads, namely those with only one object, or “type”. In this case we don’t need to get so fancy and write
Instead, we can simply say that is an n-ary operation, or
An algebra of an untyped operad will just be a single set, with a bunch of n-ary operations on it coming from the operations in .
Anyway, here’s what I said:
So: what's an operad? An operad O consists of a set O_n of abstract `n-ary operations' for each natural number n, together with rules for composing these operations. We can think of an n-ary operation as a little black box with n wires coming in and one wire coming out:
\ | / \ | / \ | / ----- | | ----- | |
We're allowed to compose these operations like this:
\ / \ | / | \ / \ | / | ----- ----- ----- | | | | | | ----- ----- ----- \ | / \ | / \ | / \ | / \ | / \ | / \ | / ----- | | ----- | |
feeding the outputs of n operations g_1,..,g_n into the inputs of an n-ary operation f, obtaining a new operation which we call f o (g_1,...,g_n). We demand that there be a unary operation serving as the identity for composition, and we impose an "associative law" that makes a composite of composites like this well-defined:
\ / | \ | / \ / \ / | \ | / \ / --- --- --- --- | | | | | | | | --- --- --- --- \ | / / \ | / / \ | / / ----- ----- ----- | | | | | | ----- ----- ----- \ | / \ | / \ | / \ | / \ | / \ | / \ | / ----- | | ----- | | (This picture has a 0-ary operation in it, just to emphasize that this is allowed.) We can permute the inputs of an n-ary operation and get a new operation:
\ / / / / / \ / / / / / \ \ | / ----- | | ----- | |
We demand that this give an action of each permutation group S_n on each set O_n. Finally, we demand that these actions be compatible with composition, in a way that's supposed to be obvious from the pictures. For example:
\ | / | \ / \\\ / / / \ | / | \ / \\/ / / --- --- --- /\\ / / | a | | b | | c | / \\/ / --- --- --- / / / \ / / / / /\\ \ / / / | | \\\ \ / / / | | \\\ / / --- --- --- / \ / = | b | | c | | a | / / --- --- --- / / \ \ | / \ | / \ | / ----- ----- | d | | d | ----- ----- | | | |
That's all there is to it!
And, just as a group can act on a set, so can an operad O, each abstract operation f in O_n being realized as actual n-ary operation on the set in a manner preserving composition, the identity, and the permutation group actions. A set equipped with an action of the operad O is usually called an algebra of O, though personally I'd prefer to call it an "action" of O on the set.
You might enjoy describing an algebra of an operad as some sort of “model” in the style we’ve been discussing lately, something like
We can, in fact, do this for all 4 concepts listed earlier! We’re really just dealing with lots of different doctrines here - categories with extra structure, namely the structure of having “multimorphisms” of various sorts. ]
Oh, it’s that simple. Thanks for letting me join the ride on ground floor!
You might enjoy describing an algebra of an operad as some sort of “model” in the style we’ve been discussing lately
Okay, good. I will think about it. Not right now, because I need to catch the train that will take me into the weekend. But later.
By writing what I’m about to write, I’m surely crossing some kind of line of crustiness. But evidently, I can’t resist.
John writes:
In a multicategory … we cannot permute the inputs.
In an operad … we can permute the inputs.
He goes on to make the distinction between typed (many-object) and untyped (one-object) structures.
It’s just terminology. But, being crusty, I want to convince you that to use terminology in the way John describes is a really bad idea.
(Of course, it’s not just John - don’t take it personally! There’s that Dr Doctrine fellow who does it too… and there are many other deviants out there.)
Here are two design criteria to be used when choosing terminology:
1. When a structure comes in both one-object and many-object versions, choose different words for the two.
For example, it’s good that “monoid” and “category” are entirely different words, even though monoids are just one-object categories and categories can be thought of as many-object monoids. Why? Well, on the one hand, the theory of monoids is interesting in its own right, and there are lots of things you can do with monoids that don’t extend to general categories. On the other, it’s very often not natural or helpful to think of categories as many-object monoids - e.g. who ever understood adjunctions by first understanding adjunctions between monoids?
Another example: the words “group” and “groupoid” are different, but probably not different enough: their similarity seems to have contributed to the false impression that groupoids are just some trivial variant of the group idea, and the ensuing anti-groupoid feeling.
2. When a structure comes in both symmetric and non-symmetric versions, use the same word, with or without an adjective.
For example, we say “ring” and “commutative ring”, “group” and “abelian group”, “monoidal category” and “symmetric monoidal category”. This is good.
(Aside: it is of course fine to, say, begin a book on algebraic geometry by declaring “‘ring’ will always mean ‘commutative ring’”. Here I’m talking about the language one uses when not abbreviating.)
John suggests using “operad” vs. “multicategory” to mean symmetric vs. non-symmetric, with an optional adjective “untyped” or “typed” to indicate one-/many-object.
This breaks Rule 1, i.e. it makes the one-object/many-object distinction look unimportant. (This is like saying that a category theorist is basically just a semigroup theorist: very dangerous.)
It also breaks Rule 2, i.e. it exaggerates the difference between the symmetric and non-symmetric versions. (It’s as bad as having totally different words for “monoidal category” and “symmetric monoidal category”.)
The correct choice, say I, is to use
operad to mean the one-object version
multicategory to mean the many-object version
preceded by the adjective “symmetric” if appropriate. This respects both Rules.
(Aside, again: many authors use “operad” to mean what would more precisely be called a “symmetric operad”, but this is no problem - it’s just like the algebraic geometry author’s use of “ring”.)
If you’re not already convinced, let’s try stating a little theorem. Any monoidal category has an underlying multicategory, obtained by forgetting the “tensor product” but remembering what the “multilinear maps” are. If the monoidal category has a symmetric structure then so does the multicategory. So, in the terminology that I think is sensible:
a. every monoidal category has an underlying multicategory;
b. every symmetric monoidal category has an underlying symmetric multicategory.
In the terminology that John describes, this reads:
a. every monoidal category has an underlying typed multicategory;
b. every symmetric monoidal category has an underlying typed operad.
Isn’t the first rendition better?
Historically, multicategories were originally many-object and non-symmetric (though their inventor, Lambek, is a category theorist and would surely have appreciated that to add symmetries is no big deal). Operads were originally one-object and symmetric (though an important example of the non-symmetric version, Stasheff’s operad of associahedra, was there from the start). So neither John nor I quite has history on our side, although that doesn’t bother me: terminology is always being revised as ideas progress.
It’s clearly time for my lie-down. But before I go, I gruffly bark “an operad is a one-object multicategory! no more, no less…” And drifting into sleep, I deliriously mutter something about how those “ancient tokens” pictured in This Weeks Finds are obviously just someone’s home-baked cookies…
Tom
Tom wrote:
By writing what I’m about to write, I’m surely crossing some kind of line of crustiness. But evidently, I can’t resist.
Hey! It’s Doctor Operad!
Good to see you here; I’ve been hoping you’d show up. If I’d been really smart, I would have deliberately munged some terminology regarding operads and multicategories, just to goad you into joining the conversation.
John suggests using “operad” vs. “multicategory” to mean symmetric vs. non-symmetric, with an optional adjective “untyped” or “typed” to indicate one-/many-object.
I wasn’t really “suggesting” this; I was attempting to report how people actually use various words. But I screwed up, because I was also trying to fit these concepts into the general theme of doctrines, which I’ve been explaining to Urs lately, treating doctrines as “categories with extra bells and whistles”. That pushed me into taking the “typed” or “many-object” case as the default for multicategories, operads, PROs and PROPs… which isn’t historically true, at least for operads.
But then, when I cited week191, where I’d been taking the “untyped” case as the default, I had to mention this untyped option.
In short, it was a complete debacle. Now that Urs has some rough sense of how people actually use these words, I’m very happy for you to step in and tell us what would be best. I don’t have any strong opinions, except that I hate the terminological quagmire that surrounds this really very pretty subject.
Another example: the words “group” and “groupoid” are different, but probably not different enough: their similarity seems to have contributed to the false impression that groupoids are just some trivial variant of the group idea, and the ensuing anti-groupoid feeling.
Have you read David Corfield’s post about Discrimination against -oids? You seem to be agreeing with Alain Connes, somewhat.
I actually have a fondness for “-oid” as a suffix denoting the many-object version of a familiar (secretly one-object) algebraic gadget. People already use this for groupoids, ringoids, algebroids, Lie algebroids, Hopf algebroids, and quantum groupoids. So, I’ve even taken to using oidization as a name for this process of “many-object-ifying” algebraic gadgets - mainly when I’m correcting people who mix it up with “categorification”.
Of course, the word “monoid” drastically breaks this cute little pattern of using “-oid” for many-object versions. And we should all be very, very thankful that Eilenberg and Mac Lane did not call categories “monoidoids”.
So, a completely systematic terminology will have to be postponed until the Revolution. But for now I’m quite willing to support your suggestions, with the exception that I like “-oids” for multi-object versions, at least when it’s not too silly-sounding.
(I will not use “operadoid” for “multicategory”.)
And drifting into sleep, I deliriously mutter something about how those “ancient tokens” pictured in This Week’s Finds are obviously just someone’s home-baked cookies…
It’s possible that when the agricultural revolution occurred around 8000 BC, primitive attempts at baking led to large numbers of rock-hard cookies.
John wrote:
If I’d been really smart, I would have deliberately munged some terminology regarding operads and multicategories, just to goad you into joining the conversation.
Yup, that would have worked…
Regarding the “pejorative suffix ‘oid’”, I don’t know. Before I read that quote of Connes, I’d never contemplated the suffix ‘oid’, and right now the only usage in non-mathematical English that I can think of is “humanoid”. I don’t think humanoid is an insult - it’s not their fault!
Lie algebroids are an interesting example. Before I saw the definition, I assumed that, like Lie algebras, they would be completely algebraic gadgets. So I was shocked to discover that a Lie algebroid has an underlying manifold. This makes it feel really different from a Lie algebra.
I guess I agree that it would be good to have a suffix meaning “many-object” (while maintaining that monoids and categories are so different as to deserve totally different names). “Oid” seems fine. Maybe the ideal would be to use oid as the systematic suffix, but allow “X-oid” to be replaced by a completely different word if a suitable one comes along.
John also wrote:
I hate the terminological quagmire that surrounds this really very pretty subject.
Who could argue with that?
Once upon a time I thought the quagmire would quickly be… drained? Dried out? Whatever makes a quagmire more pleasant. I thought that people, being sensible, would realize that we obviously need to make the terminology systematic, and would pull together to make it happen.
What I hadn’t taken into account was the effect of the existing literature. For example, the Australian school did pioneering and crucial work on higher category theory in the 1970s and 80s, and people use their results, hence their terminology, all the time. I don’t think anyone could blame them for not having invented the optimal terminology at the same time as doing this pioneering work. I guess the obvious example is something like this: in that literature, strong monoidal functor, pseudonatural transformation, and homomorphism of bicategories all mean what I (and I think you, John) would call a weak whatever.
Maybe another problem is that ‘weak’ is such an uninspiring word. In my quest for something better, I’ve gone as far as consulting a thesaurus but nothing’s leapt out. My brief flirtation with ‘fair’ came to nothing. Some people seem to want to use ‘pseudo’ as the up-to-isomorphism word, which I don’t like much, though I can’t think of any argument saying that ‘weak’ is better. Does Jim Dolan have any bright ideas?
It seems that -oid is pejorative in the modern slang of the hacking community.
jargon (from “android”) A suffix used as in mainstream English to indicate a poor imitation, a counterfeit, or some otherwise slightly bogus resemblance. Hackers will happily use it with all sorts of non-Greco/Latin stem words that wouldn’t keep company with it in mainstream English. For example, “He’s a nerdoid” means that he superficially resembles a nerd but can’t make the grade; a “modemoid” might be a 300-baud modem (Real Modems run at 144000 or up); a “computeroid” might be any bitty box.
Also a commenter on my blog pointed to the OED:
1992 N.Y. Times Bk. Rev. 26 Apr. 1/1 Lately..words that end in ‘oid’ have become synonyms for the meretricious: sleazoid, Marxoid, tabloid.
About a substitute for ‘weak’, isn’t the best solution to use nothing, reserving the unmarked noun for the most important case?
Tom writes:
Maybe another problem is that ‘weak’ is such an uninspiring word. In my quest for something better, I’ve gone as far as consulting a thesaurus but nothing’s leapt out. My brief flirtation with ‘fair’ came to nothing. Some people seem to want to use ‘pseudo’ as the up-to-isomorphism word, which I don’t like much, though I can’t think of any argument saying that ‘weak’ is better. Does Jim Dolan have any bright ideas?
Since it actually takes bigger muscles to handle weak n-categories than strict ones, I have proposed calling them macho n-categories. I think that’s pretty inspiring.
Jim’s bright idea was to call them simply n-categories. Surely we all know that’s the ultimate solution. But alas, right now there are more definitions of these n-categories than theorems relating them.
So, we have to prove a bunch of such theorems, and then a bunch of theorems relating such theorems, and so on, adding cells of higher and higher dimensions until the ∞-category of definitions of ∞-category becomes equivalent to the terminal ∞-category, giving a “unique” definition in the macho sense of the term “unique”.
This may take a while.
What little I know about this subject does indeed come from cursory interaction with Tom Leinster’s book on operads.
I did take home from this reading the message that operads are just a special case of multicategories (namely with a single object and special symmetry properties).
What I particuarly enjoyed was the characterization of multicategories as monads in a souped-up version of the bicategory of spans (section 4.2 in Tom Leinster’s book).
I am not sure yet if that perspective is helpful for attacking the exercise that Dr. Doctrine has posed, but in any case it is nice.
Just because it’s so nice, I say it again, in my words.
An ordinary category internal to is the same as a monad in the category of spans in . So it is a span with both “feet” identical
“Horizontal” composition is by pullback
and the multiplication in the mondad is given by a morphism
going diagonally through
and making everything commute.
So, such a monad in spans in is indeed a category internal to .
Now, the bicategory of spans in can be regarded as a special case of a more general bicategory, where we pick any monad on and use spans of the form
The above was the special case with being the identity.
Now horizontal composition of such -spans is essentially as before, only difference being that we apply to the entire span on the left before composing by means of pullback.
By choosing appropriate , one obtains this way generalizations of the notion of category where morphisms have not just an ordinary source object, but instead a “T-source object”.
In particular, if and if is the monad of free monoids, then a monad in “-spans” in is a plain multicategory, whose morphisms have a tuple of elements in as input and one such element as output.
(That’s example 4.2.7 on pp. 111 of Tom Leinster’s book.)
Dr. preOperad here
The essential idea of an algebra over an
operad is that of multivariable functions to one variable and the various compositions. The operad encodes the `laws’ of a class of algebras, e.g. associative algebras including not just the binary operation but all its n-ary consequences.
Es steht im buch!
jim
Is there a reason why when anyone gives examples of Koszul duality it’s always:
Are there no more familiar examples?
David writes:
Is there a reason why when anyone gives examples of Koszul duality it’s always:
- Commutative Lie
- Associative Associative
Are there no more familiar examples?
Well, there may be more general forms of Koszul duality, but I only know it for quadratic operads. Roughly, these describe vector spaces with a bunch of binary operations satisfying binary and ternary relations.
For example, in an associative algebra we have the binary product satisfying the ternary law
while in a Lie algebra we have a binary bracket satisfying the ternary Jacobi identity:
The commutative law in a commutative algebra and the anticommutative law in a Lie algebra are binary.
(What about the unit in an associative algebra? That’s not a binary operation - it’s nullary. Surprise! I was secretly talking about nonunital associative algebras. Ditto for commutative ones.)
So, what other examples do I know? One nice one is a Poisson algebra: this has two binary operations. Ever since writing week238, I’ve been wondering what the Koszul dual of the Poisson operad is. I seem to recall it being mentioned in Ginzburg and Kapranov’s paper, but that paper is not on the arXiv. Can anyone get ahold of it and look?
Another obvious one is the operad for magmas in Vect: vector spaces equipped with a binary product satisfying no laws at all (except bilinearity, e.g. the distributive law). In some rough sense, the fewer laws a quadratic operad has, the more its dual has. So, I think the dual of the operad for magmas in should describe some “maximally lawful” gadget with a binary product.
I guess this means a vector space with a binary product that vanishes identically! Call it an “abelian Lie algebra” if it makes you feel happier, or a “vector space” if you want to come clean and admit this is no extra struture at all.
Boring - but the dual of something boring should be boring.
Hmm. I just thought of another example, namely Leibniz algebras: vector spaces equipped with a bracket that satisfies the Jacobi identity in this form
but not necessarily antisymmetry. These are nice because the Jacobi identity, written this way, says “bracketing by is a derivation w.r.t. the bracketing operation.”
I’m too lazy to figure out the Koszul duals of these guys, at least tonight.
I wonder what kind of world quadratic operads live in then, i.e., what is the richest structure on the collection of all of them. And same question for all operads.
Wait a minute, a bell has been rung. Loday’s Completing the Operadic Butterfly says something about all this. Looks like you were on the right track!
Loday’s organising a conference Operads2006 (Two days on the interaction between operads, differential geometry, computer sciences, and other topics), abstracts.
I wonder what kind of world quadratic operads live in then, i.e., what is the richest structure on the collection of all of them. And same question for all operads.
I wrote a long reply to your second question here, but accidentally lost it. So, I’ll be brief and perhaps a bit cryptic.
Suppose by “operad” we mean “untyped operad with a set of operations of each arity”. Such an operad is a special sort of “species” in Joyal’s sense.
For those not in the know, a species is just a functor
An operad is an example of such a thing, assigning to each finite set some set of -ary operations.
A species can dually be thought of as a groupoid over the groupoid of finite sets:
where the functor is faithful, or in other words, forgets at most structure. Such a thing describes sets equipped with extra structure. So, we also call species structure types. If we drop the faithfulness requirement, we get stuff types.
Structure types form the free symmetric 2-rig on one object, . This is a categorified version of the polynomial rig , which is the free commutative rig on one generator.
Just as we can compose polynomials, we can compose structure types. Just composition makes polynomials into a monoid, composition makes structure types into a monoidal category.
And, a monoid in this monoidal category is precisely an operad!
So, operads live in an interesting world.
Quadratic operads live in a somewhat different world, since they necessarily have a vector space of operations of each arity. But, it’s a parallel world.
Suppose by “linear operad” we mean “untyped operad with a vector space of operations of each arity” - where of course we assume composition is multilinear.
Then, a linear operad is a monoid object in the monoidal category of linear species - that is, functors
The category of linear species deserves to be called , just as the category of species is .
You can play this game with any symmetric 2-rig taking the place of or .
So, from a certain high-falutin’ viewpoint, what we’re doing in the theory of operads is categorifying polynomial rigs, noting that composition in here gives us an extra tensor product, and using the microcosm principle to look at monoids in the resulting monoidal categories. This suggests all sorts of generalizations. But, what’s wonderful is that species are actually very practical in combinatorics, while operads are practical in topology, algebraic geometry, and string theory!
I’ll take the liberty of posting the following reply from Jean-Louis Loday, which clears up some confusions:
Dear John,
Thanks for advertising the Conference Operads 2006, which ended yesterday. It went pretty well.
I found this ad by chance on the Net. You were discussing Koszul duality of operads. Let me just mention that the dual of the Leibniz operad is the Zinbiel operad. A Zinbiel algebra has one binary operation which satisfies the following relation:
(1)It is related to commutative algebras as follows: the symmetrization of the operation is associative and (of course) commutative. So it is similar to As and Lie.
Reference:
- J.-L. Loday, Dialgebras, in Dialgebras and Related Operads, Springer Lecture Notes in Math. 1763 (2001), 7-66.
As for the magmatic operad (free operad on one binary operation) its Koszul dual is not really what you said. It is the nilpotent operad: one binary operation (nontrivial), where every product of three variables is 0. It may look boring, but in fact it may also be very helpful in proving some complicated formulas, see for instance:
- J.-L. Loday, Inversion of integral series enumerating planar trees, Séminaire Lotharingien Comb. 53 (2005), exposé B53d, 16pp.
where I give an easy proof for the inversion of the generic formal power series in terms of free operad.
You’ll find other papers with several computations of Koszul dual of operads (Dendriform, 2-associative, PreLie, Dipterous, Quadri, etc…) on my home-page.
Best. JLL
Well done, John, for encouraging Dev Sinha to write The homology of the little disks operad.
Thanks. He gave a fascinating talk on this operad in Calgary, and I wrote about it in week220.
The main cool result is an old one by Frederick Cohen. By functorial abstract nonsense, the homology of the little -cubes operad is itself an operad, living in the category of vector spaces. But what is it?
It’s the operad whose algebras are graded Poisson algebras with a bracket of degree !
So, the homology of any -fold loop space has a Poisson bracket of degree on it. That’s great if you’re a topologist. But Poisson brackets are important in classical mechanics. So, what does it all mean in terms of physics???
I wish I knew.
Dev Sinha’s proof is beautifully geometrical, with the Poisson bracket given by a “planet” (one little -cube) orbiting its “sun” (another little -cube) in a -dimensional “orbit”. The proof of the Poisson algebra identities then involves a moon orbiting a planet orbiting a sun…
Alas, I can’t see any way to connect all this celestial imagery to the role of Poisson brackets in classical mechanics. It would be so darn cute if it worked.
operad co-operation
I was chatting with Dr. Doctrine over at another table in our café. Is Dr. Operad also around? I am suffering from some operad amnesia!
I have read a couple of things, and forgot two thirds of it again. I can sort of give the definition of an operad - mainly because I know it’s just a way of not admitting that one is talking about a multicategory, which is an entirely obvious and natural concept.
Also, I know when to impress people by yelling “That’s just the little-disk operad!” when I see cobordisms being composed, and the like.
But what precisely again is an algebra for an operad??
I know that this is in a sense the crucial point of operads in the first place, but still, I can’t quite recall.
Of course I know where I could look this up. But chatting about it is much more fun.