He was brought up in Leningrad where he began his schooling in 1954. As a young child he had health problems and had two spells in hospital for surgery. Before being hospitalised he had learnt to add large numbers but it was while he was in hospital that a nurse taught him to subtract large numbers. He attended, what he describes as "two very good schools with extra emphasis on mathematics and physics". The first of these was the Leningrad Lyceum 239 from which he graduated in 1963. While at this school he developed a passion for making radio sets, succeeding in 1959. However, this was the year in which his father died and the family were left with relatively little money on which to live. Soon, however, Matiyasevich was taking part in Mathematical Olympiad competitions and proving highly successful.
From the Leningrad Lyceum 239 he went to Moscow where he spent a year at the A N Kolmogorov Physico-mathematical boarding school No 18 which was attached to Moscow State University. Although leaving his mother in Leningrad on her own was difficult for him, the opportunity to go to Moscow presented itself when his uncle, who lived in Moscow, offered financial assistance. Matiyasevich had shown his outstanding mathematical abilities while in Leningrad for he had been highly successful in the Leningrad Mathematical Olympiad Competitions between 1960 and 1963 and in the All-Union Mathematical Olympiads between 1961 and 1963. After going to the boarding school in Moscow he was equally successful in the Moscow Mathematical Olympiad of 1964 as well as the All-Union Mathematical Olympiad of that year. He competed in the International Mathematical Olympiad held in Moscow in 1964 and was awarded a gold medal.
Not only did his excellent performance in the 1964 International Mathematical Olympiad bring him wide recognition but it also had the practical effect of allowing him to enter directly into the Department of Mathematics and Mechanics of Leningrad State University without taking any examinations and also to enter a year early, missing out the final year of his school education :-
... at the beginning of his second year, autumn 1965, Matiyasevich was introduced to Post's canonical systems and his career as a mathematician properly 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. ... Maslov made a number of suggestions for research, which Matiyasevich quickly resolved. In late 1965 Maslov suggested a more difficult question about details of the unsolvability of Thue systems. Matiyasevich solved this problem too.He graduated in 1969 and continued to study for his Candidate's degree (equivalent to a Ph.D.) at the Leningrad Department of the Steklov Institute of Mathematics of the USSR Academy of Sciences with Sergei Maslov as his advisor. While an undergraduate he had already published some important papers (all in Russian): Simple examples of unsolvable canonical calculi (1967), Simple examples of unsolvable associative calculi (1967), Arithmetic representations of powers (1968), A connection between systems of word and length equations and Hilbert's tenth problem (1968), and Two reductions of Hilbert's tenth problem (1968). Before continuing to describe Matiyasevich's career, we should look briefly at "Hilbert's Tenth Problem".
In 1900 at the International Congress of Mathematicians in Paris, David Hilbert decided that he would try to set the agenda for mathematical research for the new century by giving a list of 23 problems. Hilbert saw that efforts to solve these problems would lead to important advances. In fact his talk at the Congress discussed only ten of the problems, but the full list of 23 are discussed in his paper in the Proceedings of the Congress. The Tenth Problem, which interests us here, was not in fact one of the ten which Hilbert discussed in his talk. The problem, as stated by Hilbert, is rather different from the way that it is usually stated today so let us look at both aspects. The original problem is:
Devise a process according to which it can be determined by a finite number of operations whether a given polynomial equation with integer coefficients in any number of unknowns is solvable in rational integers.The more modern statement would be:
Does there exist an algorithm to determine whether a Diophantine equation has a solution in natural numbers?The differences in these two statements are significant. Hilbert believed that an algorithm (i.e. a process determined by a finite number of operations) existed and the problem was to find it. The second version requires the general theory of computability founded by Gödel, Church, Turing and others in the 1930s before it makes precise sense to ask whether an algorithm to solve a particular problem exists. The fact that the second statement asks for a solution in natural numbers while the first asks for a solution in integers is not significant. They are equivalent using the theorem Lagrange proved in 1772, namely that every natural number can be expressed as the sum of the squares of four integers.
In 1934 Thoralf Skolem showed that to solve Hilbert's Tenth Problem, it is sufficient to consider only Diophantine equations of total degree four. Martin Davis made advances in 1953 and he continued to investigate the problem with Hilary Putnam and Julia Robinson. In fact Julia Robinson continued to make progress towards showing that no algorithm existed, publishing an important paper in 1952. Matiyasevich became interested in Hilbert's Tenth Problem when he was an undergraduate in his second year of study. He was advised by Maslov not to read the papers by 'the American mathematicians' and he made a little progress, publishing his results in the papers we mentioned above. He then read the papers by Martin Davis, Hilary Putnam, and Julia Robinson and organised a seminar on Hilbert's Tenth Problem. His fascination with the problem was such that he persisted despite the fact that his teachers and fellow students made fun of him. He said in a November 1999 interview (, see also ):-
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."Eventually he decided that he would have to forget about Hilbert's Tenth Problem and concentrate on other problems for his Candidate's Degree. However (, see also ):-
... 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 is 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. But somewhere in the mathematical heavens there must be a god or goddess of mathematics who would not let me fail to read Julia Robinson's new paper. Because of my early publications on the subject, I was considered a specialist on the tenth problem, and so the paper was sent to me to review. Thus I was forced to read Julia Robinson's paper, and Hilbert's tenth problem captured me again. I saw at once that Julia Robinson had a fresh and wonderful idea. It was connected with the special form of Pell's equation.The new ideas in Julia Robinson's paper Unsolvable Diophantine problems (1969) meant that Matiyasevich could try a new approach to proving that no algorithm existed (, see also ):-
On the morning of 3 January 1970, I believed I had a solution of Hilbert's tenth problem, 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. ... I wrote out a detailed proof without finding any mistake and asked Sergei Maslov and Vladimir Lifshitz to check it, but not to say anything about it to anyone else. 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 Lifshitz. For a fortnight I was skiing, simplifying my proof, and writing the paper. ... 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.The paper he wrote The Diophantineness of enumerable sets (Russian) was published in 1970. J W S Cassels writes:-
This paper shows that every recursively enumerable relation is diophantine and so completes the solution of Hilbert's tenth problem in the negative sense. ... The proof is elementary but ingenious and is said to use ideas of Julia Robinson ...Matiyasevich also published Solution of the tenth problem of Hilbert in Hungarian in 1970.
Solving a problem from Hilbert's famous list took him immediately to the position of one of the world's leading researchers in mathematics. He was awarded his Candidate's degree in 1970 and was appointed as a researcher in the Leningrad Department of the Steklov Institute of Mathematics of the USSR Academy of Sciences. He received the "Young mathematician" prize from the Leningrad Mathematical Society in this same year and received world-wide recognition when he presented his result in his lecture Diophantine representation of recursively enumerable predicates at the International Congress of Mathematicians in Nice in August 1970. In 1972 he was awarded his doctorate (equivalent to a D.Sc. or habilitation) for his thesis Diophantine representation of enumerable predicates which he defended on 24 February. In this thesis, as well as giving a simplified proof that no algorithm exists to determine whether Diophantine equations have integer solutions, he gave a Diophantine representation of a wide class of natural number sequences produced by linear recurrence relations. He also constructed a particular polynomial of degree 21 with 21 variables which has as its positive range precisely the set of prime numbers.
Two years later, in 1974, he was promoted to Senior Researcher. During these years Matiyasevich corresponded with Julia Robinson and the two undertook joint research projects together. This was far more difficult than it sounds, for the cold war meant that all their letters were examined by Soviet censors. They met for the first time at the International Congress for Logic, Methodology and Philosophy of Sciences held in Bucharest, Romania in 1971 where Matiyasevich gave the lecture On recursive unsolvability of Hilbert's tenth problem in which he described the joint work he had been carrying out with Julia Robinson. In 1980 Matiyasevich was appointed head of the Laboratory of Mathematical Logic at the Leningrad Department of the Steklov Institute. In 1995 he was also appointed as Professor of Software Engineering at St Petersburg State University (Leningrad had reverted to its original name of St Petersburg in 1991). Later he was appointed to the chair of Algebra and Number Theory
Matiyasevich published the book Hilbert's tenth problem in Russian in 1993 and, in the same year, an English translation was published. A French translation was published in 1995. Cristian Calude writes in a review of the English translation:-
The book is divided into ten chapters. The first five lead to the negative solution of Hilbert's Tenth Problem; the remaining chapters are devoted to various applications of the method used by the author, which is, in a sense, more important than the solution itself: it has applications to Hilbert's eighth problem, decision problems in number theory, Diophantine complexity, decision problems in calculus, and Diophantine games. ... The book is well written. It will be of great value not only to readers directly interested in Hilbert's Tenth Problem, but, in a broader sense, to potential users of some efficient Diophantine codings.Valentina Harizanov writes :-
This book is exceptional in the sense that all its parts are interesting and important - not only its text, but also its exercises, its commentaries, its appendix, and its foreword in the English translation.Let us give brief details of some more recent work by Matiyasevich. In 2004 he published Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets which he summarises as follows:-
This is a short survey of known results about elimination of quantifiers over natural numbers, and some implications of these results on the power of computer algebra systems.Also in 2004 he published Some probabilistic restatements of the four color conjecture in which he showed that the four colour conjecture can be restated as a small number of assertions about correlations of some random events. These random events are defined in a probabilistic space associated to a triangulation of a sphere. His paper Existential arithmetization of Diophantine equations (2009) continues work related to Hilbert's Tenth problem and, as Alexandra Shlapentokh writes:-
... continues his investigation of coding methods by introducing a coding scheme which, among other things, leads to the elimination of bounded quantifiers, arithmetization of Turing machines, and a much simplified construction of a universal Diophantine equation.In 2010 he published One more probabilistic reformulation of the four colour conjecture continuing the investigation described in the above 2004 paper.
Of the many honours given to Matiyasevich we mention that he was: awarded the A A Markov Prize of the USSR Academy of Sciences (1980); awarded an honorary doctorate by l'Université d'Auvergne (1996); elected a corresponding member of the Russian Academy of Sciences (1997); received the Humboldt Research Award to Outstanding Scholars (1998); elected vice-president of the St Petersburg Mathematical Society (1998); awarded an honorary doctorate by l'Université Pierre et Marie Curie in Paris (2003); elected to the Bavarian Academy of Sciences (2007); and elected as a full member of the Russian Academy of Sciences (2008). He serves on the editorial boards of Discrete Mathematics and Applications and of Computer Instruments in Education.
Article by: J J O'Connor and E F Robertson