#### by Yuri Matiyasevich

The name of Julia Robinson cannot be separated from Hilbert’s tenth problem. This is one of the 23 problems stated by David Hilbert in 1900. The section of his famous address [e1] devoted to the tenth problem is so short that it can be cited here in full:

10. Determination of the Solvability of a Diophantine Equation

Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients:To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.

The tenth problem is the only one of the 23 problems that is (in
today’s terminology) a *decision problem*; i.e., a problem consisting of
infinitely many individual problems each of which requires a definite
answer: YES or NO. The heart of a decision problem is the requirement
to find a single method that will give an answer to any individual
subproblem. Since Diophantus’s time, number-theorists have found
solutions for a large number of Diophantine equations and also have
established the unsolvability of a large number of other equations.
Unfortunately, for different classes of equations and even for
different individual equations, it was necessary to invent different
specific methods. In the tenth problem, Hilbert asks for a *universal*
method for deciding the solvability of Diophantine equations.

A decision problem can be solved in a positive or in a negative sense, by discovering a proper algorithm or by showing that none exists. The general mathematical notion of algorithm was developed by A. Church, K. Gödel, A. Turing, E. Post, and other logicians only 30 years later, but, in his lecture [e1], Hilbert foresaw the possibility of negative solutions to some mathematical problems.

I have to start the story of my collaboration with Julia Robinson by telling about my own involvement in the study of Hilbert’s tenth problem. I heard about it for the first time at the end of 1965 when I was a sophomore in the Department of Mathematics and Mechanics of Leningrad State University. At that time I had already obtained my first results concerning Post’s canonical systems, and I asked my scientific adviser, Sergei Maslov (see [e9]), what to do next. He answered: “Try to prove the algorithmic unsolvability of Diophantine equations. This problem is known as Hilbert’s tenth problem, but that does not matter to you.” — “But I haven’t learned any proof of the unsolvability of any decision problem.” — “That also does not matter. Unsolvability is nowadays usually proved by reducing a problem already known to be unsolvable to the problem whose unsolvability one needs to establish, and you understand the technique of reduction well enough.” — “What should I read in advance?” — “Well, there are some papers by American mathematicians about Hilbert’s tenth problem, but you need not study them.” — “Why not?” — “So far the Americans have not succeeded, so their approach is most likely inadequate.”

Maslov was not unique in underestimating the role
of the previous work on Hilbert’s tenth problem. One
of these papers was by
Martin Davis,
Hilary Putnam,
and Julia Robinson
[3],
and even the reviewer of it for
*Mathematical Reviews* stated:

These results are superficially related to Hilbert’s tenth problem on (ordinary, i.e., nonexponential) Diophantine equations. The proof of the authors’ results, though very elegant, does not use recondite facts in the theory of numbers nor in the theory of r.e. [recursively enumerable] sets, and so it is likely that the present result is not closely connected with Hilbert’s tenth problem. Also it is not altogether plausible that all (ordinary) Diophantine problems are uniformly reducible to those in a fixed number of variables of fixed degree, which would be the case if all r.e. sets were Diophantine.

The reviewer’s skepticism arose because the authors
of
[3]
had considered not ordinary Diophantine equations
(i.e., equations of the form
__\begin{equation}
P ( x_1 , x_2,\dots, x_m) = 0,
\end{equation}__
where __\( P \)__ is a polynomial with integer coefficients) but a
wider class of so-called *exponential Diophantine equations*.
These are equations 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 expressions constructed from
__\( x_1 , x_2,\dots,x_m \)__ and particular natural numbers by addition,
multiplication, and exponentiation. (In contrast
to the formulation of the problem as given by Hilbert,
we assume that all the variables range over the natural
numbers, but this is a minor technical alteration.)

Besides single equations, one can also consider parametric
families of equations, either Diophantine or exponential
Diophantine. Such a family
__\begin{equation}
\label{eqth}
Q(a_1,\dots,a_n,x_1,\dots,x_m) = 0
\end{equation}__
determines a relation between the *parameters*
__\( a_1,\dots,a_n \)__ which holds if and only if the equation has
a solution in the remaining variables, called *unknowns*.
Relations that can be defined in this way are called
*Diophantine* or *exponential Diophantine* according to the
equation used. Similarly, a set __\( \mathfrak{M} \)__ of __\( n \)__-tuples of natural
numbers is called (exponential) Diophantine if the relation
“to belong to __\( \mathfrak{M} \)__” is (exponential) Diophantine.
Also a function is called (exponential) Diophantine if
its graph is so.

Thus, in 1965 I did not encounter even the name of
Julia Robinson. Instead of suggesting that I first study
her pioneer works, Maslov proposed that I try to prove
the unsolvability of so-called *word equations* (or *equations
in a free semigroup*) because they can be reduced to
Diophantine equations. Today we know that this approach
was misleading, because in 1977
Gennadii Makanin
found a decision procedure for word equations.
I started my investigations on Hilbert’s tenth problem
by showing that a broader class of word equations with
additional conditions on the lengths of words is also
reducible to Diophantine equations. In 1968, I published
three notes on this subject.

I failed to prove the algorithmic unsolvability of such
extended word equations (this is still an open problem),
so I then proceeded to read “’the papers by some
American mathematicians” on Hilbert’s tenth problem.
(Sergei Adjan
had initiated and edited translations
into Russian of the most important papers on this
subject; they were published in a single issue of
Математика,
a journal dedicated to translated papers.)
After the paper by Davis, Putnam, and Robinson
mentioned above, all that was needed to solve
Hilbert’s tenth problem in the negative sense was to
show that exponentiation is Diophantine; i.e., to find a
particular Diophantine equation
__\begin{equation}
\label{eqfo}
A(a,b,c,x_1,\dots,x_m) = 0
\end{equation}__
which for given values of the parameters __\( a \)__, __\( b \)__, and __\( c \)__ __\eqref{eqfo}__
has a solution in __\( x_1,\dots, x_m \)__ if and only if __\( a = b^c \)__. With
the aid of such an equation, one can easily transform
an arbitrary exponential Diophantine equation into an
equivalent Diophantine equation with additional unknowns.

As it happens, this same problem had been tackled
by Julia Robinson at the beginning of the 1950s. According
to “The Autobiography of Julia Robinson,” an
article written by her sister Constance Reid
[e10],
Julia Robinson’s interest was originally stimulated by her
teacher,
Alfred Tarski,
who suspected that even the set
of all powers of 2 is *not* Diophantine. Julia Robinson,
however, found a sufficient condition for the existence
of a Diophantine representation __\eqref{eqfo}__ for exponentiation;
namely, to construct such an __\( A \)__, it is sufficient to have
an equation
__\begin{equation}
B(a,b,x_1,\dots,x_m) = 0
\label{eqfi}
\end{equation}__
which defines a relation __\( J(a,b) \)__ with the following properties:

- for any
__\( a \)__and__\( b \)__,__\( J(a,b) \)__implies that__\( a < b^b \)__; - for any
__\( k \)__, there exist__\( a \)__and__\( b \)__such that__\( J(a,b) \)__and__\( a > b^k \)__.

Julia Robinson called a relation __\( J \)__ with these two properties
a *relation of exponential growth*; today such relations
are also known as *Julia Robinson predicates*.

My first impression of the notion of a relation of exponential growth was “what an unnatural notion,” but I soon realized its important role for Hilbert’s tenth problem. I decided to organize a seminar on Hilbert’s tenth problem. The first meeting where I gave a survey of known results was attended by five logicians and five number-theorists, but then the numbers of participants decreased exponentially and soon I was left alone.

I was spending almost all my free time trying to find a Diophantine relation of exponential growth. There was nothing wrong when a sophomore tried to tackle a famous problem, but it looked ridiculous when I continued my attempts for years in vain. One professor began to laugh at me. Each time we met he would ask: “Have you proved the unsolvability of Hilbert’s tenth problem? Not yet? But then you will not be able to graduate from the university!”

Nevertheless I did graduate in 1969. My thesis consisted of my two early works on Post canonical systems because I had not done anything better in the meantime. That same year I became a post-graduate student at the Steklov Institute of Mathematics of the Academy of Sciences of the USSR (Leningrad Branch, LOMI). Of course, the subject of my study could no longer be Hilbert’s tenth problem.

One day in the autumn of 1969 some of my colleagues told me: “Rush to
the library. In the recent issue of the *Proceedings of the American
Mathematical Society* there is a new paper by Julia Robinson!” But I
was firm in putting Hilbert’s tenth problem aside. I told myself:
“It’s nice that Julia Robinson goes on with the problem, but I cannot
waste my time on it any longer.” So I did not rush to the library.

Somewhere in the Mathematical Heavens there
must have been a God or Goddess of Mathematics who
would not let me fail to read Julia Robinson’s new
paper
[4].
Because of my early publications on the
subject, I was considered a specialist on it, and so the
paper was sent to me to review for
Реферативныи
Журнал
Математика,
the Soviet counterpart of *Mathematical
Reviews*. Thus, I was forced to read Julia Robinson’s
paper, and on December 11, I presented it to
our logic seminar at LOMI.

Hilbert’s tenth problem captured me again. I saw at
once that Julia Robinson had a fresh and wonderful
new idea. It was connected with the special form of
Pell’s equation
__\begin{equation}
x^2 - (a^2 - 1)y^2 = 1.
\end{equation}__
Solutions
__\( \langle \chi_0,\psi_0\rangle, \langle \chi_1,\psi_1\rangle, \dots,\ \langle \chi_n,\psi_n\rangle, \dots \)__
of this
equation listed in the order of growth satisfy the recurrence
relations
__\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 sequences
__\( \chi_0,\chi_1\dots,\psi_0,\psi_1,\dots \)__
are purely periodic modulo __\( m \)__
and hence so are their linear combinations. Further, it
is easy to check by induction that the period of the
sequence
__\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}__
whereas the period of the sequence
__\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}__
begins with
__\begin{equation}
\label{eqonon}
2^0,
2^1,
2^2,\dots.
\end{equation}__
The main new idea of Julia Robinson was to synchronize
the two sequences by imposing a condition
__\( G(a) \)__ which would guarantee 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 condition is Diophantine and is valid for infinitely many
values of __\( a \)__, then one can easily show that the relation __\( a = 2^c \)__ is
Diophantine. Julia Robinson, however, was unable to find such a __\( G \)__
and, even today, we have no direct method for finding one.

I liked the idea of synchronization very much and tried to implement
it in a slightly different situation. When, in 1966, I had started my
investigations on Hilbert’s tenth problem, I had begun to use
Fibonacci numbers and had discovered (for myself) the equation
__\begin{equation}
\label{eqonth}
x^2 - xy - y^2= \pm 1
\end{equation}__
which plays a role similar to that of the above Pell
equation; namely, Fibonacci numbers __\( \phi_n \)__ and only they
are solutions of __\eqref{eqonth}__. The arithmetical properties of the
sequences __\( \psi_n \)__ and __\( \phi_n \)__ are very similar. In particular, the
sequence
__\begin{equation}
\label{eqonfo}
0,\, 1,\, 3,\, 8,\, 21,\, \dots
\end{equation}__
of Fibonacci numbers with even indices satisfies the
recurrence relation
__\begin{equation}
\label{eqonfi}
\phi_{n+1} = 3\phi_n - \phi_{n-1}
\end{equation}__
similar to __\eqref{eqse}__. This sequence grows like __\( [(3 + \sqrt{5})/2]^n \)__
and can be used instead of __\eqref{eqonon}__ for constructing a relation
of exponential growth. The role of (10) can be
played by the sequence
__\begin{equation}
\label{eqonsi}
\psi_0,
\psi_1,\dots,
\psi_n, \dots \pmod{a-3}
\end{equation}__
because it begins like __\eqref{eqonfo}__. Moreover, for special values
of __\( a \)__ the period can be determined explicitly; namely, if
__\begin{equation}
\label{eqonse}
a=
\phi_{2k}+
\phi_{2k+2},
\end{equation}__
then the period of __\eqref{eqonsi}__ is exactly
__\begin{equation}
\label{eqonei}
0,1,3,\dots, \phi_{2k},-\phi_{2k},
\dots,
-3,-1.
\end{equation}__
The simple structure of the period looked very promising.

I was thinking intensively in this direction, even on the night of New
Year’s eve of 1970, and contributed to the stories about absentminded
mathematicians by leaving my uncle’s home on New Year’s day wearing
his coat. On the morning of January 3, I believed I had found a
polynomial __\( B \)__ as in __\eqref{eqfi}__ but by the end of that day I had discovered a
flaw in my work. But the next morning I managed to mend the
construction.

What was to be done next? As a student I had had a bad experience when
once I had claimed to have proved unsolvability of Hilbert’s tenth
problem, but during my talk found a mistake. I did not want to repeat
such an embarrassment, and something in my new proof seemed rather
suspicious to me. I thought at first that I had just managed to
implement Julia Robinson’s idea in a slightly different situation;
however, in her construction an essential role was played by a special
equation that implied one variable was exponentially greater than
another. My supposed proof did not need to use such an equation at
all, and that was strange. Later I realized that my construction was a
dual of Julia Robinson’s. In fact, I had found a Diophantine condition
__\( H(a) \)__ which implied 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 Julia Robinson’s __\( G \)__,
which resulted in an essentially different construction.

I wrote out a detailed proof without finding any mistake and asked Sergei Maslov and Vladimir Lifshits to check it but not to say anything about it to anyone else. Earlier, I had planned to spend the winter holidays with my bride at a ski camp, so I left Leningrad before I got the verdict from Maslov and Lifshits. For a fortnight I was skiing, simplifying the proof, and writing the paper [e4]. I tried to convey the impact of Julia Robinson’s paper [4] on my work by a rather poetic Russian word навеят’, which seems to have no direct counterpart in English, and the later English translator used plain “suggested.”

On my return to Leningrad I received confirmation that my proof was correct, and it was no longer secret. Several other mathematicians also checked the proof, including D. K. Faddeev and A. A. Markov, both of whom were famous for their ability to find errors.

On 29 January 1970 at LOMI I gave my first public lecture on the solution of Hilbert’s tenth problem. Among my listeners was Grigorii Tseitin, who shortly afterward attended a conference in Novosibirsk. He took a copy of my manuscript along and asked my permission to present the proof in Novosibirsk. (It was probably due to this talk that the English translation of [e4] erroneously gives the Siberian Branch instead of the Leningrad Branch as my address.) Among those who heard Tseitin’s talk in Novosibirsk was John McCarthy. In “The Autobiography” [e10], Julia Robinson recalls that on his return to the United States McCarthy sent her his notes on the talk. This was how Julia Robinson learned of my example of a Diophantine relation of exponential growth. Later, at my request, she sent me a copy of McCarthy’s notes. They consisted of only a few main equations and lemmas, and I believe that only a person like Julia, who had already spent a lot of time intensively thinking in the same direction, would have been able to reconstruct the whole proof from these notes as she did.

In fact, Julia herself was very near to completing the proof of the
unsolvability of Hilbert’s tenth problem. The question sometimes asked
is *why she did not* (this question is also touched upon in
[e10]).
In
fact, several authors (see
[e5]
for further references) showed that __\( \psi \)__’s
can be used instead of __\( \phi \)__’s for constructing a Diophantine relation of
exponential growth. My shift from __\eqref{eqontw}__
to __\eqref{eqonni}__
redistributed the
difficulty in the entire construction. The path from a Diophantine __\( H \)__
to a Diophantine relation of exponential growth is not as
straightforward as the path from Julia Robinson’s __\( G \)__ would have been.
On the other hand, it turned out that to construct an __\( H \)__ is much easier
than to construct a __\( G \)__. In
[e4],
I used for this purpose a lemma stating
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 difficult to prove this remarkable property of Fibonacci
numbers *after* it has been stated, but it seems that this beautiful
fact was not discovered until 1969. My original proof of __\eqref{eqtwze}__ was
based on a theorem proved by the Soviet mathematician
Nikolai Vorob’ev
in 1942 but published only in the third augmented edition of his
popular book
[e3].
(So the translator of my paper
[e4]
made a
misleading error by changing in the references the year of publication
of
[e3]
from 1969 to 1964, the year of the second edition.) I studied
the new edition of Vorob’ev’s book in the summer of 1969 and that
theorem attracted my attention at once. I did not deduce __\eqref{eqtwze}__
at that
time, but after I read Julia Robinson’s paper
[4]
I immediately saw
that Vorob’ev’s theorem could be very useful. Julia Robinson did not
see the third edition of
[e3]
until she received a copy from me in
1970. Who can tell what would have happened if Vorob’ev had included
his theorem in the first edition of his book? Perhaps, Hilbert’s tenth
problem would have been “unsolved” a decade earlier!

The Diophantine definition of the relation of exponential growth in [e4] had 14 unknowns. Later I was able to reduce the number of unknowns to 5. In October 1970, Julia sent me a letter with another definition also in only 5 unknowns. Having examined this construction, I realized that she had used a different method for reducing the number of unknowns and we could combine our ideas to get a definition in just 3 unknowns!

This was the beginning of our collaboration. It was conducted almost entirely by correspondence. At that time there was no electronic mail anywhere and it took three weeks for a letter to cross the ocean. One of my letters was lost in the mail and I had to rewrite 11 pages (copying machines were not available to me.) On the other hand, this situation had its own advantage: Today I have the pleasure of rereading a collection of letters written in Julia’s hand. Citations from these letters are incorporated into this paper.

One of the corollaries of the negative solution of Hilbert’s tenth
problem (implausible to the reviewer for *Mathematical Reviews*) is that
*there is a constant* __\( N \)__ *such that, given a Diophantine equation with any
number of parameters and in any number of unknowns, one can
effectively transform this equation into another with the same
parameters but in only N unknowns such that both equations are
solvable or unsolvable for the same values of the parameters*. In my
lecture at the Nice International Congress of Mathematicians in 1970,
I reported that this __\( N \)__ could be taken equal to 200. This estimate was
very rough. Julia and her husband,
Raphael, were interested in getting
a smaller value of __\( N \)__, and in the above-mentioned letter Julia wrote
that they had obtained __\( N = 35 \)__. Our new joint construction of a
Diophantine relation of exponential growth with 3 (instead of 5)
unknowns automatically reduced __\( N \)__ to 33. Julia commented: “I consider
it in the range of ‘practical’ number theory, since Davenport once
wrote a paper on cubic forms in 33 variables.”

Julia sent me a detailed proof of this reduction, and it became the
basis for our further work. We were exchanging letters and ideas and
gradually reducing the value of __\( N \)__ further. In February 1971, I sent a
new improvement that reduced __\( N \)__ to 26 and commented that now we could
write equations in Latin characters without subscripts for unknowns.
Julia called it “breaking the ‘alphabetical’ barrier.”

In August 1971, I reported to the IV International Congress on Logic,
Methodology and Philosophy of Science in Bucharest on our latest
result: *any Diophantine equation can be reduced to an equation in only
14 unknowns*
[e5].
At that Congress Julia and I met for the first time.
After the Congress I had the pleasure of meeting Julia and Raphael in
my native city of Leningrad.

“With just 14 variables we ought to be able to know
every variable personally and why it has to be there,”
Julia once wrote to me. However, in March 1972 the
minimal number of unknowns unexpectedly jumped
up to 15 when she found a mistake in my count of the
number of variables! I would like to give the readers an
idea of some of the techniques used for reducing the
number of unknowns and to explain the nature of my
mistake. Actually, we were constructing not a single
equation but a system of equations in a small number
of unknowns. (Clearly, a system __\( A = B = \dots = D = 0 \)__ can be
compressed into single equation
__\( A^2 + B^2 +\dots
+ D^2 = 0 \)__). Some of the equations used in our
reduction were Pell equations:
__\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 replace these two Diophantine equations 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 remaining equations, we substitute
__\( \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 eliminate
the square roots by squaring. Thus, we reduce the total
number of unknowns by one by introducing __\( x \)__ but
eliminating __\( x_1 \)__ and __\( x_2 \)__. It was in the count of variables,
introduced and eliminated, that I made my error.

The situation was rather embarrassing for us because the result had been announced publicly. I tried to save the claimed result, but having no new ideas, I was unable to reduce the number of unknowns back to 14.

Soon I got a new letter from Julia. She tried to console me: “I think mistakes in reasoning are much worse than arithmetical ones which are sort of funny.” But more important, she came up with new ideas and managed to reduce the number of unknowns to 14 again, thus saving the situation.

We discussed for some time the proper place for publishing our joint
paper. I suggested the Soviet journal
Известия.
The idea of having a
paper published in Russian was attractive to Julia. (Her paper
[5]
had been published in the USSR in English in spite of what is said in
*Mathematical Reviews*.) On the other hand, she wanted to attract the
attention of specialists in number theory to the essentially
number-theoretical results obtained by logicians, so she suggested
*Acta Arithmetica*. Finally, we decided that we had enough material for
several papers and would publish our first joint paper in Russian in
Известия
and our second one somewhere else in English.

We found writing out a paper when we were half a world apart quite an ordeal. Later Julia wrote to me: “It seems to me that we had little trouble in collaborating mathematically on 4-week turn-around time but it is hopeless when it comes to writing the results up. Namely, by the time you could answer a question, it was no longer relevant.” We decided that one of us would write the whole manuscript, which was then to be subject to the other’s criticism. Because the first paper was to be in Russian, I wrote the first draft (more than 60 typewritten pages) and sent it to Julia in autumn 1972. Of course, she found a number of misprints and small errors but, in general, she approved it.

The reader, however, need not search the literature for a reference to this paper because that manuscript has never been published! In May 1973, I found “a mistake in reasoning.”

The mistake was the use of the incorrect implication
__\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 entire construction collapsed. I informed Julia and
she replied:

I was completely flabbergasted by your letter of May 11. I wanted to crawl under a rock and hide from myself! Somehow I had never questioned that

\( \bigl(\begin{smallmatrix}a\\c\end{smallmatrix}\bigr) \equiv \bigl(\begin{smallmatrix} b\\c \end{smallmatrix}\bigr) \pmod{a-b} \). I usually know enough not to divide by zero. I had even mentioned (asserted) it to Raphael several times, and he had not objected. He said he would have said ‘No’ if I had asked if it were true. I guess I would have myself if I had asked!

Earlier, we had discussed a similar situation, and in 1971 Julia had written to me: “Almost all mathematical mistakes come about from not writing out proofs and especially making changes after the proof is written out.” But that was not the case this time. The mistake was present from an early stage and was not detected either when one mathematician (myself) wrote out a detailed proof or when another mathematician (Julia) carefully read it.

Luckily, this time I was able to repair the proof on the spot. Julia wrote: “I am very glad you sent a way around the mistake at the same time you told me about it!” However, the manuscript had to be completely rewritten.

In 1973, the prominent Soviet mathematician A. A. Markov celebrated his seventieth birthday. His colleagues from the Computing Center of the Academy of Sciences of the USSR decided to publish a collection of papers in his honor. I was invited to contribute to the collection. I suggested a joint paper with Julia Robinson, and the editors agreed. Because of the imminent deadline, we had no time to discuss the manuscript. I just asked Julia to authorize me to write the paper and to send it to the editors without her approval. Later I would incorporate her suggestions on the proofsheets. She agreed.

So our first joint publication
[6]
appeared, and it was
in Russian. The paper was a by-product of our main
investigations on reduction of the number of unknowns
in Diophantine equations. The first theorem
stated that given a parametric Diophantine equation
__\eqref{eqth}__
we can effectively find polynomials with integer
coefficients __\( P_1,D_1,Q_1,\dots, P_k, D_k, Q_k \)__ such that the
Diophantine relation defined by __\eqref{eqth}__
is also defined by
the formula
__\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 particular large fixed number, each
inequality involves only 3 unknowns.

The second theorem states that we can also find
polynomials __\( F \)__ and __\( W \)__ such that the same relation is
defined by the formula
__\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 formula also has only 3 quantifiers but the third is
a (bounded) universal one. Such representations have
a close connection to equations because the main technical
result of
[3]
is a method for eliminating a single
bounded quantifier at the cost of introducing several
extra existential quantifiers and allowing exponentiation
to come into the resulting purely existential formula.

One of Julia’s requests in regard to this paper was that her first name should be given. She had good reason for that. I had been the Russian translator of one of the fundamental papers on automatic theorem-proving by John A. Robinson [e2]. When the translation appeared in 1970 in a collection of important papers on that subject, Soviet readers saw the names of Дж. Робинсон as the author of a paper translated by Ю. Матиясевич and М. Давис as the author of another fundamental paper on automatic theorem-proving. In the minds of many, these three names were associated with the recent solution of Hilbert’s tenth problem so a number of people got the idea that it was Julia Robinson who had invented the resolution principle, the main tool from [e2]. To add to the confusion, John Robinson in his paper thanked George Robinson, whose name in Russian translation also becomes Дж. Робинсон.

As a student I had made “a mistake of the second kind”: I did not identify J. Robinson, the author of a theorem in game theory, with J. Robinson, the author of important investigations on Hilbert’s tenth problem. (In fact, Julia’s significant paper [1] was her only publication on game theory.)

Julia’s request was agreed to by the editors, and as a result our
joint paper
[6]
is the only Russian publication where *my* first
name is given in full.

This short paper was a by-product of our main investigation, which was still to be published. As it had been decided beforehand that our second publication should be in English, Julia wrote the new paper about the reduction of the number of unknowns. Now we were able to eliminate one more variable and so had only “a baker’s dozen” of unknowns.

The second paper
[7]
was published in *Acta Arithmetica*. We had a
special reason for this choice because the whole volume was dedicated
to the memory of the prominent Soviet mathematician
Yu. V. Linnik,
whom we both had known personally. I was introduced to him soon after
showing Hilbert’s tenth problem to be unsolvable. Someone had told
Linnik the news beginning with one of the corollaries: “Matijasevich
can construct a polynomial with integer coefficients such that the set
of all natural number values assumed by this polynomial for natural
number values of the variables is exactly the set of all primes.”
“That’s wonderful,” Linnik replied. “Most likely we soon shall
learn a lot of new things about primes.” Then it was explained to him
that the main result is in fact much more general: Such a polynomial
can be constructed for every recursively enumerable set, i.e., a set
the elements of which can be listed in some order by an algorithm.
“It’s a pity,” Linnik said. “Most likely, we shall not learn
anything new about the primes.”

Since there was some interest in our forthcoming paper with the proof of a long-announced result becoming at last accessible to other researchers, numerous copies were circulated. We had exhausted our ideas but there was a chance that someone with a fresh view of the subject might improve our result. “Of course there is the possibility that someone will make a breakthrough and supersede our paper too,” Julia wrote, “but we should think of that as being good for mathematics!” Raphael, on the other hand, believed that 13 unknowns would remain the best result for decades. Actually, the record fell even before our paper appeared.

The required “new idea” turned out, as so often happens, to be an
old one that had been forgotten. In this case, it was the following
nice result by
E. E. Kummer:
*the greatest power of a prime* __\( p \)__
*which divides the binomial coefficient*
__\( \binom{a+b}{b} \)__ *is* __\( p^c \)__, *where* __\( c \)__ *is the number
of carries needed when adding* __\( a \)__ *and* __\( b \)__ *written to base* __\( p \)__. This old
result was rediscovered and reproved a number of times and I was
lucky to learn it from the review of
[e6]
in
Реферативныи
Журнал
Математика.
Kummer’s theorem turned out to be an extremely
powerful tool for constructing Diophantine equations with special
properties. (Julia once called it “a gold mine.”) It would be too
technical to explain all the applications, but one of them can be
given here.

Let __\( p \)__ be a fixed prime and let __\( f \)__ be a map from
__\( \{0,1,\dots, p - 1\} \)__ into itself such that __\( f(0) = 0 \)__. Such an
__\( f \)__ generates a function __\( 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 number with digits
__\( a_n,a_{n-1},\dots, a_0 \)__ to base __\( p \)__. Now we can easily prove
that __\( F \)__ is an exponential Diophantine function.
Namely, __\( b=F(a) \)__ if and only if there are natural numbers
__\( 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 system has a solution with
__\begin{equation}
d_i=\sum^k_{l=0}\delta_i(a_l)p^l,
\end{equation}__
where __\( \delta_i \)__ is the delta-function: __\( \delta_i(i ) = 1 \)__,
otherwise __\( \delta_i(j) = 0 \)__. In this solution
__\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 given value of __\( k \)__ that solution is in fact
unique.

Kummer’s theorem serves as a bridge between number
theory and logic because it enables one to work
with numbers as sequences of indefinite length consisting
of symbols from a finite alphabet. Application
of Kummer’s theorem to reducing the number of unknowns
resulted in a real breakthrough and, in one
jump, that number dropped from 13 to 9. I wrote out
a sketch of the new construction and sent it to Julia.
When we met for the second time in London, Ontario,
during the V International Congress on Logic, Methodology
and Philosophy of Science, she confirmed that
the proof was correct, so I dared to present the result
in my talk
[e7].
We hoped to be able to publish it as an
addendum to our paper in *Acta Arithmetica*, but it
turned out to be too late.

In 1974, the American Mathematical Society organized
a symposium on “Mathematical Developments
Arising From Hilbert’s Problems” at DeKalb, Illinois. I
was invited to speak about the tenth problem, but my
participation in the meeting did not get the necessary
approval in my country, so Julia became the speaker
on the problem; however she suggested that the paper
for the *Proceedings* of the meeting be a joint one by
Martin Davis
and the two of us. Again we had the
problem of an approaching deadline. So we first discussed
by phone what topics each of us would cover.
Of course, Julia and Martin had much more communication
with each other than with me. The final difficult
work of combining our three contributions into a
coherent exposition
[8]
was done by Martin. I believe
that this paper turned out to be one about which Julia
had thought for a long time: a nontechnical introduction
to many results obtained by logicians in connection
with Hilbert’s tenth problem.

Writing the paper for the *Proceedings* prevented me
from immediately writing a paper about the new reduction
to 9 unknowns (clearly it was my turn to write
it up). Unfortunately, Julia firmly refused to be a coauthor.
She wrote: “I do not want to be a joint author
on the 9 unknowns paper — I have told everyone that it
is your improvement and in fact I would feel silly to
have my name on it. If I could make some contribution
it would be different.”

I am sure that without Julia’s contribution to
[7]
and
without her inspiration I would never have reduced __\( N \)__
to 9. I was not inclined to publish the proof by myself,
and so the result announced in
[6]
did not appear in
print with a full proof for a long time. At last
James P. Jones
of the University of Calgary spent half a year in
Berkeley, where Julia and Raphael lived. He studied
my sketch and Julia’s comments on it, and made the
proof available to everybody in
[e8].
The photo accompanying this article was taken in
Calgary at the end of 1982 when I spent three months
in Canada collaborating with James as part of a scientific
exchange program between the Steklov Institute of
Mathematics and Queen’s University at Kingston, Ontario.
Julia at that time was very much occupied with
her new duties as President of the American Mathematical
Society and was not very active in mathematical
research, but she visited Calgary on her way to a
meeting of the Society. Martin also came to Calgary for
a few days.

I conclude these reminiscences with yet another citation from Julia’s letters with which I completely agree: “Actually I am very pleased that working together (thousands of miles apart) we are obviously making more progress than either one of us could alone.”

#### Acknowledgment

*Yuri Matijasevich graduated from Leningrad State University in 1969 and did advanced work at the Steklov Institute of Mathematics, Leningrad Branch. His name became known worldwide in 1970 when he completed the last missing step in the “negative solution” of Hilbert’s tenth problem. For this he received his Doctor of Sciences degree in 1973 and was awarded the Prize in Mathematics named after A. A. Markov (senior) from the Academy of Sciences of the USSR in 1980. His current research area is logic and number theory.*