# The Unapologetic Mathematician

## Garnir Elements

Let $A$ and $B$ be two disjoint sets of positive integers. We’re mostly interested in the symmetric group $S_{A\uplus B}$, which shuffles around all the integers in both sets. But a particularly interesting subgroup is $S_A\times S_B$, which shuffles around the integers in $A$ and $B$, but doesn’t mix the two together. Clearly, $S_A\times S_B$ is a subgroup of $S_{A\uplus B}$.

Now, let $\Pi\subseteq S_{A\uplus B}$ be a transversal collection of permutations for this subgroup. That is, we can decompose the group into cosets

$\displaystyle S_{A\uplus B}=\biguplus\limits_{\pi\in\Pi}\pi(S_A\times S_B)$

Then a “Garnir element” is

$\displaystyle g_{A,B}=\Pi^-=\sum\limits_{\pi\in\Pi}\mathrm{sgn}(\pi)\pi\in\mathbb{C}[S_{A\uplus B}]$

Now, the problem here is that we’ve written $g_{A,B}$ as if it only depends on the sets $A$ and $B$, when it clearly depends on the choice of the transversal $\Pi$. But we’ll leave this alone for the moment.

How can we come up with an explicit transversal in the first place? Well, consider the set of pairs of sets $(A',B')$ so that $\lvert A'\rvert=\lvert A\rvert$, $\lvert B'\rvert=\lvert B\rvert$, and $A'\uplus B'=A\uplus B$. That is, each $(A',B')$ is another way of breaking the same collection of integers up into two parts of the same sizes as $A$ and $B$.

Any permutation $\pi\in S_{A\uplus B}$ acts on the collection of such pairs of sets in the obvious way, sending $(A',B')$ to $(\pi(A'),\pi(B'))$, which is another such pair. In fact, it’s transitive, since we can always find some $\pi$ with $A'=\pi(A)$ and $B'=\pi(B)$. If for each $(A',B')$ we make just such a choice of $\pi$, then this collection of permutations gives us a transversal!

We can check this by first making sure we have the right number of elements. A pair $(A',B')$ is determined by taking all $\lvert A\uplus B\rvert$ integers and picking $\lvert A\rvert$ to go into $A'$. That is, we have

$\displaystyle\binom{\lvert A\uplus B\rvert}{\lvert A\rvert}=\frac{\lvert A\uplus B\rvert!}{\lvert A\rvert!\lvert B\rvert!}$

pairs. But this is also the number of cosets of $S_A\times S_B$ in $S_{A\uplus B}$!

Do we accidentally get two representatives $\pi$ and $\pi'$ for the same coset? If we did, then we’d have to have $\pi^{-1}\pi'\in S_A\times S_B$. But then $\pi^{-1}\pi'(A,B)=(A,B)$, and thus $\pi'(A,B)=\pi(A,B)$. But we only picked one permutation sending $(A,B)$ to a given pair, so $\pi'=\pi$.

As an example, let $A=\{5,6\}$ and $B=\{2,4\}$. Then we have six pairs of sets to consider

$\displaystyle\begin{array}{ccc}A'&B'&\pi\\\hline\\\{5,6\}&\{2,4\}&e\\\{4,6\}&\{2,5\}&(4\,5)\\\{2,6\}&\{5,4\}&(2\,5)\\\{5,4\}&\{2,6\}&(4\,6)\\\{5,2\}&\{6,4\}&(2\,6)\\\{2,4\}&\{5,6\}&(2\,5)(4\,6)\end{array}$

where in each case I’ve picked a $\pi$ that sends $(A,B)$ to $(A',B')$. This will give us the following Garnir element:

$g_{A,B}=e-(4\,5)-2\,5)-(4\,6)-(2\,6)+(2\,5)(4\,6)$

But, again, this is far from the only possible choice for this $A$ and $B$.

January 14, 2011 -