For which kinds of group $G$, can we identify a square element efficiently?

For a group $(G,\star)$, an element $x\in G$ is said to be square if there is $y\in G$ such that $x=y\star y$.

My question is: For which kinds of group $G$, can we decide whether $x\in G$ is a square or not?

As for the multiplicative group $(\mathbb Z/n\mathbb Z)^*$ (where $n$ is a prime or the production of some primes), we know that this problem is equivalent to the so-called quadratic residue problem, and we have methods for dealing with this problem. More specifically, if and only if the factorization of $n$ is known, we can identify a sqaure element efficiently.

How about for other groups? If we cannot hope for a general answer, can we answer this question for certain special groups?

• This question is impossible to answer in the generality you've stated. It depends completely on what you know about the group $G$. – Greg Martin May 12 '18 at 17:42
• @Greg Martin: Thanks a lot! Then, I would like to ask: When we can ask such question? My means is: What kind of structures are required for the group $G$? – Licheng Wang May 12 '18 at 17:46

For a finite group $G$, there is a long-standing answer to this question using character theory. If $\chi$ is an irreducible complex character of $G$, then its Frobenius-Schur indicator $\nu(\chi)$ is defined by $\nu(\chi) = \frac{1}{|G|} \sum_{g \in G} \chi(g^{2}).$ It is known that $\nu(\chi) \in \{0,1,-1\},$ and that $\nu(\chi) = 0$ if $\chi$ is not real-valued,$\nu(\chi) = 1$ if $\chi$ is real-valued may be afforded by a representation over $\mathbb{R},$ while $\nu(\chi) = -1$ if $\chi$ is real-valued, but may not be afforded by any representation over $\mathbb{R}.$

It then follows from the orthogonality relations for group characters that for any $x \in G,$ the number of $g \in G$ such that $g^{2} = x$ is given by the formula $\sum_{\chi \in {\rm Irr}(G)} \nu(\chi)\chi(x)$, where ${\rm Irr}(G)$ is the set of complex irreducible characters of $G$. Note that $x$ is a square in $G$ if and only if this expression is non-zero.

• Thanks a lot! Would you please suggest me some references for a better study on this topic? In particular, I want to study the case when $G$ is the multiplicative group of the matrix ring $M_d(\mathbb Z_N)$. – Licheng Wang May 12 '18 at 18:39
• Most text books on character theory of finite groups cover the Frobenius-Schur indicator ( if you have access to some of these). One such is the book "Character Theory" by I.M. Isaacs. – Geoff Robinson May 12 '18 at 18:45
• Is there a method for computing your mentioned formula $\sum_{\chi\in Irr(G)}\mu(\chi)\chi(x)$ efficiently? – Licheng Wang May 12 '18 at 19:04
• You need to know the character table of your group, and to be able to calculate the Frobenius-Schur indicators of irreducible characters. By the way, there is an inequality (for finite groups) whose proof by character theory is elementary: if G has s(G) squares and r(G) real-valued irreducible characters, then s(G) is greater than or equal to |G|/r(G). Groups of odd order show that this inequality can't be improved in general, and the inequality is strict infinitely often. – Geoff Robinson May 15 '18 at 12:27

To complete the picture, for an infinite finitely presented group, the answer can be "it is undecidable". That is, there exists a group $G$ given by a finite set of generators $X$ and a finite set of relations $R$ for which there is no algorithm to decide, given an element $g\in G$, if $g$ is a square in $G$. One example of such a group is Kharlampovich's group from MR0631441, Kharlampovich, O. G., A finitely presented solvable group with unsolvable word problem. Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852--873 (one needs to take $p=2$ in her construction). Indeed, if an element belongs to the center of Kharlampovich's group with $p=2$, then it is a square in the group if and only if it is equal to 1, and Kharlampovich proved that this property is undecidable.

• A distinct similar fact is that there is no algorithm whose input is a finite presentation and output tells whether the first generator is a square (easy consequence of the undecidability of the triviality problem). – YCor May 13 '18 at 1:08
• This does still leave one interesting piece of the puzzle, though: if $G$ is infinite and finitely presented but has decidable word problem, must the square problem be decidable? It's clearly semidecidable (just enumerate all words and check) but even in the decidable case it's not clear that there has to be any recursive bound on the potential size of a 'square root'... – Steven Stadnicki Aug 12 '18 at 4:40
• I got curious enough to ask this as a separate question: mathoverflow.net/questions/308077/… – Steven Stadnicki Aug 12 '18 at 5:30
• @StevenStadnicki: I wrote a comment there. – Mark Sapir Aug 12 '18 at 14:53

You can decide whether a given element in a torsion-free hyperbolic group is a square. This class includes finitely generated free groups, torsion-free groups acting (nicely) on trees, and fundamental groups of closed surfaces with negative Euler characteristic.

Suppose $\Gamma=\langle a_1,\ldots,a_k\rangle$ and $a_0\in\Gamma$ is the element you're interested in. You can say $\Gamma=\langle a_0,a_1,\ldots,a_k\rangle$, so then the validity of following sentence can be decided by [Sela, §4]: $$\exists x\ (a_0=x^2)$$ Technically this should begin with $\forall y$ to make an AE sentence, but the AE sentence $$\forall y\exists x\ (y=y)\wedge(a_0=x^2)$$ is equivalent.

• And Dahmani—Guirardel handled the case with torsion. But there are surely more efficient algorithms... – HJRW May 18 '18 at 8:33
• (Also, I’m not sure why you want it to be an AE sentence. The decidability if the existential theory is much easier; and the decidability of the elementary theory is certainly not due to Sela.) – HJRW May 18 '18 at 8:36
• Theorem 7.12 of the paper of Sela that you mention asserts that the universal (equivalently, existential) theory of a torsion-free hyperbolic group is decidable. For all hyperbolic groups, see Dahmani & Guirardel, `Foliations for solving equations in groups: free, virtually free, and hyperbolic groups', J. Topol.. But it would be a nice exercise to figure out how you'd solve this problem in practice for a given element of a given hyperbolic group. :) – HJRW May 18 '18 at 9:40
• You do not need the whole existential theory. Since a square root of $g$ commutes with $g$ all you need is to find the centralizer of $g$ which is a virtually cyclic group and is either finite of bounded size (constant complexity of finding a square root of $g$) or has an infinite cyclic subgroup of finite index of bounded size, and then it is also easy to find a square root. So the only difficulty is to find the centralizer, but that can be done in at most exponential time (perhaps less - Derek Holt should know). – Mark Sapir May 18 '18 at 13:45
• Yes, it is hyperbolic, but it is not a part of the input because the group is fixed and only $g$ changes. If you fix $n$, you can also pre-compute its prime decomposition. It does not affect complexity of the problem. – Mark Sapir May 18 '18 at 17:37

A low-brow addendum to Geoff's answer: For a group of odd order, the answer is always YES.

• Well, this is indeed trivial since every element is a square: every element $g$ has odd order, say $2k-1$, and then $g = (g^k)^2$. – Todd Trimble Aug 12 '18 at 0:06
• @ToddTrimble I did not claim it was difficult, but it does save a lot of work in half the cases. – Igor Rivin Aug 12 '18 at 0:39
• It can be pushed further. Every element of odd order is a square. If the order of $g$ is $2^ka$ where $a$ is odd, then $g$ is a square iff $g^a$ is a square,so the problem reduces to elements of order $2^k$ . If such an element is a square, then in case of a finite group, the square roots are in the same Sylow 2-subgroup. So the problem reduces to $2$-groups. If $G$ is a finite 2-group, then elements of max. order are not squares. Then one can take the Abelianization, and the whole lower central series. – Mark Sapir Aug 12 '18 at 2:56
• ... then consider the $2$-group $G$ modulo its center. $G/Z$. If $g\in G$ is a square, then $gZ$ is a square in the factor-group. If $gZ$ is a square, then $g=h^2z$ for some $h\in G$, $z\in Z$. Therefore the problem reduces to central elements of $2$-groups. – Mark Sapir Aug 12 '18 at 3:02
• @MarkSapir Low-tech, but effective :) – Igor Rivin Aug 12 '18 at 6:23