I want to prove that a group that acts freely on a tree is a free group. The proof I saw used weird things (in particular it considered edges as line segments, and used "half-edges") and I didn't like it so i tried to come up with my own proof, and the one I found seems much simpler, and therefore it seems suspicious (why go with a weird complicated proof when there is a simple, natural one ?). Here goes : I first prove the result assuming the action is transitive : let $G$ be a group acting freely and transitively on the (nonempty) tree $T= (V,E)$. Let $v$ be any vertex in $V$ and for $x$ a vertex, we let $N(x)$ be the set of neighbours of $x$.

I also let $N := N(v)$ for simplicity. For all $n\in N$, there is $g\in G$ with $g\cdot v = n$, because the action is transitive and since the action is free, this $g$ is unique : we denote it by $g_n$.

Then we put $S= \{g_n\mid n\in N\}$ and $S'\subset S$ such that for all $n\in N$, either $g_n$ or $g_n^{-1}$ belongs to $S'$, these options being mutually exclusive.

I want to show that $S'$ is a free generating set for $G$. First of all, it is a generating set : let $g\in G$ and let $x_0 = v, x_1,..., x_m, x_{m+1} = g\cdot v$ be a path from $v$ to $g\cdot v$ in $T$. Since the action is transitive, we can find $g_i$ with $g_i \cdot v = x_i$. Since $\{x_i, x_{i+1}\}\in E$, it follows that $g_{i+1}^{-1}g_i\in S$ and thus, since $g_1\in S$, we get that $g\in \langle S\rangle = \langle S'\rangle$, which is what I wanted to prove.

I now have to prove that $S'$ is a free generating set. But to any reduced word on $S'\cup S'^{-1}$ one can associate a path, and if, when computing the word in $G$ one gets $e$ (the unit of $G$), then we have a cycle in $T$, which is a contradiction with the fact that $T$ is a tree. Therefore $G$ has a free generating set : $G$ is a free group.

Now if the action of $G$ isn't transitive, we make it transitive : let $G$ act freely on the tree $T=(V,E)$. Let $v$ be any vertex in $V$ and $V' := G\cdot v$ (the orbit of $v$). $g\cdot v$ and $h\cdot v$ are connected in an edge in $T' = (V', E')$ if and only if either they are connected in an edge in $T$, of if all paths from one to the other in $T$ don't intersect $G\cdot v$.

Then $T'$ has no cycle because $T$ is a subdivision of $T'$, and $T$ has no cycles. Moreover, by construction, $T'$ is connected : $T'$ is a tree. The obvious action of $G$ on $T'$ is then free and transitive so we can use the previois result : $G$ acts freely and transitively on a tree, so it is a free group.

In conclusion, if $G$ acts freely on a tree, it is free.

My doubts about this proof are about the point where I prove that $S'$ is a free generating set.

They come from this fact : it seems that $\Bbb{Z}/2\Bbb{Z}$ acts freely on the tree with two vertices. The action is obvious, and $1$ has no fixed point, so the action is indeed free. But $\Bbb{Z}/2\Bbb{Z}$ is not a free group. And when looking at how my "proof" goes wheb $G=\Bbb{Z}/2\Bbb{Z}$ and $T$ is the tree with two vertices, the point where it stops working is precisely the point where I claim that $S'$ is a free generating set. While writing this, I see that my mistake is when I claim that I can define $S'$ : for $\Bbb{Z}/2\Bbb{Z}$, since $1= -1$, I cannot define $S'$ as I say. But I know that the theorem is true : what am I not seeing ?

EDIT: I'm adding this because according to another post on math.SE, it seems that the theorem that I'm mentioning (or at least one of its consequences: the Nielsen-Schreier theorem, which states that a subgroup of a free group is itself free) implies the axiom of choice for finite sets. However, in my "proof" I seem to only be using $AC(2)$, i.e. the axiom of choice for sets with $2$ elements (when picking $S'$), but if I remember correctly, the axiom of choice for finite sets isn't a consequence of $AC(2)$, and so I can't have proven the NS-theorem with only $AC(2)$. Can anyone help me spot either the mistake in the proof or the point where I use more than $AC(2)$ ?

  • $\begingroup$ Your proof is fine (it's essentially what I teach my graduate student, and what I'm putting in my $\text{Out}(F_n)$ book). The action of $\mathbb{Z}/2\mathbb{Z}$ on the tree with two vertices and one edge is not a free action: the nontrivial group element has a fixed point in the interior of the unique edge. $\endgroup$ – Lee Mosher May 27 '17 at 16:15
  • 2
    $\begingroup$ Yes, that's correct, the edges (as unordered pairs) cannot be fixed either. That's part of what "free" means for an action on a tree. $\endgroup$ – Lee Mosher May 27 '17 at 17:07
  • 1
    $\begingroup$ By the way, "simple and natural" are in the eyes of the beholder :-) To me, the simplest, most natural way to think of a tree is using topology, where an edge is indeed homeomorphic to $[0,1]$, and its interior is homeomorphic to $(0,1)$ (that is the context of my first comment). For instance, this viewpoint helped me to resolve your $\mathbb{Z}/2\mathbb{Z}$ issue. $\endgroup$ – Lee Mosher May 27 '17 at 17:10
  • 1
    $\begingroup$ There's a very short proof using a bit more topology: the quotient of a free action on a tree is a graph, and the fundamental group of a graph is a free group. $\endgroup$ – Qiaochu Yuan May 27 '17 at 18:45
  • 1
    $\begingroup$ @Max A graph is a topological space - when you visualize one in your head, you're embedding it as a topological subspace of $\Bbb R^3$ for example. $\endgroup$ – arctic tern May 27 '17 at 21:30

It seems that there is an issue with the "treeness" of $T'$ in your original argument. For example, if you consider $F_2=\langle a,b\rangle$ acting on its Cayley graph (which is an infinite regular tree of valency 4), then the subgroup $H$ consisting of all elements of $F_2$ of even length will correspond to orbits that have "every other vertex" along every path. In this case in your definition of $T'$ elements $e$, $ab$, and $ab^{-1}$ will form a triangle as the geodesics between any two of these elements will only pass through $a$, which is not in the orbit.

  • $\begingroup$ Thank you for answering ! The Cayley graph of $G$ can't be a tree because $G$ is not free. As $T'$ is a subdivision of $T$, it can't have cycles, can it ? $\endgroup$ – Max Apr 13 '18 at 16:36
  • $\begingroup$ Sorry - you are right, of course that my example is not the best here. But I do not see why in the argument $T'$ is a subdivision of $T$. Let me modify my example. Take $F_2$ - a free group of rank 2 and again consider the subgroup of index 2 consisting of all words of even length. Then there will be many copies of the complete graph $K_4$ in $T'$ by the same reason as in my previous example. $\endgroup$ – Dima Savchuk Apr 14 '18 at 17:04
  • $\begingroup$ Mhm sorry I meant that $T$ is a subdivision of $T'$; and it's because each edge in $T'$ corresponds to an edge in $T$ or a path in $T$ $\endgroup$ – Max Apr 14 '18 at 17:42
  • $\begingroup$ I meant that I did not see why $T$ was a subdivision of $T'$. Let me be more specific, and then you may be able to clarify my confusion. Take $F_2$ generated by $a$ and $b$ and subgroup $H$ as described above. Then the orbit of the identity will consist of all elements of $H$. My claim is this: points $e$, $ab$ and $ac$ form a triangle in $T'$. Indeed, according to your definition the only path in $T$ that goes from $e$ to $ab$ does not pass through points in $H$, so we connect $e$ and $ab$ by an edge in $T'$. But the same is true for $e$ and $ac$, and $ab$ and $ac$. So $T'$ is not a tree. $\endgroup$ – Dima Savchuk Apr 15 '18 at 3:18
  • $\begingroup$ Wait, I said "connect them if all paths in $T$ from one to the other don't intersect $G\cdot v$ [Here $H$]"; but here there actually is a path from $ab$ to $ac$ that intersects $H$ : go to $e$, then to $ab$, so you don't connect $ab$ and $ac$: there's no edge there so no triangle $\endgroup$ – Max Apr 15 '18 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.