No algorithm for fractions

0:00The question: fractions and algorithms

Result 004 in OpenAI’s math repository claims to settle a question that has been open for more than fifty years. Take any polynomial equation with whole-number coefficients. Is there an algorithm that can always tell you whether it has a solution in fractions? The claim is no. No computer program, however clever, can decide that for every equation. Most experts expected that answer. What nobody had was a way to prove it. To see why it’s hard, start with the version Hilbert actually asked.

0:32Hilbert’s tenth problem

In 1900, David Hilbert listed 23 problems for the new century. The tenth asks for a process that decides, in finitely many steps, whether a Diophantine equation has a solution in whole numbers. The answer took seventy years, and it was no. Martin Davis, Hilary Putnam and Julia Robinson, and finally Yuri Matiyasevich in 1970, showed that equations can imitate computer programs. Here’s a tiny example. A number n is composite exactly when (x + 2)(y + 2) = n for some whole numbers x and y that are zero or more. Their theorem says every listable set, even the set of programs that eventually halt, can be described by an equation like this. No algorithm decides which programs halt, so none decides which equations have whole-number solutions.

1:26Whole numbers versus fractions

Now allow fractions. Some equations gain solutions. x² + y² = 2 has the obvious point (1, 1), but also (1/5, 7/5), and infinitely many more. Others have none at all. x² + y² = 3 has no fraction solution: clear the denominators, and a short argument modulo three rules it out. And x³ + y³ = 6 has no whole-number solution, but it does have a fraction solution: x = 17/21 and y = 37/21. Searching through fractions finds a solution if there is one, but it can never certify that there is none. For fractions, whether some cleverer algorithm exists stayed open, and it became one of the best known open problems in the field.

2:15The obvious route, and the wall

The natural plan is to reuse the whole-number answer. Find one equation that has a fraction solution exactly when its first unknown is a whole number. Then every question about whole numbers becomes a question about fractions. Logicians came close. In 1949, Julia Robinson pinned down the integers inside the rationals with a formula that uses ’for all’ as well as ’there exists’. Later, Poonen and Koenigsmann found new formulas that switch less often between ’for all’ and ’there exists’. But an equation can only say ’there exists’. And a conjecture of Barry Mazur, about the shape of rational points, predicts that no equation can single out the integers. If he’s right, the natural plan is a dead end.

3:02The theorem

Here’s what result 004 claims. There is no algorithm which, given a polynomial with integer coefficients in any number of variables, decides whether it has a rational zero. It claims more: even for equations of degree at most four, deciding whether a fraction solution exists is exactly as hard as the halting problem. And it gets there without the forbidden equation. The paper says plainly that it gives no equation for the integers. Mazur’s conjecture is untouched.

3:34The detour: endless checklists

So how does it work? Instead of one equation, the paper builds an endless list of checklists. Each checklist is one finite list of conditions, and it passes if fractions can meet all of them at once. The key fact it proves: a whole-number equation has a whole-number solution exactly when every checklist passes. Now imagine a machine that decides fraction equations. Run two searches side by side. One tries whole-number inputs. The other uses the machine to hunt for a checklist that fails. Exactly one of the two must stop. So the machine would decide whole number equations, which the 1970 theorem showed is impossible. No such machine can exist.

4:16Counting on an elliptic curve

What do the checklists test? Whole numbers become steps along an elliptic curve. The number n becomes the point nP, and adding numbers means adding points. But multiplying numbers has no matching move on the curve, and that’s the hard part. The paper’s curve uses numbers of the form a + b√2, written as pairs of fractions. Points like these grow fast. On the simpler curve shown here, the denominator of the x-coordinate of nP grows roughly like n²: 1 digit, 3, 5, 8, 15, 21. The hard direction is the converse: with no whole-number solution, some checklist must fail. So the paper imagines a world where every checklist passes anyway. There, the tests, checked prime by prime and fed into a size bound, cap every quantity at about the solution’s size, B, while the curve forces the points to grow like B². Both can hold only if B stays small, so the solution was a genuine whole-number solution all along.

5:18Where the curves come in

One ingredient of every test controls denominators. It asks for rational points on curves like y² = x(x − l)(x + 3l). A classic method called 2-descent gives a promise, a Selmer class, that a point might exist. But a promise isn’t a point. To turn the promise into a point, the paper relies on its companion, a 91-page paper on elliptic curves, or alternatively on result 006. For l equal to eleven, a computer finds the point (75, 720). For the paper’s enormous values of l, only the theorem can. Another step, a size bound built from Shimura curves, relies on a third new paper from the same release: Fontaine–Mazur modularity at the prime two, part of result 010.

6:10Why it matters, and the caveats

If it all holds, this settles the most famous open version of Hilbert’s tenth problem, with the answer most people expected, by a route that goes around the obstacle everyone knew about. The caveats. This is a preprint, not peer reviewed, and there is no computer-checked Lean proof. It leans on two other new, unreviewed papers from the same release. A serious gap in any of them could sink the claim, unless another paper can fill it. And questions remain: can an equation single out the integers? Are equations with a few variables decidable? No algorithm for fractions, if the proof holds.