Hello all,

the information era is scary — people are commenting on a talk before it has even been given… (Or perhaps it is completely normal, but this is the first time it happened to me, and I don’t know exactly how to react. I could of course just pretend I don’t read this blog, while in reality I am refreshing the page every 20 minutes to see if somebody has guessed my whole talk!)

John wrote:

I wonder how Kock’s construction relates to Aguiar and Mahajan’s

I don’t want to ‘give away’ the talk, but a short answer is given below, after a few comments on related issues.

**Re universal property**

Connes and Kreimer discovered a universal property: the linear operator B^{+} on H that adjoins a common root to a forest is the universal 1-cocycle for Cartier-Hochschild cohomology. This amounts to the fact that

Δ B^{+} = (B^{+} ⊗ Id + e ⊗ B^{+}) Δ

and that any Hopf algebra with a linear operator satisfying this equation admits a unique Hopf algebra map from H compatible with the linear maps. Moerdijk (1999) soon found a nice conceptual explanation: for an operad P, let P[t] denote the operad obtained by freely adjoining a unary operation. If P is a Hopf monad, then P[t](0) becomes a Hopf algebra, and t itself becomes a 1-cocycle. The Connes-Kreimer Hopf algebra H is nothing but Comm[t](0), and B^{+} is t.

In other words,

(H,B^{+}) is the initial Comm[t]-algebra.

Concerning trees as initial algebra: polynomial functors cartesian over M (the free-monoid monad) are precisely nonsymmetric operads. The terminal object in Poly/M is of course just M itself, and its initial algebra is the set of planar trees. In other words, planar trees are M-trees. Nonplanar trees are not P-trees for any polynomial functor, and in fact the category of polynomial functors does not have a terminal object. The terminal object that ‘ought’ to exist is the free-commutative-monoid monad which is not polynomial (for example, it does not preserve pullbacks). It is instead analytical — it is the exponential! (It is analogous to saying that the terminal G-set is not free.)

(Over infinity-groupoids instead of sets, the difference between ‘polynomial’ and ‘analytic’ evaporates, as you can imagine. This is a main point of the theory of homotopical species — which at the moment has been written down but not written up.)

On the other hand, while nonplanar trees cannot be characterised as initial algebra *for* a polynomial endofunctor, they *are* themselves polynomial endofunctors: the polynomial endofunctor corresponding to a tree is A ← M → N → A, where A is the set of edges, N is the set of nodes, and M is the set of nodes with a marked input edge. (The first map returns the marked edge, the second forgets the mark, and the third map returns the output edge.) This makes it very convenient to talk about decorated trees (like opetopes) in terms of polynomial functors. (In my paper ‘Polynomial functors and trees’ I argue that this viewpoint on trees is in fact a practical *definition* of tree.)

**Re the role of polynomial functors**

Polynomial functors correspond to flat species, i.e. those for which the symmetric-group actions are free. Analytical functors are more expressive than polynomial functors. But many interesting analytical functors happen to be flat (for example the sequence of opetope monads of Baez-Dolan, at least the version given in Leinster’s book). In such cases the polynomial viewpoint is powerful because it exploits representability. Handling polynomial functors in terms of their representing diagrams I ← E → B → J was advocated by Joyal. Polynomial functors allow many interesting intrinsic characterisations (e.g. as local right adjoints), whereas the ‘bridge’ diagram is just a presentation. Perhaps many category theorists or geometers will feel that the intrinsic viewpoint is better. But in combinatorics a ring is not just a ring: typically, specific bases carry the combinatorial information, and change-of-bases can amount to deep combinatorial identities. Polynomial functors in the bridge-diagram viewpoint is very much about combinatorics. A more combinatorial approach to data type theory also seems to be in the air — cf. scattered remarks in the recent literature.

**Re the typicalness of minus signs in antipodes**

Combinatorial bialgebras B are most often graded connected: graded because they have bases given by combinatorial structures, and these have sizes (or otherwise simply because B is a polynomial algebra), and connected (i.e. B_{0}=k) because there is only one zero-size structure. It is a general fact that a connected graded bialgebra has an antipode — provided k is a ring! The formula is given by recursion by degree, and it always involves minus signs (-1)^{n} where n is the degree. Since an antipode is unique if it exists, a connected graded bialgebra over N never has an antipode. On the other hand, combinatorial bialgebras ought to be defined over N. Perhaps one can say (sorry if this is superficial) that the availability of additive inverses is the major trick of algebraic combinatorics?! Additive inverses are crucial for getting multiplicative inverses, as in Möbius inversion, Lagrange inversion, Birkhoff decomposition, etc. — the basic example is really matrix inversion!

**Re categorification of Hopf algebras**

Aguiar and Mahajan have found a very good way to put combinatorics into vector spaces, lifting the constructions to a categorical level. Extremely elegant. But the outcome still has the magic of algebra — the minus signs are not really explained, they are just part of the magic. To understand the minus signs, I would like to go as far as

possible just working with finite sets. The recent paper by Lawvere and Menni on the Hopf algebra of Möbius intervals is a good expression of the philosophy. The categorified antipode does not exist on its own, but it can be written as a difference between an even-degree antipode and an odd-degree antipode. Part of the game is the strive for introducing the minus sign as late as possible. And of course it becomes more and more urgent to understand what are negative sets, for example in the sense of Schanuel. Unfortunately this is very hard.

The categorification of the Connes-Kreimer Hopf algebra that I will talk about at the CT is mostly an example computation to showcase the combinatorial content of polynomial functors. But I hope it will develop into a more well-organised theory that should be a multi-version of Lawvere-Menni theory: a tree should be seen as a multi-interval. I hope there will soon be things like ‘Möbius multicategories’, in analogy with Leroux’s Möbius categories studied by Lawvere and Menni, and so on. In fact, since multicategories are just polynomial functors with a double-categorical monad map to M, it may be convenient to go instead for ‘Möbius polynomial functors’…

**Re numerical analysis**

There is an ongoing research trimester in Madrid on Combinatorics and Control, covering topics like pertubative quantum field theory, numerical integration theory, and control theory. The final conference of the programme is next week, and the speakers include Butcher, Ebrahimi-Fard, Hairer, Kawski, Munthe-Kaas.

I participated in the School earlier this Spring — it was a

fantastic experience, it opened a new world for me. It is very comforting for a pure mathematician to see advanced algebraic structures in use in very applied mathematics. What they are doing in control theory is still quite obscure to me (although Kawski gave a very entertaining example computation, showing how the differential equations and controls involved in parking a car (steering wheel and gas pedal) lead to nested integrals, brackets and pre-Lie structure!). But the numerical analysis has impressed me very much, and I want to learn more about it.

An alternative to Butcher’s book is Hairer, Lubich, and Wanner’s *Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations*, Springer, 2002. It is somewhat more algebraic, and does not avoid Hopf algebras and Lie theory.

Cheers,

Joachim.

## Re: This Week’s Finds in Mathematical Physics (Week 299)

I’d like to add that the Connes-Kreimer theory is explained in the book “Noncommutative Geometry, Quantum Fields and Motives” that is available for free here.

So “Quantum leap” is now a phrase that means a big step, instead of the “smallest possible”? :-)

They do :-), one omnipresent kind that grows this way is the B-tree. (I heard a talk of its inventor Rudolf Bayer a couple of years ago, and he confirmed that “B” does not have a specific meaning. It’s a little bit like the M in M-theory).

Nitpicking: This may be confusing to someone who did not take a QM class, because taken at face-value this is true for the spacecoordinates (x ,y, z) of a particle, too (if you know one you don’t know anything about the others). Something along the lines “complementary means that a Heisenberg uncertainty relation holds” would avoid this.