Euler Characteristic of a Category

October 11, 2006

Posted by David Corfield

After Baez and Dolan taught us about groupoid cardinality (p. 15), now Tom Leinster teaches us about the Euler characteristic of a category.

I wonder if anything further has been done about the former’s wonderfully wild idea that the Euler characteristic of the sphere, i.e., 2, should be the same as what they call its homotopy cardinality on the page mentioned above, defined as an alternating product of the orders of the homotopy groups of the sphere.

Posted at October 11, 2006 8:38 AM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/979

87 Comments & 5 Trackbacks

Re: Euler Characteristic of a Category

David wrote:

I wonder if anything further has been done…

No, not that I know of. However, Dan Christensen has been telling me some wonderful things about homotopy cardinality versus Euler characteristic. I’m too tired to retell these things now, but anyone curious about the general idea should look here:

John Baez, The mysteries of counting: Euler characteristic versus homotopy cardinality.

Lots of links… and I’ll have to add one to Tom’s new paper!

Does anyone have the energy to summarize Tom’s new paper? This is the place to do it!

Tom?

Posted by: John Baez on October 12, 2006 6:06 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

John wrote:

Does anyone have the energy to summarize Tom’s new paper?

The energy, but not quite the time. This is a summarized summary:

The Euler characteristic of a category is the sum of the entries of the inverse of the matrix of the cardinalities of the hom-sets.

More another time!

Tom

Posted by: Tom Leinster on October 12, 2006 7:05 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

I’m not sure we should be asking Tom to summarise his own paper, unless there’s an enlightening way to see what’s going on which is not included in it. I remember during a discussion of my book on the Foundations of Mathematics list, which was sparked off by someone reporting John’s review, feeling a wee bit annoyed being asked to summarise what I’d written by a person who felt he didn’t have time to read it. It didn’t stop him discussing the book though.

Perhaps it would be better to tease further thoughts out of Tom. Such as what prospects are there to extend the construction to categories with infinitely many isomorphism classes of object? Is there an obvious example of such a category where we already know what cardinality we’d like it to have, something like FinSet for Baez-Dolan, perhaps using all the kinds of wonderful trick appearing from p. 17 onwards of this? Are there any prospects for an extension to bicategories?

Posted by: David Corfield on October 13, 2006 8:04 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

David wrote:

I’m not sure we should be asking Tom to summarise his own paper […]

I take the point, and it’s true that I’ve already written the best 2-page summary I could manage: it’s the introduction to my paper. On the other hand, I feel so warmly towards you people that I’d happily write a shorter and chattier summary.

In fact, I wrote a shorter chattier summary for this blog last night, but having come into the office in order to post it here, I discover that I left it at home :-(

David wrote:

what prospects are there to extend the construction to categories with infinitely many isomorphism classes of object?

(Background: I only defined Euler characteristic for (some) finite categories.)

The only thoughts I’ve had about infinite categories are the obvious ones, so I didn’t bother including them in the paper. More specifically, what I do involves various finite sums, and of course you can try to interpret them in an infinite situation, and sometimes you get convergence and sometimes you don’t.

An important point is that no matter how much you try to relax the finiteness conditions, you always need to keep the condition that each hom-set is finite. This is because the whole approach depends on knowing what the cardinality of a finite set is.

In fact, if you have any monoidal category V and a notion of “cardinality” or “Euler characteristic” of objects of V, then you can define the Euler characteristic of a finite V-enriched category by mimicking the original case (V = FinSet) in the simplest possible way.

In particular, there’s an answer to David’s question:

Are there any prospects for an extension to bicategories?

Yes: take V = FinCat. And you can go all the way up the n-categorical ladder: see p.15 of my paper.

David wrote:

Is there an obvious example of such a category where we already know what cardinality we’d like it to have, something like FinSet for Baez-Dolan […] ?

Yes. If G is a finite directed graph and F(G) denotes the free category on G, we’d expect F(G) to have the same Euler characteristic as G (namely, no. of vertices minus no. of edges). This is proved in my paper when F(G) is finite. But it may be that F(G) is infinite, even though G is finite.

For instance, we’d expect the free monoid on n generators, regarded as a one-object category, to have Euler characteristic 1 - n.

We’d also expect the free group on n generators to have Euler characteristic 1 - n, since it has a bouquet of n circles as a classifying space.

Posted by: Tom Leinster on October 14, 2006 2:41 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

you always need to keep the condition that each hom-set is finite

I suppose there might be some scope in enriched categories to flout this condition. E.g., if you had $R^{n}$ worth of morphisms between 2 objects, you could take its Euler characteristic $(-1)^{n}$ .

Posted by: David Corfield on October 15, 2006 11:54 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

David wrote:

if you had $\mathbf{R}^n$ worth of morphisms between 2 objects, you could take its Euler characteristic $(-1)^n$ .

Agreed. This is another example of the generalization to enriched categories that I mentioned in a previous comment. Here, we’d be enriching over some category of topological spaces.

Posted by: Tom Leinster on October 15, 2006 7:24 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

That would raise the problem of identical rows occurring in the matrix to be inverted, even in a skeletal category. E.g., if all Hom sets were finite dimensional complex vector spaces, all entries would be 1.

Posted by: David Corfield on October 18, 2006 2:40 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

True, but that’s only a “problem” in the sense that it prevents the category from having Mobius inversion. It doesn’t prevent it from having Euler characteristic, which is a weaker property.

Incidentally, if all your hom-sets are vector spaces (and composition is bilinear) then it might be more appropriate to interpret the “cardinality” of each hom-set as its dimension. (This is mentioned briefly on p.15.) For example, an n-dimensional k-algebra A, interpreted as a one-object category enriched in k-modules, would then have Euler characteristic 1/n. In particular, A might be the group algebra of a group G of order n; then A and G have the same Euler characteristic, which is nice.

Of course, it all depends on what you want to achieve.

Posted by: Tom Leinster on October 18, 2006 5:40 PM | Permalink | Reply to this

Summary.

Here is my summary:

There are previously known notions of Euler characteristic (or cardinality) for groupoids, posets, and digraphs, which are all fairly simple: * The Euler characteristic of a groupoid is the sum, over connected components, of the reciprocal of the order of the automorphism group. * The Euler characteristic of a poset is the number of chains in the poset, weighted (in the usual fashion) by the parity of the length of the chain. * The Euler characteristic of a digraph is the number of vertices minus the number of edges.

Tom has a definition of Euler characteristic of a category that simultaneously generalises these. (Groupoids and posets are categories in the obvious way; a digraph gives rise to a free category.) The definition is still a bit complicated (so I leave it to an appendix), and it’s still defined in too few cases. However, it has all the usual nice properties that one would expect for a generalisation of cardinality.

The paper also includes a few applications of the theory; for example, it’s related to Möbius inversion and the inclusion/exclusion principle.

Posted by: Toby Bartels on October 14, 2006 5:44 PM | Permalink | Reply to this

Appendix.

$MathML-enabled post (click for more details).$

Here is the definition:

Given objects a and b in the category, let $\zeta ^ a _ b$ be the number of morphisms from a to b. A weighting on the category is a function a ↦ k^a, assigning a rational number to each isomorphism class of objects, such that $\sum _ b \zeta ^ a _ b k ^ b = 1$ for each object a. Similarly, a coweighting is a function a ↦ k_a such that $\sum _ a k _ a \zeta ^ a _ b = 1$ for each b.

Weightings and coweightings need not exist, nor be unique. However, it is a theorem that if a weighting and a coweighting both exist, then $\sum _ a k _ a = \sum _ b k ^ b .$ This sum is the Euler characteristic of the category.

The proof of this theorem is immediate, by plugging in an appropriate expression for 1 and swapping the order of summation. However, because of this swap, it may not apply if there are infinitely many isomorphism classes of objects. Thus, Tom’s paper limits itself to finite categories.

(Tom: Please confirm!)

Posted by: Toby Bartels on October 14, 2006 6:11 PM | Permalink | Reply to this

Re: Appendix.

$MathML-enabled post (click for more details).$

Toby wrote:

(Tom: Please confirm!)

I do. Thanks!

I also agree with this (again from Toby):

The definition is still a bit complicated […] and it’s still defined in too few cases.

I’d like to remedy both these situations. Ideally, the slightly ad hoc definition that I gave could be replaced by some nice universal property, or at least something more conceptual.

I’ve tried to do this but not come up with anything great. All I can really offer is this: if you want the theorem (2.8) on the Euler characteristic of a fibred category to be true, you’re forced to define “weight” in the way that I do - for take $X$ to be representable.

To cure “defined in too few cases”, I think we need to move beyond the rational numbers. As I mentioned briefly at the end of the Introduction, I suspect that we should be looking for Euler characteristic valued in other rigs.

There seems to be a similar situation with Euler characteristic of topological spaces. Take the set $X = \{0, 1/2, 1/4, 1/8, \ldots \}$ . This satisfies $X \cong 1 + X$ , so you’d expect its Euler characteristic $x$ to satisfy $x = 1 + x$ . But this has no solutions in any non-trivial ring, so if you want $X$ to have an Euler characteristic you’d better move to some other rig.

Posted by: Tom Leinster on October 15, 2006 7:40 PM | Permalink | Reply to this

New rigs.

The nice thing about the rationals (or reals, for Baez–Dolan groupoid cardinality) is that they include all of the other rigs. But any rig containing the integers is a ring. (To be precise, any rig with a rig homomorphism from Z is a ring.) Since we can add and multiply any categories, we’d like to add and multiple their Euler characteristics, but then they need to belong to the same rig.

Posted by: Toby Bartels on October 17, 2006 11:04 PM | Permalink | Reply to this

Discrete Calculus

$MathML-enabled post (click for more details).$

I’m going to take the liberty to convert some of this stuff into the language of discrete calculus. For background, you can try (although maybe not advised) to read the paper Urs and I worked on together

Discrete Differential Geometry on Causal Graphs

Then, there is a much simpler paper I wrote separately where the goal was to write it so that even finance people (which includes more and more physicists these days) could understand

Financial Modeling Using Discrete Stochastic Calculus

In it, I give a brief review of discrete calculus on directed graphs and show how in different continuum limits, you can recover either exterior calculus or stochastic calculus.

The basic idea is that we have some directed graph $G$ , with nodes denoted by $e_a$ and an edge directed from $e_a$ to $e_b$ denoted by $e_{ab}$ . To keep things simple, I’ll assume the number of nodes is finite (or at least if they are infinite, then they are infinite in such a way that I do not need to worry about rearranging summations).

We can also introduce functionals, i.e. discrete differential forms, on nodes and directed edges with bases given by $e^a$ and $e^{ab}$ with contraction written as an integral, i.e.

(1)

\int_{e_a} e^b = \delta^b_a

and

(2)

\int_{e_{ab}} e^{cd} = \delta^c_a \delta^d_b.

The vector space generated by $e^a$ is the space of discrete 0-forms $\Omega^0$ so that an arbitrary discrete 0-form may be written as

(3)

f = \sum_a f_a e^a.

Similarly, the space of discrete 1-forms is generated by $e^{ab}$ so that an arbitrary discrete 1-form may be written as

(4)

\alpha = \sum_{a\to b} \alpha_{ab} e^{ab}.

I like to write contraction as an integral because we end up with intuitive looking things like

(5)

\int_{e_a} f = f_a,

which is simply 0-dimensional integration (or evaluation at a point) and

(6)

\int_{e_{ab}} \alpha = \alpha_{ab}

which is simply 1-dimensional integration (or evaluation along an edge).

We have some simple multiplication rules

(7)

e^a e^b = \delta^{ab} e^a

so that multiplication of 0-forms is what we would expect, e.g.

(8)

fg = \sum_a f_a g_a e^a.

The magic comes in when we define multiplication of a 0-form and a 1-form. This is done via the very intuitive rule

(9)

e^a e^{bc} = \delta^{ab} e^{bc}

and

(10)

e^{ab} e^c = \delta^{bc} e^{ab}.

Unless we start talking about 2-categories (which I hope we do), we will not need a multiplication rule for 1-forms, but it is as obvious as you would think.

I say this is intuitive because when we multiply a 0-form $f$ on the left of a directed (co)edge $e^{ab}$ we get

(11)

f e^{ab} = f(a) e^{ab},

i.e. multiplication picks out the value of the 0-form at the beginning of the edge. Similarly,

(12)

e^{ab} f = f(b) e^{ab},

i.e. multiplication on the right picks out the value of the 0-form at the end of the directed edge.

The important thing here is that clearly discrete 0-forms and discrete 1-forms do not commute. This has pretty mind numbing consequences and is how I managed to rope Urs into all this stuff :)

Next, let’s introduce what we called the “graph operator”

(13)

\zeta = \sum_{a\to b} e^{ab}.

What Tom calls a weighting can also be thought of a 0-form $\overset{\rightarrow}{k}$ multiplying the graph operator on the right such that

(14)

\int_{G_1} \zeta \overset{\rightarrow}{k} = 1,

where

(15)

G_1 = \sum_{a\to b} e_{ab}.

Similarly, a coweighting can be thought of as a 0-form $\overset{\leftarrow}{k}$ multiplying the graph operator on the left such that

(16)

\int_{G_1} \overset{\leftarrow}{k} \zeta = 1.

Apparently, the claim is that when both $\overset{\rightarrow}{k}$ and $\overset{\leftarrow}{k}$ exist, then we have

(17)

\int_{G_0} \overset{\rightarrow}{k} = \int_{G_0} \overset{\leftarrow}{k} = \chi(G),

where

(18)

G_0 = \sum_a e_a.

I’m not sure that this change of perspective is helpful (I think it is), but I thought I would write it out just in case.

Another thing that comes to mind (this is basically another stream of consciousness) is that for some directed graphs, the discrete exterior derivative (or coboundary) can be expressed in terms of a commutator with the graph operator, i.e.

(19)

df = [\zeta,f].

Therefore, on such a directed graph we would have

(20)

\zeta \overset{\rightarrow}{k} = \overset{\rightarrow}{k} \zeta + d\overset{\rightarrow}{k}

and if the graph has no boundary than

(21)

\int_{G_1} \zeta \overset{\rightarrow}{k} = \int_{G_1} \overset{\rightarrow}{k} \zeta = 1.

If these conditions are satisfied, we could actually have the weight equal to the coweight. Not sure if that is important, but thought I would point it out.

Now that I’ve converted to a language I better understand I’ll try to think about that formula John is after.

Posted by: Eric on October 21, 2006 6:38 AM | Permalink | Reply to this

Re: Discrete Calculus

$MathML-enabled post (click for more details).$

I warned you that I am almost always wrong :)

The conditions from Tom’s paper (as summarized by Toby) do not require the integrals over the entire graph. Rather, it should be

(1)

\int_{G_1 e_b} \zeta \overset{\rightarrow}{k} = \int_{e_a G_1} \overset{\leftarrow}{k} \zeta = 1,

for all $a$ and $b$ , where

(2)

G_1 e_b = \sum_a e_{ab}

is the sum of all edges incident onto $b$ and

(3)

e_a G_1 = \sum_b e_{ab}

is the sum of all edges emanating from $a$ . However, the other condition does require the integral over the whole graph

(4)

\int_{G_0} \overset{\rightarrow}{k} = \int_{G_0} \overset{\leftarrow}{k} = \chi(G).

That is, of course, unless I’ve made another careless mistake, which we can never rule out. Urs help! :)

Posted by: Eric on October 21, 2006 7:08 AM | Permalink | Reply to this

Re: Discrete Calculus

$MathML-enabled post (click for more details).$

unless I’ve made another careless mistake

No, looks good to me (including your last correction).

This is a good move. We need to find the dictionary which tells us what various graph quantities that we are dealing with correspond to in the continuum limit.

In particular:

- what is the continuum meaning of the 0-form

(1)

f : a \mapsto \sum_b (\xi_{ab}+\xi_{ba})

I have a suspicion, but only based on intuition so far and likely to be wrong: could it be related to the volume element $\sqrt{g}$ ?

Posted by: urs on October 21, 2006 2:29 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Once in one of John’s seminars at UCR, I parsed his (and Jim’s) definition of groupoid cardinality as

(1)

\sum _ a \frac 1 { \sum _ b \card \hom ( a , b ) } ,

where the sum is taken over isomorphism classes of objects (or equivalently over objects, if you believe in equality of objects). This applies directly to categories (not just groupoids), generalises easily to enriched categories or n-categories, and respects addition and multiplication.

But it differs from Tom’s definition already when applied to the poset {0 < 1}: I say it has cardinality 3/2, while he says it has Euler characteristic 1.

Now, I can think of at least two ways that Tom’s definition is superior to mine: * It generalises the notion of Euler characteristic of a poset; * It generalises the notion of Euler characteristic of a digraph.

To better understand what one wants in a notion of Euler characteristic or homotopy cardinality, I’d like people to tell me what else is wrong with my definition. (Since this is perhaps a bit too idiosyncratic —why should anybody bother?—, people might also just suggest things for me to test them on.)

Posted by: Toby Bartels on October 14, 2006 5:21 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

The Euler characteristic of a compact space happens to coincide with the index of the operator $d + d^\dagger$ , when the latter is defineable.

This makes me want to ask a very vague question: could it be possible that generalized notions of Euler characteristic lead to generalized notions of this operator?

Or a related question: given the Čech groupoid of a good covering of a topological space $X$ by open sets. Does the Euler characteristic of that groupoid coincide with the ordinary Euler characteristic of $X$ ?

Posted by: urs on October 18, 2006 7:12 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If someone could somehow relate an n-category to an “n-diamond” and then somehow construct an operator $d+d^\dagger$ on a n-diamond, would this analogy help? :)

Posted by: Eric on October 18, 2006 8:02 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If someone could somehow relate an n-category to an “ $n$ -diamond” and then somehow construct an operator $d + d^\dagger$ on a $n$ -diamond, would this analogy help?

For others reading this, I’ll translate what Eric is suggesting here:

Consider a finite oriented graph $G$ without any parallel edges (no two edges have same source and target). Let

(1)

V_p

be the $\mathbb{C}$ -vector space spanned by sequences of length $p$ of “composable” edges in $G$ . $V_0$ is the space spanned by the vertices.

Define

(2)

d : V_0 \to V_1

(3)

d v := \sum_{v_s \neq v} (v_s \to v) \;\;-\;\; \sum_{v_t \neq v} (v \to v_t) \,,

where $v$ is a vertex, the sums run over all vertices and $v \to w$ is the edge from $v$ to $w$ if it exists, or zero otherwise.

Now divide out the minimum of relations $R$ that ensure that $d$ is nilpotent and graded Leibniz

(4)

(\mathbf{V}^\bullet,d) = (V^\bullet,d)/R \,.

Next, choose a scalar product $\langle\cdot|\cdot \rangle$ on $\mathbf{V}^\bullet$ , which vanishes unless both entries are of same degree.

Let $d^\dagger$ be the adjoint of $d$ with respect to that scalar product.

Now, define the index of $d + d^\dagger$ as

(5)

\mathrm{lim}_{t\to \infty} \mathrm{str}_{V^\bullet} e^{-t(d+d^\dagger)^2} \,.

One might expect that this is related to some notion of Euler characteristic associated to $G$ , or of the category generated by it.

Is it?

Posted by: urs on October 18, 2006 8:26 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Hi,

I don’t have any answers, just some simple observations.

For the obvious choice of inner product, the adjoint $d^\dagger$ turns out to be the same (functionally at least) as the boundary map $\partial$ . Therefore, the operator you wrote down

(1)

(d+\partial)^2 = d \partial + \partial d

is the graph laplacian, which can be written in terms of the “degree matrix” and the “adjacency matrix” via

(2)

L = D - A.

I’m sure someone did this 100+ years ago, but I’m pretty sure that for a directed graph

(3)

tr(D) = \sum_{v} deg(v) = |E|

where $v$ are the vertices, $deg(v)$ is the degree of vertex $v$ and |E| is the total number of directed edges in the graph.

Also, obviously

(4)

tr(I) = |V|

where I is the identity matrix and |V| is the number of vertices.

Finally,

(5)

tr(A) = |F|

where $A$ is the adjacency matrix and $|F|$ is the number of “loops”.

Therefore,

(6)

tr(I - L) = tr(I - D + A) = |V| - |E| + |F|.

This is probably 90% bogus, but hopefully it gives you some ideas :)

It would not be at all surprising to me if this can be extending to higher n-diamonds, which might help relate it to your question (maybe).

Posted by: Eric on October 18, 2006 11:00 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Therefore,

(1) $\mathrm{tr}(I−L) = \mathrm{tr}(I−D+A)= |V| - |E| + |F|$

Hm, that looks pretty. I don’t think I was aware of this before.

I’ll need to think about how it relates to the expression

(2)

\mathrm{str}\exp(-t(d + d^\dagger)^2) = \mathrm{str}\exp(-t \Delta)

that I wrote down.

While $\exp(-\Delta) = I - \Delta + \cdots$ , the trace you write is over a different vector space (that of vertices, which I called $V_0$ ), while my $\mathrm{str}$ denoted the supertrace over all of $V^\bullet$ . Accordingly, $\Delta = (d + d^\dagger)^2$ reduces to the $\Delta$ that you mention on $V_0$ .

So now I am hoping that in your expression you were secretly missing something, which gets fixed once we extend the trace to all of $V^\bullet$ .

Could it be hidden in this statement:

Finally,

(3) $\mathrm{tr}(A)= |F|$

where $A$ is the adjacency matrix and $|F|$ is the number of “loops”.

You want to identify $|F|$ with the number of faces. But is it? Faces should be triangles of edges. These don’t appear in $\mathrm{tr}(A)$ , unless I misunderstood something. Do they?

Hence I am currently inclined to say that your formula

(4)

\mathrm{tr}_{V_0}(I - L)

actually misses most of the faces. But that these might appear once we extend the trace over all of $V^\bullet$ (including an alternating sign).

Could that be? Please correct me if I am spouting nonsense.

Finally, again for the non-experts following this, I would like to unwrap this remark of yours:

For the obvious choice of inner product, the adjoint $d^\dagger$ turns out to be the same (functionally at least) as the boundary map $\partial$ .

What Eric has in mind here is this:

the “obvious inner product” on $V^\bullet$ is that in which the generating basis elements of $V^\bullet$ (the vertices, edges, and $R$ -classes of composable sequence of length $p$ of edges) are orthonormal.

In that basis, we compute the action of $d^\dagger$ for instance on an edge $v_1 \to v_2$ as follows (for any $v \in V$ )

(5)

\begin{aligned} \langle v | d^\dagger(v_1 \to v_2) \rangle &= \langle d v | v_1 \to v_2 \rangle \\ &= \sum_{v_s \neq v} \langle v_s \to v | v_1 \to v_2 \rangle - \sum_{v_t \neq v} \langle v \to v_t | v_1 \to v_2 \rangle \\ &= \delta_{v,v_2} - \delta_{v,v_1} \,. \end{aligned}

This is equivalent to

(6)

d^\dagger(v_1 \to v_2) = v_2 - v_1 \,.

And this is indeed the action of $\partial$ on the 1-simplex $v_1 \to v_2$ .

Posted by: urs on October 19, 2006 11:17 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

David wrote:

I’m not sure we should be asking Tom to summarise his own paper…

No, but nonetheless he should do it if we ask him.

I remember during a discussion of my book on the Foundations of Mathematics list, which was sparked off by someone reporting John’s review, feeling a wee bit annoyed being asked to summarise what I’d written by a person who felt he didn’t have time to read it.

Well, it can be annoying when someone asks you to summarize something you wrote, but you should always do it when asked in a public forum.

Why? Because it gives lots of people a chance to learn what you’ve done - not just the lazy bum who asked the question. It also gives you a chance to look magnanimous. That’s why I was always willing to explain my work to people when they asked me to on sci.physics.research. That’s also the principle I was trying to exploit by getting Tom to explain his work now.

But, it turns out Toby was the one who broke down and typed in a definition of the Euler characteristic of a category, so everyone can see it without leaving this blog. Thanks, Toby! That’s a crucial step, because having the definition “sitting there for all to see” is the best way to get mathematicians to start poking at it and trying to prove stuff about it. If you make them leave the room and read a paper, they may get distracted and not come back.

(Our discussion is occuring in a kind of “room” here, albeit a virtual one, and for some reason opening a PDF file counts as leaving that room. I’m not sure why, but I know it’s true, and one has to just accept it.)

Anyway: now that Toby has shown us Tom’s definition, and Urs and Eric have raised an analogy with graph Laplacians, ideas start to bubble and brew…

For example, I just realized that Tom’s weightings and coweightings are functions from vertices of a directed graph to numbers. Our graph happens to be a category, but that’s not necessary for the definition to make sense.

And, the equations Toby wrote down are reminiscent of Poisson’s equation for a graph Laplacian.

Normally a graph Laplacian is defined for undirected graphs (I think). Say we have a function that maps vertices of our graph to numbers: $a \mapsto k_a$ Then applying the graph Laplacian gives a new function of this sort, namely: $a \mapsto k_a - \sum_b \zeta^a_b k_b$ where $\zeta^a_b$ is the number of edges joining the vertices $a$ and $b$ .

In other words, if we call the graph Laplacian $\Delta$ , we have

$(\Delta k)_a = k_a - \sum_b \zeta^a_b k_b$

You can stick some extra numbers in this definition if you want:

$(\Delta k)_a = \alpha k_a - \beta \sum_b \zeta^a_b k_b$

and you often do. For example, if your graph is an infinite square grid, you should take $\alpha = 1$ and $\beta = 1/4$ , so the Laplacian takes a function of vertices and creates a new function by subtracting 1/4 times the sum of the nearest neighbor’s values. This is good because then

$\Delta k = 0$

holds when $k$ is constant.

Practical people - electrical engineers who use “finite element methods” - know all about this stuff. That’s one reason Eric got interested in this business, I guess - he was doing electrical engineering or something like that, back before he decided to make vast sums of money in LA.

Anyway, Poisson’s equation is where you fix a function $f$ and look for functions $k$ such that

$\Delta k = f$

If we take $f = 1$ , this says

$\alpha k_a - \beta \sum_b \zeta^a_b k_b = 1$

If we take $\alpha = 0$ and $\beta = -1$ , we get Tom’s equation

$\sum_b \zeta^a_b k_b = 1$

But, Tom goes ahead and looks at two equations,

$\sum_b \zeta^a_b k^b = 1$

and

$\sum_b \zeta^a_b k_a = 1$

for two different functions $k_a$ and $k^b$ , the weighting and coweighting. And, if both these equations have solutions, Tom shows

$\sum_a k_a = \sum_b k^b$

and this number is the Euler characteristic of the category whose underlying graph I’ve been discussing.

So, some funny stuff is going on - but there is some relation to graph Laplacians. And we know that Laplacians show up when we compute the Euler characteristic of a manifold using the heat equation on that manifold.

So, it’s vaguely possible that Tom is secretly generalizing the usual way of computing the Euler characteristic of a manifold, by replacing the manifold with a directed graph, and modifying everything accordingly.

Okay - now someone figure out the details.

Posted by: John Baez on October 19, 2006 3:20 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Normally a graph Laplacian is defined for undirected graphs (I think).

I believe

(1)

\Delta = (d+d^\dagger)^2 = (d + \partial)^2

is defined for directed graphs, but that results like

In other words, if we call the graph Laplacian $\Delta$ , we have

(2) $(\Delta k)_a = \alpha k_a - \beta \sum_b \xi^a_b k_b$

follow as special cases when the directed graph is assumed to have an edge

(3)

v_2 \to v_1

for every

(4)

v_1 \to v_2 \,.

Let’s do the computation:

For $v$ any vertex, I write $v$ for what John calls

(5)

k_a := \delta_{a,v} \,,

i.e. the 0-form supported at $v$ .

Then for any directed graph we have

(6)

\begin{aligned} \Delta v &= (d + \partial)^2 v \\ &= \partial d v \\ &= \sum_{v_s \to v} \partial (v_s \to v) - \sum_{v \to v_t} \partial (v\to v_t) \\ &= \sum_{v_s \to v} (v - v_s) - \sum_{v \to v_t} (v_t - v) \,. \end{aligned}

In general, no further simplification is possible at this point. But under special conditions there is.

So now assume the graph is such that the adjacency matrix is symmetric, i.e. that for every edge $v_1 \to v_2$ the reverse edge $v_2 \to v_1$ exists.

Then the above becomes

(7)

\begin{aligned} \Delta v &= 2 \sum_{v_s \to v} (v - v_s) \end{aligned} \,.

If we moreover assume that $G$ is an infinite square grid, this becomes

(8)

\begin{aligned} \frac{1}{2}\Delta v &= 4 v - (\text{northern neigbour}) - (\text{southern neigbour}) - (\text{western neigbour}) - (\text{eastern neigbour}) \end{aligned} \,.

coinciding, up to a global factor, with the formula that John mentioned ( $\alpha = 1$ and $\beta = 1/4$ ).

Posted by: urs on October 19, 2006 12:11 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

The mathematical universe is so highly connected. (According to David Ruelle, this is because you can pack a lot into a high-dimensional space.) At the works retreat I just returned from, we were given a tutorial on the role of Graph Laplacians in spectral clustering. The idea is that you are given a set of data points, $x_i$ , and a similarity measure for each pair of points, $s_{ij}$ . You’re looking to arrange the data into clusters based on intra-cluster similarity and extra-cluster dissimilarity. To this end you form an undirected graph with vertices corresponding to each data point, and a symmetric weight $w_{ij}$ on edges equal to $s_{ij}$ if it’s positive, 0 otherwise. The degree of a vertex, $d_i$ , is the sum of weights of edges with one end at $v_i$ . The diagonal matrix of $d_i$ is denoted $D$ , while the $w_{ij}$ are the entries of the adjacency matrix $W$ .

There are 3 forms of graph Laplacian:

$L=D-W$ is the unnormalized Laplacian.
$L_{rw}=I-D^{-1}W$ is the random walk normalized Laplacian.
$L_{sym}=I-D^{-1/2}W D^{-1/2}$ is the symmetric normalized Laplacian.

In all 3 cases, the number of 0 eigenvalues is equal to the number of components of the graph. As you will see from the tutorial, other eigenvalues give more information. Hmm, might be worth seeing if there’s any connection to what John said about Tom’s construction.

Posted by: David Corfield on October 19, 2006 12:52 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

For example, I just realized that Tom’s weightings and coweightings are functions from vertices of a directed graph to numbers.

So let’s make it very explicit what this seems to be telling us:

We are talking about a space $X$ with a function $k$ on it.

(1)

k : X \to \mathbb{R}

The claim is (apparently) that if $k$ satisfies some differential equation involving a Laplace operator on $X$ (coming with a measure $d\mu$ on $X$ ), then the integral

(2)

\chi(X) \propto \int_X k \;d \mu

is the Euler characteristic of $X$ .

(Because that’s what the expression $\sum_a k_a$ corresponds to.)

What does this way of formulating the statement do with us?

Well, it makes me think about the generalized Gauss-Bonnet theorem.

Posted by: urs on October 19, 2006 3:27 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

The claim is (apparently) that if $k$ satisfies some differential equation involving a Laplace operator on $X$ (coming with a measure $d\mu$ on $X$ ), then the integral

(1) $\chi(X) \propto \int_X k \;d \mu$

is the Euler characteristic of $X$ .

Right. But what really freaked me out was that the differential equation was a special case of Poisson’s equation - that’s what Tom’s condition

(2)

\sum_a k_a \zeta^a_b = 1

seems to be. At least, some sort of inhomogeneous equation. I’ve never heard of a way to compute Euler characteristics by doing an integral of a solution of Poisson’s equation, or any other inhomogeneous differential equation.

But maybe I’m just being dense. Maybe it’s related to the usual heat equation stuff somehow. After all, solutions of Poisson’s equation describe the $t \to \infty$ limit of a solution of the heat equation with an source term - a heat source.

But how does the source - the inhomogeneous term - get into the act?

It would be annoying if this neat stuff Tom did were so closely related to Laplacians, heat equations and their usual relation to Euler characteristic without both of them being a special case of something.

Posted by: John Baez on October 20, 2006 8:29 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

But what really freaked me out was that the differential equation was a special case of Poisson’s equation

But is it? That interpretation only works when you modify the Laplace operator by throwing in some funny constants - in particular by deleting one of the terms it consists of #.

I am a little hesitant to call the operator

(1)

k \mapsto (a \mapsto \sum_b \xi^a_b k(b))

a “Laplace operator”. It does not seem to share any of the properties that one would usually expect of a Laplace operator. Does it?

So that’s why I remarked # that there is another differential equation involving $k$ which comes from Tom Leinster’s condition and which reads

(2)

\Delta k = f k - 2 \,.

This involves the “true” Laplace operator $\Delta$ .

Somebody should try to figure out if this is an equation of the form satisfied by the Pfaffian of the Levi-Civita curvature 2-form of a $2n$ -dimensional manifold.

Because that’s what the generalized Gauss-Bonnet theorem seems to suggest #.

Posted by: urs on October 20, 2006 10:27 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Somebody should try to figure out if this is an equation of the form satisfied by the Pfaffian of the Levi-Civita curvature 2-form of a 2n-dimensional manifold.

If there weren’t enough “connections” in this dialogue already, John’s other engineer friend, Robert Kotiuga, had a nice paper

Helicity functionals and metric invariance in three dimensions
Kotiuga, P.R.
IEEE Transactions on Magnetics

Abstract
The solvability, gauge invariance, and topological aspects of dual variational principles shed light on the difficulties that arise from the use of a vector potential in three dimensions in place of a stream function in two dimensions. These aspects reveal the central role of a relative de Rham complex in place of the usual Tonti diagram. By considering the `spin complex’ associated with the de Rham complex, it is seen that the helicity functional enables the scalar potential to be used in the dual role of a Lagrange multiplier which fixes the gauge of the vector potential. The metric and constitutive law independence of the helicity term is considered. The main purpose is to show how the invariant terms of the helicity functional can be used to avoid rebuilding (reassembling) large parts of the finite-element stiffness matrix in iterative computations involving constitutive laws which change with every iteration. The results are phrased in terms of differential forms

I mention it only because my vague memory tells me that it involves a pfaffian and a discrete connection. However, the pfaffian only appears when the cells are simplicial (I think).

Posted by: Eric on October 20, 2006 3:28 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

It’s been a long time since I’ve thought about any of this (I almost completely forgot about this interesting discussion!), but now after reading Simon’s recent post, I found myself back here with a couple new thoughts.

It has to do with something that is on my mind a lot these days. That is the relationship (or my imagination thereof)

$\text{Groupoids}\leftrightarrow\text{Spaces}$

and

$\text{Categories}\leftrightarrow\text{Space-Times}$

which also relates (in my imagination at least) to the homotopy hypothesis and the directed homotopy hypothesis.

I still think that discrete calculus is related to Tom’s stuff somehow, but the exact relation is still elusive although we have many clues.

The one thing I hope to add is that maybe we should be thinking of “spaces” as special kinds of “spacetimes”. We can do this be extruding the space $\mathcal{M}$ into an orthogonal dimension, or put another way, by forming a cylinder $\mathcal{M}\times I$ .

Then when we combine this with a special kind of discretization of the resulting cylinder (I call it diamonation), then and only then can we truly talk about discrete calculus.

I can’t prove any “NO GO” theorems, but my experience has given me confidence in the claim that there is no general robust discrete calculus on any general space $\mathcal{M}$ , but there is a general robust discrete calculus on any cylinder $\mathcal{M}\times I$ .

So to determine the Euler characteristic of a space $\mathcal{M}$ using discrete calculus, we first need to construct its cylinder $\mathcal{M}\times I$ .

This is partially supported heuristically by Urs’ expression (at least in my world of speculation and total lack of rigor)

$\Delta k = fk−2.$

What if a “spacetime” Laplacian $\Delta_{total}$ could be decomposed into

$\Delta_{total} = \Delta_{space} + \Delta_{time}$

in such a way that

$\Delta_{time} k = -f k$

? If that is possible, we’d have

$\Delta_{total} k = 0$

(mod shifting by a constant).

In the prior discussion of discrete calculus, I was assuming that a discrete calculus was available. In general such a discrete calculus is not available on an arbitrary space $\mathcal{M}$ although it is available on any cylinder $\mathcal{M}\times I$ .

Posted by: Eric Forgy on October 12, 2009 10:57 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

it makes me think about the generalized Gauss-Bonnet theorem.

This is very exciting. Weight is like curvature! (Coweight is like cocurvature?)

To keep our feet on the ground, maybe I should emphasize that in general, a finite category with Euler characteristic (i.e. admitting at least one weighting and at least one coweighting) admits many weightings and many coweightings. So one shouldn’t speak of “the weight” of an object, unless one has a particular weighting in mind.

But maybe that fits the curvature picture. You can deform a Riemannian manifold so that its curvature changes locally, but the “total curvature” is the Euler characteristic, which doesn’t change.

Posted by: Tom Leinster on October 20, 2006 6:23 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Weight is like curvature!

Yes. That’s what it looks like. And curvature, on a graph, is much like defect angle (over volume).

And it is known (for instance page 2 of hep-th/0605022) that the sum of defect angles over vertices is indeed the Euler characteristic! (For triangulations of 2D surfaces, that is.)

So I’d say: a weighting is a generalization of the concept of defect angle (over volume).

And that makes intuitive sense: your formula says that the weighting is the smaller, the more edges meet in a given vertex. Intuituitively: the more edges, the smaller the remaining defect angle.

Posted by: urs on October 21, 2006 3:14 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I didn’t have a chance to look at this paper the first time around. I still don’t really have time, but just want to point out that the way they define D is essentially as the “square root” of the graph Laplacian:

$D = d + \partial$

and

$D^2 = d \partial + \partial d = Graph Laplacian = Degree Matrix - Adjacency Matrix.$

Note that the graph Laplacian is topological and does not properly incorporate the metric information contained in the Laplace-Beltrami operator. It is like choosing a non-physical metric.

Posted by: Eric on February 5, 2007 3:55 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Normally a graph Laplacian is defined for undirected graphs (I think). Say we have a function that maps vertices of our graph to numbers: $a \mapsto k_a$ Then applying the graph Laplacian gives a new function of this sort, namely:

(1) $a \mapsto k_a - \sum_b \xi^a_b k_b$

Is this formula correct in detail?

The general formula that I find # from $(d+\partial)^2$ is

(2)

(\Delta k)(a) = \sum_b (\xi_{ab}+\xi_{ba}) (k(a) - k(b)) \,.

As a consistency check, notice for instance that this way

(3)

\sum_a (\Delta k)(a) = 0 \,,

as it should be.

This also seems to be consistent with writing $\Delta = D - A$ , as Eric did #.

Now restrict attention to the case that $\xi_{ab} = \xi_{ba}$ .

Then Tom Leinster’s condition # implies here that

(4)

(\Delta k)(a) = f(a) k(a) -2 \,,

where

(5)

f(a) := \sum_b (\xi_{ab} + \xi_{ba}) \,.

So $k$ satisfies the differential equation

(6)

\Delta k = f k - 2 \,.

Posted by: urs on October 19, 2006 4:46 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If $\xi_{ab}$ is symmetric, it looks like what you arrive at is twice what I called the unnormalized graph Laplacian, $D-W$ .

Posted by: David Corfield on October 19, 2006 7:47 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If $\xi_{ab}$ ab is symmetric, it looks like what you arrive at is twice what I called the unnormalized graph Laplacian, $D−W$ .

Yes. I think so too. As I said above, this is what Eric calls $D - A$ (“A” for “adjacency”, I guess).

Posted by: urs on October 19, 2006 8:01 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

Is this formula correct in detail?

No - I knew it wasn’t, which is why I threw in some extra fudge factors $\alpha$ and $\beta$ later in that comment.

I’m working in a very rough way here, since I’m confused about something incredibly basic: namely, how you might compute the Euler characteristic as the integral of some solution of an inhomogeneous linear partial differential equation. It seems Tom is doing a discrete analogue of that - but I don’t know anything like that in the continuum case!

So, when I’ve been writing “Laplacian”, you should probably read it as “some linear differential operator”. And, when I write “Poisson’s equation”, you should read “some inhomogenous linear PDE”. Sorry!

I hope we get this figured out…

Posted by: John Baez on October 20, 2006 7:56 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

John wrote (apropos of me being asked to summarize my own paper):

he should do it if we ask him.

:-) No one can be stern in quite the same way as John.

Anyway, I plead innocence. As I mentioned, I did write a summary… but on some pieces of paper, while I was at home (computerless). And in the surprisingly long time it took me to transfer said papers to my office, Toby posted such an effective summary that I decided mine was redundant.

John wrote:

I just realized that Tom’s weightings and coweightings are functions from vertices of a directed graph to numbers.

I’ve been trying to figure out a good conceptual way of thinking about weightings, but not had a lot of success so far (hence the bland name). Here’s the best I can do.

A weighting on a graph is something that assigns to each vertex $a$ a number $k^a$ , in such a way that for all $a$ ,

(1)

\sum_{f: a \rightarrow b} k^b = 1.

Imagine a particle wandering randomly around the graph. Suppose it’s at vertex $a$ . Its next move will be to travel down one of the arrows out of $a$ , and it travels down $f: a \rightarrow b$ with probability $k^b$ . The equation above says that the probabilities sum to 1. So the idea is to think of $k^b$ as being the “attractiveness” of $b$ ; if you’re at $a$ , the probability that you move to $b$ is the attractiveness of $b$ times the fatness of the pipe from $a$ to $b$ (that is, the number $\zeta^a_b$ of arrows from $a$ to $b$ ).

So weight could be called “attractiveness”, and a weighting an “attraction function”. Coweights are repulsive.

(Of course, this explanation works best if your weights $k^a$ are all between 0 and 1, but isn’t it normal in quantum theory to have probabilities outside the traditional range?)

Posted by: Tom Leinster on October 19, 2006 9:08 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If you look at p. 12 of the notes I mentioned, $D^{-1} W$ also has a probabilistic interpretation, as the matrix of transition probabilities proportional to the weights on edges emerging from a point. Somehow you’ve got these probabilities factorised into attractiveness $\times$ fatness. I could see how to convert between them. Your $k_j$ is the sum of my $j^{th}$ column divided by the sum of fatnesses coming into $j$ . But what does it mean?

Posted by: David Corfield on October 19, 2006 10:00 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

That paper is very interesting. I wish I was smarter. There are so many inter-related concepts going on here. The probability interpretation makes sense because the Laplace-Beltrami operator is the generator for stochastic processes, i.e. random walks, on smooth manifolds. So the discrete version of this appears to be popping up.

[Note: John and Urs know this already, but others may not. My knowledge of this stuff is less than skin deep and most of what I ever say is going to be technically incorrect, but that doesn’t stop me. Usually there is a grain of truth and Urs has an amazing ability to decipher my incoherent babbling.]

Posted by: Eric on October 20, 2006 12:50 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Tom wrote:

:-) No one can be stern in quite the same way as John.

I’ll take that as a compliment, but I was actually making a complicated joke, saying: yes, David, only a jerk asks you to summarize what you just wrote, but when a jerk asks you in public, it’s good for your own reputation to go along - so, knowing that Tom knows that, I’ll be the jerk who asks him to summarize what he just wrote, and he’ll do it.

And it would have worked, except for some reason you wrote your reply on paper.

(That’s me being stern.)

More importantly:

A weighting on a graph is something that assigns to each vertex $a$ a number $k^a$ , in such a way that for all $a$ ,

(1) $\sum_{f: a \rightarrow b} k^b = 1.$

Imagine a particle wandering randomly around the graph. Suppose it’s at vertex $a$ . Its next move will be to travel down one of the arrows out of $a$ , and it travels down $f: a \rightarrow b$ with probability $k^b$ . The equation above says that the probabilities sum to 1.

Gah! So you’re thinking of $k^b$ as a probability for a particle to move from $a$ to $b$ , while I was trying to think of it as a probability of finding a particle at $b$ .

I guess that explains why I was getting so confused by the probabilistic interpretation of what you were doing! It will take a while to recover.

But, we all seem to agree there’s some mystical relationship between Euler characteristic and little particle thingies doing random walks. Does anyone know the simple reason for this mystical relationship? There’s got to be one, but nobody ever told me what it was.

(Urs is right to emphasize that the “density” of these little particle thingies may in general need to be described by a $p$ -form, not just a function.)

Posted by: John Baez on October 20, 2006 9:00 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

John is completely correct to encourage exposition. After that person requested me to summarise my book, and remember that it’s not such an easy thing to do in philosophy, I did engage in a dialogue with him, gritting my teeth in the face of protracted rudeness and willful misinterpretation on his part, sustained by the idea that I was speaking beyond him to other readers. There’s no comparison with being enticed into the cosy atmosphere of the Café!

Of course, if all mathematics were carried out in the open source, wiki style of the Café, all one would need do when asked about a paper would be to provide a link.

Tom’s probabilistic interpretation would seem to need quite some reconfiguring to bring it into line with the graph Laplacian approach (or vice versa). Remember he told us that there’s a weighting for a category with a terminal object, which is 1 on that object, and 0 elsewhere. So take a category like the full subcategory of FinSet of sets of cardinality less than 1000. There’s all that wonderful fatness of connection to be found but because the only attractiveness occurs in {*}, everything flows there in one step and stays there.

Posted by: David Corfield on October 20, 2006 9:57 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

David wrote:

Of course, if all mathematics were carried out in the open source, wiki style of the Café, all one would need do when asked about a paper would be to provide a link.

No. I seem not to have convinced you of the serious part of the point I was trying to make. So, I’ll turn up the rhetorical heat a bit - being stern as only I can be.

What’s the real-life psychological equivalent of giving someone a link when they ask you on this blog about the contents of some paper?

It’s this: you’re talking to someone, and they ask you a question about some math paper, and you say “The paper is lying on the table right there in the next room - go read it.”

The subtext is: don’t expect me to tell you; I’m too busy. Go away and figure it out yourself, and come back when you’re done.

This tends to cut off the conversation. Sometimes this is the right thing to do, but often it’s not. The main thing is to be aware of the effect.

A lot of people don’t think hard about how situations in cyberspace evoke emotions based on analogous situations in real life. This is one reason there are lots of flame wars online.

Also, a lot of people don’t think hard about how technical papers on math and science evokes emotions based on analogies to good old-fashioned story-telling. This is one reason most of these papers are so boring and hard to understand. And, it’s one reason people seem to like the way I write - because I think about this stuff.

People are a lot more primitive and emotional than they like to pretend; if one keeps this in mind all sorts of things magically work better.

Posted by: John Baez on October 20, 2006 8:31 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

Yes to conversation. I had let my imagination run ahead of me and saw a hundred interconnected cafés, franchises spread across all parts of mathematics. And good conversation to be had on whatever topic you desired just one link away.

Posted by: David Corfield on October 21, 2006 12:43 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

An example to see how strange these probabilities are: In the category with two objects, a set, 2, of 2 elements and one of 3 elements, 3, with all maps between them, the weighting is $1/2$ on 2 and $-1/9$ on 3. The ‘probability’ transition matrix is $\left( \array{2 & -1 \\ 4 & -3} \right)$ and the steady state distribution has ‘probability’ $4/3$ at 2 and $-1/3$ at 3.

If we wanted this to come from an undirected similarity graph, we would need negative weights. We could have $W$ equal to

\left( \array{8 & -4 \\ -4 & 3} \right).

The normalized Laplacian is

\left( \array{-1 & 1 \\ -4 & 4} \right),

which has

one zero eigenvalue, hence one connected component?

Posted by: David Corfield on October 20, 2006 10:35 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

[…] see how strange these probabilities are […]

I would also think that interpreting $k^b$ as the probability for motion along an edge $a \to b$ # is somewhat counter-intuitive, since that probability does not depend on the edge itself, but just on its endpoint.

That doesn’t mean that there can be no context in which this is the natural interpretation. But it looks a little non-generic to me.

Posted by: urs on October 20, 2006 2:24 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

But, we all seem to agree there’s some mystical relationship between Euler characteristic and little particle thingies doing random walks. Does anyone know the simple reason for this mystical relationship? There’s got to be one, but nobody ever told me what it was.

Stream of consciousness…

Euler characteristic can be expressed in terms of a trace over something that depends on Laplace-Beltrami.

Laplace-Beltrami is the infinitessimal generator for random walks on smooth manifolds.

The thing the Euler characteristic comes from looks like a generator.

The “square root” of Laplace-Beltrami is a Dirac operator.

The Dirac equation can be related to a Feynman checkerboard, i.e. a random walk on an n-diamond.

Dirac equation can be used to derive a metric via NCG (I think)

There is a deep connection between NCG and stochastic calculus (btw, I was the first person to apply NCG to finance ;))

Discrete calculus on an n-diamond is equivalent to a discrete version of stochastic calculus.

Stochastic calculus is all about random walks.

Any thing else? :)

Gotta run…

Eric

Posted by: Eric on October 20, 2006 3:53 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

One more thing to the stream of consciousness…

In stochastic calculus, the metric can be identified with statistical covariance.

Posted by: Eric on October 20, 2006 3:57 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

But, we all seem to agree there’s some mystical relationship between Euler characteristic and little particle thingies doing random walks. Does anyone know the simple reason for this mystical relationship? There’s got to be one, but nobody ever told me what it was.

Stream of consciousness…

Yes, that’s precisely the right stream of conciousness, I think (it’s not quite a coincidence that I agree so much with Eric here ;-).

Whether we think of classical particles doing random walks or of quantum particles doing whatever quantum particles do is not all that crucial. The difference is just a factor of $i$ in the eigenvalues of stationary states of these particles - but the Euler characteristic is determined only by the 0-eigenvalues, where the factor of $i$ becomes invisible.

Posted by: urs on October 20, 2006 4:21 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

the Euler characteristic is determined only by the 0-eigenvalues

So this should incline us to think Tom’s definition is quite distant from graph Laplacians? The category I mentioned has Euler characteristic 7/18.

Posted by: David Corfield on October 20, 2006 4:59 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

the Euler characteristic is determined only by the 0-eigenvalues

So this should incline us to think Tom’s definition is quite distant from graph Laplacians?

Hm, no, I don’t think so.

Let me clarify those 0-eigenvalues:

For an ordinary Riemannian manifold $(X,g)$ you can compute the Euler number as the alternating sum of the Betti numbers. The $p$ th Betti number, in turn, can be considered as giving the number of 0-eigenvalue eigenstates of degree $p$ of the Laplace-Beltrami operator.

The thing is, in the formula for the “partition function of the $N=2$ superparticle” on $X$ , which is

(1)

\mathrm{str} e^{-t (d + d^\dagger)^2}

all the eigenstates of eigenvalue different from 0 cancel out, because for a degree $p$ -eigenstate $\psi$ of nonvanishing eigenvalue and not annihilated by $d + d^\dagger$ we always have a degree $(p+1)$ -eigenstate of the same eigenvalue, namely $(d + d^\dagger)\psi$ . So in the supertrace their contributions cancel out and only the contributions by the 0-eigenvalues remain and conspire to give the Euler characteristic.

This is just the simplest toy example of a way bigger story. Parts of this story are discussed here.

Posted by: urs on October 20, 2006 5:20 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Urs wrote:

I am a little hesitant to call the operator

(1) $k \mapsto (a \mapsto \sum_b \xi^a_b k(b))$

a “Laplace operator”. It does not seem to share any of the properties that one would usually expect of a Laplace operator. Does it?

It’s a linear operator that is “local” in some sense, a discretized version of a partial differential operator. That’s about all. Sorry, I was getting quite sloppy.

So that’s why I remarked # that there is another differential equation involving $k$ which comes from Tom Leinster’s condition and which reads

(2) $\Delta k = f k - 2 \,.$

This involves the “true” Laplace operator $\Delta$ .

Okay, that’s much better. Thanks!

But, I’m still confused, at a very basic level: I don’t know any formula anywhere that expresses the Euler characteristic as a kind of integral involving a solution of an inhomogeneous linear PDE.

If there is such a formula, I believe Tom has discretized it, thus generalizing it from manifolds to categories.

The mere fact that Tom’s work generalizes the Euler characteristic of a finite directed circuit-free graph suggests there must be such a formula!

So, I want one of you to tell me this formula.

The Gauss-Bonnet formula expresses the Euler characteristic as an integral, but not clearly involving a solution of an inhomogeneous linear PDE. Maybe there’s a trick I’m missing. That’s why I was trying to drag in Poisson’s equation.

Posted by: John Baez on October 20, 2006 8:11 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

(1) $k \mapsto (a \mapsto \sum_b \xi^a_b k(b))$

[…] It’s a linear operator that is “local” in some sense, a discretized version of a partial differential operator.

True. If we could identify the continuum limit of this operator, it would be helpful.

As Eric points out # we could think of this expression as obtained from the exterior differential $d k$ by some manipulations. But I don’t see the natural continuum limit yet.

Which doesn’t mean that there is none.

It would also help to have a continuum understanding of the function

(2)

a \mapsto \sum_b (\xi_{ab}+\xi_{ba}) \,.

I don’t know any formula anywhere that expresses the Euler characteristic as a kind of integral involving a solution of an inhomogeneous linear PDE.

The only formula we know which expresses the Euler characteristic as the integral of anything is the (generalized) Gauss-Bonnet formula, which expresses it as the integral of the Pfaffian $P(F)$ of the Levi-Civita curvature 2-form associated to some metric.

So maybe we should ask the other way around:

is there a good differential equation satisfied by $P(F)$ ?

what is $\Delta P(F)$ ? is it maybe of the form something times $P(F)$ plus a constant? If the latter is true, we are in business.

To my embarrassment I have to realize that I have no good idea what $\Delta P(F)$ would be, not even for the 2-dimensional case (which we might want to think about first), where $P(F)$ is nothing but the Ricci scalar $R$ .

What is $\Delta R$ ?

Posted by: urs on October 21, 2006 2:47 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

I forget the details, but I think the paper from Kotiuga does something with a differential operator on the vector potential (probably computes the curvature), evaluates it on a simplex and shows that what you get is the pfaffian related to the curvature. Something like that. I don’t have the paper and have no access to a library unfortunately. Maybe I should just ask him :)

Posted by: Eric on October 21, 2006 6:27 PM | Permalink | Reply to this

Read the post Canonical Measures on Configuration Spaces
Weblog: The n-Category Café
Excerpt: On how the Leinster weighting on a category might provide path integral measures in physics.
Tracked: March 8, 2007 9:44 AM

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I hope someone notices this comment!

In some circumstances, it makes sense to talk about ‘cardinalities’ of algebraic objects: for example, the cardinality of the space of binary rooted trees is famously $\mathrm{e} ^{\pm i \pi / 3}$ , solving the equation $X=1+X^2$ . I have two questions about this.

Why does it make sense to call this sort of cardinality an Euler characteristic, as some authors do?
What is the connection of such a cardinality to the Leinster measure? Of course, these cardinalities cannot be Leinster cardinalities in general, as Leinster cardinalities are never complex.

Posted by: Jamie Vicary on June 13, 2007 9:12 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Jamie wrote:

Why does it make sense to call this sort of cardinality an Euler characteristic, as some authors do?

Because in some famous cases that’s what it is. More precisely, it’s an Euler–Schanuel characteristic. In this wonderful paper:

Steve Schanuel, Negative sets have Euler characteristic and dimension, Lecture Notes in Mathematics 1488, Springer Verlag, Berlin, 1991, pp. 379-385.

Schanuel shows you can extend Euler characteristic in such a way that you can take a space, slice it up in surprisingly general ways, and compute its Euler–Schanuel characteristic as the sum of the Euler–Schanuel characteristics of the pieces.

You can see lots of examples in the slides here.

Most famously, the Euler–Schanuel characteristic of the open interval is $-1$ , since 2 open intervals plus a point is another open interval:

$(0,1/2) \cup \{1\} \cup (1/2,1) = (0,1)$

What is the connection of such a cardinality to the Leinster measure? Of course, these cardinalities cannot be Leinster cardinalities in general, as Leinster cardinalities are never complex.

That’s only true if you’re conservative and refuse to sum divergent series using fancy resummation methods! If you use such fancy techniques you can get complex Leinster cardinalities for various categories. A fully functioning theory of when you’re allowed to do this has not yet been developed, which is why it’s hard to read much about this. But, it’s only a matter of time!

Posted by: John Baez on June 15, 2007 7:49 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I wonder how generalizable the following is.

Fiedorowicz and Loday in ‘Crossed simplicial groups and their associated homology’, Transactions of the American Mathematical Society, 326(1):57-87, 1991 (available at JSTOR), show how the cylic category, and related categories, arise from a double category with the simplicial category $\Delta$ running horizontally, and some groupoid running vertically. In the case of $\Lambda$ this groupoid is the union of finite cyclic groups. When a certain ‘star condition’ (p. 63) is satisifed, the double category gives rise to an ordinary category whose morphisms are uniquely expressible as a vertical morphism followed by a horizontal one.

In this situation presumably the characteristic of this ‘product’ is the product of the characteristics of horizontal and vertical categories. As the characteristic of $\Delta$ is 1, it would explain why that of $\Lambda$ is infinite, the characteristic of the union of cyclic groups being the harmonic series.

The star condition requires that any pair $(\phi, g)$ , $\phi$ vertical and $g$ horizontal with the same target determines a unique bimorphism. I wonder how tough a condition this is to satisfy.

Posted by: David Corfield on June 15, 2007 9:19 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Thanks for that reference. I’ve been wanting to get hold of LNM 1488 for a while now; it seems Lawvere also has an interesting paper in it, pages 1-13. But, presumably due to the ridiculous expense, Imperial doesn’t subscribe electronically, and even worse, doesn’t have a physical copy! It seems crazy that in this day and age one still has to use the inter-library loan service to get important articles…

If you use such fancy techniques you can get complex Leinster cardinalities for various categories.

Wow! Any examples??

For the case of rooted binary trees, for what category would we expect to get cardinality $e^{i \pi/3}$ — the appropriate rig category?

Posted by: Jamie Vicary on June 15, 2007 9:21 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Actually, perhaps we should be using a category where objects are (isomorphism classes of) trees, since the Euler characteristic ‘counts the number of objects’, and $e ^{i \pi/3}$ is the number of trees in a suitably-resummed way. But we need to avoid categories with initial or terminal objects, surely… and it seems far too boring to just use the discrete category where objects are iso classes of trees.

Posted by: Jamie Vicary on June 15, 2007 10:48 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

Worrying about number of objects in a category is a sign of what John calls ‘evil’. It looks like what we have here is the groupoid of binary trees with leaves labelled by an ordered set, and morphisms which are tree isomorphisms preserving leaf order. This is equivalent to what seems to you ‘too boring’, though with it we can derive an interesting equivalence between it and its seventh power.

It would be interesting to find out the cardinalities of categories with the same objects but different morphisms, e.g., forgetting the leaf order, any tree morphism.

Do we have examples yet of category cardinality for categories with infinitely many isomorphism classes of object which aren’t groupoids and which don’t have an initial or terminal object, other than the cyclic category? Note though that even in this last case there’s a ‘product’ between a groupoid and a category with a terminal object.

Posted by: David Corfield on June 15, 2007 11:20 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

It looks like what we have here is the groupoid of binary trees with leaves labelled by an ordered set, and morphisms which are tree isomorphisms preserving leaf order. This is equivalent to what seems to you ‘too boring’, though with it we can derive an interesting equivalence between it and its seventh power.

I can’t see how we’ve got enough information in this categorical picture for this to be an ‘interesting’ equivalence, though. The category we end up with is equivalent to a discrete category, right? In other words, it’s a set, and a set can’t exhibit any interesting isomorphisms, like $T \simeq 1 + T^2$ or $T \simeq T^7$ . Surely we only get an interesting equivalence when the basic isomorphism $T \simeq 1 + T^2$ is somehow built-in, but it seems to me that we erased that information as we constructed the category. This is the sense in which I describe the category as ‘too boring’.

I agree that it would be interesting to think about categories with richer morphisms, which don’t have to preserve so much structure. Surely the problem is that if you go too far with this you end up with categories that have initial or terminal objects, and so have trivial cardinality.

In fact, something here is confusing me. There’s a sense in which there are $e$ finite sets, and there’s a sense in which there are $e ^{i \pi/3}$ finite binary rooted trees. We count finite sets by taking the cardinality of the category of finite sets and bijections, but we certainly can’t get $e ^{i \pi/3}$ that way for binary rooted trees. Perhaps I’m making a mistake by identifying these notions of ‘cardinality’ in my mind; can someone separate them for me?

Posted by: Jamie Vicary on June 15, 2007 1:05 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Doesn’t the difference you mention in the last paragraph come down to disallowing nontrivial bijections in the tree case, e.g., by the device of ordering leaves? If we did this for finite sets, i.e., just looked at ordered sets and order preserving bijections, the cardinality would be $1 + 1 + 1 + ...$ , $1/(1 - x)$ evaluated at $x = 1$ .

Perhaps an interesting first step would be to work out the groupoid cardinality of binary rooted trees with their nontrivial bijections.

Posted by: David Corfield on June 15, 2007 2:13 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If we did this for finite sets, i.e., just looked at ordered sets and order preserving bijections, the cardinality would be $1+1+1+...$ , $1/(1−x)$ evaluated at x=1.

Exactly — and I can’t think of any way that we can perform some sort of formal manipulations to write that sum as

e

Perhaps an interesting first step would be to work out the groupoid cardinality of binary rooted trees with their nontrivial bijections.

Yeah, I agree. That would be a fun calculation! But what do we expect this to be? And what significance should the result have? That’s the key thing to understand.

Posted by: Jamie Vicary on June 15, 2007 3:52 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I can’t think of any way that we can perform some sort of formal manipulations to write that sum as $e$ .

But it’s not $e$ . The category of unordered sets and bijections has cardinality $e$ as the sum is $\sum 1/n!$ , each object weighted by the reciprocal of the number of bijections.

Posted by: David Corfield on June 15, 2007 4:13 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Consider the category of unordered sets over the two element set.

What is its cardinality?

Each $n$ now contributes

$\frac{1}{n!}$ for when everything lives over the first element

another

$\frac{1}{n!}$ for when everything lives over the second element

and then a contribution from every possible combination in between.

Is it

$\sum_{n=0}^\infty \sum_{k=0}^n \left( \array{ n \\ k } \right) \frac{1}{k!} \frac{1}{(n-k)!}$ ?

Posted by: urs on June 15, 2007 4:24 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

If your two element set is ordered, it should have cardinality $e^2$ . If not, $\frac{e^2}{2}$ .

I don’t think you need that combinatorial factor in your sum.

Posted by: David Corfield on June 15, 2007 4:42 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I don’t think you need that combinatorial factor in your sum.

Maybe I am confused. But are you taking into account that a morphism of sets over another set $S$ have to respect the $S$ -labels? Doesn’t that imply that when $k$ elements are labeled black and $(n-k)$ are labelled white, there are $k! (n-k)!$ many bijections?

Posted by: urs on June 15, 2007 5:10 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Oh, sorry, I get your point. You did agree with the $k!(n-k)!$ -factor, but are saying I should simply drop the combinatorial factor. Right! Thanks.

Cool, so that’s where the other powers of $e$ enter. That’s interesting, given our recent interest in sets over other sets…

Posted by: urs on June 15, 2007 5:13 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

So what’s the groupoid cardinality of $U(1)$ -phased sets, or sets over $U(1)$ ? Will it be $e^{|U(1)|}$ , which we might hazard is $e^0$ , or 1?

Posted by: David Corfield on June 15, 2007 5:31 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I bet phased sets are not quite the right thing to consider, in the end.

My money is on groupoids fibered over $\Sigma U(1)$ .

That’s why I’d think we should consider this slight modification of your question.

Posted by: urs on June 15, 2007 5:38 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

But it’s not $e$ . The category of unordered sets and bijections has cardinality $e$ as the sum is $\sum 1/n!$ , each object weighted by the reciprocal of the number of bijections.

Yes, I know, that’s exactly the point I’m trying to make! I’m arguing that only including trivial bijections (i.e. bijections of ordered sets) seems uninteresting, for precisely that reason.

Perhaps this has all got a bit muddled; what I’m trying to say isn’t particularly sophisticated. For sets, it seems interesting to take the cardinality of the category where objects are finite sets and morphisms are all bijections. For rooted binary trees, it seems interesting to take the cardinality of the category where objects are binary rooted trees with ordered leaves, and morphisms are isomorphisms preserving the ordering, because then we get the sum of the Catalan numbers, which after funky resummation $e ^{-i \pi/3}$ .

These seem to be different prescriptions for calculating cardinalities of algebraic structures. Why do we need to allow all bijections to get an interesting answer for the category of sets, but only the trivial bijections to get an interesting answer for the category of binary rooted trees? This is what I want to know.

Posted by: Jamie Vicary on June 15, 2007 5:05 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Do we know anything about the cardinality of the 2-groupoid of groupoids with finitely many objects?

Do we know anything about the cardinality of the 2-groupoid of groupoids over a fixed groupoid with finitely many objects?

Do we know anything about the cardinality of the 3-groupoid of 2-groupoids with finitely many objects?

Do we know anything about the cardinality of the 3-groupoid of 2-groupoids over a fixed 2-groupoid with finitely many objects?

Posted by: urs on June 15, 2007 5:28 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

Presumably for the first question you could just look at skeletal groupoids, which are just unions of groups.

Hmm, we don’t even know the groupoid cardinality of all finite groups.

Posted by: David Corfield on June 15, 2007 5:49 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

This is a cute question. How much is known? For instance, does the series converge, either apparently or rigorously? If not, has anyone written down the first few terms?

Posted by: James on June 16, 2007 12:58 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Yes, you wonder if this cardinality would link to various asymptotic results concerning groups of different orders.

Robert Solomon wrote in 2001,

An ever-improving arsenal of computer algorithms for the identification of permutation groups, linear groups and more generally “black box” groups is being assembled by Kantor, Seress and many other researchers. In particular there is hope of determining all finite groups of order at most 2001 in the year 2001. On the other hand, calculation of groups of order $2^{10}$ has reconfirmed the long-known fact that “most” finite groups are nilpotent groups of nilpotence class at most 2 and they exist in frightening numbers.

Thus the classification of all finite groups is completely infeasible. Nevertheless experience shows that most of the finite groups which occur “in nature” – in the broad sense not simply of chemistry and physics, but of number theory, topology, combinatorics, etc. – are “close” either to simple groups or to groups such as dihedral groups, Heisenberg groups, etc., which arise naturally in the study of simple groups. And so both the methodologies and the database of information generated in the course of the Classification Project remain of vital importance to the resolution of questions arising in other disciplines. (p. 347)

Somewhere where we have expectations of an infinite collection of groups giving rise to a finite cardinality concerns the 2-sphere. It’s Euler characteristic is 2, and this should relate to the alternating product of group orders of its homotopy groups, according to the Baez-Dolan scheme of things.

Posted by: David Corfield on June 16, 2007 9:33 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I’m glad no one beat me to this…

The series definitely diverges. The cyclic groups $Z/pZ$ of prime order have $p-1$ automorphisms, and the sum of $1/p-1$ diverges.

It seems that if you want to start playing with divergent-summation tricks, you’d have to know a lot more.

Posted by: James on June 16, 2007 10:46 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Grr! You beat me to it …

Posted by: Tim Silverman on June 16, 2007 4:46 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

This paper by Blass is the place to look to see what’s interesting about the isomorphism between $T$ and $T^7$ .

Posted by: David Corfield on June 15, 2007 8:54 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I’ll pop out of some layers of nested conversation and answer Jamie Vicary’s question here:

These seem to be different prescriptions for calculating cardinalities of algebraic structures. Why do we need to allow all bijections to get an interesting answer for the category of sets, but only the trivial bijections to get an interesting answer for the category of binary rooted trees?

It’s really pretty simple:

The relevant category of binary planar rooted trees is just a set — in other words, a ‘discrete category’, one with only identity morphisms. In this case Euler–Leinster characteristic reduces to the usual cardinality of sets.
So, to count all the binary rooted planar trees, we simply add up the number of $n$ -leaved trees for all $n$ , getting the sum of all Catalan numbers:

$1 + 1 + 2 + 5 + 14 + 42 + \cdots$

This clearly equals:

${1 - \sqrt{-3} \over 2}.$

Well, okay, we pulled a little trick here: we took the series

$1 + x + 2x + 5x^2 + 14x^3 + 42x^3 + \cdots$

and noticed that it converges to

$\frac{1 - \sqrt{1 - 4x}}{2}$

for small values of $x$ . Then we analytically continued to $x = 1$ and got our answer!

In fact the function above has a branch point at $x = 1/4$ , so we really get an ambiguous answer:

$\frac{1 \pm \sqrt{1 - 4x}}{2}$

This hints at a fun relation between Galois theory, branched covering spaces and these generalized cardinalities… something I wanted Jeffrey Morton to work on for his thesis before he revolted and insisted on doing something more connected to physics.

But anyway: we’ve got ordinary cardinality and some sneaky resummation stuff going on here. There are various ways to systematize and ‘justify’ this sneaky stuff, due to Lawvere, Blass, Schanuel and his student Robbie Gates, later generalized by Leinster and Fiore.
The relevant category of finite sets is a groupoid — the groupoid of finite sets and bijections. In this case Euler–Leinster characteristic reduces to the usual cardinality of groupoids.
So, we sum $1/|Aut(x)|$ over isomorphism classes of objects $x$ , and get

$\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots$

which converges to $e$ without any sneaky analytic continuation tricks.

You can also try to compute the cardinality of various groupoid of trees with interesting non-identity isomorphisms, etc. — a lot of variants are considered here:

F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Encyclopedia of Mathematics and its Applications vol. 67, Cambridge University Press, Cambridge, 1998.

So, while we haven’t found an all-embracing theory of cardinality that covers all the examples, all the examples seem to be hinting at the existence of such a theory: basically, Euler–Leinster characteristic for $\infty$ -categories, plus some rules for resumming divergent series.

Posted by: John Baez on June 16, 2007 7:33 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Jamie Vicary said:

Why do we need to allow all bijections to get an interesting answer for the category of sets, but only the trivial bijections to get an interesting answer for the category of binary rooted trees?

I’m not sure how you gauge interestingness. A small change to sets with trivial bijections, by 2-colouring them, and you have cardinality

$1 + 2 + 4 + ... = \frac{1}{1 - 2} = -1.$

Anyway, there’s nothing uninteresting about an infinite cardinality, e.g., that of the groupoid which is the union of cyclic groups.

That is a genuine unresummable infinity. There are a lot of subtleties in this. Pierre Cartier shows how (1 + 1 + 1 + …) has different sums if it’s a sum of zero powers of integers, depending on what the $n$ is for which the first ‘1’ is $n^0$ , see eq. 87, p. 69.

Posted by: David Corfield on June 16, 2007 9:17 AM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Anyway, there’s nothing uninteresting about an infinite cardinality, e.g., that of the groupoid which is the union of cyclic groups.

You’re right, I suppose uninteresting would be a bit strong. But a groupoid with infinite cardinality doesn’t decategorify to a scalar in our 1-category of vector spaces, right? (Depending on what our scalars are, of course — but this will be the case if our scalars are the reals or the complexes.)

Posted by: Jamie Vicary on June 16, 2007 10:57 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

John Baez said:

The relevant category of binary planar rooted trees is just a set … So, to count all the binary rooted planar trees, we simply add up the number of n-leaved trees for all n … this clearly equals

$\frac {1- \sqrt{-3}} {2}.$

The thing that I have a problem with is that you have to sneakily inject extra information! All we started with was (at least equivalent to) a countably-infinite set, in the form of a discrete category with a countable infinity of objects. But somehow, we knew how to perform the resummation! That’s information that clearly doesn’t live in the category.

So, we’re not really taking the cardinality of a category. We’re taking the cardinality of a (category + some stuff). Can we express this ‘stuff’ — presumably, the polynomial $T \simeq 1 + T^2$ — as structure on the category in the usual sense? Even better, can we then build it into a generally applicable summation algorithm? I’m sure the answer is “no!”

Posted by: Jamie Vicary on June 16, 2007 2:58 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

Jamie Vicary wrote:

So, we’re not really taking the cardinality of a category. We’re taking the cardinality of a (category + some stuff).

You’re right, of course. I was using a sneaky generalization of groupoid cardinality, which requires that we have a ‘grading’ on our groupoid $C$ , meaning a functor

$deg: C \to \mathbb{N}$

where $\mathbb{N}$ is the discrete category with natural numbers as objects. This allows us to write our groupoid as a coproduct

$C = \sum_{n = 0}^\infty C_n$

where $C_n$ is the full subcategory whose objects have degree $n$ .

Naively, the groupoid cardinality of $C$ in this situation satisfies

$|C| = \sum_{n = 0}^\infty |C_n| .$

But, in many cases this diverges, so we instead consider the power series

$|C|(z) = \sum_{n=0}^\infty |C_n| z^n.$

If this converges in some neighborhood of the origin, we can try to analytically continue it to $z = 1$ and define the result to be the ‘analytically continued’ cardinality of $C$ .

This works in many examples. Sometimes there are poles, which are no big deal unless they lie at $z = 1$ . Other times there are branch points, as in the example above. This is trickier since it means the cardinality is only defined up to the action of some Galois group (i.e., group of deck transformations).

Can we express this ‘stuff’ — presumably, the polynomial $T \simeq 1 + T^2$ — as structure on the category in the usual sense? Even better, can we then build it into a generally applicable summation algorithm? I’m sure the answer is “no!”

Why are you sure?

I wouldn’t expect to get a universally applicable summation algorithm for computing all the various generalizations of cardinality I’ve seen. But, one rarely manages to formalize all ones intuitions about a given subject. We usually settle for formalizing some of them. We dream impossible dreams, then accomplish some possible fragment of them. I don’t see any reason why we shouldn’t be able to achieve this here.

Indeed, there are already some impressive results. Gates, Leinster and Fiore have a nice general theory of objects that satisfy polynomial ‘equations’ (really isomorphisms) like $T \simeq 1 + T^2$ . There’s also a nice theory of resummation methods for Euler characteristics:

William J. Floyd and Steven P. Plotnick, Growth functions on Fuchsian groups and the Euler characteristic, Invent. Math. 88 (1987), 1-29.
R. I. Grigorchuk, Growth functions, rewriting systems and Euler characteristic, Mat. Zametki 58 (1995), 653-668, 798.

I think we just need to keep pondering this stuff and developing it.

Posted by: John Baez on June 16, 2007 11:43 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

I just read the linked paper of Leinster and Fiore, and it seems like the key point to them is that the series $T(z)=z+z^2+2z^3+5z^4+\ldots$ satisfies $T(z)=z+T(z)^2$ . We don’t really have to think of $e^{\pi i /3}$ as the result of Abel summation, it is simply the only value for $T(1)$ consistant with the above equation. The rest of the paper works with the consequences of the equation $T=T^2+1$ .

So, the real question is, in what sense is the bijection between the sets $T$ and $T^2+1$ good, while a bijection between the countably infinite sets $T$ and $2T+1$ would not be good?

It seems like Blass is attacking this in his paper (which I have only skimmed) in his notion of a “very explicit bijection”. Here at the n-Category cafe, perhaps a more natural approach would be to place some nontrivial category structure on $T$ , so that there is an equivalence of categories from $T$ to $T^2+1$ , but none from $T$ to $2T+1$ . Any thoughts?

Posted by: David Speyer on June 16, 2007 7:12 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

David Speyer wrote:

… perhaps a more natural approach would be to place some nontrivial category structure on $T$ , so that there is an equivalence of categories from $T$ to $T^2+1$ , but none from $T$ to $2T+1$ . Any thoughts?

I agree, this does sound like a natural way to think about it. It’s interesting that throughout this discussion there’s been hardly any mention of the morphisms that might form part of a category of binary rooted trees; surely this an indication that we’re not talking about things in the right way!

It’s interesting that the set of BRTs is completely generated by the isomorphism $T=1+T^2$ , allowing us to create the set of trees 1, (1,1), ((1,1),1), (1,(1,1)), ((1,1),(1,1)) and so on. Can we also employ $T=1+T^2$ to generate a category? Surely we need to ‘categorify’ $T=1+T^2$ itself first! But what’s a categorification of a polynomial? A relaxation of the equality to a particular isomorphism? And how might that apply here?

Posted by: Jamie Vicary on June 18, 2007 10:22 PM | Permalink | Reply to this

Re: Euler Characteristic of a Category

Not sure how it is related (if at all), but binary trees have certainly cropped up in the work Urs and I did together, but we called them 2-diamonds :)

I’m willing to guess that this has secretly been in the background of a lot of what Urs’ thinks about.

Posted by: Eric on June 18, 2007 10:54 PM | Permalink | Reply to this

Read the post Return of the Euler Characteristic of a Category
Weblog: The n-Category Café
Excerpt: Leinster's second paper on the Euler characteristic.
Tracked: July 9, 2007 9:40 AM

Read the post Metric Spaces
Weblog: The n-Category Café
Excerpt: Tom Leinster on the cardinality of a metric space, thought of as an enriched category --- and an interesting relation to geometric measure theory.
Tracked: February 9, 2008 7:31 PM

Read the post News on Measures on Groupoids?
Weblog: The n-Category Café
Excerpt: Benjamin Bahr apparently thought about measures on groupoids of connections.
Tracked: July 17, 2008 10:01 AM

Re: Euler Characteristic of a Category

Now we have an Euler characteristic for infinite acyclic categories with filtrations.

Posted by: David Corfield on April 16, 2010 12:37 PM | Permalink | Reply to this

Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: January 10, 2011 4:00 PM

Re: Euler Characteristic of a Category

$MathML-enabled post (click for more details).$

We might have expected that work to unify the groupoid cardinality and Euler characteristic would require some deep homotopy theory.

Lior Yanovski, Homotopy Cardinality via Extrapolation of Morava-Euler Characteristics

We answer a question of John Baez, on the relationship between the classical Euler characteristic and the Baez-Dolan homotopy cardinality, by constructing a unique additive common generalization after restriction to an odd prime $p$ . This is achieved by $\ell$ -adically extrapolating to height $n = -1$ the sequence of Euler characteristics associated with the Morava $K(n)$ cohomology theories for (any) $\ell | p-1$ . We compute this sequence explicitly in several cases and incorporate in the theory some folklore heuristic comparisons between the Euler characteristic and the homotopy cardinality involving summation of divergent series.

Posted by: David Corfield on March 8, 2023 7:47 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

October 11, 2006