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.
hub
PatternBoost: Constructions in Mathematics with a Little Help from AI
19 Pith papers cite this work. Polarity classification is still indexing.
19
Pith papers citing it
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.
hub tools
citation-role summary
background 4
citation-polarity summary
roles
background 4polarities
background 4representative citing papers
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.
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 disjoint union of K_d^circ maximizes it.
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.
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.
Proves R(B_8, B_10) = 37 via an AI-assisted short proof with a Lean formalization of the upper bound.
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.
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.
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.
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 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.
Transformers generate new FRSTs of 4D reflexive polytopes across size ranges and self-improve by retraining on their own outputs.
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.
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 graphs and a continuous analogue.
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.
AlphaEvolve rediscovered best-known solutions for most of 67 tested math problems and found improved solutions in several cases using LLM-guided evolutionary search.
Any point set P in R^2 has a subset P' with |P'| ≫ |P|^{1/3} in which all distances are distinct.
Transformer trained on S10 permutation prediction from transpositions generalizes to S25 with near 100% accuracy using identity augmentation and partitioned windows.
AI for math combines task-specific architectures and general foundation models to support research and advance AI reasoning capabilities.
citing papers explorer
-
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 disjoint union of K_d^circ maximizes it.
-
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
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 graphs and a continuous analogue.
-
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.
-
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.
-
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.