# For which triples of cycle structures $\alpha,\beta,\gamma$ are there permutations $x,y$ with $C(x),C(y),C(xy)=\alpha,\beta,\gamma?$

This question is motivated by the answer to this one There is also another followup. The question there was " Given integers $m,n,k \gt 1$ construct permutations $x,y$ with $o(x)=m,o(y)=n$ and $o(x,y)=k.$" Derek Holt relates a very elegant solution using $PSL(2,q)$ for suitable odd $q$. It is nice in that it provides a solution quickly albeit not a small or obvious one. He illustrates with $m,n,k=10,12,15$ and comes up with a solution. I tried briefly to understand what was "really" going on from staring at the permutations without refernce to the method which gave them. I did not get very far. I will report that rearranging the underlying set the solution is

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

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

$xy=[[1, 2,\cdots, 15], [16, 17, \cdots, 30], \cdots, [106, 107, \cdots 120]]$

But that says little (to me). To be fair, it was not suggested that $10,12,15$ is a hard case, merely a good one for illustrating the method.

I will ask the specific question in a moment. The underlying questions are: What are the hard cases? When can there be solutions of special kinds? How big must $B$ be to have a solution in $S_B$? The meta question is: What is the right question?

I will say that in the solution above $x,y$ and $xy$ have cycle structures $C(x)=z_{10}^{12},C(y)=z_{12}^{10}$ and $C(xy)=z_{15}^8.$

So I propose the question:

For which triples of cycle structures $\alpha,\beta,\gamma$ are there permutations $x,y$ with $C(x),C(y),C(xy)=\alpha,\beta,\gamma?$

It is an open ended question. If a complete characterization is too much to hope for, then nice sufficient conditions would be ...nice. It is natural to feel that "often" there are solutions which can be written with the integers in the cycles have relatively long runs in order or reverse order. Perhaps with each cycle in $x$ intersecting just one or two of $y.$ That feeling might be mistaken, but when is it not? I will give a few solutions below which I would say have this (vaguely specified) nature.

The example above suggests to me that the perhaps the $PSL(q)$ method establishes that there are always solutions of structure $z_m^i,z_n^j,z_k^{\ell}$ for some $i,j,\ell$. I might be wrong. If not, then perhaps more can be said about $i,j,\ell.$ In this particular case of $m,n,k=10,12,15$ I also find this example with $i,j,\ell=3,1,2.$

$x=$[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [25, 26, 27, 28, 29, 30, 31, 32, 33, 34]]

$y=$ [[1, 11, 21, 22, 23, 24, 25, 34, 33, 32, 31, 16]]

$xy=$[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

I did not find and examples $z_{10}^i,z_{12}^j,z_{15}^{\ell}$ with smaller $i,j,\ell.$

I did find $x=$[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [24, 25, 26, 27, 28, 29, 30, 31, 32, 33]]

$y=$[[1, 11, 12, 13, 14, 15], [16, 17, 18, 19, 20, 21, 22, 23, 24, 33, 32, 31]] with the same $xy.$

Also $x=$[[1, 2, 3, 4, 5, 6, 7, 8, 9, 12]], $y=$[[1, 13, 14, 15], [10, 11, 12]] with

$xy=$[[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]].

And Derek gave the minimal. $x=$[[1, 4, 6, 2, 3], [5, 7]],$y=$ [[1, 4, 2, 7], [6, 5, 8]] with $xy=$[[1,2,3,4,5],[6,7,8]].

-
Some thoughts which turned out not to apply in any useful way when I was thinking about Stefan's followup question, but which might be useful here. Firstly, there are obvious constraints on the total number of elements moved by the C's; if the sum of the number of elements moved by cycle structure $\alpha$ and the number moved by $\beta$ is not at least the number moved by $\gamma$, then certainly there are no solutions. –  ARupinski Jan 5 '13 at 20:06
The second observation, which is probably more useful is in counting the number of elements with cycle structures $\alpha$, $\beta$, and $\gamma$ in some fixed $S_n$. If in this $S_n$ $|\alpha|\cdot|\beta| < |\gamma|$ then there are also no solutions since all elements of structure $\gamma$ are conjugate and hence by conjugacy would lead to decompositions of all such elements. This is probably useful for determining lower bounds on which $S_n$'s such permutations could live in, although I couldn't use it to come up with any counterexamples to Stefan's question (yet). –  ARupinski Jan 5 '13 at 20:09
(Since its a little ambiguous looking now that I reread it, above $|\alpha|$ refers to the size of conjugacy class of structure $\alpha$ in $S_n$) –  ARupinski Jan 5 '13 at 20:10