# Prove elements generate a free group

How does one show that the elements $x^2$, $y^2$, and $xy$ have no nontrivial relations among them in the free group generated by $\{x,y\}$? This would prove that the free group $F_2$ has a subgroup isomorphic to $F_3$.

(I understand the problem, it's analogous to proving the linear independence of three vectors... except in this case the non-commutativity of the basis is the crucial piece, rather than just the multiplicity of the basis elements. I just need a hint to get me in the right direction...)

Source is Artin's "Algebra" 1ed #6.7.2, not homework just learning.

• For what it's worth, there is an elegant proof that $\langle x^2, y^2, xy\rangle$ is $F_3$ using covering spaces (a tool from algebraic topology). But given the context of this question, I understand that you're looking for a purely-algebraic proof. – Ayman Hourieh Jan 12 '14 at 21:51

This proof uses covering spaces, but I'm posting it at the request of orlandpm (the OP).

Consider the $2$-oriented graph, $G$: This space is the wedge sum of two circles. Therefore its fundamental group is the free group on two generators $\langle x, y\rangle$.

This space has the following covering space, $\widetilde G$: Since the map $p_* : \pi_1(\widetilde G) \to \pi_1(G)$ induced by the covering space $p : \widetilde G \to G$ is injective, it follows that the fundamental group of $\widetilde G$ is isomorphic to $\langle x^2, xy, y^2\rangle$.

At the same time, $\widetilde G$ is homotopy equivalent to the wedge sum of three circles. Therefore its fundamental group is the free group on three generators, $F_3$.

We conclude that $$\langle x^2, xy, y^2\rangle \cong F_3.$$

For the theory behind this, check out section $1.3$ of Hatcher's Algebraic Topology book (available freely online). (Images courtesy of the book.)

• Yet another reason that a little topology goes a long way... – Pax Kivimae Jan 14 '14 at 6:02
• Sorry for the stupid question, but why is $\tilde{G} \simeq S^1 \vee S^1 \vee S^1$? I see three circles, but they intersect "too much". – HeinrichD Apr 5 '17 at 20:35
• @HeinrichD Collapse one of the edges to a point. This will give you the wedge sum of three circles. Since an edge is contractible, the original space is homotopy equivalent to the resulting space. See 'Collapsing Subspaces' in chapter 0 of Hatcher's Algebraic Topology. – Ayman Hourieh Apr 6 '17 at 7:51

Although you can do this by bare hands, it is easier to do it after learning a bit of general theory about subgroups of free groups. These three elements generate the subgroup of the free group $F$ on $\{x,y\}$ consisting of words of even length, which clearly has index $2$ in $F$ with transversal $\{1,x\}$. The Schreier generators of the subgroup with respect to this transversal are $x^2,xy,yx^{-1}$, which are known to generate it freely. We can then replace $yx^{-1}$ by $(yx^{-1})(xy)=y^2$ to deduce that the given three elements are free generators.

You can also use the Nielsen theory to transform any set of elements to a set that freely generates the subgroup it generates. In this case, $x^2,xy,y^2$ is not Nielsen reduce, because $l(y^2(xy)^{-1}x^2) = l(yx)=2 \le l(y^2)+l(x^2)-l(xy)$, but again replacing $y^2$ by $y^{-1}x$ results in a Nielsen reduced set.

• if $U=\langle x^2,xy,yx^{-1}\rangle$, ins't that $[F:U]>2$? – janmarqz Jan 7 '14 at 21:13
• I (kind of) second @janmarqz. The words of even length do from a subgroup of index two, and hence can be generated by three elements (by Schreier's formula). However, I cannot see why $V=\langle x^2, y^2, xy\rangle$ generates this subgroup, that is, I am not convinced that $yx\in V$ (the set $\{x^2, y^2, xy, yx\}$ generates the words of even length, but does it do it freely? I don't know...). – user1729 Jan 9 '14 at 10:40
• i found that $xy^{-1}=xyy^{-2}\in U$ because $xy$ and $y^{-2}$ are. So effectively $Ux=Uy$ and from this the set of transversals are like Derek said. Also from $y^2(xy)^{-1}x^2$ which is in $U$ gives $yx\in U$.. let me tell you that I wrote some more details in juanmarqz.wordpress.com/2014/01/08/… – janmarqz Jan 9 '14 at 16:10
• Ah, right, yeah, I am convinced! – user1729 Jan 13 '14 at 10:22

Here is a “bare-hands” approach.

Let $X$ be your group generated by $x^2,y^2$ and $xy$, $A$ be the free group on three generators $a_1,a_2,a_3$. There is a unique group homomorphism $f: A \to X$, sending $a_1$ to $x^2$, $a_2$ to $y^2$, $a_3$ to $xy$. That homomorphism is obviously surjective. So all you need to show is that $f$ is injective, i.e. $f(a)\neq e$ whenever $a\neq e$.

In both $X$ and $A$, every element has a unique reduced writing (i.e. expression not containing terms of the form $tt^{-1}$ or $t^{-1}t$). This allows us to identify each element with a unique word, called its “normal form”, and saying that an element ends with a certain word.

Let $a\in A,a\neq e$. Then $a$ must end with something, there are six cases, and I claim that

(1) If $a$ ends with $a_1$ (in $A$), then $f(a)$ ends with one of $x^2,yx,y^{-1}x,y^2$ (in $X$).

(2) If $a$ ends with $a_2$ (in $A$), then $f(a)$ ends with $y^2$ (in $X$).

(3) If $a$ ends with $a_3$ (in $A$), then $f(a)$ ends with one of $xy,x^{-1}y$ (in $X$).

(4) If $a$ ends with $a_1^{-1}$ (in $A$), then $f(a)$ ends with $(x^{-1})^2$ (in $X$).

(5) If $a$ ends with $a_2^{-1}$ (in $A$), then $f(a)$ ends with one of $xy^{-1},x^{-1}y^{-1},(y^{-1})^2$ (in $X$).

(6) If $a$ ends with $a_3^{-1}$ (in $A$), then $f(a)$ ends with one of $yx^{-1},y^{-1}x^{-1}$ (in $X$).

Once this property is stated, its verification by induction on the length of $a$ and by case disjunction is purely mechanical. I can supply further details if you need them.

So we have by this disjunction in six cases, that $f(a)\neq e$ : $f$ is injective, which concludes the proof.

• didn't you like my simplification $w=a$, $a=a_1$, $b=a_2$, and $c=a_3$, devised to handle less variable-names? – janmarqz Jan 10 '14 at 19:04
• @janmarqz I like having the elements of $A$ denoted by $a$ (not $b$ or $c$) with an index. It is also nice and natural to use $a$ (not $w$) for a word whose characters are $a_1,a_2,\ldots,a_n$. – Ewan Delanoy Jan 10 '14 at 19:20
• mine is less letters same ideas, case n=3. – janmarqz Jan 10 '14 at 20:59

Instead of the choice in the OP, we could select differently in order to get wisdom of the problem with respect to "orderings of words".

Among the 12 possibilities of length two reduced words in $F_2$ we can prove that the the first three in the ordering: $$x^2<xy<xy^{-1}<x^{-2}<x^{-1}y<x^{-1}y^{-1}<yx<yx^{-1}<y^2<y^{-1}x<y^{-1}x^{-1}<y^{-2}$$ generate the other nine.

Let $S=\{ x^2\ ,\ xy\ ,\ xy^{-1}\}$ be ours alternative choice, then we get $S^{-1}=\{ x^{-2}\ ,\ y^{-1}x^{-1}\ ,\ yx^{-1}\}$.

Now, there are six remaining cases:

• $x^{-1}y=x^{-2}(yx^{-1})^{-1}y^2$ then $y^{-1}x=y^{-2}(yx^{-1})x^2$

• $x^{-1}y^{-1}=x^{-2}(xy)y^{-2}$ then $yx=y^2(xy)^{-1}x^2$

• $y^2=(yx^{-1})(xy)$ then $y^{-2}=(xy)^{-1}(yx^{-1})^{-1}$,

that is, the product of the first three reduced words of length two and their inverses generate all the twelve reduced words of length two.

So, any other word of even length in $F_2$ can be generated by $S\cup S^{-1}$.

Now, is a matter of following the Schreier's algorithm to warrant that the subgroup $U=\langle\{ x^2\ ,\ xy\ ,\ xy^{-1}\}\rangle$ is indeed free.

For, we must be sure that $F=U\cup Ux$ is a partition. This is the case because if one admits that $U$ carries all the even length words, then $Ux$ carries the odd length words. Also the presence of $xy^{-1}\in U$ implies $Ux=Uy$.

So a set of transversals is $\Sigma=\{1,x\}$, which they are minimal in their coset and which together with $S$ they are going to give us the set $$\Sigma S=\{\ x^2\ ,\ xy\ ,\ xy^{-1}\ ,\ x^3\ ,\ x^2y\ ,\ x^2y^{-1}\ \},$$ hence one receives $\overline{\Sigma S}=\{1,x\}$.

According to Schreier's method the set $\{gs\overline{gs}^{-1}\ |\ g\in\Sigma,s\in S\}$ carries the free generator for $U$. In our case one computes: \begin{eqnarray*} x^2\overline{x^2}^{-1}&=&x^2,\\ xy\overline{xy}^{-1}&=&xy,\\ xy^{-1}\overline{xy^{-1}}^{-1}&=&xy^{-1},\\ x^3\overline{x^3}^{-1}&=&x^2,\\ x^2y\overline{x^2y}^{-1}&=&x^2yx^{-1},\\ x^2y^{-1}\overline{x^2y^{-1}}^{-1}&=&x^2y^{-1}x^{-1} \end{eqnarray*} Which they all are in $U$. Hence $\{\ x^2\ ,\ xy\ ,\ xy^{-1}\ \}$ is a set of free generator for $U$.

• I would like to stress that $U$ is normal 'cuz $[F_2:U]=2$ – janmarqz Jan 14 '14 at 6:07
• note that in applying the Schreier's procedure to the original choice $x^2,y^2$ and $xy$ we get again the first three length-two-words as reported in [ wp.me/pAes4-1mC ] – janmarqz Jan 14 '14 at 23:54
• for a little review of Schreier's technique, follow to juanmarqz.files.wordpress.com/2014/01/schreierbrief.pdf – janmarqz Jan 15 '14 at 3:29

You just need to show that some word in two of the elements is not equal to the third (since every subgroup of a free group is free). Clearly, there is no word in $x^2, y^2$ which equals $x y,$ since any such word has an even power of $x, y.$ So, without loss of generality, you want to show that no word in $x^2, xy$ equals $y^2.$ Just write down a general such a word, and you will see that if there is any $x^2$ term, there is no way to cancel both $x$s.

• @Karene Indeed. My comment was responding to the original version of this answer. I didn't know it was edited and undeleted. | New comment: how do we know if it's sufficient for none of them to be equal to a word in the other two? For example, $\langle a,b,c|(abc)^3=1\rangle$ is not free but I think that condition holds for $a,b,c$. – anon Jan 6 '14 at 2:10
• @anon indeed, my apologies (I was actually trying to write a different answer, but MSE seems to be prefer undeleting). – Igor Rivin Jan 6 '14 at 2:11
• How does one write down a "general word"? – orlandpm Jan 6 '14 at 5:19
• @IgorRivin It is not enough to show this in general. The elements $x,y^2$ and $y^3$ do not freely generate a subgroup (they generate the whole of $\langle x,y \rangle$), but none of those elements can be expressed as a word in the other two. – Derek Holt Jan 6 '14 at 8:54
• @DerekHolt arghh. I was afraid of that... One lives and learns. – Igor Rivin Jan 6 '14 at 14:12