💻 computer science

Learning Primality from Modular-Inverse Graphs

This paper demonstrates that GraphSAGE can achieve near-perfect accuracy in distinguishing prime from composite integers by learning structural differences in their modular-inverse graphs, whereas GCN fails to capture these distinctions due to its specific message-passing limitations.

Original authors: Tal Weissblat

Published 2026-09-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Tal Weissblat

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Numbers are the building blocks of mathematics, and among them, prime numbers hold a special place. A prime number is a whole number greater than one that can only be divided evenly by one and itself. Numbers that can be divided by other numbers are called composite. For centuries, mathematicians have sought efficient ways to tell these two types of numbers apart, a task that remains vital for modern cryptography and computer security. While traditional methods rely on complex arithmetic calculations, a new line of inquiry asks whether machines can learn to recognize these patterns by looking at numbers not as values, but as shapes. This approach treats the hidden relationships within a number as a map, hoping that the shape of the map reveals the nature of the number itself.

In a recent study, researcher Tal Weissblat explored whether artificial intelligence could learn to distinguish prime numbers from composite ones by examining these mathematical maps. The researcher did not feed the computer the numbers themselves. Instead, every number was transformed into a unique diagram called a modular-inverse graph. To create this diagram, the researcher took a specific number and listed all the smaller whole numbers that could be formed with it. Then, the researcher drew lines between pairs of these smaller numbers if they multiplied together to produce a result that, when divided by the original number, left a remainder of one. This rule was applied exactly the same way to every single number, whether it was prime or composite, without telling the computer which was which. The goal was to see if the resulting shapes naturally looked different depending on the type of number.

The study began with a deep look at the theory behind these shapes. The analysis revealed a clear structural difference between the diagrams of prime numbers and those of composite numbers. For a prime number, the diagram is fully connected in a specific way: every point, except for zero, is linked to at least one other point. There are no lonely points floating alone. In contrast, the diagrams for composite numbers contain isolated points—numbers that have no connections at all. Furthermore, prime numbers produce diagrams with the maximum possible number of connections between distinct points, while composite numbers have fewer connections and those extra lonely points. This theoretical finding suggested that a computer should be able to tell the difference simply by counting connections or spotting the isolated points.

To test this, the researcher trained two different types of artificial intelligence models on a dataset of 10,000 integers, ranging from 2 to 10,001. The data was split so the models learned on smaller numbers and were then tested on larger numbers they had never seen before. One model, known as GraphSAGE, was designed to pay attention to the local neighborhood of each point in the diagram. The other model, a Graph Convolutional Network, used a different method that averages information from neighbors. The results were starkly different. The GraphSAGE model learned the task with remarkable precision, correctly identifying prime and composite numbers in the unseen test set with an accuracy of nearly 99.9 percent. It successfully generalized the patterns it learned from small numbers to much larger ones.

The second model, however, failed completely. It performed no better than random guessing, achieving an accuracy of exactly 50 percent. The theoretical analysis explained why this happened. The GraphSAGE model was able to distinguish between points that had connections and points that stood alone, preserving the crucial structural difference found in the prime number diagrams. The other model, due to the way it averaged information, smoothed out these differences. It treated connected points and isolated points as if they were the same, effectively erasing the very feature that distinguished prime numbers from composite ones. This failure was not a glitch but a fundamental limitation of that specific method when applied to this type of mathematical graph.

The study concluded that the ability to learn primality from these graphs depends entirely on the architecture of the machine learning model. The GraphSAGE architecture proved capable of capturing the subtle structural signatures of prime numbers, while the other common architecture could not. The research also included a check to ensure the model was actually using the graph structure and not just memorizing numbers. When the graph-processing layers were removed, the model's performance dropped back to random guessing. This confirmed that the success came from analyzing the shape of the connections, not from any hidden numerical tricks. The findings demonstrate that arithmetic properties can indeed be encoded into graph structures and learned by machines, provided the machine is built with the right tools to see the differences.

Technical Summary: Learning Primality from Modular-Inverse Graphs

Problem Statement
This research investigates whether Graph Neural Networks (GNNs) can distinguish between prime and composite integers by learning from graph-based representations of numbers. Rather than feeding the integer value directly into a model, the study encodes each integer $n$ as a "modular-inverse graph." In this representation, vertices correspond to elements $\{0, 1, \dots, n-1\}$ , and an edge exists between two vertices $a$ and $b$ if they are multiplicative inverses modulo $n$ (i.e., $a \cdot b \equiv 1 \pmod n$ ). Crucially, the graph construction rule is uniform for all integers and does not explicitly incorporate primality labels. The core challenge is to determine if systematic structural differences emerge naturally from these arithmetic relations that a GNN can exploit to classify primality.

Methodology
The study employs a three-pronged approach: theoretical characterization, architectural analysis, and empirical evaluation.

Theoretical Characterization: The author first establishes a mathematical foundation (Theorem 1) describing the structure of modular-inverse graphs. They prove that:
- Prime Integers ( $n=p$ ): The graph contains the maximum possible number of edges connecting distinct nonzero vertices and has no isolated nonzero vertices. Every nonzero element is invertible.
- Composite Integers ( $n$ ): The graph contains fewer edges connecting distinct vertices and includes isolated nonzero vertices (specifically, $n - 1 - \phi(n)$ such vertices, where $\phi$ is Euler's totient function).
- The distinction relies on the presence or absence of isolated nonzero vertices.
Architectural Analysis (Message-Passing Mechanisms): The paper theoretically analyzes how two specific GNN architectures—GraphSAGE and Graph Convolutional Networks (GCN)—process these structural differences:
- GraphSAGE: The analysis demonstrates that GraphSAGE's aggregation mechanism (separating root features from neighbor features) allows it to assign different representations to isolated vertices versus non-isolated vertices. Through global mean pooling, this local distinction is preserved at the graph level, theoretically enabling the model to detect the difference in the proportion of isolated vertices between primes and composites.
- GCN: Conversely, the analysis shows that GCN's normalized aggregation (including self-loops) causes isolated vertices and non-isolated vertices to receive identical representations after the first step. Consequently, the structural distinction identified in Theorem 1 is lost, theoretically preventing GCN from distinguishing the classes.
Experimental Setup:
- Dataset: 10,000 integers ranging from 2 to 10,001.
- Partitioning: The data was split into consecutive, non-overlapping sets: Training (2–4,000), Validation (4,001–7,000), and Test (7,001–10,001). This design tests generalization from smaller to larger, unseen integers.
- Models: GraphSAGE and GCN were evaluated with various hidden layer configurations (e.g., 1-8-8, 1-16-16).
- Metrics: Due to class imbalance (fewer primes than composites), Balanced Accuracy (BA) was the primary metric.

Key Results

GraphSAGE Performance: The selected GraphSAGE architecture (1-8-8) achieved a mean validation Balanced Accuracy of 99.97% and a mean test Balanced Accuracy of 99.89% across three random seeds. It correctly classified all 329 prime numbers in the test set (100% recall). Misclassifications were limited to a small number of composite numbers (semiprimes) incorrectly labeled as prime.
GCN Performance: In stark contrast, GCN achieved a Balanced Accuracy of 50.00% across all configurations and seeds, corresponding to chance-level performance.
Ablation Study: Removing both GNN layers from the GraphSAGE model reduced performance to 50% BA, confirming that the graph message-passing mechanism is essential for the task. Removing one layer resulted in only a marginal performance drop.
Error Analysis: Errors made by GraphSAGE were exclusively false positives (composites predicted as primes), often involving numbers with specific factorization patterns (e.g., squares of primes or products of two distinct primes), with predicted probabilities hovering near the decision threshold.

Key Contributions

Graph Representation: Introduction of a modular-inverse graph representation for integers where arithmetic properties are transformed into graph topology without explicit primality labels.
Theoretical Justification: A mathematical proof establishing systematic structural differences (specifically regarding isolated nonzero vertices) between graphs of prime and composite integers.
Architectural Insight: A theoretical and empirical demonstration that the ability to learn primality from this specific graph representation depends critically on the GNN's message-passing mechanism. The study shows that GraphSAGE can preserve the necessary structural distinctions, while standard GCN normalization destroys them.
Generalization Evidence: Empirical evidence that models trained on smaller integers can generalize to significantly larger, unseen integers when using the appropriate architecture.

Significance and Claims
The paper claims to provide a mathematically grounded framework for investigating number-theoretic properties through graph representation learning. It demonstrates that arithmetic information associated with primality can be encoded purely in graph structure and effectively learned by an appropriate GNN. The work highlights that the choice of GNN architecture is not merely a hyperparameter tuning issue but a fundamental determinant of whether specific structural information (like the presence of isolated vertices) can be utilized for learning. The results align the theoretical analysis of message-passing mechanisms with observed learning behavior, suggesting that the failure of GCN and the success of GraphSAGE are direct consequences of how these models handle the specific topology of modular-inverse graphs.

Limitations
The author notes that the study is restricted to integers up to 10,001, leaving the behavior on substantially larger ranges unverified. Additionally, the analysis is specific to the modular-inverse graph representation and the binary classification task of primality, without immediate claims regarding other number-theoretic properties or graph representations.

Technical Summary: Learning Primality from Modular-Inverse Graphs

More like this