Skip to main content
MathOverflow

Return to Answer

added 1 character in body
Source Link
user6976
user6976

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, adand Kharlampovich proved that this property is undecidable.

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, ad Kharlampovich proved that this property is undecidable.

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.

added an explanation
Source Link
user6976
user6976

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, ad Kharlampovich proved that this property is undecidable.

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).

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, ad Kharlampovich proved that this property is undecidable.

Source Link
user6976
user6976

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).