5
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ See Problem 1.4 <a href="arxiv.org/PS_cache/arxiv/pdf/1103/…> $\endgroup$
    – user6976
    Oct 30, 2011 at 12:22
  • $\begingroup$ Thanks, for the link Mark! So, I guess this question is quite tough if even existence is hard going. $\endgroup$
    – Victor
    Oct 30, 2011 at 12:47

1 Answer 1

7
$\begingroup$

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 (*).

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Victor
    Oct 30, 2011 at 20:56
  • $\begingroup$ (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? $\endgroup$
    – Victor
    Oct 30, 2011 at 20:57
  • $\begingroup$ 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: sciencedirect.com/science/article/pii/S0049237X08719438 $\endgroup$
    – Victor
    Oct 30, 2011 at 21:00
  • 1
    $\begingroup$ 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 $\endgroup$
    – Denis Osin
    Oct 30, 2011 at 21:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Denis Osin
    Oct 30, 2011 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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