Donald Knuth Names Paper After Claude AI That Solved His Open Math Problem

Donald Knuth Names Paper After Claude AI That Solved His Open Math Problem

Don Knuth, widely regarded as the father of algorithm analysis, published a paper titled "Claude's Cycles" documenting a breakthrough that has captivated the AI and mathematics communities.

The Problem

The conjecture involved decomposing directed graphs into Hamiltonian cycles. Specifically, the challenge was finding a general construction rule for partitioning the vertex set of an m-cubed-vertex directed graph into three Hamiltonian cycles of length m-cubed for all odd m greater than 2.

Knuth had solved the 3x3x3 case and verified solutions computationally up to 16x16x16 grids, but no general construction existed that worked for all odd dimensions.

How Claude Solved It

Knuth's colleague Filip Stappers fed the problem to Claude Opus 4.6 and ran 31 guided explorations over roughly one hour. Claude tried brute-force searches, invented what it called "serpentine patterns," hit dead ends, changed strategies, and eventually found a working construction.

The key breakthrough came when Claude independently recognized the problem's underlying structure as a Cayley digraph from group theory.

Important Context

The process required human guidance throughout. Claude did not solve the problem autonomously from a single prompt. Knuth read the output, verified the construction, and wrote the rigorous mathematical proof himself.

Knuth's Response

Knuth closed the paper by writing that he would have to revise his opinions about generative AI. The paper received 635,000 views and 6,000 likes within hours of publication.