Donald Knuth is not the kind of person who gets stumped easily. The Stanford computer science professor wrote The Art of Computer Programming — a multi-volume reference so exhaustive that Bill Gates once said, "If you think you're a really good programmer, read Knuth's Art of Computer Programming... You should definitely send me a résumé if you can read the whole thing." He invented TeX. He pioneered the analysis of algorithms as a formal discipline. He is, to most of the computing world, a living legend.
So when Knuth spent several weeks on a directed graph decomposition conjecture and couldn't find a general solution, it was safe to call the problem hard.
The problem came from his own ongoing work in combinatorics and graph theory. Specifically, it involved a directed graph with m³ vertices labeled (i, j, k) — a three-dimensional grid where each coordinate runs from 0 to m-1. From every vertex, exactly three arcs leave. The challenge: decompose all these arcs into exactly three Hamiltonian cycles, where each Hamiltonian cycle visits every vertex exactly once before returning to the start.
Knuth had solved it for m=3 — a 3×3×3 grid with 27 vertices. His colleague Filip Stappers had empirically verified solutions for grids up to 16×16×16. But no one had found a general construction that provably worked for any odd value of m. That's where things sat — until a colleague asked Claude Opus 4.6 to take a look.
What happened next became a case study in what AI-assisted mathematical reasoning actually looks like — messy, iterative, and ultimately productive. Across 31 guided explorations over roughly one hour, Claude made a critical insight: it independently recognized the problem's underlying structure as a Cayley digraph from group theory. This reformulation unlocked the path to a general solution. Knuth then supplied the rigorous mathematical proof, writing up the formal paper himself. He titled it "Claude's Cycles." His opening words: "Shock! Shock!"
Read the full analysis and implications for AI-assisted research: Claude Opus 4.6 Cracked a 30-Year Math Problem — Full Article
Top comments (0)