|
|
|
|
In other words, \(\mathsf{Perm}\) is the groupoid of finite \(\mathbb{Z}\)-sets. It's also equivalent to the groupoid of covering spaces of the circle having finitely many sheets!
Today I'd like to talk about another slightly bigger groupoid. It's very pretty, and I think it will shed light on a puzzle we saw earlier: the mysterious connection between random permutations and Poisson distributions.
I'll conclude with a question for homotopy theorists.
Remember the formula I proved last time:
\[ \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} \]where \(Y\) is the set of Young diagrams, \(y(k)\) is the number of columns of length \(k\) in the Young diagram \(y\), \(\mathsf{B}(G)\) is the one-object groupoid corresponding to the group \(G\), and for any category \(\mathsf{C}\) I'm using
\[ \frac{\mathsf{C}^n}{n!} \]to stand for the 'weak quotient' of \(\mathsf{C}^n\) by the permutation group \(S_n\). (That is, instead of just modding out, we throw in isomorphisms coming from permutations. I explained this in more detail last time.)
Now, in math we often see expressions like
\[ \sum_{n = 0}^\infty \frac{x^n}{n!} \]and for any category \(\mathsf{C}\),
\[ \mathsf{S}(\mathsf{C}) = \sum_{n = 0}^\infty \frac{\mathsf{C}^n}{n!} \]is the free symmetric monoidal category on \(\mathsf{C}\). The formula for \(\mathsf{Perm}\) looks vaguely similar! Indeed, the free symmetric monoidal category on \(\mathsf{B}(\mathbb{Z}/k)\) is
\[ \mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) = \sum_{n = 0}^\infty \frac{\mathsf{B}(\mathbb{Z}/k)^n}{n!} \]and this seems to be lurking in the background in a strangely fractured way here:
\[ \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} \]What's going on?
What's going on is that \(Y\), the set of Young diagrams, is really the set of functions \(y \colon \mathbb{N}^+ \to \mathbb{N}\) that vanish except at finitely many points. Suppose we drop that finiteness condition! Then things get nicer.
Remember, in any situation where products distribute over sums, if we have a bunch of things \(x_{i j}\) indexed by \(i \in I\), \(j \in J\) we can write the distributive law as
\[ \prod_{i \in I} \sum_{j \in J} x_{i j} \quad \simeq \quad \sum_{f \colon I \to J} \prod_{i \in J} x_{i f(j)} \]For example, if we multiply 5 sums of 2 things we get a sum of \(2^5\) products of 2 things. If we take
\[ \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} \]and drop the finiteness condition on \(y\), we get a new groupoid, which I'll call \(\mathsf{Poiss}\):
\[ \mathsf{Poiss} = \sum_{y \colon \mathbb{N}^+ \to \mathbb{N}} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} \]We can rewrite this using the distributive law:
\[ \begin{array}{ccl} \mathsf{Poiss} & \simeq & \displaystyle{ \prod_{k =1}^\infty \sum_{n = 0}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^n}{n!} } \\ \\ & \simeq & \displaystyle{ \prod_{k =1}^\infty \mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) } \end{array} \]It's just the product of the free symmetric monoidal categories on all the \(\mathsf{B}(\mathbb{Z}/k)\).
What is the category \(\mathsf{S}(\mathsf{B}(\mathbb{Z}/k))\) actually like? It's a groupoid. It has objects \(1, x, x^{\otimes 2}, x^{\otimes 3}, \dots\) and so on. There are no morphisms between distinct objects. The automorphism group of \(x^{\otimes n}\) is the semidirect product of \(S_n\) and \(\mathbb{Z}/k \times \cdots \times \mathbb{Z}/k\), where the symmetric group acts to permute the factors.
So, in words, \(\mathsf{S}(\mathsf{B}(\mathbb{Z}/k))\) is the 'free symmetric monoidal category on an object \(x\) having \(\mathbb{Z}/k\) as its symmetry group'.
This sounds abstract. But it's equivalent to something concrete: the groupoid of finite sets that are equipped with a permutation all of whose cycles have length \(k\). The object \(x\) corresponds to a set with a permutation having a single cycle of length \(k\). The tensor product corresponds to disjoint union. Thus, \(x^{\otimes n}\) corresponds to a set with a permutation having \(n\) disjoint cycles of length \(k\).
So, you can think of an object of
\[\mathsf{Poiss} \simeq \displaystyle{ \prod_{k =1}^\infty \mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) } \]as an infinite list of finite sets, one for each \(k = 1, 2, 3, \dots\), where the \(k\)th set is equipped with a permutation having only cycles of length \(k\).
Taking the disjoint union of all these sets, we get a single set with a permutation on it. This set may be infinite, but all its cycles have finite length, and it has finitely many cycles of each length \(k = 1, 2, 3, \dots\). So:
Theorem. The groupoid
$$ \mathsf{Poiss} \simeq \prod_{k =1}^\infty \mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) $$ is equivalent to the groupoid of sets equipped with a permutation having only cycles of finite length, with finitely many cycles of each length.It's easy from this description to see the inclusion
\[ \mathsf{Perm} \hookrightarrow \mathsf{Poiss} \]It's just the inclusion of the finite sets equipped with permutation!
I claim that the groupoid \(\mathsf{Poiss}\) explains why the number of cycles of length \(k\) in a randomly chosen permutation of an \(n\)-element set approaches a Poisson-distributed random variable with mean \(1/k\) as \(n \to \infty\). The fact that it's a product also explains why these random variables become independent in the \(n \to \infty\) limit.
I'll talk about this more later. But to get an idea of how it works, let's compute the groupoid cardinality of \(\mathsf{S}(\mathsf{B}(\mathbb{Z}/k))\). It's
\[ \begin{array}{ccl} | \mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) | &=&\displaystyle{ \left| \sum_{n = 0}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^n}{n!} \right| } \\ \\ &=& \displaystyle{ \sum_{n = 0}^\infty \frac{ |\mathsf{B}(\mathbb{Z}/k)|^n}{n!} } \\ \\ &=& \displaystyle{ \sum_{n = 0}^\infty \frac{ (1/k)^n}{n!} } \\ \\ &=& e^{1/k} \end{array} \]The Poisson distribution with mean \(1/k\) is
\[ p_n = e^{-1/k} \frac{ (1/k)^n}{n!} \]so we're seeing that lurking here. But I need to think about this more before I can give a really convincing explanation.
Let me conclude with a puzzle for homotopy theorists.
First, some background so others can enjoy the puzzle, or at least learn something. Homotopy theorists know how to take any category and turn it into a topological space: the geometric realization of its nerve. If we take a group \(G\) and apply this trick to the one-object groupoid \(\mathsf{B}(G)\) we get the Eilenberg–Mac Lane space \(K(G,1)\). This is the connected space with \(G\) as its fundamental group and all higher homotopy groups being trivial. As long as we give \(G\) the discrete topology, as we'll do for \(G = \mathbb{Z}/k\) here, \(K(G,1)\) is also the classifying space for \(G\)-bundles, denoted \(B G\). (This looks a lot like the groupoid \(\mathsf{B}(G)\) — but that's okay, because in homotopy theory a groupoid is considered only slightly different from the geometric realization of its nerve.)
Puzzle. Given a discrete group \(G\), what's a nice description of the geometric realization of the nerve of \(\mathsf{S}(\mathsf{B}(G))\), the free symmetric monoidal category on the one-object groupoid corresponding to \(G\)? I'm especially interested in the case where \(G\) is a finite cyclic group.
By the way, the classifying space \(B(\mathbb{Z}/k)\) is a 'lens space': it's formed by taking the unit sphere in \(\mathbb{C}^\infty\) and quotienting by the action of the \(k\)th roots of unity. My first guess on the puzzle is to take the disjoint union
\[ \sum_{n=0}^\infty \frac{ B(\mathbb{Z}/k)^n}{S_n} \]A point in here is a finite set of points in the lens space! Note that the construction here is different from the infinite symmetric product used in the Dold–Kan theorem, because we are not identifying an \(n\)-element set of points with an \((n+1)\)-element set whose extra element is the basepoint.
What do you think, experts?
You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|