# Wreath product $S_k\wr S_n$ inside $S_{kn}$

I want to understand wreath products a little better.

Currently, my intuition about them is as follows. Take $$nk$$ disks, pile them in order forming $$n$$ piles of $$k$$ disks (one pile contains disks {1,...,k}, another pile disks {k+1,...,2k}, so on). The wreath product $$H_{k,n}=S_k \wr S_n$$ preserves this strucutre, i.e. it only permutes disks within piles or permutes whole piles.

In other words, if $$P=S_k\times S_k\times \cdots\times S_k$$ is the direct product of groups permuting disks within piles, then $$H_{k,n}$$ is its normalizer inside $$S_{kn}$$.

I believe all the above is correct. What I need help with is how $$H_{k,n}$$ sits inside $$S_{kn}$$. For example, what is the cardinality of the double coset $$H_{k,n}/S_{kn}\backslash H_{k,n}$$?

For $$k=2$$ I known that this cardinality equals $$p(n)$$, the number of partitions of $$n$$. (My intuition is that it would always be $$p(n)$$ for any $$k$$, but I am not confident about it.)

Suggestions of accessible sources would be welcome (I am a physicist).

• Why is the cardinality $p(n)$ for $k=2$ ? – LeechLattice Oct 5 '19 at 11:39
• @Bullet51 My intuition is this: $H_{k,n}$ is the group of operations that leave the piles invariant. So the double cosets are the guys which mix the piles. A double coset is identified by how it does this mixing. For example, if there are 5 piles, a certain operation might mix 3 of the piles among themselves and the other 2 among themselves. This is how partitions come about. – thedude Oct 5 '19 at 11:42
• Your reasoning is correct. I believe it also works for $k \geq 3$. – LeechLattice Oct 5 '19 at 11:55
• The construction of $H_{k,n}$ is not symmetric in k and n: exchange the values and the order of the group changes. – LeechLattice Oct 5 '19 at 12:01
• The number of double cosets is $\langle h_n \circ h_k, h_n \circ h_k\rangle$, where $\circ$ is the plethysm product and $h_m$ is the complete homogeneous symmetric function of degree $m$. This may be useful computationally. One related result: in The enumeration of locally restricted graphs I, J. London Math. Soc 34 (1959), 417–436, Read shows that $\langle h_n \circ h_k, h_{nk/2} \circ h_2 \rangle$ enumerates $k$-regular graphs on $kn$ vertices. This is the number of orbits of $S_n \wr S_k$ on $S_{kn} / S_{kn/2} \wr S_2$. Sketch proof in ma.rhul.ac.uk/~uvah099/Talks/Plethysms.pdf – Mark Wildon Oct 5 '19 at 18:13

The numbers arise in two contexts of physics:

The first is counting symmetric tensor invariants without color. See Counting Tensor Model Observables and Branched Covers of the 2-Sphere, chapter 6.

The second is in the counting of vacuum Feynman graphs. The paper features the enumeration of row/column permutation equivalence classes of RC-magic squares, which are $$n\times n$$ integral matrices with nonnegative entries whose rows and columns sums to $$k$$. See A combinatorial matrix approach for the generation of vacuum Feynman graphs multiplicities in φ$$^4$$ theory.

The equivalence classes of RC-magic squares are in 1-1 correspondence with the double cosets.

To see this, let $$g$$ be an element of $$S_{kn}$$, acting on $$n$$ piles of $$k$$ disks.

We construct an RC-magic square $$M(g)$$ in the following way: $$M(g)_{ij}$$ is the number of elements in the $$j$$-th pile which were originally in the $$i$$-th pile.

In order to prove 1-1 correspondence, we need to prove

1)Two elements in the same double coset necessarily corresponds to the same equivalence class

2)Two elements in the same equivalent class necessarily lies in the same coset.

Let $$P$$ denote the group permuting disks within piles, and $$T$$ the group permuting piles. Let $$H$$ be the wreath product group.

To prove 1), let $$g'=h_1gh_2$$, where $$h_1,h_2\in H$$. Then there exists $$p_1,p_2\in P$$, $$t_1,t_2\in T$$ such that $$g'=t_1p_1gp_2t_2$$. $$p_1$$ and $$p_2$$ induce no action on $$M(g)$$, $$t_1$$ permute the rows, and $$t_2$$ permute the columns. So $$g$$ and $$g'$$ belongs to the same equivalent class.

To prove 2), let $$M(g)$$ and $$M(g')$$ lie in the same class. Then $$M(g)=t_1M(g')t_2$$ for some $$t_1,t_2\in T$$. ($$t_1$$ and $$t_2$$ induce actions on $$M(g')$$). So $$g$$ and $$t_1g't_2$$ moves the same number of balls from pile $$i$$ to pile $$j$$ for each $$i,j$$, which means they differ by elements in $$P$$: $$p_1g=t_1g't_2p_2$$ for some $$p_1,p_2\in P$$. (It is possible to make the point more rigorous, by assigning an order on the elements, and let $$p_1$$ and $$p_2$$ sort the elements in each pile). It follows that $$g$$ and $$g'$$ are in the same coset.

For $$k=3$$, one can find the exact numbers in Ronald C. Read's PhD Thesis, Some enumeration problems in graph theory, page 156. The asymptotics are given as

$$\frac{(3n)!}{(n!)^26^{2n}}\exp\Bigl(2 - \frac{2}{9n} + O(n^{-2})\Bigr),$$

which can be found in Brendan Mckay's MathOverflow answer.

• Do you know if Ronald C. Read's PhD Thesis is available online somewhere? – thedude Oct 5 '19 at 15:01
• I'm not sure, but I'm unable to find it. – LeechLattice Oct 5 '19 at 15:09
• How do you know the numbers are in page 156? – thedude Oct 5 '19 at 15:20
• It's in a reference on the third page of this paper: "The earliest work on this problem was that of Read [19, p. 156]". – LeechLattice Oct 5 '19 at 16:03
• Also, I don't understand your comment that "By working out the general form of a double coset, one can see the equivalence classes are in 1-1 correspondence with the double cosets." I haven't found this discussion in the linked paper. I would be very interested in understanding "the general form of a double coset", could you indicate how this can be done? – thedude Oct 6 '19 at 14:38