Generating elements of the free group of rank two up to conjugacy

Question

I've tried to google how to generate words in two generators up to conjugacy (this means I only want one representative for each conjugacy class). Sadly, I come up with articles that have, in the introduction, things like "It is well known that the elements of the free group of rank two can be enumerated by the rationals".

I think I understood that there is a bijection between the conjugacy classes of elements of the free group on two generators and the rational numbers, and this bijection has something to do with the continued fraction associated with a given rational number. I couldn't find any reference on the topic though, so if anyone could give me one I would be grateful.

I would also appreciate any other method to compute the conjugacy classes of the free group on two generators. (I need an algorithm for a program I am writing)

Thank you!

Answer 1

Every word is conjugate to a cyclically reduced word, and the cyclically reduced conjugates of a cyclically reduced word are all cyclic permutations.

This comes directly from wikipedia.

From here on, when I say a cyclically reduced word, I mean the smallest cyclic reduced word in the lexicographical order in the set of all its cyclic permutations.

The quote shows:

1. You can find a cyclically reduced representative for a conjugacy class.

2. A conjugacy class is uniquely determined by one cyclically reduced word.

The question becomes how to find a list of cyclically reduced word over two alphabets. A cyclically reduced word is called a necklace. One can search for "necklace algorithms" to get more infomation.

Practically speaking, you might just look at the answer to this question: Good simple algorithm for generating necklaces in Scheme?.

If you just want something easy to implement and doesn't care about the running time:

1. Generate the next word. (The alphabet is just 1,-1,2,-2, so one can represent a word in base 4 and count up)
2. Check if the word is cyclically reduced. If not, go back to 1.
3. Rotate the word, see if this word is lexicographically smallest in all its rotations. If not, go back to 1. If yes, print this word.