From: Ken.Pledger@vuw.ac.nz (Ken Pledger) Subject: Re: injective homomorphisms G-> S_n for small n Date: Thu, 03 Feb 2000 17:11:48 +1200 Newsgroups: sci.math Summary: [missing] In article <87abc5$5mm$1@nnrp1.deja.com>, David Bernier wrote: > Suppose G is a finite group and we are looking for a small integer > n such that the symmetric group S_n contains a subgroup isomorphic > to G.... > What techniques or theorems apply to this problem?.... There's a standard theory of permutation representations of groups, which is in various text-books, although I can't find an easy reference right now. The quick answer to your question is that G must have a subgroup H such that (1) the index |G:H| = n, and (2) the normal interior of H (i.e. the intersection of all its conjugates, which is the largest normal subgroup of G inside H) contains only the identity element. The basic idea is to permute the set {Ha, Hb, ...} of right cosets of H in G by multiplying each on the right by an element x of G. That permutation is then the image of x under the homomorphism you're looking for. The kernel of the homomorphism is the normal interior of H. Ken Pledger. ============================================================================== From: mareg@mimosa.csv.warwick.ac.uk () Subject: Re: injective homomorphisms G-> S_n for small n Date: 3 Feb 2000 10:24:42 GMT Newsgroups: sci.math In article <87abc5$5mm$1@nnrp1.deja.com>, David Bernier writes: >Suppose G is a finite group and we are looking for a small integer >n such that the symmetric group S_n contains a subgroup isomorphic >to G. If G is isomorphic to H, where H is a subgroup of S_n, >then the order of H divides the order of S_n, which is n! . >So we have that the order of G divides n! . This condition >is necessary. I believe it is sufficient for >ord(G)< 6. The group Z_6 has elements of order 6; S_3 has none >and neither does S_4. Z_6 is isomorphic to a subgroup of >S_5 generated by a 2-cycle plus a 3-cycle permutation in S_5. >What techniques or theorems apply to this problem? > >David Bernier This is a difficult problem, and a familiar one in computational group theory, where it arises frequently. A low degree permutation representation of the group is often the most convenient one for detailed structural computation. One of the difficulties is that you need some sort of representation to begin with in order to even start looking systematically for a low degree one. This can awkward if your group is given by a generator/relations presentation, for example. Sometimes the only possible approach is to start with a large degree representation and then try to reduce it by looking at actions on blocks of imprimitivity for example. You can either look for an intransitive or a transitive representation. If you can find two disjoint proper nontrivial normal subgroups N1 and N2, then a good general approach is to solve the problem first for the smaller groups G/N1 and G/N2, find faithful representations of them of degrees d1 and d2 say, and then combine these to give a faithful intransitive representation of G of degree d1+d2. Otherwise, suppose there is a unique minimal normal subgroup N. Then you need to look for a transitive representation of G, which means finding a subgroup H of G as large as possiblke subject to H not containing N. (Then the representation on the cosets of H will be faithful.) You should distinguish between the cases N abelian and nonabelian. In the nonabelian case, N is a direct product of isomorphic simple groups permutated transitively by G. The maximal subgroups of such groups are well understood, and the problem can be effectively reduced to the case where N is simple, for which a huge amount of research has been done. The N abelian case is harder in practice. If the extension splits, you might try a complement (although that will not always be the minimal degree representation.) If not, you have to start searching through the subgroups H/N of G/N, looking for instances where there is a supplement H' not containing N with NH' = H. Derek Holt.