On the proportion of elements of order a product of two primes in finite symmetric groups

1.   Introduction

The famous Cayley theorem reveals a basic fact: A finite group $G$ of order $n$ is isomorphic to a subgroup of the finite symmetric group ${{{\rm{S}}}}_n$. This means that $G$ can be given as a group generated by a set $M$ of permutations in ${{{\rm{S}}}}_n$, that is, $G = \langle M\rangle$. To construct a generating set of $G$, we need to seek special kinds of elements in ${{{\rm{S}}}}_n$, which are usually sought randomly. Further, to understand the complexity of such searches, we need to estimate the proportions of various kinds of elements, such as those with order $p$, $2p$, or $pq$ in ${{{\rm{S}}}}_n$ for the odd primes $p$ and $q$. For examples, a transposition is constructed by searching for an element $g$ of order $2m$ in ${{{\rm{S}}}}_n$ for some odd positive integer $m\leq n^{18\log n}$; see ^[1]. The upper bound for $m$ is chosen so that the proportion of such elements is large enough to find such an element $g$ with high probability, and also to construct the transposition $g^m$ at a reasonable cost. This method is better than a direct search for a transposition by examining random elements, as the proportion of transpositions is very small. The proportion of elements with order a multiple of $p$ in ${{{\rm{S}}}}_n$, called $p$-singular elements, is far greater than the proportion of elements with order $p$; see [9, Section 1]. This means that constructing elements of order $p$ by taking powers of $p$-singular elements is much more efficient than searching for such elements directly by random selection.

The proportion of elements of a given prime order $p$ in finite symmetric groups has been extensively studied. For example, in ^[4], Jacabsthal gave recursive formulas and an asymptotic expansion on this proportion for the first time. Chowla, Herstein, and Scott ^[2] and Moser and Wyman ^[6] extended Jacabsthal's result in 1952 and 1955, respectively. In 2022, Praeger and Suleiman ^[9] gave an explicit upper bound on the proportion of permutations of a given prime order $p$ in finite symmetric groups. More results can be found in ^[3,7,8].

In fact, a product of disjoint 2-cycles and $p$-cycles is a permutation of order $2p$. But we note that a permutation of order $2p$ may be obtained by other cycles, such as $2p$-cycles, a product of disjoint $2p$-cycles and $p$-cycles, or 2-cycles, and so on. In 2024, the first and third authors in ^[5] addressed an upper bound on the proportion of permutations of twice a prime order, acting on a set of given size $n$. In this paper, we generalize the result in ^[5] and present an upper bound for the elements that have order a product of two distinct odd primes in finite symmetric groups.

This paper is organized as follows: After this introduction, we give some preliminary results in Section 2. Then, the main result is given and proved in Section 3. Finally, we make a conjecture on the proportion of elements with a given order in finite symmetric groups in Section 4.

2.   Preliminaries

In this section, we give a lemma and several propositions, which will be used to prove our main result in the next section.

Let $m$ be a positive integer, and let $[m] = \{1, 2, \cdots, m \}$ and ${{{\rm{S}}}}_m$ be the symmetric group on $[m]$. First, we record a basic fact.

Lemma 2.1. For each positive integer $m$, there are exactly $(m-1)!$ pairwise distinct m-cycles in ${{{\rm{S}}}}_m$.

Proof. Each $m$-cycle in ${{{\rm{S}}}}_m$ has a unique expression of the form $(\alpha_1, \alpha_2, \cdots, \alpha_m)$ where $\alpha_i\in[m] = \{1, 2, \cdots, m \}$ for $1\leq i\leq m$ and $\alpha_j = 1$ for some $j\in [m]$. To count the number of possibilities for the $m$-cycles, there are exactly $m-1$ choices for $\alpha_1\in [m]\backslash \{1\}$, and exactly $m-2$ choices for $\alpha_2$ from $[m]\backslash \{1, \alpha_1\}$ when $\alpha_1$ is gven, and so on. This implies that there are exactly $(m-1)!$ $m$-cycles in ${{{\rm{S}}}}_m$. ■

For two distinct odd primes $p$ and $q$, the element $g$ of order $pq$ in ${{{\rm{S}}}}_n$ can be written out explicitly in one of the following forms:

$({\rm{I}})$ $\underbrace{\overbrace{(\cdots)}^{p-cycle}\overbrace{(\cdots)}^{p-cycle}\cdots\overbrace{(\cdots)}^{p-cycle}}_{s_1} \underbrace{\overbrace{(\cdots)}^{q-cycle}\overbrace{(\cdots)}^{q-cycle}\cdots\overbrace{(\cdots)}^{q-cycle}}_{t_2}$;

$({\rm{II}})$ $\underbrace{\overbrace{(\cdots)}^{pq-cycle}\overbrace{(\cdots)}^{pq-cycle}\cdots\overbrace{(\cdots)}^{pq-cycle}}_{s_2}$;

$({\rm{III}})$ $\underbrace{\overbrace{(\cdots)}^{p-cycle}\overbrace{(\cdots)}^{p-cycle}\cdots\overbrace{(\cdots)}^{p-cycle}}_{s_3} \underbrace{\overbrace{(\cdots)}^{pq-cycle}\overbrace{(\cdots)}^{pq-cycle}\cdots\overbrace{(\cdots)}^{pq-cycle}}_{t_3}$;

$({\rm{IV}})$ $\underbrace{\overbrace{(\cdots)}^{q-cycle}\overbrace{(\cdots)}^{q-cycle}\cdots\overbrace{(\cdots)}^{q-cycle}}_{s_4} \underbrace{\overbrace{(\cdots)}^{pq-cycle}\overbrace{(\cdots)}^{pq-cycle}\cdots\overbrace{(\cdots)}^{pq-cycle}}_{t_4}$; or

$({\rm{V}})$ $\underbrace{\overbrace{(\cdots)}^{p-cycle}\overbrace{(\cdots)}^{p-cycle}\cdots\overbrace{(\cdots)}^{p-cycle}}_{s_5} \underbrace{\overbrace{(\cdots)}^{q-cycle}\overbrace{(\cdots)}^{q-cycle}\cdots\overbrace{(\cdots)}^{q-cycle}}_{t_5} \underbrace{\overbrace{(\cdots)}^{pq-cycle}\overbrace{(\cdots)}^{pq-cycle}\cdots\overbrace{(\cdots)}^{pq-cycle}}_m$;

where $s_i\geq1$, $t_j\geq1$ for $1\leq i\leq5$, $2\leq j\leq5$, and $m\geq1$.

Second, we find an upper bound on the proportion of elements in each form above. Let $\mathcal{P}_n(pq)$ and $\mathcal{P}_n^{*}(pq)$ denote the set consisting of all the elements of order $pq$, and the set of elements with form (*) in ${{{\rm{S}}}}_n$, respectively, where * is one of ${\rm{I}}, {\rm{II}}, \ldots, {\rm{V}}$ above. The corresponding proportions are denoted by $\rho_{n}(pq) = \frac{|\mathcal{P}_n(pq)|}{n!}$ and $\rho_{n}^{*}(pq) = \frac{|\mathcal{P}_n^{*}(pq)|}{n!}$, respectively. In order to prove Theorem 3.1, we need the following recursion for $\rho_{n}^{*}(pq)$.

Proposition 2.1. Let $p$ and $q$ be distinct odd primes such that $p < q$. Let $n$ be a positive integer. Then the proportion $\rho_{n}^{*}(pq)$ of elements with the form (*) as above in ${{{\rm{S}}}}_n$ satisfies the following relations:

(1) If $* = I$ and $n\geq p+q+1$, then

(2) If $* = II$ and $n\geq pq+1$, then

(3) If $* = III$ and $n\geq pq+p+1$, then

(4) If $* = IV$ and $n\geq pq+q+1$, then

(5) If $* = V$ and $n\geq pq+p+q+1$, then

Proof. (1) We partition $\mathcal{P}_n^{I}(pq)$ as ${_1}\mathcal{P}_n^{I}(pq)\cup {_2}\mathcal{P}_n^{I}(pq)$, where $_{1}\mathcal{P}_n^{I}(pq)$ and $_{2}\mathcal{P}_n^{I}(pq)$ consist of all elements $g\in\mathcal{P}_n^{I}(pq)$ such that $1^g = 1$ and $1^g\neq1$, respectively. We observe that $_{1}\mathcal{P}_n^{I}(pq)$ is precisely the set of elements having form (I) in ${{{\rm{S}}}}_{\Delta}\cong{{{\rm{S}}}}_{n-1}$ where $\Delta = [n]\backslash\{1\}$, and hence $|_{1}\mathcal{P}_n^{I}(pq)| = (n-1)!\rho_{n-1}^{I}(pq)$.

Now we enumerate the elements of ${_2}\mathcal{P}_n^{I}(pq)$. Since $1^g\neq1$, $1$ lies in a cycle $h$ of $g$ of length $p$ or $q$ for each such element $g$.

Case 1. $h$ is a $p$-cycle.

The number of such cycles is equal to the number $\tbinom{n-1}{p-1}$ of subsets $\Delta^{'}$ of $(p-1)$-element subsets of $\Delta\backslash\{1\}$, times the number $(p-1)!$ of $p$-cycles in ${{{\rm{S}}}}_n$ by Lemma 2.1. Then, for each of $g\in{_2}\mathcal{P}_n^{I}(pq)$, $g = hg^{'}$ where $g^{'}\in {{{\rm{S}}}}_{[n]\backslash\{\Delta^{'}, 1\}}\cong{{{\rm{S}}}}_{n-p}$. The number of such elements $g^{'}$ is equal to the number $|\mathcal{P}_{n-p}^{I}(pq)| = (n - p)!\rho_{n-p}^{I}(pq)$ of elements with the form $(I)$ in ${{{\rm{S}}}}_{n-p}$, together with the number $|\mathcal{P}_{n-p}(q)| = (n - p)!\rho_{n-p}(q)$ of elements of order $q$ in ${{{\rm{S}}}}_{n-p}$. Thus

Case 2. $h$ is a $q$-cycle.

The number of such cycles is equal to the number $\tbinom{n-1}{q-1}$ of subsets $\Delta^{'}$ of $(q-1)$-element subsets of $\Delta\backslash\{1\}$, times the number $(q-1)!$ of $q$-cycles in ${{{\rm{S}}}}_n$ by Lemma 2.1. Then, for each of $g\in{_2}\mathcal{P}_n^{I}(pq)$, $g = hg^{'}$ where $g^{'}\in {{{\rm{S}}}}_{[n]\backslash\{\Delta^{'}, 1\}}\cong{{{\rm{S}}}}_{n-q}$. The number of such elements $g^{'}$ is equal to the number $|\mathcal{P}_{n-q}^{I}(pq)| = (n - q)!\rho_{n-q}^{I}(pq)$ of elements with the form $(I)$ in ${{{\rm{S}}}}_{n-q}$, together with the number $|\mathcal{P}_{n-q}(p)| = (n - q)!\rho_{n-q}(p)$ of elements of order $p$ in ${{{\rm{S}}}}_{n-q}$. Thus

It follows that

and so $n\rho_{n}^{I}(pq) = \rho_{n-1}^{I}(pq)+\rho_{n-p}^{I}(pq)+\rho_{n-p}(q)+\rho_{n-q}^{I}(pq)+\rho_{n-q}(p)$. This completes the proof of (1).

For (2) to (5), the proofs are analogous to the proof of (1). ■

Next, we will use Proposition 2.1 to give an upper bound on $\rho_{n}^{*}(pq)$ by induction on $n$, where $*\in \{I, II, \ldots, V\}$.

Proposition 2.2. Let $p$ and $q$ be distinct odd primes such that $p < q$, and let $n$ be a positive integer. Write $n = a\cdot pq+k$, where $a\geq0$ and $0\leq k\leq pq-1$. Then

(1) $\rho_{n}^{I}(pq)\leq\frac{1}{pq}$ with equality if and only if $n = p+q$ or $p+q+1$;

(2) $\rho_{n}^{II}(pq)\leq\frac{1}{pq\cdot k!}$ with equality if and only if $pq\leq n \leq 2pq-1$;

(3) $\rho_{n}^{III}(pq)\leq\frac{1}{p^2q}$ with equality if and only if $n = 2p+q$ or $2p+q+1$;

(4) $\rho_{n}^{IV}(pq)\leq\frac{1}{pq^2}$ with equality if and only if $n = 2q+p$ or $2q+p+1$;

(5) $\rho_{n}^{V}(pq)\leq\frac{1}{p^2q^2}$ with equality if and only if $n = 2(q+p)$ or $2(q+p)+1$.

Proof. (1) If $n < p+q$, then $\mathcal{P}_{n}^{I}(pq)$ is empty, and so $\rho_{n}^{I}(pq) = 0$. If $n = p+q$, then $|\mathcal{P}_{n}^{I}(pq)| = \frac{n!}{pq}$, and so $\rho_{n}^{I}(pq) = \frac{1}{pq}$. We now assume that $n\geq p+q+1$ and assume inductively that the result holds for all positive integers strictly less than $n$.

Case 1. $n = p+q+k$, and $1\leq k\leq 3$.

By induction, we have $\rho_{n-1}^{I}(pq) = \frac{1}{pq\cdot (k-1)!}$, $\rho_{n-p}^{I}(pq) = 0$ and $\rho_{n-q}^{I}(pq) = 0$, and we note that $\rho_{n-p}(q)\leq\frac{1}{q}$ and $\rho_{n-q}(p)\leq\frac{1}{p}$ by [9, Theorem 1]. Thus, by Proposition 2.1 (1),

with equality if and only if $n = p+q+1$.

Case 2. $n > p+q+3$.

By induction, we observe that $\rho_{n-1}^{I}(pq)\leq\frac{1}{pq}$, $\rho_{n-p}^{I}(pq)\leq\frac{1}{pq}$ and $\rho_{n-q}^{I}(pq)\leq\frac{1}{pq}$, and we see that $\rho_{n-p}(q)\leq\frac{1}{q}$ and $\rho_{n-q}(p)\leq\frac{1}{p}$ by [9, Theorem 1]. Thus, by Proposition 2.1 (1),

So we complete the proof of (1) by induction.

(2) If $n < pq$, then $\rho_{n}^{II}(pq) = 0$. If $n = pq$, then $\rho_{n}^{II}(pq) = \frac{1}{pq}$. We now assume that $n\geq pq+1$ and assume inductively that the result holds for all positive integers strictly less than $n$.

Note that $n-pq = (a-1)\cdot pq+k$, $n-1 = a\cdot pq+k-1$ if $1\leq k\leq pq-1$, and $n-1 = (a-1)\cdot pq+pq-1$ if $k = 0$.

Case 1. $a = 1$.

By induction, $\rho_{n-1}^{II}(pq) = \frac{1}{pq\cdot(k-1)!}$ and $\rho_{n-pq}^{II}(pq) = 0$. Then, by Proposition 2.1 (2),

Case 2. $a\geq2$.

If $k = 0$, then by induction, $\rho_{n-1}^{II}(pq)\leq\frac{1}{pq\cdot(pq-1)!}$ and $\rho_{n-2p}^{II}(pq)\leq\frac{1}{pq}$. So by Proposition 2.1 (2),

If $k\geq1$, then by induction, $\rho_{n-1}^{II}(pq)\leq\frac{1}{pq\cdot(k-1)!}$ and $\rho_{n-pq}^{II}(pq)\leq\frac{1}{pq\cdot k!}$. Thus, by Proposition 2.1 (2),

and this completes the proof of (2) by induction.

With techniques similar to those in (1) and (2), we can obtain the conclusions of (3) to (5). ■

3.   Main result and proof

We present the main result and use Proposition 2.2 to prove it in this section. Our main result is as follows:

Theorem 3.1. Let $n$ be a positive integer, and let $p$ and $q$ be odd primes such that $p < q$, and write $n = a\cdot pq +k$, where $0\leq k\leq pq-1$ and $a\geq 0$. Let $\rho_{n}(pq)$ be the proportion of elements of order $pq$ in the symmetric group ${{{\rm{S}}}}_n$. Then one of the following holds:

(1) $n < p+q$, $\rho_n(pq) = 0$;

(2) $p+q\leq n\leq pq-1$, $\rho_{n}(pq)\leq\frac{1}{pq}$, with equality if and only if $n = p+q$ or $p+q+1$;

(3) $pq\leq n\leq pq+p-1$, $\rho_{n}(pq) < \frac{1+k!}{pq\cdot k!}$;

(4) $pq+p \leq n \leq pq+q-1$, $\rho_{n}(pq) < \frac{p+(p+1)k!}{p^2q\cdot k!}$;

(5) $pq+q \leq n \leq pq+q+p-1$, $\rho_{n}(pq) < \frac{pq+(pq+p+q)k!}{p^2q^2 \cdot k!}$;

(6) $n\geq pq+p+q$, $\rho_{n}(pq) < \frac{pq+(pq+p+q+1)k!}{p^2q^2 \cdot k!}$.

Proof. Let $n$ be a positive integer and $p$ and $q$ odd primes with $p < q$, and write $n = a\cdot pq +k$ where $0\leq k\leq pq-1$ and $a\geq 0$.

If $n < p+q$, then $\mathcal{P}_n(pq)$ is empty, and so $\rho_n(pq) = 0$. Therefore, (1) holds.

If $p+q\leq n\leq pq-1$, then $\mathcal{P}_n(pq) = \mathcal{P}^{I}_n(pq)$, and thus $\rho_n(pq) = \rho_{n}^{I}(pq)\leq\frac{1}{pq}$ with equality if and only if $n = p+q$ or $p+q+1$ by Proposition 2.2 (1). Hence, (2) holds.

If $pq\leq n\leq pq+p-1$, then $\mathcal{P}_n(pq) = \mathcal{P}^{I}_n(pq)+\mathcal{P}^{II}_n(pq)$, and so $\rho_n(pq) = \rho_{n}^{I}(pq)+\rho_{n}^{II}(pq) < \frac{1}{pq}+\frac{1}{pq\cdot k!} = \frac{1+k!}{pq\cdot k!}$ by Propositions 2.2 (1) and (2). Thus, (3) holds.

If $pq+p \leq n \leq pq+q-1$, then $\mathcal{P}_n(pq) = \mathcal{P}^{I}_n(pq)+\mathcal{P}^{II}_n(pq)+\mathcal{P}^{III}_n(pq)$, and thus $\rho_{n}(pq) < \frac{1}{pq}+\frac{1}{pq\cdot k!}+\frac{1}{p^2q} = \frac{p+(p+1)k!}{p^2q\cdot k!}$ by Proposition 2.2 (1) to (3). So (4) holds.

If $pq+q \leq n \leq pq+q+p-1$, then $\mathcal{P}_n(pq) = \mathcal{P}^{I}_n(pq)+\mathcal{P}^{II}_n(pq)+\mathcal{P}^{III}_n(pq)+\mathcal{P}^{IV}_n(pq)$, and thus $\rho_{n}(pq) < \frac{1}{pq}+\frac{1}{pq\cdot k!}+\frac{1}{p^2q}+\frac{1}{pq^2} = \frac{pq+(pq+p+q)k!}{p^2q^2 \cdot k!}$ by Proposition 2.2 (1) to (4). Therefore, (5) holds.

If $pq+p+q\leq n$, then $\mathcal{P}_n(pq) = \mathcal{P}^{I}_n(pq)+\mathcal{P}^{II}_n(pq)+\mathcal{P}^{III}_n(pq)+\mathcal{P}^{IV}_n(pq)+\mathcal{P}^{V}_n(pq)$, and so $\rho_{n}(pq) < \frac{1}{pq}+\frac{1}{pq\cdot k!}+\frac{1}{p^2q}+\frac{1}{pq^2}+\frac{1}{p^2q^2} = \frac{pq+(pq+p+q+1)k!}{p^2q^2 \cdot k!}$ by Proposition 2.2 (1) to (5). Thus, (6) holds. ■

4.   Conclusions

We note that the upper bound of (1) and (2) is sharp in Theorem 3.1, but that in (3) to (6) it is not. Besides, from the results in Theorem 3.1 on the proportion of elements of order twice distinct odd primes in finite symmetric groups, we observe that the upper bound of the proportion is a function $f$ defined on $[pq-1] = \{0, 1, 2, \cdots, pq-1\}$. With this in mind, we make the following conjecture:

Conjecture 4.1. The proportion $\rho_{n}(m)$ of elements of order $m$ in ${{{\rm{S}}}}_n$ is controlled by a function $f$ defined on $[m-1] = \{0, 1, 2, \cdots, m-1\}$.

Author contributions

Hailin Liu, Longzhi Lu and Liping Zhong: Writing-Original Draft, Writing-Review and Editing. All authors contributed equally to the manuscript. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was partially supported by China Scholarship Council (Grant No.202208360148), National Natural Science Foundation of China (Grant No.12126415, NO.12261042, NO.12301026) and Jiangxi Provincial Natural Science Foundation (Grant No.20232BAB211006).

Conflict of interest

All authors declare no conflicts of interest in this paper.