# Five puzzles AI could crack next Date: 2026-10-29 Author: Richard Brooks Canonical: https://richard-brooks.com/five-puzzles-ai-could-crack-next/ On Tuesday I wrote about [two machines breaking the same rule on the same day](/two-machines-broke-the-same-rule/). Let's do a thought experiment. If AI can knock down a 27-year-old hypothesis in computer science, what might it do next? Nobody knows, and anyone who claims to is guessing. But the problems AI has cracked so far share a shape. [Quanta Magazine looked at the Erdős problems](https://www.quantamagazine.org/why-the-legendary-erdos-problems-are-falling-to-ai-20260803/) falling to AI this year and found they come mainly from [number theory](https://en.wikipedia.org/wiki/Number_theory), [combinatorics](https://en.wikipedia.org/wiki/Combinatorics) and [graph theory](https://en.wikipedia.org/wiki/Graph_theory), where a problem fits in a sentence and an answer can be checked. In May an unreleased OpenAI model disproved a [1946 conjecture](https://www.quantamagazine.org/why-the-legendary-erdos-problems-are-falling-to-ai-20260803/) of [Paul Erdős](https://en.wikipedia.org/wiki/Paul_Erd%C5%91s) about [how many pairs of points on a flat surface can sit exactly one unit apart](https://en.wikipedia.org/wiki/Unit_distance_graph). So I picked five famous open problems with that shape. Each can be explained over a coffee. Each has beaten the best mathematicians for decades. And each tells us something about what AI is good at, and what it isn't. ## Why does AI find some problems easier than others? There are two ways to close a maths problem. One is to produce something: an example, a [counterexample](https://en.wikipedia.org/wiki/Counterexample) or a faster recipe. The other is to prove that a statement holds for every case, for ever. The first kind is where AI has done best, because a computer can check the answer in seconds. [ETH](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) fell this way. Both labs produced a faster method, and [Lean](https://lean-lang.org/) confirmed it worked. The second kind usually needs a new idea about why something is true, and that's far harder to find and to check. The first two puzzles below are mostly of the first kind. The last three are of the second. ## 1. How big does a party need to be? Six people turn up at a party. Any two of them have either met before or are strangers. However the friendships fall, the party will always contain at least one of these: - three people who all know each other, or - three people who are all strangers to each other. If everyone already knows everyone, that's easy. Any three of them are a trio of friends. If nobody knows anybody, it's just as easy. Any three are a trio of strangers. The surprise is the mixed party, where some pairs know each other and some don't. It seems as if a careful mix should avoid both kinds of trio. With six people, it can't. Every possible mix of friends and strangers still produces at least one trio. Mathematicians call this the [theorem on friends and strangers](https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers). Why six? Any guest, say Anna, has five other people in the room, and each is either a friend of hers or a stranger. When five people split into two groups, one group always has at least three in it. If three of them are her friends, there are only two possibilities. If any two of those three know each other, that pair and Anna are a trio of friends. If none of them know each other, those three are a trio of strangers. Either way, the trio is there. The same argument works if three of them are strangers to her. Five guests aren't enough. If five people sit round a table and each knows only the two people beside them, no three of them all know each other, and no three are all strangers. So six is the smallest party that guarantees a trio. Mathematicians write this as [R(3, 3) = 6](https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers), where R stands for [Frank Ramsey](https://en.wikipedia.org/wiki/Frank_P._Ramsey), the Cambridge mathematician whose 1930 paper started this field.
Figure 1

Six guests always produce a trio

Each line is a pair of guests. Each replay deals out a new random set of friendships, and a trio of friends or strangers turns up every time.
This is [Ramsey theory](https://en.wikipedia.org/wiki/Ramsey%27s_theorem), and the numbers get harder very quickly once the group gets bigger. To guarantee four people who all know each other, or four who are all strangers, you need 18 guests. That was [proved in 1955](https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Small_Ramsey_numbers). To guarantee five, nobody knows how many guests you need. In 1989 [Geoffrey Exoo found a way](https://arxiv.org/abs/2212.12630) to arrange friendships among 42 guests with no group of five friends and no group of five strangers, so 42 isn't enough. In 2024 [Vigleik Angeltveit and Brendan McKay proved](https://arxiv.org/abs/2409.15709) that 46 guests always produce one. So the answer is 43, 44, 45 or 46, and nobody has been able to narrow it further. Erdős liked to [tell a story about this](https://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers). If aliens arrived and threatened to destroy Earth unless we told them the answer for groups of five, he said, we should put every computer and mathematician on it. If they asked for groups of six, we should try to destroy the aliens instead. Why do I think AI has a chance here? Because this is search on a colossal scale, the same family of problem as [3-SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem), the puzzle at the heart of [Tuesday's essay](/two-machines-broke-the-same-rule/). Among 43 guests there are 903 pairs, and 2 to the power 903 ways to arrange friendships between them. Computers have settled a cousin of this problem before: the [Boolean Pythagorean triples problem](https://en.wikipedia.org/wiki/Boolean_Pythagorean_triples_problem) fell to a [SAT solver](https://en.wikipedia.org/wiki/SAT_solver) in 2016, with a proof 200 terabytes long. A cleverer search, or a cleverer argument to cut the search down, is exactly what AI has been producing this year. This is the one I'd put at the top of the list. ## 2. What's the fastest way to multiply two tables of numbers? Multiplying tables of numbers, called [matrices](https://en.wikipedia.org/wiki/Matrix_multiplication), sits underneath almost everything a computer does with AI. The schoolbook method for two 2 by 2 tables takes eight multiplications. In 1969 [Volker Strassen](https://en.wikipedia.org/wiki/Volker_Strassen) [found a way](https://en.wikipedia.org/wiki/Strassen_algorithm) to do it in seven. With his trick used twice, two 4 by 4 tables take 49 multiplications instead of 64. That record stood for 56 years. In May 2025 [Google DeepMind](https://en.wikipedia.org/wiki/Google_DeepMind)'s [AlphaEvolve](https://en.wikipedia.org/wiki/AlphaEvolve) [found a way to do it in 48](https://www.theregister.com/2025/05/15/google_deepmind_debuts_algorithm_evolving/), for tables of [complex numbers](https://en.wikipedia.org/wiki/Complex_number).
Figure 2

Multiplying two 4 by 4 tables

Each block is one multiplication. One block saved sounds tiny, but recipes like these are applied billions of times, inside larger and larger tables.
The big open question is [how the cost grows](https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms) as tables get huge. The schoolbook method grows with the cube of the table size. The best known method, from [a 2024 paper by Josh Alman and colleagues](https://arxiv.org/abs/2404.16349), grows with the size to the power of about 2.371. Nobody knows whether it can reach 2, the floor set by having to read every number at least once. Why AI? Every new recipe can be checked by a computer in seconds, and AI already holds one of the records. There's also a neat loop in it. A faster recipe for multiplying matrices makes AI itself faster. ## 3. Is every even number the sum of two primes? In 1742 [Christian Goldbach](https://en.wikipedia.org/wiki/Christian_Goldbach) wrote to [Leonhard Euler](https://en.wikipedia.org/wiki/Leonhard_Euler) with a guess. Every even number above 2 is the sum of two primes. 4 is 2 plus 2. 28 is 5 plus 23. 100 is 3 plus 97, among others. [Goldbach's conjecture](https://en.wikipedia.org/wiki/Goldbach%27s_conjecture) has been checked by computer for every even number up to [4 million million million](https://www.ams.org/journals/mcom/2014-83-288/S0025-5718-2013-02787-1/), and in 2013 [Harald Helfgott](https://en.wikipedia.org/wiki/Harald_Helfgott) [proved a weaker version](https://arxiv.org/abs/1312.7748) for odd numbers and three primes. The original is still open after 284 years.
Figure 3

Goldbach's comet

Each dot is an even number up to 2,000, plotted against how many ways it splits into two primes. The cloud rises and drifts away from zero. A single dot on the bottom line would disprove Goldbach.
The picture makes the conjecture look almost obvious, but checking more numbers proves nothing about the numbers we haven't checked. A proof has to explain why the comet can never touch zero, for every even number there will ever be. That needs a new idea in number theory. If AI helps here, it will be by finding that idea, which is a much bigger step than anything we've seen so far. ## 4. Do twin primes go on for ever? Earlier this week a post about [Stanisław Ulam](https://en.wikipedia.org/wiki/Stanis%C5%82aw_Ulam)'s [prime spiral](https://en.wikipedia.org/wiki/Ulam_spiral) went round, showing primes lining up on diagonals in a way nobody fully understands. Twin primes are a puzzle from the same family. Twin primes are pairs of primes two apart, like 11 and 13 or 41 and 43. Primes get rarer as numbers grow, yet twins keep turning up. The [twin prime conjecture](https://en.wikipedia.org/wiki/Twin_prime) says they never stop.
Figure 4

Primes up to 120, with the twins joined

Each tick is a prime. Each arc joins a twin pair. The ticks thin out along the lines, yet the arcs keep appearing.
In 2013 [Yitang Zhang](https://en.wikipedia.org/wiki/Yitang_Zhang), then a little-known lecturer at the [University of New Hampshire](https://en.wikipedia.org/wiki/University_of_New_Hampshire), proved that infinitely many pairs of primes sit within 70 million of each other. Within a year, [James Maynard](https://en.wikipedia.org/wiki/James_Maynard_(mathematician)) and an online collaboration led by [Terence Tao](https://en.wikipedia.org/wiki/Terence_Tao), called [Polymath](https://arxiv.org/abs/1409.8361), had cut the gap to 246. Getting from 246 down to 2 is the whole conjecture, and experts think today's methods can't get below 6 even under optimistic assumptions, because of a known obstacle called the [parity problem](https://en.wikipedia.org/wiki/Parity_problem_(sieve_theory)). Polymath is the interesting precedent for AI. Many minds chipped away at a number in public, each improvement checked by the next person. That's a way of working AI is well suited to. But the last step from 6 to 2 needs something new, and nobody yet knows what. ## 5. Does every number end up at 1? This is the simplest rule in the list. It starts from any whole number. An even number is halved. An odd number is tripled, and then one is added. The same rule then applies to the answer, over and over. The [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture), set by [Lothar Collatz](https://en.wikipedia.org/wiki/Lothar_Collatz) in 1937, says you always end up at 1. Most numbers get there quickly. Some take an astonishing detour.
Figure 5

The long way home for 27

Start at 27 and the sequence climbs to 9,232 before collapsing to 1, 111 steps later. Its neighbour 26 gets there in ten.
In 2025 David Barina [checked every starting number up to 2 to the power 71](https://link.springer.com/article/10.1007/s11227-025-07337-0), about 2.4 thousand billion billion, and every one reached 1. In 2019 Terence Tao [proved that almost all numbers](https://arxiv.org/abs/1909.03562) get close to 1, which is as near as anyone has come. Erdős said of it that ["mathematics may not be ready for such problems"](https://en.wikipedia.org/wiki/Collatz_conjecture). This is the one I'd bet against AI cracking soon. A counterexample would be a number that climbs for ever or gets stuck in a loop, and the search up to 2 to the power 71 has found nothing. A proof needs mathematics that may not exist yet. ## Which would I bet on? The party problem and the matrix recipes. Both reward enormous search, and both produce answers a computer can check in seconds. That's the same shape as ETH, and it's where AI has already shown it can beat people. The three number theory problems are different. They need proofs about every number there is, and AI's progress there so far has come from tightening methods humans invented. None of the five is a [Millennium Prize problem](https://www.claymath.org/millennium-problems/), and [P vs NP](https://www.claymath.org/millennium/p-vs-np/) is still open too. I'd be cautious of anyone this week claiming otherwise. The pattern I take into my own work is the one I [wrote about on Tuesday](/two-machines-broke-the-same-rule/). The problems AI takes first are the ones where the answer can be checked cheaply. Which of our own business problems come with a checker like that? And for the ones that don't, who does the checking? ## Sources - Quanta Magazine (2026) [Why the legendary Erdős problems are falling to AI](https://www.quantamagazine.org/why-the-legendary-erdos-problems-are-falling-to-ai-20260803/) - Angeltveit, V. and McKay, B. D. (2024) [R(5, 5) ≤ 46](https://arxiv.org/abs/2409.15709) - Wikipedia [Ramsey's theorem](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) and [Boolean Pythagorean triples problem](https://en.wikipedia.org/wiki/Boolean_Pythagorean_triples_problem) - Wikipedia [Strassen algorithm](https://en.wikipedia.org/wiki/Strassen_algorithm) - The Register (2025) [Google DeepMind debuts algorithm-evolving AI](https://www.theregister.com/2025/05/15/google_deepmind_debuts_algorithm_evolving/) - Alman, J. et al. (2024) [More asymmetry yields faster matrix multiplication](https://arxiv.org/abs/2404.16349) - Oliveira e Silva, T., Herzog, S. and Pardi, S. (2014) [Empirical verification of the even Goldbach conjecture up to 4·10¹⁸](https://www.ams.org/journals/mcom/2014-83-288/S0025-5718-2013-02787-1/) - Helfgott, H. A. (2013) [The ternary Goldbach conjecture is true](https://arxiv.org/abs/1312.7748) - Polymath (2014) [The "bounded gaps between primes" Polymath project: a retrospective](https://arxiv.org/abs/1409.8361) - Barina, D. (2025) [Improved verification limit for the convergence of the Collatz conjecture](https://link.springer.com/article/10.1007/s11227-025-07337-0) - Tao, T. (2019) [Almost all orbits of the Collatz map attain almost bounded values](https://arxiv.org/abs/1909.03562) - Clay Mathematics Institute [Millennium Prize problems](https://www.claymath.org/millennium-problems/)