Certified Conjugacy Learning in Small-Cancellation Groups

The conjugacy decision problem is fundamental in combinatorial group theory and has applications in algebraic cryptography. Previous machine-learning studies demonstrated that conjugacy can be classified in selected non-free groups, but a statistical prediction is not an algebraic proof. This paper introduces a reproducible certificate-guided learning pipeline for random two-generator one-relator presentations satisfying the metric condition $C'(1/6)$. Positive instances are constructed with an explicit conjugator and accepted only after Dehn reduction verifies $g^{-1}ug =_G v$. Negative instances are retained only when the images of $u$ and $v$ in the abelianization are unequal, which provides an exact obstruction to conjugacy. A symmetry-preserving feature map combines pairwise word-length statistics, exponent-sum information, and aggregated labelled-walk features of orders one to three. Logistic regression and a random forest are evaluated using a presentation-disjoint split. The principal experiment contains $4{,}200$ certified pairs from six presentations: $2{,}800$ pairs from four presentations are used for training, while $1{,}400$ pairs from two previously unseen presentations are used for testing. Logistic regression obtains an accuracy of $0.9964$ and an F1 score of $0.9964$, while the random forest obtains $1.0000$ for accuracy, F1 score, and ROC–AUC. An independent experiment using a second random seed reproduces this performance pattern. These high scores characterize the certified pilot distribution and do not constitute a solution to unrestricted conjugacy. The principal contribution is a transparent computational framework that separates statistical prediction from algebraic proof, prevents the use of unverifiable class labels, and identifies the construction of difficult certified negative instances as the central problem for subsequent research.