PatternBoost: Constructions in Mathematics with a Little Help from AI
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:BLKKEL6Urecord.jsonopen to challenge →
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 23 Pith papers
-
A combinatorial large sieve for Sidon sets, distances, and norm forms
A new combinatorial large sieve produces the first super-polylogarithmic upper bounds of the form N exp(-c log N / log log N) for Sidon sets in squares and no-repeated-distance sets in the grid.
-
Split primes and the Elekes-R\'onyai problem
Constructs sets A subset R with |{x+y+(x-y)^2 : x,y in A}| <= |A|^{2-c} for some c>0, giving a counterexample to the Elekes-Rónyai problem via prime-splitting amplification.
-
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
For every d >= 3 and n = k d with k >= 2, there exist directed d-regular graphs on n vertices whose random cycle-factors have expected cycle count strictly larger than k H_d, disproving the conjecture that the disjoin...
-
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
The paper disproves the conjecture that the disjoint union of complete looped digraphs uniquely maximizes expected cycle count in random cycle-factors of d-regular digraphs for d >= 3, via explicit constructions yield...
-
The Minkowski grid has robustly many repeated distances
There exist n-point planar sets where every subset A has a distance occurring ≥|A|²/n^{1−δ} times, confirming Erdős's 1980 isosceles-triangle conjecture and answering a repeated-distance question negatively.
-
Mathematical perspective on genetic algorithms with optimization guided operators
Presents a query-complexity framework for genetic algorithms with guided operators and shows necessity of multiple operators and tight bounds for diversity in solution pools.
-
An automated proof that R(B_8,B_10)=37
Proves R(B_8, B_10) = 37 via an AI-assisted short proof with a Lean formalization of the upper bound.
-
New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
LLM-reinforced evolutionary search produces exact values Z(11,21,3,3)=116, Z(11,22,3,3)=121, Z(12,22,3,3)=132 and lower bounds for 41 additional Zarankiewicz numbers.
-
Reconstructing conformal field theoretical compositions with Transformers
Transformers reconstruct the constituent RCFTs in tensor-product theories from low-energy spectra, reaching 98% accuracy on WZW models and generalizing to larger central charges with few out-of-domain examples.
-
Optimal and Near-Optimal Constructions for Bootstrap Percolation in Hypercubes
m(Q_d;4) equals d(d² + 3d + 14)/24 + 1 for infinitely many d, with an O(d)-additive upper bound for all d.
-
Generating Hadamard matrices with transformers
Transformer networks combined with local search generate many new inequivalent Hadamard matrices up to order 244 and exploit hidden symmetries in the search space.
-
Generating Hadamard matrices with transformers
Transformers combined with local search generate new Hadamard matrices up to order 252 by learning hidden symmetries in the combinatorial search space.
-
$k$-server-bench: Automating Potential Discovery for the $k$-Server Conjecture
k-server-bench formulates potential-function discovery for the k-server conjecture as a code-based inequality-satisfaction task; current agents fully solve the resolved k=3 case and reduce violations on the open k=4 case.
-
Generating Special Triangulations with Transformers
Transformers generate new FRSTs of 4D reflexive polytopes across size ranges and self-improve by retraining on their own outputs.
-
Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry
Geometry-aware MCTS with incremental constraint updates and symmetry pruning yields new best-known configurations for five of six tested combinatorial geometry problems, including ~1.8n points for Max-N3IL on grids 82-119.
-
Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools
New counterexamples to log-concavity of dominating-set sequences in trees and graphs are found via AI search, with a construction giving arbitrarily many violations and positive log-concavity results for caterpillar g...
-
SWE-Edit: Rethinking Code Editing for Efficient SWE-Agent
Decomposing the code editing interface into Viewer and Editor subagents raises SWE-Bench Verified resolve rate by 2.1 pp, cuts inference cost by 17.9%, and lets an 8B model reach parity with larger editors via GRPO training.
-
Mathematical exploration and discovery at scale
AlphaEvolve rediscovered best-known solutions for most of 67 tested math problems and found improved solutions in several cases using LLM-guided evolutionary search.
-
Split primes and the Elekes-R\'onyai problem
Constructs sets A subset R with |{x+y+(x-y)^2 : x,y in A}| <= |A|^{2-c} for some c>0, giving a counterexample to the Elekes-Rónyai problem.
-
Geometric Sidon Problems
Any point set P in R^2 has a subset P' with |P'| ≫ |P|^{1/3} in which all distances are distinct.
-
SWE-Edit: Rethinking Code Editing for Efficient SWE-Agent
SWE-Edit decomposes agent code editing into specialized subagents and adaptive editing modes, raising resolved rate 2.1% and cutting inference cost 17.9% on SWE-bench Verified while releasing a predictive editing benchmark.
-
Learning the symmetric group: large from small
Transformer trained on S10 permutation prediction from transpositions generalizes to S25 with near 100% accuracy using identity augmentation and partitioned windows.
-
AI for Mathematics: Progress, Challenges, and Prospects
AI for math combines task-specific architectures and general foundation models to support research and advance AI reasoning capabilities.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.