Categorification request - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:36:11Z http://mathoverflow.net/feeds/question/55721 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55721/categorification-request Categorification request Jan Weidner 2011-02-17T10:58:30Z 2011-02-18T14:41:48Z <blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="http://mathoverflow.net/questions/1465/can-we-categorify-the-equation-1-t1-t-t2-1" rel="nofollow">Can we categorify the equation (1 - t)(1 + t + t^2 + &hellip;) = 1?</a> </p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/55721/categorification-request/55723#55723 Answer by Qiaochu Yuan for Categorification request Qiaochu Yuan 2011-02-17T11:34:07Z 2011-02-17T12:06:50Z <p>There are related examples at <a href="http://mathoverflow.net/questions/43579/examples-of-categorification" rel="nofollow">this MO question</a>, but most power series identities can be categorified to natural isomorphisms between <a href="http://en.wikipedia.org/wiki/Combinatorial_species" rel="nofollow">combinatorial species</a>, 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$. </p> <p>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.</p> <p>Alternately one can define $L$ to be the species of linear orders and then show that $L \cong 1 + xL$. </p> <p>The finite case is similar. Of course one can go much further with these ideas; see, for example, <a href="http://books.google.com/books?id=83odtWY4eogC&amp;printsec=frontcover&amp;dq=bergeron+labelle+leroux" rel="nofollow">Bergeron, Labelle, and Leroux</a>. I am sure Todd Trimble will also have something interesting to say.</p> http://mathoverflow.net/questions/55721/categorification-request/55724#55724 Answer by Martin Brandenburg for Categorification request Martin Brandenburg 2011-02-17T11:35:11Z 2011-02-17T11:35:11Z <p>I don't know if this counts as a categorification, but</p> <p>$\frac{q^n - 1}{q - 1} = 1 + q + ... + q^n$</p> <p>is the decomposition of the $n$-dimensional projective space over $\mathbb{F}_q$ into affine spaces. See <a href="http://math.ucr.edu/home/baez/week184.html" rel="nofollow">John Baez' week184</a>. In the limit, you get the decomposition of the infinite dimensional projective space.</p> http://mathoverflow.net/questions/55721/categorification-request/55861#55861 Answer by Todd Trimble for Categorification request Todd Trimble 2011-02-18T14:34:03Z 2011-02-18T14:41:48Z <p>I tried to discuss this geometric series example of categorification in one of my answers to another MO question by Jan Weidner, <a href="http://mathoverflow.net/questions/43579/examples-of-categorification/43602#43602" rel="nofollow">here</a>. 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). </p> <p>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. </p> <ul> <li>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. </li> </ul> <p>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. </p> <p>But perhaps this interpretation is not considered fully satisfactory if one is after a <i>direct</i> 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, </p> <p>$$"BG = 1//G"$$ </p> <p>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 </p> <p>$$card(G) = \sum_{x \in \pi_0(G)} 1/|G_x|$$ </p> <p>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. </p> <p>In general, as far as I understand things, categorified division doesn't involve dividing by a <i>set</i>, but by a suitable (usually free) <i>group</i> 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 </p> <p>$$1/G = Set^G$$ </p> <p>where the '1' here is the one-point "space" given by the topos $Set$; here one can take advantage of an equivalence </p> <p>$$EG = Set^G/G \simeq Set$$ </p> <p>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: </p> <p>$$Set^G/G \to Set^G$$ </p> <p>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. </p> <p>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 </p> <p>$$0 \to IG \to \mathbb{Z}G \stackrel{\pi}{\to} \mathbb{Z} \to 0$$ </p> <p>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 <a href="http://math.ucr.edu/home/baez/trimble/trimble_lie_operad.pdf" rel="nofollow">here</a>). 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 </p> <p>$$EG_n = \mathbb{Z}G \otimes (\Sigma IG)^{\otimes n}$$</p> <p>(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 </p> <p>$$BG = \sum_{n \geq 0} (\Sigma IG)^{\otimes n}$$ </p> <p>and this ultimately is how I am interpreting the categorification of the equation </p> <p>$$\frac1{1-x} = \sum_{n \geq 0} x^n$$ </p> <p>This was quite a long reply! I'm having trouble previewing; let's see how this looks... </p>