Enumerating palindromes and primitives in rank two free groups. (Q645235)

In a free group \(F\) of finite rank \(n\) an element is called primitive if it is a member of a basis of \(F\). In particular if \(F\) is of rank two, then an element \(A\) is primitive if there is another element \(B\) of \(F\) such that \(A,B\) generate \(F\). On the other hand a word \(w(A,B)\) in \(F\) is called a palindrome if it reads the same forwards and backwards. It is known that in a rank two free group, for any fixed set of two generators a primitive element will be conjugate either to a palindrome or to the product of two palindromes. In this paper the authors use (simple) continued fraction expansions to state their main result. Let \(p,q\) relatively prime positive integers. Let \(p/q=[a_0,a_1,\dots,a_k]\) be the expansion of \(p/q\) in a simple continued fraction. Set \(E_{0/1}=A^{-1}\), \(E_{1/0}=B\) and \(E_{1/1}=BA^{-1}\). Suppose \(p/q\) has continued fraction expansion \([a_0,a_1,\dots,a_k]\). Consider the two rationals defined by the continued fractions \([a_0,a_1,\dots,a_{k-1}]\) and \([a_0,a_1,\dots,a_k-1]\). One is smaller than \(p/q\) and the other is larger; call the smaller one \(m/n\) and the larger one \(r/s\) so that \(m/n<p/q<r/s\). The induction step in the scheme is given by {\parindent=5mm \begin{itemize}\item{}Case 1. \(pq\) odd: \(E_{p/q}=E_{r/s}E_{m/n}\). \item{}Case 2. \(pq\) even: \(E_{p/q}=E_{m/n}E_{r/s}\). \end{itemize}} A similar scheme is given for negative rationals. The main result is the following: Theorem (Enumeration of primitives by rationals). Up to conjugacy and taking formal inverses, the primitive elements of a two generator free group can be enumerated by the rationals using continued fraction expansions. The resulting primitive words are cyclically reduced and denoted by \(E_{p/q}\) so that: {\parindent=5mm \begin{itemize}\item[{\(\bullet\)}]For \(pq\) even, \(E_{p/q}\) is a palindrome. It is the unique palindrome in its conjugacy class. \item[{\(\bullet\)}]For \(pq\) odd, \(E_{p/q}\) is a product of palindromes that have already appeared in the scheme; that is, \(E_{p/q}=E_{m/n}E_{r/s}\) and both \(E_{m/n}\) and \(E_{r/s}\) are palindromes. \end{itemize}} There is a detailed exposition of their methods and the paper ends with some enlightening examples.