Hilbert's Tenth Problem: a History of Mathematical Discovery
(Diophantus, Fermat, Hilbert, Julia Robinson, Nikolay Vorob'ev, Yuri Matiyasevich)

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 "Mathematical Problems" he decided to formulate those mathematical problems, which, in his opinion, should determine development of mathematics in the upcoming century.

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.

Hilbert (1862 - 1943)

Hilbert (1862 - 1943).

In our Museum we will not analyze in detail all 23 Hilbert's problems. We will stay only to one of them: Hilbert's Tenth Problem. Its brilliant solution was made recently (1970) by the Russian mathematician Yuri Matiyasevich. Why we have selected just this Hilbert's problem? The first reason being this problem is already resolved. Secondly, being a subject of our Museum, Fibonacci numbers played an essential role in the solution of this problem.

Diophantus equations

As it is well known, Hilbert's tenth problem is called as "Determining the solvability of a Diophantus equation". To explain an essence of this problem, we should go back more then seventeen centuries into the past to the antique mathematician Diophantus. We know very little about Diophantus, which is considered the last great mathematician of antiquity. His creativity played such an important role in a history of algebra, that many historians of mathematics spent many efforts to establish the true period of his life. It is estimated, that he had lived in the middle of the 3rd century AD for a period of 84 years. Diophantus' main work is called "Arithmetics". This fundamental mathematical treasure consisting of 13 books became a turning point in development of algebra and number theory. In this book there was a final rejection of so-called "geometrical algebra" (when a solution of algebraic problem was reduced to geometrical construction with the help of dividers and ruler) and a passage to new mathematical language, the so-called "alphabetic algebra".

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: the problems of the cube duplication, of the angle trisection, and the circle squaring. Subsequently the fourth problem was also added to these problems: to find out, what polygons with a prime number of the sides can be constructed by dividers and ruler?

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 2x - 2y = 1 cannot have solutions in the domain of integer numbers since its left-hand side is always an even number. Some other equations have a finite set of solutions. For example, the equation 3x = 6 has only one solution x = 2. And finally, some equations have an infinite set of integer solutions. For example, let us solve the equation 7x - 17y = 1:

x = (17y + 1)/7 = 2y + (3y + 1)/7.

The number (3y + 1)/7 must be integer, let us denote it by z. Then 3y + 1 = 7z and x = 2y + z. Thus we have arrived at the equation 3y - 7z = -1 having smaller coefficients than the initial one. Let us apply our "coefficient reduction method" once more:

y = (7z - 1)/3 = 2z + (z - 1)/3.

The number (z - 1)/3 must be integer, let us denote it by t. Then z = 3t + 1, and

y = 2z + t = 7t + 2,

x = 2y + z = 2(7t + 2) + 3t + 1 = 17t + 5.

By taking t = 0, 1, -1, 2, -2, ... we obtain an infinite set of solutions of the equation 7x - 17y = 1 (moreover, this way we obtain all the solutions of this equation):

x = 5, y = 2; x = 22, y = 9; x = -12, y = -5; x = 39, y = 16; ... .

In general, the above "algebraic equations in the domain of integer numbers" can be defined as P = 0, where P is a polynomial with integer coefficients and one, two or more variables (the "unknowns"). For example, 7x2 - 5xy - 3y2 + 2x + 4y - 11 = 0, or x3 + y3 = z3. The problem to be solved is: given an equation P(x, y, ...) = 0, how could we determine, whether it has solutions in the domain of integer numbers, and, if it does, how to find all of them efficiently? Such equations are called Diophantus equations.

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 x2 + y2 = z2, connecting sides x, y, z of a right triangle. The natural numbers x, y and z, being solution of this equation, are called "Pythagorean triples". The numbers of 3, 4, 5 are those, because 32 + 42 = 52. We already mentioned in our Museum, that the triangle with such sides was called "sacred" or "Egyptian" and was used by the ancient Egyptians in the design of Chefren's Pyramid.

The Ancient Greece mathematicians knew all Pythagorean triples, which can be derived from the following formulas:

x = m2 - n2, y = 2mn, z = m2 + n2,

where m n are integers and m > n > 0.

But we can consider Diophantus equations of the following kind:

x3 + y3 = z3, x4 + y4 = z4, x5 + y5 = z5, ... .

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 Fermat's Last Theorem, which states that:

xn + yn = zn

has no non-zero integer solutions for x, y and z when n > 2. In other words, this equation at n > 2 has no solutions in natural numbers.

This equation was written by Fermat on margins of Diophantus' book, where he wrote the following addition: " ... I have discovered a truly remarkable proof which this margin is too small to contain".

From this hypothesis, one of the most exciting areas of mathematics was born: the history of "Fermat's Last Theorem". Ironically nobody was surprised, that Fermat has not kept the proof of this theorem, since he also did not leave any proofs of his arithmetical theorems.

Fermat (1601 - 1665)

Fermat (1601 - 1665).

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' Arithmetica, suggests that his proof was inevitably wrong.

Fermat's 350 years old hypothesis was finally proved on September 19, 1994 by English mathematician Andrew Wiles.

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 David Hilbert stated his famous 23 mathematical problems for the coming XX century (see full text at http://aleph0.clarku.edu/~djoyce/hilbert/problems.html). The 10th of these 23 Hilbert's problems was the following:

10. Determining the solvability of a Diophantus equation.

Given a Diophantus equation with any number of unknowns and with rational integer coefficients: devise a process, which could determine by a finite number of operations whether the equation is solvable in rational integers.

A problem is called a mass problem, if it contains an infinite number of cases. For example, the problem of determining whether n is a prime number, is a mass problem, since it must be solved for an infinite set of values of n. This problem can be solved by many different algorithms (some have simple solutions but take a long time to solve, while others are more complicated but take less time).

Another kind of unsolvable "mass problems" are the so-called decision problems for formal theories. Hilbert's tenth problem relates to the so-called "decision problems", i.e. the problem consisting of an infinite number of individual problems, each requiring a definite answer: YES or NO. The essence of a decision problem is requirement to find a single method that will give an answer to any individual subproblem. Since Diophantus has formulated his famous "Diophantus equations", many of them have later been solved by the number-theorists, and many others have been proved to be unsolvable. Unfortunately to solve different classes of equations and many individual equations, it was necessary to invent different specific methods. In his Tenth problem, Hilbert asks for an universal method for determining the solvability of Diophantus' equations.

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 Martin Davis (see http://cs.nyu.edu/cs/faculty/davism/) made the first step to prove that Hilbert's Tenth problem is unsolvable.

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 (1919 - 1985)

Julia Robinson (1919 - 1985).

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.

Yuri Matiyasevich together wit Maxim Vsemirnov (November 1997, St. Peterburg, Russia)

Yuri Matiyasevich (to the left) together wit Maxim Vsemirnov
(November 1997, St. Peterburg, Russia).

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 (m11, m12, m21, m22) such that

the numbers evidently satisfy the Diofantine equation

m11 ´ m22 - m21 ´ m12 = 1.

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 "however, I was unable to show the undecidability of equations in words and length (and this problem remains an open problem)". There was a necessity in a new idea, which could advance a solution of the problem. And Julia Robinson became the author of such idea. However let us give a word to Yuri Matiyasevich:

"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

x2 - (a2 -1)y2 = 1.(1)

Solutions {c0, f0}, {c1, f1}, ..., {cn, fn}, ... of this equation listed in the order of growth satisfy the recurrent relations

cn+1 = 2acn - cn-1,(2)
fn+1 = 2afn - fn-1(3)

It is easy to see that for any m the sequences 0, 1, ..., f0, f1, ... 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

f0, f1, ..., fn, ...(mod a-1)(4)

is

0, 1, 2, ..., a - 2,

whereas the period of the sequence

c0 - (a - 2) f0, c1 - (a - 2) f1, ..., cn - (a - 2) fn, (mod 4a - 5)(5)

begins with

20, 21, 22, ... .

The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition G(a) which would guarantee that the length of the period of (4) is a multiple of the length of period of (5)".

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 k-th Fibonacci number is divisible by the square of the l-th Fibonacci number if and only if k itself is divisible by the l-th Fibonacci number. This property is not difficult to prove; what is striking is that this beautiful fact has not been discovered, even empirically, since Fibonacci times".

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 Acta Arithmetica. In 1974, the American Mathematical Society organized a symposium on "Mathematical Developments Arising From Hilbert's Problems" at DeKalb, Illinois. Yuri Matiyasevich was invited to speak about Hilbert's tenth problem but his participation in the meeting did not get the necessary approval in the former USSR, so Julia Robinson became the speaker on the problem.

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.

Martin Davis, Julia Robinson, Yuri Matiyasevich Calgary, 1982

From left to right: Martin Davis, Julia Robinson, Yuri Matiyasevich Calgary, 1982.

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".