New lower bound constructions for the cap set problem
New lower bound constructions for the cap set problem is graded peer reviewed on whataifound.org, with the AI's role graded search scaffold.
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.
- Verification
- Peer reviewed
- Autonomy
- Search scaffold
- Lab
- Google DeepMind
- Model
- FunSearch (PaLM 2 / Codey)
- Field
- Mathematics
- Date
- 2023-12-14
- Problem posed
- 1970 · open 53 yrs
- Notability
- 2 Wikipedia language editions
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
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.
Sources
Community discussion
How this is graded
whataifound.org grades every entry on two axes: verification (how solid the result is, from a machine-checked proof down to refuted) and autonomy (how much the AI did versus its human collaborators). This finding is peer reviewed and search scaffold. Full definitions are in the methodology.
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-capset