# The generalized word problem vs. the uniform generalized word problem

Before asking my question, let me define my terms.

Let $G$ be a finitely generated group with fixed generating set $A$. Let $\psi\colon (A\cup A^{-1})^{\ast}\to G$ be the canonical projection where $X^*$ denotes the free monoid on a set $X$.

Definition 1. A subgroup $H$ of $G$ has a decidable membership problem if there is a Turing machine which on input a word $w\in (A\cup A^{-1})^{\ast}$ outputs "Yes", if $\psi(w)\in H$, and "No", otherwise.

The generalized word problem is said to be decidable for $G$ if each finitely generated subgroup of $G$ has decidable membership problem.

Definition 2. $G$ has decidable uniform generalized word problem if there is a Turing machine which on input words $w_1,\ldots, w_k,w\in (A\cup A^{-1})^{\ast}$ outputs "Yes", if $\psi(w)\in \langle \psi(w_1),\ldots,\psi(w_k)\rangle$, and "No", otherwise.

One easily verifies that decidability of these problems is independent of the chosen finite generating set.

Trivially decidablity of the uniform generalized word problem implies decidability of the generalized word problem. The difference between the two problems is that the uniform generalized word problem asks that there is a computable map that takes a finite subset of $G$ to a Turing machine which decides membership in the subgroup it generates.

My question is:

Does anybody know an example of a group with decidable generalized word problem but undecidable uniform generalized word problem?

In case no example is known, here is a proposed attack that I am not capable of implementing. A finitely generated group is a Tarski monster if it is infinite but all its proper subgroups are finite. Olshanskii has constructed such "beasts".

Observation 1. A Tarski monster $G$ has decidable generalized word problem iff it has decidable word problem.

For the non-trivial direction, the Turing machine which always says "Yes" solves the membership problem in $G$. If $H$ is a proper subgroup, there is a Turing machine who knows a finite list of words representing all the elements of $H$ and so it can take an input word and use the word problem for $G$ to decide if the input word belongs to $H$.

Observation 2. A Tarski monster $G$ with decidable word problem has decidable uniform generalized word problem iff one can decide given elements $w_1,\ldots, w_k\in (A\cup A^{-1})^{\ast}$ whether $G=\langle \psi(w_1),\ldots, \psi(w_k)\rangle$.

Indeed, if the uniform generalized word problem is decidable, then one can check whether each letter of the generating set $A$ of $G$ belongs to $\langle \psi(w_1),\ldots, \psi(w_k)\rangle$.

For the converse, given words $w_1,\ldots, w_k,w\in (A\cup A^{-1})^{\ast}$ one first checks whether $\psi(w_1),\ldots,\psi(w_k)$ generates $G$. If so, the Turing machine outputs "Yes". Otherwise, $\psi(w_1),\ldots,\psi(w_k)$ generates a finite subgroup. Using decidability of the word problem, the Turing machine can compute the finite subgroup $\langle \psi(w_1),\ldots, \psi(w_k)\rangle$ (by taking products until nothing new can be obtained) and then use the word problem again to determine if $\psi(w)$ belongs to this subgroup.

Is there a Tarski monster with decidable word problem, but for which on cannot decide whether a given finite set of elements generate it?

Update

Derek has shown that Tarski monsters will always have decidable uniform generalized word problem as soon as they have decidable word problem because the word problem already gives that one can decide if a finitely generated subgroup is the whole group. I'm a bit embarrassed I didn't see that. My original question still seems open though.

-
Have you looked at Miller's survey article? ms.unimelb.edu.au/~cfm/papers/paperpdfs/msri_survey.all.pdf – HJRW Aug 7 '11 at 0:15
Miller's survey seems to confuse the uniform problem and the non-uniform problem or not distinguish them. He says the membership problem for a finitely generated subgroup H tests if a word represents an element of H, but he also assume that H is given by a finite list of generators. For a fixed subgroup, it is irrelevant to have it given because it is not part of the input. We are talking about membership in a certain formal language. In the same way he assumes groups are finitely presented and given by their presentation to discuss the word problem. But for the word problem for a groups... – Benjamin Steinberg Aug 7 '11 at 1:47
which is fixed, one only needs a finite generating set. So if you read Miler's definition of the generalized word problem, it seems he means the non-uniform one but at the same time he seems to think having the generators as part of the input. – Benjamin Steinberg Aug 7 '11 at 1:48
Nevertheless, I suspect that, if anyone knows the answer to your question, it's Miller. You could try e-mailing him if you don't get anywhere on MO. – HJRW Aug 7 '11 at 11:14
@Derek, A good trivial example is the questions of is there a Turing machine that says "Yes" if the Riemann hypothesis is true and "No" if it is not true. Since the problem has no inputs, either the machine that always says "Yes" is correct or the machine that always says "No" is correct. I have no idea which machine. – Benjamin Steinberg Aug 8 '11 at 18:07

I think the answer to your final question is no. Given a finite set of generators of a subgroup $H$ of a Tarski Monster $G$, systematically evaluate words in those generators. You can use your solution to the word problem to check equality in $G$ between words. Either you will eventually produce a finite set of group elements which is closed under multiplication by the generators of $H$ and their inverses, in which case $H$ is finite, or else you will eventually find all of the generators of $G$, in which case $H=G$.

-
Derek: You are right. So Tarski monsters don't help. What are other examples of groups where finitely generated subgroups trivially have decidable membership problem but the trivial algorithm is not uniform. – Benjamin Steinberg Aug 5 '11 at 20:14

The answer is almost certainly not known (not published), but here is a way to construct a possible example. Take a non-recursive r.e. set of numbers $I$ which is given as the set of positive values of a polynomial $p(x_1,...,x_n)$ with integer coefficients. We can assume by a theorem of Matiyasevich that in addition $p$ takes each of its values only finite number of times (see Matiyasevich's book on the 10th Hilbert problem). Consider the infinitely generated Abelian group $A$ generated by $\{a_1,a_2,..., b_1, b_2...\}$ given by the commutativity relators and relators of the form $a_i=b_j^{i}$ provided $p(gd(i))=j$ where $gd(i)$ is the $n$-tuple of natural numbers with the Goedel number $i$. Note that for every f.g. subgroup $H$ of $A$, the membership problem in $H$ is decidable, but the uniform membership problem is not decidable. The first part of this statement follows from the finiteness assumption about $p$:

Indeed, consider any finitely generated subgroup $H$ generated by $w_1,...,w_k$ and an element $g$. For $g$ to belong to $H$, its letters should belong to a finite set (because of the finiteness condition). So the membership question becomes a question about a finitely generated Abelian group which is LERF.

The second part follows from the fact that $I$ is not recursive. Indeed, the question $a_i\in \langle b_j\rangle$ is undecidable.

Now embed $A$ into a finitely generated group using small cancelation, namely, take the free group $F_2$ and an infinitely many words $u_1,u_2,..., v_1, v_2,...$ in $F_2$ satisfying, say, $C'(1/12)$, then consider the presentation obtained by replacing each $a_i$ in the presentation of $A$ by $u_i$ and each $b_i$ by $v_i$. The resulting group will have undecidable uniform membership problem, but I believe (it needs to be checked!), that the membership problem in every finitely generated subgroup will be decidable. I do not have time to check it myself now, and it may be non-trivial, but intuition tells me that it is the case.

-
@Mark, I'm probably missing something obvious here, but how does the polynomial $p$ play a role? Your presentation seems to only depend only on the r.e. set $I$. – Benjamin Steinberg Aug 8 '11 at 20:00
@Ben: Yes, the construction is not quite right (I was in a hurry). One needs to have the finiteness conditions. So the assumption $i-j\in I$ should be modified. I'll do it. – Mark Sapir Aug 8 '11 at 21:15
@Ben: I have modified the answer. – Mark Sapir Aug 8 '11 at 21:40