This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American
Julia Robinson was born on December 8, 1919. She was a brilliant mathematician, generous research collaborator, and kind human being who faced some trying circumstances with a great deal of grace. I wrote about her life and work for Science News in honor of her 100th birthday.
Most of Robinson’s research focused on decision problems: given a particular set of conditions, can one tell whether an arbitrary problem has a solution or not? Specifically, she spent much of her life studying Diophantine equations, polynomials with whole number coefficients, like x2+2xy-3y2=0. Some Diophantine equations have whole number solutions (in the above, there are many: x=3 and y=3 is one), and some do not.
Hilbert’s 10th problem, one of the challenges David Hilbert issued to the mathematics community in 1900, asked whether there was a universal algorithm that could look at any Diophantine equation and decide whether it had whole number solutions or not. In 1970, Russian mathematician Yuri Matiyasevich built on the work of Robinson did with two other American mathematicians, Martin Davis and Hilary Putnam, to show that no such algorithm could exist. In the limited space of my Science News article, I couldn’t include the serendipitous way the Fibonacci numbers fit into the ultimate solution of the problem, but it's a fun story, and I wanted to share it here.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
The Fibonacci sequence—0, 1, 1, 2, 3, 5, 8, 13, 21,…—is familiar to many math enthusiasts. Starting with the numbers 0 and 1, each term is the sum of the previous two terms. Fibonacci numbers and their cousin the golden ratio are a bit of a recreational math cliché. Frankly, I’m a bit tired of the Fibonacci spiral and Fibonacci numbers in pinecones. But seeing them pop up as part of the solution to Hilbert’s 10th problem, I felt like I was bumping into a familiar friend in a difficult setting.
In a charming article about working with Robinson, Matiyasevich writes about the search for equations that would produce sequences of numbers with specific properties as solutions. The solutions needed to have particular recurrence relations: later solutions were combinations of earlier solutions. Robinson, Davis, and Putnam had shown that finding such an equation would be sufficient to settle Hilbert’s 10th problem, and Robinson had zeroed in on finding an equation with the correct properties that would produce the powers of 2. But she couldn’t quite get there.
Matiyasevich showed that the Fibonacci numbers could work instead for a modified version of Robinson, Davis, and Putnam’s argument. Key to his proof was the following fact: If the square of the nth Fibonacci number divides the mth Fibonacci number, then the nth Fibonacci number divides m. (For this property to work, note that 0 is the 0th term of the Fibonacci sequence and 1 is the 1st term.) For example, the square of the 3rd Fibonacci number, 2, is 4 (so n is 3.) The number 4 divides 8, which is the 6th Fibonacci number (so m is 6). The 3rd Fibonacci number, 2, divides 6, so the property holds. The same thing works for the 4th Fibonacci number, whose square, 9, divides the 12th Fibonacci number, 144. Keeping track of m and n is a little bit challenging, but the property is not particularly difficult to verify for specific examples if you can keep them straight in your mind.
Matiyasevich writes, “It is not difficult to prove this remarkable property of Fibonacci numbers after it has been stated, but it seems that this beautiful fact was not discovered until 1969.” He was able to prove it because he was familiar with another theorem in the third edition of a number theory book by Nikolai Vorob’ev. He suspects that if the theorem had been in the earlier edition of Vorob’ev’s book that Robinson had had access to, she and her colleagues may have solved the problem a decade earlier.
Matiyasevich describes not only an interesting application of the Fibonacci sequence but also a great example of how mathematics happens. Rarely if ever do lone geniuses work things out all by themselves. His ideas developed through reading other people’s work. He found his way to the solution because he was asked to review a paper by Robinson: “I saw at once that Julia Robinson had a fresh and wonderful idea,” he writes. It gave him ideas for a new approach to the problem, and his familiarity with Vorob’ev’s helped him fill in some gaps. He was part of a community.
After Matiyasevich solved Hilbert's 10th problem, he and Robinson maintained a long-distance collaboration through the mail. They bounced ideas off of each other, caught (and sometimes did not catch) each other’s mistakes, and pushed each other forward. Their mathematical friendship bridged differences in age, gender, and nationality. On the centennial of Robinson's birth, I raise a glass to mathematical curiosity, generous coauthors, and the hope that the Fibonacci sequence still has a few surprises in store for us.