FOM: Chudnovsky's contribution to MRDP

Martin Davis martind at cs.berkeley.edu
Tue Feb 10 17:17:28 EST 1998

Joe Shipman has requested that I tell what I know about this. It's a long
murky tale, and I'm not sure how relevant it is to F.O.M., but on inquiry,
Steve encouraged me to go ahead.

THE POLITICAL BACKGROUND: In 1969, Yuri Matiyasevich, 22, was in Leningrad,
and Gregory Chudnovsky, 17, was in Kiev. Chudnovsky is Jewish and
Matiyasevich is not. This is relevant because Soviet mathematics was riddled
with anti-semitism, and the Chudnovsky's were later to claim that the denial
of credit to Gregory was part of this pattern.

THE MATHEMATICAL BACKGROUND: In our 1961 paper, Hilary Putnam, Julia
Robinson and I proved the implication:
JR ==> Every r.e. set is Diophantine
where  JR is Julia's hypothesis that there is a Diophantine function f which
is O(x^x) but not O(x^k) for any fixed k. (I never miss an opportunity to
note that Kreisel said in his MR review of this paper "... it is likely the
present result is not closely connected with Hilbert's tenth problem" while
omitting to inform his readers of the above implication.) A 1968 paper of
mine is particularly relevant to Chudnovsky's claim. In that paper, I
introduced the equation 9(x^2+7y^2)^2 - 7(u^2+7v^2)^2 = 2; I deduced JR from
the assumption that that equation had no solutions other than the trivial
x=u=1,y=v=0. In fact that equation has many solutions, but my proof can
easily be modified to show that JR would follow if there are only finitely
many solutions. [That question remains open and not without interest; if
true, it would follow that the Turing degree of the set of Diophantine
equations with infinitely many solutions is exactly 0".]

WHAT YURI MATIYASEVICH DID IN 1970: Yuri gave a (beautiful) Diophantine
definition of the function F_{2n} where F_n is the n-th Fibonacci number,
thereby proving JR.

WHAT GREGORY CHUDNOVSKY PUBLISHED ON THE QUESTION: I know of two relevant
publications. One is a published paper that uses methods very similar to
Yuri's to prove JR, but referring to the solutions of the Pell equation (x^2
- dy^2 = 1) instead of the Fibonacci numbers. Other proofs of JR using the
Pell equation were also given shortly after Yuri's paper, using Yuri's
methods, by Kosovski in Russia and by me (among others). Later work by Yuri
and Julia reducing the total number of unknowns needed in Diophantine
definitions of r.e. sets used the Pell equation.

Gregory's other paper was a crudely mimeographed private publication done in
Kiev. It announced a proof of JR based on my 4th degree equation (mentioned
above), but furnished no details. (See a quotation from this publication in
Matiyasevich's book "HILBERT'S TENTH PROBLEM" MIT 1993, p.39; this book has
a very complete bibliography.)

WHAT JULIA TOLD ME OF HER CONVERSATIONS WITH YURI: Julia spent some time in
Leningrad working with Yuri. She was very concerned about anti-semitism in
Soviet mathematics, not only in connection with Hilbert's tenth problem. She
questioned Yuri closely about Gregory's contribution among other matters.
Yuri claimed that Gregory's published paper was done after Gregory knew his
work, that Gregory had attended a lecture in Kiev given by Yuri, and that he
was entitled to no more credit for his Pell equation proof of JR than
Kosovski or I were for ours. Finally, he stated that although Gregory's
original claim was based on my 4th degree equation, his published proof used
Yuri's methods.

MY CONVERSATION WITH THE CHUDNOVSKY'S: I talked to the Chudnovsky brothers
at the ICM in Helsinki 1978. David did most of the talking. Their story was
that Markov had both proofs (Yuri's and Gregory's) in hand, but simply
decided that "there will be only one solver of Hilbert's tenth problem" and
threw Gregory's out. I mentioned my 4th degree equation to Gregory and
explained why it was still important. I asked whether he had indeed proved
that its number of solutions is finite. He didn't answer my question but
said that that had been long ago and he was currently interested in other
matters.

THE "NEW YORKER" PROFILE: In March 1992, The New Yorker published a
"Profile" article on the Chudnovsky brothers. The article was mainly about
their home-made "super-computer" for which they were seeking financial
support and which they were using to churn out large numbers of decimal
digits of \pi, seeking to discern a pattern. The article briefly mentioned
Gregory's work on Hilbert's tenth problem and quoted the brothers as saying
"Matyasevich [sic] has recently said that the Chudnovsky method is the
preferred way to solve Hilbert's Tenth Problem". I sent Yuri email calling
this to his attention. He indicated that he personally did not intend to
respond, but suggested my writing the magazine asking on what basis the
statement was being made. I did so in a letter briefly explaining my own
involvement with the area and explaining that I wrote at Yuri's suggestion.
I received no reply either to this letter or to a follow-up letter I wrote a
month later.

THE TRUTH: Alas! History is not mathematics. With all of this, I still don't
know what "really" happened in Kiev and Moscow in 1970 and don't imagine
that I ever will. But on the basis of what I do know, I see no reason to
regard the proof of JR as due to anyone but Yuri.

Martin