Learning the Word Problem: Geodesic Lengths and Cryptographic Applications. Elisabeth Fink Middlesex University, Department of Computer Science, The Burroughs, Hendon, London NW4 4BT, UK [email protected]
July 30, 2026
arXiv:2607.26241v1 [cs.CR] 28 Jul 2026
Abstract The Word Problem has been a subject of intensive mathematical study for over a century, initially driving advances in combinatorial group theory and more recently emerging as a foundational hardness assumption in post-quantum cryptography (PQC). While generally undecidable, several families of infinite non-abelian groups exhibit solvable or algorithmically fast word problems, making them attractive platforms for cryptographic design. This paper introduces WPNet, a novel Graph Neural Network architecture capable of solving the Word Problem heuristically, which is demonstrated on the Baumslag-Solitar group BS(1, 2) and on an Artin group. By mapping unreduced words to dynamic graph structures, the model learns to cluster algebraically equivalent elements in a continuous embedding space, effectively identifying the geodesic representative of a word without executing discrete reduction steps. As an application, a model variant is developed that can predict the geodesic length of an unreduced word in both groups. To demonstrate the cryptographic severity of this structural leakage, WPNet is successfully deployed against the Wagner-Magyarik public-key cryptosystem.
1
Introduction
The word problem, introduced by Dehn in 1911, is the foundational decision problem in combinatorial group theory: given a finite presentation of a group and a word in its generators, determine whether the word represents the identity element [30]. It is undecidable in general [71, 15]. A natural refinement is the geodesic (minimal reduced-word) length problem – computing the shortest word representing a given element with respect to a fixed generating set – which underlies growth series and the metric geometry of Cayley graphs. While automatic groups admit regular languages of geodesics and rational geodesic growth series, no efficient exact algorithm for geodesic length is known for many groups of interest, including braid groups, other Artin groups, and Baumslag–Solitar groups such as BS(1,2): computing the geodesic length in a subgroup is formally hard [70], and the set of geodesics in the infinite braid group is co-NP-complete. This intractability is not merely of theoretical interest: it is the mathematical basis for post-quantum group-based cryptography. With Shor’s algorithm threatening standard public-key systems based on factorization and discrete logarithms [82], non-abelian protocols have emerged as a quantum-resistant alternative. The Wagner-Magyarik cryptosystem, one of the earliest such schemes, encodes messages by masking bits within tangled identity words, relying directly on the word problem’s hardness [87]. Despite being broken by chosen-ciphertext and reaction attacks [62, 44], its direct-decryption vulnerability makes it a natural benchmark for evaluating neural word-problem solvers. The Anshel-Anshel-Goldfeld (AAG) and Ko-Lee protocols instead rely on the Conjugacy Search Problem in braid groups [6, 60], requiring legitimate parties to solve the word problem to verify key alignment [68]. Crucially, protocol security depends on choosing obscuring word lengths that resist length-based attacks: efficient approximate length oracles have been shown to untangle conjugated words of several hundred generators in braid groups [40, 69], forcing modern designs toward word lengths in the thousands, where the exponential (or worse) Dehn function of the underlying group is relied upon to make direct search intractable [42, 79]. Any advance in efficiently solving the word 1
or geodesic length problem – algorithmic or learned – therefore directly bears on which groups remain viable post-quantum cryptographic platforms, and at what word length would be required. This tension between algorithmic tractability and geometric complexity is exemplified by two benchmark families: The Baumslag-Solitar group BS(1, 2) and Artin groups with mi,j = 2, 3. Baumslag-Solitar groups BS(m, n) = ⟨a, t | t−1 am t = an ⟩ were introduced as the first examples of two-generator, one-relator nonHopfian groups [13]. For the solvable case BS(1, q), the word problem lies in LOGSPACE and uniform T C 0 [89, 38], yet the Dehn function is strictly exponential for |q| ≥ 2 [42] – a dichotomy between cheap algorithmic decidability and exponential geometric area that makes BS(1, 2) an especially demanding benchmark for a model that must recover geodesic representatives rather than merely decide triviality. Elements in BS(1, 2) have a normal form and the length of a geodesic representing such an element can be computed in linear time ([34]). Artin groups present a complementary challenge: the word problem is solved for several subclasses via tailored geometric and rewriting techniques – spherical type via normal forms [9, 41, 18, 32, 2], rightangled and FC type via geometric methods [19, 84, 49, 5], large and extra-large type via small cancellation and shortlex automaticity [7, 77, 54], and affine, locally reducible, and 3-free types via related rewriting arguments [33, 67, 31], but no solution is known in general, and groups mixing braid and commutator relations of the kind studied here fall outside all of these solved subclasses. The two types of groups were chosen to have BS(1, 2) as one representative that is computationally very well understood and with the Artin group A(Γ) another group, where the word problem is not known to be decidable. Machine learning has recently been applied to problems of this kind. Models have been trained to predict permutations and infer relations directly from data in symmetric groups [78], and architectures such as AlgebraNets embed associative-algebra structure natively into network parameters [52]. Closest to the present setting, decision trees, random forests, and neural classifiers have solved the conjugacy decision problem in polycyclic and metabelian groups, including BS(1,2) itself [47]. A separate line of work learns distance directly on a group’s Cayley graph: a deep network trained to estimate cost-to-go on the Rubik’s cube Cayley graph via approximate value iteration guides A* search to near-optimal solutions [3], an approach since reformulated as graph neural network node classification [11] and scaled to arbitrary finite permutation groups via diffusion-distance estimation [24, 23]. Equivariant Fourier-basis heuristics offer a further design axis [74] (see [58] for a broader survey). Reinforcement learning has separately been used to untangle braids via Reidemeister moves [65]. However, all of this prior work operates at word lengths far below the thousands of generators required for cryptographic relevance: graph neural networks trained on shorter words face a fundamental scaling barrier, as models operating on word topologies exceeding their receptive field fail to propagate algebraic information globally, while increasing depth to accommodate L ≥ 1000 induces severe over-smoothing [63, 72, 4]. No prior work has targeted geodesic length prediction for unreduced words in Artin groups with mixed braid and commutator relations at cryptographically relevant lengths, nor evaluated learned heuristics against the specific hardness landscape of BS(1, 2) and braid-type presentations. This paper investigates the applicability of graph neural networks to the word problem at scale. In particular, variations of WPNet are developed to evaluate triplets of words in Artin and BS groups: each word – reduced or unreduced – is embedded in the 128-dimensional unit sphere S 128 , and given a triplet (w, p, n) where w is an unreduced word, p a geodesic representative of w, and n a word derived from p by small perturbations, WPNet is deemed to have learned a geodesic representation of w if the embeddings of w and p lie close together while those of w and n are well separated. The present results show successful separation of true geodesic representatives from decoys with over 90% accuracy for word lengths up to 5000 in both Artin and BS groups. Further, models to predict geodesic length in BS(1, 2) and this Artin group are developed, achieving 99% accuracy up to word length 200. Finally, this approach is applied to the Wagner-Magyarik system, recovering the correctly passed message with near-100% accuracy even when hidden in words up to length 1000.
2
Methods
2.1
Groups and preliminaries
Let G be a finitely presented group defined by G = ⟨S | R⟩, where S is a finite set of generators and R is a set of defining relations. Elements of G are represented by words formed from the generators and their formal inverses, S ∪ S −1 . The relations are words in S ∪ S −1 and determine cancellations, in other words, 2
which words equate to the identity. The length of a word w is the number of letters required to represent the element. In this work, the length of a word will frequently refer to the length before reduction using group relations. The word problem asks whether a given word w represents the identity element in G. The complexity of reducing a trivial word to the identity is captured by the Dehn function, δ(n). It measures the maximum number of times the relations in R must be applied to mathematically reduce any trivial word of length at most n back to the empty word. A group G is metabelian if its commutator subgroup H = ⟨g −1 h−1 gh|g, h ∈ G⟩ is abelian. An HNN extension ([50]) constructs a larger group from a base group H by introducing a stable letter t that enforces an isomorphism between two subgroups of H. A group G is defined as Hopfian ([56]) if every surjective endomorphism f : G → G is an isomorphism. Equivalently, G is Hopfian if it is not isomorphic to any of its proper quotient groups, that is, G ̸∼ = G/N for any non-trivial normal subgroup N ◁ G. Let G = ⟨S | R⟩ be a finitely presented group. For any word w over S ∪ S −1 that represents the identity element in G, the area of w, denoted Area(w), is the minimal integer k such that w can be expressed in the free group as a product of k conjugates of the defining relations and their inverses: w=
k Y
ui ri±1 u−1 i
i=1
The Dehn function δ : N → N of the given finite presentation is defined as the maximum area required to reduce any trivial word of length at most n: δ(n) = max {Area(w) | w =G 1 and |w| ≤ n} It acts as an isoperimetric inequality, bounding the worst-case geometric complexity of the word problem for the group ([46]). 2.1.1
The Baumslag-Solitar Group BS(1, 2)
The first target algebraic structure in this study is the Baumslag-Solitar group BS(1, 2), due to its wellunderstood word problem paired with exponential growth. This group is defined by the finite presentation BS(1, 2) = ⟨a, b | bab−1 a−2 = 1⟩. The broader family of Baumslag-Solitar groups, denoted BS(m, n) = ⟨a, b | bam b−1 = an ⟩, was originally introduced by Gilbert Baumslag and Donald Solitar in 1962 to provide the first examples of two-generator, one-relator non-Hopfian groups (specifically when m and n share no common prime divisors, such as in BS(2, 3)) [13]. While BS(1, 2) is Hopfian, it has become a central benchmark in combinatorial and geometric group theory due to the severe dichotomy between its algorithmic space complexity and its geometric area complexity. The major mathematical results defining the behavior of BS(1, 2) are broadly categorized into algorithmic solvability and isoperimetric growth. Because BS(1, 2) is an HNN extension of the integers and belongs to the class of metabelian groups, its Word Problem is globally decidable. Algorithmically, it can be solved with extremely high efficiency. Recent complexity results have demonstrated that the Word Problem for BS(1, q) can be solved within the highly restrictive uniform TC0 complexity class, which defines a highly restrictive model of parallel computation ([85]). Being in TC0 imposes strict upper bounds on both the sequential and parallel time complexity of the word problem in BS(1, 2). Sequentially, evaluating a uniform TC0 circuit requires time proportional to its size, meaning the word problem is solvable in deterministic polynomial time (O(nc ) for some constant c) [89, 39, 37]. In contrast to its algorithmic efficiency, the geometric landscape of BS(1, 2) is notoriously hostile. The Dehn function, Area(W ), measures the worst-case number of times the defining relator (bab−1 a−2 = 1) must be applied to mathematically reduce a trivial word W of length N back to the identity element. Gersten proved that the Dehn function for BS(1, 2) exhibits strictly exponential growth [42]. This exponential scaling is precisely what makes BS(1, 2) an optimal test environment for evaluating Graph Neural Networks in cryptographic contexts. A naive, greedy string-rewriting algorithm, or an attacker 3
attempting a brute-force length-based search, will be quickly overwhelmed by the exponentially exploding number of intermediate reduction steps required to untangle a long identity word. 2.1.2
Stochastic Artin Groups with Mixed Commutation and Braid Relations
To evaluate the capacity of the architecture, the model is tested against a stochastically generated Artin group. While the Baumslag-Solitar group tests the network’s ability to navigate exponential geometric areas, this Artin group evaluates the model’s capacity to learn high-dimensional rewriting systems derived from arbitrary Coxeter graphs. In Artin groups relations take the form: xi xj xi . . . = xj xi xj . . . | {z } | {z } mi,j terms
(1)
mi,j terms
The Coxeter graph G = (V, E) provides a compact encoding of the Artin group’s algebraic structure, where each vertex v ∈ V corresponds to a generator xi . Edges between vertices are labeled by integers mi,j ≥ 2. The word problem for Artin groups is only partially understood, but remains open in general, in particular for Artin groups with 3-relations (mi,j = 3). The construction of random groups by defining relations probabilistically relies on the Erdős-Rényi random graph model Γ(n, p). The group is defined over a large rank of generators, S = {x0 , x1 , x2 , . . . , x100 }, with the group presentation governed by a random symmetric adjacency matrix M . Such constructions were defined and used in [10, 12, 17, 83]. The experimental setup generates a sparse interaction matrix for the Coxeter graph where some of the generator pairs (10%) do not interact (mi,j = ∞), hence generate a free subgroup. The remaining pairs (90%) are distributed between mi,j = 2 and mi,j = 3. At first, the adjacency matrix of the Coxeter graph is filled with 0, 2, 3, such that each entry has a 10% probability to be 0 (representing ∞), a 45% probability to be 2 or 3 respectively. Coxeter graphs have to be undirected, hence the obtained (unsymmetric) adjacency matrix is symmetrized by setting ai,j = max(ai,j , aj,i ), hence prefering braid relations over commutators. With a chosen random seed this led to 44 pairs of generators having no relation, 1523 pairs of generators commuting and 3483 pairs of generators having a braid relation. Such frameworks have been widely utilized to determine the topological properties, hyperbolicity thresholds, and automorphism group finiteness of random right-angled Artin groups (mi,j ∈ {2, ∞}) and Coxeter groups ([25, 21, 27, 14]). Recent theoretical extensions by Goldsborough and Vaskou [43] have generalized this to random Artin groups by simultaneously scaling the group rank and the specific probability distributions of the permitted edge coefficients. Right-angled Artin groups (RAAGs) are widely studied, see for example [20, 1, 86, 8, 26, 29, 28, 61]). For RAAGs, the Word Problem is highly tractable. Hermiller and Meier demonstrated that RAAGs possess finite, complete string-rewriting systems, allowing the Word Problem to be solved in linear time with respect to the word length [49]. The inclusion of braid relations (mi,j = 3) significantly complicates the geometry. While the Word Problem for general Artin groups remains famously open, subclasses characterized by sparse interaction graphs, such as large, extra-large, and FC-type Artin groups, have been proven decidable. Holt and Rees established practical, polynomial-time solutions for wide classes of these groups using shortlex automatic structures and localized geometric reductions [55]. Due to their robust algorithmic solvability but highly complex, non-abelian subgroups, Artin groups (particularly Braid groups and RAAGs) have been heavily proposed as platforms for post-quantum key exchange protocols, making their geometric topologies prime targets for cryptanalysis [68, 48, 59, 36]. In this experimental setup, the WPNet must implicitly learn the underlying Coxeter graph routing. It must recognize when local sub-words can commute past each other or braid through one another to reach the same global topological state.
2.2
Training data
Each word in these generators is transformed by mapping discrete sequences of group generators into structured graphs. This transformation is achieved through dynamic graph builders that translate unreduced words into specialized graph structures tailored to the underlying group geometry.
4
Given an unreduced word W = (g1 , g2 , . . . , gL ) where gk ∈ ±S, first the word is broken into subwords of length 5, where a new subword starts at every even index. If the final subwords have length less than 5, they are padded with 0, which represents the identity in the respective group. Each such subword represents one node in the graph. Each letter g is mapped into R7 : g g |g| g , cos , sign(g), g 7→ , sin(g), cos(g), sin . |S| 10 10 |S| Each node in the graph has a feature tensor t ∈ R5x7 , for the 5 letters in the subword, which is projected into n a smaller space by the BiLSTM defined in the next section. A word of length n will result in a graph of 2 nodes. The resulting nodes are then connected by edges in the following way: Nodes representing neighboring subwords are connected by an edge of type 1, and nodes of distance 2 in this resulting graph are then further connected by an edge of type 2. The resulting graph for the word w = g1 g2 g1−1 g3 g2 g3−1 g1 g4 g2−1 g3 g5 g1−1 g2 g1 g4−1 in A(Γ) is shown in Figure 1, where each integer i represents gi .
Figure 1: Graph representation of the word w = g1 g2 g1−1 g3 g2 g3−1 g1 g4 g2−1 g3 g5 g1−1 g2 g1 g4−1 in A(Γ). The objective of WPNet is to determine algebraic equivalence between word representations within BS(1, 2) or a randomly generated Artin group of rank 101. The training is restricted to sequences with initial lengths ranging from L = 20 to 100. Within the free monoid over 200 symbols (generators and their formal inverses), the number of base configurations exceeds 20020 ≈ 1046 . This leads to a total state space of unique graph topologies that is computationally practically infinite, rendering a static approach with a fixed training table infeasible. Although a smaller, discrete subset could be pre-computed, utilizing a fixed dataset would likely induce overfitting, where the neural network memorizes specific syntactic patterns rather than true algebraic invariants. By employing a statistical learning strategy [80, 91], the model is exposed to a continuous variety of isometrically equivalent presentations. This forces the architecture to learn the intrinsic geometric structure of the group element rather than static sequence data. To achieve this, the training dataset consisting of 8192 sequence triplets is dynamically regenerated every five epochs to effectively prevent overfitting. To force the neural network to learn underlying algebraic invariants rather than relying on superficial length heuristics, the training data engine employs a stochastically driven triplet generator. The batch distribution is deliberately engineered to expose the model to the exact types of heavy cryptographic padding utilized in Wagner-Magyarik attacks. 5
2.2.1
Contrastive Learning for Word Embeddings
The new batch generated every epoch comprises 8192 triplets (A, P, N ), evenly partitioned into trivial identity bases and uniformly sampled random sequence bases. The Anchor (A) and Positive (P ) are constructed by independently tangling the base word through Nops randomized algebraic operations (e.g., inserting trivial pairs or applying group relators) to preserve mathematical equivalence. The tangling parameter Nops is assigned probabilistically: identity bases receive moderate to massive tangling (up to 150 operations), while random bases are tangled proportionally to their length, with a subset undergoing extreme tangling. To construct the Negative (N ), the base word is first rendered algebraically inequivalent via internal block permutations or boundary truncations. Crucially, this mutated base is then obfuscated using the exact same Nops parameter applied to A and P . This symmetrical tangling ensures N perfectly matches the visual complexity and length distribution of the anchor, preventing the network from exploiting superficial length heuristics and forcing it to map deep algebraic invariants. Example 1. To illustrate the generation pipeline, consider a short random base element over the generating set {a, b}. 1. Base Words Initialization • Base: Wbase = aba−1 • Negative Base: The base word undergoes a boundary truncation mutation (dropping the suffix generator a−1 ), yielding the inequivalent word Wmut = ab. 2. Symmetrical Tangling Exactly two randomized algebraic operations (in this case, the insertion of trivial freely-reducing pairs gg −1 ) are independently applied to expand each word. • Anchor (A): Tangling Wbase 1. Insert bb−1 at index 1: abb−1 ba−1 2. Insert a−1 a at index 0: a−1 aabb−1 ba−1 • Positive (P ): Tangling Wbase independently 1. Insert aa−1 at index 3: aba−1 aa−1 2. Insert b−1 b at index 2: abb−1 ba−1 aa−1 • Negative (N ): Tangling the mutated base Wmut 1. Insert aa−1 at index 1: aaa−1 b 2. Insert bb−1 at index 4: aaa−1 bbb−1 Resulting Triplet A = a−1 aabb−1 ba−1 P = abb−1 ba−1 aa−1 N = aaa−1 bbb−1 Despite sharing identical string lengths and an identical degree of structural obfuscation (Nops = 2), A and P mathematically reduce to the equivalence class aba−1 , while N reduces to the inequivalent class ab. 2.2.2
Geodesic length prediction
To evaluate the geodesic length estimators, a new batch of 32768 target-label tuples (Wtangled , Ltrue , Linput ) is generated each epoch to represent the unreduced graph input, the ground-truth geodesic length, and the initial string length, respectively. The process begins by uniformly sampling an inflated random sequence of generators. The reduction to a base representative Wbase is handled differently depending on the target group’s complexity. For the Baumslag-Solitar group BS(1, 2), exact symbolic solvers like GAP trigger exponential 6
memory blowup via quotient rewriting (e.g., replacing ab → b2 a). To bypass this, BS(1, 2) sequences are reduced using a greedy, length-decreasing Dehn-style heuristic. Substrings matching more than half of a symmetrized relator are strictly replaced by their shorter inverse. Combined with memorization caching, this forces rapid, polynomial-time convergence to a highly accurate local minimum (serving as an upper bound on the true geodesic). Conversely, for Artin Groups, the exact mathematical geodesic is computed. Because the relations consist of commuting generators, combining free reduction with continuous lexicographical sorting forms a complete and confluent rewriting system ([18], [49]). This guarantees that Wbase reaches its unique canonical normal form and absolute minimum length. Once Wbase is computed, its length Ltrue = |Wbase | is recorded. To ensure compatibility with the classifier’s output dimensions, any sequence where Ltrue ∈ / [2, Lmax ] is discarded. Finally, to force the network to navigate the underlying geometry rather than reading pre-reduced strings, Wbase is structurally obfuscated into Wtangled by applying k random algebraic operations (e.g., inserting trivial pairs or swapping commuting generators), with the tangling volume dynamically scaled as k = min(intensity, max(2, ⌊Ltrue /5⌋)). 2.2.3
Wagner-Magyarik attack
To train the metric learning architecture, batches of 32768 contrastive triplets (A, P, N ) are dynamically generated using a bipartite distribution. To prepare the network for cryptanalysis, 50% of the dataset simulates a Wagner-Magyarik public-key distribution: a random identity pad is generated and combined with a secret public word to form a structurally obfuscated ciphertext C. The positive sample P is constructed by appending the correct inverse key to C and tangling the result (which mathematically reduces to the identity), while the negative sample N applies an incorrect inverse key, leaving an un-canceled algebraic residual against an identity anchor A. The remaining 50% of the dataset enforces general algebraic equivalence. A base word of random length is sampled from predefined length buckets utilizing either the Baumslag-Solitar generators {a, b, a−1 , b−1 } or a localized subset of the Artin group generators. For these general triplets, the anchor A is the base word, the positive P is a structurally tangled variant, and the negative N is a tangled version of an isometrically mutated base word. Across both distributions, the volume of applied algebraic tangling operations scales dynamically with the sequence length to maintain consistent obfuscation density across varying word lengths.
2.3
WPNet Architecture
Despite addressing three distinct algebraic tasks, such as Geodesic Length Estimation in BS(1, 2), WagnerMagyarik (WM) Cryptanalysis, the core neural architecture relies on a shared, modular framework. The foundation is a temporal graph built from unreduced word chunks, processed by a sequence encoder (BiLSTM, [51]), refined via a Gated Graph Isomorphism Network (GINEConv, [90, 57]), and collapsed using Attentional Aggregation. To prevent redundancy, the shared baseline is defined first, followed by the specific structural variations required for each downstream task. 2.3.1
Shared Core Framework
The input to all models is an unreduced algebraic word represented as a directed graph, as described in detail in Subsection 2.2 1. Gated Message Passing (AlgebraicBlock): Given initial continuous node embeddings X (0) ∈ RN ×d and projected edge attributes E ∈ RM ×d , the graph undergoes K rounds of spatial message passing. Each layer computes a topological message M (k) using a GINE framework: M (k) = MLPgine X (k) + Aggregate(X (k) , E) (2) To manage non-commutative structural data and mitigate over-smoothing, node states are updated using a learned gating matrix Wgate ∈ Rd×2d : G(k) = σ Wgate [X (k) ∥ M (k) ] (3) 7
X (k+1) = LayerNorm X (k) + G(k) ⊙ M (k)
(4)
2. Attentional Aggregation: To extract a fixed-size representation of the entire word, an attentional aggregation layer ([64]) pools the node features. Two parallel multi-layer preceptrons (MLPs) compute a normalized scalar attention score and a feature transformation for the pooled representation: αi = softmax (MLPgate (Xi )) Zpool =
N X
(5)
αi · MLPfeat (Xi )
(6)
i=1
2.3.2
Task-Specific Variations
Geodesic Estimation: The geodesic model takes continuous 7-dimensional node encodings and processes them via the Bi-LSTM. It strictly relies on the final state of the GINE layers X (K) for pooling. The pooled output Zpool bypasses normalization and is fed into a classification head (two linear layers with GELU and 20% Dropout) to output unnormalized logits Ŷ ∈ RLmax +1 . Wagner-Magyarik cryptanalysis: The Wagner-Magyarik distinguisher model utilizes multi-scale jumping knowledge to capture both localized reductions and deep conjugate PK structures. Before attentional pooling, it sums the outputs across all message passing layers: Xsum = k=0 X (k) . The final pooled vector Zpool is L2 -normalized to project the embeddings onto a unit hypersphere, trained via InfoNCE to group algebraically equivalent words. Because A(Γ) is defined over a large generating set (|S| = 101), continuous sinusoidal encodings lack distinction. Instead, individual letters map to a discrete embedding matrix. Each generator letter is assigned a unique positive integer index. The padding element maps to 0. The 101 positive generators map to indices 1 through 101. Their formal inverses map to indices 102 through 202. This creates a fixed vocabulary size of V = 202. The network initializes a trainable weight matrix of size 202 × d, where d is the hidden dimension size (e.g., 512). Each integer ID in the 5-letter subword acts as a direct row index to retrieve a specific, independently learned d-dimensional vector from this matrix. The 5 token embeddings within a subword are flattened into a wide vector (5d) before Bi-LSTM processing. Following the message-passing layers, a single (K) (K) learned parameter tensor Zglobal is added identically to all N nodes (X̃i = Xi + Zglobal ) to anchor local features to a shared baseline before pooling and L2 -normalization. Local message-passing layers struggle to propagate information across extremely long sequences. Adding a global tensor to every node allows longrange, graph-wide structural properties to be accessed instantly across the entire graph without getting lost in deep message-passing steps. In tasks relying on triplet loss and similarity comparisons (like the WagnerMagyarik cryptographic attack), the global tensor anchors the final pooled embedding to a shared, learned coordinate space, improving the separation margin between valid and corrupted words. Table 1 details the specific structural variations applied to this shared core for the three distinct experimental tasks. Table 1: Architectural variations across the three algebraic tasks. d is the hidden capacity (256 to 512), dout is the output dimension, N is the number of nodes, and Lmax is the maximum exact length limit. Component
Geodesic (BS(1, 2))
Estimation
Node Encoding Chunk Size Bi-LSTM Input Integration
Continuous sinusoidal (7-dim) C=5 Node level (N × 7) Terminal output only (X (K) )
Output Head Objective Final Dim.
Linear classifier (logits) Cross-Entropy (Length Class) Lmax + 1 classes
WM Metric (BS(1, 2))
Attack
Continuous sinusoidal (7-dim) C=6 Node level (N × 7) Multi-scale summation P ( X (k) ) L2 Normalization InfoNCE (Cosine Similarity) dout = 128 hypersphere
8
Artin Embedding Discrete ID lookup (V = 201) C = 5 (flattened sequence) Token level (N × 5d) Global token shift (+Zglobal ) L2 Normalization InfoNCE (Cosine Similarity) dout = 128 hypersphere
2.4
Training Procedure
For the task of embedding words in the hypersphere, the InfoNCE objective [73, 22] uses in-batch negative sampling to contrast an anchor Aj against its hard positive Pj , hard negative Nj , and all other non-matching batch elements. The loss is defined as: B
1 X exp(sim(Aj , Pj )/τ ) L=− log P PB B j=1 exp(sim(Aj , Pj )/τ ) + k=1 exp(sim(Aj , Nk )/τ ) + k̸=j exp(sim(Aj , Pk )/τ ) where τ is the temperature and sim(u, v) is the cosine similarity between L2 -normalized representations. To maintain a stable identity reference vector, elements reducing to the trivial identity are explicitly flagged. A False Negative Mask prevents the InfoNCE loss from repelling these equivalent elements, while an Identity Gravity Penalty actively pulls them toward their batch centroid.Optimization is executed in PyTorch [76] via AdamW [66] (learning rate 10−4 , weight decay 10−4 ), gradient clipping (max norm 1.0) [75], and a plateau scheduler (factor 0.5, patience 5). For geodesic length classification, the network is optimized using cross-entropy loss ([81, 45]). Crossentropy measures the divergence between the model’s predicted probability distribution over discrete length classes and the true discrete length labels. By treating each possible word length as an independent category rather than assuming a continuous scalar progression, cross-entropy forces the network to construct sharp, highly specific decision boundaries for exact integer lengths, avoiding the outlier sensitivity and averaging issues typical of regression. For the Wagner-Magyarik attack, optimization employs Triplet Margin Loss [80, 88]. This objective function structures the latent representation space by evaluating triplets consisting of an anchor (a), a positive sample (p), and a negative sample (n). The loss penalizes the model unless the distance between the anchor and the positive is strictly smaller than the distance between the anchor and the negative by at least a predefined margin m. Expressed mathematically as: L(a, p, n) = max{d(a, p) − d(a, n) + m, 0} this formulation ensures tight clustering of algebraically equivalent elements while enforcing a strict geometric boundary against non-equivalent cryptographic mutations.
2.5
Model evaluation
The model is evaluated on three tasks. The first task is similar to the model training setup, where triplets of words are presented and the model’s embeddings are tested. In the second task, the models must predict the geodesic length of an unreduced word in BS(1, 2) and the Artin group A(Γ). The third task is the Wagner-Magyarik cryptosystem attack. 2.5.1
Word embeddings
The model’s distinguishing capability is evaluated using a triplet-based metric learning framework. For each test, the algorithm generates a triplet consisting of an anchor word, a positive word, and a negative word based on the following specific criteria: The positive word is a geodesic representative that is algebraically equivalent to the anchor word. The negative word is a group element constructed by randomly scrambling 25% to 50% of the letters from the positive word. The network projects the corresponding graphs into a normalized embedding space to compute the cosine similarities for the anchor-positive pair (spos ) and the anchor-negative pair (sneg ). A prediction is classified as correct only if the positive similarity exceeds the negative similarity by a strict margin threshold of 0.2 (spos − sneg > 0.2). Final accuracy percentages and margin statistics are then aggregated across the entire test suite. 2.5.2
Geodesic length prediction
To evaluate the geodesic length estimator, test datasets are systematically generated and stratified by their true reduced length. The evaluation domain, spanning up to the classification limit Lmax = 200, is partitioned into ten uniformly sized length buckets. For each bucket, exactly 100 valid test samples are generated. The 9
generation process begins by constructing a random sequence of generators with an initial length uniformly sampled up to four times the bucket’s maximum boundary. This heavily inflated sequence is reduced to establish its ground-truth geodesic length, and discarded if it falls outside the targeted bucket. Note that the samples generated here follow the same strategy as the training data generation and might not be the true geodesic representative in BS(1, 2). In the Artin group the reduction algorithm guarantees the true geodesic representative. To guarantee the final input remains strictly non-geodesic, the reduced core undergoes a final tangling phase where a dynamically scaled number of random algebraic operations (inserting trivial pairs or symmetrized relators, bounded to a maximum of 3 operations) is applied. Model performance is then quantitatively assessed using exact match accuracy, the strict percentage of instances where the network’s predicted length class perfectly matches the true length and the Mean Absolute Error (MAE) of the predictions. 2.5.3
Wagner-Magyarik Attack
To evaluate the network’s zero-shot algebraic understanding, the model is periodically suspended during training and applied as an equality oracle in two distinct cryptographic attacks. Both tests rely on an identity reference vector, computed by passing eight independently tangled trivial identity words through the network and averaging their L2 -normalized latent embeddings. Test 1: Wagner-Magyarik Direct Decryption 1. Generation: The environment generates two random public words (P0 , P1 ) of length 5 and selects a secret message bit b ∈ {0, 1}. A ciphertext is constructed as C = R · Pb , where R is a highly tangled identity pad (generated with noise length Nlen = 10). 2. Model Application: The attacker constructs two hypothesis strings: T0 = C · P0−1 and T1 = C · P1−1 . The model encodes T0 and T1 into the latent space. The network computes the cosine similarity of both embeddings against a stabilized identity reference vector (the computed centroid of 64 independently generated cryptographic identity pads). 3. Accuracy Calculation: The model predicts bit b = 0 if sim(T0 , Id) > sim(T1 , Id), and b = 1 otherwise. A trial is marked successful if the prediction matches the true secret bit. Total accuracy is the percentage of correct predictions over 50 independent trials. Example 2. Wagner-Magyarik Direct Decryption: Consider the Baumslag group G1,2 = ⟨a, b | bab−1 = a2 ⟩. The generators are mapped numerically as a = 1, b = 2, a−1 = −1, b−1 = −2. 1. Initialization and Encryption: • Public Words: P0 = [1, 2, 1, −2, 1] (representing abab−1 a) and P1 = [2, −1, 2, 1, 1] (representing ba−1 ba2 ). • Secret Bit: b = 0, making the target word P0 . • Identity Pad (R): A highly tangled string generated via random insertions of aa−1 , bb−1 , and the relator bab−1 a−2 . Mathematically, R reduces to the empty word. • Ciphertext (C): C = R · P0 . 2. Hypothesis Construction: Two test strings are formed by appending the inverse of each public word to the ciphertext: T0 = C · P0−1 = (R · P0 ) · P0−1 = R T1 = C · P1−1 = (R · P0 ) · P1−1 Mathematically, T0 simplifies exactly to the identity pad R, while T1 remains a complex, non-trivial group element.
10
3. Evaluation: The network embeds both T0 and T1 into the latent space and computes their cosine similarities against the stabilized identity centroid (Id): sim(T0 , Id) = 0.94
(High structural similarity to identity)
sim(T1 , Id) = 0.12
(Recognized as a non-identity element)
4. Conclusion: Since sim(T0 , Id) > sim(T1 , Id), the network correctly predicts the secret bit b = 0. The decryption trial is marked successful.
2.6
Computational Methods
All code was developed in Python 3.11.2 using Pytorch (2.10.0+cu128) on an Nvidia Quadro RTX 8000 or alternatively Python 3.13.9 and Pytorch (2.14.0.dev20260720+cu130) when working with the Nvidia Geforce RTX 5080.
3
Results and Discussion
The results are structured into three distinct parts, covering both the Baumslag-Solitar group BS(1, 2) and the Artin group A(Γ). The first part analyzes the embedding properties of equivalent and non-equivalent words. The second part presents the performance of the geodesic length prediction models, and the final part evaluates the cryptanalytic attack on the Wagner-Magyarik protocol.
3.1
Word embeddings
The model embeds words in each group into the unit sphere in R128 . When an unreduced word w is represented by a geodesic segment g, the embeddings are close to each other, in other words, they have a high cosine similarity. When a geodesic segment h is similar to g and hence w, but is not equal, then the cosine similarity of the embeddings is low. The models are trained on triplets (w, p, n), where w is an unreduced word, p a reduced representative and n a reduced word that is similar to p but not equal. Before evaluating the distinguisher against the cryptographic protocol, the topological validity of the learned embedding space must be established. The network must demonstrate that it maps visually distinct but algebraically equivalent words (positive pairs) to proximate coordinates, while mapping inequivalent words (negative pairs) to distant orthogonal coordinates. 3.1.1
Word embeddings
The separation metric is defined as the margin ∆ = Spos − Sneg , where S denotes the cosine similarity in the learned metric space. To test for zero-shot algebraic generalization, the evaluation was conducted across escalating word lengths up to L = 25000, well exceeding the examples seen in the training data where lengths were capped at 100. Analysis of the training run reveals a two-stage learning dynamic (Figure 2a). In the initial phase, the architecture rapidly generalizes, solving the word problem with 100% accuracy for sequences up to L = 250 by the second epoch. At this peak convergence state, the model achieves a mean classification accuracy of 99.93% when considering words of length up to 5000. It should be emphasized here that the model only saw words of length up to 100 in training. The generalization as demonstrated in Table 2 shows very good identification well beyond that threshold. Notably, an inverse relationship between word length and the separation margin emerges at extreme scales. As L increases beyond 250, the geometric margin compresses (decreasing from +0.599 at L = 100 to +0.298 at L = 5000). This continuous compression indicates that as the length of the sequence grows, the graph embeddings become denser, pulling the negative representations closer to the positive cluster. However, because the difference remains strictly positive with low standard deviation, the decision boundary is perfectly preserved. This confirms that the network has not memorized finite token patterns, but has
11
(a)
(b)
Figure 2: (a) Learning curve for word embeddings in BS(1,2). (b) Learning curve for word embeddings in A(Γ). successfully internalized the non-commutative quotient geometry of the group at an asymptotic scale, which is in particular emphasized by still achieving 74.90% accuracy on words of length 20,000. The task for evaluating the learning process of the Artin-WPNet was set up analogously to the task for the BS-WPNet. The success rates of both models are compared in Table 2. For the Artin group, practical reasons required capping the word length at 1000. The Artin-WPNet was evaluated in five tests on 10 samples for each word length, generating the average success rate and standard deviation. The approximate word reduction described in Section 2.2.2 in BS(1, 2) is much more efficient than in A(Γ). Further, as will be seen in the results of the geodesic length prediction, the words in BS(1, 2) reduce at a much higher rate than in the Artin group. This led to extensive memory demands for longer words, rendering the investigation of word lengths 2500 and 5000 unfeasible for the Artin group. Table 2: Combined Word Problem Classification Results BS(1,2)
Artin Group
Word Length
Accuracy (%)
Margin (± Std)
Accuracy (%)
Margin (± Std)
50 100 250 500 1000 2500 5000 10,000 15,000 20,000
97.00% ± 1.58% 97.60% ± 1.28% 100.00% ± 0.00% 100.00% ± 0.00% 100.00% ± 0.00% 97.50% ± 0.71% 94.50% ± 1.58% 86.10% ± 1.50% 79.90% ± 2.48% 74.90% ± 1.77%
+0.565 ± 0.024 +0.599 ± 0.016 +0.537 ± 0.010 +0.428 ± 0.016 +0.347 ± 0.020 +0.328 ± 0.022 +0.298 ± 0.016 +0.224 ± 0.019 +0.191 ± 0.018 +0.179 ± 0.015
100.00% ± 0.00% 100.00% ± 0.00% 100.00% ± 0.00% 98.00% ± 4.00% 96.00% ± 4.90% – – – – –
+0.744 ± 0.055 +0.585 ± 0.027 +0.471 ± 0.031 +0.356 ± 0.022 +0.310 ± 0.009 – – – – –
The final classification results of Artin-WPNet in Table 2 are very similar to the ones of BS(1, 2). The larger standard deviation stems from the lower number of tests that were possible. The success rate per word length and epoch is shown in Figure 2b. It can be seen that in contrast to the results in Figure 2a for BS(1, 2), the Artin-WPNet takes a significantly longer time to learn. Further, each epoch took on average 35.132 ± 2.946 seconds for training data generation, 9.308 ± 2.668 seconds for gradient descent and around another 2 min 38 sec (±1 min 22 sec) for evaluation, significantly longer than BS-WPNet (9.07s ± 0.58s for data generation, 7.21s ± 1.09s for each epoch training and 8.11s ± 0.44s for testing) due to the more complex data generation. It can also be seen in Figure 2b that the WPNet learns to correctly classify shorter words first, and words with noise of length up to 1000 take almost 80 epochs to reach a classification accuracy of at least 95%. The learning curves in Figure 2b also show a much higher variability than the learning curves for BS(1, 2) in Figure 2a. This is suspected to be attributed to the increased number of generators and the overall algebraic complexity. Generating and testing 1000 words of length 1000 in BS(1, 2) took 14.362 ± 0.316s seconds for generation 12
and 0.181 ± 0.042 seconds for inference. In the Artin group A(Γ) data generation and testing for 1000 words of length 1000 in the Artin group took on average 135.297 ± 20.301 seconds for generation and 1.447 ± 0.054 seconds for inference. It can already be seen that inference is significantly faster than even test data generation, further highlighting that WPNet can act as a fast approximate solution to the word problem.
3.2
Geodesic length prediction
The metabelian group BS(1, 2) heavily compresses unreduced words. Figure 3a demonstrates this, showing true geodesic representations are typically 10% to 20% of the original input length. Analyzing the unreduced versus geodesic lengths in A(Γ) reveals that the shrinkage is less pronounced than in BS(1, 2), as illustrated in Figure 3b. The parameters for the random Artin group (p = 0.9) were chosen aggressively to yield a shrinkage of approximately 20%. The WPNet for BS(1, 2) and A(Γ) further exhibit slightly different learning curves, as shown in Figure 3c and 3d. Configured as a 200-class classifier, WPNet evaluated these lengths over 150 epochs.
(a)
(b)
(c)
(d)
Figure 3: Word length reduction in BS(1, 2) (a) and A(Γ) (b). The training progress for the accuracies per length bucket are shown in (c) for BS(1, 2) and in (d) for A(Γ). Table 3 outlines the peak results for both groups, highlighting a strong global accuracy of 80.30% (MAE = 0.26) for BS(1, 2). The model excels on shorter words (> 90% accuracy) but gradually declines for geodesics exceeding 120 letters (derived from unreduced words up to length 800). Figure 3c illustrates uniform convergence, with longer words consistently trailing shorter sequences. Crucially, while exact match accuracy decreases for longer sequences (e.g., 57% for lengths 180-200), the MAE remains well below 1 across all buckets. This sub-unit error indicates that even incorrect length predictions deviate from the true geodesic length by merely one or two letters. Unsurprisingly, since the WPNet has been trained as a classifier, the generalization above length 200 is marginal, with error rates of 97% at lengths 200-300 and 0% accuracy above that. Table 3 details the models’ performance across length buckets at peak convergence. The model demonstrates exceptional precision on mid-length sequences (30 to 179 letters), consistently achieving exact match accuracies above 88% with a Mean Absolute Error (MAE) under 0.3.
13
Table 3: Combined Performance Breakdown by Length Bucket at Peak Convergence BS(1,2)
Artin Group
Length
Avg. Input
MAE
Acc. (%)
Avg. Input
Avg. Red.
MAE
Acc. (%)
0-19 20-39 40-59 60-79 80-99 100-119 120-139 140-159 160-179 180-200
33.8 79.6 127.7 184.0 239.6 266.8 346.2 379.6 423.6 500.9
0.14 0.05 0.17 0.16 0.18 0.27 0.39 0.25 0.46 0.57
95.00% 98.00% 91.00% 93.00% 86.00% 76.00% 67.00% 76.00% 64.00% 57.00%
10.6 29.2 49.5 69.3 89.2 109.9 129.1 150.1 169.7 189.9
9.9 26.3 43.7 60.0 75.0 92.4 107.2 123.1 138.9 155.8
3.18 0.20 0.08 0.00 0.06 0.10 0.12 0.20 0.08 0.52
73.00% 90.00% 96.00% 100.00% 97.00% 95.00% 94.00% 90.00% 96.00% 76.00%
BS(1,2) Global Metrics: Loss = 2.3262, MAE = 0.26, Accuracy = 80.30%.
Performance degrades at both extremes: the shortest sequences (0 to 19 letters) struggle with a high MAE of 8.79, while the longest sequences (180 to 200 letters) show a sharp decline in accuracy to 54% as the MAE exceeds 1.0. Similarly to the geodesic length prediction for BS(1, 2), the generalization beyond word length 200 is very poor, as to be expected when using a classifier.
3.3
Attack on Wagner-Magyarik
In the Wagner-Magyarik test the WPNet was trained to correctly identify one of two public words Wp1 , Wp2 , which were obscured by words w, v, where w ≡ 1, v ≡ 1 in G = BS(1, 2) or G = A(Γ). The test was set up to increase the length of w and v and the success rate in correctly identifying either Wp1 or Wp2 was recorded. Table 4 summarizes the results. With an increased length in the noise word the certainty of the detection in BS(1, 2) drops. This is reflected in the margin reducing to as low as 0.085 for noise word lengths of 1000, which means that the embedding of both words lie very close to each other, but are still distinguishable in most cases, which the accuracy of 97.80% reflects. On the other hand, the model for the Artin group A(Γ) is well capable of separating longer words, which the margin of 1.035 at length 1000 shows. Table 4: Performance of WPNet for WM on BS(1, 2) and A(Γ) Length 10 50 100 500 1000
BS(1, 2) Accuracy ± std Margin 99.20% ± 0.40% +1.706 ± 0.435 98.40% ± 0.80% +1.320 ± 0.647 97.60% ± 1.36% +0.709 ± 0.573 97.40% ± 1.74% +0.162 ± 0.151 97.80% ± 1.33% +0.085 ± 0.070
A(Γ) Accuracy ± std Margin 99.00 ± 2.00 +1.112 ± 0.190 98.00 ± 2.45 +1.050 ± 0.039 98.00 ± 4.00 +0.985 ± 0.127 98.00 ± 2.45 +1.053 ± 0.062 97.00 ± 2.45 +1.035 ± 0.088
Training just takes on average 11.37s ± 2.05s, with another 6.42s ± 0.49s for the data generation, per epoch. Testing 5x100 words of each length bucket took on average 2min 20.43s (± 6.53s), with more than 50% of the testing time allocated to the in total 500 words of length 1000. Data generation for the 8192 triplets in A(Γ) required an average of 40.05s ± 17.08s per epoch. This high variance stems from the fluctuating shrink factor between the unreduced and reduced words. Longer unreduced sequences generated larger graph structures, which subsequently increased the training time to 18.12s ± 6.01s per epoch. Testing durations remained efficient at 21.87s ± 1.51s. A notable distinction emerges regarding the detection margin under increasing noise. As shown in Table 4, the certainty margin for BS(1, 2) drops drastically to 0.085 at a noise length of 1000. In contrast, the margin for A(Γ) remains highly stable at 1.035 under identical noise conditions. This indicates a surprising robustness in the generated embeddings, particularly given the notorious computational difficulty of certain Artin groups. Ultimately, WPNet successfully uncovers the hidden messages across both groups, further confirming the established vulnerabilities of the Wagner-Magyarik protocol. While this success is expected for the
14
computationally tractable BS(1, 2) group, it is highly significant for the Artin group A(Γ), where the word problem in the presence of numerous braid relations is not generally known to be decidable.
4
Discussion
The results demonstrate that WPNet provides a fast and efficient heuristic approximation for the word problem. While the word problem in the Baumslag-Solitar group BS(1, 2) is mathematically well understood, it remains notoriously difficult, and often undecidable, for general Artin groups containing numerous braid relations. The success of the network on the latter indicates that this neuro-symbolic approach can scale effectively to other computationally hostile groups. Notably, execution runtimes are magnitudes shorter than those of exact symbolic solvers like SageMath ([53, 35]), and inference times require only a fraction of the time needed for data generation. This approach does not offer a mathematically universal solution for infinite general group structures. The outputs are strictly heuristic, and the evaluations were restricted to word lengths up to 20,000. However, this bounded computational space perfectly covers the word lengths that are practically feasible and relevant for real-world cryptographic applications. Rather than relying on a single universal architecture, a variety of models were shaped specifically for their respective learning tasks. The flexibility of WPNet allows it to be easily adapted and rapidly retrained for other algebraic structures. Furthermore, training these specialized models proved highly efficient, typically concluding within a few hours on standard consumer hardware. The geodesic lengths were predicted using a classifier, where each length represents one class. Initial experiments utilizing continuous regression heads failed to estimate geodesic lengths accurately. This failure is hypothesized to stem from the discrete, non-smooth geometry of algebraic word spaces, where smooth continuous loss functions struggle to model the abrupt length transitions caused by minor character edits. Reframing the task as discrete classification successfully resolved this optimization instability. Nevertheless, architectural limitations remain at sequence length extremes. Geodesic length predictions for very short words exhibit higher error rates, an artifact of the sequence chunking mechanism producing graphs with too few nodes to establish rich topological representations. However, this error margin is practically negligible for the targeted cryptographic applications. Conversely, evaluating significantly longer words is constrained by the heavy computational bottlenecks of training data generation. To alleviate this constraint, future iterations could implement supergraphs that bundle multiple nodes to compress the spatial representation. To further enhance classification accuracy across broad length regimes, a hierarchical multi-stage classification framework offers a promising path forward. In this setup, a coarse primary model first routes an input word into a specific length bracket, after which a specialized secondary model optimized strictly for that length range determines the exact geodesic length. The computational workloads for this study were predominantly executed on a single Quadro 8000 GPU, with some supplementary data generation outsourced to workstations equipped with GeForce RTX 5080 cards. Expanding access to advanced AI clusters and distributed computing resources would drastically accelerate the dataset generation pipeline and allow for deeper scaling. Ultimately, these findings highlight a highly promising direction for future work integrating machine learning with geometric group theory. The adaptability of WPNet suggests that similar neural constructions could be successfully applied to a wide range of algebraic challenges, including the conjugacy problem or for heuristic predictions to the shortest conjugator as recently discussed in ([16]). Furthermore, the structural embeddings of algebraic words into the continuous hypersphere generated by these models present a mathematically rich latent space that warrants independent geometric study.
5
Conclusion
This research establishes a highly promising direction for analyzing infinite groups using machine learning, presenting WPNet as an effective heuristic solver for the word problem and geodesic length prediction. By transforming unreduced algebraic words into dynamic graph structures, the architecture successfully clusters equivalent elements in a continuous embedding space without executing discrete reduction steps. While exact 15
mathematical solvers suffer from exponential memory blowup on complex topologies, the presented approach achieves rapid evaluation times. Although predictions are heuristic and currently limited to word lengths up to 20,000, this scope comfortably encompasses the domains practically utilized in post-quantum cryptography. The successful deployment against the Wagner-Magyarik cryptosystem practically demonstrates the cryptographic severity of these structural embeddings. Future work can seamlessly adapt this flexible framework to a broader range of infinite groups and related algebraic challenges, such as the conjugacy problem. Furthermore, implementing multi-stage classifiers and supergraphs to bundle nodes will efficiently resolve existing computational bottlenecks at extreme sequence lengths.
6
Acknowledgments
The author would like to thank the technical staff at Middlesex for outstanding support with access to the server infrastructure that made this work possible.
References [1] Aaron Abrams, Noel Brady, Pallavi Dani, and Robert Young. Pushing fillings in right-angled artin groups. Journal of the London Mathematical Society, 87(3):663–688, 2013. [2] Sergei I. Adian. Fragments of the word ∆ in the braid group. Matematicheskie Zametki, 36(1):25–34, 1984. [3] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik’s cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356–363, 2019. [4] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), 2021. [5] Joseph A. Altobelli. The word problem for Artin groups of FC type. Journal of Pure and Applied Algebra, 129(1):1–22, 1998. [6] Iris Anshel, Michael Anshel, and Dorian Goldfeld. An algebraic method for public-key cryptography. Mathematical Research Letters, 6(3):287–291, 1999. [7] Kenneth I. Appel and Paul E. Schupp. Artin groups and infinite coxeter groups. Inventiones mathematicae, 72(2):201–220, 1983. [8] Javier Aramayona and Conchita Martı́nez-Pérez. On the first cohomology of automorphism groups of graph groups. Journal of Algebra, 452:17–41, 2016. [9] E. Artin. Theory of braids. The Annals of Mathematics, 48:101, 1947. [10] Emil Artin. Theorie der zopfe. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 4(1):47–72, 1925. [11] Alessandro Barro. Node classification and search on the Rubik’s cube graph with GNNs. arXiv preprint arXiv:2501.18580, 2025. [12] Andreas Baudisch. Subgruppen von (reinen) artin-gruppen. Fundamenta Mathematicae, 3(96):211–219, 1977. [13] Gilbert Baumslag and Donald Solitar. Some two-generator one-relator non-hopfian groups. Bulletin of the American Mathematical Society, 68(3):199–201, 1962. [14] Jason Behrstock, Mark Hagen, and Alessandro Sisto. Thickness, relative hyperbolicity, and randomness in coxeter groups. Algebraic & Geometric Topology, 17:705–740, 2017. [15] William W. Boone. The word problem. Annals of Mathematics, 70:207–265, 1958. 16
[16] Martin R. Bridson, Timothy R. Riley, and Andrew W. Sale. Conjugator length in finitely presented groups, 2026. [17] Egbert Brieskorn. Die fundamentalgruppe des raumes der regulären orbits einer endlichen komplexen spiegelungsgruppe. Inventiones mathematicae, 12(1):57–61, 1971. [18] Egbert Brieskorn and Kyoji Saito. Artin-gruppen und Coxeter-gruppen. Inventiones Mathematicae, 17:245–272, 1972. [19] Ruth Charney. Artin groups of finite type are biautomatic. Math. Ann., 292(4):671–683, 1992. [20] Ruth Charney. An introduction to right-angled artin groups. Geometriae Dedicata, 125(1):141–158, 2007. [21] Ruth Charney and Michael Farber. Random groups arising as graph products. Algebr. Geom. Topol. 12 (2012) 979-995, 2010. [22] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597–1607. PMLR, 2020. [23] Alexander Chervov, Kirill Khoruzhii, Nikita Bukhal, Jalal Naghiyev, Vladislav Zamkovoy, Ivan Koltsov, Lyudmila Cheldieva, Arsenii Sychev, Arsenii Lenin, Mark Obozov, Egor Urvanov, and Alexey Romanov. A machine learning approach that beats large Rubik’s cubes. arXiv preprint arXiv:2502.13266, 2025. [24] Alexander Chervov, Ariel Soibelman, Stanislav Lytkin, Ivan Kiselev, Stepan Fironov, Andrey Lukyanenko, Anna Dolgorukova, Fedor Ogurtsov, Semen Petrov, Stepan Krymskii, et al. CayleyPy RL: Pathfinding and reinforcement learning on Cayley graphs. arXiv preprint arXiv:2502.18663, 2025. [25] ARMINDO COSTA and MICHAEL FARBER. Topology of random right angled artin groups. Journal of Topology and Analysis, 03:69–87, 2011. [26] Pallavi Dani. The large-scale geometry of right-angled coxeter groups. arXiv preprint arXiv:1807.08787, 2018. [27] Matthew B. Day. Finiteness of outer automorphism groups of random right-angled artin groups. Algebr. Geom. Topol. 12 (2012) 1553-1583, 2011. [28] Matthew B Day, Andrew W Sale, and Richard D Wade. Calculating the virtual cohomological dimension of the automorphism group of a RAAG. Bulletin of the London Mathematical Society, 53(1):259–273, 2021. [29] Matthew B Day and Richard D Wade. Relative automorphism groups of right-angled Artin groups. Journal of Topology, 12(3):759–798, 2019. [30] Max Dehn. Über unendliche diskontinuierliche gruppen. Mathematische Annalen, 71:116–144, 1911. [31] Patrick Dehornoy and Eddy Godelle. A conjecture about artin–tits groups. Journal of Pure and Applied Algebra, 217(4):741–756, 2013. [32] Pierre Deligne. Les immeubles des groupes de tresses généralisés. Inventiones mathematicae, 17(4):273– 302, 1972. [33] Francois Digne. Dual presentations of tress groups of closely connected a type. Commentarii Mathematici Helvetici, 81:23–47, 01 2006. [34] Murray Elder. A linear-time algorithm to compute geodesics in solvable Baumslag–Solitar groups. Illinois Journal of Mathematics, 54(1):109–128, 2010. [35] David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Mike S. Paterson, and William P. Thurston. Word Processing in Groups. Jones and Bartlett Publishers, 1992. 17
[36] Ramón Flores and Delaram Kahrobaei. Cryptography with right-angled Artin groups. Theoretical and Applied Informatics, 31(3), 2019. [37] Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. The word problem for metabelian groups in TC0 . Logical Methods in Computer Science, 17, 2021. [38] Moses Ganardi, Markus Lohrey, and Georg Zetzsche. Knapsack and the power word problem in solvable baumslag-solitar groups. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170, pages 37:1–37:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. [39] Moses Ganardi, Markus Lohrey, and Georg Zetzsche. Knapsack and the power word problem in solvable Baumslag-Solitar groups. International Journal of Algebra and Computation, 33(06):617–649, 2023. [40] David Garber, Shmuel Kaplan, Mina Teicher, Boaz Tsaban, and Uzi Vishne. Length-based conjugacy search in the braid group. Contemporary Mathematics, 418:75–88, 2006. [41] F. A. GARSIDE. The braid group and other groups. The Quarterly Journal of Mathematics, 20:235–254, 1969. [42] Stephen M. Gersten. Dehn functions and l1 -norms of finite presentations. In Algorithms and Classification in Combinatorial Group Theory, pages 195–224. Springer, 1992. [43] Antoine Goldsborough and Nicolas Vaskou. Random artin groups. arXiv, 2023. [44] Marı́a Isabel González Vasco and Rainer Steinwandt. On the Wagner-Magyarik public key cryptosystem. International Journal of Information Security, 2(3):167–172, 2004. [45] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. See Section 5.5 for maximum likelihood and cross-entropy loss. [46] Mikhael Gromov. Hyperbolic groups. In Essays in group theory, pages 75–263. Springer, 1987. [47] Jonathan Gryak, Robert M. Haralick, and Delaram Kahrobaei. Solving the conjugacy decision problem via machine learning. Experimental Mathematics, 29(1):66–78, 2020. [48] Maggie Habeeb, Delaram Kahrobaei, and Vladimir Shpilrain. A secret sharing scheme based on group presentations and the word problem. In Computational and Combinatorial Group Theory and Cryptography, volume 582, pages 143–150. American Mathematical Society, 2012. [49] S. Hermiller and J. Meier. Algorithms and geometry for graph products of groups. Journal of Algebra, 171:230–257, 1995. [50] Graham Higman, Bernhard H Neumann, and Hanna Neumann. Embedding theorems for groups. Journal of the London Mathematical Society, s1-24(4):247–254, 1949. [51] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735– 1780, 1997. [52] Jordan Hoffmann, Simon Schmitt, Simon Osindero, Karen Simonyan, and Erich Elsen. Algebranets. arXiv, 2020. [53] Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien. Handbook of Computational Group Theory. Chapman & Hall/CRC, 2005. [54] Derek F. Holt and Sarah Rees. Artin groups of large type are shortlex automatic with regular geodesics. Proceedings of the London Mathematical Society, 104(3):486–512, 2012. [55] Derek F Holt and Sarah Rees. Artin groups of large type are shortlex automatic with regular geodesics. Proceedings of the London Mathematical Society, 104(3):486–512, 2012.
18
[56] Heinz Hopf. Beiträge zur klassifizierung der flächenabbildungen. Journal für die reine und angewandte Mathematik, 165:225–236, 1931. [57] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations, 2020. [58] Haocheng Ju and Bin Dong. AI for mathematics: Progress, challenges, and prospects. arXiv preprint arXiv:2601.13209, 2026. [59] Delaram Kahrobaei and Vladimir Shpilrain, editors. Algorithmic Problems of Group Theory, Their Complexity, and Applications to Cryptography, volume 633 of Contemporary Mathematics. American Mathematical Society, 2015. [60] Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Kwon, Ju Sung Kang, and Sang Geun Hahn. New public-key cryptosystem using braid groups. In Advances in Cryptology — CRYPTO 2000, pages 166–183. Springer, 2000. [61] Rob P Kropholler and Genevieve S Walsh. Incoherence and fibering of many free-by-free groups. Annales de l’Institut Fourier, 72(6):2385–2397, 2022. [62] Françoise Levy-dit Vehel and Ludovic Perret. On the wagner-magyarik cryptosystem. In International Workshop on Coding and Cryptography (WCC), pages 316–329, 2005. [63] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semisupervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’18/IAAI’18/EAAI’18. AAAI Press, 2018. [64] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016. [65] Alexei Lisitsa, Mateo Salles, and Alexei Vernitski. An application of neural networks to a problem in knot theory and group theory (untangling braids). arXiv preprint arXiv:2206.05373, 2022. [66] Ilya Loshchilov and Frank Hutter. arXiv:1711.05101, 2017.
Decoupled weight decay regularization.
arXiv preprint
[67] Jon McCammond and Robert Sulway. Artin groups of euclidean type. Inventiones mathematicae, 210:231–282, 2017. [68] Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov. Group-based Cryptography. Advanced Courses in Mathematics - CRM Barcelona. Birkhäuser Basel, 2008. [69] Alexei D Myasnikov, Alexander Ushakov, and Vladimir Shpilrain. Random subgroups of braid groups: An approach to cryptanalysis of a braid group based cryptographic protocol. In International Workshop on Public Key Cryptography, pages 302–314. Springer, 2006. [70] Alexei G. Myasnikov and Alexander Ushakov. Random subgroups and analysis of the length-based and quotient attacks. Journal of Mathematical Cryptology, 2(1):29–61, 2008. [71] Petr S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Matematicheskogo Instituta imeni V. A. Steklova, 44, 1955. [72] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), 2020. [73] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018.
19
[74] Horace Pan and Risi Kondor. Fourier bases for solving permutation puzzles. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of PMLR, pages 172–180, 2021. [75] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pages 1310–1318. PMLR, 2013. [76] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, highperformance deep learning library. In Advances in neural information processing systems, volume 32, 2019. [77] David Peifer. Artin groups of extra-large type are biautomatic. Journal of Pure and Applied Algebra, 110(1):15–56, 1996. [78] Max Petschack, Alexandr Garbali, and Jan de Gier. Learning the symmetric group: large from small. arXiv, 2025. [79] A N Platonov. Isoperimetric function of the baumslag-gersten group. Moscow University Mathematics Bulletin, 59(3):12–17, 2004. [80] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 815–823, 2015. [81] Claude E. Shannon. 27(3):379–423, 1948.
A mathematical theory of communication.
Bell System Technical Journal,
[82] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. [83] Jacques Tits. Groupes et géométries de Coxeter. Institut des Hautes Etudes Scientifiques, 1961. [84] Leonard VanWyk. Graph groups are biautomatic. Journal of Pure and Applied Algebra, 94(3):341–352, 1994. [85] Heribert Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer Science & Business Media, 1999. [86] Richard D Wade. The lower central series of a right-angled Artin group. L’Enseignement Mathématique, 61(3):343–371, 2015. [87] Neal R Wagner and Paul R Magyarik. A public-key cryptosystem based on the word problem. In Advances in Cryptology: Proceedings of CRYPTO 84, pages 19–36. Springer, 1985. [88] Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(Feb):207–244, 2009. [89] Armin Weiß. A logspace solution to the word and conjugacy problem of generalized baumslag-solitar groups. arXiv preprint arXiv:1602.02445, 2016. [90] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019. [91] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, volume 33, pages 5812–5823, 2020.
20