The cap set problem: FunSearch finds a larger cap set in dimension 8

A program search system driven by a large language model produced the largest known cap set in dimension 8 and improved the asymptotic lower bound. The problem itself remains open.

Problem
The largest possible size of a cap set in F3n\mathbb{F}_3^n
Credit
FunSearch (Google DeepMind) · LLM-guided program search with automatic evaluation
Checked
Peer reviewed (Nature, 2023)Construction can be checked directly
Timeline
AI construction published 2023-12
Sources
Nature paper
PARTIALImproved lower bound · new construction

The problem

A set of points in F3n\mathbb{F}_3^n is a cap set if it contains no three distinct points x,y,zx, y, z with x+y+z=0x + y + z = 0, that is, no three points on a line. The question is how large a cap set in nn dimensions can be.

In 2016, Ellenberg and Gijswijt proved that a cap set has at most roughly 2.756n2.756^n points. The exact maximum in a given dimension, and the true asymptotic growth rate, are still unknown.

What AI did

FunSearch does not output an answer directly. A large language model repeatedly rewrites a program that generates cap sets; an automatic evaluator scores and filters the results, and the better programs keep evolving. For n=8n = 8 it found a cap set of size 512, where the largest previously known had 496 points.

It also found a new family of constructions that raised the growth constant in the asymptotic lower bound from 2.2180 to 2.2202.

How it was checked

The construction is an explicit set of points: anyone can check in seconds, with a few lines of code, that no three of them are on a line. This is the easiest kind of AI result in mathematics to verify: you don't need to trust the model, only the check.

Limitations

The result improves a lower bound. It does not settle the exact maximum size of a cap set in dimension 8, and asymptotically there is still a wide gap between 2.2202 and 2.756. That is why this record is graded “partial”.

∎