# Decomposition of a permutation giving cycles of equal lengtth

When trying to solve another question I bumped upon the followin situation with the following setup:

• an odd integer $n$.
• the cycle $c = (1,\ldots,n)$ generating the cyclic group $C_n$.
• the automorphism group $H$ of $C_n$ that decomposes depending on the factorization of n into powers of primes.

The following action on the set $\{1,\ldots,n\}$ can be constructed by the maps $$n_u : i \mapsto 1 + u(i-1)\mod n \text{ where } i \in \{1,2,\ldots,n\} \text{ and } \gcd(u,n) = 1$$ That this represents the automorphism group $H$ is shown by the fact that $c^u = c^{n_u}$.

Now let $p^k$ be one of the prime power factors of $n$, i.e. $n = p^km$ with $\gcd(p, m) = 1$. Then $H = C_{\varphi(p^k)} \times M$, for some abelian subgroup $M$. The group $C_{\varphi(p^k)}$ can be obtained by restricting the $u$ to the condition $u = 1 \mod(m)$. Let $K$ be the subgroup of order $p-1$ of $C_{\varphi(p^k)}$. In all the several dozen of cases I tried the permutations of $K$ all decompose in cycles that have all the same size. I can show that the number of points left fixed by $K$ is $m$ (namely $1, p^5, 2p^k, \ldots, mp^k$). So the moved points of $K$ is $p^km-m=(p^k-1)m$. This is a multiple of $p-1$ so I was inclined to reason as follows : if a permutation $p \in K$ of order $r$ has a cycle of length a divisor of $r$ then the number of moved points is compromised but this fails since there could be several such cycles to compensate for the number of moved points.

My question is : can it be proven that the cycles have the same length or is there a counter example?

Example Let $n = 5^3$ so, $c = (1,\ldots,125)$ Then $H = C_4 \times C_{25}$. The group $C_{25}$ is generated by $n_{63}$ but the cycle composition of this consists of three cycles of order $100, 20, 4$ respectively. On the other hand the group $C_4$ is generated by $n_{38}$ whose cycle decomposition consists of $31 = 5^2+5+1$ cycles all of length $4$ (no cycles of order $2$ occurring).

• Isn't this equivalent to the (true) statement that the automorphism of $C_{p^k}$ of order $p-1$ acts semiregularly on $C_{p^k} \setminus \{1\}$? Or, equivalently, nontrivial automorphism of $C_{p^k}$ of order dividing $p-1$ (i.e. coprime to $p$) can fix any non-identity element of $C_{p^k}$? Commented Mar 13, 2017 at 21:21
• @DerekHolt: the solution of this problem is the keystone to the proof of your experimental statement in this question. But I dont's see why the abstract group structure intervenes with a particular action in a permutation representation. I'll edit my question with an example. Commented Mar 13, 2017 at 23:00
• If some nontrivial orbit of $K= \langle g \rangle$ had length a proper divisor $d$ of $p-1$, then $g^d$ would fix more than $m$ points, which means that $g^d$ would centralize a subgroup of $C_n$ or order larger than $m$ and hence it would centralize some nontrivial subgroup of $C_{p^k}$. But the automorphism of $C_{p_k}$ of order $p-1$ acts semiregularly. Commented Mar 13, 2017 at 23:23
• @DerekHolt: I'm not quite following what is $K, g$? and semiregular? and what if $(p-1)/d$ cycles of order d are present? Doesn't this restore the number of points fixed? Commented Mar 13, 2017 at 23:31
• You defined $K$ yourself as the subgroup of $C_{\phi(p^k)}$ of order $p-1$, and I am taking $g$ to be a generator of $K$. So if $K$ has orbits of length $d$, then the points in these orbits are fixed points of $g^d$ So then$g^d$ would have more than $m$ fixed points. Commented Mar 14, 2017 at 0:28

Thanks to the comments of Derek Holt I found following proof of the assertion in the question. Let $L = C_{p^{k-1}}$ be such that $C_{\varphi(p^k)} = K \times L$. It is not hard to figure out that the elements $n_u \in L$ are such that $u \mod(p) = 1$. So if $n_u \in K$ then $u$ satisfies $u = km+1$ where $k$ and $p$ are coprime. To see for which $i$ we have $n_u(i) = i$ we have to solve $$1 + (km+1)(i-1) - i = 0 \mod (n) \iff km(i-1) = 0 \mod(p^km)$$ $$\text{ dividing m out } \iff k(i-1) = 0 \mod(p^k) \iff (i-1) = lp^k \iff i = lp^k+1$$ So the elements fixed by all permutations of $K$ are $1, p^k, 2p^k, \ldots, mp^k$. So there are $m$ fixed points. For a generator of $g \in K$, with order $p-1$ all the cycles have the size $p-1$, otherwise if there is a cycle of order $d$ a divisor of $p-1$ then the d-cycle disappears and its moved points become fixed points making the total number of fixed points $>m$.