MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
First part was also asked (and answered) here… – Simon Wadsley Feb 17 '11 at 13:14
Good eye, Simon. Closed. – S. Carnahan Feb 17 '11 at 15:18
I think I have to object to the closing of this question, maybe mainly because I was writing a long answer which attempts to say that there may be more to it than is suggested by how the equation was rewritten in the possible duplicate. Grrr... – Todd Trimble Feb 17 '11 at 15:22
Jan Weidner says that this is not intended to be an exact duplicate, but as written I don't see how… is not more precise and answers the question asked here. So for now, I think this should be closed as duplicate. I would love to encourage more discussion of categorification, and so hope this question stays open; if it is going to, I ask that the question be precise-ified into something distinct from op. cit. – Theo Johnson-Freyd Feb 17 '11 at 17:50
I believe pretty firmly that this is a duplicate of the cited question. I would vote to close on these grounds, if I weren't a moderator. Please direct discussion to… – Ben Webster Feb 17 '11 at 20:53

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...

share|cite|improve this answer

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.

share|cite|improve this answer
This type of decomposition should work also "motivically", whatever that is supposed to mean. So the equation also makes sense in the Grothendieck ring of varieties, in the Grothendieck ring of Hodge structures, in the Grothendieck ring of $\ell$-adic Galois representations, etc, when q is the class of the affine line. Note also that $q^{n+1} -1$ is the class of $\mathbf{A}^{n+1}\setminus \{0\}$ and that $q-1$ is the class of $\mathbf{G}_m$, so the equation really expresses that $\mathbf{P}^n$ is the set of lines through a point in an affine space one dimension higher. – Dan Petersen Feb 17 '11 at 11:42
Yes. Can't we just conclude that the purpose of Grothendieck constructions is this kind of formal "calculation"? – Martin Brandenburg Feb 17 '11 at 11:46

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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