A Chatbot Cracked a Math Problem the Algorithms Built to Crack It Couldn't

Ask a chatbot for a proof and you brace for a confident, wrong answer. So there is a certain irony in what a team of four researchers reported this week: they asked a language model to help with a decades-old problem their own carefully engineered algorithms had failed to solve, and it handed back constructions that were not only correct but better than anything on record.

The problem lives in information theory, and it goes back to Claude Shannon. When you send messages over a noisy channel, some symbols can be confused for others at the far end. The Shannon capacity of a graph measures the maximum rate at which you can still communicate with zero error, given which symbols are confusable. For most graphs the exact capacity is unknown. Even for something as simple as an odd cycle (seven points in a ring, then eleven, then thirteen), the best mathematicians can do is squeeze the true value between an upper and a lower bound and try to narrow the gap.

Pushing the lower bound up means finding a large "independent set" inside a repeatedly multiplied version of the graph: a big collection of symbol sequences, no two of which can be confused for each other. The bigger the set you can exhibit, the higher the guaranteed rate. Finding these sets is a brutal combinatorial search, and it is exactly the kind of task computers are supposed to be good at.

That is what makes the new preprint, posted to arXiv on July 23 by Nathaniel Itty, Christopher D. Rosin, Chase Carstensen and Daniel Reichman, worth a second look. The authors had thrown the usual machinery at the problem (hand-built search heuristics, including simulated annealing, and an earlier AI-designed local-search program) and come up short over an extended effort. Then they tried something different: iterative back-and-forth with a language model, prompting it toward larger and larger constructions.

It worked. In the tenth power of the seven-cycle, the model produced an independent set of 134,753 sequences, enough to lift the lower bound on the Shannon capacity of C₇ above 3.258020. For the eleven-cycle it found a set of 21,909, and for the thirteen-cycle 62,530, improving the best-known bounds to more than 5.289773 and 6.300109 respectively. Each of those numbers beats what the field had before, according to the preprint.

Here is the part that matters most, and it is easy to skip past. These are not the model narrating a result and asking you to believe it. They are explicit objects: lists you can write down. To confirm the claim, you take the model's construction and check two things: that every sequence really is in the set, and that no two of them are confusable. A computer does that in moments, and the check does not care how the set was found. It could have come from a chatbot, a supercomputer, or a monk with infinite patience. If it passes, the bound holds.

That distinction, between discovering an answer and verifying it, is the whole story. A great deal of AI-for-science lands in a gray zone where a model reports something impressive and the evidence is the model's own say-so. This is the opposite. The hard, error-prone step is generating a candidate; the checking is cheap, mechanical and certain. So even though the work is a preprint and has not been through peer review, its central mathematical claim does not hinge on peer review in the usual way. The constructions either survive verification or they don't, and the authors have published them for anyone to test.

It also fits a pattern that has been building. Recent systems such as DeepMind's FunSearch and AlphaEvolve have used language models inside a search loop to find new mathematical constructions, precisely because construction problems reward a machine that can propose many creative candidates while a verifier keeps it honest. What is striking here is how direct the setup was: not an elaborate evolutionary pipeline but a researcher in conversation with a model, steering it toward better and better guesses.

None of this means a language model "understands" Shannon capacity, and the authors do not claim it does. The upper bounds on these cycles are untouched, so the exact capacities remain open. But for a specific, respected problem where the goal is to exhibit a better object than anyone has before, the model did exactly that, and left behind proof that survives inspection. In a field awash with claims you have to take on faith, a result you can check yourself is a rare and welcome thing.