Buffio.

A field journal of machine-made science

← All discoveries

Mathematics · 14 December 2023

New cap-set constructions, written as programs

FunSearch discovered new constructions of large cap sets, including a cap set of size 512 in eight dimensions and an improved asymptotic lower bound — reported as the first discoveries on established open problems in mathematics made with large language models.

Field
Mathematics
Date
14 December 2023
AI system
FunSearch
Institution
Google DeepMind, with the University of Wisconsin–Madison
Published in
Nature
Identifier
10.1038/s41586-023-06924-6

The cap set problem asks for the largest set of points in a high-dimensional grid such that no three lie on a line. It is a central question in extremal combinatorics; Terence Tao has called it a favorite open problem. FunSearch, published in Nature on 14 December 2023, pairs a pretrained large language model with an automated evaluator that scores programs, then evolves those programs until they produce better solutions.

Applied to cap sets, FunSearch found constructions larger than those previously known, including a cap set of 512 vectors in eight dimensions. By searching in the space of programs rather than lists of points, the authors also obtained an improved lower bound on the cap set capacity. The paper describes this as the largest improvement in 20 years to the asymptotic lower bound, raising it to 2.2202. The work was done with Jordan Ellenberg of the University of Wisconsin–Madison.

The same method produced new heuristics for the online bin-packing problem that improved on widely used baselines such as first fit and best fit. Because FunSearch outputs programs, the solutions can be inspected, not only executed — a property the authors argue makes the findings more useful to mathematicians than a bare list of numbers.