Assume that $\sigma\in S_n$ has the cycle type $(p,.,p,1,..,1)$ where $p>2$ is a prime and the numbers of $1$ maybe $0$. If $\sigma_1$ and $\sigma_2$ are chosen uniformly in the conjugacy class of $\sigma$. Assume the cycle type of $\sigma_1 \sigma_2=(k_1,k_2,.,k_l)$ . Is there a lower bound $B$ such that $$\mathrm{Pr}\big(\exists j\in \{1,2,..,l\}, \text{ s.t. } k_j \bmod 2=0\big)\geq B \geq 1/T(n),$$ where $T$ is a polynomial.

  • 1
    $\begingroup$ You are asking for the probability that $\sigma_1\sigma_2$ has even order. I conjecture that it is smallest when $\sigma$ has only one $p$-cycle and is at least $cp/n$ for some constant $c$. Proof? You want proof? $\endgroup$ Commented Feb 27, 2023 at 11:36
  • $\begingroup$ yes, I need a proof $\endgroup$ Commented Feb 28, 2023 at 1:32

1 Answer 1


Let $kp$ be the size of the support of $\sigma$. Let $1,2,3,4$ be four points of the ground set. The probability that $\sigma_1$ maps $1 \mapsto 2$ is $kp/n(n-1)$, because there is a $kp/n$ chance that $1$ is in the support and conditionally a $1/(n-1)$ chance that $1 \mapsto 2$. Conditional on that, the probability that $3$ is in the support is $(kp-2)/(n-2)$ and then a $1/(n-2)$ chance that $3 \mapsto 4$ (because $3$ can map to anything apart from $2$ and $3$). Therefore the probability that $\sigma_1$ maps $1\mapsto2$ and $3 \mapsto4$ is $kp(kp-2)/n(n-1)(n-2)^2 \ge 1/n^4$. Likewise the probability that $\sigma_2$ maps $2 \mapsto 3$ and $4 \mapsto 1$ is also at least $1/n^4$. The probability that both these happen is at least $1/n^8$ and in this case $\sigma_1\sigma_2$ has a $2$-cycle.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.