Learning the symmetric group: large from small

Max Petschack, Alexandr Garbali and Jan de Gier · 2025

Read Learning the symmetric group: large from small by Max Petschack, Alexandr Garbali and Jan de Gier (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12717.txt.

Introduction

Max Petschack, Alexandr Garbali, and Jan de Gier teach a transformer the symmetric group on small cases, then watch it nail far larger ones. Their paper from twenty twenty-five trains the model to predict permutations from words built of transpositions. Noise-free math data is plentiful but pricey to generate at scale. Learning small and generalizing large sidesteps that cost.

Trained on the ten-element group, the model scores near perfect on the twenty-five-element group. With adjacent transpositions only, it still jumps from ten to sixteen elements cleanly. Identity augmentation handles shifting word lengths, and windowed training keeps costs down. The team compares variants and flags where the trick may break. Pure math gains a scaling recipe for machine exploration.

Catalog record

CREATORMax Petschack, Alexandr Garbali and Jan de Gier
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12717

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning the symmetric group: large from small Max Petschack, Alexandr Garbali and Jan de Gier Abstract Machine learning explorations can make significant inroads into solving difficult problems in pure mathematics. One advantage of this approach is that mathematical datasets do not suffer from noise, but a challenge is the amount of data required to train these models and that this data can be computationally expensive to generate. Key challenges further comprise difficulty in a posteriori interpretation of statistical models and the implementation of deep and abstract mathematical problems. We propose a method for scalable tasks, by which models trained on simpler versions of a task can then generalize to the full task. Specifically, we demonstrate that a transformer neural-network trained on predicting permutations from words formed by general transpositions in the symmetric group S 10 S_{10} can generalize to the symmetric group S 25 S_{25} with near 100% accuracy. We also show that S 10 S_{10} generalizes to S 16 S_{16} with similar performance if we only use adjacent transpositions. We employ identity augmentation as a key tool to manage variable word lengths, and partitioned windows for training on adjacent transpositions. Finally we compare variations of the method used and discuss potential challenges with extending the method to other tasks. 1 Introduction Transformer-based AI for mathematics is a fast-developing field. The effectiveness of transformers have been tested on variety of mathematical problems, including arithmetic tasks NogueiraJL2021 , linear algebra Charton2021 , knot theory GukovHRS:2020 , and pattern recognitions ChartonEWW . Inspired by the works NandaCLSS2023 ; ChughtaiCN2021 our goal is to further investigate whether transformers can efficiently learn group theory, and whether features learned from relatively small training sets are in some sense universal, so that large and more complicated groups can be studied by scaling up. Motivated by machine learning experiments on the challenging unknot problem GukovHRS:2020 , we focus on the simpler problem in the context of the symmetric group S_{n} with the goal of training a transformer to take as input a word from S_{n} expressed in terms of transpositions, and return a prediction for the corresponding permutation of (1,\ldots,n) without hardcoding the action of transpositions. Generalizations and future work may provide insights in the word problem for finitely generated groups (which is of course solved for the symmetric group, see e.g. Garsia2002 ) and applications to NP-hard computational problems related to exchanges of two consecutive sequences of genes in a genome in comparative genomics BafnaP1998 ; BulteauFR . Our aim here thus is to investigate whether S_{n} can be learned by training on smaller structures such as subgroups H<S_{n} with H\simeq S_{k} and k\ll n . In this experiment specifically, we develop a method for training a transformer on S_{10} and then have it be capable of predicting permutations from words in the higher order groups S_{16} and S_{25} . 1.1 Related work on symmetric group The concept of grokking was introduced in Power2022 where the authors considered simple algorithmic datasets and showed that validation accuracy increases towards perfect generalization long after the training accuracy becomes close to perfect. Despite overfitting early in the training process, continued optimization eventually leads to a transition where the model generalizes. This suggests that the network gradually shifts from memorization to learning the underlying algorithm. One example from Power2022 is grokking of group multiplication in the permutation group S_{5} . For a given pair of permutations a and b the model needs to compute a permutation c such that a\circ b=c . Grokking and interpretability of the group multiplication in small permutation groups has been studied in a series of subsequent works ChughtaiCN2021 ; StanderYFB2023 ; Wu2024 (see also NandaCLSS2023 ). In the present work we also consider a symmetric group problem but in contrast with previous works we ask whether a model is able to generalize from training on S_{k} data to testing on S_{n} data with k\ll n . Although we have not observed grokking, test accuracy is nearly 100%. At the time of writing it is an open question whether our models have discovered a general algorithm. Our result is reminiscent of out of distribution (OOD) learning. In mathematical problems OOD learning has been studied in, for example, Charton2022 . We test OOD learning in the context of the symmetric group, using a scalable presentation with general transpositions as group generators, as well as a less scalable, more local approach using only elementary transpositions. One motivation for this study is to identify an effective machine learning approach to improve on the unknot problem GukovHRS:2020 . An important part of earlier works on grokking in symmetric group is analysis of models using mechanistic interpretability. This can be done using different circuit level approaches Olah2020 ; Elhage2021 ; Olsson2022 ; Quirke2024 ; Zhang2023 ; Zhong2023 ; Gross2024 . Examining activations of individual neurons and intervening in various parts of the network can help us to discover circuits that implement the algorithm. We aim to perform a similar analysis of our models in a future work. The code used for this project is available on GitHub at Petschack_github . 2 Permutations and the symmetric group Permutation A permutation is a rearrangement of an ordered set. Here we will consider permutations \sigma of the set S=\{1,\ldots,n\} , and use one-line notation (\sigma(1),\ldots,\sigma(n)) for the permutation \sigma:S\to S in which each element i is replaced by the corresponding \sigma(i) . We denote by \Pi_{n} the set of all permutations of a set with n elements. Symmetric group The set \Pi_{n} can be endowed with a multiplication to form the symmetric group S_{n} , where the group operation for two permutations \sigma and \tau in the group S_{n} is the product \pi=\sigma\tau defined by, \pi(i)=\sigma(\tau(i)) (1) For example, for \sigma=(2,1,3) and \tau=(3,2,1) we find \pi=\sigma\tau=(3,1,2) and \pi^{\prime}=\tau\sigma=(2,3,1) . Transposition A transposition s_{i,j} is a permutation in which elements i and j are interchanged when multiplied on the right, (\ldots,\sigma(i),\ldots,\sigma(j),\ldots)\cdot s_{i,j}=(\ldots,\sigma(j),\ldots,\sigma(i),\ldots). (2) Adjacent transposition The transposition s_{i}:=s_{i,i+1} that exchanges adjacent elements in a permutation is called an adjacent transposition. Every group element w\in S_{n} can be written as a word in terms of products of transpositions, w=s_{i_{1},j_{1}}s_{i_{2},j_{2}}\cdots s_{i_{\ell},j_{\ell}}, (3) where \ell is the length of the word. A word w acts on a permutation by acting from the right as in ( 2 ). This expression is not unique, different factorisations in terms of transposition may represent the same group element as a result of the relations \displaystyle s_{i,j} \displaystyle=s_{i}s_{i+1}\cdots s_{j-2}s_{j-1}s_{j-2}\cdots s_{i}, \displaystyle s_{i}s_{i+1}s_{i} \displaystyle=s_{i+1}s_{i}s_{i+1}, (4) \displaystyle s_{i}^{2} \displaystyle=1. A word is called reduced if it cannot be written using a smaller number of transpositions. Adjacent transpositions generate the full symmetric group, and the Coxeter presentation of S_{n} in terms of adjacent transpositions is given by S_{n}=\left\langle s_{1},\ldots,s_{n-1}\,|\,s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}\right.,\\ \left.s_{i}s_{j}=s_{j}s_{i}{\text{ for }}|i-j|\geq 2,\,s_{i}^{2}=1\right\rangle. (5) 3 What are we learning? The experiment reported in this note investigates whether a transformer can learn the symmetric group S_{n} by training only on subgroups isomorphic to S_{m} with m<n . That is, given a word w\in S_{n} can the corresponding permutation (\sigma(1),\ldots,\sigma(n)):=(1,\ldots,n)\cdot w be correctly predicted by a transformer without explicitly hardcoding the group relations ( 4 ). We take two approaches, one in which input words w are

Read the complete text