when is an integer sequence the trace of a monad on FinSet?

Question

Given $(a_n \in \mathbb{N})$, when is there a monad $T$ on $\mathrm{FinSet}$ such that $$ | T(n) | = a_n\quad\forall n\in \mathbb{N}\:? $$

Answer 1

It is useful to think about (finitary) monads on sets as algebraic theories. An algebraic theory consists of a set of function symbols together with their arities and a set of axioms of the form $t = s$, where $t$ and $s$ are terms constructed from variables and function symbols. For every such theory, we can define a monad $T(X)$ as the set of terms of this theory with variables in $X$ up to equivalence generated by the axioms. If for every finite set $X$ the set $T(X)$ is also finite, then this gives us a monad on finite sets and every monad can be presented in this form.

Now, there are two exceptional theories:

• The theory with no function symbols and the only axiom $x = y$. This theory generates sequence $0,1,1,1,1,\ldots$.
• The theory with a single constant $c$ and the only axiom $x = y$. This theory generates sequence $1,1,1,1,1,\ldots$.

Every other theory must generate an increasing sequence. Indeed, every term with $n$ variables $x_1, \ldots x_n$ is also a term with $n+1$ variables $x_1, \ldots x_{n+1}$ in which $x_{n+1}$ is not used. Moreover, we have the term $x_{n+1}$, so if there are $a_n$ terms with $n$ variables, then there is at least $a_n+1$ terms with $n+1$ variables.

Of course, there are more restrictions. For example, $a_2 \geq 2a_1-a_0$. Indeed, for every term $t(x)$, we have terms $x,y \mapsto t(x)$ and $x,y \mapsto t(y)$ which can be equal only when $t(x)$ is constant. Similarly, there are lower bound on every $a_n$. I think that it should be true that

$$ a_n \geq \binom{n}{n-1}a_{n-1} - \binom{n}{n-2}a_{n-2} + \ldots + (-1)^{n+1} \binom{n}{0} a_0 $$

for every $n > 1$ (and for $n = 1$, the lower bound is $a_0+1$), but I did not check this carefully.

Finally, I think these lower bound are the only restriction for sequences with $a_0 > 0$. If we have a theory with a constant $c$, we can always add exactly $k$ terms with $n$ variables to it (for every $n$ and $k$) without modifying $a_i$ for $i < n$. We just add $k$ function symbols $f_1, \ldots f_k$ of arity $n$ and axioms of the form $f_i(x_1, \ldots x_n) = f_i(x_{\sigma 1}, \ldots x_{\sigma n})$ for every $i$ and every permutation $\sigma$ and $t = c$ for every term $t$ such that its top function symbol is $f_i$ for some $i$ and either $t$ has at least two function symbols or at least one variable occurs twice in $t$.

Answer 2

I can give a more categorical description of the construction in Valery Isaev's answer.

Given a functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and a subset $E$ of $F(0)$, we can construct a natural functor from $(\operatorname{Finite Sets}, \operatorname{Injections})$ to $\operatorname{FinSet}$. The construction sends a functor $F$ to the functor $F'$ given by

$$F'(S) = \bigcup_{A \subseteq S} F(A)$$

unless $S$ is empty, in which case it is $F(0) \setminus E$.

I claim every functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, when restricted to isomorphisms, arises this way.

To prove this let $G$ be a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and define $F(S)$ to be the subset of $G(S)$ consisting of elements that do not lie in the image of $G(A)$ for any proper subset $A$ of $S$. Then there is a natural map from $F'(S)$ to $G(S)$ where we send, for each subset $A$ in $S$, $F(A) \subseteq G(A)$ to $G(S)$ under the functoriality map $G(A) \to G(S)$

This map is surjective because each element either lies in the image of some proper subset or doesn't, and we can induct in the first case.

To see the map is injective, suppose that $x \in G(S)$ lies in the image of $y \in F(A) \subseteq G(A) $ and $z \in F(B)\subseteq G(B)$ for two subsets $A, B$ of $S$.

If $A=B$ then we can apply a left inverse of the inclusion $A \to S$ to see that $y=z$ in $G(A)$ and so $(A,y)= (B,z)$ in $F'(S)$.

If $B$ contains a nonempty proper subset which contains $A \cap B$, let $m$ be a left inverse of the inclusion $B \to S$ which sends $A \setminus B$ into this proper subset. Let $i_A$ and $i_B$ be the inclusions of $A $ and $B$ into $S$. Then by functoriality $$ G_{i_A} (y) = x = G_{i_b}(z)$$ and so $$z = G_m ( G_{i_b}(z)) = G_m( G_{i_A}(x)) = G_{m \circ i_A} (x) $$ but $m \circ i_A$ factors through the inclusion of $A \cap B$ into $B$, so $z$ lies in the image of $G(A \cap B)$ which contradicts the assumption that $z \in F(B)$.

This second case only fails if $B \subseteq A$ or $B$ has one element. By symmetry, we are also good unless $A \subseteq B$ or $A$ has one element. Because we also handled the cases $A = B$, the remaining cases are when $B$ and $A$ both have one element and are equal. In this case we have an isomorphism between $A$ and $B$ and left inverses show that this isomorphism sends $y$ to $z$, but injectivity can fail. To fix injectivitiy, we move these elements from $F(1)$ into $F(0)$ and place them in $E$ (the set of evil elements).

---

This gives the formula

$$| G(n)| = \sum_{k=0}^n { n \choose k} |F(k) | $$

(or $|F(0)|-|E|$ if $n=0$) so if a sequence $a_n$ arises from any functor from finite sets to finite sets (and not just a monad) we must have

$$ a_n = \sum_{k=0}^n { n \choose k} b_k $$

for some sequence of natural numbers $b_k$, with $a_0=b_0-e$. This gives the inequalities described by Valery Isaev.

Conversely, for any functor $F$ from $(\operatorname{Finite Sets}, \operatorname{Isomorphisms})$ to $\operatorname{FinSet}$ and evil subset $E$, if $F(0)\setminus E \neq 0$ and $F(1)\neq 0$ we can extend $F'$ to a functor from $\operatorname{FinSet}$ to $\operatorname{FinSet}$, and in fact to a monad.

To do this, fix $c \in F(0)\setminus E$ and thus in $F'(S)$ for all $s$, and fix $i \in F(1)$ and thus an injective natural transformation $i: S \to F'(S)$ for all $S$.

To extend $F'$ to a functor, given a map $f: S_1 \to S_2$, a subset $A\subseteq S_1$, and an element $x \in F(A)$, send $(A,x)$ to $(f(A), f(x))$ if $f$ is injective on restriction to $A$ and to $(\emptyset, c)$ otherwise. Functoriality of this is easily checked.

To extend $F'$ to a monad, our unit will be the map $i$ and our multiplication will send an element in $F'(F'(S))$ associated to a subset $A$ of $F'(S)$ and an element $x$ in $F(A)$ to, if $A$ is contained in the image of $i$, the element $(i^{-1}(A), i^{-1}(x)) \in F'(S)$, if $A$ has one element $y$ and $x=i$, the element $y \in F'(S)$, and $c$ in every other case.

The compatibility with the left and right unit come from the first two cases. The associativity is not too hard to check.

This shows a stronger functorial version of the claim that for any sequence $b_k$, as long as $b_0$ and $b_1$ are nonzero, we can find a monad with sequence $a_n$.

Also Valery showed that if $b_1$ is zero, we must have $b_0=0$ or $1$ and all higher $b_i=0$. So the main case of interest is when $b_0=0$ and $b_1$ is not zero. In this case there may be more restrictions on the $b_i$s.