Question:
Let $(G;.)$ a finite no commutative group. Find that an upper bound that to the probability that two element $X,Y$ of $G$ randomly chosen with an uniforme probability (that means the probability to pick one specific element of $G$ is $1/|G| $) commute is $\leq 5/8$
Answer:
I/Let's define the following sub set of $G$:
$S_1=\left \{ x \in G \; s.t. \; \forall y \in G \Rightarrow x.y=y.x\right \}$ = the set of all the elements of $G$ that commute with all the other elements of $G$
$S_{2 (x)} = \left \{ y \in G \; s.t. \; x.y=y.x\right \}$ = for a given $x$, $S_{2(x)}$ is the set of all the element $y\in G$ that commutes with $x$. Please remark that this set depends of $x$.
This two set are sub group of $G$ (will not writte the proof here but it's by definition).
II/Moreover we should note that it exists at least one element $x' \in G$ that does not commute with all the element of $G$ and so $x' \notin S_1$ (if such element doesn't exist $G$ will be a comutative group). More than that all the element in $S_1$ commute with $x'$ by definition. So they are all in $S_{2(x')} \Rightarrow S_1 \subset S_{2(x')} \subset G$.
Now as $S_{2(x')} \subset G$ and $S_{2(x')}$ is too a group $\Rightarrow |S_{2(x')}|\leq |G|/2$.
Same argument for $S_1$ (which is a sub group too) $\Rightarrow |S_1|\leq|S_{2(x')}|/2\Rightarrow|S_1|\leq |G| /4$
III/ Now let majorate the probability:
$\mathbb{P}(X.Y=Y.X)=\mathbb{P}( \left \{X \in S_1 \cup Y \in S_1 \right \} \cup \left \{Y\in S_{2(x)} \cup X\in S_{2(y)} \right \} )\leq ????$
explanation of the event: X and Y commutes= if the X we picked commutes with all the other elements of G OR if the Y we picked commutes with all the other elements of G OR if the Y we picked belong to all the element in G that commutes with the X we picked OR if the X we picked belong to all the element in G that commutes with the Y we picked
But here i am stuck. I ve tried different ways (exclusion principle, re writte the probability via conditional probability... but maybe trying this i ve made mistakes) to majorate this probability (above) but i never succeed to get $5/8$. Can someone please help me to conclude?
Thank a lot.
PS: i ven't any special knowledge in algebra as i got this question in a probability book.
You wrote everything you need from the algebraic part, except that you need to show that $|S_1| \leq |G|/4$ in more details - more specifically, that you can't have situation when $S_1 = S_{2(x')}$ for all $x'$ (or see this question to directly get $|S_1| \leq |G| / 4$).
The important part is that center is at most $1/4$ of the group, and elements not from center don't commutate with at least $1/2$ of the group.
We have $$P(x.y \neq y.x) \\= P(y \not \in S_2(x)) \geq P(y \not \in S_2(x) \wedge x \not \in S_1) \\ = P(x \not \in S_1) \cdot P(y \not \in S_{2(x)} | x \not \in S_1) \\ \geq \frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}$$
Thus $P(x.y = y.x) = 1 - P(x.y \neq y.x) \leq \frac{5}{8}$.