# Structure constants for the double coset algebra of a Young subgroup

Fix a Young subgroup $$H_\lambda \subseteq \mathcal S_n$$, where $$\lambda \vdash n$$ is a partition of $$n$$ with $$k$$ blocks. Inside the group algebra $$\mathbb C[\mathcal S_n]$$, consider the idempotent $$\varepsilon = \frac{1}{|H_\lambda|}\sum_{h \in H_\lambda} h.$$

The double cosets $$H_\lambda \backslash \mathcal S_n / H_\lambda$$ are indexed by matrices $$k \times k$$ with non-negative entries and row (resp. column) sums given by the blocks of $$\lambda$$ (see Richard Stanley's answer to Number of double cosets of a Young subgroup). For a representative $$\alpha_x \in \mathcal S_n$$ of a given coset, define the element $$\sigma_x = \varepsilon \alpha_x \varepsilon,$$ which is an element of the corresponding Hecke algebra; above, $$x$$ is a matrix with non-negative entries with row and column sums given by $$\lambda$$.

I would like to know how to find the structure constants of the Hecke algebra, i.e. the coefficients $$\gamma_{x,y}^z$$ such that $$\sigma_x \cdot \sigma_y = \sum_z \gamma_{x,y}^z \sigma_z.$$

Example

In the case $$\mathcal S_p \times \mathcal S_q \subseteq \mathcal S_{n=p+q}$$, the double cosets can be indexed by integers $$0 \leq x \leq \min(p,q)$$, where $$x$$ represents the number of elements of $$[1,p]$$ mapped to $$[p+1,p+q]$$. Using basic combinatorics, I can show that $$\sigma_x \sigma_1 = \frac{1}{pq} \left( (p-x)(q-x) \sigma_{x+1} + x^2 \sigma_{x-1} + (x(p-x)+x(q-x))\sigma_x \right).$$

There is a combinatorial rule for the structure constants. It appears in Section 2 of https://arxiv.org/abs/1104.1959, although it is not immediately clear that it is indeed what you are looking for.

Suppose that $$V$$ is a vector space of dimension at least $$l(\lambda)$$. Then in the setting of Schur-Weyl duality, there is a simultaneous action of $$GL(V)$$ and $$S_n$$ on $$V^{\otimes n}$$. We note that the $$\lambda$$-weight space of $$V^{\otimes n}$$ is precisely the permutation module $$M^\lambda$$ induced from the trivial module of $$H_\lambda$$.

As a representation of $$\mathbb{C}S_n$$, $$\mathbb{C}S_n \varepsilon$$ is $$M^\lambda$$. So the Hecke algebra you are implicitly considering is $$\mathrm{End}_{\mathbb{C}S_n}(M^\lambda).$$ This is related to $$\mathrm{End}_{\mathbb{C}S_n}(V^{\otimes n})$$, which is why the Schur algebra (appearing in the paper) is relevant here.

However, the most convenient basis is given by $$\xi_x = \frac{1}{|H_\lambda|}\sum_{g \in H_\lambda \alpha_x H_\lambda} g,$$ which is to say, double-coset sums divided by $$|H_\lambda|$$, which is a different normalisation to your elements $$\sigma_x$$. Explicitly, $$\sigma_x = \frac{|H_\lambda \cap \alpha_x H_\lambda \alpha_x^{-1}|}{|H_\lambda|}\xi_x,$$ and it is a standard lemma that if $$\alpha_x$$ is a minimal-length double-coset representative, $$H_\lambda \cap \alpha_x H_\lambda \alpha_x^{-1}$$ is also a Young subgroup, so its size can easily be written down.

Note that the double cosets $$H_\lambda \alpha_x H_\lambda$$ are indexed by square matrices of size $$l(\lambda)$$ whose row and column sums are $$\lambda$$. The $$(i,j)$$-th entry counts how many elements of $$\{1,2,\ldots,n\}$$ permuted by $$S_{\lambda_j}$$ are mapped by some (and therefore any) element of the double coset to elements permuted by $$S_{\lambda_i}$$.

So we let the indexing variables $$x,y,z$$ be matrices of that form, and write them with subscripts (e.g. $$x_{ij}$$) to refer to the entries of the corresponding matrices.

To calculate the coefficient of $$\xi_z$$ in $$\xi_x \xi_y$$, we consider "cubic matrices of size $$l(\lambda)$$" (i.e. $$l(\lambda) \times l(\lambda) \times l(\lambda)$$ 3-tensors) $$A_{ijk}$$ with entries in $$\mathbb{Z}_{\geq 0}$$. We require that $$\sum_i A_{ijk} = x_{jk}$$ $$\sum_j A_{ijk} = z_{ik}$$ $$\sum_k A_{ijk} = y_{ij}$$ Then the coefficient is $$\sum_A \prod_{i,k}\frac{(\sum_j A_{ijk})!}{\prod_j A_{ijk}!},$$ subject to the conditions on $$A$$ already mentioned.

Let's check this for your example. We take the matrix $$x$$ to be $$\begin{bmatrix} p-x & x \\ x & q-x \end{bmatrix}.$$ (Here there is an conflict of notation between the label of the double coset, and the number of elements it "mixes" between $$S_{p}$$ and $$S_q$$.) We take the matrix $$y$$ to be $$\begin{bmatrix} p-1 & 1 \\ 1 & q-1 \end{bmatrix}.$$ So we are going to calculate $$\xi_x \xi_y$$. Typsetting a 3-tensor $$A_{ijk}$$ is tricky, so let's consider the "slices" $$A_{i1k}$$ and $$A_{i2k}$$ separately. The row-sums of $$A_{i1k}$$ are $$(p-x,x)$$ and the column sums are $$(p-1,1)$$. There are two possibilities for $$A_{i1l}$$: $$\begin{bmatrix} p-x & 0 \\ x-1 & 1 \end{bmatrix}, \begin{bmatrix} p-x-1 & 1 \\ x & 0 \end{bmatrix}.$$ Similarly, for $$A_{i2k}$$ we have row-sums $$(x,q-x)$$ and column sums $$(1,q-1)$$, so we get $$\begin{bmatrix} 1 & x-1 \\ 0 & q-x \end{bmatrix}, \begin{bmatrix} 0 & x \\ 1 & q-x-1 \end{bmatrix}.$$ So there are four ways of combining these into the full tensor $$A_{ijk}$$. For each of these, we get a multiple of $$\xi_z$$, where $$z = A_{i1k}+A_{12k}$$, and the scalar multiple is a product of (very simple) binomial coefficients.

Choosing the first option for each of $$A_{i1k}$$ and $$A_{i2k}$$ gives $$z$$ with off-diagonal entries $$x-1$$, and the scalar multiple is $$(p-x+1)(q-x+1)$$.

Choosing the last of each gives $$z$$ with off-diagonal entries $$x+1$$, and the scalar multiple is $$(x+1)^2$$.

Each of the other two choices gives $$z$$ with off-diagonal entries $$x$$, and the scalar multiples are $$x(p-x)$$ and $$x(q-x)$$.

To recover your equation, we just need to know that if $$z$$ has off-diagonal entries equal to $$r$$, then $$\sigma_r = \frac{1}{{p \choose r}{q \choose r}} \xi_r,$$ so for example, you can immediately multiply your equation by $$pq$$ to turn $$\sigma_1$$ into $$\xi_y$$ (and clear a denominator on the right).

I have left out some details to keep this post from being egregiously long, but I would be happy to explain further or give references if it would be helpful.

What is described in this post is just the tip of the iceberg, for example it's possible to interpolate these structure constants to define certain "permutation module Deligne Categories", such as in https://arxiv.org/abs/1909.04100.

• Welcome to MathOverflow! Jun 8 '20 at 20:00
• Dear Christopher, welcome to MO and thanks a lot for taking the time to write such an insightful and detailed comment. Not only you answer precisely the question I had, the background you provide is very helpful. Note that the elements $\sigma_x$ I consider are averages over the double cosets, so my normalization is the inverse of the size of the double coset, while yours is the inverse of the size of $H_\lambda$. Also, this means that the fraction in your equation relating $\sigma_x$ and $\xi_x$ should be inverted, right? Thanks again for your help. Jun 9 '20 at 15:25
• Thanks for the kind words! I believe the relation between $\sigma_x$ and $\xi_x$ is correct as stated. I am using the fact that the size of the $(H,K)$-double coset $HgK$ in a group $G$ is $|H||K|/|H \cap gKg^{-1}|$. In particular, I am taking $H=K=H_\lambda$ and $g=\alpha_x$. (But your comment would apply if the numerator of the fraction was the size of the double coset.) Jun 10 '20 at 1:07
• Dear Christopher, you are of course right, I was confused about the formula for the size of the double coset. Thanks again! Jun 10 '20 at 16:01