On commutator length in free groups

Abstract

Let F be a free group. We present for arbitrary g∈N a LOGSPACE (and thus polynomial time) algorithm that determines whether a given w∈F is a product of at most g commutators; and more generally, an algorithm that determines, given w∈F, the minimal g such that w may be written as a product of g commutators (and returns ∞ if no such g exists). This algorithm also returns words x 1 ,y 1 ,…,x g ,y g such that w=[x 1 ,y 1]…[x g ,y g]. These algorithms are also efficient in practice. Using them, we produce the first example of a word in the free group whose commutator length decreases under taking a square. This disproves in a very strong sense a conjecture by Bardakov.