On this page
In 1970 a 22-year-old in Leningrad, Yuri Matiyasevich, settled Hilbert's tenth problem by showing that no general method can decide whether a polynomial equation has whole-number solutions. Our post on David Hilbert's 23 problems tells that ending. This post is about the person who spent twenty years building the road to it, Julia Robinson: who she was, the idea she found in 1952, a worked example with the equation at the heart of the proof, and what students can learn from how she worked.
Who was Julia Robinson?
Her MacTutor biography gives her birth in St Louis on 8 December 1919 and her death in Berkeley on 30 July 1985. Her mother died when she was two. At nine she caught scarlet fever and then rheumatic fever, and missed two years of school; a private tutor then took her through four grades' worth of syllabus in a single year. At San Diego High School she was the only girl in her mathematics and physics classes.
She moved from San Diego State College to the University of California at Berkeley, where she married the mathematician Raphael Robinson in 1941. University rules then stopped her teaching in the mathematics department because her husband was on its staff. She went on to a doctorate under Alfred Tarski, with a thesis showing that the arithmetic of the rational numbers is undecidable.
Solomon Feferman's National Academy of Sciences memoir records that a doctor told her mother in 1941 that she would be lucky to live to forty. Heart surgery in 1961 changed that, and a month later she took up cycling.
What did Hilbert's tenth problem ask?
The memoir gives Hilbert's request: devise a process that decides, in a finite number of operations, whether a Diophantine equation is solvable in integers. Some cases are easy. 3x + 6y = 7 has no integer solution, because the left side is always a multiple of 3. Others are not. Hilbert wanted one method for every polynomial equation.
What was Robinson's own contribution?
The memoir says her work began with a question from Tarski: is the set of powers of 2 Diophantine, that is, describable by a polynomial equation with whole-number unknowns? In her 1952 paper Existential definability in arithmetic she showed that if any relation of roughly exponential growth is Diophantine, then exponentiation can be defined from it, and so can binomial coefficients and factorials.
Around 1960 she received a draft by Martin Davis and Hilary Putnam that relied on an unproved hypothesis about long runs of primes in arithmetic progression. She removed that assumption and simplified the arguments, which led to their joint 1961 paper The Decision Problem for Exponential Diophantine Equations in the Annals of Mathematics. It also stated the J. R. hypothesis: some relation of roughly exponential growth is Diophantine. By her 1952 results and the 1961 paper, that hypothesis alone would settle Hilbert's problem in the negative.
Matiyasevich proved it in 1970, using the even-indexed Fibonacci numbers and the Pell equation x² − (a² − 1)y² = 1, which Robinson had used in 1952. His MacTutor biography quotes him saying that her 1969 paper drew him back to the problem. The memoir quotes her congratulations to him: "If you really are 22, I am especially pleased to think that when I first made the conjecture you were a baby and I just had to wait for you to grow up."
Worked example: exponential growth from a Pell equation
Take a = 3 in the memoir's Pell equation, giving x² − 8y² = 1.
First solution. (3, 1): 9 − 8 = 1.
A rule for the next one. From a solution (x, y), the pair (3x + 8y, x + 3y) is again a solution. You can check this by expanding: (3x + 8y)² − 8(x + 3y)² = x² − 8y².
Next solutions. (17, 6): 289 − 288 = 1. (99, 35): 9801 − 9800 = 1. (577, 204): 332929 − 332928 = 1.
The growth. The ratios of successive x values are 17/3 ≈ 5.67, 99/17 ≈ 5.82 and 577/99 ≈ 5.83, settling near 3 + √8 ≈ 5.83. Each solution is about 5.83 times the last.
So a single polynomial equation of degree 2 has solutions that grow exponentially. Properties of exactly this kind of equation are what Robinson used in 1952 and Matiyasevich used in 1970.
What do students often misread?
"No algorithm" does not mean "no solutions". It means no single method works for every equation. Particular equations can still be solved.
Not every family is hard. The memoir notes that Carl Ludwig Siegel gave an algorithm for all equations of degree 2.
Checking is not proving. Step 3 checks three cases; step 2's algebra proves the rule for all of them.
What honours did she receive?
The memoir records that she was the first woman elected to the mathematical section of the National Academy of Sciences and the first woman president of the American Mathematical Society, for 1983 to 1984. She received a MacArthur Fellowship in 1983. MacTutor notes that she gave the Society's Colloquium Lectures in 1980, only the second woman to do so, and that she wished to be remembered for her theorems rather than for being the first woman to do something.
If number theory proofs leave you unsure where a step came from, the Fermi Problem Library has a step-by-step solver that explains the reasoning. For olympiad practice, see our guide to IOQM number theory questions.
What can a student take from Robinson's way of working?
Stay with a hard problem. She worked on it from 1948 until it was solved, and on its consequences after.
Turn a question around. In a 1971 lecture, MacTutor reports, she suggested asking which equations known methods can actually handle.
Be generous with credit. Her letter to Matiyasevich celebrated his proof rather than her near miss.
Next step: use the rule in step 2 to find the solution after (577, 204), then check that it satisfies x² − 8y² = 1.
