💻 computer science

Learning Primality from Modular-Inverse Graphs

Este artículo demuestra que GraphSAGE puede lograr una precisión casi perfecta al distinguir entre enteros primos y compuestos mediante el aprendizaje de las diferencias estructurales en sus grafos de inversos modulares, mientras que GCN falla en capturar estas distinciones debido a sus limitaciones específicas de paso de mensajes.

Autores originales: Tal Weissblat

Publicado 2026-09-24

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Tal Weissblat

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Los números son los bloques de construcción de las matemáticas y, entre ellos, los números primos ocupan un lugar especial. Un número primo es un número entero mayor que uno que solo puede dividirse exactamente por uno y por sí mismo. Los números que pueden dividirse por otros números se denominan compuestos. Durante siglos, los matemáticos han buscado formas eficientes de distinguir estos dos tipos de números, una tarea que sigue siendo vital para la criptografía moderna y la seguridad informática. Mientras que los métodos tradicionales dependen de cálculos aritméticos complejos, una nueva línea de investigación plantea si las máquinas pueden aprender a reconocer estos patrones observando los números no como valores, sino como formas. Este enfoque trata la relación oculta dentro de un número como un mapa, con la esperanza de que la forma del mapa revele la naturaleza del propio número.

En un estudio reciente, el investigador Tal Weissblat exploró si la inteligencia artificial podía aprender a distinguir los números primos de los compuestos examinando estos mapas matemáticos. El investigador no le proporcionó a la computadora los números en sí. En su lugar, cada número fue transformado en un diagrama único llamado grafo de inverso modular. Para crear este diagrama, el investigador tomó un número específico y enumeró todos los números enteros menores que podían formarse con él. Luego, el investigador trazó líneas entre pares de estos números menores si al multiplicarse producían un resultado que, al dividirse por el número original, dejaba un resto de uno. Esta regla se aplicó exactamente de la misma manera a cada número, ya fuera primo o compuesto, sin decirle a la computadora cuál era cuál. El objetivo era ver si las formas resultantes se veían naturalmente diferentes dependiendo del tipo de número.

El estudio comenzó con un análisis profundo de la teoría detrás de estas formas. El análisis reveló una clara diferencia estructural entre los diagramas de los números primos y los de los números compuestos. Para un número primo, el diagrama está totalmente conectado de una manera específica: cada punto, excepto el cero, está vinculado a al menos otro punto. No hay puntos solitarios flotando solos. Por el contrario, los diagramas de los números compuestos contienen puntos aislados: números que no tienen ninguna conexión en absoluto. Además, los números primos producen diagramas con el máximo número posible de conexiones entre puntos distintos, mientras que los números compuestos tienen menos conexiones y esos puntos solitarios adicionales. Este hallazgo teórico sugería que una computadora debería ser capaz de distinguir la diferencia simplemente contando las conexiones o detectando los puntos aislados.

Para probar esto, el investigador entrenó dos tipos diferentes de modelos de inteligencia artificial con un conjunto de datos de 10,000 enteros, que iban desde el 2 hasta el 10,001. Los datos se dividieron de modo que los modelos aprendieran con números más pequeños y luego fueran probados con números más grandes que nunca habían visto antes. Un modelo, conocido como GraphSAGE, fue diseñado para prestar atención al vecindario local de cada punto en el diagrama. El otro, una Red Convolucional de Grafos, utilizaba un método diferente que promedia la información de los vecinos. Los resultados fueron marcadamente distintos. El modelo GraphSAGE aprendió la tarea con una precisión notable, identificando correctamente números primos y compuestos en el conjunto de prueba no visto con una precisión de casi el 99.9 por ciento. Logró generalizar con éxito los patrones aprendidos de números pequeños a otros mucho más grandes.

El segundo modelo, sin embargo, falló por completo. No funcionó mejor que el azar, logrando una precisión de exactamente el 50 por ciento. El análisis teórico explicó por qué sucedió esto. El modelo GraphSAGE fue capaz de distinguir entre puntos que tenían conexiones y puntos que estaban solos, preservando la diferencia estructural crucial encontrada en los diagramas de los números primos. El otro modelo, debido a la forma en que promedia la información, suavizó estas diferencias. Trataba a los puntos conectados y a los puntos aislados como si fueran lo mismo, borrando efectivamente la característica crucial que distinguía a los números primos de los compuestos. Este fallo no fue un error técnico, sino una limitación fundamental de ese método específico aplicado a este tipo de grafo matemático.

El estudio concluyó que la capacidad de aprender la primalidad a partir de estos grafos depende enteramente de la arquitectura del modelo de aprendizaje automático. La arquitectura GraphSAGE fue capaz de capturar las sutiles firmas estructurales de los números primos, mientras que la otra arquitectura común no pudo. La investigación también incluyó una comprobación para asegurar que el modelo estaba utilizando realmente la estructura del grafo y no solo memorizando números. Cuando se eliminaron las capas de procesamiento de grafos, el rendimiento del modelo cayó de nuevo al nivel del azar. Esto confirmó que el éxito provino del análisis de la forma de las conexiones, no de ningún truco numérico oculto. Los hallazgos demuestran que las propiedades aritméticas pueden, de hecho, codificarse en estructuras de grafos y ser aprendidas por las máquinas, siempre que la máquina esté construida con las herramientas adecuadas para ver las diferencias.

Resumen Técnico: Aprendizaje de la Primaridad a partir de Grafos de Inversos Modulares

Planteamiento del Problema
Esta investigación investiga si las Redes Neuronales de Grafos (GNN) pueden distinguir entre enteros primos y compuestos mediante el aprendizaje de representaciones basadas en grafos de los números. En lugar de introducir el valor entero directamente en un modelo, el estudio codifica cada entero $n$ como un "grafo de inverso modular". En esta representación, los vértices corresponden a los elementos $\{0, 1, \dots, n-1\}$ , y existe una arista entre dos vértices $a$ y $b$ si son inversos multiplicativos módulo $n$ (es decir, $a \cdot b \equiv 1 \pmod n$ ). Crucialmente, la regla de construcción del grafo es uniforme para todos los enteros y no incorpora explícitamente etiquetas de primaridad. El desafío central es determinar si surgen diferencias estructurales sistemáticas de forma natural de estas relaciones aritméticas que una GNN pueda explotar para clasificar la primaridad.

Metodología
El estudio emplea un enfoque de tres vertientes: caracterización teórica, análisis arquitectónico y evaluación empírica.

Caracterización Teórica: El autor establece primero una base matemática (Teorema 1) que describe la estructura de los grafos de inverso modular. Demuestra que:
- Enteros Primos ( $n=p$ ): El grafo contiene el número máximo posible de aristas conectando vértices distintos no nulos y no tiene vértices no nulos aislados. Todo elemento no nulo es invertible.
- Enteros Compuestos ( $n$ ): El grafo contiene menos aristas conectando vértices distintos e incluye vértices no nulos aislados (específicamente, $n - 1 - \phi(n)$ de tales vértices, donde $\phi$ es la función de Euler).
- La distinción depende de la presencia o ausencia de vértices no nulos aislados.
Análisis Arquitectónico (Mecanismos de Paso de Mensajes): El artículo analiza teóricamente cómo dos arquitecturas específicas de GNN—GraphSAGE y Redes Convolucionales de Grafos (GCN)—procesan estas diferencias estructurales:
- GraphSAGE: El análisis demuestra que el mecanismo de agregación de GraphSAGE (que separa las características de la raíz de las características de los vecinos) le permite asignar representaciones diferentes a los vértices aislados frente a los vértices no aislados. A través del agrupamiento de media global (global mean pooling), esta distinción local se preserva a nivel de grafo, lo que teóricamente permite al modelo detectar la diferencia en la proporción de vértices aislados entre primos y compuestos.
- GCN: Por el contrario, el análisis muestra que la agregación normalizada de GCN (que incluye bucles de auto-conexión o self-loops) provoca que los vértices aislados y los vértices no aislados reciban representaciones idénticas tras el primer paso. En consecuencia, la distinción estructural identificada en el Teorema 1 se pierde, lo que teóricamente impide que la GCN distinga las clases.
Configuración Experimental:
- Conjunto de Datos: 10,000 enteros que van desde 2 hasta 10,001.
- Partición: Los datos se dividieron en conjuntos consecutivos y no superpuestos: Entrenamiento (2–4,000), Validación (4,001–7,000) y Prueba (7,001–10,001). Este diseño pone a prueba la generalización de enteros más pequeños a enteros más grandes y no vistos.
- Modelos: Se evaluaron GraphSAGE y GCN con varias configuraciones de capas ocultas (por ejemplo, 1-8-8, 1-16-16).
- Métricas: Debido al desequilibrio de clases (menos primos que compuestos), la Exactitud Balanceada (BA) fue la métrica principal.

Resultados Clave

Rendimiento de GraphSAGE: La arquitectura seleccionada de GraphSAGE (1-8-8) logró una Exactitud Balanceada media de validación del 99.97% y una Exactitud Balanceada media de prueba del 99.89% a través de tres semillas aleatorias. Clasificó correctamente todos los 329 números primos en el conjunto de prueba (100% de exhaustividad/recall). Las clasificaciones erróneas se limitaron a un pequeño número de números compuestos (semiprimos) etiquetados incorrectamente como primos.
Rendimiento de GCN: En marcado contraste, GCN logró una Exactitud Balanceada del 50.00% en todas las configuraciones y semillas, lo que corresponde a un rendimiento de nivel de azar.
Estudio de Ablación: Eliminar ambas capas de GNN del modelo GraphSAGE redujo el rendimiento al 50% de BA, confirmando que el mecanismo de paso de mensajes del grafo es esencial para la tarea. Eliminar una capa resultó en una caída solo marginal del rendimiento.
Análisis de Errores: Los errores cometidos por GraphSAGE fueron exclusivamente falsos positivos (compuestos predichos como primos), involucrando a menudo números con patrones de factorización específicos (por ejemplo, cuadrados de primos o productos de dos primos distintos), con probabilidades predichas situándose cerca del umbral de decisión.

Contribuciones Clave

Representación de Grafo: Introducción de una representación de grafo de inverso modular para enteros donde las propiedades aritméticas se transforman en topología de grafo sin etiquetas de primaridad explícitas.
Justificación Teórica: Una prueba matemática que establece diferencias estructurales sistemáticas (específicamente respecto a los vértices no nulos aislados) entre los grafos de enteros primos y compuestos.
Perspectiva Arquitectónica: Una demostración teórica y empírica de que la capacidad de aprender la primaridad de esta representación de grafo específica depende críticamente del mecanismo de paso de mensajes de la GNN. El estudio muestra que GraphSAGE puede preservar las distinciones estructurales necesarias, mientras que la normalización estándar de GCN las destruye.
Evidencia de Generalización: Evidencia empírica de que los modelos entrenados en enteros más pequeños pueden generalizar a enteros significativamente más grandes y no vistos cuando se utiliza la arquitectura adecuada.

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco matemáticamente fundamentado para investigar propiedades de la teoría de números a través del aprendizaje de representaciones de grafos. Demuestra que la información aritmética asociada con la primaridad puede codificarse puramente en la estructura del grafo y ser aprendida efectivamente por una GNN apropiada. El trabajo destaca que la elección de la arquitectura de la GNN no es simplemente un problema de ajuste de hiperparámetros, sino un determinante fundamental de si la información estructural específica (como la presencia de vértices aislados) puede utilizarse para el aprendizaje. Los resultados alinean el análisis teórico de los mecanismos de paso de mensajes con el comportamiento de aprendizaje observado, sugiriendo que el fallo de GCN y el éxito de GraphSAGE son consecuencias directas de cómo estos modelos manejan la topología específica de los grafos de inverso modular.

Limitaciones
El autor señala que el estudio se restringe a enteros hasta 10,001, dejando sin verificar el comportamiento en rangos sustancialmente mayores. Además, el análisis es específico para la representación de grafo de inverso modular y la tarea de clasificación binaria de primaridad, sin realizar afirmaciones inmediatas sobre otras propiedades o representaciones de grafos de la teoría de números.

Más como este