Timeline for For which kinds of group $G$, can we identify a square element efficiently?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 1, 2020 at 10:36 | comment | added | YCor | I think there's a issue in effectiveness in Mark's recursion (say, for finite 2-groups $G$). Assuming we can solve "is $g$ a square$\to$ YES/NO" in $G/Z$, I don't see how to proceed. Assuming the algorithm in addition provide a square root: if $g$ is a square in $G/Z$ with square root $h$, then $g=h^2z$. So the question is whether there exists $s$ such that $s^2=h^2z$. If $z$ is a square in $Z$ clearly such $s$ exists, but conversely I don't see why this would imply that $z$ is a square in $Z$. Some elaboration seems needed. | |
| Apr 4, 2019 at 1:21 | vote | accept | Licheng Wang | ||
| Apr 4, 2019 at 1:24 | |||||
| Aug 14, 2018 at 9:53 | comment | added | Geoff Robinson | Since the trivial character is the only real-valued complex irreducible character of a finite group of odd order (first noted by Burnside, and an easy consequence of the orthogonality relations ), this is also an immediate consequence of the character-theoretic formula in my answer. I allude to it in my comment below my answer. | |
| Aug 14, 2018 at 1:57 | vote | accept | Licheng Wang | ||
| Apr 4, 2019 at 1:18 | |||||
| Aug 12, 2018 at 6:23 | comment | added | Igor Rivin | @MarkSapir Low-tech, but effective :) | |
| Aug 12, 2018 at 3:02 | comment | added | user6976 | ... 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. | |
| Aug 12, 2018 at 2:56 | comment | added | user6976 | 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. | |
| Aug 12, 2018 at 0:39 | comment | added | Igor Rivin | @ToddTrimble I did not claim it was difficult, but it does save a lot of work in half the cases. | |
| Aug 12, 2018 at 0:06 | comment | added | Todd Trimble | 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$. | |
| Aug 12, 2018 at 0:00 | review | Low quality posts | |||
| Aug 12, 2018 at 1:16 | |||||
| Aug 11, 2018 at 23:43 | history | answered | Igor Rivin | CC BY-SA 4.0 |