## Signed sets and ballots, part 1

The other day, Anders Claesson wrote a very nice blog post explaining a more combinatorial way to understand multiplicative inverses of virtual species (as opposed to the rather algebraic way I explained it in my previous post). In the middle of his post he makes an offhanded assumption which I stubbornly refused to take at face value; after thinking about it for a while and discussing it with Anders, I’m very glad I did, because there’s definitely more going on here than meets the eye and it’s given me a lot of interesting things to think about.

Recall that $E$ denotes the species of sets, defined by $E[U] = \{U\}$, that is, the only $E$-structure on a given label set $U$ is the set of labels itself. Recall also that the exponential generating function of a species $F$ is given by

$\displaystyle F(x) = \sum_{n \geq 0} f_n \frac{x^n}{n!}$

where $f_n$ counts the number of labelled $F$-structures of size $n$. In the case of $E$, we have $f_n = 1$ for all $n$, so

$\displaystyle E(x) = \sum_{n \geq 0} \frac{x^n}{n!} = e^x.$

(This is why $E$ is such a good name for the species of sets—though in a fantastic coincidence, it seems to originally come from the French word for set, ensemble, rather than from the fact that $E(x) = e^x$ (though on the other hand calling it a “coincidence” is probably too strong, since Joyal must surely have picked the notation with the generating function already in mind!).)

Now, from my previous post we know that

$\displaystyle E^{-1} = (1 + E_+)^{-1} = \sum_{k \geq 0} (-1)^k (E_+)^k.$

Let’s first consider $\sum_k (E_+)^k$ (without the $(-1)^k$). This means that we have, for some $k \geq 0$, a $k$-ary product of $E_+$ structures—in other words, a list of nonempty sets. This is the species of ballots, also known as ordered set partitions, and can also be written $L \circ E_+$. As an example, here is a ballot on the set of labels $\{1, \dots, 8\}$:

The order of the parts matters, so this is a different ballot:

But the order of labels within each part doesn’t matter (since each part is a set). As another example, here is the complete collection of ballot structures on the labels $\{1,2,3\}$:

We can see that there are 13 in total: six where the labels are each in their own separate part (corresponding to the six possible permutations of the labels); six where two labels share a part and the other label is a singleton part (corresponding to the three ways to choose the solitary label, times the two ways to order the parts); and one final ballot where all three labels are grouped in the same part. (As an exercise, can you verify that there are 75 different ballot structures on a set of four labels?)

Returning to $E^{-1} = \sum_k (-1)^k (E_+)^k$, we can see that it consists of signed ballots, where the sign of a ballot is the parity of its number of parts, that is, a ballot with $k$ parts has sign $(-1)^k$. The second half of Anders’ post gives a nice combinatorial proof that $E \cdot E^{-1} = 1$, via a sign-reversing involution: if we consider $E \cdot E^{-1}$-structures, i.e. pairs of sets and signed ballots, there is a natural1 way to pair them up, matching positive and negative structures so everything cancels (except in the case of the empty label set, which is why we get $1$ instead of $0$).

However, Anders is trying to do more than that. Note first that since multiplication of EGFs corresponds to multiplication of species, the EGF for $E^{-1}$ is of course $1/e^x = e^{-x}$. But this ought to also be the EGF for the virtual species $E(-X)$, and the rest of his post hinges on identifying $E(-X)$ and $E^{-1}$. As Anders and I discovered, however, this is precisely the point where it is worth being more careful.

First of all, what is $E(-X)$? Intuitively, an $E(-X)$ structure consists of a set of negative atoms; since each set can be thought of as an (unordered) product of atoms, the whole set acquires a sign given by the parity of the number of atoms. In other words, intuitively it seems that $E(-X)$ should be the species of signed sets, where an even-sized set is considered positive and an odd-sized set negative. That is,

$\displaystyle E(-X) = \sum_{n \geq 0} (-1)^n E_n,$

where $E_n$ denotes the species of sets of size exactly $n$. As a sanity check, this makes sense as an EGF equation too, since the EGF of $E_n$ is just $x^n/n!$ and indeed

$\displaystyle e^{-x} = \sum_{n \geq 0} \frac{(-x)^n}{n!} = \sum_{n \geq 0} (-1)^n \frac{x^n}{n!}.$

But hold on a minute, what does $E(-X)$ really mean, formally? It is the composition of the species $E$ with the virtual species $-X$, and it turns out that it is not at all a priori obvious how to define composition for virtual species! We can find the definition on p. 127 of Bergeron et al. A special case (which is enough for our present purposes) is

$\displaystyle \Phi(X - Y) = \Phi(X + Y) \times (E(X)E^{-1}(Y))$

where $X$ and $Y$ are two sorts of atoms, and $\times$ denotes Cartesian product of species. In our case,

$\displaystyle E(0 - X) = E(0 + X) \times ((E(0) E^{-1}(X)) = E(X) \times E^{-1}(X) = E^{-1}(X)$

since $E$ is the identity for Cartesian product (overlaying an additional $E$ structure on a set of labels does not add any structure, since there is only one possible $E$-structure).

All of this is to say, $E(-X)$ is actually defined as $E^{-1}$! So at first glance it may seem we actually have nothing to prove: $E(-X)$ and $E^{-1}$ are the same by definition, end of story. …but in fact, all we have done is shift the burden of proof elsewhere: now it is our intuitive idea of $E(-X)$ representing signed sets that requires proof!

To sum up, we know that $E(-X) = E^{-1} = \sum_k (-1)^k (E_+)^k$ is the species of signed ballots, with sign given by parity of the number of parts; and intuitively, we also believe that $E(-X)$ should correspond to parity-signed sets, $\sum_n (-1)^n E_n$. So, is there a nice combinatorial proof showing the correspondence between signed sets and signed ballots?

One can use the law of excluded middle to show that the answer must be “yes”: suppose the answer were “no”; but then I would not be writing this blog post, which is a contradiction since I am writing this blog post. But is there a constructive proof? Fear not! This blog post has gotten long enough, so I will stop here for now and let interested readers puzzle over it; in my next post I will explain what I came up with, along with some musings on linear orders and naturality.

1. I am indeed using the word natural in a technical, categorical sense here! This will play an important role in my second post…