Solving the Conjugacy Decision Problem via Machine Learning. Issue 1 (2nd March 2020)

• Record Type: Journal Article
• Authors: Gryak, Jonathan; Haralick, Robert M.; Kahrobaei, Delaram
• Is Part Of: Experimental mathematics. Volume 29:Issue 1(2020)
• Page Start: 66
• Page End: 78
• Publication Date: 2020-03-02
• Subjects: Machine learning -- group theory -- non-commutative cryptography -- polycyclic group -- conjugacy; Primary 20F10 -- Secondary 68T05; Mathematics -- Periodicals; Mathematics -- Research -- Periodicals; 510.724
• DOI: 10.1080/10586458.2018.1434704
• Languages: English
• ISSNs: 1058-6458

Abstract

ABSTRACT: Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this paper, we seek to extend these techniques to finitely presented non-free groups, with a particular emphasis on polycyclic and metabelian groups that are of interest to non-commutative cryptography. As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N -tuple neural network models are evaluated for several non-free groups. The very high accuracy of these classifiers suggests an underlying mathematical relationship with respect to conjugacy in the tested groups.