7
$\begingroup$

Upon thinking about this question, I have a feeling that there is an interesting general problem like that, but I cannot verbalise it. Here is an approximation.

The question is: given a finitely generated group $G$ and a finite set $S\subset G$, we want to find out whether the subgroup generated by $S$ is the whole group. Is there an algorithm deciding this?

One has to specify how $G$ and $S$ are presented to a machine. As for $S$, its elements are given as words in some generating set for $G$. The question how to represent a group is more delicate. Obviously not by a set of relations, since the identity problem is undecidable. There are two ways I see.

1) Let's say that $G$ is nice if there is an algorithm deciding the above problem for this group only. For example, $\mathbb Z^n$ is nice, [edit:] free groups are nice, and probably many others. Are all groups nice? What about some reasonable classes, like lattices in Lie groups?

2) This one is the best approximation of my intuitive picture of a question. Suppose we have an algorithm $A$ deciding the identity problem in $G$. (This algorithm tells us whether two elements of $G$, presented as words, are equal.) Or maybe it's an oracle rather than algorithm, I don't feel the difference. Can we decide the above problem using $A$?

Update. It turns out that even $F_6\times F_6$ is not nice in the above sense (see John Stillwell's answer). This kills the second part too. The only question that remains unanswered is the one with the least motivation behind it: Is "generating problem" solvable in lattices of Lie groups?

Improve this question
$\endgroup$
5
  • $\begingroup$ I think the concept you want is that of an automatic group: en.wikipedia.org/wiki/Automatic_group $\endgroup$
    – Qiaochu Yuan
    Commented Apr 4, 2010 at 21:18
  • $\begingroup$ I think it's too restrictive. Is Heisenberg group automatic? $\endgroup$
    – Sergei Ivanov
    Commented Apr 4, 2010 at 21:25
  • $\begingroup$ Wikipedia says no. So maybe you're right. $\endgroup$
    – Qiaochu Yuan
    Commented Apr 4, 2010 at 22:02
  • $\begingroup$ Note that FxF is automatic, so the generating problem is unsolvable in automatic groups. $\endgroup$
    – HJRW
    Commented Apr 5, 2010 at 2:31
  • $\begingroup$ The generating problem is not solvable in lattices in Lie groups. For instance, F x F is a lattice in SL_2(R) x SL_2(R). $\endgroup$
    – HJRW
    Commented Apr 5, 2010 at 2:34

3 Answers 3

Reset to default
9
$\begingroup$

The answer to the title question is that the problem is unsolvable. See p. 194 of Lyndon and Schupp's Combinatorial Group Theory, where it is called the "generating problem." It is unsolvable even when $G$ is the direct product of free groups of rank at least 6.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't have that book handy, is the proof involved or is there a quick hint? $\endgroup$
    – François G. Dorais
    Commented Apr 4, 2010 at 23:45
  • $\begingroup$ François, in the book they deduce the unsolvability of the generating problem fairly easily from unsolvability of the triviality problem for a group with six generators. But the latter comes from a construction of Rabin (Annals of Math. 67 (1958), pp. 172--194) which is quite involved. The unsolvability of the generating problem is due to C.F. Miller On Group-Theoretic Decision Problems and Their Classification, Princeton University Press, 1971 (also hard to access, I'm afraid). $\endgroup$
    – John Stillwell
    Commented Apr 5, 2010 at 1:37
  • 1
    $\begingroup$ Francois, the 'Fibred products' section of the following Tricki article explains how to turn pathologies in arbitrary fp groups into different pathologies in FxF. tricki.org/article/New_groups_from_old $\endgroup$
    – HJRW
    Commented Apr 5, 2010 at 2:30
  • $\begingroup$ Ah! Thanks for the pointers, John and Henry. $\endgroup$
    – François G. Dorais
    Commented Apr 5, 2010 at 12:21
6
$\begingroup$

Hyperbolic groups are not nice in your sense: Baumslag-Miller-Short used Rips construction to build a hyperbolic group $G$ for which there is no algorithm to decide whether a finitely generated subgroup is all of $G$, see here.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I was thinking about free groups and generalized beyond true. Now fixed. $\endgroup$
    – Sergei Ivanov
    Commented Apr 4, 2010 at 23:10
5
$\begingroup$

Let me mention that in the context of computational group theory, it is more natural to consider the group membership problem: given the generators, say as matrices $A_i \in SL(n,\Bbb Z)$ you want to decide whether matrix $M$ lies in the group generated by $A_i$. Clearly, we can apply the group membership to standard generators to decide whether $A_i$ they generate some given group $G$. Unfortunately, this is in fact a much harder problem - since $SL(4,\Bbb Z)$ contains a product of two copies of $F_2$, this is undecidable. Interestingly, one can decide in polynomial time whether the group the $A_i$'s generate is finite or infinite, as well as whether it is virtually solvable: see here and here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .