Solving the Conjugacy Decision Problem via Machine Learning

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.

KEYWORDS:

• Machine learning
• group theory
• non-commutative cryptography
• polycyclic group
• conjugacy

2010 AMS SUBJECT CLASSIFICATION:

• Primary 20F10
• Secondary 68T05

Acknowledgments

We would like to thank Benjamin Fine and Vladimir Shpilrain for their helpful suggestions throughout the development of this work. We would also like to thank the reviewers for their constructive questions, comments, and corrections. This paper is based in part on the Ph.D. dissertation of Jonathan Gryak at the City University of New York, 2017, written under the supervision of Gryak’s advisor Delaram Kahrobaei.

Additional information

Funding

Delaram Kahrobaei is partially supported by a PSC-CUNY grant from the CUNY Research Foundation, the City Tech Foundation, and ONR (Office of Naval Research) grants N000141210758 and N00014-15-1-2164.