F.p. groups where all elements of the same order are conjugate - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:54:25Z http://mathoverflow.net/feeds/question/79510 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79510/f-p-groups-where-all-elements-of-the-same-order-are-conjugate F.p. groups where all elements of the same order are conjugate Victor 2011-10-30T08:55:27Z 2011-10-30T19:33:38Z <p>The question I want to ask is related to the Boone-Higman conjecture (see <a href="http://mathoverflow.net/questions/73568/embedding-in-f-p-simple-groups" rel="nofollow">http://mathoverflow.net/questions/73568/embedding-in-f-p-simple-groups</a> for the details).</p> <p>We discussed recently with Ievgen Bondarenko this conjecture and he noticed that it would follow if the answer to the following question was "yes":</p> <p>\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?}</p> <p>Does anybody know if that is "no" actually? Or, at least, is it "no" if we take out the condition of solubility of WP?</p> <p>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?</p> http://mathoverflow.net/questions/79510/f-p-groups-where-all-elements-of-the-same-order-are-conjugate/79539#79539 Answer by Denis Osin for F.p. groups where all elements of the same order are conjugate Denis Osin 2011-10-30T19:22:45Z 2011-10-30T19:33:38Z <p>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. </p> <p>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:</p> <p>(*) There is no algorithm that allows to decide for any given $x,y\in R$ whether $|x|=|y|$.</p> <p>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$. </p> <p>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 (*).</p> <p>Given two elements $x,y\in R$, we run two algorithms.</p> <p><strong>Algorithm A.</strong> 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.</p> <p><strong>Algorithm B.</strong> 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. </p> <p>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 (*).</p>