1
$\begingroup$

Let $G \leq S_n$ be a permutation group. Also let $G^{(i)}, 1 \leq i \leq n$ be the subgroups of permutation whic fix elements $1,2,\cdots i$. Then $G= G^{(0)} = (G^{(0)}/G^{(1)}) (G^{(1)}/G^{(2)}) \cdots (G^{(n-1)}/G^{(n)})$ (product of quotients) I am trying to understand the matter at page 37 of $\href{http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4567802&tag=1}{this}$ paper. How do we prove this.

enter image description here

  • 1
    It may be not a good idea to choose that notation $\,G^{(i)}\,$ ,as it is already in use for something very different within group theory (the derived groups). Besides this, in order to talk of *quotient groups*, we must have *normal* subgroups...but these are **not** normal subgroups: for example, with $$n=3\,\,,\,\,G^{(1)}=\{(1)\,,\,(23)\}\rlap{\;/}\triangleleft G^{(0)}=S_3\,\,...$$2012-08-27
  • 0
    @DonAntonio I have added reference to the question, please help me understand that part. Please edit the question to make it appropriate, based on the ref.2012-08-27
  • 0
    Sorry @Durga, I've no access to that paper now. If you can download it somewhere and make accessible to everybody that'd be great.2012-08-27
  • 0
    @DonAntonio I can download and keep in accessible place, but are there any copyright issues?2012-08-27
  • 0
    I don't know, yet if you download it for personal use I don't think there's any problem...but I'm not sure.2012-08-27
  • 0
    I added a monochrome bitmap image of that page. I hope this is not a serious breach of IEEE copyright.2012-08-27
  • 0
    @Don Antonio: You may be right about $G^{(i)}$ not being a good choice of notation, but I am afraid that it has become standard in the computational theory of permutation groups. It was used by Charles Sims, who first introduced the ideas of bases and strong generating sets.2012-08-27
  • 0
    @DerekHolt, thanks for the info. I didn't know that.2012-08-27

2 Answers 2

4

My interpretation is that they mean the following:

  1. By $G^{(i)}/G^{(i+1)}$ they mean a set of representatives of cosets of $G^{(i+1)}$ in $G^{(i)}$. With a view of reducing any confusion I will select, once and for all, such sets of representatives, and denote them by $D_i$, $i=0,1,\ldots$. Note that they are not subgroups of $G$ (or groups at all).
  2. The decomposition that troubles the OP means the following. Let $g$ be an arbitrary element of $G$. Then it can be written in a unique way as $$ g=d_0d_1d_2\cdots d_{n-1}, $$ where $d_i\in D_i$ for all indices $i$.

This follows more or less immediately from the definitions. The given element $g\in G$ belongs to a unique coset of the subgroup $G^{(1)}$, so we can write $$ g=d_0g_1, $$ where $d_0\in D_0$ and $g_1\in G^{(1)}$. We can then proceed, because $g_1$ belongs to a unique coset of $G^{(2)}$, and can thus be written (in a unique way) as a product $g_1=d_1g_2$, where $d_1\in D_1$ and $g_2\in G^{(2)}$. Clearly we can continue to do this. The uniqueness of the end result also follows from the fact that "tail part" of such a product, $d_jd_{j+1}\cdots d_{n-1}$ clearly belongs to the subgroup $G^{(j-1)}$.

  • 0
    +1 Excellent interpretation to an otherwise pretty confussing text. I agree that's what the author must have meant.2012-08-27
0

Note the following: the author does not prove or note that the $G^{(i)}$ are normal. I therefore think that he does not talk about proper quotient groups, but rather some kind of left quotient that he does not properly define.

However, whatever he is talking about, if it is a true statement we can probably prove it by induction.

The theorem is trivial for $n=1$.

For the induction step, we know that $G^{(1)}\cong(G^{(1)}/G^{(2)}) \times \cdots \times (G^{(n-1)}/G^{(n)})$. Prove that $G\cong(G/G^{(1)})\times G^{(1)}$ (whatever this $G/G^{(1)}$ is).

Now, if $G$ is abelian, all subgroups are normal, and then we can use the "normal" defition of quotient groups, but this is not assumed by the author.

  • 0
    This is wrong: $\,G^{(1)}\,$ is not a normal subgroup of $\,G\,$ so $\,G/G^{(1)}\, $ is meaningless...2012-08-27
  • 0
    Can you agree with my modified version?2012-08-27
  • 0
    indeed. Yet I think Jyrki's version is right on the money and without any need of normality or abelianity, which can be quite an issue when dealing with permutation groups.2012-08-27
  • 0
    Agreed, I'll leave this in place for reference.2012-08-27