Orders of Elements in Symmetric Groups

Question

We define the symmetric group $S_n$ to be the set of all permutations of the first $n$ natural numbers. Moreover, we define the set $T_n$ as the set of all possible orders of elements in $S_n$ i.e.

$$T_n=\{ \space|\sigma| \mid \sigma \in S_n \}$$

We are interested in studying the set $T_n$.

---

First, we can start by observing when $x \in T_n$, given positive integers $x$ and $n$. Clearly, $x=1$ is an element of $T_n$ for any $n \in \mathbb{N}$ since the identity permutation has order $1$. For $x>1$, let the prime factorization of $x$ be: $$x=\prod_{i=1}^k p_i^{a_i}$$ Assume that a permutation $\sigma \in S_n$ has order $x$. Let the unique cycle decomposition (with cycles of length $1$ ignored) of $\sigma$ be: $$\sigma=\prod_{j=1}^t C_j$$ We have $x=|\sigma|=\text{lcm}(|C_1|,|C_2|,\ldots,|C_t|)$. Using this equation, we can show that for every $1 \leqslant i \leqslant k$, there exists some $1 \leqslant j \leqslant t$ such that $p_i^{a_i} \mid |C_j|$. This implies that $p_i^{a_i} \leqslant |C_j|$. Moreover, if we have multiple prime powers, say $p_1^{a_1}, p_2^{a_2}, \ldots ,p_i^{a_i}$ (WLOG a list of $i$ prime powers) all dividing $|C_j|$, we can see that: $$p_1^{a_1}p_2^{a_2}\cdots p_i^{a_i} \mid |C_j| \implies p_1^{a_1}+p_2^{a_2}+\cdots+p_i^{a_i} < p_1^{a_1}p_2^{a_2}\cdots p_i^{a_i} \leqslant |C_j|$$

This tells us that: $$\sum_{i=1}^k p_i^{a_i} \leqslant \sum_{j=1}^t |C_j| \leqslant n \implies \sum_{i=1}^k p_i^{a_i} \leqslant n$$

However, one can see that this is a sufficient condition for the existence of a permutation $\sigma$ as we can set $k=t$ and $|C_i|=p_i^{a_i}$ for all $1 \leqslant i \leqslant k$. Thus: $$x \in T_n \iff \sum_{i=1}^k p_i^{a_i} \leqslant n$$

---

We can see that the sum of the prime powers in the factorization of numbers is relevant in studying $T_n$. Thus, we define: $$f \bigg( \prod_{i=1}^k p_i^{a_i} \bigg) = \sum_{i=1}^k p_i^{a_i}$$

One result we can deduce using this function is showing that the only exception to $|T_n|>|T_{n-1}|$ for $n>2$ is $n=6$. Clearly, we can see from above that: $$|T_n|>|T_{n-1}| \iff \exists \space x \in \mathbb{N} \text{ such that } f(x)=n$$

We can check that $n=1,6$ are the only exceptions till $n<11$. For $n \geqslant 11$, we prove by induction hypothesis. We assume that $1$ and $6$ are the only exceptions until $n-1$. As $11$ is the second Ramanujam prime, we have: $$\pi(n)-\pi \bigg(\frac{n}{2} \bigg) \geqslant 2$$

So, let two primes in the interval $\bigg(\frac{n}{2},n \bigg]$ be $p$ and $q$. Clearly, $n-p$ and $n-q$ are not simultaneously $1$ and $6$ due to parity. WLOG, let $n-p \neq 1,6$. We have: $$f(x)=n-p \implies f(px)=n$$ Note that $p \nmid x$ as $p>n-p$. Thus, we have concluded that $|T_n|>|T_{n-1}|$ for $n>2, n\neq6$.

---

We can see that the observation of $f(x)$ gives us better insight on the set $T_n$. I have the following questions:

$1.$ What is the average order of $f(x)$? Can we write an asymptotic expression for the same?

$2.$ Is there an asymptotic expression for $|T_n|$? Can we say anything about the same using the function $f(x)$?

Answer 1

Let us consider all of the primes $p_i$ that could appear in one of the orders $\mathcal{T}_n$ in order to approximate $T_n \overset{\text{def}}{=} |\mathcal{T}_n|$. It is straight forward to see that a necessary and sufficient condition for this to occur is that $\log_{p_i}(n)\geq 1$; more generally for prime power $p_i^k$ a necessary and sufficient condition is that $\log_{p_i^k}(n)\geq 1$. Let us denote this set of primes as \begin{equation} \mathcal{S}_n \overset{\text{def}}{=} \{ p_i \in \mathbb{P} \ | \ p_i\leq n \}. \end{equation} From the set $\mathcal {S}_n$ we can define a set of integer partitions that will give us the exact value of $T_n$; indeed if we let \begin{equation} \mathcal{P}_n \overset{\text{def}}{=} \left\{ y = \sum_{x \in S} x^{e_i} \ \Bigg| \ S \subset\mathcal{S}_n ,\ y \leq n , \ e_i \in \mathbb{N}_{>0} \right\} \end{equation} then we have the equality $T_n = P_n \overset{\text{def}}{=} |\mathcal{P}_n|$. The beautiful thing is that $P_n$ can be enumerated by taking the following generating function \begin{equation} \mathcal{F}_n (x) = \prod_{p \in \mathcal{S}_n}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right) \end{equation} and summing up the first $n$ coefficients $F_i$ see sec.5.3 of Chen & Khee Meng for generating function techniques for partitions. In other words if we let \begin{equation} F_m = [x^m]\mathcal{F}_n (x) = [x^m] \prod_{p \in \mathcal{S}_n}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right) \end{equation} where $F_m = [x^m]\mathcal{F}_n (x) $ is defined by the relation \begin{equation} \mathcal{F}_n (x) = \sum_{k \in \mathbb{N}}F_kx^k \end{equation} then we have that \begin{equation} T_n = P_n = \sum_{k \leq n}F_k. \end{equation} While Flajolet and Sedgewick contains a wealth of methods for asymptotic approximations (which you definitely should look into) we can already try to get a rough approximation that is computationally feasible.

For simplicity let \begin{equation} \mathcal{S}_n^{<\omega} \overset{\text{def}}{=} \{ p_i^l \leq n \ | \ p_i \in \mathcal{S} \}.\end{equation}

We know that asymptoticly we have the following approximation $p_k \sim k\log k $ and therefore (by Sterling's approximation) that if $k$ is the largest number satisfying $\log k! \leq n $ then it is approximately equal the largest prime smaller than $n$; furthermore remembering the original constraint on the exponents we also have
\begin{equation} \log^l k! \leq n \implies \log^l k! \in \mathcal{S}_n^{<\omega} \end{equation} and also that \begin{equation} \log^l k! \leq n \implies l \leq \frac{\log n}{\log \log k!} \end{equation} Therefore we can approximate $F_n $ as \begin{equation} \mathcal{F}_n (x) = \prod_{p \in \mathcal{S}_n}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right) \sim \prod_{\log k! \leq n}\left(1+\sum_{l \leq \frac{\log n}{\log \log k!} }x^{\log^l k!}\right). \end{equation} Defining $F^*_m$ as follows \begin{equation} F^*_m = [x^m] \mathcal{F}^{*}_n (x) = [x^m]\prod_{\log k! \leq n}\left(1+\sum_{l \leq \frac{\log n}{\log \log k!} }x^{ \log^l k!}\right), \end{equation} we can get a fast approximation for $T_n$ as \begin{equation} T_n \approx \sum_{i\leq n} F_i^* \end{equation} and seeing as the equivalnce of the enumeration problem you asked for is essentially reduced to a difficult problem I doubt there will be a simple closed form solution (but you might be able to find better approximations).

Good luck on your mathematical adventures young padawan! Bon Voyage!

Explicit derivation of the generating function The user Angela has brought it my attention that there is another generating function $\mathcal{T}(x) = \frac{1}{1-z}\prod_{p : \text{ prime}}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right)$ given in this link to the OEIS. This is in fact equivalent to the solution given here, lest us give a proof.

(Proof): The first thing to notice is that the generating function \begin{equation} \mathcal{F}_n (x) = \prod_{p \in \mathcal{S}_n}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right) = (1+x^2+x^4+...)(1+x^3+x^9+ ...) (1+x^5+...)... \end{equation} is the sequence counts the number of ways as representing any $k \leq n$ as a sum of distinct prime powers. To see the reason why just interepret multiplication as an and and the addition as an or see "On Picture-Writing" by Gearge Polya. So that for example $[x^5]\mathcal{F}_n(x)$ will be equal to $2$ because one can only choose $x^2$ and $x^3$ from the first two products or choose $x^5$ from the third product to get exponents that add up to the exponent $x^5$. The point of replacing $p : \text{ prime}$ with $p \in \mathcal{S}_n$ is that when you actually go to compute the generating function you can only perform a finite number of operations. The question post by Haran essentially contains a proof of the fact that $\sum_{k\leq n}F_k = T_n$. Therefore using the relation \begin{equation} \frac{1}{1-x}\mathcal{A}(x) = \sum_{n \in \mathbb{N}}\left(\sum_{k \leq n} a_k\right )x^n \end{equation} we get that \begin{equation} \mathcal{T} (x) = \frac{1}{1-x}\prod_{p : \text{ prime}}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right), \end{equation} but if we are only interested in the terms up until $n$ (which is what you are going to have to do in practice) you can just use \begin{equation} \mathcal{T}_n (x) = \frac{1}{1-x}\prod_{p \in \mathcal{S}_n}\left(1+\sum_{l \in \mathbb{N}}x^{p^l}\right). \end{equation} QED