Celebratio Mathematica

Julia Robinson

Dear Julia, Dear Yuri:
A mathematical correspondence

by Allyn Jackson

I be­came so ex­cited I wanted to tele­phone Len­in­grad and find out if it were true but the math­em­aticians here [in Berke­ley] said not to — after all the world has waited 70 years without know­ing the an­swer to Hil­bert’s tenth prob­lem, surely you can wait a few weeks more. For­tu­nately, I didn’t have to. On Wed­nes­day, John Mc­Carthy called from Stan­ford Uni­versity to say that he had heard a lec­ture by Ceĭt­in in Nov­os­ibirsk on your proof. I re­ceived his notes yes­ter­day and now I know it is true, it is beau­ti­ful, it is won­der­ful.

 — Ju­lia Robin­son to Yuri Matiy­a­sevich, 22 Feb­ru­ary 1970

Ju­lia Robin­son was 50 years old when she learned that Yuri Matiy­a­sevich had re­solved Hil­bert’s Tenth Prob­lem. He was just 22; she had been pon­der­ing the prob­lem al­most since the time of his birth. In the let­ter quoted above she con­veyed her ec­stat­ic re­sponse to his achieve­ment. The notes about the proof were sketchy, but long ex­per­i­ence with Hil­bert’s Tenth Prob­lem al­lowed her to quickly fill in the de­tails — and also to see just how close she her­self had come to solv­ing this icon­ic prob­lem.

It would have been un­der­stand­able had she felt envy, dis­ap­point­ment, an­ger. But her let­ter is en­tirely free of such emo­tions. And in her sub­sequent cor­res­pond­ence with Matiy­a­sevich, com­pris­ing about 150 let­ters, one sees that the ar­dent sin­cer­ity of that first let­ter was a hall­mark of her char­ac­ter. It set the tone for their col­lab­or­a­tion and for the warm friend­ship they shared un­til her death in 1985, at the age of 65.1

Ju­lia’s first let­ter was typed and car­ried the sa­luta­tion “Dear Dr. Mati­jasevič”, a ne­ces­sary form­al­ity when writ­ing to a col­league in a for­eign coun­try. Be­fore long she began writ­ing by hand and sug­ges­ted they go to first names. After that, let­ters ad­dressed “Dear Ju­lia” and “Dear Yuri” made the long trek, usu­ally last­ing two to three weeks, between Berke­ley on the west­ern coast of the United States, to Len­in­grad, at the north­west­ern tip of the So­viet Uni­on.

1. Two people, two nations, two very different worlds

I wish to thank you for your kind let­ter of 22nd Feb­ru­ary. You have made an out­stand­ing con­tri­bu­tion to the solu­tion of Hil­bert’s tenth prob­lem and, in fact, to a great­er ex­tent it is your vic­tory.

 — Yuri to Ju­lia, 17 March 1970

Yuri’s solu­tion to Hil­bert’s Tenth Prob­lem grew out of earli­er work by Ju­lia as well as work by Mar­tin Dav­is and Hil­ary Put­nam. It’s not un­com­mon for young math­em­at­ic­al hot­shots to down­play pre­vi­ous work in or­der to fo­cus the glory on them­selves. Not Yuri. He showed a far more ideal­ist­ic spir­it in his ad­mir­ing, gen­er­ous reply (17 March 1970) to Ju­lia’s first let­ter.

From the start the cor­res­pond­ents were dis­posed to friend­ship and trust, al­most as if the polit­ic­al chasms that sep­ar­ated them didn’t ex­ist. Yet when they ex­changed these first let­ters in 1970, in the depths of the Cold War, the US and the (then) USSR had be­come im­plac­able en­emies, amass­ing rival nuc­le­ar ar­sen­als. In­tern­al polit­ics shaped the re­search cli­mate of the re­spect­ive math­em­at­ic­al com­munit­ies in pro­foundly dif­fer­ent ways.

In the USSR, So­viet premi­er Le­onid Brezh­nev had stepped up polit­ic­al re­pres­sion in the wake of Nikita Khrushchev’s de-Sta­lin­iz­a­tion policies. Cri­ti­ciz­ing the rul­ing party could land one in jail. Math­em­at­ic­al re­search op­er­ated with­in a dense thick­et of secrecy reg­u­la­tions, re­stric­tions on for­eign travel, and dis­crim­in­at­ory policies. Nev­er­the­less math­em­at­ics thrived. For gif­ted stu­dents the field provided an in­tel­lec­tu­al refuge from the ab­surdity and cor­rup­tion of the state. So­viet math­em­aticians were re­source­ful in cob­bling to­geth­er what his­tor­i­an Slava Ge­r­ovitch has called a “par­al­lel so­cial in­fra­struc­ture” [e14] by or­gan­iz­ing in­form­al sem­inars, study groups, and cor­res­pond­ence courses.

The US by com­par­is­on en­joyed far great­er so­cial free­dom but was blighted by ra­cial vi­ol­ence and deep eco­nom­ic di­vi­sions. The as­sas­sin­a­tion of Mar­tin Luth­er King Jr. in the fall of 1968 set off massive demon­stra­tions and civil un­rest. Uni­versity cam­puses be­came protest hot­spots as young people raged against the hy­po­crisy of a so­ci­ety that tol­er­ated the hor­ror of the Vi­et­nam war and the scourge of per­vas­ive in­equal­ity. Many US math­em­aticians, while de­plor­ing the vi­ol­ence sparked dur­ing demon­stra­tions, re­tained sym­pathy for the spir­it of un­com­prom­ising hon­esty that marked the protests. There was a good deal of soul-search­ing with­in the US math­em­at­ic­al com­munity about such mat­ters as the eth­ics of ac­cept­ing re­search sup­port from the mil­it­ary.

Against this back­drop, Ju­lia and Yuri began their re­mark­able cor­res­pond­ence, an ex­change made more pre­cious to each by the con­scious­ness of the gulf across which they reached. That they be­came friends so read­ily un­der­scores the power­ful al­lure of math­em­at­ics: its po­ten­tial to unite even dis­tant thinkers in a shared quest for un­der­stand­ing.

2. What is Hilbert’s 10th Problem?

I agreed months ago to talk to a sci­entif­ic so­ci­ety meet­ing on H10 to non-math­em­aticians. Just this minute I got a call from New York for the title of this talk. I star­ted to say Hil­bert’s tenth prob­lem and then I real­ized that most sci­ent­ists would not have heard of Hil­bert… Maybe I’ll call it “The re­volu­tion in di­o­phant­ine equa­tions”.

 — Ju­lia to Yuri, 11 Oc­to­ber 1973

Ju­lia gave that talk at the an­nu­al meet­ing of the Amer­ic­an As­so­ci­ation for the Ad­vance­ment of Sci­ence in San Fran­cisco in March 1974. In it she had to ex­plain what Hil­bert’s Tenth Prob­lem (H10) is, and that’s also a good place for us to be­gin.

The sub­ject of the prob­lem is Di­o­phant­ine equa­tions, which are poly­no­mi­al equa­tions in any num­ber of un­knowns and with in­teger coef­fi­cients, for which in­teger solu­tions are sought. Re­flect­ing their deep roots in an­tiquity, these equa­tions are named after Di­o­phantus of Al­ex­an­dria, who was act­ive in the third cen­tury A.D. and de­scribed them in his most im­port­ant work Arith­met­ica, large por­tions of which were lost. What sur­vived made its way to the early mod­ern world through Byz­antine copy­ists and via me­di­ev­al Ar­ab­ic sources in which cer­tain of the treat­ise’s equa­tions were re­stated and scru­tin­ized. In her now-clas­sic 1952 pa­per “Ex­ist­en­tial defin­ab­il­ity in arith­met­ic” [1], Ju­lia gave an ex­ample of a Di­o­phant­ine prob­lem stud­ied by Ar­ab math­em­aticians in the middle ages.

When in 1900 Dav­id Hil­bert presen­ted his fam­ous list of 23 prob­lems, a few spe­cial­ized solu­tion meth­ods had been found for lim­ited classes of Di­o­phant­ine equa­tions. A gen­er­al meth­od, one that would find the solu­tions of any equa­tion what­so­ever, seemed out of reach. So the tenth prob­lem on Hil­bert’s list asked for something that looked more mod­est: A meth­od that, when presen­ted with a Di­o­phant­ine equa­tion, would tell you wheth­er the equa­tion has a solu­tion in the in­tegers.

What H10 asks for, in today’s par­lance, is an al­gorithm. But at the time Hil­bert posed the prob­lem, a pre­cise math­em­at­ic­al defin­i­tion of al­gorithm was still in the fu­ture. That defin­i­tion came in the 1930s, through the work of such pi­on­eers as Alonzo Church, Kurt Gödel, Emil L. Post, and Alan Tur­ing. It then be­came pos­sible to prove that some al­gorithms one might hope for simply do not ex­ist — in oth­er words, to prove that some prob­lems are un­solv­able.

In a 1941 pa­per, Post wrote that H10 “begs for an un­solv­ab­il­ity proof”. In this way he con­nec­ted H10, which had un­til then been con­sidered part of num­ber the­ory, to lo­gic. Mar­tin Dav­is, then in his early 20s and a stu­dent of Post’s at City Col­lege in New York, read that state­ment and began a lifelong ob­ses­sion with H10. His fas­cin­a­tion was un­der­stand­able. Up to that time the only prob­lems that had been shown un­solv­able either resided in the realm of math­em­at­ic­al lo­gic or were de­pend­ent upon a cer­tain com­pu­ta­tion­al mod­el. H10 was dif­fer­ent. It was a nat­ur­al prob­lem with deep roots in math­em­at­ics, and one for which a solu­tion would be of wide in­terest.

Lo­gi­cians brought to Hil­bert’s ques­tion a new per­spect­ive, that of Di­o­phant­ine sets. A Di­o­phant­ine poly­no­mi­al can “rep­res­ent” a set in the fol­low­ing way. Sup­pose we have a Di­o­phant­ine equa­tion \( P(k, x_1, x_2, \dots x_n) = 0 \), where we think of \( k \) as a para­met­er and of the \( x_i \) as un­knowns. The set of all \( k \) for which the equa­tion has a solu­tion \( (x_1, x_2, \dots, x_n) \) is called a Di­o­phant­ine set rep­res­en­ted by \( P \). A simple ex­ample: The non-powers of 2 are rep­res­en­ted by \( k - (2x+1)y = 0 \).

Pos­ing the ques­tion “Which sets are Di­o­phant­ine?” brings in­to play power­ful con­cepts from lo­gic. A listable set comes equipped with an al­gorithm that can gen­er­ate, or list, the mem­bers of a set. A de­cid­able set has an al­gorithm that does a more dif­fi­cult job: When fed a num­ber, it re­turns “yes” if the num­ber is in the set and “no” oth­er­wise. A de­cid­able set is al­ways listable be­cause, by sys­tem­at­ic­ally feed­ing all in­tegers in­to the al­gorithm and re­cord­ing those for which the al­gorithm an­swers “yes”, you can list the mem­bers of the set. But the con­verse is false: There are listable sets for which no mem­ber­ship-de­cid­ing al­gorithm ex­ists. This asym­metry between listable and de­cid­able is at the root of many un­solv­ab­il­ity proofs.

In his doc­tor­al thes­is of 1950 [e1], Mar­tin Dav­is made what Yuri later called a “dar­ing hy­po­thes­is”: Every listable set is Di­o­phant­ine. If this were true, then there would ex­ist Di­o­phant­ine sets that are not de­cid­able, im­me­di­ately im­ply­ing that Hil­bert’s hoped-for al­gorithm would not ex­ist.

Ju­lia’s con­tri­bu­tions to the frame­work needed to solve H10 began to take shape at about the same time that Dav­is was com­plet­ing his thes­is. She could not en­joy a “nor­mal” ca­reer in math­em­at­ics, however: a ser­i­ous child­hood ill­ness had left her health in a del­ic­ate state. To un­der­stand her pas­sion for math­em­at­ics — a pas­sion that she and Yuri shared in their let­ters — we must con­sider the road she took to be­come a math­em­atician.

3. A childhood happy and sad

When I was in the 5th grade, I came down with rheum­at­ic fever and was kept out of school un­til the 9th grade. Then I went to a big school and did not know any oth­er stu­dents. So at lunch time I hid while eat­ing (I didn’t want the oth­er kids to know I didn’t have any friends) and then I walked around the school yard try­ing to look like I didn’t want to talk to any­one. This went on for sev­er­al months un­til fi­nally an­oth­er girl called out “Why do you al­ways stay by your­self? If you are not eat­ing with someone else, join us.” At last — I was res­cued!

 — Ju­lia to Yuri, 26 March 1973

This is one of the few places in the cor­res­pond­ence where Ju­lia talked about her child­hood. At the time she and Yuri began writ­ing to each oth­er, Ju­lia was not a pub­lic fig­ure, and the math­em­at­ic­al world was largely un­aware of the un­usu­al cir­cum­stances that gave rise to her in­tel­lec­tu­al life. It wasn’t un­til after her death that her older sis­ter, Con­stance Re­id, an au­thor of books about math­em­aticians, in­clud­ing an ac­claimed bio­graphy of Dav­id Hil­bert, set down on pa­per what we know about Ju­lia’s early child­hood. Her book Ju­lia: A Life in Math­em­at­ics [e11] presents what is es­sen­tially a brief auto­bi­o­graphy, con­sist­ing of Ju­lia’s first-per­son re­col­lec­tions, which she com­mu­nic­ated to Con­stance while strug­gling with the leuk­emia that even­tu­ally took her life in Ju­ly 1985.

Ju­lia Bow­man was born in 1919 in St. Louis, Mis­souri. Her early life was both happy and sad. She was two and Con­stance four when their moth­er died. The girls were sent to live with their grand­moth­er in Ari­zona, where Ju­lia’s earli­est memor­ies were of ar­ran­ging pebbles in the shad­ow of a gi­ant cac­tus. Their fath­er mar­ried again, to a wo­man whom Ju­lia al­ways thought of as her moth­er. When Ju­lia was five the fam­ily moved to San Diego. “Like the desert, it was open to ex­plor­a­tion and fantasy,” Ju­lia said in the auto­bi­o­graphy. There a baby sis­ter, Bil­lie Es­th­er, was born.

The ill­ness that Ju­lia men­tioned to Yuri kept her in bed for one year and out of school for two. With the help of a tu­tor she caught up to and even sur­passed what she would have learned in school dur­ing that time. She ex­celled above all in math­em­at­ics. After high school she en­rolled in the loc­al state col­lege and stud­ied all the math­em­at­ics she could. In her second year there, an­oth­er dis­aster struck. Her fath­er, in des­pair over eco­nom­ic ru­in brought on by the Great De­pres­sion, com­mit­ted sui­cide.

In the wake of per­son­al tragedy, Ju­lia proved re­si­li­ent: a few years later she found her­self “happy, really bliss­fully happy” after she began math­em­at­ics stud­ies at the Uni­versity of Cali­for­nia at Berke­ley. There she met and mar­ried Raphael Robin­son, who was eight years older and a ju­ni­or fac­ulty mem­ber. A fine math­em­atician and an ex­cel­lent teach­er and ex­pos­it­or, Raphael was a ma­jor in­flu­ence on Ju­lia’s math­em­at­ics. In 1948, two years be­fore Dav­is made his “dar­ing hy­po­thes­is”, Ju­lia earned a PhD in math­em­at­ics from Berke­ley.

The rheum­at­ic fever she suffered as a school­girl had so weakened Ju­lia’s heart that she was ad­vised not to try to have chil­dren. This left her quite de­pressed; math­em­at­ics was an ab­sorb­ing dis­trac­tion from this un­happy real­ity and later per­haps a solace. In 1960, at the age of 41, she un­der­went a then-new sur­gic­al pro­ced­ure that dra­mat­ic­ally im­proved her health. Nev­er­the­less she could not meet the de­mands of a full-time ca­reer. She oc­ca­sion­ally taught courses in the Berke­ley math­em­at­ics de­part­ment, where she was mainly known as “Pro­fess­or Robin­son’s wife.”

Not hav­ing to build a résumé meant Ju­lia could work on whatever she felt like. Dur­ing a stint at the RAND Cor­por­a­tion in 1949–1950, she wrote her only pa­per in the sub­ject of game the­ory. The ideas in this pa­per have be­come quite in­flu­en­tial, par­tic­u­larly with the rise of in­ter­net com­merce and the growth of al­gorithmic game the­ory. The pa­per has more than 1000 cita­tions in Google Schol­ar, many of them in the past twenty years. After RAND, in the mid-1950s, Ju­lia de­voted a lot of time to polit­ics, in­clud­ing the pres­id­en­tial cam­paigns of Ad­lai Steven­son. But she nev­er stopped think­ing about H10.

4. The Julia Robinson hypothesis

Tarski ori­gin­ally sug­ges­ted to me that it would be nice to show some par­tic­u­lar set such as the set of primes or the set of powers of 2 is not di­o­phant­ine. I quickly gave up and tried in­stead to show that they were di­o­phant­ine.

 — Ju­lia to Yuri, 5 Ju­ly 1971

Al­fred Tarski made this sug­ges­tion in 1948, the year when Ju­lia com­pleted her PhD un­der his su­per­vi­sion. Tarski had joined the fac­ulty at Berke­ley in 1942, and had pro­ceeded to build the de­part­ment in­to a ma­jor world cen­ter for lo­gic. Ju­lia was one of his first PhD stu­dents and be­nefited from his ex­cep­tion­ally broad per­spect­ive on math­em­at­ics. It was Tarski who planted the seed of her fas­cin­a­tion with H10.

The arith­met­ic re­la­tion “\( z \) is not equal to any power of 2” can be rep­res­en­ted by a Di­o­phant­ine equa­tion, as we saw earli­er: \( k \) is not a power of 2 if and only if the Di­o­phant­ine equa­tion \( k = (2x + 1)y \) has a solu­tion \( (x,y) \). But how do you show that the re­la­tion “\( z \) is equal to some power of 2” has a Di­o­phant­ine rep­res­ent­a­tion? That looks a lot harder.

In her 1952 pa­per “Ex­ist­en­tial defin­ab­il­ity in arith­met­ic” [1], Ju­lia for­mu­lated the no­tion of a re­la­tion of ex­po­nen­tial growth. This is a Di­o­phant­ine re­la­tion that grows fast, but not too fast: It out­runs any ex­po­nen­tial \( x^n \) for a fixed \( n \), but it is bounded by \( x^x \). The con­jec­ture that such a re­la­tion ex­ists came to be known as the Ju­lia Robin­son Hy­po­thes­is, or simply JR. Her pa­per showed that, if JR were true, then the set of powers of 2 — and in fact any ex­po­nen­tial — would be Di­o­phant­ine. Not only that: The primes would be Di­o­phant­ine. This last im­plic­a­tion was es­pe­cially sur­pris­ing be­cause the re­ceived wis­dom in num­ber the­ory said that there could be no for­mula for the primes.

Ju­lia presen­ted these res­ults at the In­ter­na­tion­al Con­gress of Math­em­aticians in 1950. This was the first time she met Mar­tin Dav­is, who also spoke at the Con­gress. “I re­mem­ber Mar­tin said there that he didn’t think one could solve Hil­bert’s prob­lem by look­ing at spe­cial cases of di­o­phant­ine re­la­tions and I said I couldn’t prove any gen­er­al the­or­ems,” Ju­lia later wrote to Yuri on 5 Ju­ly 1971. Mar­tin thought one might get to H10 by im­prov­ing one of his own the­or­ems about listable sets. “I guess we were both right,” Ju­lia wrote.

While a stu­dent at Len­in­grad State Uni­versity in the mid-1960s, Yuri read Ju­lia’s pa­per in Rus­si­an trans­la­tion and learned about JR. “I thought, ‘what [an] un­nat­ur­al con­di­tion’,” he told her in a let­ter from 23 June 1971. “But soon I saw that many at­tempts to define \( p^s \) led to this con­di­tion.”

JR is re­mark­able. It stood as a ful­crum between two dif­fer­ent scen­ari­os, both of which har­bored seem­ingly im­plaus­ible con­sequences. If JR were true, then there would be ab­so­lute bounds on both the de­gree and the num­ber of un­knowns needed to define any Di­o­phant­ine set. Some at the time took this as evid­ence that JR might not be true. But the op­pos­ite scen­ario, in which JR were false, car­ried con­sequences about the rate of growth of poly­no­mi­al func­tions that were equally as­ton­ish­ing. Ju­lia tried for many years to prove JR; at one point she even took the op­pos­ite tack and tried to dis­prove it.

In the late 1950s Mar­tin Dav­is and Hil­ary Put­nam worked on an ad­apt­a­tion of Dav­is’ dar­ing hy­po­thes­is (from his 1950 PhD thes­is). Rather than try­ing to show that listable sets are Di­o­phant­ine, they tried to show they are ex­po­nen­tial Di­o­phant­ine — in oth­er words, that listable sets can be rep­res­en­ted by Di­o­phant­ine equa­tions in which un­knowns can ap­pear as ex­po­nents. They al­most suc­ceeded, save for one un­proven as­sump­tion: the ex­ist­ence of ar­bit­rar­ily long se­quences of primes in arith­met­ic pro­gres­sion. (Such se­quences do ex­ist, but that fact was proven only in 2004, in a cel­eb­rated res­ult of Ben Green and Ter­ence Tao.)

When Dav­is and Put­nam sub­mit­ted their pa­per for pub­lic­a­tion, they also sent a copy to Ju­lia. Be­fore long she came up with an ar­gu­ment that cir­cum­ven­ted the then-un­proven as­sump­tion. Dav­is pro­posed with­draw­ing the pa­per in fa­vor of a new, three-au­thor pa­per that would in­cor­por­ate Ju­lia’s ideas. She and Put­nam agreed, and the pa­per, “The de­cision prob­lem for ex­po­nen­tial di­o­phant­ine equa­tions” [2], known by the nick­name DPR after the last names of the au­thors, has be­come a clas­sic. It showed that listable sets and ex­po­nen­tial Di­o­phant­ine sets are the same.

That pa­per, which ap­peared in 1961, threw the sig­ni­fic­ance of JR in­to vivid re­lief. JR pro­posed that ex­po­nen­ti­ation was Di­o­phant­ine, and DPR said listable sets are ex­po­nen­tial Di­o­phant­ine. Were JR true, then listable sets would be Di­o­phant­ine, and un­solv­ab­il­ity of H10 would im­me­di­ately fol­low.

5. How Yuri solved H10

I asked a friend of mine why he did not try to solve [H10]. He ex­plained his po­s­i­tion: try­ing to solve the 10th prob­lem is equi­val­ent to ski­ing down a moun­tain — you can be­come a world cham­pi­on but more likely you will break your neck.

 — Yuri to Ju­lia, 23 June 1971

Much like Mar­tin Dav­is, Yuri had an ir­res­ist­ible at­trac­tion to H10. And like Mar­tin, he had to dis­cip­line him­self away from it in or­der to make pro­gress on his doc­tor­ate. In the let­ter con­tain­ing the quo­ta­tion above, Yuri told Ju­lia the story of how he re­solved H10.2

Yuri was born in Len­in­grad in 1947. He showed math­em­at­ic­al tal­ent at a young age and ex­celled in the Math­em­at­ic­al Olympi­ad. He was se­lec­ted to par­ti­cip­ate in spe­cial math­em­at­ics classes out­side of school and when he was 15 went to a sum­mer pro­gram where the teach­ers in­cluded An­drei Kolmogorov and Vladi­mir Arnold. He entered uni­versity in Len­in­grad in 1965 and im­me­di­ately solved a dif­fi­cult prob­lem con­cern­ing cer­tain lo­gic­al sys­tems in­ven­ted by Emil L. Post.

It was Yuri’s ad­viser, Sergei Maslov, who sug­ges­ted Yuri work on H10. Maslov knew how close DPR had come to solv­ing H10 but thought the Amer­ic­ans must be on the wrong track be­cause their meth­ods hadn’t worked yet. He pro­posed that Yuri ap­proach the prob­lem by try­ing to es­tab­lish the un­solv­ab­il­ity of word equa­tions, be­cause they can be re­duced to Di­o­phant­ine equa­tions. Yuri did write some good pa­pers on the sub­ject, but it was a dead-end as far as H10 was con­cerned: In 1977, Gen­adii Makan­in proved that word equa­tions are solv­able.

Still Yuri re­mained fas­cin­ated by H10. He spent al­most all his free time try­ing to find a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth. One pro­fess­or began to tease Yuri, say­ing he would not be able to gradu­ate if he didn’t solve H10. Yuri didn’t need H10 to gradu­ate — but he needed something. So his earli­er work on Post ca­non­ic­al sys­tems be­came his PhD thes­is. In 1969 he gradu­ated and be­came a post­gradu­ate stu­dent at the Steklov In­sti­tute in Len­in­grad.

Late that year a col­league, Grigori Mints, told Yuri to rush to the lib­rary be­cause a new pa­per by Ju­lia had just ap­peared [3]. Yuri re­coun­ted his re­ac­tion in his let­ter to Ju­lia: “It is very well that Ju­lia Robin­son con­tin­ue her in­vest­ig­a­tions on Hil­bert’s tenth prob­lem but I my­self can­not waste time any­more.” But, Yuri wrote, God in­ter­vened: The Rus­si­an math­em­at­ic­al re­view­ing journ­al asked him to re­view the pa­per.

He then saw it con­tained a bril­liant new idea con­cern­ing the peri­od­icity of se­quences of solu­tions of a well known Di­o­phant­ine equa­tion called Pell’s equa­tion. His let­ter to Ju­lia quoted above (23 June 1971) re­coun­ted the drama of the first few days of Janu­ary 1970 when he figured out how to ad­apt this idea to a dif­fer­ent se­quence, namely, the Fibon­acci num­bers. This al­lowed him to show that the se­quence of Fibon­acci num­bers is Di­o­phant­ine, thereby es­tab­lish­ing the truth of JR — and the un­solv­ab­il­ity of H10.

This work earned him his DSc de­gree (sim­il­ar to a European Ha­bil­it­a­tion), awar­ded in 1973. Yuri soon got a per­man­ent po­s­i­tion as a re­search­er at the Steklov In­sti­tute in Len­in­grad. He has re­mained there throughout his ca­reer in the Labor­at­ory of Math­em­at­ic­al Lo­gic.

With four people hav­ing con­trib­uted de­cis­ively to the res­ol­u­tion of the mo­nu­ment­al H10, it’s re­mark­able that there was not even a hint of a pri­or­ity dis­pute among them. All four bent over back­wards to give cred­it to the oth­ers. The fi­nal res­ult has gone by vari­ous names in­clud­ing Matiy­a­sevich’s The­or­em and MRDP. Yuri him­self calls it DPRM.

Re­cently, Yuri ob­served to this au­thor3 that Ju­lia was “not an am­bi­tious per­son”. She just wanted to know the truth. She was not afraid that someone else might re­solve H10 be­fore her. Her only fear was that the proof, when it came, would be very dif­fi­cult and she would be too old to un­der­stand it. As she put it in her auto­bi­o­graphy, “I felt that I couldn’t bear to die without know­ing the an­swer.”

6. A counterintuitive consequence of H10

Raphael and I showed that 35 vari­ables is enough for a uni­ver­sal di­o­phant­ine equa­tion. Do you know a bet­ter res­ult? […] In view of Alan Baker’s work, it seems like num­ber the­or­ists would be very much in­ter­ested in the min­im­um num­ber needed.

 — Ju­lia to Yuri, 22 Oc­to­ber 1970

After Yuri’s break­through be­came known, he re­ceived many in­vit­a­tions to speak, in­clud­ing one to give an in­vited ad­dress at the In­ter­na­tion­al Con­gress of Math­em­aticians in Nice in Au­gust 1970. There Yuri met Mar­tin Dav­is for the first time, though not Ju­lia, as she did not at­tend. In Au­gust of 1971 Ju­lia and Yuri did meet at a con­fer­ence in Bucharest. Af­ter­ward Ju­lia to­geth­er with her hus­band Raphael traveled to the USSR to meet Yuri and his wife Nina in Len­in­grad.

Nice and Bucharest turned out to be ex­cep­tions. Yuri’s let­ters to Ju­lia men­tion sev­er­al in­vit­a­tions to speak that he had to de­cline be­cause of the So­viet gov­ern­ment’s re­stric­tions on travel. In par­tic­u­lar there was no chance for him to come to the US. As a res­ult dur­ing 1970 and 1971 Ju­lia lec­tured about his work at in­sti­tu­tions around the US. In the USSR, Yuri him­self gave a couple of talks about his work, as did Yuri Man­in. Man­in was in­vited for such lec­tures, Matiy­a­sevich ex­plained,4 be­cause at that time he him­self was not a very ex­per­i­enced speak­er, while Man­in was known to be an ex­cel­lent speak­er and could also de­scribe the H10 work in a way that would ap­peal to num­ber the­or­ists.

In 1969, Ju­lia had giv­en a talk on H10 at a meet­ing in Stony Brook. When it came time to write up her con­tri­bu­tion for the pro­ceed­ings volume, she had by then learned of Yuri’s solu­tion and wrote about that in­stead of pre­par­ing a manuscript of her ori­gin­al talk. Com­ment­ing on open prob­lems in her con­tri­bu­tion, she noted, “I think the most ex­cit­ing prob­lem is to find some in­ter­est­ing bound on the num­ber of vari­ables needed in a uni­ver­sal di­o­phant­ine equa­tion.”

The ex­ist­ence of such a “uni­ver­sal” equa­tion is an­oth­er coun­ter­in­tu­it­ive con­sequence of the fact that Di­o­phant­ine and listable sets are the same. A uni­ver­sal Di­o­phant­ine equa­tion takes the form \[ P(k,a, x_1,x_2,\dots x_n) = 0 \] for a Di­o­phant­ine poly­no­mi­al \( P \). For any listable set \( S \), there is a \( k \) such that \( P \) rep­res­ents \( S \); that is, \( P \) has a solu­tion \( (x_1, x_2, \dots x_n) \) if and only if \( a \) be­longs to \( S \).

As Ju­lia told Yuri in the let­ter quoted above (22 Oc­to­ber 1970), she be­lieved num­ber the­or­ists would be in­ter­ested in the min­im­um num­ber of un­knowns in a uni­ver­sal Di­o­phant­ine equa­tion. She men­tioned in par­tic­u­lar Alan Baker be­cause he had re­ceived the Fields Medal in 1970 for work shed­ding light on Di­o­phant­ine equa­tions in two un­knowns with de­gree great­er than two.

“I have not pre­cisely es­tim­ated the num­ber of vari­ables needed for [a] uni­ver­sal poly­no­mi­al,” Yuri replied on 13 Novem­ber 1970. “My very rough es­tim­ate was 100–120 vari­ables. Nev­er­the­less it seems to me that your fine es­tim­ate of 35 vari­ables can be re­duced.” He went on to out­line some of his ideas. The next sev­er­al let­ters con­tain close dis­cus­sion of the prob­lem. In her let­ter of 2 March 1971 Ju­lia asked Yuri if he wanted to write a joint pa­per.

Ever gra­cious, she ad­ded: “Or if you would like to write it up your­self it is OK with me.” Equally gra­cious, Yuri replied on 12 April 1971: “I would be very glad to have a joint pa­per with you.” It was Yuri’s first real col­lab­or­a­tion.

7. Two equals, sharing ups and downs

I re­ceived your let­ter yes­ter­day — just 5 days after you mailed! You are just full of new ideas — I read it with “Ah’s” and “Oh’s”. Un­for­tu­nately I am ter­ribly pressed for time right now so I can only tell you how im­pressed I am.

 — Ju­lia to Yuri, 17 June 1971

Ju­lia some­times taught in the UC Berke­ley math­em­at­ics de­part­ment, but be­cause her hus­band Raphael was on the fac­ulty, anti-nepot­ism rules pre­ven­ted her from hold­ing a reg­u­lar po­s­i­tion. There­fore she could not form­ally ad­vise PhD stu­dents. “In a real sense, Yuri was the gradu­ate stu­dent Ju­lia nev­er had,” Len­ore Blum has ob­served [e12]. Per­haps he was also in some sense the child Ju­lia nev­er had. Some of her let­ters struck a moth­erly tone, such as when she wrote on 4 June 1974, “Now, Yuri, please take care of your­self.”

Nev­er­the­less as col­lab­or­at­ors they were very much equals. When one of them came out with a good idea, there was praise from the oth­er. “Now about your new ideas,” Yuri wrote on 16 Au­gust 1972. “They are won­der­ful!”

And when one of them made an er­ror, there was en­cour­age­ment. “I must apo­lo­gize for send­ing you a let­ter with so many mis­takes,” was Yuri’s sheep­ish state­ment on 24 Feb­ru­ary 1971. “I am not a man one can rely on in veri­fy­ing proofs.” Yuri had men­tioned to Ju­lia sev­er­al times the in­flu­ence of A. A. Markov (son of the more fam­ous Markov of stochast­ic pro­cesses), who was known for his ex­treme care­ful­ness and in­sist­ence on de­tailed proofs.

Ju­lia replied on 2 March 1971 that she had already found the mis­takes Yuri had men­tioned but wasn’t bothered be­cause they left the fi­nal res­ult un­changed. She re­as­sured him, “Don’t worry every­one has made mis­takes — chances are that Markov did when he was young so he is try­ing to make up for it now.” Ju­lia also en­cour­aged Yuri’s ef­forts to es­cape from Markov’s pedant­ic writ­ing style, which ten­ded to ob­scure the main ideas.

Her sense of hu­mor again lightened the mood when two years later Yuri found a more ser­i­ous mis­take in their work on the uni­ver­sal Di­o­phant­ine equa­tion. They had as­sumed a cer­tain im­plic­a­tion about bi­no­mi­al coef­fi­cients, and he found an ob­vi­ous counter­example in­volving only the num­bers 2, 3, and 5. “I was com­pletely flab­ber­gas­ted,” wrote Ju­lia on 30 May 1973. “I wanted to crawl un­der a rock and hide from my­self!” She had men­tioned the im­plic­a­tion sev­er­al times to Raphael, who hadn’t ob­jec­ted. “He said he would have said ‘No’ if I had asked him if it were true. I guess I would have my­self if I had asked!” For­tu­nately, at the same time Yuri found the mis­take, he also found a way around it. But the pa­per had to be com­pletely re­writ­ten.

In a let­ter from 11 Septem­ber 1972, Yuri told Ju­lia in con­fid­ence that he had been try­ing to solve the four-col­or prob­lem. His idea was to ex­press, in the lan­guage of pre­dic­ate lo­gic, the con­di­tion of two coun­tries hav­ing the same col­or. If one as­sumed there ex­ists a graph that can­not be four-colored, Yuri guessed that these lo­gic­al ex­pres­sions would lead to a con­tra­dic­tion.

When his in­vest­ig­a­tions came to an im­passe, Ju­lia was en­cour­aging but prac­tic­al. “My ad­vice is to work on whatever in­terests you but don’t let any prob­lem be­come an ob­ses­sion,” she wrote on 13 Au­gust 1973. “If you have been spend­ing a great deal of time on the 4CP, then I would sug­gest that you take a va­ca­tion from it for awhile…(P.S. I don’t al­ways fol­low my own ad­vice.)” Three years later, on 16 Au­gust 1976, she sent the news that the four-col­or the­or­em had been proved. “I think it is very ex­cit­ing that it has been proved after all these years and it is also in­ter­est­ing (but a little dis­ap­point­ing too) that it took a com­puter to do it,” she wrote.

In 1972, a few months after his 25th birth­day, Yuri ex­pressed to Ju­lia a fear com­mon among math­em­aticians who achieve early suc­cess: Maybe he would nev­er again do any­thing great in math­em­at­ics. Ju­lia’s reply, on 28 Ju­ly 1972, com­bined her op­tim­ism with a dash of self-de­prec­at­ing wit: “Yuri, it would be silly to think that you wer­en’t go­ing to prove big­ger and bet­ter the­or­ems just be­cause you’re so old. After all every­body knows that girls are no good at math­em­at­ics at all. Be­sides if you look at the work of any great math­em­atician you’ll find that he didn’t just shriv­el up when he reached 25.”

8. Chipping away at the number of unknowns

With just 14 vari­ables we ought to be able to know every vari­able per­son­ally and why it has to be there and what lee­way it has.

 — Ju­lia to Yuri, 22 Feb­ru­ary 1972

Ju­lia and Yuri slowly chipped away at the num­ber of un­knowns in the uni­ver­sal equa­tion. From the ini­tial es­tim­ate of around 100 by Yuri and of 35 by Ju­lia and Raphael, they quickly got to 33, then 28. When they hit 26, Ju­lia cel­eb­rated the mo­ment when they “broke the ‘al­pha­bet­ic­al’ bar­ri­er” (5 Ju­ly 1971). Be­fore long they were at 23 and then 20, and by fall 1971 the num­ber stood at 14. Cor­rec­tion of over­sights caused a re­vi­sion up­ward to 16 the next spring, but soon they were back to 14 and by Au­gust 1971 they were at 13. When they hit 12 in Feb­ru­ary 1973, Ju­lia asked (5 Feb­ru­ary 1973) “Do you think we will ever fin­ish the pa­per?” Twelve proved to be a mirage, so it was back to 13. In May 1973 Yuri found the mis­take in­volving bi­no­mi­al coef­fi­cients, but his res­cue left the num­ber at 13. And there it re­mained.

How did they do it? The ba­sic con­struc­tion is im­pli­cit in the DPRM the­or­em. Giv­en an ar­bit­rary lo­gic­al re­la­tion, you can break it in­to smal­ler pieces and rep­res­ent each piece by Di­o­phant­ine equa­tions. Sum­ming the squares of those equa­tions gives you a Di­o­phant­ine equa­tion rep­res­ent­ing the re­la­tion. But this brute-force meth­od is very in­ef­fi­cient and causes the de­gree and the num­ber of un­knowns to ex­plode.

Us­ing ele­ment­ary num­ber the­ory, Ju­lia and Yuri de­veloped clev­er re­la­tion-com­bin­ing meth­ods that al­lowed them to carry out this pro­cess more ef­fi­ciently. The main idea was to get some of the un­knowns to play more than one role. For ex­ample, to rep­res­ent the lo­gic­al con­di­tions \( a\geq b \) and \( (c+1)\mkern1mu|\mkern1mu d \), one could use two un­knowns \( x \) and \( y \) and two equa­tions \( a=b+x \) and \( (c+1)y=d \). More eco­nom­ic­al would be to in­tro­duce only one un­known \( z \) and one equa­tion for both con­di­tions: \( (c+1)(d+1)a=(c+1)(d+1)b+(c+1)z+d \). They searched as­sidu­ously for such small eco­nom­ies, bring­ing to bear all the num­ber-the­or­et­ic in­tu­ition they could muster.

Writ­ing up the pa­per took quite a while. “It seems to me that we had little trouble in col­lab­or­at­ing math­em­at­ic­ally on a 4-week turn­around time but it is hope­less when it comes to writ­ing the res­ults up,” Ju­lia wrote on 15 Feb­ru­ary 1974. “[B]y the time you could an­swer a ques­tion, it was no longer rel­ev­ant and be­sides when I tried to ex­plain why I didn’t fol­low your sug­ges­tions I real­ized it would be like writ­ing the whole pa­per over again.” The pa­per was fi­nally pub­lished in 1975 [4].

Mid­way through that year Yuri dis­covered a new meth­od for re­du­cing the num­ber of un­knowns, us­ing an old the­or­em of E. Kum­mer. Ju­lia once called this re­mark­able the­or­em a “gold mine” for con­struct­ing Di­o­phant­ine equa­tions. It com­bines the “num­ber” view­point on in­tegers, in which fac­tor­iz­a­tion and di­vis­ib­il­ity prop­er­ties come in­to play, with the “word” view­point, in which in­tegers are viewed as strings of sym­bols with a po­s­i­tion­al nota­tion and with op­er­a­tions like con­cat­en­a­tion.

Yuri’s new meth­od sud­denly brought the num­ber down to 9. “What a sur­prise to learn of your new im­prove­ment!” Ju­lia wrote on 8 June 1975. “Raphael said he thought 13 un­knowns would prob­ably be the re­cord for ‘gen­er­a­tions’.” She stud­ied care­fully Yuri’s ideas and was so en­thu­si­ast­ic that she spoke about them at a num­ber the­ory meet­ing in As­ilo­mar that year. En­cour­aging him to write up his res­ults, she stead­fastly de­clined his sug­ges­tion that she be a coau­thor. “I have told every­one that it is your im­prove­ment and in fact I would feel silly to have my name on it,” she wrote on 2 Oc­to­ber 1976. “If I could make some con­tri­bu­tion it would be dif­fer­ent.”

In Oc­to­ber 1975 Ju­lia wrote to Yuri about two Berke­ley PhD stu­dents, Le­onard Adle­man and Ken­neth Manders, who had taken a course she had taught about Yuri’s H10 work. “Len and Ken”, as she called them, had star­ted think­ing about com­pu­ta­tion­al com­plex­ity as­pects of di­o­phant­ine prob­lems, and Ju­lia real­ized that Yuri’s 9-un­knowns meth­od would sim­pli­fy it. Since the meth­od was un­pub­lished, she gave the stu­dents a copy of the rel­ev­ant let­ter from Yuri. Adle­man and Manders were able to use Yuri’s work and wrote sev­er­al pa­pers to­geth­er.

Yuri nev­er pub­lished the full de­tails of his 9-un­knowns res­ult. In his In­tel­li­gen­cer art­icle [e9] he wrote that he would not have got­ten this res­ult without Ju­lia’s in­spir­a­tion and there­fore did not want to pub­lish on his own. The res­ult fi­nally ap­peared in print in 1982, in a pa­per by his col­lab­or­at­or James P. Jones, who gave full cred­it to Yuri [e6].

9. A competing claim, a trusted confidante

[M]athem­aticians should be able to trust one an­oth­er.

 — Ju­lia to Yuri, 7 Novem­ber 1974

Ju­lia’s ideal­ist­ic ap­proach to math­em­at­ics was part of her per­son­al­ity. But it also re­flec­ted her cir­cum­stances. Free of the need to build a ca­reer, she did not have to deal with com­pet­it­ive pres­sures in math­em­at­ics. When oth­ers faced them though, she showed em­pathy. They form a run­ning theme in the let­ters, as Yuri con­fided in her about a com­pet­ing claim that arose soon after his res­ol­u­tion of H10.

News of Yuri’s feat spread quickly around the USSR in Janu­ary and Feb­ru­ary 1970. He gave his first pub­lic lec­ture on the res­ult at the end of Janu­ary. After the lec­ture Gregory Ceĭt­in asked Yuri for per­mis­sion to speak on the work in Nov­os­ibirsk, and Yuri agreed. It was Ceĭt­in’s Nov­os­ibirsk lec­ture that John Mc­Carthy at­ten­ded and that was the source of the notes he sent to Ju­lia in Feb­ru­ary 1970. That same month Yuri mailed a copy of his manuscript to a col­league in Kiev. Not long after these events, word cir­cu­lated that 17-year-old Gregory Chud­novsky, then liv­ing in his birth­place of Kiev, claimed he had in­de­pend­ently re­solved H10.

This was not a pri­or­ity dis­pute, as the pub­lished re­cord makes clear. Yuri’s four-page pa­per con­tain­ing his proof ap­peared in Dok­lady Aka­demii Nauk with a re­ceived date of 5 Feb­ru­ary 1970 [e3]. A two-page pa­per by Chud­novsky, claim­ing H10 but without a proof, ap­peared in Us­pekhi Matem­aticheskikh Nauk, with a re­ceived date of 30 March 1970 [e4]. Chud­novsky did in­clude a proof in a 1971 pre­print is­sued by the Math­em­at­ics In­sti­tute of the Ukrain­i­an Academy of Sci­ences [e5] (it was pub­lished only much later, in 1984 [e7]).

The ques­tion, then, was wheth­er Chud­novsky had in­de­pend­ently found a proof. When Yuri wrote to Chud­novsky to try to cla­ri­fy the situ­ation, his let­ters went un­answered. In Septem­ber 1971, upon her re­turn from Len­in­grad to Berke­ley, Ju­lia found that Chud­novsky had sent her a copy of his pre­print. She replied in a friendly man­ner, pos­ing dir­ect and spe­cif­ic ques­tions about his claim to an in­de­pend­ent res­ol­u­tion of H10. Her let­ter too went un­answered.

In Decem­ber 1972, Ju­lia learned second-hand that An­dré Weil, after a vis­it to Kiev, be­lieved Chud­novsky’s work had been in­de­pend­ent. Ju­lia then ex­changed let­ters with Weil. In his reply, Weil told her that Chud­novsky suffered from a long-term neur­omus­cu­lar dis­ease called my­as­thenia grav­is, which since child­hood had kept him bedrid­den and in need of con­stant care from his fam­ily. Weil had not raised the ques­tion about in­de­pend­ence dir­ectly with Chud­novsky but heard about it from oth­ers in Kiev. On this basis, and out of con­cern about dis­cour­aging the ob­vi­ously tal­en­ted Chud­novsky, Weil sug­ges­ted that Yuri pub­licly ac­know­ledge that Chud­novsky’s proof was in­de­pend­ent.

However, giv­en the pub­lished re­cord and Chud­novsky’s con­tin­ued si­lence, Yuri felt he had no basis for a pub­lic ac­know­ledg­ment. Frus­trated by Chud­novsky’s “am­bigu­ous for­mu­la­tions,” Yuri wrote to Ju­lia on 3 March 1973, “I can’t real­ize why a man who in­deed found his proof in­de­pend­ently could not write about it ex­pli­citly.” In this and oth­er let­ters he also noted that Chud­novsky did not give prop­er at­tri­bu­tion to the con­tri­bu­tions of oth­ers and seemed not to dis­tin­guish between what he had done him­self and what he had learned from oth­ers.

In her reply on 26 March 1973, Ju­lia dis­cussed what she called Chud­novsky’s “ex­pan­ded pa­per,” which pre­sum­ably is the 1971 pre­print. In it, Chud­novsky claimed three dif­fer­ent ways to re­solve H10. The first, proved in full, bears sim­il­ar­ity to Yuri’s meth­od; it bears even more sim­il­ar­ity to proofs found shortly after Yuri’s H10 work by Mar­tin Dav­is and Nikolai Kos­sovsky. Chud­novsky’s second and third ways of resolv­ing H10 — one based on an earli­er res­ult of Mar­tin Dav­is [e2] and the oth­er on mod­el the­ory — are not giv­en full proofs. Ju­lia seemed per­plexed that, in these last two at­tempts at proof, Chud­novsky “leaves out the cru­cial ar­gu­ment.”

On the one hand, she was in­clined to be­lieve Chud­novsky had an in­de­pend­ent proof be­cause his col­leagues in Kiev said so. “[N]o one can be a char­lat­an math­em­atician for long,” she wrote. On the oth­er hand, she noted, “it seems hard to as­sert it as a fact.” “An­dré Weil just be­lieved what he was told in Kiev and did not take in­to ac­count how it was Chud­novsky him­self who had be­clouded the is­sue,” Ju­lia con­cluded in that same let­ter. “It seems to me that your ref­er­ences to Chud­novsky have been ab­so­lutely cor­rect.”

She and Yuri still faced the ques­tion of wheth­er to refer to Chud­novsky’s work in their own pa­per. In the end they in­cluded Chud­novsky’s 1970 pa­per in the bib­li­o­graphy of the 13-un­knowns pa­per, as well as that of a short­er pa­per they wrote around the same time in Rus­si­an, for in­clu­sion in a volume to hon­or Markov.

The story has an ad­di­tion­al di­men­sion. Chud­novsky is Jew­ish, and he has said that anti-semit­ism un­der­mined his claim about H10.5 Anti-semit­ic dis­crim­in­a­tion was rife in the So­viet math­em­at­ic­al com­munity and of­ten in­si­di­ous, tak­ing place out­side of pub­lic view.

On 24 Ju­ly 1977, the New York Times car­ried a short item6 say­ing Chud­novsky’s par­ents had been beaten up in a Kiev street, pre­sum­ably in re­tali­ation for their ap­plic­a­tion to emig­rate from the So­viet Uni­on to seek bet­ter med­ic­al treat­ment for their son. After read­ing this news, Ju­lia wrote a sym­path­et­ic note to Chud­novsky and un­der­took ef­forts to help the fam­ily emig­rate. The main pro­ponent of these ef­forts was Ed­win He­witt, a math­em­atician at the Uni­versity of Wash­ing­ton who had the year be­fore traveled to Kiev and col­lab­or­ated with Chud­novsky [e8].

The fam­ily was able to leave for France in Au­gust 1977. Not long there­after, Chud­novsky wrote to Ju­lia from Par­is and thanked her for her help. When Ju­lia told Yuri of Chud­novsky’s let­ter, she ex­pressed the hope that Chud­novsky would vis­it Berke­ley. But it isn’t clear wheth­er he did — or in­deed wheth­er Ju­lia ever met him.

In sum­mer 1978 Yuri sent Ju­lia two volumes in what be­came a five-volume Rus­si­an math­em­at­ic­al en­cyc­lo­pe­dia and poin­ted out one art­icle that men­tioned her. “This art­icle was ori­gin­ally writ­ten by me some­when [sic] in 1971 and gave a ref­er­ence to Chud­novsky’s pa­per too,” Yuri wrote on 18 Ju­ly 1978. “Now that he has left this coun­try I was in­formed that the ref­er­ence to his pa­per had been elim­in­ated by the ed­it­ors of the En­cyc­lo­pe­dia.”

Ju­lia found the en­cyc­lo­pe­dia “very im­press­ive” but she too noted the cen­sor­ing of the names of many Jew­ish math­em­aticians. “In it­self it seems very petty but more ser­i­ous things are be­ing done to Jew­ish math­em­aticians in your coun­try,” she wrote on 11 Decem­ber 1978, point­ing to re­cently pub­lished evid­ence.7 “I know it is al­most im­possible for one per­son to stand alone against such things but math­em­at­ics would be in tat­ters if all the con­tri­bu­tions by Jews were re­moved.” Among the Jew­ish math­em­aticians men­tioned in her let­ter was their own coau­thor Mar­tin Dav­is.

This is the only place in the cor­res­pond­ence where Ju­lia dir­ectly cri­ti­cized the USSR. She might have been cir­cum­spect out of con­cern about get­ting Yuri in­to trouble with the So­viet au­thor­it­ies, who were mon­it­or­ing the cor­res­pond­ence. This mon­it­or­ing was dis­cussed dir­ectly only once, in a let­ter Yuri wrote in 1976; he was in Fin­land at the time, so he could be sure the So­viet au­thor­it­ies would not see it.

10. A masterpiece of exposition

The meet­ing at DeKalb was great. I went to about half the talks and found them ex­hil­ar­at­ing. There was a cer­tain old-fash­ion [sic] air about them nat­ur­ally but this helped to make them un­der­stand­able. Many people praised our talk and they were talk­ing about the con­tent.

 — Ju­lia to Yuri, 4 June 1974

When Ju­lia learned that Yuri had been in­vited to speak at an Amer­ic­an Math­em­at­ic­al So­ci­ety meet­ing in April 1974 at North­ern Illinois Uni­versity in DeKalb, she was ex­cited. “It is great news and I hope you can ex­tend your vis­it to Cali­for­nia,” she wrote on 21 Janu­ary 1974. Oth­er in­sti­tu­tions were cer­tain to ex­tend in­vit­a­tions, and gradu­ate stu­dents would be es­pe­cially eager to meet him. She re­called that, when the news had ar­rived in Berke­ley that a 22-year-old Rus­si­an had solved H10, “all of the stu­dents were tre­mend­ously ex­cited and they still look back on it as the high point of their gradu­ate stud­ies.” But these hopes were dashed: Once again Yuri could not get per­mis­sion to travel.

The main event of the meet­ing was a sym­posi­um titled “Math­em­at­ic­al De­vel­op­ments Arising from the Hil­bert Prob­lems,” in which top math­em­aticians were re­cruited to speak, one on each of the 23 prob­lems. In Yuri’s stead, Ju­lia ac­cep­ted the in­vit­a­tion to speak; her one con­di­tion was that Mar­tin Dav­is should be in­vited to in­tro­duce her. She and Mar­tin “were both dis­ap­poin­ted and in­dig­nant that the speak­er had to be changed,” Ju­lia wrote on 4 June 1974. (By “the speak­er” she meant Yuri. She may have writ­ten in this el­lipt­ic­al way out of con­cern about mon­it­or­ing of their let­ters.)

For the DeKalb sym­posi­um pro­ceed­ings, Ju­lia pro­posed to Yuri a three-au­thor pa­per with Mar­tin. Mar­tin vis­ited Berke­ley over the fol­low­ing sum­mer, and he and Ju­lia met reg­u­larly to work on the pa­per. In her let­ters to Yuri, Ju­lia was care­ful to so­li­cit his in­put and re­as­sure him that they would not move to pub­lic­a­tion without his okay. Mar­tin was the one who brought all the pieces to­geth­er and as­sembled the fi­nal art­icle, mainly be­cause he was at the Cour­ant In­sti­tute at New York Uni­versity and could get the art­icle typed by Cour­ant’s ex­cel­lent math­em­at­ic­al typ­ist, Con­nie Engle.

Yuri was es­pe­cially in­ter­ested in con­nec­tions between Di­o­phant­ine equa­tions and fam­ous open prob­lems like the Riemann Hy­po­thes­is. It’s easy to un­der­stand why. The ques­tion “Is the Riemann Hy­po­thes­is true?” is equi­val­ent to the ques­tion of wheth­er a cer­tain Di­o­phant­ine equa­tion has no solu­tions. That the truth of such a cent­ral ques­tion boils down to solv­ab­il­ity of a single poly­no­mi­al equa­tion is as­ton­ish­ing. Yuri’s let­ters to Ju­lia from this time con­tain long pas­sages on this theme, which were then in­cor­por­ated in­to the joint ef­fort.

With the title “Hil­bert’s tenth prob­lem: Di­o­phant­ine equa­tions: pos­it­ive as­pects of a neg­at­ive solu­tion,” the pa­per ap­peared in 1976 [5]. A re­view by Craig Smoryn­ski in the Journ­al of Sym­bol­ic Lo­gic called the pa­per “a mas­ter­piece […]. The sur­vey is thor­ough; the bib­li­o­graphy is com­plete; and the ex­pos­i­tion is flaw­less.” The pa­per is an el­eg­ant test­a­ment to the en­thu­si­asm of the three au­thors for a prob­lem close to their hearts and makes a com­pel­ling case for the im­press­ive power of Di­o­phant­ine equa­tions.

About that equa­tion that cap­tures the Riemann Hy­po­thes­is: Con­struct­ing it is straight­for­ward, al­most routine. So it would be pos­sible to write the equa­tion down, though this is not done in the pa­per. It would not be a pretty sight, nor an edi­fy­ing one. As Dav­is has put it, “This is an equa­tion that only its moth­er could love” [e13].

11. Learning Russian, gathering mushrooms

I en­joy your let­ters wheth­er they are about math­em­at­ics or mush­rooms or any­thing else.

 — Ju­lia to Yuri, 27 Janu­ary 1975

In some ways Ju­lia’s let­ters con­form to the ste­reo­type of the cheer­ful, pos­it­ive-minded Amer­ic­an. She in­cludes chatty asides about all kinds of things — red­wood trees, bike rid­ing, birth­day cakes, whale watch­ing. While Yuri’s let­ters are more re­served and less vol­uble, from the let­ters of both flow warmth, es­teem, and trust.

In fact, what looks like re­serve in Yuri’s let­ters might simply have been an ar­ti­fact of his hav­ing to write in a lan­guage that is not his moth­er tongue. Nev­er­the­less he had no trouble ex­press­ing him­self. “Your Eng­lish is very good,” Ju­lia wrote on 2 March 1971. “[T]he few mis­takes have been where you are lo­gic­al but Eng­lish isn’t.”

Soon after she began writ­ing to Yuri, Ju­lia un­der­took an en­thu­si­ast­ic ef­fort to learn his lan­guage. As prac­tice she some­times in­cluded a para­graph or two in Rus­si­an, and Yuri re­spon­ded in kind. In speak­ing Rus­si­an she struggled to roll her r’s. “At first I was sure I could nev­er teach my tongue to vi­brate,” she wrote on 31 May 1971. “[I]t was like telling my ears to wag!” When their col­lab­or­a­tion got un­der way, stick­ing to Eng­lish proved more prac­tic­al. Yuri of­ten asked Ju­lia for ad­vice on Eng­lish, and her replies were al­ways per­spic­a­cious.

And they really did dis­cuss mush­rooms. After Yuri told Ju­lia he had for­aged for wild mush­rooms, she wor­ried that he would get poisoned and sent him an art­icle about the Aman­ita phal­loides, or death cap mush­room. You can al­most hear Yuri’s kindly chuck­ling as he re­as­sured her in a let­ter on 27 Decem­ber 1974: The death cap “is very well known in this coun­try,” he wrote. “Nobody even chil­dren would ever take it in hand.”

Ju­lia was bet­ter able to cir­cu­late in the math­em­at­ic­al com­munity than was Yuri, and she of­ten told him about people she had met at con­fer­ences. In a let­ter from 7 Ju­ly 1978, she talked about a sym­posi­um she had at­ten­ded the pre­vi­ous month, for Steph­en Kleene’s sev­en­ti­eth birth­day. “I met our friend Craig Smoryn­ski for the first time,” Ju­lia said. Smoryn­ski, who had got­ten a PhD in lo­gic in 1973, cor­res­pon­ded with both Ju­lia and Yuri and is men­tioned sev­er­al times in the let­ters. “[Craig] pre­tends to be very cyn­ic­al and feels that people are mak­ing fun of him when they aren’t. So he feels like an out­sider but of course we all are. I like him and ad­mire him very much.”

After at­tend­ing the In­ter­na­tion­al Con­gress of Math­em­aticians in Van­couver in Au­gust 1974, Ju­lia told Yuri that a few people there had said he should have got­ten a Fields Medal. “[T]he only one I can identi­fy was [Paul] Er­dős,” she wrote on 11 Septem­ber 1974. “Ac­tu­ally 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 Bom­bieri’s total work was so great he cer­tainly de­served one and you were still quite young […]. Ac­tu­ally I don’t think it makes much sense to try to com­pare math­em­aticians. I would just as soon let the phys­i­cists fight over No­bel prizes while we praise all good work.”

12. Not the “first this or that,” just a mathematician

Raphael says to thank you for get­ting me elec­ted to our Na­tion­al Academy of Sci­ences. If you hadn’t solved H10, I’m sure no one would have even pro­posed my name. Of course it was prob­ably help­ful that I am a wo­man too. In fact, I guess I’m the first wo­man to be elec­ted in the math­em­at­ics sec­tion. I can think of oodles of people who be­long in be­fore I do but it is sort of fun to get all the at­ten­tion for a bit.

 — Ju­lia to Yuri, 16 Au­gust 1976

Elec­tion to the Na­tion­al Academy of Sci­ences left the ever-mod­est Ju­lia pleased but em­bar­rassed. Yuri saw no need for em­bar­rass­ment. “I don’t think that Raphael is right,” he de­clared when he sent his con­grat­u­la­tions on 24 Septem­ber 1976. “[C]er­tainly, the [re­verse] im­plic­a­tion is true: you could be elec­ted without my con­tri­bu­tion to H10 but I could not com­plete the solu­tion without your works as back­ground.”

After Ju­lia’s elec­tion, the Uni­versity of Cali­for­nia at Berke­ley, where she had oc­ca­sion­ally taught courses, sud­denly made her a pro­fess­or. “The uni­versity was sort of em­bar­rassed that I wasn’t em­ployed so they claimed I was a ‘lec­turer’ but I really wasn’t,” she told Yuri in the same let­ter quoted above (16 Au­gust 1976). The Uni­versity gave her a re­duced teach­ing load that she could man­age without com­prom­ising her health. Oth­er dis­tinc­tions rolled in, such as an hon­or­ary de­gree from Smith Col­lege, a Ma­cAr­thur “geni­us” Award, and pres­id­ency of the Amer­ic­an Math­em­at­ic­al So­ci­ety. Ju­lia was also in the news out­side aca­demia, even ap­pear­ing on a list of the 100 most out­stand­ing wo­men in Amer­ica pub­lished by the Ladies Home Journ­al.

While she was un­com­fort­able be­ing known as “the first wo­man this or that”, as she put it in her auto­bi­o­graphy, she was aware of her sig­ni­fic­ance as a role mod­el. “I have al­ways tried to do everything I could to en­cour­age tal­en­ted wo­men to be­come re­search math­em­aticians.” She did this in a quiet, per­son­al way, without fan­fare.

Ju­lia would prob­ably be em­bar­rassed to know that she is now so fam­ous that there is even a pro­gram called the Ju­lia Robin­son Math­em­at­ics Fest­iv­al, which since 2007 has sponsored math­em­at­ic­al activ­it­ies for young people around the world. But she would have liked the fest­iv­al’s stated aim, “to in­spire joy with math.” It’s a joy she knew in­tim­ately.

13. Reaching across time and place and culture

You know, Yuri, usu­ally when I write a let­ter I can’t think of much to say and have a hard time filling one page but to you it is dif­fer­ent.

 — Ju­lia to Yuri, 5 Ju­ly 1971

When her cor­res­pond­ence with Yuri began, Ju­lia’s life was settled. She had been mar­ried for close to 30 years and had long ac­cep­ted that her two-per­son fam­ily with Raphael could not in­clude chil­dren. Her let­ters spoke of din­ners with long-stand­ing friends Der­rick and Emma Lehmer, trips to math­em­at­ics meet­ings with an­oth­er old friend Lisl Gaal, bike rides around the Bay Area, Thanks­giv­ing with the fam­ily of her sis­ter Con­stance Re­id.

Yuri was at a far more event­ful time of life. At 22 he was pre­par­ing for his wed­ding, fin­ish­ing his time as a stu­dent, start­ing out as a math­em­atician. His let­ters tell of a new apart­ment, his wife’s long ill­ness, her re­cov­ery, the birth of their daugh­ter Dasha (“I felt like jump­ing up and dan­cing around the room as I read your let­ter,” was Ju­lia’s re­ac­tion on 2 June 1979. “I do wish I could hold her now and see her grow up.”).

In an art­icle that ap­peared in 1996 [e10], a dec­ade after Ju­lia’s death, her sis­ter Con­stance quoted something that Ju­lia once said to a group of young people: Ju­lia thought of math­em­aticians “as form­ing a na­tion of our own without dis­tinc­tions of geo­graph­ic­al ori­gins, race, creed, sex, age, or even time (the math­em­aticians of the past and you of the fu­ture are our col­leagues too) — all ded­ic­ated to the most beau­ti­ful of the arts and sci­ences.” It was this ro­mantic view of math­em­at­ics that al­lowed Ju­lia and Yuri to reach across time and place and cul­ture to form a friend­ship. They met in per­son only a couple of times; their few phone calls were marked by dif­fi­culties un­der­stand­ing each oth­er. Their friend­ship really took place in their let­ters. Suf­fused with art­less de­light at find­ing deep res­on­ance in a far-flung cor­res­pond­ent, the let­ters trace the meet­ing of two minds de­voted to the truth and beauty of math­em­at­ics.

14. Acknowledgments

The au­thor would like to thank Mar­tin Dav­is, Yuri Matiy­a­sevich, Sheila New­bery, and Car­ol Wood.


[1] J. Robin­son: “Ex­ist­en­tial defin­ab­il­ity in arith­met­ic,” Trans. Am. Math. Soc. 72 : 3 (1952), pp. 437–​449. MR 48374 Zbl 0047.​24802 article

[2] M. Dav­is, H. Put­nam, and J. Robin­son: “The de­cision prob­lem for ex­po­nen­tial di­o­phant­ine equa­tions,” Ann. Math. (2) 74 : 3 (November 1961), pp. 425–​436. MR 133227 Zbl 0111.​01003 article

[3] J. Robin­son: “Un­solv­able di­o­phant­ine prob­lems,” Proc. Am. Math. Soc. 22 : 2 (1969), pp. 534–​538. MR 244046 Zbl 0182.​01901 article

[4] Y. Mati­jasevič and J. Robin­son: “Re­duc­tion of an ar­bit­rary Di­o­phant­ine equa­tion to one in 13 un­knowns,” Acta Arith. 27 (1975), pp. 521–​553. MR 387188 Zbl 0279.​10019 article

[5] M. Dav­is, Y. Mati­jasevič, and J. Robin­son: “Hil­bert’s tenth prob­lem: Di­o­phant­ine equa­tions: Pos­it­ive as­pects of a neg­at­ive solu­tion,” pp. 323–​378 in Math­em­at­ic­al de­vel­op­ments arising from Hil­bert prob­lems (DeKalb, IL, 13–17 May 1974), Part 2. Edi­ted by F. E. Browder. Pro­ceed­ings of Sym­po­sia in Pure Math­em­at­ics 28. 1976. With a loose-leaf er­rat­um. MR 432534 Zbl 0346.​02026 incollection