Virtual species suffice

Over six years ago, I wrote a post explaining how virtual species are defined. Ever since then (time flies!) I’ve been meaning to write a follow-up post explaining a bit more about virtual species and how they actually suffice to give us not just additive inverses, but also (somewhat surprisingly) multiplicative inverses.

Recall that the intuitive idea of a combinatorial species is a family of labelled structures which are invariant under relabelling. If you’ve never seen the formal definition before, don’t worry: just think “data structures” or “algebraic data types” for now.

The basic idea of virtual species is to work with pairs of species (P,N) where P is considered “positive” and N “negative”. Formally, we consider equivalence classes of such pairs under the equivalence relation defined by (P_1, N_1) \cong (P_2, N_2) iff P_1 + N_2 = P_2 + N_1.1 This parallels the way one typically gives a formal definition of the integers starting from the natural numbers (the “Grothendieck construction”); see my previous post for more details.

Intuition

How can we build intuition for virtual species, and for additive inverses of species in particular? To be honest I have been struggling with this question for many years.

Multiplicative inverses are much simpler to think about: they are like matter and antimatter. Having both an F-structure and an F^{-1} structure is the same as having nothing; they annihilate each other. By “having nothing” we mean “having no information”, that is, having a unit value: F F^{-1} = 1.

What about additive inverses? Note first that the 0 species does not correspond to having nothing; the word “nothing” corresponds to the 1 (i.e. unit) species. Instead the 0 (i.e. uninhabited) species corresponds to (logical) impossibility. So to interpret -F we have to imagine something where having either F or -F is impossible.

…yeah, me neither. This seems deeply strange. If someone says, “I either have an F or a -F”, you can confidently call them a liar, because it is impossible to have either an F or a -F; that is, F - F = 0. But surely if you actually have an F-structure, it should also be true to say “I have either an F or a G”? Well, that works for normal, positive species—in which case we can define a canonical injection F \to F + G. But once we introduce negative species this completely breaks down. As another example, if someone truthfully says, “I have either a tree or a negative non-empty tree”, you should be able to say, “Aha! I know what you have—it must be an empty tree.” In general, it’s strange that expressing a disjunction can cause some possibilities to be ruled out. Normally, we are used to disjunctions only increasing the number of possibilities.

Inspired by James and Sabry’s really cool paper The Two Dualities of Computation: Negative and Fractional Types, I have thought a bit about whether there is some plausible interpretation involving travelling backwards in time, but I haven’t been able to come up with one. I can’t quite seem to make the formalism of the paper match up with my intuition about species (though this may just be a failure of my imagination or intuition).

Multiplicative Inverses

In any case, let’s see why the ring of virtual species actually has multiplicative inverses—at least, all the ones we could possibly hope for. This is somewhat surprising, since when we build integers from natural numbers by considering equivalence classes of pairs, we certainly don’t get any multiplicative inverses, only additive ones. To get multiplicative inverses we have to do the same process a second time, building the rational numbers as equivalence classes of pairs of integers. But species already have enough extra structure that throwing in additive inverses is all it takes.

First, a caveat: we don’t get multiplicative inverses for all species, but only those species G such that G(0) = 1: that is, species G with only a single structure of size zero, which are of the form G = 1 + X(\dots). With any constant term other than 1, we clearly have no hope of finding another species H such that GH = 1, since the constant term of GH will be a multiple of G’s constant term.

So given such a G, write G = 1 + G_+, where G_+ denotes “non-empty G-structures”. Then we can define the multiplicative inverse of G as follows:

\displaystyle G^{-1} = \sum_{k \geq 0} (-1)^k (G_+)^k = 1 - G_+ + G_+^2 - G_+^3 + \dots

That is, a G^{-1}-structure consists of a list of nonempty G-structures, except that even-length lists are considered “positive” and odd-length lists considered “negative”.

We can easily check that this indeed defines a multiplicative inverse for G:

\displaystyle \begin{array}{rcl}G G^{-1} &=& (1 + G_+) (1 - G_+ + G_+^2 - G_+^3 + \dots) \\[0.5em] &=& (1 - G_+ + G_+^2 - G_+^3 + \dots) + (G_+ - G_+^2 + G_+^3 - G_+^4 + \dots) \\[0.5em] &=& 1 \end{array}

The infinite sums telescope down to leave only 1. Notice this really isn’t about species in particular, but really about infinite power series (of which species are the categorification): any infinite power series with integer coefficients and a constant term of 1 has a multiplicative inverse which is also such a power series.

As an example, consider 1/(1-X) = (1-X)^{-1}. We know this is “supposed” to be the species of lists (since it results from solving L = 1 + XL for L), but let’s see what happens. In this case G = 1-X and G_+ = -X. So the inverse ought to be

\displaystyle (1-X)^{-1} = \sum_{k \geq 0} (-1)^k (-X)^k = \sum_{k \geq 0} X^k = 1 + X + X^2 + X^3 + \dots

And hey, look at that! Lists!

A field of species?

So what would we need to get a true field, i.e. a multiplicative inverse for every nonzero species? Well, for that we would need to throw in rational coefficients. I forget exactly where I read this—some paper by Baez and Dolan, most likely—but I believe the proper way to interpret this would be as groupoid-valued species, since there is a sense in which the “cardinality” of groupoids can be interpreted as rational numbers. But to be honest I have no idea where this leads.


  1. Note that species sum is cancellative—that is, if A + C = B + C then A = B—so this is a coherent definition. This cancellative property is probably worth another post of its own since the reason for it is not entirely trivial.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in combinatorics and tagged , . Bookmark the permalink.

23 Responses to Virtual species suffice

  1. christopher andrew upshaw says:

    Okay, I am sure you have thought of this, but cardinality and un-normalized discreet probability are pretty dang closely related. Which ishould in turn closely related to general probability, and quantum logic* is often considered to be the generalization of probability. So maybe, maybe..embedding virtual species in a complex space makes sense?

    So maybe equivalence classes of (P, N) * e ^ipiR? Not sure if R is just a real and e^ipi_ is basicly just formal, or if e^ipiR is some sort of function space?
    Now this line of inqirery might be pointless, because quantum amplitudes don’t have a intuitive semantics, so all that work might just give us another formal model with no intuition.

    On another topic, I to don’t really understand the semantics of additive cup and cap in The Two Dualities of Computation: Negative and Fractional Types.

    Linear types also have a “negative” of sorts, with a pretty straitfroward interpretation as moving the type from environment to production.

    (Parts of which are even preserved in non linear types. For example the isomorphism between (a+b)->c and (a->c,b->c) )

    But I little idea what “linear” species would be. As you now have two additions and two multiplications, and each only distributes over the one they are not dual with. Maybe by using “classical” liner types you can use the demorgan rules to normalize things?

    Sorry for the long rambling comment.

  2. Derek Elkins says:

    Perhaps considering species valued in (monoidal) categories with a magnitude as surveyed in Leinster’s “The magnitude of a metric space: from category theory to geometric measure theory” https://arxiv.org/abs/1606.00095 would produce something interesting in that vein.

  3. sn0wleopard says:

    Awesome! Applying the Grothendieck group construction to the algebra of graphs has been on my todo list for quite some time, but I had no idea one may also be able to get multiplicative inverses for free. In my case, the cancellation law does not hold, so there will be some complications though. And then there is this weird fact that 0=1, so let’s see what happens :-)

    • Brent says:

      Sounds like fun! My understanding is that if cancellation does not hold then you want to define (a,b) = (c,d) iff there is some x such that a+d+x = b+c+x.

      • sn0wleopard says:

        The problem with the standard \exists x. p1+n2+x = p2+n1+x definition is that if x is a complete graph of the whole universe, then a + x = x, and everything collapses into the same equivalence class. In other words, existence of an absorbing element seems to lead to a trivial group in Grothendiek construction. Sets are quite similar to graphs in this sense; perhaps, I should start by looking for ways to turn a set into a non-trivial group, although I now doubt if it’s possible at all.

        • Brent says:

          Aha, I see, that is a problem indeed.

        • Chris Upshaw says:

          Well if you have a weighting on edges that is a group then you don’t really need the grothendieck construction, and can still get some nice ideas of negation.

          For example:
          Using F T under xor gets you sum where a graph is its own inverse. Weighting by Z gives you Multigraphs that can have negative number of edges. Wightin by R+ (and using multiplication) you get something really weird.

          But I think your addition is closer to an meet/union then a disjoint union so maybe look at lattices? Or at the min,+ rig?

          You have probably considered all this.

          • sn0wleopard says:

            Thanks Chris!

            I do have a few examples where nodes and edges have labels that form a semiring, and so far these semirings were idempotent, to match the a + a = a law in the algebra (a natural definition for labelled graph overlay is [x]a + [y]a = [x y]a).

            Your suggestion to consider labels forming a group is interesting. Indeed, this will give negation, even though we’ll then lose the idempotence of graph overlay. I’ll look into it!

          • sn0wleopard says:

            That should have been [x]a + [y]a = [x ++ y]a, where ++ is the addition from the semiring.

    • Arun Debray says:

      What does it mean that 0 = 1 in the algebra of graphs? Any semiring satisfying 0 = 1 is trivial, are graphs a different algebraic structure?

  4. Regarding difference of species, I would recommend thinking of them in term of difference of multisets (think of what the Grothendieck construction does to multiset).

    Examples where a difference of two species is a species but not one with a (recursive) polynomial definition can be nice. I think this works: Lists – Bags ≃ Non-increasing lists.

    (Disclaimer: my knowledge of species is very limited)

    • Brent says:

      I think I see what you mean about multisets — it does make for nice intuition to explain why there exist “purely virtual” species which are neither positive nor negative (in the same way that a “purely virtual multiset” might contain a positive number of one element and a negative number of another). Though I don’t really see how it helps come up with an intuitive idea of how to constructively interpret virtual species.

      I like your example of Lists – Bags. But I am not exactly sure what you mean by “non-increasing”. Do you mean lists where the labels are not sorted in increasing order (i.e. identifying a bag of size n with a canonically sorted list of size n)? That does make for a nice example, although to be pedantic we can really only interpret Lists – Bags as non-sorted lists in the context of L-species (where the labels are equipped with a linear order).

      • Sorry: I’m a high-latency person.

        The intuition I have, with multisets, is fibres of species are like multisets. Ostensibly they’re sets, but since the sum is tagged, they are more like multisets: L+L has two of each lists at each size. And sum is fibre-wise. It’s kind of where sum and product differ: products modify what « shapes » are available at each fibre, for sums, the « shape » of object is opaque, so we might as well take blurry glasses and see them as atoms. So, from this point of view, sums are pretty much just fibre-wise multiset sums (and subtraction, fibre-wise « virtual » multiset subtraction).

        Regarding List-Bags: that’s indeed what I meant. And I realise that I was abusing the notation a bit (we could say that it’s all the lists except one per size, then every choice of the one missing list yields a syntactically different, but equivalent, species, but that’s rather boring…).

  5. Aaron says:

    Hey, man do you mind if I register your rss feed on gwene. I would love to be able to read your blog
    with gnus.

  6. Pingback: Signed sets and ballots, part 1 | blog :: Brent -> [String]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s