The month of December in the San Francisco Bay Area was foggy, cold and wet. A warm remarkable Mathematical tale however was awaiting as I arrived at the former house of Julia Robinson, perched at the top of a hill at Kensington, California.
The celebration of Julia Robinson Centennial kickstarted at Julia's former house with a reception organized by Nancy Blachman who founded the Julia Robinson Mathematics Festival (JRMF). It was a marvelous evening as I made new friends (math circle friends at the Bay Area, Howard Landman, Manuel Blum and his wife Lenore Blum who just retired from CMU) and catching up with old friends (Mark Saul and Nancy Blachman). I was especially delighted to get the autograph of Martin Davis and Yury Matiyasevich who were Julia's former collaborators. The celebration continued the next day with a Symposium in Honor of Julia Robinson's 100th Birthday organized by the Mathematical Sciences Research Institute, where prominent speakers e.g., Lenore Blum (who was Julia's former postdoc), Martin Davis, Yury Matiyasevich shared more on the highlights of Julia's mathematical quest. After her death, Julia's husband, Raphael M. Robinson, also an eminent mathematician at UC Berkeley, created the Julia Bowman Robinson Fund for scholarships for graduate students at Berkeley, which received the bulk of the Robinsons' estate (the sale of Julia's former house) upon his death. The charitable Robinson mathematicians were truly highly remarkable persons.
Julia Robinson was instrumental in resolving Hilbert's 10th problem, together with American mathematicians, Martin Davis, Hilary Putnam. Hilbert posed his 10th problem along with twenty two others in 1900, now famously known as Hilbert's problems. And this 10th problem was finally closed in 1970 by a young Russian mathematician Yuri Matiyasevich who built on the work of Robinson, Davis and Putnam. Out of Hilbert's 23 questions, this 10th problem was the only decision problem, asking for a computational procedure to determine the solvability of a Diophantine equation. Martin Davis' prediction that "Julia Robinson's conjecture is true and it will be proved by a clever young Russian" essentially came true. It was truly remarkable how leading mathematicians on both sides of the Iron Curtain could come together to complement each other's work in resolving Hilbert's problem seventy years after it was first posed. Lenore Blum's Public Lecture "Julia Robinson: Personal Reflections, Her Work and Time" gave a very comprehensive overview of the mathematical quest and Julia's personality. These mathematicians and logicians laid down very strong foundations for theoretical computer science as computer science becomes a mainstream academic discipline mushrooming in universities starting in the seventies.
To show that Hilbert's 10th problem has no solution (i.e., no such algorithm exists) was a tour de force of mathematics and logic, requiring the invention of new mathematical tricks, connecting revolutionary concepts (Turing's halting problem with Diophantine equations in number theory) and the discoveries of new properties of the Fibonacci numbers (properties overlooked for centuries and discovered by Yuri Matiyasevich). What struck me the most was that to those Diophantine equations that do have a solution (and therefore an algorithm to determine the solution), the quest for the algorithm by extraordinary mathematicians since ancient times is equally exciting!
Here, I'll point out some of these special cases. The linear Diophantine equation in two variables was solved completely many years ago by Diophantine (who else?) and relies on the Euclid's algorithm. This Diophantine equation is a mathematical statement that links the prime decomposition of natural numbers with the solvability of the equation (the notion of solvability means a computable program): Two natural numbers, say a and b, are relatively prime if and only if the linear Diophantine equations with integral variables x and y: ax+by =1 has a solution. The Euclid's algorithm is fundamental to its solution. Next, moving to the nonlinear world, another special case is the Pell's equation, which can be solved by the Chakravala method invented by the great Indian mathematician Bhāskara II, and this algorithm was considered "the finest thing achieved in the theory of numbers before Lagrange" by Hankel. Another special case is the exponential Diophantine equation associated with the enumeration of dyadic distributions that connects to binary search tree algorithms that are fundamental in information theory and coding theory (e.g., construct prefix-free code for compression). And, until only recently, the task of expressing the sum of three cubes for 33 and 42 was completed in 2019 by supercomputers and massively parallel computational search algorithms. It is undeniable that finding solutions to solvable Diophantine equations requires a skillful use of computers. Further reading on how Julia's legacy impacts the future of computer science can be found in Undecidability in Number Theory by Bjorn Poonen published in AMS 2008.
This is an inspirational mathematical tale worth telling to many more students of mathematics and computer science.
Nancy Blachman and myself beside the Christmas Tree at MSRI
Martin Davis showing a picture of the collaborators who nailed down Hilbert's 10th Problem.
