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.
$\begingroup$
$\endgroup$
2
-
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$– Brendan McKayCommented Feb 27, 2023 at 11:36
-
$\begingroup$ yes, I need a proof $\endgroup$– constantineCommented Feb 28, 2023 at 1:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
