26 February 2008

Combinatorial quotients

Consider a combinatorial class (in the sense of Flajolet and Sedgewick) or combinatorial species (in the sense of Bergeron, Labelle, and Leroux). There are certain generating functions associated with combinatorial classes/species (I'm conflating the two for the moment because the difference between the two theories aren't important here), and the operations of sum and product have nice "combinatorial" interpretations -- addition of generating functions corresponds to disjoint unions of classes/species and multiplication of generating functions what I'll call here "combinatorial product", i. e. for two species F and G, an FG-structure on the set [n] is a pair which consists of an F-structure on some subset S of [n] and a G-structure on [n]-S. Then the generating function of the FG-structures is the product of the generating function of the F-structures and that of the G-structures.

Other natural operations on functions have combinatorial interpretations: composition of functions, taking exponentials or logarithms, differentiation, integration, etc. Even subtraction has an interpretation, although one has to be careful: this is the "virtual species". (A virtual species is a pair of ordinary species (F, G), written as F-G, where (F, G) = (H, K) if F + K = G + H. Replacing species with integers and addition with multiplication, this looks like the construction of the rational numbers from the integers.)

But is there a natural quotient operation? If there is, I can't find a mention of it in Flajolet and Sedgewick, and Marko Petkovsek (who I was just talking about this with) tells me it's not in Bergeron et al. either; this is one of the sources he's using for our current topics course in combinatorics. Let F be a species with 1 structure on the set of size 0, and let Fn be its restriction to size n. Let F+ be its restriction to all positive sizes. Then
F^{-1} = (1 + F_+)^{-1}

where 1 is the multiplicative identity species (hence the name); it has one structure on a set of size 0. We can of course write this as
1 - F_+ + F_+^2 - F_+^3 + F_+^4 - \cdots

and we collect the "positive" and "negative" terms to get
F^{-1} = \sum_{k=0}^\infty F_+^{2k} - \sum_{k=0}^\infty F_+^{2k+1}

So the inverse of the species F exists, and it's a virtual species in which the positive part is even-length tuples of nonempty F-structures, and the negative part is odd-length tuples of nonempty F-structures. This doesn't quite seem like a "combinatorially natural" operation -- but on the other hand I was able to describe it in a single sentence, so it seems plausible that it could be a natural thing to occur somewhere.

Notice that this also proves that if
F(z) = \sum_{n=0}^\infty f_n {z^n \over n!}, G(z) = \sum_{n=0}^\infty g_n {z^n \over n!}

and F(z)G(z) = 1, f0 = 1, then all the gn are integers, since the generating function G(z) actually counts something! (Well, a virtual something -- but that's close enough. It won't surprise you to learn that for two species H and K, the generating function corresponding to the virtual species H-K is H(z) - K(z). G here is a virtual species, so the gn are (possibly negative) integers. Of course, there are other ways to prove this, but I think this is a cute "combinatorial proof".

4 comments:

unapologetic said...

As you're surely learning in those lecture notes of Baez', generating functions naturally live in $\mathbb{N}[X]$ -- the rig of power series with natural number coefficients. It's possible to adjoin negatives (moving to $\mathbb{Z}$) and get a ring, but it's really hard to turn this ring into a field in a natural way. That, to me, explains the difficulty of interpreting division.

Isabel Lugo said...

You mean "as you surely will learn in those lecture notes of Baez' when you have time to read them". (I keep looking for references to various things online and keep coming across them, though, so they're moving higher and higher on the list.)

But that did occur to me on the walk home tonight. The obvious way to try to turn the ring into a field is to just start dividing power series formally, but unless all your power series have constant term 1 then one starts getting rational coefficients which aren't integers. But the power series with constant term 1 aren't closed under addition.

There's a notion of "weighted species" that comes up here in the theory of combinatorial species -- basically instead of counting each species once we count it with a weight drawn from some ring. (The weights don't have to be numbers -- often the weight of some structure s is t^{f(s)} where t is just another formal variable and f is some statistic on structures.) One could probably form a field of weighted species with weights in the rationals -- but that just seems too artificial to me. (And it may not actually be possible; defining subtraction on species is surprisingly nontrivial.)

unapologetic said...

Natural numbers have obvious interpretations as cardinalities. Negative numbers have a less-obvious interpretation that you mentioned in the post. But if you're going to divide like that, then what the hell does a rational cardinality mean?

Not saying the question doesn't have an answer, but that's the hard conceptual nut here.

Matt Noonan said...

The usual way to get rational-like objects is to look at G-sets: a set X which carries an action of the finite group G can be productively thought of as having cardinality |X| / |G| even if the action of G is not nice. For example, it is pretty reasonable to think of [-1,1] mod negation as an interval with a "half point" on the right end. The Euler characteristic of the quotient is (1/2 + 1) - 1 = 1/2, reflecting the fact that it is covered 2-1 by a space of Euler characteristic 1.