Fibonacci numbers, 5

A small diversion before we come to the conclusion of this series. I am grateful to Robin Whitty for pointing this out to me.

A set S of positive integers is recursively enumerable if there is a computer program which prints out just the members of S.

In 1971, Yuri Matijasevich gave a resounding negative answer to Hilbert’s tenth problem. Hilbert had asked for a constructive method for determining whether a polynomial diophantine equation has a solution in natural numbers: that is, given a polynomial p(x1,…,xn), there are integer values for the variables which make the value of the polynomial equal to zero. Hilbert wanted an algorithm which would take the polynomial as input and decide whether a solution exists.

An easy argument shows that we may restrict to the case where the values of the variables are positive integers.

Building on work of Martin Davis, Hilary Putnam and Julia Robinson, Matijasevic showed that any recursively enumerable set S of natural numbers could be obtained as the set of positive integer values of a polynomial q with positive integer arguments. That is, the equation x0 = q(x1,…,xn) has a solution in positive integers if and only if x0 belongs to S.

Now a diagonal argument shows that there exist recursively enumerable sets S which are not recursive, that is, there is no algorithm to test membership of S. For such a set, the corresponding diophantine equation has no algorithm for solvability.

Now back to our subject. The Fibonacci numbers are certainly recursively enumerable, since a computer programmed with the recurrence relation and the initial values will print them all out. So the Fibonacci numbers have a Diophantine representation. Here it is:

The solutions (x,y) in positive integers to the equation (x2+xyy2)2−1 = 0 are the pairs of consecutive Fibonacci numbers.

It is easy to show by induction that a pair of consecutive Fibonacci numbers do indeed satisfy x2+xyy2 = ±1. Conversely, suppose that (x,y) satisfies this equation. Then x2y2 ≤ 0, so x ≤ y; and simple manipulation shows that (yx,x) also satisfies the equation. So we may reduce until x = 0, in which case y = 1 and the result is clear.

It is interesting to note that a slightly more complicated Diophantine problem about Fibonacci numbers (namely, finding a Diophantine representation of the set of pairs (x,y) for which y is the 2x-th Fibonacci number) formed the last step in Matijasevic’s proof.

Previous | Next

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , . Bookmark the permalink.

2 Responses to Fibonacci numbers, 5

  1. Pingback: On Fibonacci numbers and the golden ratio « Maximal determinant blog

  2. Pingback: Weekly links for March 25 | God plays dice

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.