Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 9, 2007

Return of the Euler Characteristic of a Category

Posted by David Corfield

Tom Leinster has a follow up to The Euler characteristic of a category, which sparked a lively conversation here last October. The new one goes by the title The Euler characteristic of a category as the sum of a divergent series.

Abstract:

The Euler characteristic of a cell complex is often thought of as the alternating sum of the number of cells of each dimension. When the complex is infinite, the sum diverges. Nevertheless, it can sometimes be evaluated; in particular, this is possible when the complex is the nerve of a finite category. This provides an alternative definition of the Euler characteristic of a category, which is in many cases equivalent to the original one

Posted at July 9, 2007 9:30 AM UTC

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

33 Comments & 4 Trackbacks

Re: Return of the Euler Characteristic of a Category

When my previous paper came out, someone here asked me to write a short summary. Toby beat me to it, so I’ll summarize this one instead.

Given a simplicial set XX, you’d like to say that the Euler characteristic of XX is c 0c 1+c 2, c_0 - c_1 + c_2 - \cdots, where c nc_n is the number of nondegenerate nn-simplices (which I’m assuming to be finite). Usually this series is divergent. Nevertheless, you can try to sum it in the following way. Consider the power series f X(t)=c nt nf_X(t) = \sum c_n t^n. If you’re really lucky, this series converges in some neighbourhood of 00 and has a unique analytic continuation to 1-1, and you could then declare the Euler characteristic of XX to be the value at 1-1 of this analytic continuation.

In particular, you can try this strategy on the nerve XX of any finite category, since this has only finitely many simplices of each dimension.

All of this so far was a suggestion of Clemens Berger. As it turns out, it was an excellent suggestion. What happens is this: if XX is the nerve of a finite category then f X(t)f_X(t) is in fact a rational function, whose value at 1-1 (if finite) I call the series Euler characteristic of the category. And in many cases - perhaps the most interesting cases - this is equal to the Euler characteristic in my previous sense.

Two problems, though. First, series Euler characteristic isn’t invariant under equivalence! Second, there are examples of categories whose Euler characteristic and series Euler characteristic are different. (This follows from the first point, since the original Euler characteristic is invariant under equivalence.) So personally, I still prefer the original definition.

Posted by: Tom Leinster on July 9, 2007 8:06 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

When the Euler characteristic and series Euler characteristic differ, is it possibly to find an equivalent category where they agree? If so, might it be possible to say why that choice was ‘good’?

Posted by: David Corfield on July 10, 2007 9:53 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

I don’t know. My guess is that there are examples where it’s not possible.

By the way, I made a mistake in the last paragraph of my previous post: you should ignore the bit in brackets. (But there are no mistakes in the paper, as far as I know.)

Posted by: Tom Leinster on July 10, 2007 7:50 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

Nice summary!

First, series Euler characteristic isn’t invariant under equivalence! Second, there are examples of categories whose Euler characteristic and series Euler characteristic are different. (This follows from the first point, since the original Euler characteristic is invariant under equivalence.) So personally, I still prefer the original definition.

Which is easier to compute? I can imagine mechanically computing the series Euler characteristic, but I’m not sure how mechanically one can find those weightings and coweightings.

I’m also curious how new definition relates to Tim Silverman’s method of generalizing your earlier Euler characteristic to finitely generated (but infinite) categories. Both methods involve Abel summation — that trick of summing a nt n\sum a_n t^n and then analytically continuing. Your method attaches a power of t nt^n to an nn-simplex in the nerve, while his attaches it to a 1-morphism that’s a product of nn generators. But those are closely related things, since a composable string of nn 1-morphisms gives an nn-simplex in the nerve.

Posted by: John Baez on July 10, 2007 9:54 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

John wrote:

Which is easier to compute?

The (original) Euler characteristic, by far. At least, that’s the case with the computational methods that I know.

Let’s look at the necessary computations for both invariants. Take a finite category. To calculate both its EC and its series EC, we use the matrix ZZ of cardinalities of hom-sets.

To calculate the Euler characteristic, we have to find a weighting; the Euler characteristic is then the sum of its entries. Recall that a weighting for the category is a column vector ww solving the equation Zw=e Z w = e where ee is the column vector (1,,1)(1, \ldots, 1). So to find one is a routine piece of Gaussian elimination. (I’m assuming that AA does have Euler characteristic; to check that it does requires work of no greater complexity.)

However, to calculate the series Euler characteristic requires (to my knowledge) work of the same kind of complexity as calculating determinants. Details are at the bottom of p.6 of my paper. Thus, it rapidly gets more expensive as the size of the matrix - which is the number of objects in the category - grows.

I do actually have some practical experience of this. To find all those counterexamples in the paper, I computed the series Euler characteristics of dozens of 22-, 33- and 44-object categories. This took a great deal of computation time. As you can deduce from that last sentence, I did it all by hand (to the mirth of certain colleagues). For 44 objects, i.e. 4×44 \times 4 matrices, I reckon that the series Euler characteristic would take me about twenty minutes to calculate, but ordinary Euler characteristic only about five.

On the other matter, I want to look again at what Tim wrote. One terminological thing first, though. While I was writing the new paper, I did some searching around to see if this method of summation via analytic continuation had a name. To my surprise, I couldn’t find one. You call it Abel summation, but my impression had been that this was used rather more restrictively, e.g. as on p.49 of Cartier’s Mathemagics. Do other people use the term in as general a way as you do?

Posted by: Tom Leinster on July 10, 2007 8:24 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

Tom wrote:

I do actually have some practical experience of this.

Yes, I could tell.

As you can deduce from that last sentence, I did it all by hand (to the mirth of certain colleagues).

(This emoticon denotes ‘rolling on the floor with laughter’.)

You call it Abel summation, but my impression had been that this was used rather more restrictively…

Yeah, sorry — I often feel guilty about stretching the usage this way.

Abel summation usually refers to the case where a nz n\sum a_n z^n converge for all |z|<1|z| \lt 1 and lim z1a nz n \lim_{z \uparrow 1} \sum a_n z^n exists. Lots of nice theorems apply only to this case. I don’t know a name for the generalization where a nz n\sum a_n z^n converges in small disk around the origin and admits a unique analytic continuation to the point z=1z = 1 — even though this is an important trick!

By the way, it gets even more subtle when a nz n\sum a_n z^n converges in small disk around the origin and admits a nonunique analytic continuation to the point z=1z = 1, due to branch points. A classic case here is ‘the cardinality of the set of planar rooted binary trees’.

You know this well, but I can never resist retelling a good joke. So: we take the sum of Catalan numbers:

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

regularize it by sticking in powers of zz:

z+z 2+2z 3+5z 4+14z 5+42z 6+ z + z^2 + 2z^3 + 5z^4 + 14z^5 + 42z^6 + \cdots

cleverly notice that this converges to

114z2 \frac{1 - \sqrt{1 - 4z}}{2}

for |z|<1/4|z| \lt 1/4, but then dodge the branch point at z=1/4z = 1/4 and analytically continue to z=1z = 1, getting a non-unique answer:

1±32. {1 \pm \sqrt{-3} \over 2}.

What fascinates me about this is the obvious relation to Galois theory: branched covers, Galois groups and the like! Somehow the number of trees has a ‘hidden symmetry’: the Galois group \mathbb{Z}/2.

Instead of ‘number of trees’, I should really say ‘set of trees’, or better yet, the ‘species of trees’ defined recursively by

T=z+T 2T = z + T^2

You can see that somehow the T 2T^2 in the above equation gives rise to the branched double covering in the Riemann surface for

T(z)=1±14z2T(z) = \frac{1 \pm \sqrt{1 - 4z}}{2}

This is what gives the Galois group /2\mathbb{Z}/2. But is this /2\mathbb{Z}/2 really just coming directly from the ability to switch the two trees that sit inside this tree?

  -----   -----
 |     | |     |
 |  T  | |  T  |
 |     | |     |
  -----   -----
    \      /
     \    /
      \  /
       \/

It seems that it is! But can we go further and understand situations where the Galois group is something much more interesting?

I’ve been trying to get someone to work on this for a long time — but it doesn’t seem to be happening, and it never quite rises to the top of my stack. So, I’ll just throw the problem out here, and hope someone grabs it and solve it!

Posted by: John Baez on July 11, 2007 11:03 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

I don’t know, the youth of today! What would they rather do than carry on this project?

We figured out how to categorify the algebraic integers in any algebraic extension of the rationals, getting an “algebraic extension” of the category of finite sets. We figured out the beginnings of a theory that associates a “Galois 2-group” to any such algebraic extension.

Posted by: David Corfield on July 11, 2007 12:03 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

I’m not “youth”, but I did think about this for a day or two a few weeks ago. But, insofar as I’m working on anything, I’d rather spend time on 2-Galois groups (and their 2-reps) for the case of coverings of 2-graphs and their deck transformations.

Posted by: Tim Silverman on July 11, 2007 12:37 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

…coverings of 2-graphs and their deck transformations.

2-graph as in Two-graph?

Posted by: David Corfield on July 11, 2007 4:25 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

No, nothing so interesting. Digraphs with oriented faces.

Posted by: Tim Silverman on July 11, 2007 4:51 PM | Permalink | Reply to this

Overcoming divergence

You guys who post comments to two or three different threads on the same day - I don’t know how you do it. I’ve been spending the last few days thinking about John’s suggestion that there might be a connection between the methods in my paper and a couple of Tim Silverman’s posts (1, 2). In fact, I still haven’t made it onto Tim’s second post (possibly the longest comment that the n-Café has ever seen!). And I still don’t really know what the connection is. Anyway, here are my thoughts.

In what Tim wrote, the following question is implicit:

Q. What’s the cardinality of a sequence Y=(Y 0,Y 1,)Y = (Y_0, Y_1, \ldots) of finite sets?

You could say it’s |Y n|\sum |Y_n| - but however good you might be at summing divergent series, there are always going to be some awkward customers that resist being summed. You could say that it’s the sequence (|Y 0|,|Y 1|,)(|Y_0|, |Y_1|, \ldots). As I’ll explain (see the Challenge in my next comment), I think that the right answer is neither of these.

On the other hand, my paper contains the following question:

Q. What’s the cardinality of a simplicial set XX with only finitely many simplices of each dimension?

You might want to say - and in the paper, I do! - that it’s (1) n|X n nd|\sum (-1)^n |X^{nd}_n|, where X n ndX^{nd}_n is the number of nondegenerate nn-simplices. Again, you have the problem that this usually can’t be summed in any sensible way.

There are some obvious similarities between the two questions. A simplicial set has, of course, an underlying sequence of sets. But when it comes to taking the cardinality (a.k.a. Euler characteristic), you mustn’t ignore the simplicial structure: that would be like defining the Euler characteristic of a topological space to be the cardinality of its set of points. That’s why we had an ordinary sum |Y n|\sum |Y_n| in one context and an alternating sum (1) n|X n nd|\sum (-1)^n |X^{nd}_n| in the other.

I want to make some comments about the first question. I’ll begin by revisiting a result of Tim’s.

The original definition of Euler characteristic (== cardinality) of a category assumed that the category was finite, and in particular had finite homsets. It’s not clear what to do with a category with infinite homsets, because we need to take the cardinality of each homset, and the things we need to do with those cardinalities don’t seem to work well with infinite cardinals.

An example of a category with finitely many objects but infinite homsets is the free category F(G)F(G) on a finite directed graph GG. Tim observed that although the homsets of F(G)F(G) are infinite sets, these sets are not just bags of indistinguishable elements - they have some structure. Precisely, each homset in F(G)F(G) is graded by length, and the part in each degree is finite. In other words, F(G)F(G) is really an infinite sequence of finite sets.

Let’s pause for a moment to ‘recall’ that if VV is a monoidal category and we already have a sensible notion of cardinality of objects of VV, then it’s possible to talk about the cardinality of a finite VV-enriched category. (Simply take the definition of Euler characteristic of an ordinary category and replace finite sets by objects of VV.) In particular, we can do this when V=FinSet V = FinSet^{\mathbb{N}}, with the convolution tensor product, declaring the cardinality of YFinSet Y \in FinSet^\mathbb{N} to be the formal power series n|Y n|t n[[t]]. \sum_n |Y_n| t^n \in \mathbb{Q}[[t]]. Let AA be a finite FinSet FinSet^\mathbb{N}-enriched category. We have the matrix ζ A\zeta_A of cardinalities of homsets, with entries in [[t]]\mathbb{Q}[[t]]. With luck, ζ A\zeta_A has an inverse μ A\mu_A, and in that case, the cardinality of AA is the sum of the entries of μ A\mu_A. Thus |A|[[t]]|A| \in \mathbb{Q}[[t]]. You can then try your hand at evaluating this formal power series at t=1t = 1 to obtain an actual number.

Now here’s Tim’s result. Take a finite directed graph GG with g 0g_0 vertices and g 1g_1 edges. Write γ\gamma for the ‘incidence’ matrix of GG, that is, the g 0×g 0g_0 \times g_0 matrix over \mathbb{N} whose (i,j)(i, j)-entry is the number of edges from the iith object to the jjth object. Let F(G)F(G) be the free category on GG, regarded as a FinSet FinSet^\mathbb{N}-enriched category as above. Then ζ F(G)(t)=1+γt+γ 2t 2+, \zeta_{F(G)}(t) = 1 + \gamma t + \gamma^2 t^2 + \cdots, (a matrix over [[t]]\mathbb{Q}[[t]]), which has inverse μ F(G)(t)=1γt. \mu_{F(G)}(t) = 1 - \gamma t. The sum of the entries of the identity matrix 11 is g 0g_0, and the sum of the entries of γ\gamma is g 1g_1, so |F(G)|=g 0g 1t[[t]]. |F(G)| = g_0 - g_1 t \in \mathbb{Q}[[t]]. But this is a mere polynomial over \mathbb{Q}, so it can certainly be evaluated at t=1t = 1, giving an answer of g 0g 1g_0 - g_1. And this is the Euler characteristic of GG itself.

Ta-dah!

But there’s a fly in the ointment (or sand in the vaseline). I’ve been flitting between two different opinions on what type of thing the cardinality of a sequence of finite sets should be - one moment I’m saying it should be a sequence of numbers (or equivalently, a formal power series), and the next I’m saying that it should be a single number. I’ll suggest how to remove the fly/sand in my next comment.

Posted by: Tom Leinster on July 16, 2007 9:06 PM | Permalink | Reply to this

What’s the cardinality of a sequence of finite sets?

For various reasons (some mentioned in my previous comment, some not), I want to issue a challenge. First let me set the scene.

We’re interested in defining the ‘cardinality’ of objects of various kinds. Ultimately it would be good to have a general definition of the cardinality of objects of any kind, but let’s put that ambition on hold. Given a new type of object for which one would like a definition of cardinality, one can apply the following

General Principle: Don’t try to define the cardinality of an object. Instead, say when two objects have the same cardinality.

To see how this works, suppose you’ve come up with a good equivalence relation \sim, ‘has the same cardinality as’, on the collection of objects. Then the cardinality of an object is simply its equivalence class, and you might call {objects}/\{ objects \} / \sim the collection of cardinals.

Very often the collection of objects has some structure - for instance, they might be the objects of a rig category. If \sim respects that structure then the cardinals inherit the structure too - in this case, they’d form a rig.

(It might be that there’s a further map from the rig of cardinals to some familiar rig such as \mathbb{Z} or \mathbb{C}, or even an isomorphism - but if so, that’s a bonus feature of the particular type of object you’re considering, and not part of the general procedure.)

A simple and familiar example is (possibly infinite) sets. It’s easy to decide when two sets have the same cardinality: \sim is isomorphism. Because sets form a rig category, cardinals form a rig.

A more sophisticated example is Schanuel’s Euler characteristic of a polyhedral set, in his ‘Negative sets…’ paper.

A non-example is my work on Euler characteristic of categories! That’s why there’s this unattractive business of Euler characteristic being undefined for some categories. It would be great if someone could find an approach that conforms to the General Principle.

Now: I’d like to define the cardinality of a sequence of finite sets in a way that follows the General Principle. In other words, I’d like to decide when two sequences of finite sets should have the same cardinality. This is easier said than done, and leads to the following challenge.

Terminology: call a sequence a=(a n) na = (a_n)_{n \in \mathbb{N}} of natural numbers summable if a n=0a_n = 0 for all but finitely many values of nn.

Challenge: Find an equivalence relation \sim on the set \mathbb{N}^\mathbb{N} of sequences of natural numbers such that

  • if aa and bb are summable then a n=b n\sum a_n = \sum b_n iff aba \sim b
  • if aaa \sim a' and bbb \sim b' then a+ba+ba + b \sim a' + b'.

The idea is that the cardinality of a sequence (X n)(X_n) of finite sets would then be the equivalence class of (|X n|) n(|X_n|)_{n \in \mathbb{N}} in /\mathbb{N}^\mathbb{N}/\sim.

I probably haven’t succeeded in asking exactly the right question. (If I knew the right question, I’d be halfway to the right answer.) For example, there might be some unhelpful solution to the Challenge involving the Axiom of Choice. A satisfactory solution is meant to give us the right notion of cardinality of a sequence of finite sets.

There are many variants of the Challenge. Some might be easier. For example, you could replace sequences of natural numbers by sequences of complex numbers. And you could then replace ‘summability’ by any of the following:

  • Absolute convergence (of the series a n\sum a_n)
  • Convergence
  • ‘Continuation summability’, i.e. summability by the method of analytic continuation discussed at the beginning of this thread
  • ‘Eulerian summability’, i.e. summability by the sort of magic that Euler used. For example, by trusting his pen, Euler found that 1+1+1+=1/2 1 + 1 + 1 + \cdots = -1/2 and 1+2+3+=1/12, 1 + 2 + 3 + \cdots = -1/12, both of which were later confirmed by Riemann: his zeta function satisfies ζ(0)=1/2\zeta(0) = -1/2 and ζ(1)=1/12\zeta(-1) = -1/12.

You can also add to the list of conditions that \sim should satisfy. For instance, you might want to include:

  • Invariance under some group of permutations of \mathbb{N} (permuting the sequence should perhaps leave the sum unchanged)
  • Invariance under right-shift: (a 0,a 1,)(0,a 0,a 1,)(a_0, a_1, \ldots) \sim (0, a_0, a_1, \ldots)
  • Invariance under grouping, e.g. a(a 0+a 1,0,a 2+a 3+a 4,)a \sim (a_0 + a_1, 0, a_2 + a_3 + a_4, \ldots)
  • Multiplicativity: if aaa \sim a' and bbb \sim b' then aabba \cdot a' \sim b \cdot b', where \cdot is convolution product.

I should maybe point out that some of these conditions are incompatible with some of the types of summability. For example, if you want invariance under all permutations of \mathbb{N} then you have to stick to absolute convergence. If you want invariance under grouping then you’d better not use continuation summability: for that method gives 11+11+=1/2 1 - 1 + 1 - 1 + \cdots = 1/2 (because 1x+x 2=1/(1+x)1 - x + x^2 - \cdots = 1/(1 + x)), whereas grouping as (11)+(11)+ (1 - 1) + (1 - 1) + \cdots gives an answer of 00. If you want multiplicativity then you can’t use Eulerian summability, since we have a convolution (1,1,1,)(1,1,1,)=(1,2,3,) (1, 1, 1, \ldots ) \cdot (1, 1, 1, \ldots) = (1, 2, 3, \ldots) but (1+1+1+)(1+1+1+)=(1/2)(1/2)1/12=1+2+3+. (1 + 1 + 1 + \cdots ) \cdot (1 + 1 + 1 + \cdots ) = (-1/2)(-1/2) \neq -1/12 = 1 + 2 + 3 + \cdots.

I’d be very happy to see a solution to any version of the Challenge!

Posted by: Tom Leinster on July 16, 2007 9:19 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

You can’t even be sure about 1 + 1 + 1 + … . It seems to depend on where it comes from.

Posted by: David Corfield on July 16, 2007 10:06 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Couldn’t you just take Z^N and quotient out by the subgroup of summable sequences whose sum is 0? If you’re really interested in positivity, then you could look at the image of N^N in this group, or rather the corresponding equivalence relation. Equivalently, a and b are equivalent if their difference is a summable sequence of sum zero. (I hope I understand you correctly…)

Posted by: James on July 16, 2007 11:29 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

David: yes, agreed. This is the trickiest kind of sum: of all the methods above, 1+1+1 + 1 + \cdots is only amenable to ‘Eulerian summability’, i.e. summability by black magic. I don’t know what more to say.

James: again, agreed. Absolutely. Despite lengthy thought, I haven’t been able to find exactly the right question to ask.

Looking at the spirit rather than the letter of the challenge, I don’t think your answer is going to give that useful a notion of cardinality of a sequence of finite sets. For instance, since 2+2x+4x 2+8x 3+=1+112x, 2 + 2x + 4x^2 + 8x^3 + \cdots = 1 + \frac{1}{1 - 2x}, it would be good to be able to say that 2+2+4+8+=0 2 + 2 + 4 + 8 + \cdots = 0 (an instance of ‘continuation summability’), and so (2,2,4,8,)(0,0,0,0,). (2, 2, 4, 8, \ldots) \sim (0, 0, 0, 0, \ldots). This means that a sequence of finite sets with respective cardinalities 2,2,4,8,2, 2, 4, 8, \ldots is supposed to have cardinality 00.

Fine - but you could now update your suggestion by simply changing ‘summable’ to ‘continuation-summable’. And again, that would be perfectly correct. It might even be exactly the equivalence relation I’m looking for - it’s just not presented in a way that makes that obvious.

Let me have another try at expressing what I’m after.

Among all sequences of natural numbers (or integers, or whatever), there is a subset consisting of the summable sequences (in whatever sense you please). We know what the equivalence relation should be when restricted to this subset. As you point out, there’s a trivial way of taking this equivalence relation and extending it to the whole set.

What I don’t like about this is that it makes a special case of the summable sequences. In other words, it splits \mathbb{N}^\mathbb{N} into two parts - the summable sequences and the non-summable sequences - and it treats them differently. I’d like something uniform.

It also goes against the General Principle above. This dictates that whatever the answer to the challenge is, it shouldn’t mention sums. Much as I don’t want to poison anyone’s mind with my own failed attempts, maybe I should give an example of what a satisfactory answer might look like: it might, for instance, say that \sim is the equivalence relation generated by some subset of the invariance conditions that I listed, together with respecting addition and maybe multiplication.

Of course, it may be that the reason why I seem to be incapable of formulating a question that stands a chance of having a sensible answer is that there is no sensible answer. Perhaps I’m barking up the wrong tree. But if there is a canonical notion of the cardinality of a sequence of finite sets, then there surely is a canonical answer.

Posted by: Tom Leinster on July 17, 2007 1:47 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

OK. I don’t have anything intelligent to say, so instead I’ll just repeat some number-theoretic wisdom on the off chance that you’ll find it useful.

First is that the sequence 2+2+4+8+… does converge to 0 in the 2-adic topology. In fact any geometric series converges to what you’d naively hope in either the real topology or in some p-adic topology, except 1+1+… and 1-1+1-1+…. Second, from the number-theoretic perspective, it’s unnatural to prefer the real numbers to the p-adic numbers, so I wouldn’t be very happy if you require your sums to take real or complex values, though I admit your General Principle steps around this issue.

What if we take my example and quotient out by additional relations saying that every geometric series is equivalent to what you’d naively hope its sum would be. (I guess we’d have to use sequences of rational numbers.) It looks like this would pass the next test you gave. Can you think of another test that it would fail?

I’m just hoping to get you to divulge as many secret requirements on your desired equivalence relation as possible, since I haven’t really been following the spirit of the problem.

Posted by: James on July 17, 2007 10:16 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Ah, so it looks like you are the James I suspected you were :-)

Thanks for the observations about pp-adic convergence. As you say, the General Principle is intended to separate out the general (categorical) considerations from algebraic considerations, so we don’t actually need to decide where cardinality is going to take values. Nevertheless, it might be useful to know something about what rigs you could map into.

As I should have said in my original comment, given any list of requirements on \sim, you can simply take the smallest equivalence relation satisfying them all. I now add the following half-precise requirement for a solution: that in defining \sim, you’re not allowed to use the word ‘sum’. (Or any synonyms, of course.)

Now that you’re making me divulge my secret assumptions, I see how ill-defined they are…

Posted by: Tom Leinster on July 17, 2007 12:26 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Have you been talking with a certain well-known gossip again? Or maybe the key clue was admitting that I had nothing intelligent to say…

Hi Tom. (I’m assuming you’re the Tom Leinster I suspect you are, but I could be looking for lost keys under the streetlight again.)

Back to your question, do you know how to define your equivalence relation on the set of summable sequences without using the word ‘sum’? I guess you could say it’s the equivalence relation generated by moving +1 between adjacent terms in your sequence. Or do you have something better in mind?

I have to say I’m not too optimistic of getting a good equivalence relation in general, but the payoff would be so high that it I think it’s worth pursuing.

Posted by: James on July 18, 2007 12:15 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

I’ve been talking to no one! Just cooped up in my garret, asking questions with trivial answers.

Just shifting 1’s about will work for the simplest form of the challenge. Life becomes more interesting when you try to handle continuation summability, or even just the restricted form of it that you get by regarding the rings of rational functions and power series as both embedded in the field of Laurent series (so that you can speak of a power series ‘being rational’). I don’t know what to do then.

Posted by: Tom Leinster on July 18, 2007 2:11 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Tom, would you be able to come up with a reason why you don’t want to use the word ‘sum’? I usually think of summing as one of the most innocuous things in all of maths. Subtraction, division, and even multiplication are sometimes bad, but finite sums?

Posted by: James on July 19, 2007 8:36 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

My bad (again). I only wanted to exclude infinite sums, not finite ones.

Posted by: Tom Leinster on July 19, 2007 5:39 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Oh, I should have realized that that’s what you meant. But I have the same question about infinite sums. Do you not like them because, something like, you evaluate them using analytic means and you don’t think that’s a fundamental thing? Or do you have another reason?

For example, suppose I model the ring Q[[t]]Q[[t]] of power series with coefficients in QQ by just sequences in QQ equipped with a shift endomorphism tt. So the series 1+2t+4t 2+1+2t+4t^2+\dots would correspond to the sequence 1,2,4,1,2,4,\dots. Let xx denote this sequence. Then we have 2tx+1=x2 t x+1 = x, where we view a rational number rr as the sequence r,0,0,r,0,0,\dots. Let VV denote the set of sequences, and let U=V/(tid)U=V/(t-id). Then in UU, we have x=1x=-1. In other words, 1=1+2+4+-1 = 1+2+4+\dots.

How does that do by your secret requirements?

  1. You like it because you don’t need analysis or infinite sums to say when two series are equal at 1.

  2. You don’t like it because it is obviously the same thing as doing an infinite sum in some sense, so your objection probably applies to more things than just infinite sums (in which case you should tell me).

  3. You don’t like it because you ought to be able to multiply cardinalities of sequences and the ideal generated by t1t-1 is the whole ring. (In which case I need to think harder.)

  4. There is a new secret reason why you don’t like it.

  5. Something else I haven’t thought of.

By the way, is there any evidence that there actually is a good notion of two series having the same cardinality, or is it just a dream?

Posted by: James on July 20, 2007 11:09 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Tom wrote:

… there might be some unhelpful solution to the Challenge involving the Axiom of Choice.

Speaking of this, Terry Tao has a really nice explanation of ultrafilters as methods for taking limits of arbitrary bounded sequences, which then goes on to explain what all this has to do with nonstandard analysis. While ultrafilters require the axiom of choice, it’s still fun reading — and it contains a list of desiderata a bit like yours.

I especially like the ‘voting’ metaphor.

Posted by: John Baez on July 18, 2007 12:30 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Tom wrote:

Multiplicativity:ifa~aandb~bthenaa~bb,whereisconvolutionproduct.\bullet Multiplicativity: if a~a' and b~b' then a\cdot a'~b\cdot b', where \cdot is convolution product.

Did you really mean

Ifa~aandb~bthenab~ab?If a~a' and b~b' then a\cdot b~a'\cdot b'?

Another possible desideratum is, if we have a notion of a limit of a series of sequences, then the equivalence should respect that:

If a i~b ia_i ~ b_i and a iaa_i\rightarrow a, b ibb_i\rightarrow b, then a~ba~b. Presumably we’ll need to be careful what sort of convergence we pick. Something where the sums of the individual sequences converge to a limit, which is the sum of the limit sequence.

For the very little that it’s worth, I have an uneasy feeling about this challenge (apart from it just being difficult). Something about it makes me feel that it would be very surprising for there to be a unique extension from summable sequences to all sequences. But I can’t put my finger on what exactly my feeling is coming from. Something about divergent sequences being too big/random/numerous/pregnant with possibilities to meekly fit into one box. But that’s just a vague feeling, so not much use at the moment.

In other words, I too have nothing intelligent to say. But I am watching this space carefully.

Posted by: Tim Silverman on July 18, 2007 1:51 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

There are continuous linear functionals on the space of all bounded sequences that agree with the usual limit on those sequences that have limits.

You can get such functionals to take positive values on positive sequences. You can also get them to be shift-invariant!

Such functionals are called Banach limits.

But, to prove Banach limits exist, people use the Hahn-Banach theorem or ultrafilters — both of which require some version of the axiom of choice. So, I bet some version of choice is needed to get Banach limits.

Now I’m talking about limits instead of sums, and I’m only talking about bounded sequences. But still, I’m I think what I’m saying is related to your feeling that sequences are

too big/random/numerous/pregnant with possibilities to meekly fit into one box.

It’s also very related to Terry Tao’s stuff on ultrafilters.

Posted by: John Baez on July 18, 2007 3:30 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Talking of boxes, to return to Cartier’s example, I still don’t see how anyone’ll get round the problem that the number of ways to put no things in at least nn boxes, depends on nn (it’s 1/2n1/2 - n), yet for any nn this is an interpretation of 1+1+1+...1 + 1 + 1 + ....

Posted by: David Corfield on July 18, 2007 3:42 PM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Thanks! I think it may be the combination of the use of the axiom of choice (which doesn’t usually make me queasy) with the fact that Banach limits are not uniquely determined on all sequences. In fact, mostly the latter. Trying to include unbounded sequences can only make things worse, I’d imagine.

Restricting to sums whose initial partial sums are bounded would make the problems more similar, but, just glancing through Tom’s examples, we can see that don’t want to restrict to this case!

But maybe we can still get a nice categorical account by acknowledging that we have to make some arbitrary choices at the start, and then just looking for generic structures in the result that are independent of the particular choices.

Posted by: Tim Silverman on July 19, 2007 11:59 AM | Permalink | Reply to this

Re: What’s the cardinality of a sequence of finite sets?

Apologies for writing such ill-focussed things in this thread. I appreciate people’s help in bringing the problem into focus.

I’ve just come across this interesting paper by V.S. Varadarajan in the Bulletin of the AMS. (The link may expire in a while; it’s called “Euler and his work on infinite series”.) Section 3 is on Euler’s work on “summing” divergent series. The long quotation from Euler on p.12-13 is especially good, and highly relevant to this question of the cardinality/Euler characteristic of a sequence of finite sets.

Posted by: Tom Leinster on July 19, 2007 1:15 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

A closely related conversation is going on at the Everything Seminar (one for the links list, Café owners?).

Posted by: Tom Leinster on August 2, 2007 8:04 PM | Permalink | Reply to this
Read the post BV-Formalism, Part IV
Weblog: The n-Category Café
Excerpt: Lie algebroids of action groupoids and their relation to BRST formalism.
Tracked: October 11, 2007 9:47 PM
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:33 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:03 AM

Re: Return of the Euler Characteristic of a Category

Jim Stasheff kindly forwarded the following to me, which I’ll just reproduce here without having followed the references myself for the moment in order not to forget it and to come back to it later:

[Somebody is] thinking about what might be needed to make sense of integrating over a category for purposes of counting. Rob and Yuliy Baryshnikov have some nice papers on ‘counting’ essentially using a measure arising from an Euler characteristic.

My belief is that this fits very well in a categorical framework. One could form a kind of Euler-Poincare’ series with sufficient finiteness conditions. If the series converged at t=1t = -1, then that would give an analogue of the Euler characteritsitc.

Posted by: Urs Schreiber on July 20, 2008 8:27 PM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

It looks like you meant Rob Ghrist. Here’s a paper he wrote with Baryshnikov. Ghrist’s preprints.

Posted by: David Corfield on July 21, 2008 9:02 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

Thanks. This is not anything going beyond what Tom Leinster discusses, as far as measuring categories is concerned, is it?

Posted by: Urs Schreiber on July 21, 2008 11:12 AM | Permalink | Reply to this

Re: Return of the Euler Characteristic of a Category

Jim Propp writes a note on Euler integration here.

Posted by: David Corfield on July 21, 2008 11:55 AM | 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 3:58 PM

Post a New Comment