Polynomial Functors

Over at the cafe, the mathematician Joachim Kock has been talking about polynomial functors. Think of these as polynomials in sets, although we could draw the diagrams in any suitable category. For example, a one variable polynomial $\Sigma_{a \in A} x^{B(a)}$ is given by a function $f: B \rightarrow A$, as in the diagram where $*$ is a terminal one point set and $!$ the unique map to this set. Allowing several variables (indexed by $I$) and families of polynomials (indexed by $J$) the diagram becomes where we use $s$ and $t$ to stand for source and target, since triangles like the one above are supposed to make us think of comma categories. In a topos like Set, some polynomials with $f$ monic (one to one) arise from the characteristic squares where we have chosen $J$ to be the two point set and $I$ the one point set. Observe that for finite sets, the one to one condition says that the allowed powers in the polynomial (i) only occur once and (ii) are restricted by the cardinality of $A$. Property (i) essentially says that only coefficients of $1$ or $0$ are allowed, which means we are looking at something like the two element field. Property (ii) relates to the number of copies of two, that is a $2^{n}$ element field, as in two qubits or four qubits and so on. The object $\Omega$ gives us a pair of such polynomials, which are complementary to each other in the sense that one characterises $B$ and the other the complement of $B$.

Thus polynomial functors are one hint that sets with a prime number of elements play a special role in categorified arithmetic, just as the prime ordinals are special, although in the usual category Set one does not worry about primes.