Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question: is there any example of a finitely presented (or at least finitely generated) group $G$ with an infinite cyclic subgroup $C \leqslant G$ such that the word problem in $G$ is solvable but the membership problem for $C$ in $G$ is unsolvable?

I would guess that such examples should exist, since otherwise amalgams and HNN-extensions of f.p. groups with solvable word problem along cyclic subgroups would again have solvable word problem. But using such free constructions one could (possibly?) produce a group with unsolvable word problem, starting with a group for which the word problem is solvable...

share|improve this question

1 Answer 1

up vote 6 down vote accepted

@Ashot: Finitely presented examples exist. It is in our paper with Olshanskii, Olshanskii, A. Yu.; Sapir, M. V., Length functions on subgroups in finitely presented groups. Groups—Korea '98 (Pusan), 297–304, de Gruyter, Berlin, 2000.

An easier construction is this. Take the free Abelian group $A$ with generators $x_i, i=0,1,...$. Consider an injective recursive function $\mathbb{N}\to \mathbb{N}$ with non-recursive image $f(n)$. Impose the following relations on $A$: $x_{f(n)}=x_0^{n!}, n=1,2,...$. The word problem in the resulting (infinitely generated) group $A_f$ is solvable. Indeed, consider any word $w=x_{i_1}^{k_1}...x_{i_m}^{k_m}$, $i_1\lt i_2\lt...$. That word is equal to 1 if and only if each $i_s$ is of the form $f(n_s)$ for some $n$ and $k_1n_1!+k_2n_2!+...=0$. That means all $n_i$ cannot be much bigger than $\max |k_i|$. Thus checking $w=1$ requires finite number of calculations of the function $f(n)$, so it is decidable. On the other hand the membership problem of $x_m$ into $\langle x_0\rangle$ is clearly undecidable since $f$ has non-recursive image.

Now use Clapham's version of Higman's embedding and embed $A_f$ into a finitely presented group $G$ with decidable word problem. Given $i$, one can recursively find a word in $G$ representing $x_i$. Thus the membership problem in the cyclic subgroup $\langle x_0\rangle$ of $G$ is undecidable.

Update Here is how to construct an injective recursive function with non-recursive image. Using Matiyasevich's theorem, find a polynomial $p(x_1,...,x_s)$ such that the solvability of the equation $a=p(x_1,...,x_s)$ is undecidable. Now take any Turing machine $M$ that computes $p(x_1,...,x_n)$ in binary. Add a new tape to $M$ and during the computation of $M$ write down the history of computation (i.e. numbers of the executed commands in binary, separated by number 3) on the new tape. When the machine stops, interpret the word written on the extra tape and the value of $p(x_1,...,x_s)$ as one number $f(x_1,...,x_s)$ (say, write first the value of $p$, then number 4, then the history, view the whole number as written in the 5-ary system). The function $n$ is clearly recursive and injective because the history determines the values of $x_1,...,x_s$ (make the machine scan the input before it computes $p$). It is also clear that the image of $n$ is not recursive. To make $n$ a function in one variable, precompose it with a (Goedel) function that enumerates ${\mathbb Z}^s$.

share|improve this answer
    
Thanks, Mark! Which statement from the paper I should look at? –  Ashot Minasyan May 7 '12 at 14:01
    
It is not explicitly there, but can be easily deduced. In Corollary 1 we describe all length functions of cyclic subgroups of finitely presented groups. The way it is proved is this. First embed the cyclic group into a finitely generated group $G_1$ with given length function. If the length function is recursive, then the group $G_1$ will have decidable word problem. Then embed $G_1$ into a finitely presented group with decidable word problem. The membership problem in the cyclic subgroup is undecidable if the image of the length function is not recursive. –  Mark Sapir May 7 '12 at 14:20
    
Thanks for the easy construction, it is very nice. It seems also easy to construct an injective recursive function $g$ with non-recursive range starting with a non-injective function $f$ with same properties. WLOG assume that $f(\mathbb{N}) \subseteq 2\mathbb{N}$. Set $g(1)=f(1)$ and start recording the elements in the range of $f$. Let $g(n)=f(n)$ if $f(n)$ has not been recorded yet, otherwise let $g(n)=2n+1$. Clearly $g:\mathbb{N}\to\mathbb{N}$ is injective, recursive, but still has non-recursive range as $g(\mathbb{N}) \cap 2\mathbb{N}=f(\mathbb{N})$. –  Ashot Minasyan May 7 '12 at 18:46

Your Answer

 
discard

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.