16
$\begingroup$

From Zeilberger's PCM article on enumerative combinatorics:

The reaction of the combinatorial enumeration community to the involution principle was mixed. On the one hand it had the universal appeal of a general principle... On the other hand, its universality is also a major drawback, since involution-principle proofs usually do not give any insight into the specific structures involved, and one feels a bit cheated. [... O]ne still hopes for a really natural, "involution-principle-free proof."

The quest for bijective proofs really is, at heart, the quest to categorify an equation proved via "decategorified" arithmetic, to provide an explicit family of isomorphisms in the category of finite sets (or the category of finite sets and bijections, I don't think it matters). So categorifying multiplication and addition is easy -- they just correspond to product and coproduct of sets, respectively. Categorifying subtraction is trickier, but that's what the involution principle does for us. (On a tangential note, I know that categorifying division is [in]famously hard in the category of sets -- is it anything like as hard when we talk about finite sets? ETA: Looking at Conway's paper, the answer seems to be "yes and no." No, because with finite sets it's kosher to use a bijection between a set of size n and {0, 1, ..., n-1}; yes, because this is sort of like a "finitary Axiom of Choice," and in particular it's not canonical.)

So is there any real meaning, in a categorical sense, to the enumerative-combinatorial dream of "really nice proofs?" Or will there necessarily be identities that can only be proved bijectively by categorifying, in a general and universal way, their "manipulatorics" proofs?

Edit: So philosophically this is a category-theory question, and it'd be nice to have it as a "real" category-theory question. Here's my (very rough) attempt at phrasing it as such.

Let T be a topos where we can categorify addition, multiplication, and subtraction of natural numbers. Then, are there functors between T and FinSet that preserve these decategorifications? If so, then I think maybe we can ask the question in terms of topos theory, although maybe not -- I don't really know much topos theory, so I'm certainly having trouble.

Improve this question
$\endgroup$
3
  • $\begingroup$ I like the tone of this question. The notion of "bijective proof" is perhaps the most basic instance of categorification. It's a shame that some people have the impression that categorification is something intrinsically to do with knot theory or representation theory. Of course there are beautiful examples of categorification in those subjects, but as this question makes clear, it comes up naturally in much more elementary contexts. $\endgroup$
    – Tom Leinster
    Jan 19, 2012 at 19:47
  • $\begingroup$ What does the acrony ETA stand for, apart from Estimated Time of Arrival? $\endgroup$
    – Vincent
    Nov 10, 2017 at 10:51
  • $\begingroup$ @Vincent, probably “edited to add”. $\endgroup$
    – LSpice
    Dec 22, 2019 at 5:04

2 Answers 2

Reset to default
5
$\begingroup$

Baez and Dolan argue that in some cases division is easier than subtraction. In particular, most division problems come from group actions, and Baez and Dolan define a "weak quotient" of a G-set with cardinality precisely the ratio that you want it to be.

Here's what he does. Recall that a groupoid is a category with all morphisms invertible. Two examples: a groupoid with only identity morphisms is naturally a set; a groupoid with only one object is naturally a group; these are two extremes (trivial on the morphism level; trivial on the object level).

I will consider only finite groupoids. Then for each object x, consider the number 1/|Aut(x)|, where Aut(x) = Hom(x,x). This is a class function: if x and y are isomorphic, then |Aut(x)|=|Aut(y)|. Baez and Dolan define the cardinality of a groupoid to be the sum over equivalence classes of 1/|Aut(-)|. The cardinality is preserved under equivalences of groupoids.

Anyway, let X be a set and G a group acting on it. One defines the "action groupoid" to have objects X and morphisms pairs (x,_g_) ∈ X x G, where the source of the morphism is x and the target is gx. Turns out that the cardinality of the action groupoid is |X|/|G|.

(I think that the right way to think about the action groupoid is as some sort of extension, like a semidirect product, of the groupoids X and G, and what's really going on is that you should think of G as a groupoid with 1/|G| many objects.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ I don't think this is quite what I meant -- by "decategorifying division," I meant: given an isomorphism between S x X and S x Y, exhibit an isomorphism between X and Y. $\endgroup$
    – Harrison Brown
    Oct 28, 2009 at 9:50
  • $\begingroup$ And of course by "decategorifying division" I meant "categorifying division"... $\endgroup$
    – Harrison Brown
    Oct 28, 2009 at 9:59
  • $\begingroup$ Oh, yes, that's much harder. Sorry, I misunderstood. (Besides, I wasn't really answering your question at all.) My only knowledge about categorifying division is the paper by Doyle and Conway, which you've probably already read. The final paragraph in that paper is particularly fantastic. But anyway, when I think of "categorification", I normally think of it as the challenge of finding interesting categories that decategorify the way you want. Schanuel's paper on Euler characteristic of semialgebraic sets comes to mind. $\endgroup$
    – Theo Johnson-Freyd
    Oct 28, 2009 at 17:24
4
$\begingroup$

Igor Pak wrote a paper in which he defines the notion of an "asymptotically stable" partition bijection, then shows there is no such bijection proving the Rogers-Ramanujan identities.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting -- I've only looked at the introduction so far (and fear that I probably won't be able to get too much farther), but from what I can tell, it looks like he's saying that a "generic" bijection has a certain property, and that no bijection with this property can prove Rogers-Ramanujan. (Is this close?) I don't really see why this property should characterize "niceness," though... $\endgroup$
    – Harrison Brown
    Oct 28, 2009 at 13:28
  • $\begingroup$ I don't think generic is the right word. My understanding is that he defines "nice" to mean "doesn't mess up the shape of a large random partition too much" (or at least transforms it in a reasonably nice way). $\endgroup$
    – Qiaochu Yuan
    Oct 28, 2009 at 14:14
  • $\begingroup$ Qiaochu, your second understanding is correct. For example, if I recall correctly the standard bijection between partitions into distinct odd parts and partitions into self-conjugate parts is asymptotically stable. These don't have "the same shape" (for one thing, the limiting shape is self-conjugate in one case but not in the other!) but the limiting shapes are related in a "nice" way. $\endgroup$
    – Michael Lugo
    Oct 28, 2009 at 14:44
  • $\begingroup$ "partitions into self-conjugate parts" should, of course, be "self-conjugate partitions" in the previous comment. $\endgroup$
    – Michael Lugo
    Oct 28, 2009 at 14:46
  • 1
    $\begingroup$ Ah, I see where my understanding was wrong -- I somehow got confused between "random partitions" and "random bijections." Okay, yeah, a generic bijection now seems like it should fail horribly, but a "low-complexity" bijection should tend to be asymptotically stable, if I'm thinking about this correctly. $\endgroup$
    – Harrison Brown
    Oct 28, 2009 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.