Joachim's web pages [Home] [Math] [Cat]

### Polynomial functors

A polynomial functor (of one variable) is an endofunctor of the category of sets, built from disjoint unions, products, and exponentiation. They are the categorification of polynomials with natural-number coefficients, and many constructions and results about such polynomials of numbers can be explained on the level of polynomials of sets, e.g. basic constructions like sums, products, substitutions, differentiation, and their basic properties, like the Leibniz rule and the chain rule. Just as for polynomials you can perform many manipulations solely in terms of the coefficients, the operations on polynomial functors can be performed in terms of sets. The theory of polynomial functors has applicatons to combinatorics, type theory, topology, operads and higher category theory.

• Notes on polynomial functors
Very preliminary draft, 420pp. Version 2009-08-05.
These notes gather a lot of different stuff - it's just a heap of annotations. Many sections are in a very preliminary and sketchy form or full of superfluous details.
I recommend instead the papers listed below.

See also the page on Combinatorics of graphs and trees in perturbative quantum field theory

• Local fibered right adjoints are polynomial
With Anders Kock. To appear in Math. Struct. Comput. Sci. ArXiv:1005.4236

Abstract: For any locally cartesian closed category E, we prove that a local fibered right adjoint between slices of E is given by a polynomial. The slices in question are taken in a well known fibered sense.

• Polynomial functors and polynomial monads
With Nicola Gambino. Math. Proc. Cambridge Phil. Soc. 154 (2013), 153-192. ArXiv:0906.4931

Abstract: We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.

• Polynomial functors and trees
Int. Math. Res. Not. 2011 (2011), 609-673. ArXiv:0807.2874

Abstract: We explore the relationship between polynomial functors and trees. In the first part we characterise trees as certain polynomial functors and obtain a completely formal but at the same time conceptual and explicit construction of two categories of rooted trees, whose main properties we describe in terms of some factorisation systems. The second category is the category Ω of Moerdijk and Weiss. Although the constructions are motivated and explained in terms of polynomial functors, they all amount to elementary manipulations with finite sets. Included in part 1 is also an explicit construction of the free monad on a polynomial endofunctor, given in terms of trees. In the second part we describe polynomial endofunctors and monads as structures built from trees, characterising the images of several nerve functors from polynomial endofunctors and monads into presheaves on categories of trees. Polynomial endofunctors and monads over a base are characterised by a sheaf condition on categories of decorated trees. In the absolute case, one further condition is needed, a projectivity condition, which serves also to characterise polynomial endofunctors and monads among (coloured) collections and operads.

• Polynomial functors and opetopes
With André Joyal, Michael Batanin, and Jean-François Mascari.
Adv. Math. 224 (2010), 2690-2737. ArXiv:0706.1033

Abstract: We give an elementary and direct combinatorial definition of opetopes in terms of trees, well-suited for graphical manipulation (e.g. drawings of opetopes of any dimension and basic operations like sources, target, and composition); a substantial part of the paper is constituted by drawings and example computations. To relate our definition to the classical definition, we recast the Baez-Dolan slice construction for operads in terms of polynomial monads: our opetopes appear naturally as types for polynomial monads obtained by iterating the Baez-Dolan construction, starting with the trivial monad. Finally we observe a suspension operation for opetopes, and define a notion of stable opetopes. Stable opetopes form a least fixpoint for the Baez-Dolan construction. The calculus of opetopes is also well-suited for machine implementation: in an appendix we show how to represent opetopes in XML, and manipulate them with simple Tcl scripts.

• Categorification of Hopf algebras of rooted trees
Centr. Eur. J. Math. 11 (2013), 401-422.

Abstract: We exhibit a monoidal structure on the category of finite sets indexed by P-trees for a finitary polynomial endofunctor P. This structure categorifies the monoid scheme (over Spec N) whose semiring of functions is (a P-version of) the Connes—Kreimer bialgebra H of rooted trees (a Hopf algebra after base change to Z and collapsing H0). The monoidal structure is itself given by a polynomial functor, represented by three easily described set maps; we show that these maps are the same as those occurring in the polynomial representation of the free monad on P.

• Data types with symmetries and polynomial functors over groupoids
Proceedings of the 28th Conference on the Mathematical Foundations of Programming Semantics, Bath 2012, Electronic Notes in Theoretical Computer Science 286 (2012), 351-365. ArXiv:1210.0828

Abstract: Polynomial functors (over Set or other locally cartesian closed categories) are useful in the theory of data types, where they are often called containers. They are also useful in algebra, combinatorics, topology, and higher category theory, and in this broader perspective the polynomial aspect is often prominent and justifies the terminology. For example, Tambara's theorem states that the category of finite polynomial functors is the Lawvere theory for commutative semirings [Tambara], [Gambino-Kock]. In this talk I will explain how an upgrade of the theory from sets to groupoids (or other locally cartesian closed 2-categories) is useful to deal with data types with symmetries, and provides a common generalisation of and a clean unifying framework for quotient containers (in the sense of Abbott et al.), species and analytic functors (Joyal 1985), as well as the stuff types of Baez and Dolan. The multi-variate setting also includes relations and spans, multispans, and stuff operators. An attractive feature of this theory is that with the correct homotopical approach — homotopy slices, homotopy pullbacks, homotopy colimits, etc. — the groupoid case looks exactly like the set case. After some standard examples, I will illustrate the notion of data-types-with-symmetries with examples from perturbative quantum field theory, where the symmetries of complicated tree structures of graphs play a crucial role, and can be handled elegantly using polynomial functors over groupoids. (These examples, although beyond species, are purely combinatorial and can be appreciated without background in quantum field theory.) Locally cartesian closed 2-categories provide semantics for a 2-truncated version of Martin-Löf intensional type theory. For a fullfledged type theory, locally cartesian closed ∞-categories seem to be needed. The theory of these is being developed by David Gepner and the author as a setting for homotopical species, and several of the results exposed in this talk are just truncations of ∞-results obtained in joint work with Gepner. Details will appear elsewhere.

Last updated: 2013-01-10 by Joachim Kock.