Primes occurring as orders of elements of a finitely presented group

Question

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$?

Answer 1

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.

Answer 2

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$.

Answer 3

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.