Mathematical Reflections 2013, Issue 1 - Problem U255

Problem:
Let $S_n$ be the group of permutations of $\{1,2,\ldots,n\}$. If $d > 1$ is an integer, let $H_d$ be the set of those $\sigma \in S_n$ for which there are $k \geq 1$ and $\sigma_1,\ldots,\sigma_k \in S_n$ with $\sigma = \sigma_1^d \cdots \sigma_k^d$. Find $H_2$ and $H_3$.

Proposed by Mihai Piticari and Sorin Radulescu.

Solution:
If $n=1,2$, clearly $H_2=H_3=S_n$. Let $n \geq 3$. We first prove that $H_d$ is a group for every integer $d > 1$. Indeed, if $\sigma, \tau \in H_d$, clearly $\sigma \tau \in H_d$. The associative property follows from the associativite property of the product of permutations. Moreover, $\textrm{id} \in S_n$ and $\textrm{id} = \textrm{id}^d$, so $\textrm{id} \in H_d$ for every $d > 1$. Finally if $\sigma_1,\ldots,\sigma_k \in H_d$ and $\sigma=\sigma_1^d \cdots \sigma_k^d$ for some $k \geq 1$, we have that $\sigma_1^{-1},\ldots,\sigma_k^{-1} \in S_n$ and $\tau=(\sigma_k^{-1})^d\cdots(\sigma_1^{-1})^d$ is the inverse of $\sigma$. Now, let $d=2$. It is clear that $H_2$ is a subgroup of $A_n$ since every permutation in $H_2$ is a product of even permutations and so is an even permutation. For every $a_1,a_2,a_3 \in \{1,\ldots,n\}$, we have also that $(a_1, a_2, a_3)=(a_1, a_3, a_2)^2$ so every $3$-cycle belongs to $H_2$. Since $A_n$ is generated by its $3$-cycles, it follows that $A_n$ is a subgroup of $H_2$, from which $H_2=A_n$. Now, let $d=3$. Obviously, $H_3$ is a subgroup of $S_n$. Moreover, for every $a_1,a_2 \in \{1,\ldots,n\}$ we have $(a_1,a_2)=(a_1,a_2)^3$, so every $2$-cycle belongs to $H_3$. Since $S_n$ is generated by its $2$-cycles, it follows that $S_n$ is a subgroup of $H_3$, which gives $H_3=S_n$.