Fast Algorithm of Commutator Length Computing in Free Group

Overview

In modern algebra there exist a lot of abstract notions and problems but very few computational algorithms. My work is devoted to the notion of free group and a problem of commutator length computing in such group. I present a new algorithm, allowing to compute this abstract algorithmic property. Let G be a group and [G,G] be its commutator subgroup. It is well-known that every element from commutator subgroup can be represented as a product of commutators. The minimal number of commutators needed for representing element g from [G,G] is called a commutator length of this element and is denoted as cl(g). It is very important to be able to compute commutator length algorithmically. It is known that every group can be represented as a quotient group of free group. So, the commutator length in free groups is of particular interest, in comparison with other groups. I developed and implemented as a computer program two algorithms. The first is the fast algorithm of commutator length computing in free group. My algorithm is based on Bardakov's algorithm. However, mine is faster, and in addition to commutator length for an element it gives its representation as a commutators' product. The second algorithm is a simple algorithm that helps us to define whether some free group element is a commutator or not. This algorithm is much faster than the algorithm based on Wicks’ theorem.

Competition history

• ISEF 2015 Category not listed · Entry MATH019I

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.