10
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This question is impossible to answer in the generality you've stated. It depends completely on what you know about the group $G$. $\endgroup$
    – Greg Martin
    Commented May 12, 2018 at 17:42
  • 1
    $\begingroup$ @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$? $\endgroup$
    – Licheng Wang
    Commented May 12, 2018 at 17:46

4 Answers 4

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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)$. $\endgroup$
    – Licheng Wang
    Commented May 12, 2018 at 18:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Geoff Robinson
    Commented May 12, 2018 at 18:45
  • $\begingroup$ Is there a method for computing your mentioned formula $\sum_{\chi\in Irr(G)}\mu(\chi)\chi(x)$ efficiently? $\endgroup$
    – Licheng Wang
    Commented May 12, 2018 at 19:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Geoff Robinson
    Commented May 15, 2018 at 12:27
13
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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). $\endgroup$
    – YCor
    Commented May 13, 2018 at 1:08
  • 1
    $\begingroup$ 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'... $\endgroup$
    – Steven Stadnicki
    Commented Aug 12, 2018 at 4:40
  • 1
    $\begingroup$ I got curious enough to ask this as a separate question: mathoverflow.net/questions/308077/… $\endgroup$
    – Steven Stadnicki
    Commented Aug 12, 2018 at 5:30
  • $\begingroup$ @StevenStadnicki: I wrote a comment there. $\endgroup$
    – user6976
    Commented Aug 12, 2018 at 14:53
3
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • 2
    $\begingroup$ And Dahmani—Guirardel handled the case with torsion. But there are surely more efficient algorithms... $\endgroup$
    – HJRW
    Commented May 18, 2018 at 8:33
  • 1
    $\begingroup$ (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.) $\endgroup$
    – HJRW
    Commented May 18, 2018 at 8:36
  • 1
    $\begingroup$ 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. :) $\endgroup$
    – HJRW
    Commented May 18, 2018 at 9:40
  • 3
    $\begingroup$ 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). $\endgroup$
    – user6976
    Commented May 18, 2018 at 13:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – user6976
    Commented May 18, 2018 at 17:37
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Todd Trimble
    Commented Aug 12, 2018 at 0:06
  • 1
    $\begingroup$ @ToddTrimble I did not claim it was difficult, but it does save a lot of work in half the cases. $\endgroup$
    – Igor Rivin
    Commented Aug 12, 2018 at 0:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – user6976
    Commented Aug 12, 2018 at 2:56
  • 4
    $\begingroup$ ... 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. $\endgroup$
    – user6976
    Commented Aug 12, 2018 at 3:02
  • $\begingroup$ @MarkSapir Low-tech, but effective :) $\endgroup$
    – Igor Rivin
    Commented Aug 12, 2018 at 6:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .