On commutator length in free groups

Let F be a free group. We present for arbitrary g\in\mathbb{N} a LOGSPACE (and thus polynomial time) algorithm that determines whether a given w\in F is a product of at most g commutators; and more generally, an algorithm that determines, given w\in F , the minimal g such that w may be written as a...

Full description

Saved in:
Bibliographic Details
Published in:Groups, geometry and dynamics geometry and dynamics, 2024-01, Vol.18 (1), p.191-202
Main Authors: Bartholdi, Laurent, Ivanov, Sergei O., Fialkovski, Danil
Format: Article
Language:English
Subjects:
Algorithms
Group theory
Mathematical research
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let F be a free group. We present for arbitrary g\in\mathbb{N} a LOGSPACE (and thus polynomial time) algorithm that determines whether a given w\in F is a product of at most g commutators; and more generally, an algorithm that determines, given w\in F , the minimal g such that w may be written as a product of g commutators (and returns \infty if no such g exists). This algorithm also returns words x_1,y_1,\dots,x_g,y_g such that w=[x_1,y_1]\dots[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.
ISSN:1661-7207
1661-7215
DOI:10.4171/GGD/747