Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider natural numbers $m,n,k > 1$. There are finite groups $G$ containing elements $x,y$ such that $o(x) = m, o(y) = n$ and $o(xy) = k$. After embedding these groups in $S_\mathbb{N}$ we drive: Given $m,n,k >1$ there are $f,g \in S_\mathbb{N}$ such that $o(f) = m, o(g) = n$ and $o(fg)=k$. This argument shows the existence of $f,g$. But how to construct such permutations $f,g$ in $S_\mathbb{N}$ in terms of $m$, $n$ and $k$ ?

share|improve this question
2  
I don't think this is really a research-level question,as the solution involves playing around with basic properties of permutations... One can write $x$ in cycle-notation, and then construct $y$ so that it `links together' different cycles of $x$ to give the right order for $xy$. Tricky, but elementary I guess. –  Nick Gill Jan 4 '13 at 10:17
5  
@Nick: Don't agree. That depends on what we have in mind about research-level. Besides I think the tricky part (as you mentioned) is not ordinary. –  Ivan Jan 4 '13 at 10:50
1  
@Ivan: Given the complexity of Derek's (excellent) answer, I reckon you've got a point. –  Nick Gill Jan 4 '13 at 14:12
3  
@Ivan and Nick: Indeed. -- Given that there are open problems which on a first glance look too elementary even to be posed as student questions, I would be very careful to attribute a question as "not research-level" unless I know the answer. –  Stefan Kohl Jan 4 '13 at 17:02
4  
This is the famous "r-s-t" problem assigned to first year graduate students at the University of Chicago out of Alperin-Bell, which intentionally contains many highly nontrivial problems mixed among the easy ones, older grad students are sworn to secrecy as to which are which. We all spent hours trying to solve it inside the symmetric group using multiple different special cases. Only one or two students in history were known to get it correct, and it is easier to do inside PSL. It saddens me to see the answer posted here. –  daveh Jan 4 '13 at 17:26
show 1 more comment

1 Answer

It is not hard in practice, at least for reasonably small values of $m,n,k$, to find permutations with the required property, and I did once convince myself that I could find a systematic way of doing it, but it was very messy and hard to describe.

Here is one way to do it, which will not produce permutations of optimally small degree, but which is at least easy to describe and even to do on a computer using GAP or Magma if you want to.

We will produce our permutations as elements of ${\rm PSL}(2,q)$ for suitable odd $q$. We do this by finding elements $X,Y \in {\rm SL}(2,q)$ of orders $2m,2n$ with product of order $2k$, and use their images in ${\rm PSL}(2,q)$. We make use of the fact that, for elements of ${\rm SL}(2,q)$ with order greater than 2 and dividing $q^2-1$, their order is detmined by their trace.

It is easiest to do if you choose $q$ such that $q-1$ is divisible by all of $2l,2m,2k$. We can assume that $m,n,k$ are all greater than 1. Let $ \lambda,\mu $ be primitive $ 2m^{\mathrm{th}} $, $ 2n^{\mathrm{th}} $ roots of unity in the field ${\mathbb F}_q$ of order $q$. Let

$ A = \left( \begin{array}{cc} \lambda & 0 \\ 1 & \lambda^{-1} \end{array} \right) $ and $ B = \left( \begin{array}{cc} \mu & \alpha \\ 0 & \mu^{-1} \end{array} \right) $, for some $ \alpha $. So $ |A| = 2m $ and $ |B| = 2n $. Now $ AB = \left( \begin{array}{cc} \lambda\mu & \lambda\alpha \\ \mu & \alpha + \lambda^{-1}\mu^{-1} \end{array} \right) $ and $ {\rm Tr}(AB) = \lambda \mu + \alpha + \lambda^{-1} \mu^{-1} $. Let $ t $ be the trace of an element of $ S $ of order $ 2k $, and choose $ \alpha = t - \lambda\mu - \lambda^{-1}\mu^{-1} $. Then $ |AB| = 2k $.

As an example, I tried $m,n,k = 10,12,15$ with $q=121$, and took $\lambda=w^6$, $\mu=w^5$, $\alpha=w^4+w^{-4}-w^{11}-w^{-11}$, with $w$ a primitive field element. Then, using Magma to project onto ${\rm PSL}(2,121)$, I got the following permutations $x,y \in S_{122}$ with $(|x|,|y|,|xy|) = (10,12,15)$.

$x=$ (2, 105, 31, 119, 44, 29, 107, 98, 58, 120)(3, 36, 24, 18, 48, 12, 54, 30, 42, 60)(4, 19, 72, 87, 38, 117, 33, 102, 41, 66)(5, 73, 79, 104, 49, 56, 45, 118, 112, 69)(7, 57, 91, 67, 106, 109, 101, 50, 46, 114)(8, 103, 64, 81, 74, 21, 43, 40, 35, 77)(9, 32, 89, 34, 84, 65, 61, 47, 116, 80)(10, 26, 82, 17, 27, 94, 100, 70, 76, 99)(11, 37, 93, 83, 39, 52, 108, 14, 86, 68)(13, 75, 121, 22, 78, 23, 110, 97, 62, 113)(15, 85, 63, 92, 55, 122, 115, 95, 59, 16)(20, 25, 96, 28, 71, 88, 90, 111, 51, 53)

$y=$ (1, 95, 18, 77, 29, 118, 22, 71, 39, 80, 38, 67)(2, 99, 65, 119, 41, 102, 89, 51, 75, 113, 70, 53)(4, 103, 74, 86, 106, 37, 10, 7, 88, 97, 66, 90)(5, 115, 109, 47, 112, 61, 31, 78, 57, 98, 121, 15)(6, 87, 91, 26, 63, 60, 43, 120, 73, 13, 20, 68)(8, 35, 12, 76, 114, 46, 104, 94, 32, 45, 48, 34)(9, 122, 72, 59, 23, 62, 101, 30, 50, 64, 42, 33)(11, 107, 108, 40, 69, 117, 21, 49, 27, 58, 17, 19)(14, 56, 36, 54, 116, 25, 85, 79, 84, 81, 55, 83)(16, 92, 93, 110, 100, 44, 52, 24, 82, 111, 96, 105).

Added later: I should perhaps add that by starting with elements $x,y \in S_8$ with orders 10,12, and replacing $y$ by random conjugates, I rapidly found a solution in $S_8$: $x=(1,2,3,4,5)(6,7)$, $y=(1,2,4,7)(3,6,8)$, so I would guess that some kind of reasonably intelligent random algorithm is the best way to solve this in practice.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.