# Yuri Matiyasevich

Yuri Matiyasevich started school in 1954 at the age of seven and school was important to him from the beginning. He also found it easy, except for music. During his early years in school he had to go to the hospital twice for surgery. He had learned to add large numbers and in the hospital, he was taught how to subtract large numbers. In the fifth year, mathematics was taught by a special mathematics teacher, and soon Yuri Matiyasevich was excused from normal mathematics class work as long as he did the homework and passed the tests. He read books on radio for amateurs and was perplexed about how a heterodyne receiver worked, spending hours drawing graphs of sine waves with different frequencies and then adding them to make a third graph [14].

In January 1959 one of Yuri’s friends received a kit to build a superheterodyne radio receiver^{[1]} with four vacuum tubes. They spent hours carefully assembling the kit but it never worked. Yuri received a second kit for his birthday in March and this time, a week after his birthday, he was listening to the radio. He says that this made his father very happy because his father, a construction engineer who designed railroad bridges, was purely a theoretician, and had no talent for doing anything with his hands. But this happiness did not last. A few days after listening to the radio, Yuri’s father died suddenly.

Yuri’s mother served during the Second World War as a typist in the army but afterwards had dedicated her life to raising Yuri and so had no job when his father died. However, the next year in school marked the beginning of mathematics competitions and Yuri’s success in these became a focus for him and a ticket to new opportunities. He did very well in mathematical Olympiads. The seventh year brought the kruzhoks or extra evening classes and he was invited to join. That was not only work but also social events.

The mathematical Olympiads were dedicated to discover which young comrades were the most gifted in mathematics, and special schools were formed often at the instigation of prominent mathematicians. Yuri attended one of those elite schools in Leningrad which officially existed to provide “worker professionals” and supposedly trained operators of mainframe computers. These special schools were called *internats.* An extra year of school for everyone before work at university was added, and experienced mathematicians invested their time teaching gifted young people two days a week.

In 1962 a summer boarding school outside Moscow was organized by A.N. Kolmogorov. Also teaching were P.S. Aleksandrov and V.I. Arnold, among others. Matiyasevich attended. In keeping with these professors’ love not only of mathematics but also of vigorous physical culture, the students were encouraged to swim a wide river and to hike in the woods.

In fall of 1963 a new school was opening in Moscow for able students from outside Moscow as the result of efforts by Kolmorogov and others. An uncle of Matiyasevich who lived in Moscow offered to pay for the extra costs and so Yuri moved to Moscow. Although it was not easy for him to leave Leningrad and his mother behind, he felt that he had to do it. In the summer he had a good class with Arnold, but a geometry course that Kolmogorov taught based on spatial movements rather than lines and points was too abstract for him at age sixteen. Matiyasevich was also, by this time, on something of an Olympiad treadmill. In his own words:

In the spring of 19641 was rather tired, participating every Sunday in some competition. One of them was the selection of the internat team for the all-union Olympiad. I easily passed the selection. During the Olympiad itself I used half of the given time and left, being sure that again I had solved all the problems. I remember that I decided, having saved time at the Olympiad, to walk from the building of the university where the competition took place to the internat situated in the suburbs of Moscow, about two hours walk. I felt that I needed to give myself a bit of rest. I was later disappointed to discover a mistake in a solution to one of the problems.

The same year the International Olympiad was held in Moscow, and Matiyasevich was chosen for the Soviet team, despite the fact that he was only a tenth-year-student. He was not happy about his performance, but still won a diploma of the first degree. Members of the team were granted admission to the university of their choice. Yuri tried to get permission to enroll at Moscow State University, the most prestigious university, but could not make his way through bureaucratic resistance. He still had to get his attestat degree from school. Fed up, he boarded a train for Leningrad. There it was worked out he would take the exams for the attestat in his first school while studying at the university. During this first year, 1964-1965, he was busy with exams and, though he attended a few seminars on logic, he and other first-year-students were forbidden to study logic.

He stayed at Leningrad and, at the beginning of his second year, the fall of 1965, Matiyasevich was introduced to Post’s canonical system and his career as a mathematician began. He immediately achieved an elegant result on a difficult problem the professor proposed. This led him to meet Maslov, the local expert on Post canonical systems. The logical community in the Soviet Union had developed along different paths than in the west. The heavily philosophical tradition of Frege, Carnap, Russell, Whitehead, Godel, and Tarski was at odds with Communist Party doctrine. They had their own logic and it was not symbolic. Therefore, after Kolmogorov’s early bold work, Russian mathematicians had not been quick to pick up and pursue the work in logic of the 1930s. Sometimes mathematical terms were changed. For example, eventually the Russians had their own version of recursive functions and effective computability, which they called the theory of algorithms. In the United States and England the emergence of electronic computers interacted with symbolic logic, while in the Soviet Union this field lagged. Post’s resolutely unphilosophical versions of symbolic logic (it is about rules for generating strings of symbols) was mathematical in its perspective and therefore unsubversive. Thus there were Soviet mathematicians at work in this field.

Maslov made a number of suggestions for research that Matiyasevich quickly resolved. In late 1965 Maslov suggested a more difficult question about details of the unsolvability for Thue systems. Matiyasevich solved this problem and the opportunity to publish the result was offered, but it had to be written up in an entirely rigorous manner in the style of Markov and Post. Matiyasevich was given an Underwood typewriter of manufacture predating the Revolution (by the second wife of his grandfather). He could hardly have been able to buy one of his own. He spent a considerable part of the next year typing. Only five corrections per page were allowed and the paper was 100 pages long. He missed lectures in school, particularly, he says, in complex analysis. He was invited to give a talk at the 1966 International Congress of Mathematicians in Moscow, a major honor, and was particularly impressed to meet Kleene. Toward the end of 1965, Maslov also suggested Hilbert’s tenth problem. He said that “some Americans” had done some work on this problem but that their approach was probably wrong. Matiyasevich did not read their work but, like Davis and Robinson, he was enchanted by the problem and was drawn to it again and again. Once as an undergraduate he thought he had solved it and even began a seminar presenting his solution. He soon discovered his error but became known as the undergraduate who worked on Hilbert’s tenth problem, with an edge of humor. As the years of his undergraduate education passed, like Davis, he too began to think he needed to discipline himself away from this trap of a problem. He did read the work of the Americans and recognized its possible importance. If he could find a Diophantine equation whose solutions grew appropriately, exponentiation would be proved to be Diophantine, and therefore by the Davis-Putnam-Robinson theorem, all recursively enumerable sets would be shown to be Diophantine, and therefore there would exist a Diophantine set that was not decidable. Hilbert’s problem would be solved.

His undergraduate years were ending. He had not done anything better than the early work he had delivered at the International Congress. In his own words:

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!

In the fall of 1969 when a colleague told him to rush to the library to read a new paper by Robinson, a survey on what had been achieved so far in connection with Hilbert’s tenth problem [12], he stayed away. However, because he was considered an expert, he was sent the paper to review and so was forced to read it. He delivered a seminar on it on December 11, 1969. Robinson’s paper had a fresh flavor and a new result, namely that if any infinite set of prime numbers is Diophantine, then the exponential function is Diophantine. Matiyasevich was caught again. He spent December 1969 obsessing over the problem. On the morning of January 3, 1970, he thought he had found a solution but with an error that he was able to fix the next morning. He was now in possession of a solution in the negative of Hilbert’s tenth problem. However, he was afraid there was still an error. After all, he had once gone so far as to start giving a seminar on a solution. He wrote out a full proof and asked both Maslov and Vladimir Lifschits to check it but say nothing until they talked to him again. Matiyasevich then left for a couple of weeks with his soon-to-be wife for a ski camp. There he worked also in refining his paper. He returned to Leningrad to find that the verdict was that he had solved Hilbert’s tenth problem and it was no longer a secret. Both D.K. Faddeev and Markov, famous for finding mistakes, had also checked the proof and passed it. Matiyasevich gave his first public talk on the result on January 29, 1970. News of the result moved around the country. Grigori Tseitin took a copy of the manuscript and, with Matiyasevich’s permission, presented it at a conference in Novosibirisk. An American mathematician John McCarthy attended this talk and it was through him that information about the result made its way to Davis and Robinson.

Whereas Robinson had worked with the sequence of solutions of so-called Pell equations of the special form *x*^{2} - (a^{2} *-* 1)*y ^{2} =* 1, Matiyasevich preferred to use the famous Fibonacci numbers which have rather similar properties. The Fibonacci numbers are defined by the recurrence F

_{0}

*=*0, Fi = 1,

*F*F

_{n+2}=_{n+1}

*+ F*

_{n}. What

Yuri had proved was the set of pairs *{u,* v} such that *v* is the *2u*-th Fibonacci number is Diophantine. Because of the exponential growth of the Fibonacci numbers, it is rather obvious that this set does satisfy the conditions of JR, and for this same reason it was natural to use them in a proof of JR. What had been missing was some kind of Diophantine relation between the number *F _{n}* and the subscript n. Some time previously, Yuri had proved the following important fact:

This finally was indeed a relation between the Fibonacci numbers and their respective subscripts, and it was apparently something that the Americans working on the problem didn’t know, but it required much more than this to obtain Yuri’s Diophantine definition. His proof is a wonderful tapestry, delicate and beautiful. Although it would be difficult to find a clear technical connection between Julia’s paper and Yuri’s breakthrough, Yuri was eager to indicate at least a psychological connection. In this connection he used a Russian word whose literal translation is “wafted”, as though the influence of her paper on his accomplishment was as subtle as that of the scent of a flower.^{[2]} We must point out that at this time, it had still been far from obvious that the tenth problem was near solution or that the solution lay in the direction of Robinson’s hypothesis. Matiyasevich’s adviser had told him to ignore the Americans’ work. In this period even Robinson had at one point despaired of proving her hypothesis. It was necessary for Yuri to recognize that it could be made to work despite all of that.

Matiyasevich had received his kandidat degree, equivalent to a PhD, in 1970 for his early work on Post’s systems. He received his doctoral degree for his work on Hilbert’s tenth.

The key direct result obtained in terms of which a solution of Hilbert’s tenth problem was obtained is that any set that a computer can be programmed to generate, can be generated by a specific Diophantine equation. Many of the major questions in Mathematics, including Fermat’s last theorem, and the four-color map problem, only settled late in the twentieth century, and Goldbach’s conjecture, and the Riemann Hypothesis, both still undecided, can each be seen to be equivalent to a specific

Diophantine equation having no solution [16]. This is simply astounding. In the end, the unsolvability of Hilbert’s tenth problem is richer for mathematicians than a decision process for which Hilbert asked would have been.