New lower bound constructions for the cap set problem
FunSearch discovered larger cap sets than any previously known construction, the first time an LLM-based system produced a genuinely new discovery on an established open problem.
- Model
- FunSearch (PaLM 2 / Codey)
- Field
- Mathematics
- Date
- 2023-12-14
- Problem posed
- 1970 · open 53 yrs
Sources
Original work
Announcement
What was found
FunSearch pairs an LLM that proposes programs with an automated evaluator that rejects incorrect ones, sidestepping hallucination by construction. Applied to extremal combinatorics, it found new large cap sets in both finite-dimensional and asymptotic cases. Published in Nature. Historically the first entry in this registry's scope.
Novelty check
Cap set bounds are a well-tracked literature; the constructions were confirmed to exceed the standing record at publication.
Caveats and known objections
The LLM proposes; a human-designed evaluator and search loop does the selecting. Calling this 'the AI discovered it' overstates the model's role, though the discovery is real.
Nobody outside the lab has checked this yet.
Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Peer reviewed and Search scaffold.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Community discussion
Graded peer reviewed for verification and search scaffold for autonomy. What these mean.
Cite this entry
whataifound.org. (2023). New lower bound constructions for the cap set problem. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2023-12-funsearch-capsetBibTeX
@misc{whataifound-googledeepmind-2023-capset,
title = {New lower bound constructions for the cap set problem},
author = {{whataifound.org}},
year = {2023},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Google DeepMind. Verification: Peer reviewed. Autonomy: Search scaffold.},
url = {https://whataifound.org/finding/2023-12-funsearch-capset}
}