# Primes occurring as orders of elements of a finitely presented group

Is it true that given a finitely presented group $G$, either all primes or only finitely many of them occur as orders of elements of $G$?

-

No. The set of primes can be whatever you want (added: within reason! As Benjamin Steinberg points out, it can in fact be any recursively enumerable set of primes).

First, note that for infinitely presented groups, the torsion can be whatever you like: the torsion in the group

$*_i \mathbb{Z}/p_i$

is precisely the set of primes $p_i$, by standard facts about free products. (Added: As long as the set of $p_i$ is recursively enumerable, then this group admits a recursive presentation on a countable set of generators.)

By Higman's Embedding Theorem, the above group can be embedded in a finitely presented group. More subtlely, this embedding doesn't introduce any new torsion---see, for instance, Theorem 2.5 of this preprint of Chiodo.

Clarification: Higman's Embedding Theorem is commonly stated as only applying to finitely generated countable groups. In fact, an old construction of Higman, Neumann and Neumann shows how to embed a countably generated group into a 2-generated group; if the countably generated group is recursively presented, then the 2-generated group can be taken to be recursively presented as well.

Further update: Following Benjamin Steinberg's comments below answer and an argument in another paper of Chiodo (see also Francois G. Dorais's comments), I think we have a very exciting characterization of the sets of primes that can occur as torsion in finitely presented groups. (For the solvable-word-problem case, one also needs a theorem of Clapham, which says that the Higman Embedding can be made to preserve solvability of the word problem.)

Very exciting theorem:

Let $P$ be a set of primes.

1. $P$ occurs as the torsion in some finitely presented group if and only if $P$ is $\Sigma^0_2$.
2. $P$ occurs as the torsion in some finitely presented group with solvable word problem if and only if $P$ is recursively enumerable.
-
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? –  Stefan Kohl Feb 8 '13 at 14:06
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. –  Stefan Kohl Feb 8 '13 at 14:20
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. –  Benjamin Steinberg Feb 8 '13 at 15:17
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). –  Benjamin Steinberg Feb 8 '13 at 15:22
It seems that this works. What a nice question. –  Benjamin Steinberg Feb 8 '13 at 21:58

Notation:

If $n\in \mathbb{N}$, then we denote by $\pi(n)$ the set of all non-trivial factors of $n$, including $n$ but excluding $1$. Call a set $X \subseteq \mathbb{N}$ factor-complete if it is closed under taking non-trivial factors. That is, $n\in X \Rightarrow \pi(n) \subseteq X$. Now we can state a strengthened answer to the main question of this post:

Complete characterisation:

Let $X\subseteq \mathbb{N}$. Then the following are equivalent:

$1$. $X$ is the set of orders of torsion elements of a finitely presented group $G$.

$2$. $X$ is factor-complete and has a $\Sigma_{2}^{0}$ description.

That $1\Rightarrow 2$ is immediate; torsion-orders are closed under taking factors, and have a $\Sigma_{2}^{0}$ description (see the proof of theorem 3.5 in arXiv:1107.1489v2). That $2 \Rightarrow 1$ can be seen from the following result, which is proved by a generalisation of an argument provided by Francois Dorais in an earlier post on this thread:

Technical result:

There is a uniform algorithm that, on input of a computable function $\phi: \mathbb{N}^3 \to \mathbb{N}$ which describes a factor-complete $\Sigma_{2}^{0}$ set $A$, outputs a finite presentation $P_{\phi}$ such that $A$ is precisely the set of torsion elements of $gp(P_{\phi})$.

As any set of primes is factor-complete, we get the following corollary.

Answer to main question:

A set of primes $A$ appears as the torsion elements of a finitely presented group if and only if $A$ has a $\Sigma_{2}^{0}$ description.

Observe that if $X\subseteq \mathbb{N}$ then the set $X_{prime}:=\{p_{i}\ |\ i \in X\}$ is factor-complete and one-one equivalent to $X$ (being a set of primes, with a computable numbering). So we conclude with the following:

Sets which can be realised up to one-one equivalence:

Given any $\Sigma_{2}^{0}$ set $A$, the set $A_{prime}$ is one-one equivalent to $A$, and can be realised as the set of orders of torsion elements of some finitely presented group $G$.

For completeness, we provide the proof of the technical result. This is the construction described by Francois Dorais, generalised and applied carefully so that none of the torsion elements bump in to each other'. Apologies for its lenght.

Proof of technical result:

Let $\{a \in \mathbb{N}\ | \ (\exists m)(\forall n) (\phi(a,m,n)=1)\}$ be the description for the factor-complete $\Sigma_{2}^{0}$ set $A$, where $\phi: \mathbb{N}^3 \to \mathbb{N}$ is our computable function. Let $p_{1}, p_{2}, \ldots$ be the standard indexing of the primes ordered by size. Then we construct a countably generated recursive presentation as follows: Take the infinite set of symbols $x_{1}, x_{2}, \ldots$; this is our generating set. For any fixed $i>1$, add the relation $x_{p_{i}}^{i}=1$. Then, start successively computing $\phi(i,1,1), \phi(i,1,2), \phi(i,1,3), \ldots$ increasing the last variable by $1$ each time. If at some point $\phi(i,1,n)\neq 1$ then stop, add the relations $x_{p_{i}}=1$, $x_{p_{i}^{2}}^{i}=1$, and start successively computing $\phi(i,2,1), \phi(i,2,2), \phi(i,2,3), \ldots$. If again some $\phi(i,2,n)\neq 1$, then stop, add the relations $x_{p_{i}^{2}}=1$, $x_{p_{i}^{3}}^{i}=1$, and start computing $\phi(i,3,1),\phi(i,3,2), \ldots$. By interleaving this process for all $i \in \mathbb{N}$, we get a countably generated recursive presentation which we denote by $Q_{\phi}$. Notice that:

a) If $i \in A$, then there will be some (smallest) $m$ such that $\phi(i,m,1)=1, \phi(i,m,2)=1, \ldots$, and so the relation $x_{p_{i}^{m}}^{i}=1$ will be present, but no other relation involving $x_{p_{i}^{m}}$, and so $\langle x_{p_{i}^{m}} \rangle \cong C_{i}$ becomes a free product factor in this group.

b) If $i \notin A$ then for all $m \in \mathbb{N}$ we will have the relation $x_{p_{i}^{m}}=1$, and since $A$ is factor-complete $i$ does not divide any element of $A$. Hence no element of order $i$ occurs in the group.

So we end up with the group $gp(Q_{\phi}) \cong F_{\infty}$ $* _ {a \in A} ( * _ {j \in \pi(a)} C_{j})$

(With a slightly more complicated indexing, one could do away with the $F_{\infty}$ factor). As $A$ is factor-complete, we immediately see that it is the set of orders of torsion elements of $gp(Q_{\phi})$. Now apply the construction of Higman-Neumann-Neumann, and then the construction of Higman, to embed this in a finitely presented group with presentation $P_{\phi}$. Note that these embeddings strictly preserve the set of orders of torsion elements (see lemma 6.9 and theorem 6.10 of M. Chiodo Finding non-trivial elements and splittings in groups'). Also note that this construction is completely uniform in the computable function $\phi$ used to describe the set $A$.

-
Wow, still a more general result ... -- Great! -- Thanks! –  Stefan Kohl Feb 14 '13 at 20:52
Minor remark: on this site, for some reasons set brackets need to be escaped by two backslashes -- otherwise they vanish. –  Stefan Kohl Feb 14 '13 at 20:58
@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. –  user31415 Feb 14 '13 at 23:20
@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). –  user31415 Feb 15 '13 at 0:36
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. –  user31415 Feb 15 '13 at 0:45

This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function $f\colon U\to Primes$ and r.e. sets L,K contained in U such that $P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer.

Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with $u^p=1$ in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K).

Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations $x^{f(x)}=1$ for x in L and $x=1$ for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one).

Edit. I have learned from Computable images of differences of r.e. sets that the sets of the above form are precisely the $\Sigma^0_2$ sets of the arithmetic hierarchy and hence much broader than differences of re sets. In his comments to HW's answer François sketches how to construct the analogue of G above directly from a logical formula.

-
I think in the last paragraph the generators of $G$ are meant to be the projections of the elements of $U$ to the first coordinate, and similarly the $x$ in the basis in $x^{f(x)} = 1$ should rather be its projection to the first coordinate -- or am I mistaken? Otherwise -- as far as I can tell!! -- this looks right to me. -- Thanks again! –  Stefan Kohl Feb 9 '13 at 10:52
Last paragraph U is any re set not just the pairs in the second paragraph. –  Benjamin Steinberg Feb 9 '13 at 13:11
O.k., thank you. –  Stefan Kohl Feb 9 '13 at 13:51
No, this should definitely be a separate answer, and deserves full credit. This is really a great example of how interesting decision theory arises from innocuous group-theoretic questions. –  HJRW Feb 10 '13 at 15:26
@HW, this question ended up being one of the most fun experiences I had on MO. It shows that by putting together several mathematicians who may never have met in person with differing areas of expertise one can pose and solve a nice problem. –  Benjamin Steinberg Feb 10 '13 at 20:59