Automated conjecturing with \emph{TxGraffiti}

Resumen Técnico de "Conjeturación Automatizada con TxGraffiti"

Enunciado del Problema
El artículo aborda el desafío de la conjeturación automatizada: la generación de desigualdades matemáticamente útiles, no redundantes e interpretables entre invariantes numéricos de objetos matemáticos (específicamente grafos). Si bien la demostración automática de teoremas es un campo maduro, la generación automatizada de conjeturas ha luchado históricamente con el problema de "demasiadas afirmaciones", donde la enumeración sistemática produce vastas cantidades de afirmaciones verdaderas en la base de datos pero triviales o redundantes. El objetivo es filtrar estas afirmaciones para identificar aquellas que ofrecen nueva información genuina (informatividad) y son adecuadas para el escrutinio y la demostración humana.

Metodología
El artículo introduce TxGraffiti (Texas Graffiti), un sistema basado en heurísticas y optimización que opera sobre una tabla de instantánea versionada y finita de objetos matemáticos. A diferencia de sus predecesores (Graffiti y Graffiti.pc), que calculan invariantes dinámicamente durante la búsqueda, TxGraffiti trata la base de evidencia como un artefacto estático.

La tubería de conjeturación consta de las siguientes etapas:

1. Curación de Datos (Tabla de Instantánea):

   • Se construye una tabla donde las filas representan objetos (grafos) y las columnas representan invariantes numéricos precalculados (por ejemplo, número de independencia $\alpha$, número de emparejamiento $\mu$) y predicados booleanos (por ejemplo, "es conexo", "es regular").
   • La estrategia de curación prioriza la cobertura sobre la aleatoriedad, incluyendo específicamente construcciones extremas, testigos de igualdad (casos agudos) y contraejemplos para asegurar que la tabla sea diagnósticamente rica.

2. Generación de Candidatos mediante Optimización:

   • Para un invariante objetivo elegido $\alpha$ y un predicado booleano $P$ (hipótesis), el sistema busca cotas afines de la forma $\alpha \le mx + b$ o $\alpha \ge mx + b$, donde $x$ es un invariante predictor.
   • En lugar de enumerar árboles de expresión complejos, TxGraffiti fija una clase de hipótesis paramétrica simple (cotafines univariadas) y ajusta los coeficientes resolviendo Programas Lineales (PL).
   • PL de Cota Superior: Minimiza el holgura total $\sum (mx_i + b - \alpha_i)$ sujeto a $\alpha_i \le mx_i + b$ para todas las filas que satisfacen $P$.
   • PL de Cota Inferior: Maximiza el holgura total (o minimiza el holgura negativo) sujeto a $\alpha_i \ge mx_i + b$.
   • El sistema también admite cotas multivariadas y relaciones no lineales expandiendo el esquema con columnas derivadas (por ejemplo, $n-\mu$, $\Delta^2$), aunque la interfaz web predeterminada prioriza modelos de predictor único para la interpretabilidad.

3. Filtrado (Heurística Estática-Dalmata):

   • Para gestionar la redundancia, TxGraffiti emplea una heurística estática-dalmata.
   • Número de Contacto: Definido como la cuenta de objetos en la instantánea donde la desigualdad se cumple con igualdad (instancias agudas).
   • Lógica de Selección: Los candidatos se ordenan por número de contacto. Un candidato se acepta como "representativo" si toca al menos un objeto que aún no está cubierto por los conjuntos agudos de los representantes previamente aceptados. Si el conjunto agudo de un candidato es idéntico al de un representante aceptado, se retiene como un "alias" (una forma sintáctica diferente del mismo lugar de igualdad). Los candidatos que no añaden nuevas instancias agudas se descartan.

Contribuciones Clave

• Arquitectura del Sistema: TxGraffiti se presenta como un sistema modular disponible como una aplicación web interactiva y un paquete de código abierto en Python (txgraffiti). Desacopla el cálculo de invariantes de la generación de conjeturas, permitiendo una iteración rápida en conjuntos de datos fijos.
• Ajuste Basado en Optimización: El artículo cambia el paradigma de la enumeración basada en gramática (generar fórmulas y probarlas) al ajuste basado en optimización (resolver PLs para encontrar las cotas más ajustadas para predictores específicos). Esto asegura que los candidatos generados sean "verdaderos en la tabla" por construcción y optimizados para la precisión.
• Filtrado Estático-Dalmata: La adaptación de la heurística Dalmata a una instantánea fija permite un proceso de filtrado determinista de un solo paso que prioriza las cotas con alto "contacto" (muchos testigos agudos) mientras elimina la redundancia.
• Interpretabilidad: Al restringir la clase de hipótesis a plantillas afines simples y racionalizar los coeficientes, el sistema produce conjeturas que son concisas y legibles para humanos.

Resultados
El artículo demuestra la eficacia del sistema a través de varios ejemplos:

• Ilustración del Flujo de Trabajo: Usando el número de dominación total $\gamma_t$, el sistema generó una cota $\gamma_t(G) \ge \frac{2}{3}R(G)$ para grafos con $\Delta(G) \le 3$. Esto se generalizó rápidamente a un teorema que involucra $\Delta(G)$ y se demostró utilizando estimaciones estándar.
• Publicaciones Estimuladas: El artículo cataloga varios resultados de teoría de grafos que se originaron como conjeturas de TxGraffiti y fueron posteriormente demostrados:
  • Independencia vs. Emparejamiento: La conjetura de que $\alpha(G) \le \mu(G)$ para grafos $r$-regulares fue demostrada en [51].
  • Cotas de Fuerza Cero: Varias desigualdades que relacionan los números de fuerza cero ($Z, Z_t, Z_+$) con parámetros de dominación e independencia fueron conjeturadas y demostradas, incluyendo $Z(G) \le \beta(G)$ para grafos sin garras y cotas para grafos cúbicos.
  • Problemas Abiertos: El sistema identificó la conjetura $Z(G) \le \alpha(G) + 1$ para grafos conexos con $\Delta \le 3$, que sigue siendo un problema abierto central, aunque existen resultados parciales.

Significado y Afirmaciones
El artículo posiciona a TxGraffiti no como una herramienta para descubrir teoremas profundos de forma autónoma, sino como un generador de evidencia estructurado que facilita la investigación matemática humana.

• Validez Empírica: El sistema produce afirmaciones "verdaderas en la tabla", lo que significa que se cumplen para todas las instancias en la instantánea curada. Los autores reservan explícitamente el término "teorema" para afirmaciones establecidas por demostración formal, distinguiendo la salida del sistema como conjeturas.
• Postura Filosófica: Ecos de la perspectiva empírica de Fajtlowicz (quien diseñó Graffiti), el artículo argumenta que la capacidad de las máquinas para producir conjeturas plausibles y profundas es un hecho empírico que respalda la visión de las máquinas como participantes significativos en el descubrimiento matemático abierto.
• Escalabilidad y Reproducibilidad: Al tratar la tabla de instantánea como un artefacto versionado y auditable, TxGraffiti aborda los problemas de robustez de la corrupción de datos y asegura que las conjeturas puedan reproducirse y refinarse a medida que crece la base de evidencia.

Los autores concluyen que, si bien la implementación actual se centra en invariantes de grafos, el "paradigma de tabla de instantánea" y la tubería de optimización y filtrado son ampliamente aplicables a cualquier dominio donde los objetos admitan características y predicados computables.