I became so excited I wanted to telephone Leningrad and find out if it were true but the mathematicians here [in Berkeley] said not to — after all the world has waited 70 years without knowing the answer to Hilbert’s tenth problem, surely you can wait a few weeks more. Fortunately, I didn’t have to. On Wednesday, John McCarthy called from Stanford University to say that he had heard a lecture by Ceĭtin in Novosibirsk on your proof. I received his notes yesterday and now I know it is true, it is beautiful, it is wonderful.
— Julia Robinson to Yuri Matiyasevich, 22 February 1970
Julia Robinson was 50 years old when she learned thathad resolved Hilbert’s Tenth Problem. He was just 22; she had been pondering the problem almost since the time of his birth. In the letter quoted above she conveyed her ecstatic response to his achievement. The notes about the proof were sketchy, but long experience with Hilbert’s Tenth Problem allowed her to quickly fill in the details — and also to see just how close she herself had come to solving this iconic problem.
It would have been understandable had she felt envy, disappointment, anger. But her letter is entirely free of such emotions. And in her subsequent correspondence with Matiyasevich, comprising about 150 letters, one sees that the ardent sincerity of that first letter was a hallmark of her character. It set the tone for their collaboration and for the warm friendship they shared until her death in 1985, at the age of 65.1
Julia’s first letter was typed and carried the salutation “Dear Dr. Matijasevič”, a necessary formality when writing to a colleague in a foreign country. Before long she began writing by hand and suggested they go to first names. After that, letters addressed “Dear Julia” and “Dear Yuri” made the long trek, usually lasting two to three weeks, between Berkeley on the western coast of the United States, to Leningrad, at the northwestern tip of the Soviet Union.
1. Two people, two nations, two very different worlds
I wish to thank you for your kind letter of 22nd February. You have made an outstanding contribution to the solution of Hilbert’s tenth problem and, in fact, to a greater extent it is your victory.
— Yuri to Julia, 17 March 1970
Yuri’s solution to Hilbert’s Tenth Problem grew out of earlier work by Julia as well as work byand . It’s not uncommon for young mathematical hotshots to downplay previous work in order to focus the glory on themselves. Not Yuri. He showed a far more idealistic spirit in his admiring, generous reply (17 March 1970) to Julia’s first letter.
From the start the correspondents were disposed to friendship and trust, almost as if the political chasms that separated them didn’t exist. Yet when they exchanged these first letters in 1970, in the depths of the Cold War, the US and the (then) USSR had become implacable enemies, amassing rival nuclear arsenals. Internal politics shaped the research climate of the respective mathematical communities in profoundly different ways.
In the USSR, Soviet premier Leonid Brezhnev had stepped up political repression in the wake of Nikita Khrushchev’s de-Stalinization policies. Criticizing the ruling party could land one in jail. Mathematical research operated within a dense thicket of secrecy regulations, restrictions on foreign travel, and discriminatory policies. Nevertheless mathematics thrived. For gifted students the field provided an intellectual refuge from the absurdity and corruption of the state. Soviet mathematicians were resourceful in cobbling together what historian Slava Gerovitch has called a “parallel social infrastructure” [e14] by organizing informal seminars, study groups, and correspondence courses.
The US by comparison enjoyed far greater social freedom but was blighted by racial violence and deep economic divisions. The assassination of Martin Luther King Jr. in the fall of 1968 set off massive demonstrations and civil unrest. University campuses became protest hotspots as young people raged against the hypocrisy of a society that tolerated the horror of the Vietnam war and the scourge of pervasive inequality. Many US mathematicians, while deploring the violence sparked during demonstrations, retained sympathy for the spirit of uncompromising honesty that marked the protests. There was a good deal of soul-searching within the US mathematical community about such matters as the ethics of accepting research support from the military.
Against this backdrop, Julia and Yuri began their remarkable correspondence, an exchange made more precious to each by the consciousness of the gulf across which they reached. That they became friends so readily underscores the powerful allure of mathematics: its potential to unite even distant thinkers in a shared quest for understanding.
2. What is Hilbert’s 10th Problem?
I agreed months ago to talk to a scientific society meeting on H10 to non-mathematicians. Just this minute I got a call from New York for the title of this talk. I started to say Hilbert’s tenth problem and then I realized that most scientists would not have heard of Hilbert… Maybe I’ll call it “The revolution in diophantine equations”.
— Julia to Yuri, 11 October 1973
Julia gave that talk at the annual meeting of the American Association for the Advancement of Science in San Francisco in March 1974. In it she had to explain what Hilbert’s Tenth Problem (H10) is, and that’s also a good place for us to begin.
The subject of the problem is Diophantine equations, which are polynomial equations in any number of unknowns and with integer coefficients, for which integer solutions are sought. Reflecting their deep roots in antiquity, these equations are named after Diophantus of Alexandria, who was active in the third century A.D. and described them in his most important work Arithmetica, large portions of which were lost. What survived made its way to the early modern world through Byzantine copyists and via medieval Arabic sources in which certain of the treatise’s equations were restated and scrutinized. In her now-classic 1952 paper “Existential definability in arithmetic” , Julia gave an example of a Diophantine problem studied by Arab mathematicians in the middle ages.
When in 1900presented his famous list of 23 problems, a few specialized solution methods had been found for limited classes of Diophantine equations. A general method, one that would find the solutions of any equation whatsoever, seemed out of reach. So the tenth problem on Hilbert’s list asked for something that looked more modest: A method that, when presented with a Diophantine equation, would tell you whether the equation has a solution in the integers.
What H10 asks for, in today’s parlance, is an algorithm. But at the time Hilbert posed the problem, a precise mathematical definition of algorithm was still in the future. That definition came in the 1930s, through the work of such pioneers as, , , and . It then became possible to prove that some algorithms one might hope for simply do not exist — in other words, to prove that some problems are unsolvable.
In a 1941 paper, Post wrote that H10 “begs for an unsolvability proof”. In this way he connected H10, which had until then been considered part of number theory, to logic. Martin Davis, then in his early 20s and a student of Post’s at City College in New York, read that statement and began a lifelong obsession with H10. His fascination was understandable. Up to that time the only problems that had been shown unsolvable either resided in the realm of mathematical logic or were dependent upon a certain computational model. H10 was different. It was a natural problem with deep roots in mathematics, and one for which a solution would be of wide interest.
Logicians brought to Hilbert’s question a new perspective, that of Diophantine sets. A Diophantine polynomial can “represent” a set in the following way. Suppose we have a Diophantine equation \( P(k, x_1, x_2, \dots x_n) = 0 \), where we think of \( k \) as a parameter and of the \( x_i \) as unknowns. The set of all \( k \) for which the equation has a solution \( (x_1, x_2, \dots, x_n) \) is called a Diophantine set represented by \( P \). A simple example: The non-powers of 2 are represented by \( k - (2x+1)y = 0 \).
Posing the question “Which sets are Diophantine?” brings into play powerful concepts from logic. A listable set comes equipped with an algorithm that can generate, or list, the members of a set. A decidable set has an algorithm that does a more difficult job: When fed a number, it returns “yes” if the number is in the set and “no” otherwise. A decidable set is always listable because, by systematically feeding all integers into the algorithm and recording those for which the algorithm answers “yes”, you can list the members of the set. But the converse is false: There are listable sets for which no membership-deciding algorithm exists. This asymmetry between listable and decidable is at the root of many unsolvability proofs.
In his doctoral thesis of 1950 [e1], Martin Davis made what Yuri later called a “daring hypothesis”: Every listable set is Diophantine. If this were true, then there would exist Diophantine sets that are not decidable, immediately implying that Hilbert’s hoped-for algorithm would not exist.
Julia’s contributions to the framework needed to solve H10 began to take shape at about the same time that Davis was completing his thesis. She could not enjoy a “normal” career in mathematics, however: a serious childhood illness had left her health in a delicate state. To understand her passion for mathematics — a passion that she and Yuri shared in their letters — we must consider the road she took to become a mathematician.
3. A childhood happy and sad
When I was in the 5th grade, I came down with rheumatic fever and was kept out of school until the 9th grade. Then I went to a big school and did not know any other students. So at lunch time I hid while eating (I didn’t want the other kids to know I didn’t have any friends) and then I walked around the school yard trying to look like I didn’t want to talk to anyone. This went on for several months until finally another girl called out “Why do you always stay by yourself? If you are not eating with someone else, join us.” At last — I was rescued!
— Julia to Yuri, 26 March 1973
This is one of the few places in the correspondence where Julia talked about her childhood. At the time she and Yuri began writing to each other, Julia was not a public figure, and the mathematical world was largely unaware of the unusual circumstances that gave rise to her intellectual life. It wasn’t until after her death that her older sister, Constance Reid, an author of books about mathematicians, including an acclaimed biography of David Hilbert, set down on paper what we know about Julia’s early childhood. Her book Julia: A Life in Mathematics [e11] presents what is essentially a brief autobiography, consisting of Julia’s first-person recollections, which she communicated to Constance while struggling with the leukemia that eventually took her life in July 1985.
Julia Bowman was born in 1919 in St. Louis, Missouri. Her early life was both happy and sad. She was two and Constance four when their mother died. The girls were sent to live with their grandmother in Arizona, where Julia’s earliest memories were of arranging pebbles in the shadow of a giant cactus. Their father married again, to a woman whom Julia always thought of as her mother. When Julia was five the family moved to San Diego. “Like the desert, it was open to exploration and fantasy,” Julia said in the autobiography. There a baby sister, Billie Esther, was born.
The illness that Julia mentioned to Yuri kept her in bed for one year and out of school for two. With the help of a tutor she caught up to and even surpassed what she would have learned in school during that time. She excelled above all in mathematics. After high school she enrolled in the local state college and studied all the mathematics she could. In her second year there, another disaster struck. Her father, in despair over economic ruin brought on by the Great Depression, committed suicide.
In the wake of personal tragedy, Julia proved resilient: a few years later she found herself “happy, really blissfully happy” after she began mathematics studies at the University of California at Berkeley. There she met and married, who was eight years older and a junior faculty member. A fine mathematician and an excellent teacher and expositor, Raphael was a major influence on Julia’s mathematics. In 1948, two years before Davis made his “daring hypothesis”, Julia earned a PhD in mathematics from Berkeley.
The rheumatic fever she suffered as a schoolgirl had so weakened Julia’s heart that she was advised not to try to have children. This left her quite depressed; mathematics was an absorbing distraction from this unhappy reality and later perhaps a solace. In 1960, at the age of 41, she underwent a then-new surgical procedure that dramatically improved her health. Nevertheless she could not meet the demands of a full-time career. She occasionally taught courses in the Berkeley mathematics department, where she was mainly known as “Professor Robinson’s wife.”
Not having to build a résumé meant Julia could work on whatever she felt like. During a stint at the RAND Corporation in 1949–1950, she wrote her only paper in the subject of game theory. The ideas in this paper have become quite influential, particularly with the rise of internet commerce and the growth of algorithmic game theory. The paper has more than 1000 citations in Google Scholar, many of them in the past twenty years. After RAND, in the mid-1950s, Julia devoted a lot of time to politics, including the presidential campaigns of Adlai Stevenson. But she never stopped thinking about H10.
4. The Julia Robinson hypothesis
Tarski originally suggested to me that it would be nice to show some particular set such as the set of primes or the set of powers of 2 is not diophantine. I quickly gave up and tried instead to show that they were diophantine.
— Julia to Yuri, 5 July 1971
made this suggestion in 1948, the year when Julia completed her PhD under his supervision. Tarski had joined the faculty at Berkeley in 1942, and had proceeded to build the department into a major world center for logic. Julia was one of his first PhD students and benefited from his exceptionally broad perspective on mathematics. It was Tarski who planted the seed of her fascination with H10.
The arithmetic relation “\( z \) is not equal to any power of 2” can be represented by a Diophantine equation, as we saw earlier: \( k \) is not a power of 2 if and only if the Diophantine equation \( k = (2x + 1)y \) has a solution \( (x,y) \). But how do you show that the relation “\( z \) is equal to some power of 2” has a Diophantine representation? That looks a lot harder.
In her 1952 paper “Existential definability in arithmetic” , Julia formulated the notion of a relation of exponential growth. This is a Diophantine relation that grows fast, but not too fast: It outruns any exponential \( x^n \) for a fixed \( n \), but it is bounded by \( x^x \). The conjecture that such a relation exists came to be known as the Julia Robinson Hypothesis, or simply JR. Her paper showed that, if JR were true, then the set of powers of 2 — and in fact any exponential — would be Diophantine. Not only that: The primes would be Diophantine. This last implication was especially surprising because the received wisdom in number theory said that there could be no formula for the primes.
Julia presented these results at the International Congress of Mathematicians in 1950. This was the first time she met Martin Davis, who also spoke at the Congress. “I remember Martin said there that he didn’t think one could solve Hilbert’s problem by looking at special cases of diophantine relations and I said I couldn’t prove any general theorems,” Julia later wrote to Yuri on 5 July 1971. Martin thought one might get to H10 by improving one of his own theorems about listable sets. “I guess we were both right,” Julia wrote.
While a student at Leningrad State University in the mid-1960s, Yuri read Julia’s paper in Russian translation and learned about JR. “I thought, ‘what [an] unnatural condition’,” he told her in a letter from 23 June 1971. “But soon I saw that many attempts to define \( p^s \) led to this condition.”
JR is remarkable. It stood as a fulcrum between two different scenarios, both of which harbored seemingly implausible consequences. If JR were true, then there would be absolute bounds on both the degree and the number of unknowns needed to define any Diophantine set. Some at the time took this as evidence that JR might not be true. But the opposite scenario, in which JR were false, carried consequences about the rate of growth of polynomial functions that were equally astonishing. Julia tried for many years to prove JR; at one point she even took the opposite tack and tried to disprove it.
In the late 1950s Martin Davis and Hilary Putnam worked on an adaptation of Davis’ daring hypothesis (from his 1950 PhD thesis). Rather than trying to show that listable sets are Diophantine, they tried to show they are exponential Diophantine — in other words, that listable sets can be represented by Diophantine equations in which unknowns can appear as exponents. They almost succeeded, save for one unproven assumption: the existence of arbitrarily long sequences of primes in arithmetic progression. (Such sequences do exist, but that fact was proven only in 2004, in a celebrated result ofand .)
When Davis and Putnam submitted their paper for publication, they also sent a copy to Julia. Before long she came up with an argument that circumvented the then-unproven assumption. Davis proposed withdrawing the paper in favor of a new, three-author paper that would incorporate Julia’s ideas. She and Putnam agreed, and the paper, “The decision problem for exponential diophantine equations” , known by the nickname DPR after the last names of the authors, has become a classic. It showed that listable sets and exponential Diophantine sets are the same.
That paper, which appeared in 1961, threw the significance of JR into vivid relief. JR proposed that exponentiation was Diophantine, and DPR said listable sets are exponential Diophantine. Were JR true, then listable sets would be Diophantine, and unsolvability of H10 would immediately follow.
5. How Yuri solved H10
I asked a friend of mine why he did not try to solve [H10]. He explained his position: trying to solve the 10th problem is equivalent to skiing down a mountain — you can become a world champion but more likely you will break your neck.
— Yuri to Julia, 23 June 1971
Much like Martin Davis, Yuri had an irresistible attraction to H10. And like Martin, he had to discipline himself away from it in order to make progress on his doctorate. In the letter containing the quotation above, Yuri told Julia the story of how he resolved H10.2
Yuri was born in Leningrad in 1947. He showed mathematical talent at a young age and excelled in the Mathematical Olympiad. He was selected to participate in special mathematics classes outside of school and when he was 15 went to a summer program where the teachers includedand . He entered university in Leningrad in 1965 and immediately solved a difficult problem concerning certain logical systems invented by Emil L. Post.
It was Yuri’s adviser,, who suggested Yuri work on H10. Maslov knew how close DPR had come to solving H10 but thought the Americans must be on the wrong track because their methods hadn’t worked yet. He proposed that Yuri approach the problem by trying to establish the unsolvability of word equations, because they can be reduced to Diophantine equations. Yuri did write some good papers on the subject, but it was a dead-end as far as H10 was concerned: In 1977, proved that word equations are solvable.
Still Yuri remained fascinated by H10. He spent almost all his free time trying to find a Diophantine relation of exponential growth. One professor began to tease Yuri, saying he would not be able to graduate if he didn’t solve H10. Yuri didn’t need H10 to graduate — but he needed something. So his earlier work on Post canonical systems became his PhD thesis. In 1969 he graduated and became a postgraduate student at the Steklov Institute in Leningrad.
Late that year a colleague, . Yuri recounted his reaction in his letter to Julia: “It is very well that Julia Robinson continue her investigations on Hilbert’s tenth problem but I myself cannot waste time anymore.” But, Yuri wrote, God intervened: The Russian mathematical reviewing journal asked him to review the paper., told Yuri to rush to the library because a new paper by Julia had just appeared
He then saw it contained a brilliant new idea concerning the periodicity of sequences of solutions of a well known Diophantine equation called Pell’s equation. His letter to Julia quoted above (23 June 1971) recounted the drama of the first few days of January 1970 when he figured out how to adapt this idea to a different sequence, namely, the Fibonacci numbers. This allowed him to show that the sequence of Fibonacci numbers is Diophantine, thereby establishing the truth of JR — and the unsolvability of H10.
This work earned him his DSc degree (similar to a European Habilitation), awarded in 1973. Yuri soon got a permanent position as a researcher at the Steklov Institute in Leningrad. He has remained there throughout his career in the Laboratory of Mathematical Logic.
With four people having contributed decisively to the resolution of the monumental H10, it’s remarkable that there was not even a hint of a priority dispute among them. All four bent over backwards to give credit to the others. The final result has gone by various names including Matiyasevich’s Theorem and MRDP. Yuri himself calls it DPRM.
Recently, Yuri observed to this author3 that Julia was “not an ambitious person”. She just wanted to know the truth. She was not afraid that someone else might resolve H10 before her. Her only fear was that the proof, when it came, would be very difficult and she would be too old to understand it. As she put it in her autobiography, “I felt that I couldn’t bear to die without knowing the answer.”
6. A counterintuitive consequence of H10
Raphael and I showed that 35 variables is enough for a universal diophantine equation. Do you know a better result? […] In view of Alan Baker’s work, it seems like number theorists would be very much interested in the minimum number needed.
— Julia to Yuri, 22 October 1970
After Yuri’s breakthrough became known, he received many invitations to speak, including one to give an invited address at the International Congress of Mathematicians in Nice in August 1970. There Yuri met Martin Davis for the first time, though not Julia, as she did not attend. In August of 1971 Julia and Yuri did meet at a conference in Bucharest. Afterward Julia together with her husband Raphael traveled to the USSR to meet Yuri and his wife Nina in Leningrad.
Nice and Bucharest turned out to be exceptions. Yuri’s letters to Julia mention several invitations to speak that he had to decline because of the Soviet government’s restrictions on travel. In particular there was no chance for him to come to the US. As a result during 1970 and 1971 Julia lectured about his work at institutions around the US. In the USSR, Yuri himself gave a couple of talks about his work, as did 4 because at that time he himself was not a very experienced speaker, while Manin was known to be an excellent speaker and could also describe the H10 work in a way that would appeal to number theorists.. Manin was invited for such lectures, Matiyasevich explained,
In 1969, Julia had given a talk on H10 at a meeting in Stony Brook. When it came time to write up her contribution for the proceedings volume, she had by then learned of Yuri’s solution and wrote about that instead of preparing a manuscript of her original talk. Commenting on open problems in her contribution, she noted, “I think the most exciting problem is to find some interesting bound on the number of variables needed in a universal diophantine equation.”
The existence of such a “universal” equation is another counterintuitive consequence of the fact that Diophantine and listable sets are the same. A universal Diophantine equation takes the form \[ P(k,a, x_1,x_2,\dots x_n) = 0 \] for a Diophantine polynomial \( P \). For any listable set \( S \), there is a \( k \) such that \( P \) represents \( S \); that is, \( P \) has a solution \( (x_1, x_2, \dots x_n) \) if and only if \( a \) belongs to \( S \).
As Julia told Yuri in the letter quoted above (22 October 1970), she believed number theorists would be interested in the minimum number of unknowns in a universal Diophantine equation. She mentioned in particularbecause he had received the Fields Medal in 1970 for work shedding light on Diophantine equations in two unknowns with degree greater than two.
“I have not precisely estimated the number of variables needed for [a] universal polynomial,” Yuri replied on 13 November 1970. “My very rough estimate was 100–120 variables. Nevertheless it seems to me that your fine estimate of 35 variables can be reduced.” He went on to outline some of his ideas. The next several letters contain close discussion of the problem. In her letter of 2 March 1971 Julia asked Yuri if he wanted to write a joint paper.
Ever gracious, she added: “Or if you would like to write it up yourself it is OK with me.” Equally gracious, Yuri replied on 12 April 1971: “I would be very glad to have a joint paper with you.” It was Yuri’s first real collaboration.
7. Two equals, sharing ups and downs
I received your letter yesterday — just 5 days after you mailed! You are just full of new ideas — I read it with “Ah’s” and “Oh’s”. Unfortunately I am terribly pressed for time right now so I can only tell you how impressed I am.
— Julia to Yuri, 17 June 1971
Julia sometimes taught in the UC Berkeley mathematics department, but because her husband Raphael was on the faculty, anti-nepotism rules prevented her from holding a regular position. Therefore she could not formally advise PhD students. “In a real sense, Yuri was the graduate student Julia never had,” Lenore Blum has observed [e12]. Perhaps he was also in some sense the child Julia never had. Some of her letters struck a motherly tone, such as when she wrote on 4 June 1974, “Now, Yuri, please take care of yourself.”
Nevertheless as collaborators they were very much equals. When one of them came out with a good idea, there was praise from the other. “Now about your new ideas,” Yuri wrote on 16 August 1972. “They are wonderful!”
And when one of them made an error, there was encouragement. “I must apologize for sending you a letter with so many mistakes,” was Yuri’s sheepish statement on 24 February 1971. “I am not a man one can rely on in verifying proofs.” Yuri had mentioned to Julia several times the influence of(son of the more famous Markov of stochastic processes), who was known for his extreme carefulness and insistence on detailed proofs.
Julia replied on 2 March 1971 that she had already found the mistakes Yuri had mentioned but wasn’t bothered because they left the final result unchanged. She reassured him, “Don’t worry everyone has made mistakes — chances are that Markov did when he was young so he is trying to make up for it now.” Julia also encouraged Yuri’s efforts to escape from Markov’s pedantic writing style, which tended to obscure the main ideas.
Her sense of humor again lightened the mood when two years later Yuri found a more serious mistake in their work on the universal Diophantine equation. They had assumed a certain implication about binomial coefficients, and he found an obvious counterexample involving only the numbers 2, 3, and 5. “I was completely flabbergasted,” wrote Julia on 30 May 1973. “I wanted to crawl under a rock and hide from myself!” She had mentioned the implication several times to Raphael, who hadn’t objected. “He said he would have said ‘No’ if I had asked him if it were true. I guess I would have myself if I had asked!” Fortunately, at the same time Yuri found the mistake, he also found a way around it. But the paper had to be completely rewritten.
In a letter from 11 September 1972, Yuri told Julia in confidence that he had been trying to solve the four-color problem. His idea was to express, in the language of predicate logic, the condition of two countries having the same color. If one assumed there exists a graph that cannot be four-colored, Yuri guessed that these logical expressions would lead to a contradiction.
When his investigations came to an impasse, Julia was encouraging but practical. “My advice is to work on whatever interests you but don’t let any problem become an obsession,” she wrote on 13 August 1973. “If you have been spending a great deal of time on the 4CP, then I would suggest that you take a vacation from it for awhile…(P.S. I don’t always follow my own advice.)” Three years later, on 16 August 1976, she sent the news that the four-color theorem had been proved. “I think it is very exciting that it has been proved after all these years and it is also interesting (but a little disappointing too) that it took a computer to do it,” she wrote.
In 1972, a few months after his 25th birthday, Yuri expressed to Julia a fear common among mathematicians who achieve early success: Maybe he would never again do anything great in mathematics. Julia’s reply, on 28 July 1972, combined her optimism with a dash of self-deprecating wit: “Yuri, it would be silly to think that you weren’t going to prove bigger and better theorems just because you’re so old. After all everybody knows that girls are no good at mathematics at all. Besides if you look at the work of any great mathematician you’ll find that he didn’t just shrivel up when he reached 25.”
8. Chipping away at the number of unknowns
With just 14 variables we ought to be able to know every variable personally and why it has to be there and what leeway it has.
— Julia to Yuri, 22 February 1972
Julia and Yuri slowly chipped away at the number of unknowns in the universal equation. From the initial estimate of around 100 by Yuri and of 35 by Julia and Raphael, they quickly got to 33, then 28. When they hit 26, Julia celebrated the moment when they “broke the ‘alphabetical’ barrier” (5 July 1971). Before long they were at 23 and then 20, and by fall 1971 the number stood at 14. Correction of oversights caused a revision upward to 16 the next spring, but soon they were back to 14 and by August 1971 they were at 13. When they hit 12 in February 1973, Julia asked (5 February 1973) “Do you think we will ever finish the paper?” Twelve proved to be a mirage, so it was back to 13. In May 1973 Yuri found the mistake involving binomial coefficients, but his rescue left the number at 13. And there it remained.
How did they do it? The basic construction is implicit in the DPRM theorem. Given an arbitrary logical relation, you can break it into smaller pieces and represent each piece by Diophantine equations. Summing the squares of those equations gives you a Diophantine equation representing the relation. But this brute-force method is very inefficient and causes the degree and the number of unknowns to explode.
Using elementary number theory, Julia and Yuri developed clever relation-combining methods that allowed them to carry out this process more efficiently. The main idea was to get some of the unknowns to play more than one role. For example, to represent the logical conditions \( a\geq b \) and \( (c+1)\mkern1mu|\mkern1mu d \), one could use two unknowns \( x \) and \( y \) and two equations \( a=b+x \) and \( (c+1)y=d \). More economical would be to introduce only one unknown \( z \) and one equation for both conditions: \( (c+1)(d+1)a=(c+1)(d+1)b+(c+1)z+d \). They searched assiduously for such small economies, bringing to bear all the number-theoretic intuition they could muster.
Writing up the paper took quite a while. “It seems to me that we had little trouble in collaborating mathematically on a 4-week turnaround time but it is hopeless when it comes to writing the results up,” Julia wrote on 15 February 1974. “[B]y the time you could answer a question, it was no longer relevant and besides when I tried to explain why I didn’t follow your suggestions I realized it would be like writing the whole paper over again.” The paper was finally published in 1975 .
Midway through that year Yuri discovered a new method for reducing the number of unknowns, using an old theorem of. Julia once called this remarkable theorem a “gold mine” for constructing Diophantine equations. It combines the “number” viewpoint on integers, in which factorization and divisibility properties come into play, with the “word” viewpoint, in which integers are viewed as strings of symbols with a positional notation and with operations like concatenation.
Yuri’s new method suddenly brought the number down to 9. “What a surprise to learn of your new improvement!” Julia wrote on 8 June 1975. “Raphael said he thought 13 unknowns would probably be the record for ‘generations’.” She studied carefully Yuri’s ideas and was so enthusiastic that she spoke about them at a number theory meeting in Asilomar that year. Encouraging him to write up his results, she steadfastly declined his suggestion that she be a coauthor. “I have told everyone that it is your improvement and in fact I would feel silly to have my name on it,” she wrote on 2 October 1976. “If I could make some contribution it would be different.”
In October 1975 Julia wrote to Yuri about two Berkeley PhD students,and , who had taken a course she had taught about Yuri’s H10 work. “Len and Ken”, as she called them, had started thinking about computational complexity aspects of diophantine problems, and Julia realized that Yuri’s 9-unknowns method would simplify it. Since the method was unpublished, she gave the students a copy of the relevant letter from Yuri. Adleman and Manders were able to use Yuri’s work and wrote several papers together.
Yuri never published the full details of his 9-unknowns result. In his Intelligencer article [e9] he wrote that he would not have gotten this result without Julia’s inspiration and therefore did not want to publish on his own. The result finally appeared in print in 1982, in a paper by his collaborator James P. Jones, who gave full credit to Yuri [e6].
9. A competing claim, a trusted confidante
[M]athematicians should be able to trust one another.
— Julia to Yuri, 7 November 1974
Julia’s idealistic approach to mathematics was part of her personality. But it also reflected her circumstances. Free of the need to build a career, she did not have to deal with competitive pressures in mathematics. When others faced them though, she showed empathy. They form a running theme in the letters, as Yuri confided in her about a competing claim that arose soon after his resolution of H10.
News of Yuri’s feat spread quickly around the USSR in January and February 1970. He gave his first public lecture on the result at the end of January. After the lectureasked Yuri for permission to speak on the work in Novosibirsk, and Yuri agreed. It was Ceĭtin’s Novosibirsk lecture that John McCarthy attended and that was the source of the notes he sent to Julia in February 1970. That same month Yuri mailed a copy of his manuscript to a colleague in Kiev. Not long after these events, word circulated that 17-year-old , then living in his birthplace of Kiev, claimed he had independently resolved H10.
This was not a priority dispute, as the published record makes clear. Yuri’s four-page paper containing his proof appeared in Doklady Akademii Nauk with a received date of 5 February 1970 [e3]. A two-page paper by Chudnovsky, claiming H10 but without a proof, appeared in Uspekhi Matematicheskikh Nauk, with a received date of 30 March 1970 [e4]. Chudnovsky did include a proof in a 1971 preprint issued by the Mathematics Institute of the Ukrainian Academy of Sciences [e5] (it was published only much later, in 1984 [e7]).
The question, then, was whether Chudnovsky had independently found a proof. When Yuri wrote to Chudnovsky to try to clarify the situation, his letters went unanswered. In September 1971, upon her return from Leningrad to Berkeley, Julia found that Chudnovsky had sent her a copy of his preprint. She replied in a friendly manner, posing direct and specific questions about his claim to an independent resolution of H10. Her letter too went unanswered.
In December 1972, Julia learned second-hand that André Weil, after a visit to Kiev, believed Chudnovsky’s work had been independent. Julia then exchanged letters with Weil. In his reply, Weil told her that Chudnovsky suffered from a long-term neuromuscular disease called myasthenia gravis, which since childhood had kept him bedridden and in need of constant care from his family. Weil had not raised the question about independence directly with Chudnovsky but heard about it from others in Kiev. On this basis, and out of concern about discouraging the obviously talented Chudnovsky, Weil suggested that Yuri publicly acknowledge that Chudnovsky’s proof was independent.
However, given the published record and Chudnovsky’s continued silence, Yuri felt he had no basis for a public acknowledgment. Frustrated by Chudnovsky’s “ambiguous formulations,” Yuri wrote to Julia on 3 March 1973, “I can’t realize why a man who indeed found his proof independently could not write about it explicitly.” In this and other letters he also noted that Chudnovsky did not give proper attribution to the contributions of others and seemed not to distinguish between what he had done himself and what he had learned from others.
In her reply on 26 March 1973, Julia discussed what she called Chudnovsky’s “expanded paper,” which presumably is the 1971 preprint. In it, Chudnovsky claimed three different ways to resolve H10. The first, proved in full, bears similarity to Yuri’s method; it bears even more similarity to proofs found shortly after Yuri’s H10 work by Martin Davis and [e2] and the other on model theory — are not given full proofs. Julia seemed perplexed that, in these last two attempts at proof, Chudnovsky “leaves out the crucial argument.”. Chudnovsky’s second and third ways of resolving H10 — one based on an earlier result of Martin Davis
On the one hand, she was inclined to believe Chudnovsky had an independent proof because his colleagues in Kiev said so. “[N]o one can be a charlatan mathematician for long,” she wrote. On the other hand, she noted, “it seems hard to assert it as a fact.” “just believed what he was told in Kiev and did not take into account how it was Chudnovsky himself who had beclouded the issue,” Julia concluded in that same letter. “It seems to me that your references to Chudnovsky have been absolutely correct.”
She and Yuri still faced the question of whether to refer to Chudnovsky’s work in their own paper. In the end they included Chudnovsky’s 1970 paper in the bibliography of the 13-unknowns paper, as well as that of a shorter paper they wrote around the same time in Russian, for inclusion in a volume to honor Markov.
The story has an additional dimension. Chudnovsky is Jewish, and he has said that anti-semitism undermined his claim about H10.5 Anti-semitic discrimination was rife in the Soviet mathematical community and often insidious, taking place outside of public view.
On 24 July 1977, the New York Times carried a short item6 saying Chudnovsky’s parents had been beaten up in a Kiev street, presumably in retaliation for their application to emigrate from the Soviet Union to seek better medical treatment for their son. After reading this news, Julia wrote a sympathetic note to Chudnovsky and undertook efforts to help the family emigrate. The main proponent of these efforts was Edwin Hewitt, a mathematician at the University of Washington who had the year before traveled to Kiev and collaborated with Chudnovsky [e8].
The family was able to leave for France in August 1977. Not long thereafter, Chudnovsky wrote to Julia from Paris and thanked her for her help. When Julia told Yuri of Chudnovsky’s letter, she expressed the hope that Chudnovsky would visit Berkeley. But it isn’t clear whether he did — or indeed whether Julia ever met him.
In summer 1978 Yuri sent Julia two volumes in what became a five-volume Russian mathematical encyclopedia and pointed out one article that mentioned her. “This article was originally written by me somewhen [sic] in 1971 and gave a reference to Chudnovsky’s paper too,” Yuri wrote on 18 July 1978. “Now that he has left this country I was informed that the reference to his paper had been eliminated by the editors of the Encyclopedia.”
Julia found the encyclopedia “very impressive” but she too noted the censoring of the names of many Jewish mathematicians. “In itself it seems very petty but more serious things are being done to Jewish mathematicians in your country,” she wrote on 11 December 1978, pointing to recently published evidence.7 “I know it is almost impossible for one person to stand alone against such things but mathematics would be in tatters if all the contributions by Jews were removed.” Among the Jewish mathematicians mentioned in her letter was their own coauthor Martin Davis.
This is the only place in the correspondence where Julia directly criticized the USSR. She might have been circumspect out of concern about getting Yuri into trouble with the Soviet authorities, who were monitoring the correspondence. This monitoring was discussed directly only once, in a letter Yuri wrote in 1976; he was in Finland at the time, so he could be sure the Soviet authorities would not see it.
10. A masterpiece of exposition
The meeting at DeKalb was great. I went to about half the talks and found them exhilarating. There was a certain old-fashion [sic] air about them naturally but this helped to make them understandable. Many people praised our talk and they were talking about the content.
— Julia to Yuri, 4 June 1974
When Julia learned that Yuri had been invited to speak at an American Mathematical Society meeting in April 1974 at Northern Illinois University in DeKalb, she was excited. “It is great news and I hope you can extend your visit to California,” she wrote on 21 January 1974. Other institutions were certain to extend invitations, and graduate students would be especially eager to meet him. She recalled that, when the news had arrived in Berkeley that a 22-year-old Russian had solved H10, “all of the students were tremendously excited and they still look back on it as the high point of their graduate studies.” But these hopes were dashed: Once again Yuri could not get permission to travel.
The main event of the meeting was a symposium titled “Mathematical Developments Arising from the Hilbert Problems,” in which top mathematicians were recruited to speak, one on each of the 23 problems. In Yuri’s stead, Julia accepted the invitation to speak; her one condition was that Martin Davis should be invited to introduce her. She and Martin “were both disappointed and indignant that the speaker had to be changed,” Julia wrote on 4 June 1974. (By “the speaker” she meant Yuri. She may have written in this elliptical way out of concern about monitoring of their letters.)
For the DeKalb symposium proceedings, Julia proposed to Yuri a three-author paper with Martin. Martin visited Berkeley over the following summer, and he and Julia met regularly to work on the paper. In her letters to Yuri, Julia was careful to solicit his input and reassure him that they would not move to publication without his okay. Martin was the one who brought all the pieces together and assembled the final article, mainly because he was at the Courant Institute at New York University and could get the article typed by Courant’s excellent mathematical typist, Connie Engle.
Yuri was especially interested in connections between Diophantine equations and famous open problems like the Riemann Hypothesis. It’s easy to understand why. The question “Is the Riemann Hypothesis true?” is equivalent to the question of whether a certain Diophantine equation has no solutions. That the truth of such a central question boils down to solvability of a single polynomial equation is astonishing. Yuri’s letters to Julia from this time contain long passages on this theme, which were then incorporated into the joint effort.
With the title “Hilbert’s tenth problem: Diophantine equations: positive aspects of a negative solution,” the paper appeared in 1976 . A review by in the Journal of Symbolic Logic called the paper “a masterpiece […]. The survey is thorough; the bibliography is complete; and the exposition is flawless.” The paper is an elegant testament to the enthusiasm of the three authors for a problem close to their hearts and makes a compelling case for the impressive power of Diophantine equations.
About that equation that captures the Riemann Hypothesis: Constructing it is straightforward, almost routine. So it would be possible to write the equation down, though this is not done in the paper. It would not be a pretty sight, nor an edifying one. As Davis has put it, “This is an equation that only its mother could love” [e13].
11. Learning Russian, gathering mushrooms
I enjoy your letters whether they are about mathematics or mushrooms or anything else.
— Julia to Yuri, 27 January 1975
In some ways Julia’s letters conform to the stereotype of the cheerful, positive-minded American. She includes chatty asides about all kinds of things — redwood trees, bike riding, birthday cakes, whale watching. While Yuri’s letters are more reserved and less voluble, from the letters of both flow warmth, esteem, and trust.
In fact, what looks like reserve in Yuri’s letters might simply have been an artifact of his having to write in a language that is not his mother tongue. Nevertheless he had no trouble expressing himself. “Your English is very good,” Julia wrote on 2 March 1971. “[T]he few mistakes have been where you are logical but English isn’t.”
Soon after she began writing to Yuri, Julia undertook an enthusiastic effort to learn his language. As practice she sometimes included a paragraph or two in Russian, and Yuri responded in kind. In speaking Russian she struggled to roll her r’s. “At first I was sure I could never teach my tongue to vibrate,” she wrote on 31 May 1971. “[I]t was like telling my ears to wag!” When their collaboration got under way, sticking to English proved more practical. Yuri often asked Julia for advice on English, and her replies were always perspicacious.
And they really did discuss mushrooms. After Yuri told Julia he had foraged for wild mushrooms, she worried that he would get poisoned and sent him an article about the Amanita phalloides, or death cap mushroom. You can almost hear Yuri’s kindly chuckling as he reassured her in a letter on 27 December 1974: The death cap “is very well known in this country,” he wrote. “Nobody even children would ever take it in hand.”
Julia was better able to circulate in the mathematical community than was Yuri, and she often told him about people she had met at conferences. In a letter from 7 July 1978, she talked about a symposium she had attended the previous month, for Stephen Kleene’s seventieth birthday. “I met our friend Craig Smorynski for the first time,” Julia said. Smorynski, who had gotten a PhD in logic in 1973, corresponded with both Julia and Yuri and is mentioned several times in the letters. “[Craig] pretends to be very cynical and feels that people are making fun of him when they aren’t. So he feels like an outsider but of course we all are. I like him and admire him very much.”
After attending the International Congress of Mathematicians in Vancouver in August 1974, Julia told Yuri that a few people there had said he should have gotten a Fields Medal. “[T]he only one I can identify was,” she wrote on 11 September 1974. “Actually he didn’t say that but he asked me what I thought about the fact that you didn’t get one. I said I thought total work was so great he certainly deserved one and you were still quite young […]. Actually I don’t think it makes much sense to try to compare mathematicians. I would just as soon let the physicists fight over Nobel prizes while we praise all good work.”
12. Not the “first this or that,” just a mathematician
Raphael says to thank you for getting me elected to our National Academy of Sciences. If you hadn’t solved H10, I’m sure no one would have even proposed my name. Of course it was probably helpful that I am a woman too. In fact, I guess I’m the first woman to be elected in the mathematics section. I can think of oodles of people who belong in before I do but it is sort of fun to get all the attention for a bit.
— Julia to Yuri, 16 August 1976
Election to the National Academy of Sciences left the ever-modest Julia pleased but embarrassed. Yuri saw no need for embarrassment. “I don’t think that Raphael is right,” he declared when he sent his congratulations on 24 September 1976. “[C]ertainly, the [reverse] implication is true: you could be elected without my contribution to H10 but I could not complete the solution without your works as background.”
After Julia’s election, the University of California at Berkeley, where she had occasionally taught courses, suddenly made her a professor. “The university was sort of embarrassed that I wasn’t employed so they claimed I was a ‘lecturer’ but I really wasn’t,” she told Yuri in the same letter quoted above (16 August 1976). The University gave her a reduced teaching load that she could manage without compromising her health. Other distinctions rolled in, such as an honorary degree from Smith College, a MacArthur “genius” Award, and presidency of the American Mathematical Society. Julia was also in the news outside academia, even appearing on a list of the 100 most outstanding women in America published by the Ladies Home Journal.
While she was uncomfortable being known as “the first woman this or that”, as she put it in her autobiography, she was aware of her significance as a role model. “I have always tried to do everything I could to encourage talented women to become research mathematicians.” She did this in a quiet, personal way, without fanfare.
Julia would probably be embarrassed to know that she is now so famous that there is even a program called the Julia Robinson Mathematics Festival, which since 2007 has sponsored mathematical activities for young people around the world. But she would have liked the festival’s stated aim, “to inspire joy with math.” It’s a joy she knew intimately.
13. Reaching across time and place and culture
You know, Yuri, usually when I write a letter I can’t think of much to say and have a hard time filling one page but to you it is different.
— Julia to Yuri, 5 July 1971
When her correspondence with Yuri began, Julia’s life was settled. She had been married for close to 30 years and had long accepted that her two-person family with Raphael could not include children. Her letters spoke of dinners with long-standing friends Derrick and Emma Lehmer, trips to mathematics meetings with another old friend Lisl Gaal, bike rides around the Bay Area, Thanksgiving with the family of her sister Constance Reid.
Yuri was at a far more eventful time of life. At 22 he was preparing for his wedding, finishing his time as a student, starting out as a mathematician. His letters tell of a new apartment, his wife’s long illness, her recovery, the birth of their daughter Dasha (“I felt like jumping up and dancing around the room as I read your letter,” was Julia’s reaction on 2 June 1979. “I do wish I could hold her now and see her grow up.”).
In an article that appeared in 1996 [e10], a decade after Julia’s death, her sister Constance quoted something that Julia once said to a group of young people: Julia thought of mathematicians “as forming a nation of our own without distinctions of geographical origins, race, creed, sex, age, or even time (the mathematicians of the past and you of the future are our colleagues too) — all dedicated to the most beautiful of the arts and sciences.” It was this romantic view of mathematics that allowed Julia and Yuri to reach across time and place and culture to form a friendship. They met in person only a couple of times; their few phone calls were marked by difficulties understanding each other. Their friendship really took place in their letters. Suffused with artless delight at finding deep resonance in a far-flung correspondent, the letters trace the meeting of two minds devoted to the truth and beauty of mathematics.
The author would like to thank Martin Davis, Yuri Matiyasevich, Sheila Newbery, and Carol Wood.