# Roots of permutations

Consider the equation $$x^2=x_0$$ in the symmetric group $$S_n$$, where $$x_0\in S_n$$ is fixed. Is it true that for each integer $$n\geq 0$$, the maximal number of solutions (the number of square roots of $$x_0$$) is attained when $$x_0$$ is the identity permutation? How far may it be generalized?

• I assume x_0 and x_o are the same? Also "identical permutation" means "identity permutation"? – JBL Oct 11 '10 at 13:52
• The number of $k$-th roots of a permutation is the number of ways to collect its cycles into tuples according to certain rules. At least for prime $k$, I think it follows immediately that the maximum is achieved at the identity permutation. – JBL Oct 11 '10 at 14:34

$$\DeclareMathOperator{\GL}{GL} \DeclareMathOperator{\SL}{SL}$$ The maximum of the function counting square roots is attained at $$x_0=1$$ and this statement generalises quite well.

Let $$s(\chi)$$ denote the Frobenius-Schur indicator of the irreducible character $$\chi$$. For the definition, see the edit below. One has $$s(\chi)=1$$ if the representation of $$\chi$$ can be realised over $$\mathbb{R}$$, $$s(\chi)=-1$$ if $$\chi$$ is real-valued but the corresponding representation is not realisable over $$\mathbb{R}$$, and $$s(\chi)=0$$ if $$\chi$$ is not real-valued. Then, the number of square roots of an element $$g$$ in any group is equal to $$\sum_\chi s(\chi)\chi(g),$$ where the sum runs over all irreducible characters of the group. See below for a reference and a quick proof of this identity.

It follows from the usual theory of representations of $$S_n$$ that in this special case all Frobenius-Schur indicators are $$1$$, so the number of square roots of $$x_0$$ is just $$\sum_\chi \chi(x_0)$$. This proves that the maximal number of solutions is indeed attained by $$x_0 = 1$$, since each character value attains its maximum there. This generalises immediately to all groups for which every representation is either realisable over $$\mathbb{R}$$ or has non-real character, in other words has no symplectic (or sometimes called quaternionic) representations. That includes all abelian groups, all alternating groups, all dihedral groups, $$\GL_n(\mathbb{F}_q)$$ for all $$n\in \mathbb{Z}_{\geq 1}$$ and all prime powers $$q$$ (see [1, Ch. III, 12.6]), and many more.

 A. Zelevinsky, Representations of Finite Classical Groups, Lecture Notes in Mathematics, Vol. 869, Springer-Verlag, New York/Berlin, 1981.

Edit: One reference I have found for the identity expressing the number of square roots in terms of Frobenius-Schur indicators is Eugene Wigner, American Journal of Mathematics Vol. 63, No. 1 (Jan., 1941), pp. 57-63, "On representations of certain finite groups". Once you get used to the notation, you will recognise it in displayed formula (11). Since the notation is really heavy going, I will supply a quick proof here:

Claim: If $$n(g)$$ is the number of square roots of an element $$g$$ of a finite group $$G$$, then we have $$n(g) = \sum_\chi s(\chi)\chi(g),$$ where the sum runs over all characters of $$G$$, and $$s(\chi)$$ denotes the Frobenius-Schur indicator of $$\chi$$, defined as $$s(\chi)=\frac{1}{|G|}\sum_{h\in G}\chi(h^2)$$.

Proof: It is clear that $$n(g)$$ is a class function, so it is a linear combination of the irreducible characters of $$G$$. The coefficient of $$\chi$$ in this linear combination can be recovered as the inner products of $$n$$ with $$\chi$$. We can write $$n(g) = \sum_h \delta_{g,h^2}$$ (here $$\delta$$ is the usual Kronecker delta), so we obtain \begin{align*} \left< n,\chi \right> &= \frac{1}{|G|}\sum_{g\in G}n(g)\chi(g) = \frac{1}{|G|}\sum_{g\in G}\sum_{h\in G}\delta_{g,h^2}\chi(g)=\\\\ &=\frac{1}{|G|}\sum_{h\in G}\sum_{g\in G}\delta_{g,h^2}\chi(g) = \frac{1}{|G|}\sum_{h\in G}\chi(h^2), \end{align*} as claimed.

Edit 2: I got curious and ran a little experiment. The proof above applies to all finite groups that have no symplectic representations. So the natural question is: what happens for those that do? Among the groups of size $$\leq 150$$, there are 1911 groups that have a symplectic representation, and for 1675 of them, the square root counting function does not attain its maximum at the identity! There are several curious questions that suggest themselves: is there a similar (representation-theoretic?) 2-line criterion that singles out those 300-odd groups that satisfy the conclusion but not the assumptions of the above proof? What happens for the others? Can we find a complete characterisation of the groups whose square root counting functions is maximised by the identity? Following Pete's suggestion, I have started two follow-up questions on this business: one on square roots and one on $$n$$-th roots.

• Wow, neat: I didn't see that coming at all. Do you have a reference for your identity? – Pete L. Clark Oct 11 '10 at 14:55
• See also Exercise 7.69 of my book Enumerative Combinatorics, vol. 2. In particular, part (c) asserts that if $k$ is a positive integer and $r_k(w)$ is the number of $k$th roots of $w\in S_n$, then $r_k$ is a character of $S_n$. It follows that $r_k$ takes its maximum value at the identity permutation. – Richard Stanley Oct 11 '10 at 15:26
• @Alex: Your Edit 2 seems very interesting. I doubt it is getting optimal exposure here: please consider asking it as as a separate question. – Pete L. Clark Oct 13 '10 at 16:48

To your last question - "how far may it be generalized" - Richard Stanley answered when you fix the equation ($$X^2=c$$) and vary the group. You may also wonder about other equations. The situation is interesting: There are equations and groups with the property that the identity is not the RHS yielding the most solutions. This is so even though the LHS has no constants, just variables.

One may rephrase the question as follows: given a word $$w=w(X_1,X_2,\ldots,X_r)$$ in the free group $$F_r$$ with variables $$X_1,\ldots,X_r$$, and given any finite group $$G$$, one may naturally consider $$w$$ as inducing a function $$G^r \to G$$ by plugging elements of $$G$$ as variables. This in turn defines a probability distribution on $$G$$: if you plug uniform random elements, what do you get? The most likely outcome is often, but not always, the identity.

In fact, the probability of getting the identity can be made arbitrarily small iff the group is non-solvable. I circulated this as a conjecture some years ago and it was proven by Miklos Abert (for the non-solvable case) and Nikolov and Segal (for the solvable one).

• In fact, Richard Stanley didn't fix the equation. He is talking about equations of the form $x^k = c$ in $S_n$. – Alex B. Oct 12 '10 at 8:39
• True. My answer attempts to generalize further into equations in several variables. – Alon Amit Oct 12 '10 at 18:44

For a general finite group $$G$$ and an arbitrary element $$y \in G,$$ there is a general way to use characters to compare the number of solutions of $$x^{2} = y$$ in $$G$$ with the number of solutions of $$x^{2} = 1$$ within $$C_{G}(y).$$

For notice that any element $$x$$ with $$x^{2} = y$$ already lies in $$C_{G}(y).$$ Hence (using the general formula mentioned in Alex's answer, but within the group $$C_{G}(y)$$) the number of solutions of $$y^{2} = x$$ is $$\sum_{ \mu \in {\rm Irr}(C_{G}(y)} \nu(\mu) \mu(y),$$ where $$\nu(\mu)$$ is the Frobenius-Schur indicator of $$\mu$$ ( which Alex denoted by $$s(\mu)$$).

But now we note (using Schur's Lemma) that unless $$y{\rm ker} \mu$$ has order $$1$$ or $$2$$ in $$C_{G}(y)/{\rm ker}(\mu)$$ we have $$\nu(\mu) = 0$$ since $$\mu$$ is certainly not real-valued.

Hence if $$y$$ has order $$m,$$ then we need only consider irreducible characters $$\mu$$ with $$y$$ in their kernel when $$m$$ is odd, and irreducible characters $$\mu$$ with $$y^{2}$$ in their kernel when $$m$$ is even.

In any case, the contribution to the sum from those characters with $$y$$ in their kernel is the same as the number of square roots of the identity in $$C_{G}(y)/\langle y \rangle.$$

I won't give all details, but we may continue to deduce that the difference between the number of square roots of the identity in $$C_{G}(y)$$ and the number of square roots of $$y$$ in $$G$$ is given by the formula:

$$\sum_{\mu \in {\rm Irr}(C_{G}(y)/\langle y^{2} \rangle) \backslash {\rm Irr}(C_{G}(y)/\langle y \rangle)} 2\nu(\mu)\mu(1).$$

Note that this number is non-negative unless $$C_{G}(y)$$ has an irreducible character $$\mu$$ with $$\nu(\mu) = -1$$ and with $$y^{2} \in {\rm ker} \mu$$ but $$y \not \in {\rm ker} \mu$$.

Hence we may conclude in particular that for a general element $$y$$ of a general finite group $$G,$$ the number of square roots of $$y$$ in $$G$$ is already less that the number of solutions of square roots of the identity in $$C_{G}(y)$$ unless $$C_{G}(y)$$ has an irreducible character $$\mu$$ of Frobenius-Schur indicator $$-1$$ such that $$y{\rm ker} \mu$$ has order $$2$$ in $$C_{G}(y)/{\rm ker} \mu.$$

Latter edit: It is perhaps worth remarking that this argument shows that the number of square roots of $$y$$ in $$G$$ is the same as the number of square roots of $$yM$$ in $$C_{G}(y)/M$$, where $$M$$ is the normal subgroup $$\langle y^{2} \rangle$$ of $$C_{G}(y).$$ This reduces the computation of the number of square roots of $$y \in G$$ to the case that $$y$$ has order $$1$$ or $$2$$ and that $$y \in Z(G).$$

Returning to the (last part of the) original question, it means that each finite group $$G$$ for which the maximum number of square roots is not attained at the identity has a section (ie a factor group of a subgroup) $$H$$ such that $$Z(H)$$ such contains an involution $$u$$ with the number of elements of order four with square $$u$$ at least two greater that the number of involutions of $$H$$ ( here an involtion is considered to be an element of order exactly two). Furthermore, the section $$H$$ has the form $$C_{G}(y)/\langle y^{2} \rangle$$ where $$y$$ is an element of $$G$$ with the maximum number of square roots. Note also that if the identity element does not have the maximum number of square roots then the element $$y$$ attaining the maximum number necessarily has even order.

Note that in the essential case that $$y \in Z(G)$$ is an involution, then $$y$$ has more square roots in $$G$$ than the identity does if and only if we have $$\sum_{ \{\chi \in {\rm Irr}(G) \backslash {\rm Irr}(G/\langle y \rangle): \nu(\chi) = -1 \}}\chi(1) > \sum_{ \{\chi \in {\rm Irr}(G) \backslash {\rm Irr}(G/\langle y \rangle): \nu(\chi) = +1 \} } \chi(1).$$

• That's nice! A data point, in particular in connection with my related question (link in my answer): out of the 1911 groups of order less than 150 that have a symplectic representation, in 236 the square root counting function takes its maximum at the identity. Out of those, 8 satisfy your criterion, i.e. there is no $y$ and $\mu\in {\rm Irr}_{C_G(y)}$ with Frobenius-Schur indicator $-1$ and such that $y{\rm ker}\mu$ has order $2$ in $C_G(y)/{\rm ker}\mu$. All 8 are groups of order $128$. – Alex B. Mar 14 '19 at 11:57
• Are there any general results regarding Frobenius-Schur indicators of element centralisers in finite groups? In particular, are there any infinite families of groups that may have symplectic representations but for which your criterion kicks in? – Alex B. Mar 14 '19 at 11:57
• Not sure if you have now seen the new edit, which reduces the problem to the essential case of a central involution which has strictly more square roots than the identity. For groups like ${\rm SL}(2,q)$ ($q$ odd) I think it's obvious that the central involution has more square roots than the identity since the identity has only two square roots,whereas there are already at least six elements of order $4$ in the Sylow $2$-subgroup. But the character theoretic condition also shows this easily too. – Geoff Robinson Mar 14 '19 at 12:33
• Our comments overlapped, we had been typing at the same time. I had also noticed that among the aforementioned small groups, in the vast majority of them (all but 23), the square root counting function attains its maximum at a central element. Your argument offers an explanation of this observation. – Alex B. Mar 14 '19 at 12:57