Suppose \( G \) is a nonabelian finite group. A fun question to ask is is `what is the probability that two elements of \( G \), selected at random with replacement, commute?' Let's denote this probability by \(\Pr(G)\). A nice folklore result, first recorded (I think) by Gustafson in a note in 1973, says: Theorem: \(\Pr(G) \leq \frac{5}{8}\). To prove this we can use the following fundamental fact: Lemma: \(\Pr(G) = \frac{k(G)}{|G|}\) where \(k(G)\) is the number of conjugacy classes in \(G\). Proof: First, note that \[ \Pr(G) = \frac{|\{(x,y) \mid x,y \in G, xy=yx \}|}{|G|^2}. \] Let \[ C = \{ (a,b) \in G \times G \mid ab=ba \}.\] If we fix \(x \in G\), then the number of elements in \(C\) of the form \((x,y)\) is \(|C_G(x)|\), where \(C_G(x)\) is the centraliser of the element \(x\) in \(G\). So, \[ |C| = \sum_{x \in G} |C_G(x)| .\] Now, let \(x_1, \ldots, x_k\) be representatives of the \(k=k(G)\) conjugacy classes in \(G\). If \(x\) is conjugate to \(y\) in \(G\), then \(C_G(x)\) and \(C_G(y)\) are conjugate subgroups and so \(|C_G(x)|=|C_G(y)|\). So, since \(|x^G| = |G : C_G(x)|\), we have \[ \begin{align*} |C| &= \sum_{i=1}^k |x_i^G| \cdot |C_G(x_i)| \\\\ &= \sum_{i=1}^k |G : C_G(x_i)| \cdot |C_G(x_i)|\\\\ &= \sum_{i=1}^k \frac{|G|}{|C_G(x_i)|} \cdot |C_G(x_i)| = k \cdot |G|. \end{align*} \] So, \[ \Pr(G) = \frac{|C|}{|G|^2} = \frac{k(G) \cdot |G|}{|G|^2} = \frac{k(G)}{|G|}. \] Now, to prove Gustafson's result, note that the class equation says that \[ |G| = |Z| + |K_1| + \cdots + |K_t| \] where \(|Z|\) is the centre of \(G\) and the \(K_i\) are the nontrivial conjugacy classes. So, \(|K_i| \geq 2 \) and so \[ \frac{|G| - |Z|}{2} \geq t \] i.e. \[ k = t + |Z| \leq \frac{|G| - |Z|}{2}. \] Since \(G\) is nonabelian, \(G/Z\) is noncyclic and so \( |Z| \leq \frac{|G|}{4}\). So, \( k \leq \frac{5}{8}|G|\) and so \(\Pr(G) \leq \frac{5}{8}\). The bound is realised by the dihedral group of order 8 and so is best-possible. In the same note, Gustafson notes that if \(G\) is a (nonabelian) compact, Hausdorff topological group then the same bound holds (where the probability computations are done via the unique normalised Haar measure on \(G\)). It is much harder to find good lower bounds for \(\Pr(G)\), although Gustafson notes that Erdös and Turán (in a paper in 1968 which is, to the best of my knowledge, the first place anybody considers \(\Pr(G)\)) prove that if \(G\) is a finite group, then \[ \Pr(G) \geq \frac{\log_2 \log_2 |G|}{|G|} .\]
izzy806
andulkaphoto
s-u-f-j-a-n-s-t-e-v-e-n-s
romaincrisis
stormborns
origamiaround
amandla