Categorification request

2011-02-17T10:58:30Z

Possible Duplicate:
Can we categorify the equation (1 - t)(1 + t + t^2 + …) = 1?

Can you give a categorification of the geometric series identity: $$1/(1-x)=1+x+x^2+...$$ Categorifications of partial sum identities $$(1-x^{n+1})/(1-x)=1+x+x^2+...+x^n$$ would also be nice.

Answer by Qiaochu Yuan for Categorification request

2011-02-17T11:34:07Z

There are related examples at this MO question, but most power series identities can be categorified to natural isomorphisms between combinatorial species, which are functors $\text{FinSet}_0 \to \text{FinSet}_0$ from the category of finite sets and bijections to itself. The idea is that the decategorification of a species $F$ is the power series $\sum F(n) \frac{x^n}{n!}$ where $F(n)$ is the cardinality of $F(S)$, where $|S| = n$.

Then $x$ is the decategorification of the species $X$ which corresponds to the structure of "being a one-element set." $L = \frac{1}{1-x}$ is the decategorification of the unique species satisfying $L \cong 1 + xL$, or "an $L$-structure is either empty or an $x$-structure together with an $L$-structure." (Addition and multiplication of generating functions correspond to natural operations on species which are left as an exercise to define.) Then the identity we want is $L \cong 1 + x + x^2 + ...$ which follows just by repeatedly substituting the isomorphism $L \cong 1 + xL$ into itself.

Alternately one can define $L$ to be the species of linear orders and then show that $L \cong 1 + xL$.

The finite case is similar. Of course one can go much further with these ideas; see, for example, Bergeron, Labelle, and Leroux. I am sure Todd Trimble will also have something interesting to say.

Answer by Martin Brandenburg for Categorification request

2011-02-17T11:35:11Z

I don't know if this counts as a categorification, but

$\frac{q^n - 1}{q - 1} = 1 + q + ... + q^n$

is the decomposition of the $n$-dimensional projective space over $\mathbb{F}_q$ into affine spaces. See John Baez' week184. In the limit, you get the decomposition of the infinite dimensional projective space.

Answer by Todd Trimble for Categorification request

2011-02-18T14:34:03Z

I tried to discuss this geometric series example of categorification in one of my answers to another MO question by Jan Weidner, here. I can't tell whether this reply was considered unsatisfactory, but what one considers satisfactory would have to depend on what one is looking for (especially as "categorification" is a vague term -- intentionally so).

Qiaochu has already given one interpretation, rewriting the linear fractional transformation $L = \frac{1}{1-x}$ in the form $L = 1 + xL$ and categorifying that. There are general ways of "categorifying" fixed points of functions, replacing endofunctions by endofunctors and equations by isomorphisms, but one is generally interested in a canonical solution. To illustrate this in the present case, one may categorify the endofunction $f: s \mapsto 1 + xs$ (on $\mathbb{R}$, say) to an endofunctor $F: S \mapsto 1 + X \times S$ on the category of sets. Now, there will generally be many "fixpoint solutions" of endofunctors (meaning a set $L$ together with an isomorphism $F(L) \cong L$), but many people (for example, those who like to talk about datatypes from a categorical perspective) tend to favor a canonical fixpoint solution that arises by applying the following result of Joachim Lambek.

If $F: C \to C$ is an endofunctor, define an $F$-algebra to be an object $c$ of $C$ together with a morphism $F(c) \to c$. Morphisms are defined in the obvious way (involving a commutative square). Theorem (Lambek): if $(c, \alpha: F(c) \to c)$ is initial in the category of $F$-algebras, then $\alpha$ is an isomorphism.

For $F(S) = 1 + X \times S$ on $Set$, the initial $F$-algebra turns out to be the free monoid on $X$ as already indicated by Qiaochu. Another canonical fixpoint is obtained by dualizing Lambek's theorem, referring instead to terminal coalgebras of endofunctors. The first type of solution is typically recursive and algebraic; the second solution co-recursive and coalgebraic.

But perhaps this interpretation is not considered fully satisfactory if one is after a direct categorification of division or reciprocation which does not fall back on rewriting an equation multiplicatively. For example, when a topologist writes, in categorification mode as it were,

$$"BG = 1//G"$$

for the classifying space (take '1' here to be $EG$ which is homotopy equivalent to a point, and divide out by the action of $G$ on $EG$), he clearly doesn't mean $G \times BG \cong EG$. People like Baez and Dolan have thought about what it means to categorify reciprocals; in the decategorification direction, they define the cardinality of a groupoid $G$, when $G$ is equivalent to a disjoint sum of finite groups $G_x$, where $x$ ranges over the set of connected components, to be

$$card(G) = \sum_{x \in \pi_0(G)} 1/|G_x|$$

so that for example, the cardinality of the groupoid of finite permutations is e. In particular, the cardinality of a finite group is the reciprocal of its order.

In general, as far as I understand things, categorified division doesn't involve dividing by a set, but by a suitable (usually free) group action. Hints of this can be seen in my first answer to the other categorification request linked to above, where the categorified term $X^n/\mathbf{n!}$ means dividing by the usual action of the symmetric group $\mathbf{n!}$ on a tensor power $X^n$. A thorough discussion of this point would lead to considerations in $(\infty, 1)$-category theory, but to give a taste, one may think of a "space" $BG = 1/G$ (taking $G$ for now to be discrete) as given by the topos

$$1/G = Set^G$$

where the '1' here is the one-point "space" given by the topos $Set$; here one can take advantage of an equivalence

$$EG = Set^G/G \simeq Set$$

where the middle term is a slice topos (note: the notation for a slice should not be interpreted as division!), and define a "bundle projection" between toposes:

$$Set^G/G \to Set^G$$

which is the geometric morphism right adjoint to pulling back along $G \to 1$ in $Set^G$; concretely, it takes a morphism $p: X \to G$ in $Set^G/G$ to the internal object of sections.

To return now to the question, where one is attempting to categorify $\frac1{1-x}$, one needs somehow to construe $1-x$ as a group $G$ with a suitable action on a contractible object playing the role of 1. The question is: what is $x$ here (what does it categorify to)? My best attempt at an answer (which I tried to give, maybe not very successfully, in one of my answers to the other MO question) is to write $x = 1 - G = -(G - 1)$, interpreting here $G$ actually as a group object $\mathbb{Z}G$ (more precisely, a cocommutative Hopf algebra, which is a group object in the cartesian category of cocommutative coalgebras), then interpreting $G - 1$ as the so-called augmentation ideal $IG$ fitting in the exact sequence

$$0 \to IG \to \mathbb{Z}G \stackrel{\pi}{\to} \mathbb{Z} \to 0$$

where $\pi$ is an augmentation map which sits at the right end of a bar construction for $EG$ (in an abelian sense, meaning a free resolution for computing cohomology of $G$), and finally interpreting the additive inverse $-(G-1)$, or rather additive inversion generally, as the odd degree shift functor on the category of $\mathbb{Z}_2$-graded abelian groups (I'll call it $\Sigma$, for suspension; it takes a a graded object $(V_0, V_1)$ to $(V_1, V_0)$; I tried to explain why this is sensible here). The point I had alluding to is that there are various models for the contractible simplicial object $EG$, but the relevant one for purposes of this categorification problem seems to be where

$$EG_n = \mathbb{Z}G \otimes (\Sigma IG)^{\otimes n}$$

(more precisely, the free resolution $EG$ is taken to be a normalized bar resolution; see the reference to Hilton-Stammbach in my earlier answer); here $EG_n$ lives in degree $n \pmod 2$. Dividing the total graded space $EG$ by the action of $\mathbb{Z}G$, one is left with the model

$$BG = \sum_{n \geq 0} (\Sigma IG)^{\otimes n}$$

and this ultimately is how I am interpreting the categorification of the equation

$$\frac1{1-x} = \sum_{n \geq 0} x^n$$

This was quite a long reply! I'm having trouble previewing; let's see how this looks...

Categorification request - MathOverflow

Categorification request

Answer by Qiaochu Yuan for Categorification request

Answer by Martin Brandenburg for Categorification request

Answer by Todd Trimble for Categorification request