FunSearch produces new results on open mathematics problems

Background

On 14 December 2023, Nature published FunSearch together with results on two problems^[1]. The first was the cap set problem, described in the paper as a central question in extremal combinatorics^[1]. Extremal combinatorics studies how large a structure can be while avoiding certain forbidden patterns, and the cap set problem is one of its central questions^[1]. The second problem was online bin packing, an algorithmic problem with practical scheduling uses^[1]. In an online problem, decisions must be made as inputs arrive, without knowing what will come later; bin packing concerns placing items into bins under capacity limits^[1]. These two problems differ in character: one is a mathematical question about extremal structure, the other an algorithmic scheduling problem^[1]. That difference matters because the same search method was applied to both^[1].

What happened

The headline result is comparative: in both cases the search produced results better than the best previously known^[1]. FunSearch is not presented as a direct solver that outputs one answer and stops. Unlike most computer search approaches, it does not search over candidate solutions directly^[1]. The title of the paper describes the approach as program search with large language models^[1]. So the object being searched is a program or procedure, not a single candidate answer^[1]. The authors conclude that it is possible to make discoveries on established open problems with LLMs^[1].

Key details

The distinction between searching solutions and searching programs is the key detail^[1]. If a method searches candidate solutions directly, each candidate is an answer to the problem^[1]. If it searches programs, each candidate is a procedure that can produce or check answers^[1]. The paper states the negative side clearly: FunSearch does not search over candidate solutions directly^[1]. The paper's title supplies the positive description: program search with large language models^[1]. A program can be run repeatedly, inspected, and adapted, while an answer is a single object; the unit of search therefore shifts from answer to reusable procedure^[1]. This is why the method can be discussed as a search over programs rather than over a list of answers^[1].

Why it matters

The results matter because they are better than the previous best on both problems^[1]. They also matter because of the authors' conclusion: discoveries on established open problems are possible with LLMs^[1]. That conclusion is narrower than a claim that LLMs solve mathematics in general^[1]. It is tied to the two problems reported with the paper^[1]. Still, it gives a concrete case in which a computer search built around an LLM was used on problems that were already established as open questions^[1]. The significance is therefore both specific and methodological: specific because the comparison is against the best previously known results on cap set and online bin packing, and methodological because the search operates on programs rather than directly on solutions^[1].