Timeline for Decision problem on triviality of intersection of two subgroups
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2015 at 4:26 | comment | added | HJRW | Ditto.${}{}{}{}$ | |
| Mar 12, 2015 at 12:43 | comment | added | Joel David Hamkins | I deleted all my comments above, because they are distracting from the discussion. | |
| Mar 10, 2015 at 23:11 | comment | added | YCor | @JoelDavidHamkins: you're right, I understood the problem for a fixed given f.g. group, since the uniform problem is indeed senseless. On the other hand in the case of free groups (with respect to their free generating family) there is a uniform algorithm as a consequence of the fact that there is an algorithm for $F_2$. | |
| Mar 10, 2015 at 21:35 | comment | added | YCor | @JoelDavidHamkins: this is not an issue. If we pick a finite generating family in $G$ then the input is clear. All what's needed it to check that this does not change if we pick another finite generating family. Since we can go by steps from one to another by adding and removing generators, it is enough to understand what's going on when we pass from $(x_1,\dots,x_n)$ to $(x_1,\dots,x_n,y)$, where $y=m(x_1,\dots,x_n)$. If it's solvable in the first case then it's also in the second (by replacing $y$ with $m$). Conversely if it's solvable in the second family, then it's for the first (trivial). | |
| Mar 10, 2015 at 11:07 | answer | added | MCC | timeline score: 3 | |
| Mar 10, 2015 at 0:07 | vote | accept | owb | ||
| Mar 10, 2015 at 0:07 | vote | accept | owb | ||
| Mar 10, 2015 at 0:07 | |||||
| Mar 9, 2015 at 21:02 | comment | added | Benjamin Steinberg | For rational subgroups of automatic groups (in the sense of Gersten-Short), one can check triviality of intersection provided one is given as part of the input the automata giving the rational structure (or the corresponding quasi-convexity constant wrt the regular cross-section). The set of normal forms from the regular cross-section of elements of each of the subgroups is a regular language and hence so is their intersection. But checking if a regular language is just the empty word is decidable. | |
| Mar 9, 2015 at 20:21 | comment | added | HJRW | In the negatively curved world (eg hyperbolic groups, free groups etc) the correct hypothesis is that the subgroup should be not just finitely generated but quasiconvex (in some suitable sense). For these subgroups, Stallings' techniques argument in free groups can be generalized (see a recent paper of Kharlampovich--Myasnikov--Weil). The Rips consruction argument I described in my answer shows that some hypothesis along these lines is necessary. | |
| Mar 9, 2015 at 20:17 | answer | added | HJRW | timeline score: 8 | |
| Mar 9, 2015 at 20:09 | answer | added | Benjamin Steinberg | timeline score: 9 | |
| Mar 9, 2015 at 16:11 | comment | added | owb | As Andy let me know, Stalling's non-trivial result implies decidability of the problem for free non-abelian groups. Is anything known about this problem for finitely generated nilpotent groups, free solvable groups, etc.? Are there known examples of finitely generated (or even finitely presented) groups with solvable word problem for which the problem above is undecidable? Isn't such an example the group F x F, where F is a finitely generated free non-abelian group? | |
| Mar 9, 2015 at 16:09 | comment | added | owb | Yes, the problem is obviously undecidable for groups with unsolvable word problem, and the question was about the groups with solvable word problem. The precise formulation of the problem is as follows. Let G=<A; R>, where A is finite, R is computably enumerable, and G has solvable word problem. Given finite sets of group words V and W over A, decide whether the subgroups of G generated by V and W have trivial intersection. Clearly decidability of the problem does not depend on the choice of the presentation <A;R> of G. | |
| Mar 9, 2015 at 3:31 | comment | added | Andy Putman | It is not decidable in general since it would allow you to solve the word problem (given an element $w$, just apply it to the subgroups $\langle w \rangle$ and $\langle w \rangle$; their intersection is trivial if and only if $w$ is trivial). On the other hand, it is decidable for free groups; indeed, using the algorithm described in Stallings's paper "The topology of finite graphs", you can compute the rank of the intersection of two finitely generated subgroups of a free group. | |
| Mar 9, 2015 at 3:14 | history | asked | owb | CC BY-SA 3.0 |