## 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)

Ah, thanks!

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)

Great, thanks.

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

### Re: Random Permutations (Part 13)

In case anyone is interested, we worked out some answers to this question over on the nLab.

Quite a route via group characters and Schur functions.

Posted by: David Corfield on April 29, 2021 10:42 AM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

To follow up on this, the question is whether the matrix with entries $A_{i,j}(z) = z^{d(x_i,x_j)}$ is positive definite for all $z \in (0,1)$: here the variable $z$ replaces $\exp(-t)$. Since $A(z)$ is symmetric, that’s equivalent to asking whether all eigenvalues are positive for each $z$. Since the eigenvalues of vary continuously as $z$ varies from $0$ to $1$, it is sufficient for the determinant $\det A(z)$ to be positive until $z$ reaches $1$, when all but one of the eigenvalues becomes zero.

This determinant $\det A(z)$ is a polynomial invariant of the metric space. When the metric is graph distance, it is a polynomial graph invariant, which turns out to be invariant under $1$-isomorphism: for example, all trees on $n$ vertices have the same invariant $(1-z^2)^{n-1}$.

Is this a form of a known invariant?

Posted by: Richard Pinch on March 19, 2020 6:06 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

A minor quibble: $det A(z)$ is only a polynomial if all the distances in the metric space are integers.

I don’t recognize this invariant, but someone must have considered it previously somewhere in the literature on metric spaces of negative type.

In the graph context it’s certainly related to the magnitude of a graph.

Posted by: Mark Meckes on March 20, 2020 7:36 PM | Permalink | Reply to this

### Re: Random Permutations (Part 13)

Agreed that one needs a wider definition of polynomial (arbitrary positive real exponents) in the general case.

As far as graphs, are concerned, the polynomial $\det A(z)$ does indeed appear in the definition of magnitude, defined as a rational function attached to a graph, as a denominator, thanks for the pointer.

Posted by: Richard Pinch on March 22, 2020 6:21 PM | Permalink | Reply to this

### Qiaochu

Your formula for Perm has a shorter and more conceptual description and proof! It says exactly that Perm is the free symmetric monoidal groupoid on the groupoid of cycles $\bigsqcup_{k \ge 1} B \mathbb{Z}/k$, which is just a properly categorified way of describing the precise sense in which a permutation has a cycle decomposition and the precise sense in which it’s unique. Said another way, it’s a categorification of the exponential formula in permutation form

$\sum_{n \ge 0} Z(S_n) t^n = \exp \left( \sum_{k \ge 1} z_k \frac{t^k}{k} \right)$

where $Z(S_n)$ are the cycle index polynomials of the symmetric groups. In species language, cycle decomposition is an isomorphism $\text{Perm} \cong \text{Multiset} \circ \text{Cyc}$.

You describe Perm as the groupoid of finite $\mathbb{Z}$-sets here. You can replace $\mathbb{Z}$ with any group $G$; the generalization of cycle decomposition is that the groupoid of finite $G$-sets is the free symmetric monoidal groupoid on the groupoid of finite transitive $G$-sets, and as I described in this blog post taking groupoid cardinalities gives a really lovely generating function (for finitely generated $G$)

$\sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} t^n = \exp \left( \frac{a_n}{n} t^n \right)$

where $a_n$ is the number of subgroups of $G$ of index $n$. I have no idea who this is due to but it appears in Stanley’s Enumerative Combinatorics somewhere. The $\frac{1}{n}$ can’t be interpreted in terms of $\mathbb{Z}/n$ or any group of order $n$ in general; it corresponds to the groupoid of finite transitive $G$-sets with $n$ elements having a canonical $n$-fold cover, namely the groupoid of finite transitive pointed $G$-sets with $n$ elements, and this groupoid can in turn canonically be identified with the discrete groupoid (no nontrivial automorphisms) of subgroups of $G$ of index $n$, by taking the stabilizer of the distinguished point.

I give several cute applications of this identity in this blog post (taking $G = F_2$ tells us what the coefficients of the logarithm of $\sum n! t^n$ mean!), and in this later post I use it to count subgroups of the modular group $\Gamma$ (by taking $G = \mathbb{Z}/2$ and $G = \mathbb{Z}/3$ and using the fact that $|\text{Hom}(-, S_n)|$ sends free products to products).

Posted by: Qiaochu Yuan on September 7, 2020 7:25 PM | Permalink | Reply to this

### Qiaochu

Oh, also: there are too many posts and comments for me to keep track, so I hope this isn’t a duplicate observation. The claim that the number of cycles of lengths $1, 2, \dots k$ for fixed $k$ are asymptotically independent Poisson with rates $1, \frac{1}{2}, \dots \frac{1}{k}$ can be proven (up to details about what kinds of convergence in terms of moments or moment generating functions imply what kinds of convergence in terms of distributions) with a pretty short computation from the exponential formula, which I did here; I guess a version of this argument is what you’re alluding to towards the end?

As for the homotopy theory question, the free symmetric monoidal groupoid on a space breaks up into components and the components are the “homotopy symmetric powers” $X^n/S_n$. I don’t know a nicer description of this than that it’s a homotopy quotient; I suppose it depends on how nice your models of $BS_n$ and $ES_n$ are (I think they can be taken to be configurations of $n$ unordered resp. ordered points in $\mathbb{R}^{\infty}$).

Posted by: Qiaochu Yuan on September 7, 2020 7:35 PM | Permalink | Reply to this

Post a New Comment