1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Subgroups of Sn containing Sn-1

  1. Nov 13, 2012 #1
    I want to show that the only subgroups of Sn (the symmetric group of n elements) containing Sn-1 are Sn and Sn-1. So essentially, all that's needed to be checked is that there is no subgroup of order greater than (n-1)!, the order of Sn-1 and less than n!, the order of Sn. I was first thinking that if there did exist such a subgroup of Sn, then it would contradict Lagrange's theorem, as then (n-1)! would not divide the order of said subgroup. However, that fails for large enough n, as the said subgroup may have order (n-1)*k, where 2<=k<n. Any ideas? Or should I just try a different approach? Can induction work here?
     
  2. jcsd
  3. Nov 13, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't think Lagrange's theorem is going to work here.

    Try to prove that if you have [itex]S_{n-1}[/itex] and if you add an arbitrary other element of [itex]S_n[/itex], then that generates entire [itex]S_n[/itex].
    So, for example, what you can show is how to form all other elements of [itex]S_n[/itex] using just [itex]S_{n-1}[/itex] and the arbitrary other element.

    Things you might want to look at is theorems that say things like "this collection of elements generates [itex]S_n[/itex]". Do you know such things?
     
  4. Nov 13, 2012 #3
    I don't know of such theorems. Are you perchance hinting to the set of generators or the set of orbits of Sn?

    But I'm thinking that if you take an element in Sn, call it sigma_n that's not in Sn-1, then it must shift the position of the nth element in the set (1,...,n), since if it were in Sn-1, then it could permute elements in the set (1,...,n-1), but would have to leave n in its place. Now, sigma_n can do whatever it pleases to the elements of (1,...,n-1), and I get that the composition of sigma_n with elements of Sn-1 would give you some elements of Sn, but what guarantees that we would get ALL elements of Sn?
     
  5. Nov 13, 2012 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Ah, that is a nice approach. So indeed, an element f of [itex]S_{n-1}[/itex] has the property that [itex]f(n)=n[/itex].
    Now, we are given a specific element g such that [itex]g(n)\neq n[/itex]. We want to see if we can write any element in [itex]S_n[/itex] using [itex]S_{n-1}[/itex] and g.

    Thus: take [itex]h\in S_n[/itex] arbitrary. Can you find [itex]f,f^\prime\in S_{n-1}[/itex] such that [itex]h=fgf^\prime[/itex] (I claim we can always write h in that form). Think about what must happen if you apply both h and fgf' on the element n and on 1,...,n-1.
     
  6. Nov 13, 2012 #5
    I don't know how to find such f,f', but my first guess was to define f inverse as f' and f as h restricted to the set (1,...,n-1), but I don't know if that actually works. But the equation you gave reminds me of conjugates. Are you trying to prove that h and g are conjugates? Or am I completely off? Also, I found a theorem saying that any element of Sn can be written as a product of transpositions. Does that help here?
     
  7. Nov 13, 2012 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I wouldn't think about conjugates. Just try to think about what f,g and f' should be. For example, apply both h and fgf' to n. What can you conclude?

    Perhaps. We'll see.
     
  8. Nov 13, 2012 #7
    Ok. Either h(n) = n or not. If h(n) = n, then h is in Sn-1, in which case I don't know what g should be, as g(n) not equal to n, and regardless of what f and f' are, fgf'(n) won't equal n, which is a problem (but maybe you just disregard g completely in this case).
    Suppose h(n) not equal to n. Then g(k) = k and f(k) = h(k), for 1<=k<=n-1. And f' can just be the identity. I think in that case, h = fgf'. I see no problem with this approach, besides the fact that g is chosen very specifically. Is that allowed? If not, could I just define f(k) = h(g inverse (k)) for all 1<=k<=n-1. If so, why the need for f' at all?
     
  9. Nov 13, 2012 #8

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    The goal is to write every element in [itex]S_n[/itex] as a product of elements in [itex]S_{n-1}[/itex] and the specific element g. But if h is in [itex]S_{n-1}[/itex] then this can be done trivially. So in this case, we don't need to look at h=fgf'.

    But g is a fixed element that you add to [itex]S_{n-1}[/itex]. The elements h and g are fixed, and you need to find f and f'.
     
  10. Nov 13, 2012 #9
    I still don't see why both f anf f' are needed. But doesn't defining f(k) = h°g^-1(k) for all 1<=k<=n-1 work? If f' is really necessary, it can be the identity, so h = f°g°f'
     
  11. Nov 13, 2012 #10

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Is [itex]hg^{-1}[/itex] in [itex]S_{n-1}[/itex]?
     
  12. Nov 13, 2012 #11
    As it is restricted (can only permute the first n-1 elements), I think it is in Sn-1. But I think that since f is in Sn-1, f(n) = n. But g(n) ≠ n, so (f°g)(n) = n, which is not what we want, as h(n) ≠ n. But I think that one of f and f' should be a transposition (perhaps of order 2?) and the other should be some sort of a rotation (for the lack of a better term) (perhaps of order n?). Am I inching closer to the right track, or going away from it?
     
  13. Nov 13, 2012 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You're getting closer, I think.
     
  14. Nov 13, 2012 #13
    I now see the importance of f. Since g(n)≠n, g(n) = p for some 1≤p≤n-1. Similarly, h(n) = q for some 1≤q≤n-1. Since we have freedom to choose f, we can define it such that f(p) = q. Now, if f' is the identity (I still don't see its importance), then h(n) = (f°g°f')(n). Similarly, we can define (f°g)(t) = h(t) for all 1≤t≤n-1. Is there a flaw in this?
     
  15. Nov 13, 2012 #14

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Does this also work for the t such that [itex]g(t)=n[/itex]??
     
  16. Nov 13, 2012 #15
    I did consider this situation, but didn't at first think it would be problematic. But clearly, h(t) doesn't have to equal n. and now f' would be useful. But I'm still not sure how to do so. Any hints on how to proceed?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook