Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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’, Perm\mathsf{Perm}. Remember:

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

In other words, Perm\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:

Perm yY k=1 B(/k) y(k)y(k)! \mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}

where YY is the set of Young diagrams, y(k)y(k) is the number of columns of length kk in the Young diagram yy, B(G)\mathsf{B}(G) is the one-object groupoid corresponding to the group GG, and for any category C\mathsf{C} I’m using

C nn! \frac{\mathsf{C}^n}{n!}

to stand for the ‘weak quotient’ of C n\mathsf{C}^n by the permutation group S nS_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

n=0 x nn! \sum_{n = 0}^\infty \frac{x^n}{n!}

and for any category C\mathsf{C},

S(C)= n=0 C nn! \mathsf{S}(\mathsf{C}) = \sum_{n = 0}^\infty \frac{\mathsf{C}^n}{n!}

is the free symmetric monoidal category on C\mathsf{C}. The formula for Perm\mathsf{Perm} looks vaguely similar! Indeed, the free symmetric monoidal category on B(/k)\mathsf{B}(\mathbb{Z}/k) is

S(B(/k))= n=0 B(/k) nn! \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:

Perm yY k=1 B(/k) y(k)y(k)! \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 YY, the set of Young diagrams, is really the set of functions y: +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 ijx_{i j} indexed by iIi \in I, jJj \in J we can write the distributive law as

iI jJx ij f:IJ iJx if(j) \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 52^5 products of 2 things. So, if we take

Perm yY k=1 B(/k) y(k)y(k)! \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 yy, we get a new groupoid, which I’ll call Poiss\mathsf{Poiss}:

Poiss= y: + k=1 B(/k) y(k)y(k)! \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:

Poiss k=1 n=0 B(/k) nn! k=1 S(B(/k)) \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 B(/k)\mathsf{B}(\mathbb{Z}/k).

What is the category S(B(/k))\mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) actually like? It’s a groupoid. It has objects 1,x,x 2,x 3,1, x, x^{\otimes 2}, x^{\otimes 3}, \dots and so on. There are no morphisms between distinct objects. The automorphism group of x nx^{\otimes n} is the semidirect product of S nS_n and /k××/k\mathbb{Z}/k \times \cdots \times \mathbb{Z}/k, where the symmetric group acts to permute the factors.

So, in words, S(B(/k))\mathsf{S}(\mathsf{B}(\mathbb{Z}/k)) is the ‘free symmetric monoidal category on an object xx having /k\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 kk. The object xx corresponds to a set with a permutation having a single cycle of length kk. The tensor product corresponds to disjoint union. Thus, x nx^{\otimes n} corresponds to a set with a permutation having nn disjoint cycles of length kk.

So, you can think of an object of

Poiss k=1 S(B(/k))\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,k = 1, 2, 3, \dots, where the kkth set is equipped with a permutation having only cycles of length kk.

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,k = 1, 2, 3, \dots . So:

Theorem. The groupoid Poiss k=1 S(B(/k)) \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

PermPoiss \mathsf{Perm} \hookrightarrow \mathsf{Poiss}

It’s just the inclusion of the finite sets equipped with permutation!

I claim that the groupoid Poiss\mathsf{Poiss} explains why the number of cycles of length kk in a randomly chosen permutation of an nn-element set approaches a Poisson-distributed random variable with mean 1/k1/k as nn \to \infty. The fact that it’s a product also explains why these random variables become independent in the nn \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 S(B(/k))\mathsf{S}(\mathsf{B}(\mathbb{Z}/k)). It’s

|S(B(/k))| = | n=0 B(/k) nn!| = n=0 |B(/k)| nn! = n=0 (1/k) nn! = e 1/k \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/k1/k is

p n=e 1/k(1/k) nn! 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 GG and apply this trick to the one-object groupoid B(G)\mathsf{B}(G) we get the Eilenberg–Mac Lane space K(G,1)K(G,1). This is the connected space with GG as its fundamental group and all higher homotopy groups being trivial. As long as we give GG the discrete topology, as we’ll do for G=/kG = \mathbb{Z}/k here, K(G,1)K(G,1) is also the classifying space for GG-bundles, denoted BGB G. (This looks a lot like the groupoid B(G)\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 GG, what’s a nice description of the geometric realization of the nerve of S(B(G))\mathsf{S}(\mathsf{B}(G)), the free symmetric monoidal category on the one-object groupoid corresponding to GG? I’m especially interested in the case where GG is a finite cyclic group.

By the way, the classifying space B(/k)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 kkth roots of unity. My first guess on the puzzle is to take the disjoint union

n=0 B(/k) nS n \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 nn-element set of points with an (n+1)(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

16 Comments & 0 Trackbacks

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?

Posted by: Thomas Read on January 19, 2020 12:15 PM | Permalink | Reply to this

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 nn \in \mathbb{N}, n1n \geq 1, let

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

be given by sending a pair of permutations (σ 1,σ 2)(\sigma_1, \sigma_2) to the number of cycles in σ 1σ 2 1\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(nn) with the set of all transpositions as generators, then the distance between two permutations (σ 1,σ 2)(\sigma_1,\sigma_2) is nn - the number of cycles in σ 1σ 2 1\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))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 dd here you mean the distance in the Cayley graph for Sym(n)Sym(n) generated by transpositions. In that case I don’t know whether exp(d(x,y))\exp(-d(x,y)) is a positive semidefinite kernel, but I do know that exp(td(x,y))\exp(- t d(x,y)) is not positive semidefinite for every t>0t > 0. The latter property is one way of saying that the metric space (Sym(n),d)(Sym(n), d) is of “negative type”. I happen to know that (Sym(n),d)(Sym(n), d) is not of negative type for n3n \ge 3, since the Cayley graph of Sym(3)Sym(3) is the complete bipartite graph K 3,3K_{3,3}, which contains K 3,2K_{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 tt for which exp(td(x,y))exp(-t d(x,y)) is positive semidefinite on (Sym(n),d)(Sym(n), d), presumably depending on nn?

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 tt is (Sym(n),td)(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!)1t > log(n!) - 1 .

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

This now looks like a statement about some sort of partition function on Sym(n)\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 1n! σSym(n)exp[tC(σ)](1+1n!)e tn, \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 nn 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 2n!e tn. \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)S(n) is adjacent transpositions.

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

Post a New Comment