Skip to main content
edited body
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

This is one way to motivate the following definition. Let $G$$X$ be a groupoid all of whose objects have a finite automorphism group which is tame in the sense that the sum

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

converges (where $\pi_0(G)$$\pi_0(X)$ is the set of isomorphism classes of objects of $X$). The above sum is called the groupoid cardinality of $G$$X$, and it induces a natural probability measure on $\pi_0(G)$$\pi_0(X)$ where an isomorphism class $x$ occurs with probability inversely proportional to $\text{Aut}(x)$.

Example. Let $X$ be a finite set on which a finite group $G$ acts. Form the action groupoid, whose objects are the elements of $X$ and which has a morphism $s_1 \to s_2$ labeled by $g \in G$ whenever $gs_1 = s_2$. Then the groupoid cardinality of the action groupoid is

$$\sum_{x \in \pi_0(X)} \frac{1}{|\text{Stab}(x)|} = \frac{|S|}{|G|}$$

and the induced probability measure on $\pi_0(X)$ is the one we considered above.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For further discussion of the naturality of groupoid cardinality see this blog post.

Example. Let $X$ be a finite set on which a finite group $G$ acts. Form the action groupoid, whose objects are the elements of $X$ and which has a morphism $s_1 \to s_2$ labeled by $g \in G$ whenever $gs_1 = s_2$. Then the groupoid cardinality of the action groupoid is

$$\sum_{x \in \pi_0(X)} \frac{1}{|\text{Stab}(x)|} = \frac{|S|}{|G|}$$

and the induced probability measure on $\pi_0(X)$ is the one we considered above.

Example. Let $G$ beConsider the groupoid of finite sets and bijections. Its groupoid cardinality is

With respect to the corresponding probability measure, a random finite set $S$ occurs with probability $\frac{1}{e |S|!}$. The distribution of cardinalities youwe get this way is Poisson with mean $1$.

This is one way to motivate the following definition. Let $G$ be a groupoid all of whose objects have a finite automorphism group which is tame in the sense that the sum

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

converges (where $\pi_0(G)$ is the set of isomorphism classes of objects). The above sum is called the groupoid cardinality of $G$, and it induces a natural probability measure on $\pi_0(G)$ where an isomorphism class $x$ occurs with probability inversely proportional to $\text{Aut}(x)$.

Example. Let $X$ be a finite set on which a finite group $G$ acts. Form the action groupoid, whose objects are the elements of $X$ and which has a morphism $s_1 \to s_2$ labeled by $g \in G$ whenever $gs_1 = s_2$. Then the groupoid cardinality of the action groupoid is

$$\sum_{x \in \pi_0(X)} \frac{1}{|\text{Stab}(x)|} = \frac{|S|}{|G|}$$

and the induced probability measure on $\pi_0(X)$ is the one we considered above.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For further discussion of the naturality of groupoid cardinality see this blog post.

Example. Let $G$ be the groupoid of finite sets and bijections. Its groupoid cardinality is

With respect to the corresponding probability measure, a random finite set $S$ occurs with probability $\frac{1}{e |S|!}$. The distribution of cardinalities you get this way is Poisson with mean $1$.

This is one way to motivate the following definition. Let $X$ be a groupoid all of whose objects have a finite automorphism group which is tame in the sense that the sum

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

converges (where $\pi_0(X)$ is the set of isomorphism classes of objects of $X$). The above sum is called the groupoid cardinality of $X$, and it induces a natural probability measure on $\pi_0(X)$ where an isomorphism class $x$ occurs with probability inversely proportional to $\text{Aut}(x)$.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For further discussion of the naturality of groupoid cardinality see this blog post.

Example. Let $X$ be a finite set on which a finite group $G$ acts. Form the action groupoid, whose objects are the elements of $X$ and which has a morphism $s_1 \to s_2$ labeled by $g \in G$ whenever $gs_1 = s_2$. Then the groupoid cardinality of the action groupoid is

$$\sum_{x \in \pi_0(X)} \frac{1}{|\text{Stab}(x)|} = \frac{|S|}{|G|}$$

and the induced probability measure on $\pi_0(X)$ is the one we considered above.

Example. Consider the groupoid of finite sets and bijections. Its groupoid cardinality is

With respect to the corresponding probability measure, a random finite set $S$ occurs with probability $\frac{1}{e |S|!}$. The distribution of cardinalities we get this way is Poisson with mean $1$.

added 394 characters in body
Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For a longerfurther discussion of the naturality of groupoid cardinality see this blog post.

What kind of process produces random finite sets? One candidate is to take the fixed point set of a random permutation $\pi \in S_n$ for $n$ large, and in fact one can show that as $n \to \infty$ the distribution of $|\text{Fix}(\pi)|$ approaches a Poisson distribution with mean $1$ (see. See, for example, this blog post for details.)

More generally, the distribution of the number of $r$-cycles of a random permutation in $S_n$ as $n \to \infty$ is Poisson with mean $\frac{1}{r}$. This should have somean interpretation in terms of random finite sets of $r$-cycles, and indeed it does: a collection of $n$ $r$-cycles should have an automorphism group of size $r^n n!$ because we can both permute the cycles and cyclically permute the elements in each cycle, and this recovers a Poisson distribution with mean $\frac{1}{r}$.

For a related example of a more number-theoretic flavor, one can say the same thing about irreducible factors of degree $r$ in a random monic polynomial of large degree over $\mathbb{F}_q$, except that now one has to let $q \to \infty$ as well: see this blog post for details.

Example. Here is ananother example from number theory. Recall that by the Chebotarev density theorem, the Frobenius elements associated to primes $p$ in the Galois group $G = \text{Gal}(K/\mathbb{Q})$ of a number field $K$ are equidistributed in $G$ as $p$ varies. But Frobenius elements are not elements of $G$, they are conjugacy classes, hence objects, well-defined up to isomorphism, in the action groupoid associated to the action of $G$ on itself by conjugacy. So the Chebotarev density theorem can be reinterpreted as saying that a given conjugacy class appears as a Frobenius element with probability inversely proportional to the size of its centralizer.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For a longer discussion of the naturality of groupoid cardinality see this blog post.

What kind of process produces random finite sets? One candidate is to take the fixed point set of a random permutation $\pi \in S_n$ for $n$ large, and in fact one can show that as $n \to \infty$ the distribution of $|\text{Fix}(\pi)|$ approaches a Poisson distribution with mean $1$ (see, for example, this blog post.)

More generally, the distribution of the number of $r$-cycles of a random permutation in $S_n$ as $n \to \infty$ is Poisson with mean $\frac{1}{r}$. This should have some interpretation in terms of random finite sets of $r$-cycles, and indeed it does: a collection of $n$ $r$-cycles should have an automorphism group of size $r^n n!$ because we can both permute the cycles and cyclically permute the elements in each cycle, and this recovers a Poisson distribution with mean $\frac{1}{r}$.

Example. Here is an example from number theory. Recall that by the Chebotarev density theorem, the Frobenius elements associated to primes $p$ in the Galois group $G = \text{Gal}(K/\mathbb{Q})$ of a number field $K$ are equidistributed in $G$ as $p$ varies. But Frobenius elements are not elements of $G$, they are conjugacy classes, hence objects in the action groupoid associated to the action of $G$ on itself by conjugacy. So the Chebotarev density theorem can be reinterpreted as saying that a given conjugacy class appears as a Frobenius element with probability inversely proportional to the size of its centralizer.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For further discussion of the naturality of groupoid cardinality see this blog post.

What kind of process produces random finite sets? One candidate is to take the fixed point set of a random permutation $\pi \in S_n$ for $n$ large, and in fact one can show that as $n \to \infty$ the distribution of $|\text{Fix}(\pi)|$ approaches a Poisson distribution with mean $1$. See, for example, this blog post for details.

More generally, the distribution of the number of $r$-cycles of a random permutation in $S_n$ as $n \to \infty$ is Poisson with mean $\frac{1}{r}$. This should have an interpretation in terms of random finite sets of $r$-cycles, and indeed it does: a collection of $n$ $r$-cycles should have an automorphism group of size $r^n n!$ because we can both permute the cycles and cyclically permute the elements in each cycle, and this recovers a Poisson distribution with mean $\frac{1}{r}$.

For a related example of a more number-theoretic flavor, one can say the same thing about irreducible factors of degree $r$ in a random monic polynomial of large degree over $\mathbb{F}_q$, except that now one has to let $q \to \infty$ as well: see this blog post for details.

Example. Here is another example from number theory. Recall that by the Chebotarev density theorem, the Frobenius elements associated to primes $p$ in the Galois group $G = \text{Gal}(K/\mathbb{Q})$ of a number field $K$ are equidistributed in $G$ as $p$ varies. But Frobenius elements are not elements of $G$, they are conjugacy classes, hence objects, well-defined up to isomorphism, in the action groupoid associated to the action of $G$ on itself by conjugacy. So the Chebotarev density theorem can be reinterpreted as saying that a given conjugacy class appears as a Frobenius element with probability inversely proportional to the size of its centralizer.

Source Link
Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741

I don't have a book reference, but here are some rambling words about why one might, in general, expect objects $x$ to appear with probability proportional to $\frac{1}{|\text{Aut}(x)|}$. The short version is that this is a very natural number to associate to $x$.

To start with, let $X$ be a finite set. If you wanted to pick a random element of $X$, probably you would do it uniformly, and you expect that in the absence of further structure this is what would happen "in Nature."

Now suppose $X$ comes equipped with the action of a finite group $G$, and you wanted to pick a random orbit of $X$. One way to do this is to pick a random element of $X$ and consider its orbit. The induced probability measure on orbits, rather than assigning each orbit equal weight, assigns each orbit a weight inversely proportional to the size of its stabilizer.

This is one way to motivate the following definition. Let $G$ be a groupoid all of whose objects have a finite automorphism group which is tame in the sense that the sum

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

converges (where $\pi_0(G)$ is the set of isomorphism classes of objects). The above sum is called the groupoid cardinality of $G$, and it induces a natural probability measure on $\pi_0(G)$ where an isomorphism class $x$ occurs with probability inversely proportional to $\text{Aut}(x)$.

Example. Let $X$ be a finite set on which a finite group $G$ acts. Form the action groupoid, whose objects are the elements of $X$ and which has a morphism $s_1 \to s_2$ labeled by $g \in G$ whenever $gs_1 = s_2$. Then the groupoid cardinality of the action groupoid is

$$\sum_{x \in \pi_0(X)} \frac{1}{|\text{Stab}(x)|} = \frac{|S|}{|G|}$$

and the induced probability measure on $\pi_0(X)$ is the one we considered above.

One way to think about groupoid cardinality is that it is analogous to the Euler characteristic. The basic intuition is that we expect $\chi(X/G) = \frac{\chi(X)}{|G|}$ for a suitably nice group action of a finite group $G$ on a space $X$, and the one-object groupoid associated to a group $G$ can be thought of as a model of the classifying space $BG = EG/G$, where $EG$ is contractible and so in particular $\chi(EG) = 1$. For a longer discussion of the naturality of groupoid cardinality see this blog post.

Example. Let $G = \mathbb{Z}/2\mathbb{Z}$. Then $BG \cong \mathbb{RP}^{\infty}$ has a cell decomposition with one cell in every dimension, so its Euler characteristic should be

$$1 - 1 + 1 - 1 \pm ...$$

which has, say, Cesaro sum $\frac{1}{2} = \frac{1}{|G|}$!

Example. Let $G$ be the groupoid of finite sets and bijections. Its groupoid cardinality is

$$\sum_{n=0}^{\infty} \frac{1}{n!} = e.$$

With respect to the corresponding probability measure, a random finite set $S$ occurs with probability $\frac{1}{e |S|!}$. The distribution of cardinalities you get this way is Poisson with mean $1$.

What kind of process produces random finite sets? One candidate is to take the fixed point set of a random permutation $\pi \in S_n$ for $n$ large, and in fact one can show that as $n \to \infty$ the distribution of $|\text{Fix}(\pi)|$ approaches a Poisson distribution with mean $1$ (see, for example, this blog post.)

More generally, the distribution of the number of $r$-cycles of a random permutation in $S_n$ as $n \to \infty$ is Poisson with mean $\frac{1}{r}$. This should have some interpretation in terms of random finite sets of $r$-cycles, and indeed it does: a collection of $n$ $r$-cycles should have an automorphism group of size $r^n n!$ because we can both permute the cycles and cyclically permute the elements in each cycle, and this recovers a Poisson distribution with mean $\frac{1}{r}$.

Example. Here is an example from number theory. Recall that by the Chebotarev density theorem, the Frobenius elements associated to primes $p$ in the Galois group $G = \text{Gal}(K/\mathbb{Q})$ of a number field $K$ are equidistributed in $G$ as $p$ varies. But Frobenius elements are not elements of $G$, they are conjugacy classes, hence objects in the action groupoid associated to the action of $G$ on itself by conjugacy. So the Chebotarev density theorem can be reinterpreted as saying that a given conjugacy class appears as a Frobenius element with probability inversely proportional to the size of its centralizer.