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

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

(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

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 natural¹ 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,

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

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

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

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.