Constructing strong starters of orders $3p$: triplication with SAT solver

Este artículo presenta un método de triplicación que utiliza un solucionador SAT para construir strong starters de orden $3p$a partir de starters de orden$p$, abordando así la conjetura de Horton sobre su existencia en órdenes impares divisibles por 3.

Lo esencial

¡Claro que sí! Imagina que este artículo es como una receta de cocina secreta para crear un tipo especial de "rompecabezas matemático" llamado iniciador fuerte (strong starter).

Aquí tienes la explicación en español, usando analogías sencillas:

🧱 La Idea Principal: El "Triplicador" de Magia

Imagina que tienes un bloque de construcción pequeño y perfecto (un iniciador fuerte de un tamaño pequeño, digamos 7 piezas). Los matemáticos saben que estos bloques existen y funcionan bien. Pero, ¿qué pasa si quieres construir algo tres veces más grande (de tamaño 21)?

La teoría matemática tradicional se queda atascada aquí. No saben si siempre es posible hacer ese bloque grande. Este paper presenta una nueva "máquina mágica" llamada triplicación que intenta resolverlo.

La máquina funciona así:

1. Toma tu bloque pequeño (el "base").
2. Le añade un "ingrediente secreto" (llamado clave o key).
3. Intenta resolver un rompecabezas tipo Sudoku, pero en lugar de números del 1 al 9, usamos solo los números 0, 1 y 2 (como si fuera un Sudoku muy pequeño y repetitivo).
4. Si logras llenar ese Sudoku, ¡la máquina te devuelve automáticamente el bloque grande perfecto!

🕵️‍♂️ El Problema: El Sudoku Modulo 3

El corazón del método es este "Sudoku especial". No es un Sudoku normal donde buscas que los números no se repitan en filas y columnas. Aquí, las reglas son un poco más extrañas:

• Imagina que tienes una tabla con tres columnas. La primera columna es tu bloque original.
• Las otras dos columnas son "versiones encriptadas" de la primera.
• El reto es llenar una tabla paralela con los números 0, 1 y 2 de tal manera que:
  • Las diferencias entre los números en cada fila sean todas distintas.
  • Las sumas de ciertos grupos de números no choquen entre sí.
  • Cumplan reglas de "colores" (si un número aparece en un lugar, no puede aparecer en otro lugar específico).

Si logras encontrar una forma de llenar esta tabla sin violar ninguna regla, ¡tienes éxito! Si no puedes, es que esa combinación de bloque base y "clave" no funciona.

🤖 La Herramienta: El Detective Z3 (SAT Solver)

Como los humanos somos lentos probando millones de combinaciones de 0, 1 y 2, los autores usaron un detective de computadora llamado Z3.

• Z3 es un programa muy inteligente diseñado para resolver problemas de "satisfacción". Básicamente, le dices: "Aquí tienes 100 reglas estrictas. ¿Puedes encontrar una combinación de números que cumpla todas?".
• Si Z3 dice "Sí", te da la solución.
• Si dice "No", esa combinación no sirve.

Los autores usaron este detective para probar miles de casos. Es como si le dijeran a un robot: "Prueba todas las formas posibles de llenar este Sudoku especial y dime cuáles funcionan".

📊 ¿Qué descubrieron? (Los Resultados)

1. Funciona, pero cuesta trabajo: El método funciona muy bien para crear estos iniciadores grandes. Sin embargo, a medida que el bloque base se hace más grande, el detective Z3 tarda más en encontrar la solución.
   • Analogía: Es como buscar una aguja en un pajar. Si el pajar es pequeño (bloque base pequeño), lo encuentras en segundos. Si el pajar es gigante (bloque base grande), el detective puede tardar horas o incluso días.
2. No es una solución mágica para todo: Hay ciertas "llaves" (claves) que no funcionan. Si eliges la clave incorrecta, el Sudoku es imposible de resolver. El paper explica cómo saber de antemano qué claves descartar para no perder tiempo.
3. La mayoría de los rompecabezas son "falsos": Cuando probaron con iniciadores generados al azar, descubrieron que la inmensa mayoría no se pueden crear con este método de triplicación. Solo una pequeña fracción (como un 1.8% en algunos casos) sí se puede hacer así. Es como si la mayoría de las llaves no abrieran esta puerta específica.

🎯 ¿Por qué es importante?

Los matemáticos llevan desde 1989 con una conjetura (una suposición inteligente) de que estos iniciadores grandes deberían existir siempre, excepto en casos muy raros. Pero nadie ha podido probarlo ni construirlos sistemáticamente para todos los casos.

Este paper ofrece una nueva herramienta práctica:

• En lugar de esperar a que la teoría matemática pura nos diga "sí, existe", ahora tenemos una receta (Triplicación + Sudoku + Z3) para construirlos físicamente cuando sea posible.
• Es un paso gigante para entender mejor cómo se organizan los números en grupos cíclicos.

En resumen

Imagina que quieres construir un castillo de arena gigante (el iniciador de orden 3p). No sabes si el castillo puede mantenerse en pie.

• Este paper te dice: "Toma un castillo pequeño que ya sabes que funciona (orden p)".
• "Usa una receta especial (Triplicación) que te pide llenar un Sudoku de 3x3".
• "Usa un robot (Z3) para llenar ese Sudoku".
• "Si el robot lo llena, ¡tienes tu castillo gigante!"

Es una mezcla de magia matemática, lógica de Sudoku y fuerza bruta computacional para resolver un misterio que lleva décadas sin resolverse.

Resumen técnico

Resumen Técnico: Construcción de Inicios Fuertes de Orden 3p mediante Triplicación y Solucionadores SAT

1. El Problema

El artículo aborda la construcción de inicios fuertes (strong starters) en grupos cíclicos $\mathbb{Z}_n$ donde el orden $n$ es divisible por 3 (específicamente $n = 3p$, con $p$ primo a 3).

• Definición de Inicio Fuerte: Un inicio fuerte en un grupo abeliano de orden impar $n$ es una partición del conjunto $G^* = G \setminus \{0\}$ en pares $\{a_i, b_i\}$ tales que:
  1. Todas las sumas $a_i + b_i$ son distintas y no nulas módulo $n$.
  2. Todas las diferencias $\pm(a_i - b_i)$ son distintas y no nulas módulo $n$.
• Estado del Conocimiento: Se sabe que los inicios fuertes existen para la mayoría de los órdenes impares. Sin embargo, la conjetura de Horton (1989) postula que existen inicios fuertes para todos los órdenes impares, excepto $n=3, 5, 9$. A pesar de la evidencia computacional, la existencia teórica para órdenes $n=3p$ (donde $p > 3$ y $\gcd(p,3)=1$) no está completamente resuelta teóricamente, especialmente para $n > 1000$.
• Objetivo: Desarrollar un método constructivo para generar inicios fuertes de orden $3p$a partir de un inicio fuerte de orden$p$, llenando así un vacío en la literatura teórica y demostrando la viabilidad práctica de tal construcción.

2. Metodología: El Método de Triplicación

Los autores proponen un algoritmo novedoso llamado "triplicación". Este método reduce el problema de construir un inicio fuerte de orden $3p$ a la resolución de un sistema de ecuaciones y desigualdades lineales módulo 3, denominado "problema de Sudoku modular".

Pasos del Algoritmo:

1. Entrada: Se parte de un inicio fuerte $T$ de orden $p$ (coprimo con 3) y un valor clave $t \in \mathbb{Z}_p$.

2. Construcción de la Tabla $\Sigma_p$:

   • Se genera una tabla de triplicación con 3 columnas y $q+1$ filas (donde $q=(p-1)/2$).
   • Columna 1: Copia del inicio base $T$.
   • Columna 2: Transformación de $T$ sumando $t$ a cada elemento: $(x+t, y+t) \pmod p$.
   • Columna 3: Transformación de $T$ invirtiendo y restando: $(t-y, t-x) \pmod p$.
   • Fila Superior: Un par especial $(t, t)$.
   • Esta tabla $\Sigma_p$ contiene pares cuyas diferencias módulo $p$ son constantes por fila.

3. Formulación del Problema de Sudoku Modular ($\Sigma_3$):

   • Se introduce una tabla de incógnitas $\Sigma_3$ con los mismos índices que $\Sigma_p$, pero cuyos valores son enteros módulo 3 ($\{0, 1, 2\}$).
   • Se imponen tres tipos de restricciones estrictas para asegurar que la combinación final (vía Teorema Chino del Residuo) sea un inicio fuerte:
     • Restricciones de Fila: Las diferencias de los pares en cada fila de $\Sigma_3$ deben ser distintas módulo 3 (formando el conjunto $\{0, 1, 2\}$).
     • Restricciones de Conjuntos Débiles: Basadas en las sumas módulo $p$ de los pares en $\Sigma_p$. Si varios pares en $\Sigma_p$ tienen la misma suma, sus correspondientes sumas en $\Sigma_3$ deben ser distintas (y no nulas si la suma en $p$ es 0).
     • Restricciones de Color (Monocromáticas): Los valores en las posiciones donde un número específico aparece en $\Sigma_p$ deben tomar valores distintos en $\Sigma_3$.

4. Resolución:

   • El problema de encontrar una asignación válida para $\Sigma_3$ se formula como un problema de satisfacción de restricciones (CSP).
   • Se utiliza un solucionador SAT de propósito general (z3 de Microsoft) para encontrar una solución.
   • Si existe una solución para $\Sigma_3$, se combina con $\Sigma_p$ usando el Teorema Chino del Residuo para obtener el inicio fuerte final $S$ de orden $3p$.

3. Contribuciones Clave

• Nuevo Método Constructivo: La introducción del método de "triplicación" que transforma un problema combinatorio complejo en un problema de satisfacción de restricciones modular.
• Teorema de Existencia (Teorema 1): Demostración rigurosa de que cualquier solución válida al problema de Sudoku modular genera automáticamente un inicio fuerte de orden $3p$.
• Condiciones de Solvabilidad (Teorema 2): Establecimiento de una condición necesaria: la clave $t$ no debe ser 0 ni pertenecer al conjunto de sumas de pares del inicio base $T$. Si $t$ viola esto, el problema no tiene solución.
• Simetría de Soluciones (Teorema 3): Demostración de que las soluciones del Sudoku modular vienen en pares debido a una simetría involutiva (intercambio de 1 y 2 módulo 3).
• Algoritmo de Reconocimiento Inverso: Se propone un algoritmo para determinar si un inicio fuerte dado de orden $3p$puede haber sido generado por triplicación, analizando la estructura de sus filas módulo$p$.

4. Resultados Computacionales

Los autores implementaron el método en Python utilizando la biblioteca z3-solver y realizaron experimentos numéricos extensos:

• Series de Pruebas:
  • Serie 1: Órdenes base $p < 100$. Se probaron todos los valores de clave admisibles.
  • Serie 2: Órdenes base entre 100 y 500. Se probaron claves aleatorias.
  • Serie 3: Orden fijo $p=101$, ejecutando múltiples veces para analizar la variabilidad del tiempo de ejecución.
• Desempeño:
  • El tiempo de ejecución crece aproximadamente de forma polinómica (ajustado a $\tau \approx 0.023 \cdot m^2 \ln m$) para órdenes menores a 200.
  • Para órdenes mayores, el tiempo aumenta más rápido, pero el solucionador sigue siendo capaz de encontrar soluciones en tiempos razonables (minutos a horas para $p \approx 500$).
  • Comparación: El método de triplicación es significativamente más rápido que intentar encontrar un inicio fuerte de orden $3p$directamente con un solucionador SAT. Por ejemplo, para$n=39$, la triplicación tomó <1 segundo, mientras que la búsqueda directa tomó ~200 segundos.
• Hallazgos sobre la Conjetura: En todos los casos donde se cumplió la condición necesaria (clave $t$ válida), el solucionador encontró una solución, apoyando la conjetura de que tales inicios fuertes existen para todos los casos permitidos.

5. Significado e Impacto

• Avance Teórico: El trabajo proporciona una herramienta constructiva poderosa para abordar la conjetura de Horton en órdenes divisibles por 3, un área donde la teoría pura ha avanzado poco.
• Viabilidad Práctica: Demuestra que los solucionadores SAT modernos son herramientas efectivas para problemas de diseño combinatorio complejos, incluso cuando no se dispone de algoritmos especializados.
• Nuevas Direcciones: El problema del "Sudoku modular" se presenta como un nuevo objeto de estudio matemático. Los autores planean desarrollar algoritmos especializados que superen a los solucionadores SAT genéricos en futuras investigaciones.
• Limitaciones y Futuro: Aunque el método es efectivo, el tiempo de cálculo aumenta con el orden. Además, el método no garantiza encontrar todos los inicios fuertes de un orden dado, solo aquellos que son "triplicables". Sin embargo, los experimentos sugieren que la mayoría de los inicios fuertes aleatorios no son triplicables, lo que indica que la estructura de los inicios triplicados es un subconjunto específico pero importante.

En conclusión, el artículo presenta un puente exitoso entre la teoría de grupos, el diseño combinatorio y la computación moderna, ofreciendo un método robusto para generar estructuras matemáticas complejas que antes eran difíciles de construir sistemáticamente.