Results 1 to 3 of 3

Thread: The subgroup membership problem for F_2 x F_2

  1. #1
    MHF Contributor Swlabr's Avatar
    May 2009

    The subgroup membership problem for F_2 x F_2

    So, I am not entirely sure what belongs in here so I thought I would share a very elegant proof I came across recently, due to one K.A. Mihailova, from 1958.

    Background: Let $\displaystyle G=\langle X; R\rangle$ be a group given in terms of generators and relations. It is a natural question to ask, given two words $\displaystyle U(X)$ and $\displaystyle V(X)$,

    $\displaystyle \textnormal{is }U\equiv V \text{ mod }R \textnormal{ ?}$

    Unfortunately, this is a question which is insoluble in general: it is called the word problem for groups (note that this is equivalent to asking "$\displaystyle \textnormal{is }U(X)\equiv 1 \text{ mod }R\text{?}$").

    For more details, and examples, see wiki. Note that some of the examples there are finitely presented.

    This is a driving question in group theory: Hyperbolic groups, probably the most studied class of groups of today, were defined so as to have soluble word (and conjugacy) problem*.

    However, Free groups are nice. A word is freely equal to the trivial word if and only if it is the trivial word after freely reducing it. Free reduction is a finite process, so we have an algorithm to determine if a word is the trivial word or not. Similarly, two words are conjugate if and only if, after cyclically reducing them, they are cyclic shifts of one another. Finally, two free groups are isomorphic if and only if they are of the same rank - they are generated by the same number of elements. In fact, it is a theorem that every question you could want to know about free groups can be answered.

    That said, the direct product of two free groups is not nice. This is counter-intuitive: free groups are nice, and so (surely) is the direct product! So presumably the direct product of two free groups is nice, no?

    Question: For all $\displaystyle H\leq F_2\times F_2$ finitely generated does there exist an algorithm to determine,

    $\displaystyle \textnormal{given }h \in F_2\times F_2\textnormal{ is }h \in H\text{?}$

    Answer: No.

    Solution: Firstly, note that $\displaystyle F_2\times F_2$ contains a copy of $\displaystyle F_n\times F_n$ for all $\displaystyle n\in\mathbb{N}\cup\{\infty\}$. This is because $\displaystyle F_n\leq F_2$ (which is well-known). So it is enough to prove the result for $\displaystyle F_n\times F_n$ for some $\displaystyle n\in \mathbb{N}$.

    So, let $\displaystyle G=\langle X; R\rangle$ be a finitely presented group with insoluble word problem. Let $\displaystyle \phi: F(X) \times F(X)\rightarrow G\times G$ in the natural way. Let $\displaystyle \Delta = \{(g, g): g\in G\}$ be the diagonal subgroup and let $\displaystyle H=\Delta\phi^{-1}$, the pre-image of $\displaystyle \Delta$ under $\displaystyle \phi$. It is clearly a subgroup of $\displaystyle F(X) \times F(X)$. Then,

    $\displaystyle (g, h) \in H \Longleftrightarrow g=h \textnormal{ in }G$.

    However, as $\displaystyle G$ has insoluble word problem you cannot solve the membership problem for $\displaystyle H$.

    That is the elegant bit of the proof over. One now has to prove that $\displaystyle H$ is finitely generated, which comes from the fact that $\displaystyle G$ is finitely presented. It is sufficient to show that,

    $\displaystyle H=\langle (x, x), (1, r), (r, 1): x\in X, r \in R\rangle$

    (where $\displaystyle G=\langle X; R\rangle$) which I shall leave as an exercise (it isn't too hard). Alternatively, you can find all this here.

    The key point to take away is this: the direct product isn't nice...

    *Basically, Gromov took an old algorithm, called Dehn's algorithm, which solved these two problems and found the most general class of groups which it would work for.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Nov 2009
    Berkeley, California
    What I find most fascinating about the unsolvability of the word problem and related unsolvability problems in group theory is how readily they tell us how hard a problem is in other branch of math. For example, it seems intractable to develop methods of determining whether two $\displaystyle 4$-manifolds are homeomorphic since given any free group $\displaystyle F$ one can construct a $\displaystyle 4$-manfiold $\displaystyle M$ such that $\displaystyle \pi_1\left(M\right)=F$. Thus, to be able to solve this problem would imply that we would be able to tell from a presentation whether two free groups are isomorphic.

    Are you aware of any more examples of this? Do you do work in this area? I didn't think people were doing this kind of group theory as much anymore.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Swlabr's Avatar
    May 2009
    Quote Originally Posted by Drexel28 View Post
    ....would be able to tell from a presentation whether two free groups are isomorphic.
    We can tell this - it is dependent on the rank! Two free groups are equal if and only if they are generated by the same number of elements. (This book is an excellent reference for free group stuff).
    However, you are correct in principle. Every finitely presented group is the fundamental group of some 4-manifold, and as one cannot, in general, prove that two such groups are isomorphic, you are done.

    I believe that the same does not hold for 3-manifolds - if I remember correctly, given two fundamental groups of 3-manifolds one can prove if they are isomorphic, using Dehn's algorithm (which is the algorithm from which Hyperbolic Groups came along).

    I don't really work in this area. However, I am unsure if it was something studied in its own right*. I mean, you'd get a class of groups and you'd try to prove they the word/conjugacy/isomorphism problems hold, or you'd take an algorithm and prove that it works for such-and-such a class (for instance, small cancellation theory or Hyperbolic groups both came up in this way). What people do do for sure is work out how efficient algorithms are. I recently went to a talk by someone who was talking about an efficient algorithm for calculating the word problem for automorphisms of finitely generated hyperbolic groups, I think it was. It was pretty neat.

    The idea was this:

    Two automorphisms are equal if and only if the generators are mapped, pairwise, to the same elements,

    $\displaystyle \phi_x: a_1\mapsto x_1, 1_2\mapsto x_2, \ldots, a_n\mapsto x_n$

    $\displaystyle \phi_y: a_1\mapsto y_1, 1_2\mapsto y_2, \ldots, a_n\mapsto y_n$

    then $\displaystyle \phi_x=\phi_y$ if and only if $\displaystyle x_i=y_i$ for all i. As the word problem for hyperbolic groups is soluble, we are done. However, this algorithm is very inefficient so he had come up with a better one.

    *Well, after the first counter-examples were fround. But I am very unsure about this...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. difference between membership and subset operators
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 6th 2011, 11:44 PM
  2. [SOLVED] Set Membership Cycles: The Axiom of Regularity in ZF Set Theory.
    Posted in the Discrete Math Forum
    Replies: 83
    Last Post: Jul 27th 2010, 03:28 AM
  3. MemberShip Tables
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: Jul 17th 2010, 11:32 PM
  4. dendrogram about a known membership
    Posted in the Math Software Forum
    Replies: 0
    Last Post: Aug 13th 2009, 10:32 AM

Search Tags

/mathhelpforum @mathhelpforum