# roots of permutations

Consider equation $x^2=x_0$ in symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 1$, the maximal number of solutions (square roots) has 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
of course, thank you – Fedor Petrov Oct 11 '10 at 14:19
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

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$. Thus, $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 quick proof of this identity.

Of course, in $S_n$, 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 any group, for which any representation is either realisable over $\mathbb{R}$ or has non-real character, e.g. all abelian groups. Other cases would require more thought, but this is likely the right way to go about it.

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 the Frobenius-Schur indicator of $\chi$ is 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 let's just take inner products with all characters of $G$ to find their coefficients, noting that we can write $n(g) = \sum_h \delta_{g,h^2}$ (here $\delta$ is the usual Kronecker delta): \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 required.

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 impose 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 an if and only if characterisation that provides more insight into the structure 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

Two 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