Re: complexity of the subgroup problem in free groups

mareg_at_mimosa.csv.warwick.ac.uk
Date: 07/12/04 

Date: Mon, 12 Jul 2004 08:46:12 +0000 (UTC)

In article <k2wu1a2i9h.fsf@vayu.cs.iitm.ernet.in>,
        Abi <abi_k--cut-here--@myrealbox.com> writes:
>actually, from what i read about free groups and todd coxeter
>enumeration, and stuff,
>
>1. The problem of finding whether some word lies in this sub-group is
> decidable only if the index of the subgroup is finite.

This is not true - maybe you meant "if" rather than "only if"?
The problem you are talking about is known as the generalized word problem.
It is solvable for a finitely generated subgroup of finite index in a group
defined by a finite presentation.
But it is solvable in some other cases as well. For example it is solvable for
any finitely generated subgroup of a free group of finite rank, which was
the original problem in this thread.
It is of course unsolvable in general. For example there are finitely
generated subgroups of the direct product F2 x F2 of two copies of the free
group of rank 2 for which it is unsolvable.

>2. And it is undecidable in general to compute the index of the
> subgroup.

Yes, that is true. But it is useful to remember that, for finitely generated
subgroups of finite index finitely presented groups, it is possible to verify
that the index is finite - that is exactly what Todd-Coxeter coset enumeration
does. So this property is in some sense semi-decidable.

Derek Holt.

Relevant Pages

  • Re: Some group presentations
    ... is not free abelian of rank 3. ... If it had a nilpotent subgroup H of finite index, ... presented groups given a generating set, ...
    (sci.math)
  • Re: Some group presentations
    ... If it had a nilpotent subgroup H of finite index, ... there is an algorithm for computing ... presented groups given a generating set, ...
    (sci.math)
  • Re: Maximal compact subgroups
    ... I want to understand, for instance, the simple case when G is compact ... Is the existence of a maximal compact subgroup obvious in this case? ... maximal closed proper subgroup if G is compact (and ... Do we always have a closed proper subgroup of finite index? ...
    (sci.math)
  • Re: Maximal compact subgroups
    ... I want to understand, for instance, the simple case when G is compact ... Is the existence of a maximal compact subgroup obvious in this case? ... maximal closed proper subgroup if G is compact (and ... Do we always have a closed proper subgroup of finite index? ...
    (sci.math)
  • Re: four questions on free groups
    ... Does every maximal subgroup M of F have a finite index? ... No. Let a and b be two generators. ... Is there a subgroup H in F of infinite index which is not contained ...
    (sci.math.research)