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

Notes on 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.

Table of contents:

  {Preface}{iii}
  {Introduction}{1}
    {Historical remarks}{4}
{PART I Polynomial functors in one variable}{9}
    {{0.0}Prologue: natural numbers and finite sets}{11}
  {{1}Basic theory of polynomials in one variable}{17}
    {{1.1}Definition}{19}
    {{1.2}Examples}{24}
    {{1.3}Other viewpoints}{28}
    {{1.4}Basic operations on polynomials}{30}
    {{1.5}Composition of polynomials (substitution)}{34}
    {{1.6}Differential calculus}{40}
    {{1.7}Properties of polynomial functors}{43}
  {{2}Categories of polynomial functors in one variable}{45}
    {{2.1}The category $\text {\textbf {\textsl {Set}}}[X]$ of polynomial functors}{46}
      {Cartesian morphisms}{48}
    {{2.2}Sums, products}{54}
    {{2.3}Algebra of polynomial functors: categorification and Burnside semirings}{56}
    {{2.4}Composition}{60}
    {{2.5}The subcategory $\text {\textbf {\textsl {Poly}}}$: only cartesian natural transformations}{60}
      {Products in $\text {\textbf {\textsl {Poly}}}$}{63}
      {Differentiation in $\text {\textbf {\textsl {Poly}}}$}{65}
  {{3}Aside: Polynomial functors and negative sets}{67}
    {{3.1}Negative sets}{67}
    {{3.2}The geometric series revisited}{74}
    {{3.3}Moduli of punctured Riemann spheres}{77}
  {{4}Algebras}{81}
    {{4.1}Initial algebras, least fixpoints}{81}
      {Functoriality of least fixpoints}{84}
    {{4.2}Natural numbers, free monoids}{84}
    {{4.3}Tree structures as least fixpoints}{89}
    {{4.4}Induction, well-founded trees}{93}
    {{4.5}Transfinite induction}{95}
    {{4.6}Free-forgetful}{99}
  {{5}Polynomial monads and operads}{105}
    {{5.1}Polynomial monads}{105}
      {Cartesian monads}{105}
      {The free monad on a polynomial endofunctor (one variable)}{110}
      {Examples}{112}
    {{5.2}Classical definition of operads}{114}
    {{5.3}The monoidal category of collections}{115}
    {{5.4}Finitary polynomial functors and collections}{118}
      {Equivalence of monoidal categories}{120}
    {{5.5}The free operad on a collection}{121}
    {{5.6}$P$-operads}{122}
  {{6}[Polynomial functors in computer science]}{125}
    {{6.1}Data types}{125}
      {Shapely types}{133}
    {{6.2}Program semantics}{135}
  {{7}[Species\relax $\mathsurround \z@ \ldotp \ldotp \ldotp $\ ]}{139}
    {{7.1}Introduction to species and analytical functors}{139}
    {{7.2}Polynomial functors and species}{140}
{PART II Polynomial functors in many variables}{141}
  {{8}Polynomials in many variables}{143}
    {{8.1}Introductory discussion}{143}
    {{8.2}The pullback functor and its adjoints}{146}
      {Coherence}{155}
    {{8.3}Beck-Chevalley and distributivity}{156}
    {{8.4}Further Beck-Chevalley gymnastics}{165}
      {The twelve ways of a square}{165}
      {The six ways of a pair of squares}{167}
      {One more lemma}{168}
    {{8.5}Composition}{170}
      {Rewrite systems and coherence}{175}
    {{8.6}Basic properties}{178}
    {{8.7}Examples}{180}
      {The free-category functor on graphs with fixed object set}{182}
  {{9}Examples}{185}
    {{9.1}Linear functors (matrices)}{185}
    {{9.2}Finite polynomials: the Lawvere theory of comm.\ semirings}{191}
      {Lawvere theories}{192}
      {Proof of Tambara's theorem}{197}
    {{9.3}Differential calculus of polynomial functors}{200}
      {Introduction}{200}
      {Partial derivatives}{200}
      {Homogeneous functors and Euler's Lemma}{201}
    {{9.4}Classical combinatorics}{205}
    {{9.5}Polynomial functors on collections and operads}{208}
      {The free-operad functor}{209}
      {Linear differential operators are linear}{210}
    {{9.6}Bell polynomials}{214}
  {{10}Categories and bicategories of polynomial functors}{219}
    {{10.1}Natural transformations between polynomial functors}{219}
      {Basic properties of $\text {\textbf {\textsl {PolyFun}}}(I,J)$: sums and products}{228}
      {Misc}{228}
      {$\text {\textbf {\textsl {Poly}}}^{\text {c}}(I,J)$: the cartesian fragment}{229}
      {Sums and products in $\text {\textbf {\textsl {Poly}}}^{\text {c}}(I,J)$}{229}
    {{10.2}Horizontal composition and the bicategory of polynomial functors}{230}
      {Some preliminary exercises in the cartesian fragment}{231}
      {Horizontal composition of $2$-cells}{234}
  {{11}Double categories of polynomial functors}{241}
    {{11.1}Summary}{241}
      {Reminder on double categories}{243}
      {The double category of polynomial functors}{244}
      {Lifts}{250}
      {old calculations}{251}
    {{11.2}Horizontal composition}{257}
    {{11.3}Cartesian}{260}
      {Horizontal composition of cartesian $2$-cells}{261}
      {Misc issues in the cartesian fragment}{263}
      {Surjection-injection factorisation in $\text {\textbf {\textsl {Poly}}}$}{263}
      {Sums and products in the variable-type categories}{264}
      {Coherence problems}{265}
  {{12}Trees (1)}{267}
    {{12.1}Trees}{270}
    {{12.2}From trees to polynomial endofunctors}{271}
      {Examples of trees}{275}
    {{12.3}The category $\text {\textbf {\textsl {TEmb}}}$}{278}
    {{12.4}$\mathsf {P}$-trees}{286}
  {{13}Polynomial monads}{291}
    {{13.1}The free polynomial monad on a polynomial endofunctor}{291}
    {{13.2}Monads in the double category setting}{295}
      {relative}{299}
    {{13.3}Coloured operads and generalised operads}{299}
    {{13.4}$P$-spans, $P$-multicategories, and $P$-operads}{299}
      {Coloured operads}{313}
      {Polynomial monads and coloured operads}{314}
  {{14}Trees (2)}{317}
    {{14.1}$\mathsf {P}$-trees and free monads}{319}
      {Examples of polynomial monads from trees}{321}
    {{14.2}The category $\text {\textbf {\textsl {Tree}}}$}{323}
    {{14.3}Trees of trees, constellations, and the Baez-Dolan construction}{331}
{PART III Categorical polynomial functors}{337}
    {{14.4}Introduction}{339}
  {{15}[Polynomial functors for slices of $\text {\textbf {\textsl {Cat}}}$]}{341}
      {$\text {\textbf {\textsl {Cat}}}$ is not locally cartesian closed}{341}
    {{15.1}Conduch\'e fibrations}{343}
    {{15.2}Polynomial functors in $\text {\textbf {\textsl {Cat}}}$}{351}
    {{15.3}The family functor}{353}
    {{15.4}Final functors and discrete fibrations}{356}
  {{16}[Polynomial functors for presheaf categories]}{357}
    {{16.1}Some prelims}{357}
      {Kan extensions}{357}
      {Categories of elements}{358}
      {Nerves}{363}
      {Generic morphisms}{365}
      {Monads with arities}{369}
    {{16.2}Distributors and mixed fibrations}{375}
    {{16.3}The free-category monad}{380}
      {The free-multicategory monad}{387}
      {The free-coloured-operad monad}{388}
    {{16.4}Local right adjoints}{389}
  {{17}[Generalised species and polynomial functors]}{393}
  {{18}Appendices}{395}
    {{A}Pullbacks}{395}
  {Index}{407}{chapter*.55}

Last updated: 2009-08-06 by Joachim Kock.