# Are all vector-space valued functors on sets free?

Let $\mathbf{Set}$ be the category of finite sets and functions between them, and let $\mathbf{Vect}$ be the category of finite-dimensional complex vector spaces and linear transformations between them. There is a free functor $G \colon \mathbf{Set} \to \mathbf{Vect}$, left adjoint to the forgetful functor, given by $G(X) = \mathbb{C}^X$ and $G(f)(\phi)(y) = \sum_{f(x)=y} \phi(x)$.

Is any functor $\mathbf{Set} \to \mathbf{Vect}$ of the form $H \circ G \circ F$ for $F \colon \mathbf{Set} \to \mathbf{Set}$ and $H \colon \mathbf{Vect} \to \mathbf{Vect}$?

A priori one might expect lots more functors, but I'm having a hard time coming up with any. On the other hand, functoriality seems to keep $G$ from "creating chaos" to "mess up freeness" (sorry that I can't explicate this feeling better). To keep it simple, let's keep things finite(-dimensional), and not consider anything about other base fields, or monoidal structure.

-
If it helps, we may restrict to skeletons of $\mathbf{Set}$ and $\mathbf{Vect}$, i.e. to sets $\{1,\ldots,n\}$, and vector spaces $\mathbb{C}^n$ and matrices between them. – Chris Heunen Jul 14 '14 at 10:58
Does the thing have to do much with complex numbers? As was noticed, Vect is equivalent to the category of finite sets and complex matrices. But even if you replace this by the category of finite sets and matrices with values in {0, 1}, i.e. the category Rel, will there be a counterexample? What would be the Rel analogue of the counterexample in the answer below? – Dimitri Chikhladze Jul 14 '14 at 20:36
@DimitriChikhladze If we replace Set with Rel (but keep the target some category of vector spaces) the recent preprint arxiv.org/abs/1510.03034 provides a complete answer. The irreducible representations V of Rel correspond to finite lattices, and V is projective exactly when its lattice is distributive! – John Wiltshire-Gordon Nov 11 at 16:49
@JohnWiltshire-Gordon Interesting. I'll check it out. – Dimitri Chikhladze Nov 12 at 1:12

This is probably an absurdly over-complicated answer, but ...

Let $$J(X)=\left\{\sum_{x\in X}a_xx\in GX: \sum_{x\in X}a_x=0\right\}.$$

I claim that $J$ is not of the form $H\circ G\circ F$.

Suppose it were.

Let $n=\{0,\dots,n-1\}$.

The functors $F,G,H$ induce group homomorphisms $$S(n)\to S(F(n))\to \operatorname{GL}(GF(n))\to\operatorname{GL}(HGF(n))$$ (where $S(n)$ is the symmetric group) and $J(n)$ is a representation (of dimension $n-1$) of all of these groups. It's irreducible as an $S(n)$-module, and so must be irreducible for all the other groups. (Actually, I'm really only going to need the case $n=3$.)

Since, for $0<n<m$, $n$ is a retract of $m$, and $J(n)\not\cong J(m)$, it follows that $F(n)\not\cong F(m)$ and $|F(1)|<|F(2)|<\dots$. So $\dim GF(n)\geq n-1 (=\dim HGF(n))$. But all homomorphisms $\operatorname{GL}(k,\mathbb{C})\to\operatorname{GL}(l,\mathbb{C})$ have abelian image for $k>l$ and so $\dim GF(n)=|F(n)|=n-1$ for $n>2$, or else $J(n)$ would be a direct sum of one-dimensional representations.

But $S(n-1)$ doesn't usually have any $(n-1)$-dimensional irreducible representations.

-
Very nice, thanks! Would imposing any linear relation on $G$ do the trick? – Chris Heunen Jul 14 '14 at 20:05
@ChrisHeunen The linear relation would have to be essentially the one in the answer, in order for $J$ to be a functor. You need $J(f)$ to make sense, in particular for $f$ a permutation. – Andreas Blass Jul 14 '14 at 20:26

The easiest example is the functor that sends the empty set to a 1-dimensional vector space, and all other finite sets to zero. (Any H that sends some vector space to 0 must send 0 to 0 as well).

The second-easiest example is the one given by Jeremy Rickard.

If you're interested in functors from the category of finite sets to finite dimensional vector spaces, you might take a look at my paper http://arxiv.org/abs/1406.0786 The main result is a structure theorem about (finitely-generated) functors in this category.

-

There are some functors obtained by the "doubly contravariant trick" --- composites of the form $\mathbf{Set}\to\mathbf{Set}^{\mathrm{op}}\to\mathbf{Vect}$ or $\mathbf{Set}\to\mathbf{Vect}^{\mathrm{op}}\to\mathbf{Vect}$. I doubt all these can be represented as $H\circ G\circ F$...

-
$\mathbf{Vect}$ is equivalent to $\mathbf{Vect}^\mathrm{op}$, so that shouldn't matter. What is the functor $\mathbf{Set} \to \mathbf{Set}^\mathrm{op}$ you're using? – Chris Heunen Jul 14 '14 at 15:16
@ChrisHeunen just to clarify -- the equivalence of Vect with its opposite category is something special to the finite-dimensional case, right? – Yemon Choi Jul 14 '14 at 15:33
@YemonChoi: that's correct. In arbitrary dimension there is also a "free" functor $G \colon \mathbf{Set}^\mathrm{op} \to \mathbf{Vect}$, and we could ask the same question based on $G$ for contravariant functors, I suppose. Are the two questions related? – Chris Heunen Jul 14 '14 at 15:46
@ChrisHeunen You are probably right about the equivalence... for $\mathbf{Set}\to\mathbf{Set}^{\mathrm{op}}$ - well any contravariant hom would do, that is, $\hom(\_,S)$ for any finite set $S$... – მამუკა ჯიბლაძე Jul 14 '14 at 15:48