# Probability and Combinatorial Group Theory.

If this is too broad or is otherwise a poor question, I apologise.

I learned recently that the probability that two integers generate the additive group of integers is $\frac{6}{\pi^2}$.

What other results are there like this?

I'm looking for any results of probability applied to group theory, preferably combinatorial group theory, in manner such as the one above.

Here are some quite similar facts:

The probability that a random pair of elements generates either $S_n$ or $A_n$ is $1 - \frac{1}{n} - \frac{1}{n^2} - \frac{4}{n^3} - \frac{23}{n^4} - \frac{172}{n^5} - \frac{1542}{n^6} - O\left(\frac{1}{n^7}\right)$.

The probability that a random triple of elements generates either $S_n$ or $A_n$ is $1 - \frac{1}{n^2} - \frac{3}{n^4} - \frac{6}{n^5} - O\left(\frac{1}{n^6}\right)$.

The probability that a random pair of elements generates exactly $S_n$ is $\frac{3}{4} + O(\frac{1}{n})$

The probability that a random element generates $\mathbb{Z}_n$ is $\frac{\phi(n)}{n}$, where $\phi$ is Euler's totient function.

The probability that $m$ random elements generate $\mathbb{Z}_{p^n}$, where $p$ is prime, is $1 - \frac{1}{p^m}$.

The probability that $n$ random elements generate $\mathbb{Z}^{n-1}$ is $\prod_{j=2}^n \zeta(j)^{-1}$, where $\zeta$ is Riemann zeta function.

The most general fact of that type is that the probability of $m$ random elements generating an arbitrary finite group $G$ is $\sum_{H \leq G} \mu(G, H) {\left(\frac{|H|}{|G|}\right)}^m$, where $\mu$ is the Moebius function for subgroup lattice of $G$. However, despite being much stronger, than aforementioned facts, this one is very hard to use, because we can only apply it to the groups with known subgroup structure.

• Another one: Dixon's conjecture—the probability, that two random elements generate a finite simple group $G$ tends to $1$ as $\lvert G \rvert \to \infty$. – Orat Aug 5 '18 at 21:29
• It's "probability that", not "probability, that". – Shaun Aug 6 '18 at 23:09
• For the symmetric group, there's a positive probability that the random pair or triple of elements consists entirely of even permutations, in which case we can't hope to get more than $A_n$. I believe the correct statement is something along the lines of "The probability that a random pair of elements generates either $A_n$ or $S_n$". – Kevin P. Costello Aug 6 '18 at 23:17

For a finite group you can compute the probability that any two random elements will commute by looking at certain conjugacy classes.

• That sounds interesting... Would you mind to give us a bit more detailed information about this fact? – Yanior Weg Aug 5 '18 at 19:03
• – Orat Aug 6 '18 at 0:57
• @YaniorWeg What I was talking about can be found at this link: math.stackexchange.com/questions/846217/… The formula I was thinking of is the k/|G| at the very end where k is the number of conjugacy classes. – Jimmy Mixco Aug 6 '18 at 2:17
• Similar results hold in combinatorial group theory. See, for example, this answer of mine. – user1729 Aug 7 '18 at 1:32

This question seems quite vast, but the first thing that comes to my mind when I ear "probability" and "group" theory in a sentence is the series of papers by Erdös and Turán "On some problems of a statistical group-theory, I--VII" and Erdös and Hall's "Some new results in probabilistic group theory". You can found these at https://users.renyi.hu/~p_erdos/Erdos.html.

For more concrete answers, a seminal result, pointed out by Yanior Weg, is Dixon Theorem "the probability that pair of permutations of $$S_n$$ generates the symmetric or the alternating group of size n goes to 1 with n" $$|(x,y) \in S_n^2 | \: \langle x,y\rangle = S_n \text{ or } A_n|/|S_n|^2 \to_{n\to \infty} 1$$ This was originally proved in Dixon "The probability of generating the symmetric group", and later improve with better bounds (see Dixon "Asymptotics of generating the symmetric and alternating groups" for a survey) and extended to any simple group by Kantor and Lubotzky "The probability of generating a finite classical group" and Liebeck and Shalev "The probability of generating a finite simple group".

In the same spirit, as Jimmy Mixco pointed out, W. H. Gustafson proved in "What is the Probability that Two Group Elements Commute?" that if the probability that a pair of element of a finite group commute then the group has to be Abelian. $${|\{(x,y) \in G^2| \: xy = yx\} |/|G|^2 > 5/8} \Leftrightarrow G \text{ is Abelian }$$ This was also extended to infinite groups in Anton, Martino and Ventura "Degree of commutativity of infinite groups": fix a generating set S for your group. If the limsup of the number of pair of elements of size at most n with respect with S is greater then the group is Abelian. Moreover if this limit is strictly positive then the group is virtually nilpotent

$${\limsup_{n\to \infty}|\{(x,y) \in B_{G,S}(n)| \: xy = yx\} |/|B_{G,S}(n)|^2 > 5/8} \Leftrightarrow G \text{ is Abelian }$$

One can also ask, for example, about the probability of being conjugate, see S.R. Blackburn, J.R. Britnell and M. Wildon, "The probability that a pair of elements of a finite group are conjugate".

Another possibility is to ask questions about the shape of the Cayley graph for some families of groups and random generating sets. This led to interesting connection with graph theory (e.g. Alon and Roichman "Random Cayley graphs and expanders"). See also Helfgott, Seress, Zuk "Random generators of the symmetric group: diameter, mixing time and spectral gap"

Finally, you can also look to other ways of generating groups, for instance by presentation: $$G = \langle a_1 ... a_n | r_1 ... r_m \rangle$$ means, in a nutshell, that $$G$$ is a group whose element are written as words other the $$a_i^{\pm 1}$$'s and such that the $$\{a_1^{\pm 1},...,a_n^{\pm 1}\}^* \ni r_i$$'s are words that represent the identity in the group. For instance $$\mathbb{Z}^2 = \langle a_1,a_2 | a_1a_2a_1^{-1}a_2^{-1} \rangle$$. Then a possible way to generate a random group is to fix n, pick some random $$r_i$$ and consider this $$G = \langle a_1 ... a_n | r_1 ... r_m \rangle$$. This as been initiated by Gromov and a nice survey due to Ollivier can be found here: http://www.yann-ollivier.org/rech/publs/randomgroups.pdf