## January 17, 2020

### Random Permutations (Part 13)

#### Posted by John Baez Last time I started talking about the groupoid of ‘finite sets equipped with permutation’, $\mathsf{Perm}$. Remember:

• an object $(X,\sigma)$ of $\mathsf{Perm}$ is a finite set $X$ with a bijection $\sigma \colon X \to X$;
• a morphism $f \colon (X,\sigma) \to (X',\sigma')$ is a bijection $f \colon X \to X'$ such that $\sigma' = f \sigma f^{-1}$.

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. So, 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)!}$

and 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} \cong \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?

Posted at January 17, 2020 1:34 AM UTC

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

### Re: Random Permutations (Part 13)

I think the formula after “we can write the distributive law” has the sums and products the wrong way round?

### Re: Random Permutations (Part 13)

Yes, thanks for catching that! This is a typo that doesn’t affect the calculations that follow. I’ll fix it.

Posted by: John Baez on January 19, 2020 7:19 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Asking for a friend, has anyone heard of people constructing a kind of inner product on permutations?

For any $n \in \mathbb{N}$, $n \geq 1$, let

$\langle -,-\rangle \;:\; Sym(n) \times Sym(n) \longrightarrow \{1, \cdots,n \} \subset \mathbb{N}$

be given by sending a pair of permutations $(\sigma_1, \sigma_2)$ to the number of cycles in $\sigma_1 \circ \sigma_2^{-1}$.

Posted by: David Corfield on January 29, 2020 1:46 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Not as an inner product, but this is a known distance function. If we take the Cayley graph for Sym($n$) with the set of all transpositions as generators, then the distance between two permutations $(\sigma_1,\sigma_2)$ is $n -$ the number of cycles in $\sigma_1 \cdot \sigma_2^{-1}$.

Posted by: Richard Pinch on February 6, 2020 1:17 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Great, thanks! The hope was to bound the difference between the sum of two sides of a triangle and the third, perhaps after exponentiating that number of cycles. Would you know if there’s anything along these lines?

Posted by: David Corfield on February 6, 2020 5:36 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

So really what’s wanted is to know whether $exp(−d(x,y))$ is a positive semidefinite kernel. There are general conditions, as here. Do they apply to this case?

Posted by: David Corfield on February 7, 2020 1:41 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

So I guess by $d$ here you mean the distance in the Cayley graph for $Sym(n)$ generated by transpositions. In that case I don’t know whether $\exp(-d(x,y))$ is a positive semidefinite kernel, but I do know that $\exp(- t d(x,y))$ is not positive semidefinite for every $t > 0$. The latter property is one way of saying that the metric space $(Sym(n), d)$ is of “negative type”. I happen to know that $(Sym(n), d)$ is not of negative type for $n \ge 3$, since the Cayley graph of $Sym(3)$ is the complete bipartite graph $K_{3,3}$, which contains $K_{3,2}$, which is a minimal example of a metric space which is not of negative type.

Posted by: Mark Meckes on February 7, 2020 9:50 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Posted by: David Corfield on February 8, 2020 10:14 AM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

So are there strategies to work out ranges of $t$ for which $exp(-t d(x,y))$ is positive semidefinite on $(Sym(n), d)$, presumably depending on $n$?

Posted by: David Corfield on February 8, 2020 4:45 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

In language which is familiar in these parts you’re asking, for which $t$ is $(Sym(n), t d)$ a positive definite metric space? I don’t know the optimal answer in this case, but Proposition 2.4.17 of “The magnitude of metric spaces” implies that it is for $t > log(n!) - 1$.

You could do possibly better with a direct application of the Gershgorin circle theorem: $exp(-t d(x,y))$ will be positive definite whenever $\sum_{x \neq y} exp(-t d(x,y))< 1$ for each $y$. From what Richard said, this is equivalent to $\sum_{\sigma \in Sym(n) \setminus \{ Id \} } exp[t C(\sigma)] \le e^{t n},$ where $C(\sigma)$ is the number of cycles in $\sigma$.

This now looks like a statement about some sort of partition function on $\Sym(n)$, and I bet there are ideas floating around this series of posts by John that would help analyze this question.

Posted by: Mark Meckes on February 8, 2020 7:40 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

I meant for that last inequality to be strict. That typo snuck in while I was trying to debug TeX errors.

However, I was being a bit cavalier about positive definite versus semidefinite generally. In the context of magnitude of metric spaces we really want to focus on the strictly positive definite case. But if you (David) are really only interested in knowing about positive semidefiniteness, just make all the inequalities I wrote non-strict.

Posted by: Mark Meckes on February 8, 2020 7:49 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Or, if you’re paying more attention to what this series of posts was all about than I was, you’d write that last inequality as $\frac{1}{n!} \sum_{\sigma \in Sym(n)} exp[t C(\sigma)] \le \left(1+\frac{1}{n!}\right) e^{t n},$ and recognize the left hand side as the moment generating function of the number of cycles of a random permutation on $n$ letters.

In which case some useful ideas are definitely floating around here somewhere, but I’m having trouble locating them at the moment.

Posted by: Mark Meckes on February 8, 2020 8:00 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

That last sentence describes the state of my brain pretty much all the time.

Posted by: Blake Stacey on February 9, 2020 4:34 AM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Posted by: David Corfield on February 9, 2020 2:10 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Apparently I can’t do simple algebra, either. The right hand side above should of course have been $\frac{2}{n!} e^{t n}.$

Posted by: Mark Meckes on February 10, 2020 1:12 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

It seems there is a Mallows kernel (p. 11), which is positive definite, where the generating set for $S(n)$ is adjacent transpositions.

Posted by: David Corfield on February 10, 2020 3:22 PM | Permalink | Reply to this

Post a New Comment