# Order of products of elements in symmetric groups

Let $$n \in \mathbb{N}$$. Is it true that for any $$a, b, c \in \mathbb{N}$$ satisfying $$1 < a, b, c \leq n-2$$ the symmetric group $${\rm S}_n$$ has elements of order $$a$$ and $$b$$ whose product has order $$c$$?

The assertion is true at least for $$n \leq 10$$, see here.

Update on Sep 2, 2015: On Aug 10, 2015 Joachim König has posted a preprint to the arXiv which gives a positive answer to the question. Assuming that this preprint is correct, this completely answers the question -- and thus also Problem 18.49 in the Kourovka Notebook.

Update on Jun 18, 2014: The assertion is true at least for $$n \leq 50$$, see here (4MB text file).

The list of examples in GAP-readable format can be found here.

Added on Dec 11, 2013: This question will appear as Problem 18.49 in:

Kourovka Notebook: Unsolved Problems in Group Theory. Editors V. D. Mazurov, E. I. Khukhro. 18th Edition, Novosibirsk 2014.

Added on Nov 24, 2013: Is there really not enough known about, say, the class multiplication coefficients of $${\rm S}_n$$ to answer this question?

Text of the question as of Feb 12, 2013:

This question is a follow-up on Order of elements . Derek Holt's answer to that question is nice, but it seems that the degree of the permutations it gives is a lot larger than necessary.

So, given natural numbers $$m, n, k > 1$$, what is the smallest $$d$$ such that the symmetric group of degree $$d$$ has elements of order $$m$$ and $$n$$ whose product has order $$k$$? - Clearly if the largest of the numbers $$m$$, $$n$$, $$k$$ is prime, then $$d$$ must be at least $$\max(m,n,k)$$, and there are some cases where $$d$$ actually must be larger. However a quick computation suggests that $$d = \max(m,n,k) + 2$$ might work always. - But does this or a similar bound hold?

EDIT: Smallest-degree examples for all $$m, n, k \leq 8, m \leq n$$ can be found here.

• An even stronger conjecture would be that it is the smallest $d$ such that there exist permutations $x,y,z∈\in S_d$ of orders $m,n,k$ such that ${\rm sgn}(x){\rm sgn}(y)={\rm sgn}(z)$ (where ${\rm sgn}(x)$ is $1$ and $−1$ for even and odd permutations). Can you find a counterexample to that? Jan 4 '13 at 22:53
• @Derek: I am not sure I understand your question right - depending on $m$, $n$ and $k$, the degree $d$ may of course be smaller than $\max(m,n,k)$. I performed a brief computation and found that for $d = 3, 4, 5, 6, 7, 8 and 10$ your setting permits precisely the same triples (m,n,k), while for $d = 9$, in addition (2,5,20), (2,20,5), (5,5,10), (5,5,12), (5,10,5), (5,12,5) and (5,20,2) occur (this means e.g. that there are permutations $x$, $y$ and $z$ of orders 5, 5 and 12 with sign +1 in $S_9$, but not such that $xy=z$, etc.). Jan 5 '13 at 0:28
• It looks as though my conjecture was over-optimisitic! Jan 5 '13 at 10:10

The main theorem in a paper of G. A. Miller [1] is the following:

THEOREM. If $$l, m, n$$ are any three integers greater than unity, of which we call the greatest $$k$$, it is always possible to find three substitutions $$(L, M, N)$$ of $$k + 2$$ or some smaller number of elements and of orders $$l, m, n$$ respectively such that $$LM=N$$.

Papers [3], [4], [5] by Brenner and Lyndon give a different proof of Miller's result, and consider the problem of finding for $$l,m,n > 1$$ the smallest $$d$$ such that $$S_d$$ contains permutations $$x,y$$ with $$(|x|, |y|, |xy|) = (l,m,n)$$. Other related results are e.g. in [2] and [6].

Papers [8], [9] also give a proof of the theorem by Miller. Also in [7], although it seems without assuming permutations of degree $$\leq \max(l,m,n)+2$$ in some cases.

The main theorem of [10] constructs for $$l,m,n > 1$$ elements $$A,B \in PSL(2,q)$$ (for suitable $$q$$) such that $$|A| = l$$, $$|B| = m$$, and $$|AB| = n$$. The construction pointed out by Derek Holt here is similar but a bit shorter. Yet another construction with matrices is in [11].

References:

[1] MR1505829 G. A. Miller, On the Product of Two Substitutions. Amer. J. Math. 22 (1900), no. 2, 185–190. JSTOR

[2] MR1505882 G. A. Miller, Groups Defined by the Orders of Two Generators and the Order of their Product. Amer. J. Math. 24 (1902), no. 1, 96–100. JSTOR

[3] MR0767585 J. L. Brenner, R. C. Lyndon, A theorem of G. A. Miller on the order of the product of two permutations. I. Jñānābha 14 (1984), 1–16. link

[4] MR0809272 J. L. Brenner, R. C. Lyndon, A theorem of G. A. Miller on the order of the product of two permutations. II. The minimal degree in case a=2. Indian J. Math. 26 (1984), no. 1-3, 105–133 (1985).

[5] MR0748120 J. L. Brenner, R. C. Lyndon, A theorem of G. A. Miller on the order of the product of two permutations. III. The minimal degree in case a>2. Pure Appl. Math. Sci. 20 (1984), no. 1-2, 37–51.

[6] MR0743150 J. L. Brenner, R. C. Lyndon, The orbits of the product of two permutations. European J. Combin. 4 (1983), no. 4, 279–293. DOI

[7] MR0053937 R. H. Fox, On Fenchel's conjecture about F-groups. Mat. Tidsskr. B 1952 (1952), 61–65. JSTOR

[8] MR3508006 J. König, A note on the product of two permutations of prescribed orders. European J. Combin. 57 (2016), 50–56. DOI

[9] MR3694453 J. Pan, On a conjecture about orders of products of elements in the symmetric group. J. Pure Appl. Algebra 222 (2018), no. 2, 291–296. DOI

[10] MR0283093 R. D. Feuer, Torsion-free subgroups of triangle groups. Proc. Amer. Math. Soc. 30 (1971), 235–240. DOI

[11] MR0207852 J. Mennicke, Eine Bemerkung über Fuchssche Gruppen. Invent. Math. 2 (1967), 301–305. DOI

• Wow-- that is indeed a surprise! -- So, König's result is actually a rediscovery of a result found already 116 years before ... . Jul 16 at 9:38
• I guess the paper by Miller has been overlooked. In G. Moran, Of planar Eulerian graphs and permutations. Trans. Amer. Math. Soc. 287 (1985), no. 1, 323–341. the author comments: "Proposition 3.1 was rediscovered several times since 1900. (The author rediscovered it in 1981, in the course of establishing Theorem 1.)" Jul 17 at 3:52

The question has meanwhile been answered in the positive in:

Joachim König, A note on the product of two permutations of prescribed orders. European Journal of Combinatorics 57 (2016), 50-56.

The proof makes a case distinction based on the smallest $$n$$ such that there are elements of given orders $$a \leq b \leq c$$ in the symmetric group on $$n$$ points whose product is the identity:

1. $$n = c$$ is sufficient,

2. $$n = c+1$$ is needed and sufficient, and

3. $$n = c+2$$ is needed.

It analyzes the various subcases, and makes use of Corollary 4.4 and Lemma 4.5 in:

A.L. Edmonds, R.S. Kulkarni, R.E. Stong: Realizability of branched coverings of surfaces. Trans. Amer. Math. Soc. 282(2) (1984), 773--790.

First let me paraphrase the question. Given integers $m,n,k$ each at least 2, set $d:=\max(m,n,k)+2$. Do there exist elements $a,b$ in the symmetric group $S_d$ such that $|a|=m$, $|b|=n$ and $|ab|=k$?

It is convenient to write $c=ab$. A simple argument shows that we can assume $m\leq n\leq k$ and $d=k+2$. [The equation $b*a=bcb^{-1}$ shows we can swap $m$ and $n$ as $|bcb^{-1}|=k$. The equation $a^{-1}c=b$ shows we can swap $n$ and $k$ as $|a^{-1}|=m$. Thus we may assume $m\leq n\leq k$.]

It is easy to prove the result for small cases such as $m=n=2$. With these simple ideas Stefan's table of data can be simplified, and extended. It seems that there may be results already in the literature. Can an expert help? What about the special case when $m,n,k$ are each powers of the same prime?