🔢 mathematics

Automated conjecturing with \emph{TxGraffiti}

Cet article présente la conception, les principes fondamentaux et la méthodologie fondée sur les données de \emph{TxGraffiti}, un programme informatique qui automatise la génération de conjectures mathématiques — en particulier en théorie des graphes — tout en mettant en évidence ses contributions à la littérature et en introduisant une nouvelle interface web interactive.

Auteurs originaux : Randy Davila

Publié 2026-05-12

📖 4 min de lecture🧠 Analyse approfondie

CC0 1.0

Auteurs originaux : Randy Davila

Article original placé dans le domaine public sous CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez une immense bibliothèque numérique remplie de milliers de types d'énigmes différents (dans ce cas, des formes mathématiques appelées « graphes »). Pour chaque énigme de la bibliothèque, les mathématiciens ont déjà calculé une longue liste de statistiques : le nombre de pièces qu'elle contient, le nombre de connexions qu'elle établit, et si elle contient certaines formes à l'intérieur.

TxGraffiti est un programme informatique intelligent qui agit comme un détective hyper-organisé dans cette bibliothèque. Son travail n'est pas de résoudre les énigmes pour vous, mais d'examiner les statistiques et de deviner les règles qui les gouvernent.

Voici comment cela fonctionne, décomposé en étapes simples :

1. La bibliothèque « Instantané »

Au lieu que l'ordinateur tente de calculer les statistiques à la volée (ce qui serait lent), les chercheurs prennent d'abord un « instantané » de la bibliothèque. Ils créent une gigantesque feuille de calcul où chaque ligne est une énigme et chaque colonne est une statistique. Cette feuille de calcul constitue la « base de preuves ». L'ordinateur ne devine pas au hasard ; il ne regarde que les faits déjà inscrits dans cette feuille de calcul.

2. Le « Jeu de devinettes » (Ajustement de la ligne)

L'ordinateur choisit une statistique qu'il souhaite prédire (appelons-la « Cible », comme le nombre de pièces indépendantes dans une énigme). Il examine ensuite d'autres statistiques (les « Prédicteurs ») pour voir si elles peuvent aider à deviner la Cible.

Imaginez que vous essayez de deviner la taille d'une personne (Cible) en fonction de sa pointure de chaussures (Prédicteur). L'ordinateur trace une ligne droite sur un graphique qui se situe juste au-dessus de toutes les personnes dans la feuille de calcul. Il essaie de rendre cette ligne aussi proche que possible des personnes sans jamais passer en dessous d'elles.

Si la ligne touche une personne, cette personne est un « exemple parfait » de la règle.
L'ordinateur fait cela mathématiquement pour chaque combinaison possible de statistiques afin de trouver le « plafond » (borne supérieure) ou le « plancher » (borne inférieure) le plus serré et le plus précis.

3. Le filtre « Mur de la Renommée » (L'heuristique Dalmatien)

L'ordinateur génère des milliers de ces « lignes » (règles). La plupart sont ennuyeuses ou inutiles. Par exemple, il pourrait trouver une règle qui est vraie mais si lâche qu'elle ne vous apprend rien de nouveau.

Pour remédier à cela, TxGraffiti utilise un filtre appelé l'heuristique Dalmatien. Imaginez-le comme un conservateur de musée :

L'ordinateur examine une nouvelle règle.
Il se demande : « Cette règle explique-t-elle une énigme qu'aucune autre règle n'a encore expliquée ? »
Si la réponse est oui, la règle est ajoutée au « Mur de la Renommée ».
Si la réponse est non (car une autre règle couvre déjà parfaitement cette énigme), la nouvelle règle est jetée comme redondante.

Cela garantit que la liste finale est courte, précise et ne contient que les découvertes les plus intéressantes.

4. De la devinette à la preuve

La sortie de TxGraffiti est une liste de conjectures. En mathématiques, une conjecture est une « devinette intelligente » qui semble vraie basée sur les preuves, mais qui n'a pas encore été prouvée.

Le flux de travail : Un mathématicien humain examine la devinette de l'ordinateur. Il vérifie si elle a du sens. Il tente de la prouver en utilisant la logique.
Le succès : L'article présente plusieurs exemples concrets où TxGraffiti a fait une devinette, et où des mathématiciens humains l'ont ensuite prouvée pour en faire un théorème (un fait avéré).
- Exemple 1 : L'ordinateur a deviné que dans certaines formes régulières, le nombre de pièces indépendantes n'est jamais supérieur au nombre de paires appariées. Les humains ont prouvé que c'est vrai.
- Exemple 2 : Il a deviné une relation entre la « force nulle » (une méthode spécifique de coloration de formes) et les formes « sans griffe ». Les humains ont prouvé cela aussi.

Pourquoi cela compte

Avant des systèmes comme celui-ci, les mathématiciens devaient fixer des données pendant des années pour trouver des motifs. TxGraffiti automatise la partie « repérage de motifs ». Il ne remplace pas le mathématicien humain ; au contraire, il agit comme un télescope haute puissance, balayant les données pour orienter l'humain vers les nouvelles lois les plus prometteuses de l'univers.

En résumé : TxGraffiti est un outil qui prend une feuille de calcul de faits mathématiques, trace les meilleures lignes possibles à travers elles, filtre les ennuyeuses, et remet les « devinettes intelligentes » restantes aux humains pour les transformer en lois prouvées.

Résumé technique de « Conjecturation automatisée avec TxGraffiti »

Énoncé du problème
L'article aborde le défi de la conjecturation automatisée : la génération d'inégalités mathématiquement utiles, non redondantes et interprétables entre des invariants numériques d'objets mathématiques (spécifiquement des graphes). Alors que la preuve automatique de théorèmes est un domaine mature, la génération automatique de conjectures a historiquement lutté contre le problème des « trop nombreuses affirmations », où l'énumération systématique produit un vaste nombre d'énoncés vrais dans la base de données mais triviaux ou redondants. L'objectif est de filtrer ces énoncés pour identifier ceux qui offrent de véritables informations nouvelles (informativité) et qui sont adaptés à l'examen et à la preuve par des humains.

Méthodologie
L'article présente TxGraffiti (Texas Graffiti), un système basé sur des heuristiques et l'optimisation qui opère sur un tableau d'instantané versionné et fini d'objets mathématiques. Contrairement à ses prédécesseurs (Graffiti et Graffiti.pc), qui calculent les invariants dynamiquement pendant la recherche, TxGraffiti traite la base de preuves comme un artefact statique.

Le pipeline de conjecturation se compose des étapes suivantes :

Curation des données (Tableau d'instantané) :
- Un tableau est construit où les lignes représentent des objets (graphes) et les colonnes représentent des invariants numériques précalculés (par exemple, le nombre d'indépendance $\alpha$ , le nombre d'appariement $\mu$ ) et des prédicats booléens (par exemple, « est connexe », « est régulier »).
- La stratégie de curation privilégie la couverture par rapport au hasard, incluant spécifiquement des constructions extrémales, des témoins d'égalité (cas nets) et des contre-exemples pour garantir que le tableau soit diagnostiquement riche.
Génération de candidats via l'optimisation :
- Pour un invariant cible choisi $\alpha$ et un prédicat booléen $P$ (hypothèse), le système recherche des bornes affines de la forme $\alpha \le mx + b$ ou $\alpha \ge mx + b$ , où $x$ est un invariant prédictif.
- Au lieu d'énumérer des arbres d'expressions complexes, TxGraffiti fixe une classe d'hypothèses paramétrique simple (bornes affines univariées) et ajuste les coefficients en résolvant des Programmes Linéaires (PL).
- PL de borne supérieure : Minimise le relâchement total $\sum (mx_i + b - \alpha_i)$ sous la contrainte $\alpha_i \le mx_i + b$ pour toutes les lignes satisfaisant $P$ .
- PL de borne inférieure : Maximise le relâchement total (ou minimise le relâchement négatif) sous la contrainte $\alpha_i \ge mx_i + b$ .
- Le système prend également en charge des bornes multivariées et des relations non linéaires en étendant le schéma avec des colonnes dérivées (par exemple, $n-\mu$ , $\Delta^2$ ), bien que l'interface web par défaut privilégie les modèles à prédicteur unique pour l'interprétabilité.
Filtrage (Heuristique Dalmatien statique) :
- Pour gérer la redondance, TxGraffiti emploie une heuristique Dalmatien statique.
- Nombre de contacts : Défini comme le nombre d'objets dans l'instantané où l'inégalité tient avec égalité (instances nettes).
- Logique de sélection : Les candidats sont triés par nombre de contacts. Un candidat est accepté comme « représentatif » s'il touche au moins un objet non encore couvert par les ensembles nets des représentants précédemment acceptés. Si l'ensemble net d'un candidat est identique à celui d'un représentant accepté, il est conservé comme un « alias » (une forme syntaxique différente du même lieu d'égalité). Les candidats n'ajoutant aucune nouvelle instance nette sont rejetés.

Contributions clés

Architecture du système : TxGraffiti est présenté comme un système modulaire disponible sous forme d'application web interactive et de package Python open-source (txgraffiti). Il découple le calcul des invariants de la génération de conjectures, permettant une itération rapide sur des ensembles de données fixes.
Ajustement basé sur l'optimisation : L'article opère un changement de paradigme passant de l'énumération basée sur la grammaire (génération de formules et test) à l'ajustement basé sur l'optimisation (résolution de PL pour trouver les bornes les plus serrées pour des prédicteurs spécifiques). Cela garantit que les candidats générés sont « vrais dans le tableau » par construction et optimisés pour la précision.
Filtrage Dalmatien statique : L'adaptation de l'heuristique Dalmatien à un instantané fixe permet un processus de filtrage déterministe en un seul passage, privilégiant les bornes avec un « contact » élevé (de nombreux témoins nets) tout en éliminant la redondance.
Interprétabilité : En restreignant la classe d'hypothèses à des modèles affines simples et en rationalisant les coefficients, le système produit des conjectures concises et lisibles par les humains.

Résultats
L'article démontre l'efficacité du système à travers plusieurs exemples :

Illustration du flux de travail : En utilisant le nombre de domination totale $\gamma_t$ , le système a généré une borne $\gamma_t(G) \ge \frac{2}{3}R(G)$ pour les graphes avec $\Delta(G) \le 3$ . Cela a été rapidement généralisé en un théorème impliquant $\Delta(G)$ et prouvé en utilisant des estimations standard.
Publications stimulées : L'article recense plusieurs résultats de théorie des graphes qui ont pris leur origine comme conjectures TxGraffiti et ont été ensuite prouvés :
- Indépendance vs Appariement : La conjecture selon laquelle $\alpha(G) \le \mu(G)$ pour les graphes $r$ -réguliers a été prouvée dans [51].
- Bornes de forçage nul : Plusieurs inégalités reliant les nombres de forçage nul ( $Z, Z_t, Z_+$ ) aux paramètres de domination et d'indépendance ont été conjecturées et prouvées, incluant $Z(G) \le \beta(G)$ pour les graphes sans griffe et des bornes pour les graphes cubiques.
- Problèmes ouverts : Le système a identifié la conjecture $Z(G) \le \alpha(G) + 1$ pour les graphes connexes avec $\Delta \le 3$ , qui reste un problème ouvert central, bien que des résultats partiels existent.

Signification et affirmations
L'article positionne TxGraffiti non pas comme un outil pour découvrir des théorèmes profonds de manière autonome, mais comme un générateur de preuves structuré qui facilite l'enquête mathématique humaine.

Validité empirique : Le système produit des énoncés « vrais dans le tableau », ce qui signifie qu'ils tiennent pour toutes les instances dans l'instantané curaté. Les auteurs réservent explicitement le terme « théorème » aux énoncés établis par une preuve formelle, distinguant la sortie du système comme des conjectures.
Position philosophique : Faisant écho à la perspective empirique de Fajtlowicz (qui a conçu Graffiti), l'article soutient que la capacité des machines à produire des conjectures plausibles et profondes est un fait empirique qui étaye la vision des machines comme des participants significatifs dans la découverte mathématique ouverte.
Évolutivité et reproductibilité : En traitant le tableau d'instantané comme un artefact versionné et auditable, TxGraffiti répond aux problèmes de robustesse liés à la corruption des données et garantit que les conjectures peuvent être reproduites et affinées à mesure que la base de preuves s'étend.

Les auteurs concluent que, bien que l'implémentation actuelle se concentre sur les invariants de graphes, le « paradigme du tableau d'instantané » et le pipeline d'optimisation et de filtrage sont largement applicables à tout domaine où les objets admettent des caractéristiques et des prédicats calculables.