Timeline for Are (group theoretic) Markov properties on groups with decidable word problems, decidable?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31 at 18:47 | history | edited | Perry Bleiberg | CC BY-SA 4.0 |
deleted 270 characters in body
|
| Aug 31 at 18:46 | vote | accept | Perry Bleiberg | ||
| Aug 26 at 14:49 | answer | added | E.Rauzy | timeline score: 6 | |
| Aug 20 at 2:36 | history | edited | Perry Bleiberg | CC BY-SA 4.0 |
added 160 characters in body
|
| Aug 18 at 12:39 | comment | added | HJRW | For the record, I have no doubt that being torsion-free — which is a Markov property — is not “recursive modulo the word problem”. I will think about whether a proof is known. | |
| Aug 18 at 11:39 | comment | added | HJRW | @Carl-FredrikNybergBrodda: agreed, triviality is trivial! For more results beyond the free case, see arxiv.org/abs/1210.2101v1. | |
| Aug 18 at 5:09 | comment | added | Carl-Fredrik Nyberg Brodda | @HJRW Being trivial is trivially checkable when the word problem is decidable — just check if every generator is equal to $1$. Your freeness result (with Groves) is the strongest I know in this direction. | |
| Aug 17 at 20:17 | comment | added | Perry Bleiberg | @HJRW Thank you, I think these references are really what I'm looking for. | |
| Aug 17 at 18:49 | comment | added | HJRW | It’s certainly not known that all Markov properties are decidable given an oracle, but some — such as being trivial, or free — are known. See, for instance, arxiv.org/abs/0704.0989v2 . | |
| Aug 17 at 18:48 | comment | added | HJRW | Even framing this kind of question rigorously is tricky. I suggest you look at the recent papers of Rauzy: arxiv.org/abs/2111.01190v2 and arxiv.org/abs/2111.01179v5 . | |
| Aug 17 at 17:04 | comment | added | Perry Bleiberg | @CorentinB great points, I think I will need to edit the question slightly | |
| Aug 17 at 16:48 | comment | added | Perry Bleiberg | @BenjaminSteinberg thanks, fixed | |
| Aug 17 at 16:48 | history | edited | Perry Bleiberg | CC BY-SA 4.0 |
added 76 characters in body
|
| Aug 17 at 16:17 | comment | added | Corentin B | Two trivial comments: 1) In order for the question to make sense, one should consider another notion of Markov property, where both "witness" groups have decidable word problems. 2) Your reformulation with oracle is not (at least, not obviously) equivalent with an "Adian-Rabin theorem for groups with decidable word problem". Actually, neither of the implications is clear to me (I don't see an algorithm which, given a presentation of a group with decidable word problem, output an algorithm for the Word Problem) | |
| Aug 17 at 16:11 | comment | added | Benjamin Steinberg | You linked to the edit of your MSE post rather than the post. | |
| Aug 17 at 16:00 | history | asked | Perry Bleiberg | CC BY-SA 4.0 |