Celebratio Mathematica

The name of Ju­lia Robin­son can­not be sep­ar­ated from Hil­bert’s tenth prob­lem. This is one of the 23 prob­lems stated by Dav­id Hil­bert in 1900. The sec­tion of his fam­ous ad­dress [e1] de­voted to the tenth prob­lem is so short that it can be cited here in full:

10. De­term­in­a­tion of the Solv­ab­il­ity of a Di­o­phant­ine Equa­tion
Giv­en a Di­o­phant­ine equa­tion with any num­ber of un­known quant­it­ies and with ra­tion­al in­teg­ral nu­mer­ic­al coef­fi­cients: To de­vise a pro­cess ac­cord­ing to which it can be de­term­ined by a fi­nite num­ber of op­er­a­tions wheth­er the equa­tion is solv­able in ra­tion­al in­tegers.

The tenth prob­lem is the only one of the 23 prob­lems that is (in today’s ter­min­o­logy) a de­cision prob­lem; i.e., a prob­lem con­sist­ing of in­fin­itely many in­di­vidu­al prob­lems each of which re­quires a def­in­ite an­swer: YES or NO. The heart of a de­cision prob­lem is the re­quire­ment to find a single meth­od that will give an an­swer to any in­di­vidu­al sub­prob­lem. Since Di­o­phantus’s time, num­ber-the­or­ists have found solu­tions for a large num­ber of Di­o­phant­ine equa­tions and also have es­tab­lished the un­solv­ab­il­ity of a large num­ber of oth­er equa­tions. Un­for­tu­nately, for dif­fer­ent classes of equa­tions and even for dif­fer­ent in­di­vidu­al equa­tions, it was ne­ces­sary to in­vent dif­fer­ent spe­cif­ic meth­ods. In the tenth prob­lem, Hil­bert asks for a uni­ver­sal meth­od for de­cid­ing the solv­ab­il­ity of Di­o­phant­ine equa­tions.

A de­cision prob­lem can be solved in a pos­it­ive or in a neg­at­ive sense, by dis­cov­er­ing a prop­er al­gorithm or by show­ing that none ex­ists. The gen­er­al math­em­at­ic­al no­tion of al­gorithm was de­veloped by A. Church, K. Gödel, A. Tur­ing, E. Post, and oth­er lo­gi­cians only 30 years later, but, in his lec­ture [e1], Hil­bert foresaw the pos­sib­il­ity of neg­at­ive solu­tions to some math­em­at­ic­al prob­lems.

I have to start the story of my col­lab­or­a­tion with Ju­lia Robin­son by telling about my own in­volve­ment in the study of Hil­bert’s tenth prob­lem. I heard about it for the first time at the end of 1965 when I was a sopho­more in the De­part­ment of Math­em­at­ics and Mech­an­ics of Len­in­grad State Uni­versity. At that time I had already ob­tained my first res­ults con­cern­ing Post’s ca­non­ic­al sys­tems, and I asked my sci­entif­ic ad­viser, Sergei Maslov (see [e9]), what to do next. He answered: “Try to prove the al­gorithmic un­solv­ab­il­ity of Di­o­phant­ine equa­tions. This prob­lem is known as Hil­bert’s tenth prob­lem, but that does not mat­ter to you.” — “But I haven’t learned any proof of the un­solv­ab­il­ity of any de­cision prob­lem.” — “That also does not mat­ter. Un­solv­ab­il­ity is nowadays usu­ally proved by re­du­cing a prob­lem already known to be un­solv­able to the prob­lem whose un­solv­ab­il­ity one needs to es­tab­lish, and you un­der­stand the tech­nique of re­duc­tion well enough.” — “What should I read in ad­vance?” — “Well, there are some pa­pers by Amer­ic­an math­em­aticians about Hil­bert’s tenth prob­lem, but you need not study them.” — “Why not?” — “So far the Amer­ic­ans have not suc­ceeded, so their ap­proach is most likely in­ad­equate.”

Maslov was not unique in un­der­es­tim­at­ing the role of the pre­vi­ous work on Hil­bert’s tenth prob­lem. One of these pa­pers was by Mar­tin Dav­is, Hil­ary Put­nam, and Ju­lia Robin­son [3], and even the re­view­er of it for Math­em­at­ic­al Re­views stated:

These res­ults are su­per­fi­cially re­lated to Hil­bert’s tenth prob­lem on (or­din­ary, i.e., non­ex­po­nen­tial) Di­o­phant­ine equa­tions. The proof of the au­thors’ res­ults, though very el­eg­ant, does not use re­con­dite facts in the the­ory of num­bers nor in the the­ory of r.e. [re­curs­ively enu­mer­able] sets, and so it is likely that the present res­ult is not closely con­nec­ted with Hil­bert’s tenth prob­lem. Also it is not al­to­geth­er plaus­ible that all (or­din­ary) Di­o­phant­ine prob­lems are uni­formly re­du­cible to those in a fixed num­ber of vari­ables of fixed de­gree, which would be the case if all r.e. sets were Di­o­phant­ine.

The re­view­er’s skep­ti­cism arose be­cause the au­thors of [3] had con­sidered not or­din­ary Di­o­phant­ine equa­tions (i.e., equa­tions of the form $$\begin{array}{}\text{(1)}& P(x_1,x_2,\dots ,x_m)=0,\end{array}$$ where $P$ is a poly­no­mi­al with in­teger coef­fi­cients) but a wider class of so-called ex­po­nen­tial Di­o­phant­ine equa­tions. These are equa­tions of the form $$\begin{array}{}\text{(2)}& E_1(x_1,x_2,\dots ,x_m)=E_2(x_1,x_2,\dots ,x_m),\end{array}$$ where $E_1$ and $E_2$ are ex­pres­sions con­struc­ted from $x_1,x_2,\dots ,x_m$ and par­tic­u­lar nat­ur­al num­bers by ad­di­tion, mul­ti­plic­a­tion, and ex­po­nen­ti­ation. (In con­trast to the for­mu­la­tion of the prob­lem as giv­en by Hil­bert, we as­sume that all the vari­ables range over the nat­ur­al num­bers, but this is a minor tech­nic­al al­ter­a­tion.)

Be­sides single equa­tions, one can also con­sider para­met­ric fam­il­ies of equa­tions, either Di­o­phant­ine or ex­po­nen­tial Di­o­phant­ine. Such a fam­ily $$\begin{array}{}\text{(3)}& Q(a_1,\dots ,a_n,x_1,\dots ,x_m)=0\end{array}$$ de­term­ines a re­la­tion between the para­met­ers $a_1,\dots ,a_n$ which holds if and only if the equa­tion has a solu­tion in the re­main­ing vari­ables, called un­knowns. Re­la­tions that can be defined in this way are called Di­o­phant­ine or ex­po­nen­tial Di­o­phant­ine ac­cord­ing to the equa­tion used. Sim­il­arly, a set $\mathfrak{M}$ of $n$-tuples of nat­ur­al num­bers is called (ex­po­nen­tial) Di­o­phant­ine if the re­la­tion “to be­long to $\mathfrak{M}$” is (ex­po­nen­tial) Di­o­phant­ine. Also a func­tion is called (ex­po­nen­tial) Di­o­phant­ine if its graph is so.

Thus, in 1965 I did not en­counter even the name of Ju­lia Robin­son. In­stead of sug­gest­ing that I first study her pi­on­eer works, Maslov pro­posed that I try to prove the un­solv­ab­il­ity of so-called word equa­tions (or equa­tions in a free semig­roup) be­cause they can be re­duced to Di­o­phant­ine equa­tions. Today we know that this ap­proach was mis­lead­ing, be­cause in 1977 Gen­nadii Makan­in found a de­cision pro­ced­ure for word equa­tions. I star­ted my in­vest­ig­a­tions on Hil­bert’s tenth prob­lem by show­ing that a broad­er class of word equa­tions with ad­di­tion­al con­di­tions on the lengths of words is also re­du­cible to Di­o­phant­ine equa­tions. In 1968, I pub­lished three notes on this sub­ject.

I failed to prove the al­gorithmic un­solv­ab­il­ity of such ex­ten­ded word equa­tions (this is still an open prob­lem), so I then pro­ceeded to read “’the pa­pers by some Amer­ic­an math­em­aticians” on Hil­bert’s tenth prob­lem. (Sergei Ad­jan had ini­ti­ated and ed­ited trans­la­tions in­to Rus­si­an of the most im­port­ant pa­pers on this sub­ject; they were pub­lished in a single is­sue of Математика, a journ­al ded­ic­ated to trans­lated pa­pers.) After the pa­per by Dav­is, Put­nam, and Robin­son men­tioned above, all that was needed to solve Hil­bert’s tenth prob­lem in the neg­at­ive sense was to show that ex­po­nen­ti­ation is Di­o­phant­ine; i.e., to find a par­tic­u­lar Di­o­phant­ine equa­tion $$\begin{array}{}\text{(4)}& A(a,b,c,x_1,\dots ,x_m)=0\end{array}$$ which for giv­en val­ues of the para­met­ers $a$, $b$, and $c$ $\text{(4)}$ has a solu­tion in $x_1,\dots ,x_m$ if and only if $a=b^c$. With the aid of such an equa­tion, one can eas­ily trans­form an ar­bit­rary ex­po­nen­tial Di­o­phant­ine equa­tion in­to an equi­val­ent Di­o­phant­ine equa­tion with ad­di­tion­al un­knowns.

As it hap­pens, this same prob­lem had been tackled by Ju­lia Robin­son at the be­gin­ning of the 1950s. Ac­cord­ing to “The Auto­bi­o­graphy of Ju­lia Robin­son,” an art­icle writ­ten by her sis­ter Con­stance Re­id [e10], Ju­lia Robin­son’s in­terest was ori­gin­ally stim­u­lated by her teach­er, Al­fred Tarski, who sus­pec­ted that even the set of all powers of 2 is not Di­o­phant­ine. Ju­lia Robin­son, however, found a suf­fi­cient con­di­tion for the ex­ist­ence of a Di­o­phant­ine rep­res­ent­a­tion $\text{(4)}$ for ex­po­nen­ti­ation; namely, to con­struct such an $A$, it is suf­fi­cient to have an equa­tion $$\begin{array}{}\text{(5)}& B(a,b,x_1,\dots ,x_m)=0\end{array}$$ which defines a re­la­tion $J(a,b)$ with the fol­low­ing prop­er­ties:

• for any $a$ and $b$, $J(a,b)$ im­plies that $a<b^b$;
• for any $k$, there ex­ist $a$ and $b$ such that $J(a,b)$ and $a>b^k$.

Ju­lia Robin­son called a re­la­tion $J$ with these two prop­er­ties a re­la­tion of ex­po­nen­tial growth; today such re­la­tions are also known as Ju­lia Robin­son pre­dic­ates.

My first im­pres­sion of the no­tion of a re­la­tion of ex­po­nen­tial growth was “what an un­nat­ur­al no­tion,” but I soon real­ized its im­port­ant role for Hil­bert’s tenth prob­lem. I de­cided to or­gan­ize a sem­in­ar on Hil­bert’s tenth prob­lem. The first meet­ing where I gave a sur­vey of known res­ults was at­ten­ded by five lo­gi­cians and five num­ber-the­or­ists, but then the num­bers of par­ti­cipants de­creased ex­po­nen­tially and soon I was left alone.

I was spend­ing al­most all my free time try­ing to find a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth. There was noth­ing wrong when a sopho­more tried to tackle a fam­ous prob­lem, but it looked ri­dicu­lous when I con­tin­ued my at­tempts for years in vain. One pro­fess­or began to laugh at me. Each time we met he would ask: “Have you proved the un­solv­ab­il­ity of Hil­bert’s tenth prob­lem? Not yet? But then you will not be able to gradu­ate from the uni­versity!”

Nev­er­the­less I did gradu­ate in 1969. My thes­is con­sisted of my two early works on Post ca­non­ic­al sys­tems be­cause I had not done any­thing bet­ter in the mean­time. That same year I be­came a post-gradu­ate stu­dent at the Steklov In­sti­tute of Math­em­at­ics of the Academy of Sci­ences of the USSR (Len­in­grad Branch, LO­MI). Of course, the sub­ject of my study could no longer be Hil­bert’s tenth prob­lem.

One day in the au­tumn of 1969 some of my col­leagues told me: “Rush to the lib­rary. In the re­cent is­sue of the Pro­ceed­ings of the Amer­ic­an Math­em­at­ic­al So­ci­ety there is a new pa­per by Ju­lia Robin­son!” But I was firm in put­ting Hil­bert’s tenth prob­lem aside. I told my­self: “It’s nice that Ju­lia Robin­son goes on with the prob­lem, but I can­not waste my time on it any longer.” So I did not rush to the lib­rary.

Some­where in the Math­em­at­ic­al Heav­ens there must have been a God or God­dess of Math­em­at­ics who would not let me fail to read Ju­lia Robin­son’s new pa­per [4]. Be­cause of my early pub­lic­a­tions on the sub­ject, I was con­sidered a spe­cial­ist on it, and so the pa­per was sent to me to re­view for Реферативныи Журнал Математика, the So­viet coun­ter­part of Math­em­at­ic­al Re­views. Thus, I was forced to read Ju­lia Robin­son’s pa­per, and on Decem­ber 11, I presen­ted it to our lo­gic sem­in­ar at LO­MI.

Hil­bert’s tenth prob­lem cap­tured me again. I saw at once that Ju­lia Robin­son had a fresh and won­der­ful new idea. It was con­nec­ted with the spe­cial form of Pell’s equa­tion $$\begin{array}{}\text{(6)}& x^2-(a^2-1)y^2=1.\end{array}$$ Solu­tions $⟨{\chi }_0,{\psi }_0⟩,⟨{\chi }_1,{\psi }_1⟩,\dots ,⟨{\chi }_n,{\psi }_n⟩,\dots$ of this equa­tion lis­ted in the or­der of growth sat­is­fy the re­cur­rence re­la­tions $$\begin{array}{}\text{(7)}& \begin{array}{rl}{\chi }_{n+1}& =2a{\chi }_n-{\chi }_{n-1},\\ {\psi }_{n+1}& =2a{\psi }_n-{\psi }_{n-1}.\end{array}\end{array}$$ It is easy to see that for any $m$ the se­quences ${\chi }_0,{\chi }_1\dots ,{\psi }_0,{\psi }_1,\dots$ are purely peri­od­ic mod­ulo $m$ and hence so are their lin­ear com­bin­a­tions. Fur­ther, it is easy to check by in­duc­tion that the peri­od of the se­quence $$\begin{array}{}\text{(8)}& {\psi }_0,{\psi }_1,\dots {\psi }_n,\dots (\mathrm{mod}a-1)\end{array}$$ is $$\begin{array}{}\text{(9)}& 0,1,2,\dots ,a-2,\end{array}$$ where­as the peri­od of the se­quence $$\begin{array}{}\text{(10)}& {\chi }_0-(a-2){\psi }_0,{\chi }_1-(a-2){\psi }_1,\dots ,{\chi }_n-(a-2){\psi }_n,\dots (\mathrm{mod}4a-5)\end{array}$$ be­gins with $$\begin{array}{}\text{(11)}& 2^0,2^1,2^2,\dots .\end{array}$$ The main new idea of Ju­lia Robin­son was to syn­chron­ize the two se­quences by im­pos­ing a con­di­tion $G(a)$ which would guar­an­tee that $$\begin{array}{}\text{(12)}& \text{the length of the period of }\text{(8)}\text{ is a multiple of the length of the period of }\text{(10)}\text{.}\end{array}$$ If such a con­di­tion is Di­o­phant­ine and is val­id for in­fin­itely many val­ues of $a$, then one can eas­ily show that the re­la­tion $a=2^c$ is Di­o­phant­ine. Ju­lia Robin­son, however, was un­able to find such a $G$ and, even today, we have no dir­ect meth­od for find­ing one.

I liked the idea of syn­chron­iz­a­tion very much and tried to im­ple­ment it in a slightly dif­fer­ent situ­ation. When, in 1966, I had star­ted my in­vest­ig­a­tions on Hil­bert’s tenth prob­lem, I had be­gun to use Fibon­acci num­bers and had dis­covered (for my­self) the equa­tion $$\begin{array}{}\text{(13)}& x^2-xy-y^2=\pm 1\end{array}$$ which plays a role sim­il­ar to that of the above Pell equa­tion; namely, Fibon­acci num­bers ${\phi }_n$ and only they are solu­tions of $\text{(13)}$. The arith­met­ic­al prop­er­ties of the se­quences ${\psi }_n$ and ${\phi }_n$ are very sim­il­ar. In par­tic­u­lar, the se­quence $$\begin{array}{}\text{(14)}& 0,1,3,8,21,\dots \end{array}$$ of Fibon­acci num­bers with even in­dices sat­is­fies the re­cur­rence re­la­tion $$\begin{array}{}\text{(15)}& {\phi }_{n+1}=3{\phi }_n-{\phi }_{n-1}\end{array}$$ sim­il­ar to $\text{(7)}$. This se­quence grows like $[(3+\sqrt{5})/2{]}^n$ and can be used in­stead of $\text{(11)}$ for con­struct­ing a re­la­tion of ex­po­nen­tial growth. The role of (10) can be played by the se­quence $$\begin{array}{}\text{(16)}& {\psi }_0,{\psi }_1,\dots ,{\psi }_n,\dots (\mathrm{mod}a-3)\end{array}$$ be­cause it be­gins like $\text{(14)}$. Moreover, for spe­cial val­ues of $a$ the peri­od can be de­term­ined ex­pli­citly; namely, if $$\begin{array}{}\text{(17)}& a={\phi }_{2k}+{\phi }_{2k+2},\end{array}$$ then the peri­od of $\text{(16)}$ is ex­actly $$\begin{array}{}\text{(18)}& 0,1,3,\dots ,{\phi }_{2k},-{\phi }_{2k},\dots ,-3,-1.\end{array}$$ The simple struc­ture of the peri­od looked very prom­ising.

I was think­ing in­tens­ively in this dir­ec­tion, even on the night of New Year’s eve of 1970, and con­trib­uted to the stor­ies about ab­sent­minded math­em­aticians by leav­ing my uncle’s home on New Year’s day wear­ing his coat. On the morn­ing of Janu­ary 3, I be­lieved I had found a poly­no­mi­al $B$ as in $\text{(5)}$ but by the end of that day I had dis­covered a flaw in my work. But the next morn­ing I man­aged to mend the con­struc­tion.

What was to be done next? As a stu­dent I had had a bad ex­per­i­ence when once I had claimed to have proved un­solv­ab­il­ity of Hil­bert’s tenth prob­lem, but dur­ing my talk found a mis­take. I did not want to re­peat such an em­bar­rass­ment, and something in my new proof seemed rather sus­pi­cious to me. I thought at first that I had just man­aged to im­ple­ment Ju­lia Robin­son’s idea in a slightly dif­fer­ent situ­ation; however, in her con­struc­tion an es­sen­tial role was played by a spe­cial equa­tion that im­plied one vari­able was ex­po­nen­tially great­er than an­oth­er. My sup­posed proof did not need to use such an equa­tion at all, and that was strange. Later I real­ized that my con­struc­tion was a dual of Ju­lia Robin­son’s. In fact, I had found a Di­o­phant­ine con­di­tion $H(a)$ which im­plied that $$\begin{array}{}\text{(19)}& \text{the length of the period of }\text{(16)}\text{ is a multiple of the length of the period of }\text{(8)}\text{.}\end{array}$$ This $H$, however, could not play the role of Ju­lia Robin­son’s $G$, which res­ul­ted in an es­sen­tially dif­fer­ent con­struc­tion.

I wrote out a de­tailed proof without find­ing any mis­take and asked Sergei Maslov and Vladi­mir Lif­shits to check it but not to say any­thing about it to any­one else. Earli­er, I had planned to spend the winter hol­i­days with my bride at a ski camp, so I left Len­in­grad be­fore I got the ver­dict from Maslov and Lif­shits. For a fort­night I was ski­ing, sim­pli­fy­ing the proof, and writ­ing the pa­per [e4]. I tried to con­vey the im­pact of Ju­lia Robin­son’s pa­per [4] on my work by a rather po­et­ic Rus­si­an word навеят’, which seems to have no dir­ect coun­ter­part in Eng­lish, and the later Eng­lish trans­lat­or used plain “sug­ges­ted.”

On my re­turn to Len­in­grad I re­ceived con­firm­a­tion that my proof was cor­rect, and it was no longer secret. Sev­er­al oth­er math­em­aticians also checked the proof, in­clud­ing D. K. Fad­deev and A. A. Markov, both of whom were fam­ous for their abil­ity to find er­rors.

On 29 Janu­ary 1970 at LO­MI I gave my first pub­lic lec­ture on the solu­tion of Hil­bert’s tenth prob­lem. Among my listen­ers was Grig­orii Tseitin, who shortly af­ter­ward at­ten­ded a con­fer­ence in Nov­os­ibirsk. He took a copy of my manuscript along and asked my per­mis­sion to present the proof in Nov­os­ibirsk. (It was prob­ably due to this talk that the Eng­lish trans­la­tion of [e4] er­ro­neously gives the Siberi­an Branch in­stead of the Len­in­grad Branch as my ad­dress.) Among those who heard Tseitin’s talk in Nov­os­ibirsk was John Mc­Carthy. In “The Auto­bi­o­graphy” [e10], Ju­lia Robin­son re­calls that on his re­turn to the United States Mc­Carthy sent her his notes on the talk. This was how Ju­lia Robin­son learned of my ex­ample of a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth. Later, at my re­quest, she sent me a copy of Mc­Carthy’s notes. They con­sisted of only a few main equa­tions and lem­mas, and I be­lieve that only a per­son like Ju­lia, who had already spent a lot of time in­tens­ively think­ing in the same dir­ec­tion, would have been able to re­con­struct the whole proof from these notes as she did.

In fact, Ju­lia her­self was very near to com­plet­ing the proof of the un­solv­ab­il­ity of Hil­bert’s tenth prob­lem. The ques­tion some­times asked is why she did not (this ques­tion is also touched upon in [e10]). In fact, sev­er­al au­thors (see [e5] for fur­ther ref­er­ences) showed that $\psi$’s can be used in­stead of $\phi$’s for con­struct­ing a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth. My shift from $\text{(12)}$ to $\text{(19)}$ re­dis­trib­uted the dif­fi­culty in the en­tire con­struc­tion. The path from a Di­o­phant­ine $H$ to a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth is not as straight­for­ward as the path from Ju­lia Robin­son’s $G$ would have been. On the oth­er hand, it turned out that to con­struct an $H$ is much easi­er than to con­struct a $G$. In [e4], I used for this pur­pose a lemma stat­ing that $$\begin{array}{}\text{(20)}& {\phi }_n^2|{\phi }_m⟹{\phi }_n|m.\end{array}$$ It is not dif­fi­cult to prove this re­mark­able prop­erty of Fibon­acci num­bers after it has been stated, but it seems that this beau­ti­ful fact was not dis­covered un­til 1969. My ori­gin­al proof of $\text{(20)}$ was based on a the­or­em proved by the So­viet math­em­atician Nikolai Vorob’ev in 1942 but pub­lished only in the third aug­men­ted edi­tion of his pop­u­lar book [e3]. (So the trans­lat­or of my pa­per [e4] made a mis­lead­ing er­ror by chan­ging in the ref­er­ences the year of pub­lic­a­tion of [e3] from 1969 to 1964, the year of the second edi­tion.) I stud­ied the new edi­tion of Vorob’ev’s book in the sum­mer of 1969 and that the­or­em at­trac­ted my at­ten­tion at once. I did not de­duce $\text{(20)}$ at that time, but after I read Ju­lia Robin­son’s pa­per [4] I im­me­di­ately saw that Vorob’ev’s the­or­em could be very use­ful. Ju­lia Robin­son did not see the third edi­tion of [e3] un­til she re­ceived a copy from me in 1970. Who can tell what would have happened if Vorob’ev had in­cluded his the­or­em in the first edi­tion of his book? Per­haps, Hil­bert’s tenth prob­lem would have been “un­solved” a dec­ade earli­er!

The Di­o­phant­ine defin­i­tion of the re­la­tion of ex­po­nen­tial growth in [e4] had 14 un­knowns. Later I was able to re­duce the num­ber of un­knowns to 5. In Oc­to­ber 1970, Ju­lia sent me a let­ter with an­oth­er defin­i­tion also in only 5 un­knowns. Hav­ing ex­amined this con­struc­tion, I real­ized that she had used a dif­fer­ent meth­od for re­du­cing the num­ber of un­knowns and we could com­bine our ideas to get a defin­i­tion in just 3 un­knowns!

This was the be­gin­ning of our col­lab­or­a­tion. It was con­duc­ted al­most en­tirely by cor­res­pond­ence. At that time there was no elec­tron­ic mail any­where and it took three weeks for a let­ter to cross the ocean. One of my let­ters was lost in the mail and I had to re­write 11 pages (copy­ing ma­chines were not avail­able to me.) On the oth­er hand, this situ­ation had its own ad­vant­age: Today I have the pleas­ure of re­read­ing a col­lec­tion of let­ters writ­ten in Ju­lia’s hand. Cita­tions from these let­ters are in­cor­por­ated in­to this pa­per.

One of the co­rol­lar­ies of the neg­at­ive solu­tion of Hil­bert’s tenth prob­lem (im­plaus­ible to the re­view­er for Math­em­at­ic­al Re­views) is that there is a con­stant $N$ such that, giv­en a Di­o­phant­ine equa­tion with any num­ber of para­met­ers and in any num­ber of un­knowns, one can ef­fect­ively trans­form this equa­tion in­to an­oth­er with the same para­met­ers but in only N un­knowns such that both equa­tions are solv­able or un­solv­able for the same val­ues of the para­met­ers. In my lec­ture at the Nice In­ter­na­tion­al Con­gress of Math­em­aticians in 1970, I re­por­ted that this $N$ could be taken equal to 200. This es­tim­ate was very rough. Ju­lia and her hus­band, Raphael, were in­ter­ested in get­ting a smal­ler value of $N$, and in the above-men­tioned let­ter Ju­lia wrote that they had ob­tained $N=35$. Our new joint con­struc­tion of a Di­o­phant­ine re­la­tion of ex­po­nen­tial growth with 3 (in­stead of 5) un­knowns auto­mat­ic­ally re­duced $N$ to 33. Ju­lia com­men­ted: “I con­sider it in the range of ‘prac­tic­al’ num­ber the­ory, since Dav­en­port once wrote a pa­per on cu­bic forms in 33 vari­ables.”

Ju­lia sent me a de­tailed proof of this re­duc­tion, and it be­came the basis for our fur­ther work. We were ex­chan­ging let­ters and ideas and gradu­ally re­du­cing the value of $N$ fur­ther. In Feb­ru­ary 1971, I sent a new im­prove­ment that re­duced $N$ to 26 and com­men­ted that now we could write equa­tions in Lat­in char­ac­ters without sub­scripts for un­knowns. Ju­lia called it “break­ing the ‘al­pha­bet­ic­al’ bar­ri­er.”

In Au­gust 1971, I re­por­ted to the IV In­ter­na­tion­al Con­gress on Lo­gic, Meth­od­o­logy and Philo­sophy of Sci­ence in Bucharest on our latest res­ult: any Di­o­phant­ine equa­tion can be re­duced to an equa­tion in only 14 un­knowns [e5]. At that Con­gress Ju­lia and I met for the first time. After the Con­gress I had the pleas­ure of meet­ing Ju­lia and Raphael in my nat­ive city of Len­in­grad.

“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,” Ju­lia once wrote to me. However, in March 1972 the min­im­al num­ber of un­knowns un­ex­pec­tedly jumped up to 15 when she found a mis­take in my count of the num­ber of vari­ables! I would like to give the read­ers an idea of some of the tech­niques used for re­du­cing the num­ber of un­knowns and to ex­plain the nature of my mis­take. Ac­tu­ally, we were con­struct­ing not a single equa­tion but a sys­tem of equa­tions in a small num­ber of un­knowns. (Clearly, a sys­tem $A=B=\cdots =D=0$ can be com­pressed in­to single equa­tion $A^2+B^2+\cdots +D^2=0$). Some of the equa­tions used in our re­duc­tion were Pell equa­tions: $$\begin{array}{}\text{(21)}& \begin{array}{rl}{x}_1^2-d_1{y}_1^2& =1,\\ x_2^2-d_2{y}_2^2& =1.\end{array}\end{array}$$ We can re­place these two Di­o­phant­ine equa­tions by a single one: $$\begin{array}{}\text{(22)}& \prod (\chi \pm \sqrt{(1+d_1{y}_1^2)\phantom{{\hat{a}}_1}}\pm (1+d_1{y}_1^2)\sqrt{(1+d_2{y}_2^2)\phantom{{\hat{a}}_1}})=0,\end{array}$$ where the product is over all the four choices of signs $\pm$. In the re­main­ing equa­tions, we sub­sti­tute $\sqrt{(1+d_1{y}_1^2)\phantom{{\hat{a}}_1}}$ for $x_1$, $\sqrt{(1+d_2{y}_2^2)\phantom{{\hat{a}}_1}}$ for $x_2$, and elim­in­ate the square roots by squar­ing. Thus, we re­duce the total num­ber of un­knowns by one by in­tro­du­cing $x$ but elim­in­at­ing $x_1$ and $x_2$. It was in the count of vari­ables, in­tro­duced and elim­in­ated, that I made my er­ror.

The situ­ation was rather em­bar­rass­ing for us be­cause the res­ult had been an­nounced pub­licly. I tried to save the claimed res­ult, but hav­ing no new ideas, I was un­able to re­duce the num­ber of un­knowns back to 14.

Soon I got a new let­ter from Ju­lia. She tried to con­sole me: “I think mis­takes in reas­on­ing are much worse than arith­met­ic­al ones which are sort of funny.” But more im­port­ant, she came up with new ideas and man­aged to re­duce the num­ber of un­knowns to 14 again, thus sav­ing the situ­ation.

We dis­cussed for some time the prop­er place for pub­lish­ing our joint pa­per. I sug­ges­ted the So­viet journ­al Известия. The idea of hav­ing a pa­per pub­lished in Rus­si­an was at­tract­ive to Ju­lia. (Her pa­per [5] had been pub­lished in the USSR in Eng­lish in spite of what is said in Math­em­at­ic­al Re­views.) On the oth­er hand, she wanted to at­tract the at­ten­tion of spe­cial­ists in num­ber the­ory to the es­sen­tially num­ber-the­or­et­ic­al res­ults ob­tained by lo­gi­cians, so she sug­ges­ted Acta Arith­met­ica. Fi­nally, we de­cided that we had enough ma­ter­i­al for sev­er­al pa­pers and would pub­lish our first joint pa­per in Rus­si­an in Известия and our second one some­where else in Eng­lish.

We found writ­ing out a pa­per when we were half a world apart quite an or­deal. Later Ju­lia wrote to me: “It seems to me that we had little trouble in col­lab­or­at­ing math­em­at­ic­ally on 4-week turn-around time but it is hope­less when it comes to writ­ing the res­ults up. Namely, by the time you could an­swer a ques­tion, it was no longer rel­ev­ant.” We de­cided that one of us would write the whole manuscript, which was then to be sub­ject to the oth­er’s cri­ti­cism. Be­cause the first pa­per was to be in Rus­si­an, I wrote the first draft (more than 60 type­writ­ten pages) and sent it to Ju­lia in au­tumn 1972. Of course, she found a num­ber of mis­prints and small er­rors but, in gen­er­al, she ap­proved it.

The read­er, however, need not search the lit­er­at­ure for a ref­er­ence to this pa­per be­cause that manuscript has nev­er been pub­lished! In May 1973, I found “a mis­take in reas­on­ing.”

The mis­take was the use of the in­cor­rect im­plic­a­tion $$\begin{array}{}\text{(23)}& a\equiv b(\mathrm{mod}q)⟹(\begin{array}{c}a\\ c\end{array})\equiv (\begin{array}{c}b\\ c\end{array})(\mathrm{mod}q).\end{array}$$ The en­tire con­struc­tion col­lapsed. I in­formed Ju­lia and she replied:

I was com­pletely flab­ber­gas­ted by your let­ter of May 11. I wanted to crawl un­der a rock and hide from my­self! Some­how I had nev­er ques­tioned that $(\begin{array}{c}a\\ c\end{array})\equiv (\begin{array}{c}b\\ c\end{array})(\mathrm{mod}a-b)$. I usu­ally know enough not to di­vide by zero. I had even men­tioned (as­ser­ted) it to Raphael sev­er­al times, and he had not ob­jec­ted. He said he would have said ‘No’ if I had asked if it were true. I guess I would have my­self if I had asked!

Earli­er, we had dis­cussed a sim­il­ar situ­ation, and in 1971 Ju­lia had writ­ten to me: “Al­most all math­em­at­ic­al mis­takes come about from not writ­ing out proofs and es­pe­cially mak­ing changes after the proof is writ­ten out.” But that was not the case this time. The mis­take was present from an early stage and was not de­tec­ted either when one math­em­atician (my­self) wrote out a de­tailed proof or when an­oth­er math­em­atician (Ju­lia) care­fully read it.

Luck­ily, this time I was able to re­pair the proof on the spot. Ju­lia wrote: “I am very glad you sent a way around the mis­take at the same time you told me about it!” However, the manuscript had to be com­pletely re­writ­ten.

In 1973, the prom­in­ent So­viet math­em­atician A. A. Markov cel­eb­rated his sev­en­ti­eth birth­day. His col­leagues from the Com­put­ing Cen­ter of the Academy of Sci­ences of the USSR de­cided to pub­lish a col­lec­tion of pa­pers in his hon­or. I was in­vited to con­trib­ute to the col­lec­tion. I sug­ges­ted a joint pa­per with Ju­lia Robin­son, and the ed­it­ors agreed. Be­cause of the im­min­ent dead­line, we had no time to dis­cuss the manuscript. I just asked Ju­lia to au­thor­ize me to write the pa­per and to send it to the ed­it­ors without her ap­prov­al. Later I would in­cor­por­ate her sug­ges­tions on the proof­sheets. She agreed.

So our first joint pub­lic­a­tion [6] ap­peared, and it was in Rus­si­an. The pa­per was a by-product of our main in­vest­ig­a­tions on re­duc­tion of the num­ber of un­knowns in Di­o­phant­ine equa­tions. The first the­or­em stated that giv­en a para­met­ric Di­o­phant­ine equa­tion $\text{(3)}$ we can ef­fect­ively find poly­no­mi­als with in­teger coef­fi­cients $P_1,D_1,Q_1,\dots ,P_k,D_k,Q_k$ such that the Di­o­phant­ine re­la­tion defined by $\text{(3)}$ is also defined by the for­mula $$\begin{array}{}\text{(24)}& \mathrm{\exists }x\mathrm{\exists }y\underset{i=1}{\overset{k}{\mathrm{\&}}}\mathrm{\exists }z[P_i(a,x,y)<D_i(a,x,y)z<Q_i(a,x,y)].\end{array}$$ While $k$ can be a par­tic­u­lar large fixed num­ber, each in­equal­ity in­volves only 3 un­knowns.

The second the­or­em states that we can also find poly­no­mi­als $F$ and $W$ such that the same re­la­tion is defined by the for­mula $$\begin{array}{}\text{(25)}& \mathrm{\exists }x\mathrm{\exists }y\mathrm{\forall }z[z\le F(a,x,y)\Rightarrow W(a,x,y,z)>0].\end{array}$$ This for­mula also has only 3 quan­ti­fi­ers but the third is a (bounded) uni­ver­sal one. Such rep­res­ent­a­tions have a close con­nec­tion to equa­tions be­cause the main tech­nic­al res­ult of [3] is a meth­od for elim­in­at­ing a single bounded quan­ti­fi­er at the cost of in­tro­du­cing sev­er­al ex­tra ex­ist­en­tial quan­ti­fi­ers and al­low­ing ex­po­nen­ti­ation to come in­to the res­ult­ing purely ex­ist­en­tial for­mula.

One of Ju­lia’s re­quests in re­gard to this pa­per was that her first name should be giv­en. She had good reas­on for that. I had been the Rus­si­an trans­lat­or of one of the fun­da­ment­al pa­pers on auto­mat­ic the­or­em-prov­ing by John A. Robin­son [e2]. When the trans­la­tion ap­peared in 1970 in a col­lec­tion of im­port­ant pa­pers on that sub­ject, So­viet read­ers saw the names of Дж. Робинсон as the au­thor of a pa­per trans­lated by Ю. Матиясевич and М. Давис as the au­thor of an­oth­er fun­da­ment­al pa­per on auto­mat­ic the­or­em-prov­ing. In the minds of many, these three names were as­so­ci­ated with the re­cent solu­tion of Hil­bert’s tenth prob­lem so a num­ber of people got the idea that it was Ju­lia Robin­son who had in­ven­ted the res­ol­u­tion prin­ciple, the main tool from [e2]. To add to the con­fu­sion, John Robin­son in his pa­per thanked George Robin­son, whose name in Rus­si­an trans­la­tion also be­comes Дж. Робинсон.

As a stu­dent I had made “a mis­take of the second kind”: I did not identi­fy J. Robin­son, the au­thor of a the­or­em in game the­ory, with J. Robin­son, the au­thor of im­port­ant in­vest­ig­a­tions on Hil­bert’s tenth prob­lem. (In fact, Ju­lia’s sig­ni­fic­ant pa­per [1] was her only pub­lic­a­tion on game the­ory.)

Ju­lia’s re­quest was agreed to by the ed­it­ors, and as a res­ult our joint pa­per [6] is the only Rus­si­an pub­lic­a­tion where my first name is giv­en in full.

This short pa­per was a by-product of our main in­vest­ig­a­tion, which was still to be pub­lished. As it had been de­cided be­fore­hand that our second pub­lic­a­tion should be in Eng­lish, Ju­lia wrote the new pa­per about the re­duc­tion of the num­ber of un­knowns. Now we were able to elim­in­ate one more vari­able and so had only “a baker’s dozen” of un­knowns.

The second pa­per [7] was pub­lished in Acta Arith­met­ica. We had a spe­cial reas­on for this choice be­cause the whole volume was ded­ic­ated to the memory of the prom­in­ent So­viet math­em­atician Yu. V. Lin­nik, whom we both had known per­son­ally. I was in­tro­duced to him soon after show­ing Hil­bert’s tenth prob­lem to be un­solv­able. Someone had told Lin­nik the news be­gin­ning with one of the co­rol­lar­ies: “Mati­jasevich can con­struct a poly­no­mi­al with in­teger coef­fi­cients such that the set of all nat­ur­al num­ber val­ues as­sumed by this poly­no­mi­al for nat­ur­al num­ber val­ues of the vari­ables is ex­actly the set of all primes.” “That’s won­der­ful,” Lin­nik replied. “Most likely we soon shall learn a lot of new things about primes.” Then it was ex­plained to him that the main res­ult is in fact much more gen­er­al: Such a poly­no­mi­al can be con­struc­ted for every re­curs­ively enu­mer­able set, i.e., a set the ele­ments of which can be lis­ted in some or­der by an al­gorithm. “It’s a pity,” Lin­nik said. “Most likely, we shall not learn any­thing new about the primes.”

Since there was some in­terest in our forth­com­ing pa­per with the proof of a long-an­nounced res­ult be­com­ing at last ac­cess­ible to oth­er re­search­ers, nu­mer­ous cop­ies were cir­cu­lated. We had ex­hausted our ideas but there was a chance that someone with a fresh view of the sub­ject might im­prove our res­ult. “Of course there is the pos­sib­il­ity that someone will make a break­through and su­per­sede our pa­per too,” Ju­lia wrote, “but we should think of that as be­ing good for math­em­at­ics!” Raphael, on the oth­er hand, be­lieved that 13 un­knowns would re­main the best res­ult for dec­ades. Ac­tu­ally, the re­cord fell even be­fore our pa­per ap­peared.

The re­quired “new idea” turned out, as so of­ten hap­pens, to be an old one that had been for­got­ten. In this case, it was the fol­low­ing nice res­ult by E. E. Kum­mer: the greatest power of a prime $p$ which di­vides the bi­no­mi­al coef­fi­cient $(\genfrac{}{}{0ex}{}{a+b}{b})$ is $p^c$, where $c$ is the num­ber of car­ries needed when adding $a$ and $b$ writ­ten to base $p$. This old res­ult was re­dis­covered and re­proved a num­ber of times and I was lucky to learn it from the re­view of [e6] in Реферативныи Журнал Математика. Kum­mer’s the­or­em turned out to be an ex­tremely power­ful tool for con­struct­ing Di­o­phant­ine equa­tions with spe­cial prop­er­ties. (Ju­lia once called it “a gold mine.”) It would be too tech­nic­al to ex­plain all the ap­plic­a­tions, but one of them can be giv­en here.

Let $p$ be a fixed prime and let $f$ be a map from $\{0,1,\dots ,p-1\}$ in­to it­self such that $f(0)=0$. Such an $f$ gen­er­ates a func­tion $F$ defined by $$\begin{array}{}\text{(26)}& F\overline{(a_n{a}_{n-1}\cdots a_0)}=\overline{f(a_n)f(a_{n-1})\cdots f(a_0)},\end{array}$$ where $a_n{a}_{n-1}\cdots a_0$ is the num­ber with di­gits $a_n,a_{n-1},\dots ,a_0$ to base $p$. Now we can eas­ily prove that $F$ is an ex­po­nen­tial Di­o­phant­ine func­tion. Namely, $b=F(a)$ if and only if there are nat­ur­al num­bers $c_0,\dots ,c_{p-1},d_0,\dots ,d_{p-1},k,s,u,w_0,\dots ,w_{p-1},v_0,\dots ,v_{p-1}$ such that $$\begin{array}{}\text{(27)}& a& =\phantom{f(0)}0\ast d_0& +& \phantom{f(1)}1\ast d_1& +& & \cdots & & +& \phantom{f}(p-1)\ast d_{p-1},\text{(28)}& b& =f(0)\ast d_0& +& f(1)\ast d_1& +& & \cdots & & +& f(p-1)\ast d_{p-1},\text{(29)}& s& =\phantom{f(0)\ast }{d}_0& +& \phantom{f(1)\ast }{d}_1& +& & \cdots & & +& \phantom{f(p-1)\ast }{d}_{p-1},\end{array}$$ $$\begin{array}{}\text{(30)}& s& =(p^{k+l}-1)/(p-1),\text{(31)}& u& =2^{s+1},\text{(32)}& (u+1{)}^s& =w_i{u}^{d_i+1}+c_i{u}^{d_i}+v_i,\end{array}$$ $$\begin{array}{}\text{(33)}& v_i& <u^{d_i},\text{(34)}& c_i& <u,\text{(35)}& p& \nmid c_i.\end{array}$$ This sys­tem has a solu­tion with $$\begin{array}{}\text{(36)}& d_i=\sum _{l=0}^k{\delta }_i(a_l)p^l,\end{array}$$ where ${\delta }_i$ is the delta-func­tion: ${\delta }_i(i)=1$, oth­er­wise ${\delta }_i(j)=0$. In this solu­tion $$\begin{array}{}\text{(37)}& w_i& =\sum _{k=d_i+1}^s(\genfrac{}{}{0ex}{}{s}{k})u^k\text{(38)}& c_i& =(\genfrac{}{}{0ex}{}{s}{d_i}),\text{(39)}& v_i& =\sum _{k=0}^{d_i-1}(\genfrac{}{}{0ex}{}{s}{k})u^k,\end{array}$$ and for any giv­en value of $k$ that solu­tion is in fact unique.

Kum­mer’s the­or­em serves as a bridge between num­ber the­ory and lo­gic be­cause it en­ables one to work with num­bers as se­quences of in­def­in­ite length con­sist­ing of sym­bols from a fi­nite al­pha­bet. Ap­plic­a­tion of Kum­mer’s the­or­em to re­du­cing the num­ber of un­knowns res­ul­ted in a real break­through and, in one jump, that num­ber dropped from 13 to 9. I wrote out a sketch of the new con­struc­tion and sent it to Ju­lia. When we met for the second time in Lon­don, Ontario, dur­ing the V In­ter­na­tion­al Con­gress on Lo­gic, Meth­od­o­logy and Philo­sophy of Sci­ence, she con­firmed that the proof was cor­rect, so I dared to present the res­ult in my talk [e7]. We hoped to be able to pub­lish it as an ad­dendum to our pa­per in Acta Arith­met­ica, but it turned out to be too late.

In 1974, the Amer­ic­an Math­em­at­ic­al So­ci­ety or­gan­ized a sym­posi­um on “Math­em­at­ic­al De­vel­op­ments Arising From Hil­bert’s Prob­lems” at DeKalb, Illinois. I was in­vited to speak about the tenth prob­lem, but my par­ti­cip­a­tion in the meet­ing did not get the ne­ces­sary ap­prov­al in my coun­try, so Ju­lia be­came the speak­er on the prob­lem; however she sug­ges­ted that the pa­per for the Pro­ceed­ings of the meet­ing be a joint one by Mar­tin Dav­is and the two of us. Again we had the prob­lem of an ap­proach­ing dead­line. So we first dis­cussed by phone what top­ics each of us would cov­er. Of course, Ju­lia and Mar­tin had much more com­mu­nic­a­tion with each oth­er than with me. The fi­nal dif­fi­cult work of com­bin­ing our three con­tri­bu­tions in­to a co­her­ent ex­pos­i­tion [8] was done by Mar­tin. I be­lieve that this pa­per turned out to be one about which Ju­lia had thought for a long time: a non­tech­nic­al in­tro­duc­tion to many res­ults ob­tained by lo­gi­cians in con­nec­tion with Hil­bert’s tenth prob­lem.

Writ­ing the pa­per for the Pro­ceed­ings pre­ven­ted me from im­me­di­ately writ­ing a pa­per about the new re­duc­tion to 9 un­knowns (clearly it was my turn to write it up). Un­for­tu­nately, Ju­lia firmly re­fused to be a coau­thor. She wrote: “I do not want to be a joint au­thor on the 9 un­knowns pa­per — 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. If I could make some con­tri­bu­tion it would be dif­fer­ent.”

I am sure that without Ju­lia’s con­tri­bu­tion to [7] and without her in­spir­a­tion I would nev­er have re­duced $N$ to 9. I was not in­clined to pub­lish the proof by my­self, and so the res­ult an­nounced in [6] did not ap­pear in print with a full proof for a long time. At last James P. Jones of the Uni­versity of Cal­gary spent half a year in Berke­ley, where Ju­lia and Raphael lived. He stud­ied my sketch and Ju­lia’s com­ments on it, and made the proof avail­able to every­body in [e8]. The photo ac­com­pa­ny­ing this art­icle was taken in Cal­gary at the end of 1982 when I spent three months in Canada col­lab­or­at­ing with James as part of a sci­entif­ic ex­change pro­gram between the Steklov In­sti­tute of Math­em­at­ics and Queen’s Uni­versity at King­ston, Ontario. Ju­lia at that time was very much oc­cu­pied with her new du­ties as Pres­id­ent of the Amer­ic­an Math­em­at­ic­al So­ci­ety and was not very act­ive in math­em­at­ic­al re­search, but she vis­ited Cal­gary on her way to a meet­ing of the So­ci­ety. Mar­tin also came to Cal­gary for a few days.

I con­clude these re­min­is­cences with yet an­oth­er cita­tion from Ju­lia’s let­ters with which I com­pletely agree: “Ac­tu­ally I am very pleased that work­ing to­geth­er (thou­sands of miles apart) we are ob­vi­ously mak­ing more pro­gress than either one of us could alone.”

Yuri Mati­jasevich gradu­ated from Len­in­grad State Uni­versity in 1969 and did ad­vanced work at the Steklov In­sti­tute of Math­em­at­ics, Len­in­grad Branch. His name be­came known world­wide in 1970 when he com­pleted the last miss­ing step in the “neg­at­ive solu­tion” of Hil­bert’s tenth prob­lem. For this he re­ceived his Doc­tor of Sci­ences de­gree in 1973 and was awar­ded the Prize in Math­em­at­ics named after A. A. Markov (seni­or) from the Academy of Sci­ences of the USSR in 1980. His cur­rent re­search area is lo­gic and num­ber the­ory.