Details

An element in a free group is primitive if there exists a basis for the free group containing the given element. For free groups of rank two, Piggott observed that there is a very fast algorithm (linear on word length) that determines whether or not an element is primitive based on a construction by Osbourne and Zieschang. The algorithm to determine if a cyclic word in the free group of rank 2 is as follows.

By we denote the length of the word . By we denote the absolute value of the exponent sum of . In other words, the absolute value of the number of ’s minus the number of ’s. We define similarly.

1. If both and appear in or if both and appear, then is not primitive. This happens precisely when .

2. If , then is primitive if and only if or , i.e., .

3. Otherwise, is written cyclically around the unit circle starting at the point and moving between letters. If two letters occupy the same location on the circle, i.e., , or if the two letters are not in two contiguous groups, the element is not primitive. If these two conditions do not occur, then the word is primitive.

Inverses of basis elements are denoted by capital letters: , etc.

Snapshot 1: The word is not primitive as both and appear, i.e., . For this word, .

Snapshot 3: The word is not primitive as the groups of letters are not contiguous.

A C implementation of this algorithm can be obtained from Piggott’s website.

References

[1] R. P. Osborne and H. Zieschang, "Primitives in the Free Group on Two Generators," Inventiones Mathematicae, 63(1), 1981 pp. 17–24.

[2] A. Piggott, "Palindromic Primitives and Palindromic Bases in the Free Group of Rank Two," Journal of Algebra, 304(1), 2006 pp. 359–366.