Groupoid cardinality

November 8, 2012 by Qiaochu Yuan

Suitably nice groupoids have a numerical invariant attached to them called groupoid cardinality. Groupoid cardinality is closely related to Euler characteristic and can be thought of as providing a notion of integration on groupoids.

There are various situations in mathematics where computing the size of a set is difficult but where that set has a natural groupoid structure and computing its groupoid cardinality turns out to be easier and give a nicer answer. In such situations the groupoid cardinality is also known as “mass,” e.g. in the Smith-Minkowski-Siegel mass formula for lattices. There are related situations in mathematics where one needs to describe a reasonable probability distribution on some class of objects and groupoid cardinality turns out to give the correct such distribution, e.g. the Cohen-Lenstra heuristics for class groups. We will not discuss these situations, but they should be strong evidence that groupoid cardinality is a natural invariant to consider.

Axiomatics

For convenience, in this section we will restrict to essentially finite groupoids, namely those groupoids equivalent to groupoids with finitely many objects and morphisms.

Associated to any essentially finite groupoid $X$ is a rational number, its groupoid cardinality $\chi(X)$ , which is uniquely determined by the following four properties, analogous to the properties uniquely specifying Euler characteristic:

Cardinality: $\chi(\text{pt}) = 1$ , where $\text{pt}$ is the groupoid with one object and one morphism.
Homotopy invariance: If $X \sim Y$ ( $X$ is equivalent to $Y$ ), then $\chi(X) = \chi(Y)$ .
Gluing: $\chi(X \sqcup Y) = \chi(X) + \chi(Y)$ .
Covering: If $F : X \to Y$ is an $n$ -sheeted covering map, then $\chi(X) = n \chi(Y)$ .

A covering map of groupoids is a functor $F : X \to Y$ which is surjective on objects and which satisfies the unique path lifting property: if $p : y_1 \to y_2$ is a morphism in $Y$ and $x_1$ is an object in $X$ such that $F(x_1) = y_1$ , then there exists a unique morphism $p' : x_1 \to x_2$ in $X$ such that $F(p') = p$ . This axiomatizes the path lifting property satisfied by a covering map of topological spaces. A covering map is $n$ -sheeted if the preimage of every object in $Y$ consists of $n$ objects in $X$ .

The homotopy invariance and gluing axioms imply that groupoid cardinality is completely determined by how it behaves on one-object groupoids $BG$ , where $G$ is a finite group (since we are assuming essential finiteness). Associated to any such groupoid is a canonical $|G|$ -sheeted cover

$\displaystyle EG \to BG$

where $EG$ is the action groupoid for the action of $G$ on itself (the objects are the elements of $G$ and there is a unique morphism $g \to h$ between any pair of objects). This covering map sends the morphism $g \to h$ to the element $h g^{-1}$ of $G$ . The notation $EG$ is by strong analogy with the theory of classifying spaces.

Since $EG$ is equivalent to a point, $\chi(EG) = 1$ by the cardinality axiom, and the covering axiom then implies that $\chi(BG) = \frac{1}{|G|}$ . In conclusion, we find that if $X$ is an essentially finite groupoid then, writing the skeleton of $X$ as

$\displaystyle \bigsqcup_{x \in \pi_0(X)} B\text{Aut}(x)$

we have

$\displaystyle \chi(X) = \sum_{x \in \pi_0(X)} \frac{1}{|\text{Aut}(x)|}$ .

In words, the groupoid cardinality of $X$ is a weighted sum over the isomorphism classes of objects in $X$ , where an object is weighted by the size of its automorphism group. Intuitively speaking, we can think of the objects of $X$ as being “cut up” by their automorphism groups into fractional points.

Groupoid cardinality has other properties besides the above that make it a natural measure of the size of a groupoid.

Proposition: Let $X, Y$ be essentially finite groupoids. Then their product $X \times Y$ is also essentially finite, and $\chi(X \times Y) = \chi(X) \times \chi(Y)$ .

Proof. A groupoid is essentially finite if and only if it has finitely many isomorphism classes and the objects in each isomorphism class have finitely many automorphisms. This condition is preserved under finite products; moreover, if

$\displaystyle X \sim \bigsqcup_{x \in \pi_0(X)} B \text{Aut}(x)$

and

$\displaystyle Y \sim \bigsqcup_{y \in \pi_0(Y)} B \text{Aut}(y)$

then

$\displaystyle X \times Y \sim \bigsqcup_{(x, y) \in (\pi_0(X) \times \pi_0(Y))} B(\text{Aut}(x) \times \text{Aut}(y))$

which gives the desired result. $\Box$

Alternatively, one could show that $\frac{\chi(- \times Y)}{\chi(Y)}$ satisfied all of the axioms above.

Proposition: Let $S$ be a finite set and $G$ be a finite group acting on $S$ . Then the groupoid cardinality of the action groupoid or weak quotient $S//G$ is $\chi(S//G) = \frac{|S|}{|G|}$ .

Note that this is badly false for the set-theoretic quotient $S/G$ , a point which trips up many beginners in combinatorics.

The idea of the proof is that we would like to apply the covering axiom to the natural map $S \to S//G$ (thinking of $S$ as a discrete groupoid), except that this map isn’t a covering map unless the action of $G$ is free. However, it can be replaced by a covering map up to equivalence (a kind of fibrant replacement) essentially using the Borel construction.

Proof. Instead of considering $S$ , consider the equivalent groupoid $S \times EG$ , which consists of pairs $(s, g)$ where $s \in S, g \in G$ , and where there is a unique morphism $(s, g) \to (s, h)$ for every $g, h \in G$ . Since $G$ acts on both $S$ and $EG$ , it acts on this product, and so we can consider the action groupoid $(S \times EG)//G$ and the corresponding map

$\displaystyle S \times EG \to (S \times EG)//G$ .

Since $G$ acts freely on $S \times EG$ , this map is a $|G|$ -sheeted covering map. Moreover, $S \times EG \sim S$ and $(S \times EG)//G \sim S//G$ . We can now apply the covering axiom, and the conclusion follows. $\Box$

For a more pedestrian proof, observe that it suffices by the gluing axiom to prove the statement in the case that the action of $G$ on $S$ is transitive, where it reduces to the orbit-stabilizer theorem.

Digression: random finite sets

The definition of groupoid cardinality can be extended to tame groupoids, namely those groupoids $X$ such that the sum

$\displaystyle \sum_{x \in \pi_0(X)} \frac{1}{|\text{Aut}(x)|}$

converges. For any such groupoid, there is a natural probability measure on $\pi_0(X)$ given by the condition that a given isomorphism class $x \in \pi_0(X)$ occurs with probability

$\displaystyle \frac{1}{\chi(X)} \left( \frac{1}{|\text{Aut}(x)|} \right)$ .

For example, if $X = \text{core}(\text{FinSet})$ is the groupoid of finite sets and bijections, then

$\displaystyle \chi(X) = \sum_{n \ge 0} \frac{1}{n!} = e$

and the finite set of cardinality $n$ occurs with probability $\frac{1}{e n!}$ . In other words, “size of a random finite set” is Poisson with parameter $\lambda = 1$ . It is unclear to me what the significance of this observation is, if any.

More generally, let $s$ be a finite set and consider the groupoid of $s$ -colored finite sets. This is the groupoid whose objects are finite sets $x$ equipped with a map $x \to s$ (assigning to each element of $x$ its color) and whose morphisms are bijections $x_1 \to x_2$ compatible with colors. The cardinality of this groupoid may be computed in two ways. On the one hand, there are $s^n$ isomorphism types of objects where $|x| = n$ , and the groupoid consisting these isomorphism types is equivalent to the action groupoid of $S_n$ acting on the set of all functions from an $n$ -element set to $s$ , hence the groupoid cardinality is

$\displaystyle \sum_{n \ge 0} \frac{|s|^n}{n!}$ .

On the other hand, the groupoid of $s$ -colored finite sets is equivalent to the product of $|s|$ copies of the groupoid of finite sets; the equivalence is given by sending an $s$ -colored finite set to the finite sets given by the elements of each color. It is not hard to show that for tame groupoids we have $\chi(X \times Y) = \chi(X) \times \chi(Y)$ , hence the groupoid cardinality is

$\displaystyle \left( \sum_{n \ge 0} \frac{1}{n!} \right)^{|s|}$ .

Hence “size of a random $s$ -colored finite set” is Poisson with parameter $\lambda = |s|$ , and along the way to seeing this we have shown that two ways of defining $e^{|s|}$ give the same answer (and also implicitly given a combinatorial proof that $e^{|s| + |t|} = e^{|s|} e^{|t|}$ ).

There is much more to say about these kinds of arguments, much of which has been said by John Baez at some point, but I don’t know a place where all of the relevant links have been collected. One place to start and work backwards from is week300.

Groupoid cardinality and Euler characteristic

The axiomatic definition of groupoid cardinality suggests that it ought to behave like Euler characteristic, except that the Euler characteristic of familiar spaces are integers and groupoid cardinality is not an integer. However, there is a nice sense in which the Euler characteristic of $BG$ ought to be $\frac{1}{|G|}$ .

$BG$ is a groupoid model of a classifying space of $G$ , also denoted $BG$ , which for discrete groups has two equivalent definitions. It is the unique (up to homotopy) connected space such that $\pi_1(BG) = G$ and such that all higher homotopy groups are trivial; in other words, it is the Eilenberg-MacLane space $K(G, 1)$ . Such spaces are also known as aspherical spaces.

The classifying space $BG$ is also the space which represents, in a suitable homotopy category, the functor sending a topological space to its set of principal $G$ -bundles. When $G$ is a discrete group, this is the same thing as a $G$ -cover, but the definition in terms of bundles also generalizes to topological groups.

Example. $B\mathbb{Z}$ is the circle $S^1$ .

Example. More generally, a nice connected space $X$ is a $BG$ for $G = \pi_1(X)$ if and only if its universal cover is contractible; in particular any hyperbolic manifold has this property.

Example. $B\mathbb{Z}/2\mathbb{Z}$ is infinite real projective space $\mathbb{RP}^{\infty}$ .

The sense in which $\chi(BG)$ ought to be $\frac{1}{|G|}$ for $G$ finite is the following. Recall that if $X$ is, say, a finite CW complex, we should have

$\displaystyle \chi(X) = \sum_{i \ge 0} (-1)^i c_i$

where $c_i$ is the number of $i$ -cells of $X$ . There is a distinguished model of $BG$ (the space) having a cell decomposition in which $c_i = (|G| - 1)^i$ , and thus we ought to have

$\displaystyle \chi(BG) = \sum_{i \ge 0} (-1)^i (|G| - 1)^i = \frac{1}{1 + (|G| - 1)} = \frac{1}{|G|}$

by summing a divergent geometric series! I learned this from MO. This can be seen more explicitly for $\mathbb{RP}^{\infty}$ , for example, which has a single cell in each dimension and therefore whose Euler characteristic ought to be Grandi’s series

$\displaystyle \chi(\mathbb{RP}^{\infty}) = 1 - 1 + 1 \mp ... = \frac{1}{2}$ .

Posted in math.AT, math.CT | Tagged group actions, groupoids, MaBloWriMo | 10 Comments

10 Responses

on March 13, 2020 at 3:25 pm | Reply Combien il y a-t-il de nombres entiers naturels ? - Les carnets de Beussom

[…] blogs très sympas sur le sujet ici et […]
on September 2, 2017 at 8:14 pm | Reply The Groupoid Cardinality of Finite Semi-Simple Algebras | The Germs of Generality

[…] It is important to count only one object from each isomorphism class since we want the notion of groupoid cardinality to be invariant under equivalences of groupoids (in the sense of category theory) and every category is equivalent to it’s skeleton. For further motivation for the idea of a groupoid cardinality, see Qiaochu Yuan’s post on them […]
on April 13, 2017 at 5:08 pm | Reply Counting objects up to isomorphism: groupoid cardinality | What's new

[…] number of axioms such as these (similar to the axioms that determine Euler characteristic); see this blog post of Qiaochu Yuan for […]
on November 29, 2015 at 12:30 am | Reply Drawing subgroups of the modular group | Annoying Precision

[…] Euler characteristic, which in some sense generalizes both the usual Euler characteristic and groupoid cardinality. We will only compute this number for (classifying spaces of) finitely generated groups which are […]
on November 4, 2015 at 10:42 pm | Reply The categorical exponential formula | Annoying Precision

[…] prove and apply a version of the exponential formula that comes from relating (weighted) groupoid cardinalities of a groupoid and of the free symmetric monoidal groupoid on […]
on April 1, 2014 at 1:09 pm | Reply The free cocompletion I | Annoying Precision

[…] (thinking of taking coinvariants with respect to an -action as categorifying dividing by , in accordance with the general yoga of groupoid cardinality.) […]
on November 9, 2012 at 5:48 am | Reply JSE

Re the significance of the fact that the cardinality of a random finite set is Poisson with mean 1; there are lots of situations where some finite set of covers is NOT naturally a group, as in Cohen-Lenstra, but merely a finite set, and in cases like this you might naturally expect to find a Poisson distribution. E.G. in the paper of Dunfield and Thurston you find that set of Q-covers of a “random 3-manifold” in their model is a random finite set, when Q is a finite simple group. In the “Cohen-Lenstra” spirit one might guess along similar lines that if N is a random positive squarefree integer, the number of totally real quintic fields with discriminant N is distributed as Poisson with mean 1/120.

Re nice properties of groupoid uniform distribution — in my paper with Cais and Zureick-Brown we used this to make an argument that was really horrible nice and clean instead…

Also, see http://quomodocumque.wordpress.com/2008/11/26/tom-leinster-on-entropy-diversity-and-cardinality/
for a discussion of an application (by Leinster) to mathematical biology!
on November 9, 2012 at 5:01 am | Reply plm

Thanks.

So is there a good reference for what the “right” Euler characteristic of a space should be? One that gives consistent results in all situations. Or a reasoned classification of possible Euler characteristics?
- on November 9, 2012 at 10:35 am | Reply Qiaochu Yuan
  
  I don’t know. Even for, say, nice noncompact smooth manifolds there are at least two reasonable notions of Euler characteristic, namely the ordinary one coming from singular or de Rham cohomology and compactly supported Euler characteristic, coming from compactly supported de Rham cohomology. The latter is not invariant up to homotopy (but is invariant up to proper homotopy?) but satisfies the correct gluing laws (e.g. I think $(0, 1)$ has compactly supported Euler characteristic $-1$ instead of $1$ and this is compatible with the decomposition of $S^1$ into $(0, 1)$ and a point).
  - on November 9, 2012 at 6:22 pm | Reply plm
    
    Thanks for the example.
    A few remarks, not very interesting:
    For algebraic varieties I found this paper
    
    Click to access Euler.pdf
    
    about Euler characteristics, which mentions another reasonable characteristic, defined from intersection homology. Then I remembered that (Euler) characteristics are more generally any homomorphism between K-groups or K-rings, or at least with one K-group as target or domain, and usually with a more complicated domain, perhaps geometric (manifolds, varieties, etc.), and a simpler more linear target -the usual Euler characteristic is to K(N). This includes (Lang’s?) definition of Euler-Poincaré mapping with K_0 of the category of modules as domain. So I guess Euler characteristics should probably be seen as available in a variety of flavors: depending on what we study, what we want them to retain or forget (in the case of the interval, that it is contractible, or that it has 1 point compactification the circle).

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos

Recent Comments

Blogroll

Categories

Archives

Tag Cloud

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos