1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Wallpaper Groups, Free Groups, and Trees

  1. Jul 2, 2005 #1

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    1. Describe the elements of the groups c2mm, p4mm, and p3m1. My book doesn't do a good job of explaining this notation, any help?

    2. Let m and n be positive integers. Prove that there is a homomorphism from the free group generated by n generators, [itex]F_n[/itex], onto the free group generated by m generators, [itex]F_m[/itex], if and only if m < n. Well if m = n, then the two are isomorphic, and this is obvious. If m < n, then the homomorphism that takes a word of [itex]F_n[/itex] and simply omits any occurences of [itex]x_{m+1},\, x_{m+2},\, \dots ,\, x_n[/itex] is a surjective homomorphism, where [itex]x_1,\, \dots ,\, x_n[/itex] are the generators of [itex]F_n[/itex]. I want to show that if m > n, then there is no homomorphism. This seems almost too obvious, but I'm having trouble proving it. I know that [itex]F_n[/itex] and [itex]F_n[/itex] are isomorphic if and only if m = n, and I have the isomorphism theorems. So I know that [itex]F_m[/itex] is isomorphic to [itex]F_n / \mathop{\rm Ker}(\phi )[/itex] where φ is the surjective homomorphism that was proven to exist in the first part of this proof. If there is a surjective homomorphism from [itex]F_m[/itex] onto [itex]F_n[/itex], then by the previous sentence, there is one from [itex]F_n / \mathop{\rm Ker}(\phi )[/itex] onto [itex]F_n[/itex]. Let:

    [tex]\psi \, :\, F_n / \mathop{\rm Ker}(\phi ) \to F_n[/tex]

    be this homomorphism. Then [itex]F_n[/itex] is isomorphic to:

    [tex](F_n /\mathop{\rm Ker}(\phi ) )/\mathop{\rm Ker}(\psi )[/tex]

    It seems like this should be so simple, but I can't seem to prove it.

    3. Check that {x, y|xyx-1y-1} is a presentation for [itex]\mathbb{Z} \times \mathbb{Z} = \mathbb{Z}^2[/itex]. That is to say that [itex]\mathbb{Z}^2[/itex] is isomorphic to [itex]F_2/N[/itex] where N is the smallest normal group containing [itex]xyx_{-1}y^{-1}[/itex]. Well the function defined by:

    [tex]\phi(x^{a_1}y^{b_1}\dots x^{a_n}y^{b_n}) = (\sum _{i = 1} ^n a_i , \sum _{i = 1} ^n b_i)[/tex]

    is a surjective homomorphism from [itex]F_2[/itex] to [itex]\mathbb{Z}^2[/itex]. I need to show that it's kernel is N. I know that N is contained in the kernel, so I need to show that if g is in the kernel, then it is in N, that is, if I have any word [itex]x^{a_1}y^{b_1}\dots x^{a_n}y^{b_n}[/itex], then I can express it as some conjugate of products of conjugates of products... of conjugates of xyx-1y-1. Or maybe there's a better way?

    4. Show that F2 x F2 is not a free group. That is to say that there is no set of generators such that there is a unique word for every non-identity element of the group. Suppose there were such a set of generators. Then (x,y) would only be the result of a unique word, but (x,y) = (x,0)(0,y) = (0,y)(x,0), so if the word for (x,0) is w, and the word for (0,y) is w', then ww' = w'w. w is not equal to w', neither of w and w' is a power of the other, and neither is the empty word. If w and w' are words of the same length, then w = w', which is impossible, so they are of different length. Define |w| as the length of the word w, and without loss of generality, assume |w| > |w'|. The last |w'| letters of w must be w', as must the first |w'|. Suppose let v = (w')-1w. Then we get:

    vw' = w = w'v

    Now |v| is not equal to |w'|, otherwise v = w' since v is the last |v| letters of w and w' is the last |w'| letters of w, and this would imply that w = (w')², which we already determined is impossible. Continually taking the shorter word, and finding the word that results from removing the shorter word from the front of the longer word, I think this process will eventually lead us to some sort of contradiction, namely that one of (x,0) and (0,y) is a power of the other. Is this right?

    5. Suppose we have a group action on a tree [itex]\Gamma[/itex]. If the group element g fixes two vertices, u, v of [itex]\Gamma[/itex], prove that g must leave all of the geodesic [itex]\vec{uv}[/itex] fixed.

    I'm not exactly sure what's being asked here. An action of G on [itex]\Gamma[/itex] is technically a pair of actions, one on the vertices of the tree, and the other on the edges of the tree. The action on the edges maps each element of g to a permutation of the edges. We can simply look at g as a bijective mapping from A to A, where A is the set of edges for the tree. But a geodesic is a path. It is made up of elements of A, but it is not itself an element of A, so treating g as a mapping whose domain is A, it doesn't technically make sense to speak of g leaving a geodesic fixed. Is there some aspect of the definition of an action on a tree that I'm overlooking, because as far as I can tell, the question doesn't even make sense.
     
  2. jcsd
  3. Jul 2, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    surely the action of a group on a tree cannot tear apart neighbouring vertices, if if there is an edge from x to y there is an edge for gx to gy. i don't know this but it makes sense, other wise G would simple by a group action on ExV (set of edges product set of vertices) with no "treeness properties" involved. it would then follow that 5. is true by induction on the number if edges in the shortest path from u to v.
     
  4. Jul 2, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    as for the free groups one.

    suppose that F_n surjects to F_m, and let N be the kernel, then there are m cosets
    x_1N,..,x_mN that generate a copy of F_n. can this happen if there are at most n generators in F_n?
     
  5. Jul 2, 2005 #4

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Well the group action will send the tree to itself, so in that sense it's the same tree, and so the geodesics are the same. And yes, you're right, the action does not tear apart vertices. But I'm still not sure what the question is asking. Is it saying that if the path [itex]a_1a_2\dots a_n[/itex] is a geodesic from u to v, then the path [itex]g(a_1)\dots g(a_n)[/itex] is a geodesic from g(u) to g(v) for any pair u and v? Again, g doesn't technically act on geodesics, just individual edges.
     
  6. Jul 2, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    it sends edges to edges and you;re asked to prove it preserves the geodesics. it doesn't need to 'technically' act on the geodesics for this to be true. i mean a linear map acts on pints of a vector space but it sends subspaces to subspaces to even though ti doesn't apparently act on the set of subspaces.
     
    Last edited: Jul 2, 2005
  7. Jul 2, 2005 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Unless I'm missing something, the action will send the tree to itself, so it has to preserve the geodesics. The tree and the image of the tree under the action are the same tree, are they not? After all, g is just a bijection of the vertices, and a bijection of the edges, so if the vertices are sent back to the vertices, and the edges back to the edges, then the image is just the original tree. If they're the same tree, then the geodesics are the same. An action on a tree (in general, on any graph) must be more than just a bijection of the vertices and edges, but that's not even relevant. So long as g is just a bijection of the vertices and edges, the image and pre-image are the same, and so are the geodesics. This seems too simple, so I have to assume I'm not properly understanding the question.
     
    Last edited: Jul 2, 2005
  8. Jul 2, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    well, i didn't say it was a hard theorem, or indeed one that isn't obvious (from the onyl sensible interpretation of it), though i'm not sure i agree that your observation is sufficient*. i think you can prove it by induction on path length, or by positing a counter example of minimal length and getting a contradiction.


    * use the vector space analogy. on R^2 the map (x,y) to (x,y) if y>0 and (x,y) to (-x,y) othewise is a bijection on R^2 and R^2 has the same set of subvector spaces yet the bijection doesn't preserve the subspaces.
     
    Last edited: Jul 2, 2005
  9. Jul 2, 2005 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    What does "preserve geodesics" mean? Does it mean that the geodesics of the preimage tree are geodesics of the image tree? Well that's obvious because they're the same tree. Does it mean that if a1...an is a geodesic, then so is g(a1)...g(an)? Well that's also sort of obvious, since g(a1)...g(an) is a geodesic so long as it contains no round trips, and it can't contain a round trip since if we had:

    g(ai)g(ai+1)

    being a round trip, then g(ai) is the reverse of g(ai+1), which is equal to g((ai+1)-1) by definition of an action on a graph. But since g is a bijection, this means that:

    ai = (ai+1)-1

    meaning that our original path contained a round trip, contradiction. So far, I have made no reference to the fact that some pair of points u and v are kept fixed. Or maybe it means that if a1...an is a geodesic from u' to v', then not only is g(a1)...g(an) a geodesic, but a geodesic from u' to v'. This would mean that g fixes u' and v', and if this is to be true for any pair u', v', then g would have to fix every vertex since we're saying that g(a1)...g(an) a geodesic from u' to v', but it's already true that it is a geodesic from g(u') to g(v'). But there is no reason why an action which fixes two verticse must fix them all. Suppose our tree has 4 vertices and 3 edges, in the shape of a "Y". Let it swap the two upper arms of the "Y". The central vertex and bottom vertex are fixed, as is the geodesic between them, but not all points are fixed.

    So unless there is a fourth interpretation, the result to be proved is either false, or it is both trivial and in no way dependent on whether or not g fixes some pair of points.
     
    Last edited: Jul 2, 2005
  10. Jul 2, 2005 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    i would suggest it means that if d is a geodesic from x to y then gd is the geodesic from gx to gy. gd makes sense since i can define gd to be the union of the images of ge for each edge e in d. the question is then to show that gd is a geodesic fro gx to gy. firstly does it join gx to gy and is it minimal with this property. these are "obviously true by induction" ie iffalse i pick a geodesic of minimal length for which it is false. then i claim i can split this geodesic into two smaller ones for which it must be false too contradicting the minimality
     
  11. Jul 2, 2005 #10

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    It might help you to know that I've already proven that any path from u to v is just the geodesic from u to v, plus any number of round trips thrown in. So if abc is the geodesic, then any other path from u to v would have to contain some round trip, for example:

    abdee-1d-1c

    So any path that contains no round trips is a geodesic, and my post above proves that if some path is a geodesic, then it's image is also a geodesic.
     
  12. Jul 2, 2005 #11

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Don't you mean, "there are m cosets that generate a copy of Fm? So you're saying that if Fn surjects to Fm, and n < m, then there's a copy of Fm in Fn, but not enough generators in Fn to make it so? Or are there some extra details that involve the cosets that you're using to make this argument? Mind you, one of the problems later in this chapter asks me to prove:

    Let n be a positive integer. Prove that F2 contains a subgroup which is isomorphic to Fn.
     
  13. Jul 2, 2005 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    i did indeed get an m and n mixed up. i haven't proved the claim, just restated your problem.

    the later problem isn't worrying since the first one deals with a quotient not a subgroup, and in anycase, any subrgoup of a free group is free, so you';re just showing that there are all subgroups possible.
     
    Last edited: Jul 2, 2005
  14. Jul 2, 2005 #13

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    That's what I figured.
     
  15. Jul 2, 2005 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    an example would be, i think, the group generated by a^2, b^2 and ab. i think if we look at the words in those three elements then each is uniqeuly formed by a reduced combination of the generators. i supect one could prove some general theorem like that or could do something clever by making F_2 act on somethign and then picking a subspace of that "thing" and looking at the subgroup that acts freely on it and preserves it.

    the difference in the quotient case is that the cosets x_iN and all powers x_i^rN must be distinct and cover F_2 which i suspect will lead to some problems, though i don't know that is the best way to prove it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Wallpaper Groups, Free Groups, and Trees
  1. Abelian group (Replies: 8)

  2. Group Velocity (Replies: 1)

  3. Group Velocity (Replies: 1)

  4. Speed of Group (Replies: 3)

  5. Group velocity (Replies: 2)

Loading...