À la recherche des nombres de Schur avec des LLMs
Time: 14:00 -- Location: bat 650, 445
summary: Notre but est d’améliorer les bornes inférieures des nombres de Schur. Le nombre de Schur S(k) est le plus
grand entier N tel qu’il existe une façon de colorier les entiers {1, ..., N } avec k couleurs sans qu’il existe
trois entiers a, b, c de même couleur vérifiant a + b = c. Les valeurs exactes ne sont connues que pour k ≤ 5,
S(5) = 160 ayant été prouvé en 2018 (Heule, 2018) par une approche SAT dont le certificat dépasse 2 TB.
Au-delà, aucune méthode exhaustive n’est envisageable. Les meilleures bornes inférieures connues reposent
sur des constructions utilisant des S-templates, qui permettent d’établir des relations de récurrence entre les
S(k) (Ageron et al., 2022).
AlphaEvolve (Novikov et al., 2025) est la méthode sur laquelle repose notre approche évolutionnaire. À
chaque itération, le LLM reçoit quelques-unes des meilleures heuristiques de la population et doit en produire
une nouvelle, contrainte à travailler dans l’espace des S-templates.
Nous explorons deux approches au sein d’AlphaEvolve :
• La première consiste à assigner une couleur à chaque entier de 1 à N dans l’ordre, en suivant l’heuristique
que le LLM a affinée au fil des cycles. La plus grande partition valide construite par cette heuristique
fournit alors un score N.
• La seconde est une approche SAT visant à faire évoluer l’espace de recherche en demandant au LLM de
proposer de nouvelles contraintes structurelles. Les instances sont ensuite résolues avec PySAT. Le score
attribué à une heuristique est alors le temps de résolution des instances ou la plus grande partition valide
obtenue.
AlphaEvolve a déjà permis d’améliorer des bornes dans des problèmes combinatoires proches, ce qui
motive notre recherche.
Translations: en