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 16, 2013 at 20:05 | comment | added | HJRW | Stefan - sure, but a group encoding all natural numbers is necessarily much easier than any other, since the Turing machine recognising the set of natural numbers is necessarily very easy. A set which is even slightly algorithmically non-trivial, such as the set of primes, is likely to be much harder. | |
| Feb 16, 2013 at 19:02 | comment | added | Stefan Kohl♦ | @Maurice: I find Higman's simple group particularly nice since it admits the explicit determination of a permutation representation which is suitable for computation (see the first example in gap-system.org/DevelopersPages/StefanKohl/rcwa/doc/chap7.html). | |
| Feb 16, 2013 at 18:43 | comment | added | user31415 | @Stefan: Of course, Higman's universal finitely presented group also has this property (though the presentation is likely to be a little more complicated). I think the real challenge here is to find the "best" Turing machine to encode the set you care about, and then directly apply Higman's construction. As I commented earlier, this is mostly about chasing Turing machines, which can get complicated. Valiev came up with one presentation, and then improved it (4 years later). I'll take a look at the Higman reference next week when I have library access. | |
| Feb 16, 2013 at 18:31 | comment | added | Stefan Kohl♦ | @Maurice: Precisely all primes may be difficult, I don't know. But there is a nice example of a group having all primes (and in fact all positive integers) as orders of torsion elements, namely the Higman-Thompson group (which happens to be a simple group), see Higman, G., Finitely Presented Infinite Simple Groups, Department of Pure Mathematics, Australian National University, Canberra, Notes on Pure Mathematics (1974). That group even admits explicit computation. | |
| Feb 16, 2013 at 18:17 | comment | added | user31415 | @Stefan: Regarding your question "Would it be feasible to find a finite presentation for a group whose orders of torsion elements are precisely the primes congruent to 1 mod 4?" This is a recursive set of primes, but the task of finding a finite presentation with this set of torsion orders is still quite difficult. An even easier task: a finite presentation whose torsion orders is precisely all primes. Sounds easy, but it is not. I recommend looking at Valiev (arXiv:1107.1489v2 citations [25], [26]). These are short papers. In [26] he constructs a 14-generator 21-relator universal fp group. | |
| Feb 16, 2013 at 18:07 | comment | added | user31415 | (...continued) Lempp realised a $\Sigma_{2}^{0}$-complete set in the set of all finitely presented groups, but that was at the group level. Similarly, Boone-Rogers realised a $\Sigma_{2}^{0}$-complete set in the set of all finitely presented groups. The set K from theorem 3.6 of arXiv:1107.1489v2 , if shown to be $\Sigma_{3}^{0}$-complete, would be another interesting encoding. | |
| Feb 16, 2013 at 17:53 | comment | added | user31415 | @HW @ Stefan: My apologies. I have indeed claimed something in my comment which is not true (though the discussion that follows still holds). The comment should instead begin as follows: Encoding a $\Pi_{2}^{0}$-complete set into a single finitely presented group, which I first did in arXiv:1107.1489v2 (theorem 5.8), shows that........ So no, I did not encode arbitrary $\Sigma_{2}^{0}$ or $\Pi_{2}^{0}$ sets into a single finitely presented group. But I have a $\Pi_{2}^{0}$-complete set encoded into a single finitely presented group, so can reduce all $\Pi_{2}^{0}$ sets to it. (tbc....) | |
| Feb 16, 2013 at 15:33 | comment | added | HJRW | MC, could you briefly point to where in arXiv:1107.1489v2 you encode arbitrary $\Sigma^0_2$ sets into groups? Are you referring to your Theorem 5.8? | |
| Feb 15, 2013 at 11:24 | comment | added | Stefan Kohl♦ | @Maurice: Interesting! -- Anyway I'd be interested to see some concrete examples. To start with something (supposedly!) easy, would it be feasible to find a finite presentation for a group whose orders of torsion elements are precisely the primes congruent to 1 mod 4? -- Knowing that something exists is one important thing, but explicitly finding it is still more (in particular for someone like me with a background in explicit computation!). | |
| Feb 15, 2013 at 0:45 | comment | added | user31415 | Additionally, chasing Turing Machines has been done in the past, with some success. Valiev has constructed explicit examples of universal finitely presented groups. I would be interested in seeing the following: 1. An explicit finite presentation of a universal finitely presented torsion-free group. 2. An explicit finite presentation of a group whose set of orders of torsion elements form a $\Sigma_{2}^{0}$-complete set. Perhaps an analysis of the work of Valiev would be of some use, but I can't say for sure. | |
| Feb 15, 2013 at 0:36 | comment | added | user31415 |
@Stefan: The problem here is that you are not given the ($\Sigma_{2}^{0}$) set $A$, but a description involving just the function $\phi$. It is possible to come up with very complicated descriptions of very easy' sets (recognising descriptions of the empty set is undecidable, so these can get very hard!). Since there are infinitely many distinct $\Sigma_{2}^{0}$ sets, such presentations would be unbounded in length' (the presentations I describe above can all be made to be 2-generator, so we can define length as the sum of the lengths of the generators).
|
|
| Feb 15, 2013 at 0:07 | comment | added | Stefan Kohl♦ | @Maurice: I wonder to what extent these nice results can be turned into practical algorithms. Thus for example for which sets $X$ of integers it would be computationally feasible to obtain a finite presentation of a group which has precisely the $n \in X$ as orders of torsion elements. Also it would be interesting to see how long the resulting presentations would be in concrete nontrivial examples. | |
| Feb 14, 2013 at 23:30 | comment | added | user31415 | Figured it out (spacing around the _ ). Fixed it. | |
| Feb 14, 2013 at 23:29 | history | edited | user31415 | CC BY-SA 3.0 |
Improved formatting
|
| Feb 14, 2013 at 23:21 | comment | added | user31415 | That formatting issue is baffling me, and I have no way of fixing it at the moment (first time on M.O.). | |
| Feb 14, 2013 at 23:20 | comment | added | user31415 | @Stefan: Encoding arbitrary $\Sigma_{2}^{0}$ or $\Pi_{2}^{0}$ sets into a single finitely presented group, which I first did in arXiv:1107.1489v2, shows that such groups (even individually) are incredibly rich. When considered collectively, they are even richer: A result by Boone-Rogers shows that the set of finite presentations of groups with solvable word problem is $\Sigma_{3}^{0}$-complete. I have yet to see (but am interested in seeing) if any set harder than $\Sigma_{2}^{0}$ or $\Pi_{2}^{0}$ can be encoded into a single finitely presented group. | |
| Feb 14, 2013 at 21:22 | comment | added | Stefan Kohl♦ | In the comment it does compile -- strange. | |
| Feb 14, 2013 at 21:21 | comment | added | Stefan Kohl♦ | Another formatting issue: the expression $F_{\infty}*{a \in A}(*{j \in \pi(a)}C_{j})$ does not seem to compile. | |
| Feb 14, 2013 at 21:19 | comment | added | Stefan Kohl♦ | I posted this question since I wondered how rich the class of finitely presented groups is in a certain sense. I would have found finitely presented groups rather boring if the answer to my question would have been "yes". -- But now the answers tell me that the class of finitely presented groups is richer than I thought! | |
| Feb 14, 2013 at 21:17 | history | edited | user31415 | CC BY-SA 3.0 |
Numbering in the "complete characterisation" was accidentally inverted.
|
| Feb 14, 2013 at 21:16 | comment | added | user31415 | Arrows were indeed wrong, thanks. Factors and divisors mean the same thing (I believe). Thank you for checking through so thoroughly! | |
| Feb 14, 2013 at 21:08 | comment | added | Stefan Kohl♦ | Further minor remarks: 1. I think "$1 \Rightarrow 2" and "$2 \Rightarrow 1" at the beginning of your post need to be interchanged(?) 2. "factors" should rather mean "divisors", right? | |
| Feb 14, 2013 at 21:05 | history | edited | user31415 | CC BY-SA 3.0 |
Improved formatting (only).
|
| Feb 14, 2013 at 21:03 | comment | added | user31415 | Ah, damn. My bad. First time posting to MO. I thought I had sorted out all the formatting issues. | |
| Feb 14, 2013 at 21:00 | comment | added | user31415 | No problem. I really should have realised this when I was working on arXiv:1107.1489v2. Full credit to Francois for the very useful construction in computability theory. Did you have a particular application of this question in mind when you asked it? | |
| Feb 14, 2013 at 20:58 | comment | added | Stefan Kohl♦ | Minor remark: on this site, for some reasons set brackets need to be escaped by two backslashes -- otherwise they vanish. | |
| Feb 14, 2013 at 20:52 | comment | added | Stefan Kohl♦ | Wow, still a more general result ... -- Great! -- Thanks! | |
| Feb 14, 2013 at 18:58 | history | answered | user31415 | CC BY-SA 3.0 |