2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$ – Fallen Apart Dec 17 '14 at 23:42
  • $\begingroup$ 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! $\endgroup$ – A.E Dec 17 '14 at 23:47
  • $\begingroup$ 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. $\endgroup$ – A.E Dec 17 '14 at 23:52
  • $\begingroup$ 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$. $\endgroup$ – A.E Dec 17 '14 at 23:53
  • $\begingroup$ 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. $\endgroup$ – Fallen Apart Dec 20 '14 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.