FunSearch: an LLM finds new cap-set constructions, the first LLM discovery in open maths
FunSearch (Nature, Dec 2023) paired a code LLM with an automated evaluator in an evolutionary loop. It found a cap set of size 512 in dimension 8 (previous best 496) and better lower bounds on the asymptotic cap-set capacity. It also found bin-packing heuristics beating first-fit and best-fit.
Key facts
- Cap set in F_3^8 of size 512, beating the previous record of 496
- Improved lower bound on cap-set capacity via new admissible sets
- Outputs are programs, so humans can read how the construction works
- Co-author: mathematician Jordan Ellenberg
Science result
- Field
- mathematics / extremal combinatorics
- Problem
- Cap set problem: largest subsets of F_3^n with no three points on a line
- Result
- Largest known cap set in dimension 8 (512 vs 496) and improved capacity lower bound.
- AI system
- FunSearch (PaLM 2 / Codey)
- Human role
- Humans wrote program skeleton and evaluator; LLM-driven search autonomous
- Verification
- Peer-reviewed in Nature; constructions verified computationally
- Status
- confirmed
- Why surprising
- First time an LLM-based system produced a verifiably new result on a well-known open combinatorics problem.
What happened
DeepMind evolved short Python programs that construct cap sets, with an LLM proposing program mutations and a scorer keeping the best.
Why it matters
It was the direct ancestor of AlphaEvolve and showed that LLMs' mistakes don't matter when outputs can be automatically checked.
Changelog
- 2026-09-29: created
Related events
- AlphaEvolve: Gemini-powered agent discovers new algorithms ★★★★
- DeepMind and mathematicians use machine learning to guide new theorems in knot theory and representation theory ★★★
Sources (3)
- paperMathematical discoveries from program search with large language models (Nature)
- codeGitHub: google-deepmind/funsearch
- discussionErnest Davis: comment on FunSearch
id: 2023-12-14-funsearch-cap-sets · updated 2026-09-29 · open in the interactive timeline