PatternBoost: Constructions in Mathematics with a Little Help from AI

François Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, Geordie Williamson
11/1/2024
math.COcs.LG

No official code found. Best implementation: zawagner22/transformers_math_experiments (40 stars, last commit 2024-10-16).

Abstract

We introduce PatternBoost, a flexible method for finding interesting constructions in mathematics. Our algorithm alternates between two phases. In the first ``local'' phase, a classical search algorithm is used to produce many desirable constructions. In the second ``global'' phase, a transformer neural network is trained on the best such constructions. Samples from the trained transformer are then used as seeds for the first phase, and the process is repeated. We give a detailed introduction to this technique, and discuss the results of its application to several problems in extremal combinatorics. The performance of PatternBoost varies across different problems, but there are many situations where its performance is quite impressive. Using our technique, we find the best known solutions to several long-standing problems, including the construction of a counterexample to a conjecture that had remained open for 30 years.

View on arXivView PDF

Code Implementations(1)

zawagner22/transformers_math_experimentsCommunity100%
4018Julia, PythonMay 9, 20242 years ago

Similar Papers

From Black Box to Bijection: Interpreting Machine Learning to Build a Zeta Map Algorithm

80% match2025

Finding Clustering Algorithms in the Transformer Architecture

79% match2025

Using Reasoning Models to Generate Search Heuristics that Solve Open Instances of Combinatorial Design Problems

78% match2025

Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics

78% match2025

Simulation of Graph Algorithms with Looped Transformers

78% match1 repo52026

Discovering Algorithms with Computational Language Processing

78% match1 repo2025

Cite this paper

@article{charton2024patternboost,
  title  = {PatternBoost: Constructions in Mathematics with a Little Help from AI},
  author = {François Charton and Jordan S. Ellenberg and Adam Zsolt Wagner and Geordie Williamson},
  year   = {2024},
  eprint = {2411.00566},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2411.00566v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2411.00566.svg)](https://codeofpaper.com/paper/2411.00566)

Discussion