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{equation} P ( x_1 , x_2,\dots, x_m) = 0, \end{equation} 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{equation} E_1(x_1,x_2,\dots,x_m) = E_2(x_1,x_2,\dots,x_m), \end{equation} 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{equation} \label{eqth} Q(a_1,\dots,a_n,x_1,\dots,x_m) = 0 \end{equation} 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{equation} \label{eqfo} A(a,b,c,x_1,\dots,x_m) = 0 \end{equation} which for giv­en val­ues of the para­met­ers \( a \), \( b \), and \( c \) \eqref{eqfo} 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 \eqref{eqfo} for ex­po­nen­ti­ation; namely, to con­struct such an \( A \), it is suf­fi­cient to have an equa­tion \begin{equation} B(a,b,x_1,\dots,x_m) = 0 \label{eqfi} \end{equation} 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{equation} x^2 - (a^2 - 1)y^2 = 1. \end{equation} Solu­tions \( \langle \chi_0,\psi_0\rangle, \langle \chi_1,\psi_1\rangle, \dots,\ \langle \chi_n,\psi_n\rangle, \dots \) of this equa­tion lis­ted in the or­der of growth sat­is­fy the re­cur­rence re­la­tions \begin{equation} \label{eqse} \eqalign{ \chi_{n+1} &= 2a\chi_n-\chi_{n-1},\cr \psi_{n+1}&=2a\psi_n-\psi_{n-1}. } \end{equation} 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{equation} \label{eqei} \psi_0,\psi_1,\dots\,\psi_n,\dots \pmod{a - 1} \end{equation} is \begin{equation} 0,1,2,\dots, a-2, \end{equation} where­as the peri­od of the se­quence \begin{equation} \label{eqte} \chi_0 - (a-2)\psi_0,\, \chi_1 - (a-2)\psi_1,\,\dots,\,\chi_n - (a-2)\psi_n,\,\dots \pmod{4a-5} \end{equation} be­gins with \begin{equation} \label{eqonon} 2^0, 2^1, 2^2,\dots. \end{equation} 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{equation} \label{eqontw} \text{the length of the period of \eqref{eqei} is a multiple of the length of the period of \eqref{eqte}.} \end{equation} 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{equation} \label{eqonth} x^2 - xy - y^2= \pm 1 \end{equation} 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 \eqref{eqonth}. 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{equation} \label{eqonfo} 0,\, 1,\, 3,\, 8,\, 21,\, \dots \end{equation} of Fibon­acci num­bers with even in­dices sat­is­fies the re­cur­rence re­la­tion \begin{equation} \label{eqonfi} \phi_{n+1} = 3\phi_n - \phi_{n-1} \end{equation} sim­il­ar to \eqref{eqse}. This se­quence grows like \( [(3 + \sqrt{5})/2]^n \) and can be used in­stead of \eqref{eqonon} 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{equation} \label{eqonsi} \psi_0, \psi_1,\dots, \psi_n, \dots \pmod{a-3} \end{equation} be­cause it be­gins like \eqref{eqonfo}. Moreover, for spe­cial val­ues of \( a \) the peri­od can be de­term­ined ex­pli­citly; namely, if \begin{equation} \label{eqonse} a= \phi_{2k}+ \phi_{2k+2}, \end{equation} then the peri­od of \eqref{eqonsi} is ex­actly \begin{equation} \label{eqonei} 0,1,3,\dots, \phi_{2k},-\phi_{2k}, \dots, -3,-1. \end{equation} 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 \eqref{eqfi} 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{equation} \label{eqonni} \text{the length of the period of \eqref{eqonsi} is a multiple of the length of the period of \eqref{eqei}.} \end{equation} 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 \eqref{eqontw} to \eqref{eqonni} 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{equation} \label{eqtwze} \phi^2_n \mkern1mu|\mkern1mu \phi_m \quad\implies\quad \phi_n\mkern1mu|\mkern1mu m. \end{equation} 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 \eqref{eqtwze} 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 \eqref{eqtwze} 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 = \dots = D = 0 \) can be com­pressed in­to single equa­tion \( A^2 + B^2 +\dots + D^2 = 0 \)). Some of the equa­tions used in our re­duc­tion were Pell equa­tions: \begin{equation} \label{eqtwon} \eqalign{ x^2_1- d_1y^2_1 &= 1,\cr x^2_2- d_2y^2_2 &= 1.} \end{equation} We can re­place these two Di­o­phant­ine equa­tions by a single one: \begin{equation} \label{eqtwtw} \prod \bigl(\chi \pm \sqrt{\smash{(1+d_1y^2_1)}\vphantom{\hat{a}_1}} \pm (1+d_1y^2_1)\sqrt{\smash{(1+d_2y^2_2)}\vphantom{\hat{a}_1}}\bigr)= 0, \end{equation} where the product is over all the four choices of signs \( \pm \). In the re­main­ing equa­tions, we sub­sti­tute \( \sqrt{\smash{(1+d_1y^2_1)}\vphantom{\hat{a}_1}} \) for \( x_1 \), \( \sqrt{\smash{(1+d_2y^2_2)}\vphantom{\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{equation} \label{eqtwth} a\equiv b \pmod{q} \quad\implies\quad \biggl(\begin{matrix}a\\c\end{matrix}\biggr)\equiv \biggl(\begin{matrix}b\\c\end{matrix}\biggr)\pmod{q}. \end{equation} 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 \( \bigl(\begin{smallmatrix}a\\c\end{smallmatrix}\bigr) \equiv \bigl(\begin{smallmatrix} b\\c \end{smallmatrix}\bigr) \pmod{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 \eqref{eqth} 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 \eqref{eqth} is also defined by the for­mula \begin{equation} \label{eqtwfo} \exists x \, \exists y \, \mathop{\&}\limits^{k}_{i=1}\, \exists z\, [P_i(a,x,y) < D_i(a,x,y)z < Q_i(a,x,y)]. \end{equation} 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{equation} \label{eqtwfi} \exists x\, \exists y\, \forall z\, [\mkern1mu z \leq F(a,x,y)\ \Rightarrow\ W (a,x,y,z) > 0]. \end{equation} 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 \( \binom{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{equation} \label{eqtwsi} F\overline{(a_n a_{n-1}\cdots a_0)} = \overline{f(a_n)f(a_{n-1})\cdots f(a_0)}, \end{equation} 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{alignat}{9} a&=\phantom{f(0)}\llap{0}\ast d_0 &{}+{}&\phantom{f(1)}\llap{1}\ast d_1 &{}+{}& &{}\cdots{}& &{}+{}&\phantom{f}(p-1)\ast d_{p-1},\\ b&=f(0)\ast d_0 &{}+{}& f(1) \ast d_1&+& &{}\cdots{}& &{}+{}& f(p-1)\ast d_{p-1},\\ s&=\phantom{f(0)\ast{}}d_0&{}+{}&\phantom{f(1)\ast{}}d_1&{}+{}& &{}\cdots{}& &{}+{}&\phantom{f(p-1)\ast{}} d_{p-1}, \end{alignat} \begin{align} s &= (p^{k+l} - 1)/(p - 1),\\ u &= 2^{s+1},\\ (u + 1)^s &= w_iu^{d_i+1} + c_iu^{d_i} +v_i, \end{align} \begin{align} v_i & < u^{d_i},\\ c_i & < u, \\ p&\nmid c_i. \end{align} This sys­tem has a solu­tion with \begin{equation} d_i=\sum^k_{l=0}\delta_i(a_l)p^l, \end{equation} where \( \delta_i \) is the delta-func­tion: \( \delta_i(i ) = 1 \), oth­er­wise \( \delta_i(j) = 0 \). In this solu­tion \begin{alignat}{1} w_i&= \sum^s_{k=d_i+1} \binom{s}{k} u^k\\ c_i&= \binom{s}{d_i},\\ v_i&= \sum^{d_i-1}_{k=0}\binom{s}{k}u^k, \end{alignat} 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.