# Proof of the fact that the set of (p,q) shuffles is a cross section of the subgroup $S_p\times S_q$

Definition Let $G$ be a group and $H$ its subgroup. We name a subset $K$ of $G$ a cross section if it has exactly one element from each left coset of $G/H$.

Definition Let $n=p+q$ for some positive integers $p,q.$ A permutation $\sigma\in S_n$ is called $(p,q)$ shuffle if $$\sigma(1)<\sigma(2)\dots<\sigma(p)\hspace{5pt}\text{and}\hspace{5pt}\sigma(p+1)<\sigma(p+2)\dots<\sigma(p+q)$$ and the set of all $(p,q)$ shuffles is denoted by $S(p,q).$

Theorem Let $n=p+q$ for some positive integers $p,q.$ Consider the subgroup of $S_n$, such that leaves invariant first $p$ and last $q$ places, and denoted it abuse the language by $S_p\times S_q.$ That is $$\sigma\in S_p\times S_q \iff \sigma(\{1,2,\dots,p\})=\{1,2,\dots,p\} \\\text{and}\hspace{5pt}\sigma(\{p+1,p+2,\dots,p+q\})=\{p+1,p+2,\dots,p+q\}.$$ We claim that the set $S(p,q)$ is a cross section of $S_p\times S_q.$

In literature this fact is said to be obvious [1] or left as an exercise [2]. I have no idea how to grasp it.

[1] Bishop, Crittenden, Geometry of Manifolds, 1964, p. 58

[2] Spivak, A Comprehensive Introduction to Differential Geometry, vol. 1, 1999, p. 227

Let's think about $S(p, q)$ and $S_p \times S_q$.

$S(p, q)$ has $\binom{p+q}{p}$ elements. Think of $n$ adjacent slots: we have to choose $p$ of them to put the first $p$ in order, and afterwards the $q$ remaining elements must go in the consecutive remaining slots. $S_p \times S_q$ has $p!q!$ many elements: $p!$ permutations of the first $p$ elements and $q!$ permutations of the last two. Of course, $S_n = S_{p+q}$ has $(p+q)!$ elements.

Notice that $\frac{|S_n|}{|S_p \times S_q|} = |S(p,q)|$. So the number of left cosets of $S_p \times S_q$ in $S_n$ equals the number of elements in $S(p,q)$.

The two sets only have one element in common, the identity.

Now, if you can show that for each $\sigma_1, \sigma_2 \in S(p, q)$, the cosets $(\sigma_1)(S_p \times S_q)$ and $(\sigma_2)(S_p \times S_q)$ are distinct, then you are in business.

EDIT:

Since cosets are either identical or disjoint, we need only that $$(\sigma_1)(S_p \times S_q) - (\sigma_2)(S_p \times S_q)$$ is non-empty. To do so, we argue it contains $\sigma_1$.

For the sake of contradiction, suppose $\sigma_1 \in (\sigma_2)(S_p \times S_q)$. Thus, there exists $\sigma \in S_p \times S_q$ such that $\sigma_1 = \sigma_2 \sigma$. By assumption, $\sigma_2 \neq \sigma_1$, hence $\sigma \neq e$. Consider some cycle of order $m$ in $\sigma$.

Let $k \in \{1, ..., p + q\}$ be the largest element in the cycle. Then

$$\sigma_1 k = \sigma_2 \sigma k < \sigma_2 k = \sigma_2 \sigma^m k = \sigma_1 \sigma^{m - 1} k$$

$$\implies \sigma_1 k < \sigma_1 \sigma^{m - 1} k$$

But $\{k, \sigma^{m - 1} k \}$ is either a subset of $\{1, ..., p\}$ or $\{p + 1, ..., p + q\}$, and $\sigma_1$ preserves the order of elements in those subsets. This is the contradiction we set out to find:

$$\sigma^{m-1} k < k \wedge \sigma_1 \sigma^{m - 1} k > \sigma_1 k$$

Hence, $\sigma_1 \not\in (\sigma_2)(S_p \times S_q)$, and the two cosets are therefore disjoint.

• I believe I have moderated intuition, but I stuck with proving two sentences you said. I mean "The two sets only have one element in common, the identity." and "Now, if you can show that for each σ1,σ2∈S(p,q), the cosets (σ1)(Sp×Sq) and (σ2)(Sp×Sq) are distinct, then you are in business." Those are ones I can't handle. – Fallen Apart Dec 17 '14 at 23:42
• Consider $S_p \times S_q \cap S(p,q)$. Any element (permutation) in this must set keep the first $p$ elements in the first $p$ slots and the last $q$ elements in the last $q$ slots, AND (!) it must keep the the elements ordered! So it has to put the first $p$ elements in the first $p$ slots in order, and the same with the last $q$. So it is the identity! – A.E Dec 17 '14 at 23:47
• Next, recall that two cosets are either identical or disjoint. So argue that every coset produced by an element $\sigma \in S(p,q)$ is unique. – A.E Dec 17 '14 at 23:52
• Since the $|S(p,q)| =$ the number of left cosets of $S_p \times S_q$, and each determines a unique coset, so it is a cross section of $S_p \times S_q$. – A.E Dec 17 '14 at 23:53
• At the beginning I misunderstood your way of thinking. Now I see that it is cleaver cause it reduces to showing that (σ1)(Sp×Sq) and (σ2)(Sp×Sq) are distinct insted of showing that (σ1)(Sp×Sq) and (σ2)(Sp×Sq) are disjoint. But still I can't cope with showing that (σ1)(Sp×Sq) and (σ2)(Sp×Sq) are distinct. – Fallen Apart Dec 20 '14 at 16:41