Recognition of Whitehead-Minimal Elements in Free Groups of Large Ranks - Artificial Intelligence and Symbolic Computation - page 211

Recognition of Whitehead-Minimal Elements
in Free Groups of Large Ranks

Alexei D. Miasnikov

The Graduate Center of CUNY
Computer Science
365 5th ave, New York, USA
[e-mail]

Abstract. In this paper we introduce a pattern classification system to
recognize words of minimal length in their automorphic orbits in free
groups. This system is based on Support Vector Machines and does not
use any particular results from group theory. The main advantage of the
system is its stable performance in recognizing minimal elements in free
groups with large ranks.

1 Introduction

This paper is a continuation of the work started in [5, 7]. In the previous pa-
pers we showed that pattern recognition techniques can be successfully used
in abstract algebra and group theory in particular. The approach gives one an
exploratory methods which could be helpful in revealing hidden mathematical
structures and formulating rigorous mathematical hypotheses. Our philosophy
here is that if irregular or non-random behavior has been observed during an
experiment then there must be a pure mathematical reason behind this phe-
nomenon, which can be uncovered by a proper statistical analysis.
In [7] we introduced a pattern recognition system that recognizes minimal
(sometimes also called Whitehead minimal ) words, i.e., words of minimal length
in their automorphic orbits, in free groups. The corresponding probabilistic clas-
sification algorithm, a classifier , based on quadratic regression is very fast (linear
time algorithm) and recognizes minimal words correctly with the high accuracy
rate of more then 99%. However, the number of model parameters grows as
a polynomial function of degree 4 on the rank of the free group. This limits
applications of this system to free groups of small ranks (see Section 3.3).
In this paper we describe a probabilistic classification system to recognize
Whitehead-minimal elements which is based on so-called Support Vector Ma-
chines [9, 10]. Experimental results described in the last section show that the
system performs very well on different types of test data, including data gener-
ated in groups of large ranks.
The paper is structured as follows. In the next section we give a brief intro-
duction to the Whitehead Minimization problem and discuss the limitations of
the known deterministic procedure. In Section 3 we describe major components