MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question I want to ask is related to the Boone-Higman conjecture (see Embedding in f.p. simple groups for the details).

We discussed recently with Ievgen Bondarenko this conjecture and he noticed that it would follow if the answer to the following question was "yes":

\textbf{Question: Does every f.p. group with soluble word problem embed in a f.p. group with all elements of the same order being conjugate?}

Does anybody know if that is "no" actually? Or, at least, is it "no" if we take out the condition of solubility of WP?

Could anybody suggest some references with examples of f.p. groups with elements of the same order being conjugate. Do there exist such groups where occur all possible orders of elements?

share|cite|improve this question
See Problem 1.4 <a href="…; – Mark Sapir Oct 30 '11 at 12:22
Thanks, for the link Mark! So, I guess this question is quite tough if even existence is hard going. – Victor Oct 30 '11 at 12:47
up vote 7 down vote accepted

I think the answer to the main question is negative. That is, there exists a finitely presented group $G$ with decidable WP that does not embed into any f.p. group where all elements of the same order are conjugate.

Here is the construction. Let us start with a recursively presented group $S$ such that the WP in $S$ is decidable while the order problem (that is, given an element, find its order) is not. Such groups exist and, in fact, are not hard to construct. Then we take the direct product of $S$ and cyclic groups $\mathbb Z$ and $\mathbb Z/n\mathbb Z$ for all $n$. The resulting group, call it $R$, is recursively presented, has decidable WP, and has the following property:

(*) There is no algorithm that allows to decide for any given $x,y\in R$ whether $|x|=|y|$.

Indeed if such an algorithm existed, given $x\in S$ we could run countably many copies of this algorithm taking the generators of the cyclic subgroups $\mathbb Z$ and $\mathbb Z/n\mathbb Z$ as $y$'s. All these algorithms can be run simultaneously using the standard diagonal argument and one of them always stops, which gives the solution to the order problem in $S$.

Further let us embed $R$ into a finitely presented group $G$ with decidable WP. This is always possible since the Higman embedding preserves decidability of the WP. Suppose now that the group $G$ is embedded into a f.p. group $P$ where all elements of the same order are conjugate. We will derive a contradiction by showing that $P$ can be used to decide whether two elements of $R$ have the same order, thus violating (*).

Given two elements $x,y\in R$, we run two algorithms.

Algorithm A. Using the finite presentation of $P$, this algorithm produces the list of all elements of $P$ conjugate to $x$. If at some point we see $y$ in this list, the algorithm stops, otherwise it runs forever.

Algorithm B. This algorithm starts by solving the WP in $R$ for the elements $x,y, x^2, y^2, x^3, y^3 \ldots$. If all these elements are nontrivial, the algorithm does not stop. Otherwise let $x^n$ (or $y^n$) be the first trivial element in the list. We will only consider the case of $x^n$, the case of $y^n$ is symmetric. Then $|x|=n$. We can then use decidability of the WP in $R$ to effectively answer the question of whether $|y|=n$. Then the algorithm stops and returns the answer.

Observe now that at least one of the algorithms always stops. Indeed if $|x|=|y|$, then $x$ and $y$ are conjugate in $P$ and hence Algorithm A stops. Otherwise at least one of the orders $|x|$, $|y|$ is finite. Hence Algorithm B will stop and tell us if $|x|=|y|$. Thus we can decide whether $|x|=|y|$, which contradicts (*).

share|cite|improve this answer
This is a very neat idea to go via the order problem! Well, in the proof you use two things completely new to me: (1) that Higman's embedding preserves solubility of WP -- perhaps this is in the original paper of Boone & Higman, right?; (2) and the second is how to create a recursively presented group with insoluble order problem. I found another paper of Boone and Higman, where they write that a group $G$ has soluble order problem if and only if (a) $G$ can be embedded in a simple subgroup of a f.p. group and (b) $G$ embdes in a group $H$ in which all elements of infinite order are conjugate. – Victor Oct 30 '11 at 20:56
(cont.) But! (a) says exactly that $G$ has soluble WP, and (b) then holds automatically -- as we can always embed a group with soluble WP in an existentially closed group which always has property (b). What am I missing here? – Victor Oct 30 '11 at 20:57
Well, I can see only the first page of this paper of Boone and Higman which puts me off -- with only the statement I cited: – Victor Oct 30 '11 at 21:00
Groups with decidable WP and undecidable order problem: J. McCool, Unsolvable problems in groups with solvable word problem, Canad. J. Math., 22 (1970), 836–838. – Denis Osin 0 secs ago – Denis Osin Oct 30 '11 at 21:24
Higman embedding preserves unsolvability degree of the WP (in particular, solvability): C.R.J. Clapham, An embedding theorem for finitely generated groups, Proc. London Math. Soc. 17 (1967), 419–430. For modern proofs using S-machines this is essentially obvious. – Denis Osin Oct 30 '11 at 21:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.