Large language models are being used to tackle combinatorics problems in mathematics, with potential applications in various fields.
The card game Set has long been a source of inspiration for mathematicians seeking to solve interesting problems. Now, a new technique utilizing large language models (LLMs) is demonstrating that artificial intelligence (AI) can assist mathematicians in generating novel solutions. The AI system, called FunSearch, has made significant progress in combinatorics, a branch of mathematics that focuses on counting the possible arrangements of sets with a finite number of objects. This groundbreaking method, described in a recent study published in Nature, has the potential to be applied to a wide range of mathematical and computer science questions.
FunSearch: A Mathematical Chatbot
FunSearch operates by creating requests for a specially trained LLM, prompting it to generate short computer programs capable of finding solutions to specific mathematical problems. The system then quickly evaluates whether these solutions are superior to existing ones. If not, it provides feedback to the LLM, enabling it to improve in subsequent iterations.
According to Bernardino Romera-Paredes, a computer scientist at DeepMind, FunSearch utilizes the LLM as a “creativity engine.” While not all programs generated by the LLM are useful, the system can swiftly discard incorrect ones and test the output of the correct programs.
Breaking New Ground: The Cap Set Problem
The FunSearch team tested their system on the “cap set problem,” which originated from the game Set, invented by geneticist Marsha Falco in the 1970s. Set consists of a deck of 81 cards, each displaying one, two, or three symbols that are identical in color, shape, and shading. With three possible options for each feature, the total number of possibilities is 3 × 3 × 3 × 3 = 81. Players must flip over the cards and identify special combinations of three cards called sets.
Mathematicians have determined that players are guaranteed to find a set if at least 21 cards are revealed. They have also discovered solutions for more complex versions of the game, where abstract versions of the cards possess five or more properties. However, certain mysteries remain, such as the minimum number of cards required to guarantee a solution when there are n properties, with n being any whole number.
This problem can be expressed in terms of discrete geometry, equivalent to finding specific arrangements of three points in an n-dimensional space. Mathematicians have established bounds on the general solution, determining that the required number of “cards on the table” must be greater than a certain formula but smaller than another.
Human-Machine Collaboration
FunSearch surpassed the lower bound for n = 8 by generating sets of cards that meet all the game’s requirements. Although the researchers do not prove that further improvements are impossible, they have achieved a construction that goes beyond existing knowledge.
One notable aspect of FunSearch is that it allows humans to examine the successful programs created by the LLM, offering an opportunity for learning and collaboration. This sets the technique apart from other AI applications, where the AI system remains a black box.
Co-author Jordan Ellenberg, a mathematician at the University of Wisconsin-Madison, emphasizes the potential for new modes of human-machine collaboration. He sees AI systems like FunSearch as force multipliers, augmenting the capabilities of human mathematicians rather than replacing them.
Conclusion:
The development of FunSearch, an AI system based on large language models, has demonstrated its potential to generate new mathematical solutions. By utilizing the LLM as a creativity engine, FunSearch has made progress in solving combinatorics problems, surpassing existing bounds in the cap set problem. The ability for human mathematicians to learn from the programs generated by FunSearch sets this technique apart from other AI applications. As AI continues to evolve, human-machine collaboration holds promise for advancing mathematical research and problem-solving in various fields.
