Hilbert's Tenth Problem: a History of Mathematical Discovery About Hilbert's address and his 23 mathematical problems In the summer of 1900 mathematicians met on the Second International Congress in Paris. David Hilbert (1862-1943), the famous German mathematician, Professor of the Goettingen University, was invited to deliver one of the main lectures. As the greatest World mathematician he became famous by his works in algebra and number theory, and shortly before the Congress resolutely, he has rebuilt an axiomatics of the Euclidean geometry in the fundamental work "Foundations of Geometry" (1899). After long doubts Hilbert chose an unusual form of the lecture. In the speech Hilbert's address of 1900 to the International Congress of Mathematicians in Paris is perhaps the most influential speech ever given to mathematicians, given by a mathematician, or given about mathematics. In it, Hilbert outlined 23 major mathematical problems to be studied in the coming century. Some are broad, such as the axiomatization of physics (problem 6) and might never be considered completed. Others, such as problem 3, were much more specific and solved quickly. Some were resolved contrary to Hilbert's expectations, as the continuum hypothesis (problem 1). Hilbert's address was more than a collection of problems. It outlined his philosophy of mathematics and proposed problems important to his philosophy. Although almost a century old, Hilbert's address is still important and should be read (at least in part) by anyone interested in pursuing research in mathematics.
In our Museum we will not analyze in detail all 23 Hilbert's problems. We will stay only to one of them: Diophantus equations As it is well known, Hilbert's tenth problem is called as Already in the 5th century up to AD in the Greek mathematics there appeared mathematical problems, which cannot be resolved by means of the classic geometrical algebra. The most famous of these are the three mathematical problems of antiquity: As it is known, one of the major algebraic problems has always been the solution of algebraic equations, to which many mathematical problems are reduced. The solutions to the equations of the first and second degree "in radicals" did not present any difficulties for mathematicians (any schoolboy knows the general formula for calculus of the second degree algebraic equation radicals). However, the solution of the cubic equations appeared more complicated, and the general formula for solution of such an equation "in radicals" was found only in the 16th century by the Italian mathematicians Ferro and Tartalia. One of the most relevant problems of the theory of algebraic equations in the 17th and 18th centuries became searching for a formula to solve the 5th degree algebraic equations. This research was completed by works of the French mathematician Evarist Galois and resulted in creation of the new algebra. What new ideas did Diophantus introduce in the development of this area, and why is his name until now does not descend from pages of the mathematical tutorials? Problems that can be solved by finding solutions of algebraic equations in the domain of integer numbers are known since the very beginning of mathematics. Some of these equations do not have solutions at all. For example, the equation 2
The number (3
The number (
By taking
In general, the above "algebraic equations in the domain of integer numbers" can be defined as Fermat's Last Theorem The next step would be considering Diophantus equations of 3rd order, 4th order etc. For example, let's consider the algebraic equation The Ancient Greece mathematicians knew all Pythagorean triples, which can be derived from the following formulas:
where But we can consider Diophantus equations of the following kind:
Mathematical research of the French mathematician Fermat have a direct relation to Diophantus equations. It is widely accepted opinion that Fermat's research started the new stage in development of number theory. The most famous of his work is
has no non-zero integer solutions for This equation was written by Fermat on margins of Diophantus' book, where he wrote the following addition: From this hypothesis, one of the most exciting areas of mathematics was born: the history of
Many great mathematicians, such as Euler, Legendre, Êummer, took part in trying to find a generic solution to the "Fermat's Last Theorem", but succeeded only in finding proofs for particular cases. Therefore, Fermat's statement that his proof did not fit on the margins of Diophantus' Fermat's 350 years old hypothesis was finally proved on September 19, 1994 by English mathematician Hilbert's Tenth Problem Until now, we still have no general method of solving an arbitrary degree Diophantus equation. All the sophisticated methods invented by smartest number theorists apply only to very specific types of equations. Why? From August 6th to August 12th 1900, the Second International Congress of Mathematicians took place in Paris. In his Wednesday morning lecture of August 8 10. Determining the solvability of a Diophantus equation. A problem is called a Another kind of unsolvable "mass problems" are the so-called In 1936 Turing, Post and Church, introduced the first formalized concepts of algorithm. Obviously, they also discovered the first unsolvable mass problems. Soon after this, in his Ph.D. theses of 1950 Julia Robinson The name of the American mathematician Julia Robinson cannot be separated from Hilbert's tenth problem. Let us consider scientific biography of Julia Robinson. She was born on December 8, 1919 and died on July 30, 1985 in USA. After graduating from San Diego High School she entered San Diego State College. Later she transferred to the University of California at Berkley. Robinson was awarded a doctorate in 1948 and in the same year started to work on Hilbert's tenth problem. Along with Martin Davis and Hilary Putman she produced a fundamental result, which contributed to the solution of Hilbert's tenth problem. She also did important work on that problem with Matiyasevich after he gave the solution in 1970.
Julia Robinson received many honors. She was the first woman to be elected to the National Academy of Sciences in 1975, the first woman officer of the American Mathematical Society in 1978 and the first woman president of the Society in 1982. She was elected to the American Academy of Arts and Sciences on 1984. She was awarded a MacArthur Fellowship in 1983 in recognition of her contribution to mathematics. Jury Matiyasevich Hilbert's tenth problem had been solved by the young Russian mathematician Yuri Matijasevich in 1970. But who is Yury Matiyasevich? Yuri Matiyasevich was born on March 2, 1947 in Leningrad, the USSR. In 1969 he graduated from Department of Mathematics and Mechanics of Leningrad State University and continued his study as post-graduate student at the Steklov Institute of Mathematics, Leningrad Branch. Since 1970 he works in this institute, currently as the Head of the Laboratory of Mathematical Logic. The name of Yuri Matiyasevich became known worldwide in 1970 when he completed the last missing step in the "negative solution" of Hilbert's tenth problem. Yuri Matiyasevich is Docteur Honoris Causa de Universite d'Auvergne, France (1966) and Correspondent Member of the Russian Academy of Sciences (1997). He stated a history of his discovery and a history of his collaboration with Julia Robinson in his remarkable articles "Hilbert's Tenth Problem: A two-way Bridge between Number Theory and Computer Science" and "My collaboration with Julia Robinson" (http://logic.pdmi.ras.ru/~yumat/Julia/). According to these articles, he began to study Hilbert's tenth problem in 1965 when he was a sophomore in the Department of Mathematics and Mechanics of Leningrad State University. At this time he familiarized himself with the article by Martin Davis, Hilary Putman and Julia Robinson on Hilbert's tenth problem. Matiyasevich's work was greatly influenced by this article and personal contact with Julia Robinson.
The scope of this article does not allow us to include all mathematical details of Yuri Matiyasevich's analysis, which led him to the solution of Hilbert's tenth problem. We would like to try to outline some general ideas concerning to usage of the Fibonacci numbers. However, let us allow Yuri Matiyasevich speak for himself: "The idea was as follows. A universal computer science tool for representing information uses words rather than numbers. However, there are many ways to represent words by numbers. One of such methods is naturally related to Diophantus equations. Namely, it is not difficult to show that every 2 ´ 2 matrix with the m's being non-negative integers and the determinant equal to 1 can be represented, in any unique way, as a product of matrices It is evident that any product of such matrices has non-negative integer elements and the determinant equals 1. This implies that we can uniquely represent a word in two-letter alphabet by the four-tuple ( the numbers evidently satisfy the Diofantine equation
Under this representation of words by matrices, the concatenation of words corresponds to matrix multiplication and thus can be easily expressed as a system of Diophantus equations. This opens a way to transform an arbitrary system of word equations into equivalent Diophantus equations. Many decision problems about words had been shown undecidable, so it was quite natural to try to attack Hilbert's tenth problem by proving the undecidability of systems of word equations". It can be concluded from the following that the main idea of Matiyasevich's approach is reducing a solution of the undecidability of Diophantus equations by proving the undecidability of systems of word equations! In the next passage we can see how Yuri Matiyasevich came up with the idea of using the Fibonacci numbers for solving the Hilbert's tenth problem. Matiyasevich writes: "My next attempt was to consider a broader class of word equations with additional predicates. Since the ultimate goal was always Hilbert's tenth problem, I could consider only such predicates, which (under suitable coding) would be represented by Diophantus equations. In this way I came to what I have called equations in words and length. Reduction of such equations was based on celebrated Fibonacci numbers. It is well known that every natural number can be represented, in an almost unique way, as the sum of different Fibonacci numbers, none of which are consecutive (so called Zeckendorf representation). Thus we can look at natural numbers as words in two-letter alphabet {0, 1} with additional constraint that there cannot be two consecutive 1's. I managed to show that under this representation of words by numbers both the concatenation of words and the equality of the length of two words can be expressed by Diophantus equations". Zeckendorf representation Hardly the Belgian doctor Eduardo Zeckendorf (1901-1983) could guess, that his infatuation with mathematics will appear so severe, that one of his mathematical outcomes will be used at the solution of Hilbert's tenth problem. The question is one of the famous "Zeckendorf's sums" or Zeckendorf's representation". In 1939 he published the article, in which he proved the theorem that every positive integer can be represented uniquely as the sum of non-consecutive Fibonacci numbers. Let us explain this theorem on a simple example. Suppose it is required to present the number 30 in the Fibonacci code. Let us choose the following Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21 as digit weights for such representation. Then there are some ways of the number 30 representation using sums of the Fibonacci numbers: 30 = 21 + 8 + 1 = 21 + 5 + 3 + 1 = 13 + 8 + 5 + 3 + 1 = 13 + 8 + 5 + 2 + 1 + 1. But among them it is possible to select one and only one representation 30 = 21 + 8 + 1, in which no consecutive Fibonacci numbers are being used. Note, that the mentioned above "Zeckendorf representation" is called also the "minimal form". The minimal form is a basis of "Fibonacci Arithmetic" considered above in our Museum. It should be noted, that many articles on the subject of "Zeckendorf's sums" were published in "The Fibonacci Quarterly". Striking Julia Robinson However the idea of usage of Fibonacci numbers and "Zeckendorf representation" was only some relevant step in the solution of Hilbert's tenth problem. As Matijasevich recalls "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 who would let me fail to read Julia Robinson's new paper. Because of my early publications on the subject, I was considered as a specialist on it and so the paper was sent to me to review for "Mathematics Reference Journal", 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 idea. It was connected with the special form of Pell's equation
Solutions {c
It is easy to see that for any m the sequences ñ
is 0, 1, 2, ..., whereas the period of the sequence
begins with 2 The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition G(a) which would guarantee that We would not go deep into very nice mathematical reasoning's by Julia Robinson and we will take on faith her outstanding mathematical result and again we address to Matiyasevich's articles to evaluate how its result influenced on his mathematical discovery. Vorob'ev's Theorem Yuri Matiyasevich wrote: "Due my previous work, I realized the importance of Fibonacci numbers for Hilbert's tenth problem. That is why during summer of 1969 I was reading with great interest the third augmented edition of a popular book on Fibonacci numbers written by N.N. Vorob'ev from Leningrad. It seems incredible that in the 20th century one can still find something new about the numbers introduced by Fibonacci in the 13th century in connection with multiplying rabbits. However, the new edition of the book contained, besides traditional stuff, some original results of the author. In fact, Vorob'ev had obtained them a quarter of a century earlier but he never published anything before. His results attracted my attention at once but I was not able to use them immediately for constructing a Diophantus representation of a relation of exponential growth". Evaluating Vorob'ev's and Robinson's influence on his solution of Hilbert's tenth problem Matiyasevich wrote: "The period when I was not thinking about Diophantus equations, Vorob'ev theorem and new ideas of Julia Robinson led me to negative solution of Hilbert's tenth problem. On January, 1970 I gave at my institute the first talk on a Diophantus relation of exponential growth ... Surprisingly, in order to construct a Diophantus representation for this relation I needed to proof a yet new purely number-theoretical result about Fibonacci numbers, that And further Yuri Matiyasevich evaluated a role of Nikolay Vorob'ev and Julia Robinson in his solution of Hilbert's tenth problem as the following: "My original proof ...was based on a theorem proved by the Soviet mathematician Nikolay Vorob'ev in 1942 but published only in the third augmented edition of his popular book. ... After I read Julia Robinson's paper I immediately saw that Vorob'ev's theorem could be very useful. Julia Robinson did not see the third edition of Vorob'v's book 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!" Julia Robinson and Yuri Matiyasevich About influence of Julia Robinson works on his research Yuri Matiyasevich wrote the following: "I tried to convey the impact of Julia Robinson's paper 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". The first meeting of Julia Robinson and Yuri Matiyasevich, two outstanding contemporary mathematicians, took place in Bucharest during the IV International Congress on Logic, Methodology and Philosophy of Science. Their first meeting became a beginning of their friendship, which found itself highly productive in creative relation. In 1973, the prominent Soviet mathematician A.A. Markov celebrated his seventieth birthday. His colleagues from the Computing Center of the Academy of Science of the USSR decided to publish a collection of papers in his honor. Yuri Matiyasevich was invited to contribute to the collection. According to his initiative the first joint paper with Julia Robinson was submitted to the collection and the editors agreed with such proposal. Their second joint paper was published on The photo below was taken in Calgary at the end of 1982 when Yuri Matiyasevich spent three months in Canada as participant of a scientific exchange program between the Steklov Institute of Mathematics and Queen's University at Kingston. Ontario. At that time Julia Robinson was very much occupied with her new duties as President of the American Mathematical Society but she was able to visit Calgary on her way to a meeting of the Society. Martin Davis also came to Calgary for a few days.
We would like to conclude this article on a history of the outstanding mathematical discovery with quote from Julia Robinson's letter to Yuri Matiyasevich: "Actually I am very pleased that working together (thousands miles apart) we are obviously making more progress than either one of us could alone". |