$\DeclareMathOperator\PGL{PGL}\DeclareMathOperator\Conj{Conj}$Let $G$ be the symmetric group $S_n$ or the projective general linear group $\PGL_2(n)$.

Let $X$ be a cyclically reduced word in the abstract variables $x_1, x_2, \ldots,x_k$, i.e. $X$ is a product containing $x_1, x_2, \ldots,x_k$ and their inverses, without any element appearing next to its own inverse in any cyclic permutation. (Only words with length $4$, $6$, $8$ are needed in my research.)

Consider the probability $P$ that the word sums to $1$, with each $x_i$ chosen uniformly and independently from $G$.


What are the upper bounds of $\log_{|G|}P$?

If $\log_{|G|}P$ converges when $n\to\infty$, what's the value?

Answers are acceptable for either $G=S_n$ or $G=\PGL_2(n)$.


If there's a variable occurring only once in $X$, then $P$ is exactly $1/|G|$.

If $X=x_1^k$, then the limit is $-1/k$ for symmetric groups by David E Speyer's argument.

As Richard Stanley pointed out, if $X=x_1x_2x_1^{-1}x_2^{-1}$, then $P=|\Conj(G)|/|G|$. ($|\Conj(G)|$ is the number of conjugacy classes of $G$)

The formula $P=|\Conj(G)|/|G|$ holds for the words $x_1x_1x_2x_2$ and $x_1x_2x_1x_2^{-1}$ if all the characters of $G$ are real, and that's exactly the case for $S_n$ and $\PGL_2(n)$.

  • $\begingroup$ What is $\varepsilon$? It doesn't seem to appear anywhere else except in the clause "for each $\varepsilon >0$". $\endgroup$ Jun 8, 2019 at 13:02
  • 2
    $\begingroup$ I have edited the question: There should be no $ε$. $\endgroup$ Jun 8, 2019 at 13:03
  • 4
    $\begingroup$ If $X = A^k$ then the limit is $-1/k$. The generating function for the probability that an element of $S_n$ obeys $g^k=1$ is $f_k(x) := \exp \left( \sum_{d|k} t^d/d \right)$. Taking the contour integral $\oint f_k(x) x^{-N-1} dx$ around a circle of radius $N^{1/k}$ gives asymptotics of the form $N^{-N/k} \exp(N/k+o(N))$. $\endgroup$ Jun 8, 2019 at 13:42
  • 2
    $\begingroup$ A paper that is somewhat related is A. Nica, On the number of cycles of given length of a free word in several random permutations, Random Structures & Algorithms 5 (1994), 703-730. An unrelated comment: for $X=xyx^{-1}y^{-1}$, the limit is 1, since the number of commuting pairs in any finite group $G$ is $|G|\cdot k(G)$, where $k(G)$ is the number of conjugacy classes, and the number of conjugacy classes in $S_n$ is around $e^{c\sqrt{n}}$. $\endgroup$ Jun 9, 2019 at 13:15
  • 2
    $\begingroup$ As for $X=x_1x_1x_2x_2$, this is part of Exercise 7.69(h) of Enumerative Combinatorics, vol. 2. Possibly part (i) can solve the problem for $xy^kxy^{-k}$ and $xy^kx^{-1}y^k$, but I have not tried to do this. See also (f) for a possible approach to $X=x_1^{a_1}\cdots x_m^{a_m}$. $\endgroup$ Jun 9, 2019 at 22:22

1 Answer 1


$\DeclareMathOperator\PGL{PGL}$I believe the best result in this direction is due to M. Larsen & A. Shalev (2012); see this paper. I'll summarize their results here. This doesn't answer the questions whether the limit exists or what its precise value is, though, so this is not a full answer.

Denote the length of the word $X$ by $\ell$ (while $k$ is the size of the alphabet).

As for $S_n$, Proposition 2.3 gives $P < n!^{-\eta}$ for large enough $n$, if $\eta < \frac{2k-1}{4\left((2k)^{2\ell+1}-1\right)}$, so $\log_{|S_n|}P < -\eta. $

As for $\PGL_n(\mathbb{F}_q)$, Proposition 3.3 gives $\log_{|G|}P \le -\eta$ for large enough $n$ (and every $q$), if $\eta < \frac{1}{1800\ell^2}$. (This holds for all classical groups of Lie type).

Shalev and Larsen handle all finite simple groups in their paper. They also refer to this paper, which gives a bound for simple groups $G$ of Lie type of bounded rank $r$: $ P \le \frac{C}{q}$ where $C = C(r, X)$ is a constant, and $q \ge G^{\epsilon}$ for some $\epsilon = \epsilon(r)$, hence $\log_{|G|}P \le -\eta$ for large enough $G$ if $\eta < \epsilon$. EDITED: this last paragraph answers the $n=2, q\to\infty$ case.

  • $\begingroup$ OP asked the asymptotics for $\mathrm{PGL}_2(q)$ for large $q$, nor $\mathrm{PGL}_n(q)$ for fixed $q$ and large $n$ (but agree that the analogy with $S_n$ makes it more natural to consider $\mathrm{PGL}_n(q)$ for $n\to\infty$). $\endgroup$
    – YCor
    Mar 5, 2022 at 11:07
  • $\begingroup$ The last paragraph handles this case (bounded rank). I admit I wasn't sure which group OP meant, so I tried to answer both possible meanings. $\endgroup$ Mar 5, 2022 at 12:08

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.