Timeline for Primes occurring as orders of elements of a finitely presented group
Current License: CC BY-SA 3.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 10, 2013 at 15:11 | history | edited | HJRW | CC BY-SA 3.0 |
Corrected the Very Exciting Theorem
|
| Feb 10, 2013 at 15:07 | comment | added | HJRW | Yes, I realized on Friday evening that we didn't quite have the correct statement, but haven't had time to . Well done Benjamin and Francois for sorting it out! | |
| Feb 9, 2013 at 13:12 | comment | added | Benjamin Steinberg | Francois. That is essentially my answer. | |
| Feb 9, 2013 at 5:56 | comment | added | François G. Dorais | (...) Assuming such non-interfering $w$'s can be chosen, this gives a recursively presented group with the required properties. Then, as I understand from the answer, this group can be embedded into a finitely presented group without additional torsion. | |
| Feb 9, 2013 at 5:39 | comment | added | François G. Dorais | (...) If $\exists m \forall n \phi(p,m,n)$ is true then we eventually stabilize at some $m$ and the word $w$ we picked for this $m$ has order $p$. Otherwise, all the potential $w$'s we picked eventually become $1$. The words $w$ have to be chosen in such a way that they don't interfere with each other much so that we don't accidentally add an element of order $p$ while working for other primes. | |
| Feb 9, 2013 at 5:36 | comment | added | François G. Dorais | Yes, I think the $\Sigma^0_2$ sets of primes are precisely the ones that can be achieved this way. The statement itself is $\Sigma^0_2$ and we can mimic a $\Sigma^0_2$-statement $\exits m \forall n \phi(p,m,n)$ as follows. For each $p$, keep track of a potential $m$ starting with $0$ and a word $w$ with the relation $w^p = 1$. As soon as you find an $n$ such that $\phi(p,m,n)$ is false, add the relation $w = 1$ then increment $m$ and pick a fresh word $w$ with the relation $w^p = 1$. (Continued...) | |
| Feb 9, 2013 at 5:05 | comment | added | Benjamin Steinberg | The answer to mathoverflow.net/questions/121268/… seems to say we get those subsets of primes living in the $\Sigma^0_2$ part of the arithmetic hierarchy. | |
| Feb 9, 2013 at 4:09 | comment | added | Benjamin Steinberg | I added a clarification in an answer below because I don't see how to prove a computable image of a difference of re sets is again a difference of re sets. | |
| Feb 8, 2013 at 22:33 | comment | added | Stefan Kohl♦ | @HW and Benjamin: I originally thought about asking which sets of primes can occur, but then preferred to ask a question that would more likely admit a definite answer -- and now you have answered even more than the former question. -- Great!! | |
| Feb 8, 2013 at 22:04 | comment | added | Benjamin Steinberg | Well what is clear is that the set of all pairs (w,p) with order of w equal to p is the intersection of an re and co-re set. Now we take a computable projection to get the primes. I assume this is still in re intersect co-re. | |
| Feb 8, 2013 at 21:58 | comment | added | Benjamin Steinberg | It seems that this works. What a nice question. | |
| Feb 8, 2013 at 20:19 | history | edited | HJRW | CC BY-SA 3.0 |
Changed 'recursive' to 're' yet again.
|
| Feb 8, 2013 at 20:00 | comment | added | HJRW | Yes, Chiodo's argument shows that you can do any intersection of any re set and any co-re set of primes. (If {p_i| i in S} is the co-re set, just add relations x_i=1 for all i not in S.) And, as Benjamin observes, the set of primes is always of that form. | |
| Feb 8, 2013 at 17:01 | vote | accept | Stefan Kohl♦ | ||
| Feb 8, 2013 at 17:01 | comment | added | Stefan Kohl♦ | @HW: Thank you very much! -- Now with your clarification regarding Higman's Embedding Theorem and the restriction to recursively enumerable sets of primes, it's clear. | |
| Feb 8, 2013 at 16:57 | comment | added | Benjamin Steinberg | The paper of Chiodo seems to show that any co-re set can also be the orders of elements of a finitely presented group. See Thm 2.7. | |
| Feb 8, 2013 at 16:05 | comment | added | Benjamin Steinberg | You can enumerate words w with $w^p=1$ for some prime but you cannot figure out if $w\neq 1$. So basically it seems to me you are looking at the intersection of an re and a co-re set, or something like that. | |
| Feb 8, 2013 at 15:59 | comment | added | Benjamin Steinberg | You are right that you need the word problem decidable to guarantee that the orders be re. | |
| Feb 8, 2013 at 15:50 | comment | added | HJRW | Ugh, as Benjamin points out again, I mean re, not recursive: the fact that a recursive presentation is really a recursively enumerable presentation is a source of never-ending confusion to me. | |
| Feb 8, 2013 at 15:49 | history | edited | HJRW | CC BY-SA 3.0 |
Amended recursive to re
|
| Feb 8, 2013 at 15:43 | comment | added | HJRW | Huh, there's a sort-of interesting problem here (for a rather, er, specialised definition of interesting), isn't there? It's not clear to me that it's necessary that the set of primes occurring be recursive. (It will be recursive whenever the word problem is solvable, but of course the word problem may not be solvable.) So what sets of primes can be realised, beyond the recursive sets? | |
| Feb 8, 2013 at 15:31 | history | edited | HJRW | CC BY-SA 3.0 |
Corrected minor errors
|
| Feb 8, 2013 at 15:26 | comment | added | HJRW | Sorry, Benjamin is quite right - the set of primes does indeed need to be recursive. | |
| Feb 8, 2013 at 15:22 | comment | added | Benjamin Steinberg | Look in the section of D Cohen's book on Higman embeddings to see that a recursive presentation is enough (the generators don't need to be finite). | |
| Feb 8, 2013 at 15:17 | comment | added | Benjamin Steinberg | You need the set of primes to be recursive for this to work. In this case the free product is recursively presented which is enough for Higman. | |
| Feb 8, 2013 at 14:20 | comment | added | Stefan Kohl♦ | In any case, for reasons of cardinality, the set of primes cannot be "whatever one wants" -- there are uncountably many sets of primes, but only countably many finitely presented groups. | |
| Feb 8, 2013 at 14:06 | comment | added | Stefan Kohl♦ | Well -- but is the free product of infinitely many cyclic groups of prime order finitely generated? -- As I understand, Higman's Embedding Theorem is only for finitely generated groups, or am I missing something? | |
| Feb 8, 2013 at 13:03 | history | answered | HJRW | CC BY-SA 3.0 |