4
$\begingroup$

A primitive element of a free group is an element of some basis of the free group. I have seen some recent papers on algorithmic problems concerning primitive elements of free groups, for example, the papers on determining whether a subgroup of a free group contains a primitive element and determining whether a given element is primitive. However, I'm a little confused about the definition: it seems to me that every element of the free group on a finite set of generators is primitive.

Suppose $\{x_1, \dotsc, x_n\}$ is the set of generators for a free group on $n$ generators. Let $u$ be a word of length $m$ in the free group, and suppose $u = u_1 \dotsb u_m$, where each $u_i$ is one of the generators. I claim that $u$ is primitive because $u (u_2 \dotsb u_m)^{-1} = u_1$, hence $\{(u_2 \dotsb u_m)^{-1}, x_2, \dotsc, x_n\}$ is a basis of the free group, assuming without loss of generality that $u_1 = x_1$.

Where is the flaw in my argument?

$\endgroup$
  • 1
    $\begingroup$ What about $(2,1)$ in $\mathbb Z\times\mathbb Z$? $\endgroup$ – Gregory Grant May 5 '15 at 18:42
  • 3
    $\begingroup$ @GregoryGrant your group is not free. But anyway, what about $2\in\mathbb Z$? $\endgroup$ – Hagen von Eitzen May 5 '15 at 18:43
  • 1
    $\begingroup$ @GregoryGrant It is free-abelian, but not free. There is no homomorphism $\mathbb Z\times \mathbb Z\to S_3$ that maps $(1,0)\mapsto (1\,2)$ and $(0,1)\mapsto (1\,2\,3)$. $\endgroup$ – Hagen von Eitzen May 5 '15 at 18:45
  • 1
    $\begingroup$ Inverses tend to exist in groups. The problem with the argument is that it concludes e.g. that $-m+1$ is a basis of $\mathbb Z$. $\endgroup$ – Thomas Poguntke May 5 '15 at 18:47
  • 1
    $\begingroup$ You may have a typo somewhere: $\{(u_2\cdots u_m)^{-1},x_2,\ldots,x_n\}$ isn't a basis for the free group; $u$ itself isn't in it! (Consider $u=ab$ in the free group on $a$ and $b$; then the basis you claim is $\{b^{-1},b\}$...) $\endgroup$ – Steven Stadnicki May 5 '15 at 18:50
8
$\begingroup$

Your argument would show that every element of $\mathbb{Z}$ is primitive. In fact the primitive elements are $1$ and $-1$. Do you see what goes wrong with your argument in this case?

The primitive elements of a free group $F_n$ have the special property that under a homomorphism $F_n \to G$ to some other group $G$, they can be sent to arbitrary elements of $G$. But most elements of a free group don't have this property. For example, in the free group $F_2$ on two generators $a, b$,

  • $a^2$ doesn't have this property because it must be sent to a square, and for example $1 \in \mathbb{Z}_2$ is not a square.
  • $[a, b]$ doesn't have this property because it must be sent to a commutator, and for example $1 \in \mathbb{Z}_2$ is also not a commutator.

And so forth.

$\endgroup$
  • $\begingroup$ Is it not true that the set $\{x_1, \dotsc, x_n\} \cup \{w\}$ generates the entire free group, for any free group element $w$? $\endgroup$ – argentpepper May 11 '15 at 20:41
  • $\begingroup$ @argentpepper: yes, but it's not a basis. $\endgroup$ – Qiaochu Yuan May 11 '15 at 20:50
5
$\begingroup$

$\newcommand{\GL}{\mathrm{GL}}$Let $F$ be free on $x, y$. Then $x^{2}$ is not primitive. If $x^{2}, z$ were a basis of $F$, then their images in the abelianization $F/F'$ should be a basis of $F/F'$. But with respect to the basis made of the images of $x, y$, we have that $x^{2}, z$ have matrix $$ \begin{bmatrix} 2 & a\\ 0 & b\\ \end{bmatrix} $$ which has determinant $2 b \ne \pm 1$, and thus is not in $\GL(2, \mathbb{Z})$.. So in $F/F'$ you cannot express the images of $x, y$ in terms of the images of $x^{2}, z$.

$\endgroup$
  • $\begingroup$ Oh, dear hollie mollie! Exactly the same thing I posted as a comment some moments ago...hehe. Nice! Your explanation is fine, yet I'm not sure about mine...? $\endgroup$ – Timbuc May 5 '15 at 18:59
  • $\begingroup$ I'm a bit unfamiliar with this area, could you clarify your answer a bit? What is $F'$? What are $a$ and $b$? What does this matrix have to do with the elements $x^2$ and $z$? $\endgroup$ – argentpepper May 5 '15 at 19:03
  • 1
    $\begingroup$ @argentpepper $F'$ is the derived group; in this case you just need to see 'the abelianization', which is essentially the group that you get by taking $F$ and 'modding out' by element order (i.e., $xy=yx$; technically, $F'$ is the group generated by $xyx^{-1}y^{-1}$, so $F/F'$ is the group you obtain by setting all members of $F'$ equal to the identity). This argument is saying that if there were some two-element basis $x^2,z$ of $F$ then that basis would also be a basis of the abelianization of $F$. $\endgroup$ – Steven Stadnicki May 5 '15 at 19:15
  • 2
    $\begingroup$ But bases of the free abelian group on two elements (i.e., $\mathbb{Z}^2$) are related by a base change - i.e., an integer matrix of determinant 1 (this is classic linear algebra). The matrix here is the shape that such a base change would have to have, and the comment about the determinant being $2b$ is why such a base change can't exist. $\endgroup$ – Steven Stadnicki May 5 '15 at 19:19
  • $\begingroup$ Sorry for not intervening sooner, I was otherwise busy. And many thanks to @StevenStadnicki for filling in the dots in my too concise answer. Another way of looking at it is to consider the quotient $F/F^{2}F'$, which is the Klein four-group, the non-cyclic group of order $4$. Clearly the image of $x^{2}$ is trivial here, so that the image of $y$ alone is unable to generate it. $\endgroup$ – Andreas Caranti May 6 '15 at 7:05
3
$\begingroup$

The problem with your argument as written is that you assume that $(u_2\cdots u_m)^{-1}\in\{x_2, x_3, \ldots, x_n\}$, but this isn't necessarily the case; it could be that $x_1$ is also among the $u_i$ and not just in the first place. For instance, consider the subgroup of the free group on two elements $a$ and $b$ generated by $\{aba, b\}$; it should be intuitively clear (and can be easily proven) that $a$ itself isn't a member of this subgroup.

Your argument does work in the case where the first 'basis letter' of your hypothetically-primitive element isn't repeated in the rest of the word; for instance, it's obvious that $\langle ab,b\rangle = \langle a,b\rangle$, and similarly $\langle ab^n,b\rangle = \langle a,b\rangle$ for all $n$.

$\endgroup$
  • 1
    $\begingroup$ The subgroup generated by $\{aa, b\}$ works as a counterexample as well; this is the counterexample given in the answer by @AndreasCaranti below and in the comments on the original question. $\endgroup$ – argentpepper May 5 '15 at 19:07

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.