Let $\sigma,\tau\in S_n$ be two $n$-cycles. When does $\langle\sigma\rangle\cap\langle\tau\rangle=1$? Note that $\sigma$ and $\tau$ are conjugate in $S_n$ and WLOG we may assume $\sigma = (1,2,\dots,n)$ and $\tau = \sigma^g$ for some $g\in S_n$. I need to find the number of $g$ in $S_n$ such that $\langle\sigma\rangle\cap\langle\sigma^g\rangle=1$.
In particular, I'm now focusing the case when $n+1$ is a Fermat prime, and hence $n$ is a power of $2$.
Is there any methods to deal with this problem for $n+1$ to be a Fermat prime or even for general $n$?
Best Answer
If $\sigma^k$ is a power of $\tau$, then so is $\sigma^j$ if $\gcd(j,n)=\gcd(k,n)$, that is, if $\sigma^k$ and $\sigma^j$ are of the same order. Thus we can divide the powers of $\sigma$ and $\tau$ into equivalence classes according to their order and use $\sigma^\frac nd$ and $\tau^\frac nd$ as representatives of the powers of order $d$. So for each $d\mid n$ we need to count the permutations $\tau$ for which $\tau^\frac nd=\sigma^\frac nd$.
$\sigma^\frac nd$ consists of $\frac nd$ cycles of length $d$. Write $\sigma=(1\sigma_2\sigma_3\cdots\sigma_n)$ in cycle notation, and likewise $\tau=(1\tau_2\tau_3\cdots\tau_n)$. Then the cycles are formed by the sets of elements $\frac nd$ apart, so these must coincide as a whole. Within the cycle notation for $\tau$, these sets can be permuted in $\left(\frac nd-1\right)!$ ways, the cycles themselves can be one of $\phi(d)$ powers of those in $\sigma$, and their position in $\tau$ can be chosen in $d^{\frac nd-1}$ ways, for a total of
$$ \left(\frac nd-1\right)!\phi(d)d^{\frac nd-1}\;. $$
Of course if $\tau^\frac nd=\sigma^\frac nd$, this is also true with any multiple of $\frac nd$ in the exponent, so we need to perform inclusion–exclusion on the divisor lattice of $n$ to count every $\tau$ exactly once. This yields
$$ |\{\tau\mid\langle\sigma\rangle\cap\langle\tau\rangle=\{1\}\}|=\sum_{d\mid n}\mu(d)\left(\frac nd-1\right)!\phi(d)d^{\frac nd-1}\;, $$
where $\mu$ is the Möbius function. Denoting by $P$ the set of primes that divide $n$ and by $\pi_D$ the product $\prod_{p\in D}p$, we can also write this as
$$ \sum_{D\subseteq P}(-1)^{|D|}\left(\frac n{\pi_D}-1\right)!\phi\left(\pi_D\right)\pi_D^{\frac n{\pi_D}-1} \\= \sum_{D\subseteq P}(-1)^{|D|}\left(\frac n{\pi_D}-1\right)!\prod_{p\in D}(p-1)\pi_D^{\frac n{\pi_D}-1}\;. $$
For instance, for $n=6$ this is
$$ (6-1)!\cdot1\cdot1^{6-1}-(3-1)!\cdot1\cdot2^{3-1}-(2-1)!\cdot2\cdot3^{2-1}+(1-1)!\cdot2\cdot6^{1-1}=108\;, $$
and for $n=12$ it is
$$ (12-1)!\cdot1\cdot1^{12-1}-(6-1)!\cdot1\cdot2^{6-1}-(4-1)!\cdot2\cdot3^{4-1}+(2-1)!\cdot2\cdot6^{2-1}=39912648\;, $$
which is all except for $4152$ of the $11!$ cycles of length $12$.
For $n$ a power of $2$ (greater than $1$), the result is just
$$ (n-1)!-\left(\frac n2-1\right)!\cdot2^{\frac n2-1}\;. $$