This question is inspired by classical cryptography, namely transposition ciphers, but it's really a pure problem in permutation groups, which isn't really my field. Suppose k divides n and you consider a "diagonal" embedding of S_k into S_n, namely if you have a cycle (abc...d) in S_k, map it to (abc...d)(a+k b+k c+k ... d+k)...(a+(n-k) b+(n-k) c+(n-k) ... d+(n-k)). For example, S_2 goes into S_6 by (12) goes to (12)(34)(56) and S_3 goes into S_6 by (12) goes to (12)(45), (123) goes to (123)(456), etc.
Now let n be the gcd of k and m and consider the subgroup of S_n generated by the embeddings of S_k and S_m. It's pretty clearly transitive and imprimitive. Is it all of S_n? According to a rather small number of test cases, it seems to work unless k=2, m=3. (Or vice versa, of course.) In that case it generates the copy of S_5 which is transitive in S_6. I'm pretty sure I can reduce the problem to the case where k and m are relatively prime, and I think I have a proof when k=2 and m>3 is odd, but it's pretty ad hoc and I don't really see how it would generalize. (It involves generating a transposition and then apply Jordan's theorem for transitive imprimitive groups.)
Any thoughts? Thanks!
----Josh
if k,m> 5, then it suffice to consider the [(12)_p,(12)_q], the commutator of both images of (12) can be written (aq aq+1 aq+2)(bq bq-1 bq+1) with a and b different. the 6-transitivity will give a 3-cycle so Jordan's theorem apply and one the two images of (12) is of signature -1. Consequently, you get the whole group.
The answer is then yes if 5
Thanks! Yes, I meant lcm. I did work out a proof of my own a month or two ago but yours is shorter.
Yes, but the small k cases require altering the proof somewhat. Basically I worked out an explicit formula for taking an element of the embedding and S_k and an element of the embedding of S_m and generating a 5-cycle. Since the group is imprimitive and transitive, the appropriate version of Jordan's Theorem shows that it has to be all of S_n. For k>=4 and m>=6 you can take the image of (3,4) in S_k and the image of (1,2,3)(4,5) in S_m. For the smaller cases of k and m you can find similar generators although you can also just let a computer find the group by brute force.
Sorry, I forgot to finish the formula. To get the 5-cycle you take the product of the two images and raise it to the 12th power, to annihilate everything except the 5-cycle.
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Materials Science
- Materials Chemistry
- Polymer Chemistry