2 added 88 characters in body

The intuition I have is that relations definable by polynomials is complicated enough that projections can give rise to very complicated sets. The essential point here is not exponential growth, that comes from the unboundedness of the quantifiers, the essential point is that the graph of a very fast growing function can be represented by a polynomial.

On the other hand, if the question is about how polynomial equations can represent graphs of complicated function, then I guess the best explanation is by the people who came up with the idea of how to use these equations to represent the graph of a fast growing function, you which can find about it in My Collaboration with JULIA ROBINSON by Yuri MATIYASEVICH (skip to the line numbered (6) in the text):text) or in his book.

"I saw at once that Julia Robinson had a fresh and wonderful idea. It was connected with the special form of Pell's equation

(6) $$x^2-(a^2-1)y^2 = 1.$$

Solutions $<\chi_0, \psi_0>, <\chi_1, \psi_1>,\cdots, <\chi_n, \psi_n>,\cdots$ of this equation listed in the order of growth satisfy the recurrence relations

(7) $$\chi_{n+1}=2a\chi_n-\chi_{n-1}$$
$$\psi_{n+1}=2a\psi_n-\psi_{n-1}$$

It is easy to see that for any $m$ the sequences $\chi_0,\chi_1,\cdots, \psi_0,\psi_1,\cdots$ 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

(8) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-1)$$

is

(9) $$0, 1, 2,\cdots, a - 2,$$

whereas the period of the sequence

(10) $$\chi_0-(a-2)\psi_0,\chi_1-(a-2)\psi_1,\cdots, \chi_n-(a-2)\psi_n,\cdots (\mod 4a-5)$$

begins with

(11) $$2^0, 2^1, 2^2,\cdots$$

The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition $G(a)$ which would guarantee that

(12) $$\text{the length of the period of (8) is a multiple of the length of the period of (10).}$$

If such a condition is Diophantine and is valid for infinitely many values of $a$, then one can easily show that the relation $a = 2^c$ is Diophantine. Julia Robinson, however, was unable to find such a $G$ and, even today, we have no direct method for finding one.

I liked the idea of synchronization very much and tried to implement it in a slightly different situation. When, in 1966, I had started my investigations on Hilbert's tenth problem, I had begun to use Fibonacci numbers and had discovered (for myself) the equation

(13) $$x^2 - xy - y^2=\pm 1$$

which plays a role similar to that of the above Pell's equation; namely, Fibonacci numbers $\phi_n$ and only they are solutions of (13). The arithmetical properties of the sequences $\psi_n$ and $\phi_n$ are very similar. In particular, the sequence

(14) $$0, 1, 3, 8, 21, \cdots$$

of Fibonacci numbers with even indices satisfies the recurrence relation

(15)$$\phi_{n+1}=3\phi_n-\phi_{n-1}$$

similar to (7). This sequence grows like $[(3+\sqrt 5)/2]^n$ and can be used instead of (11) for constructing a relation of exponential growth. The role of (10) can be played by the sequence

(16) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-3)$$

because it begins like (14). Moreover, for special values of a the period can be determined explicitly; namely, if

(17) $$a = \phi_{2k}+\phi_{2k+2},$$

then the period of (16) is exactly

(18) $$0,1,3,\cdots,\phi_{2k},-\phi_{2k},\cdots,-3,1.$$

The simple structure of the period looked very promising.

I was thinking intensively in this direction, even on the night of New Year's Eve of 1970, and contributed to the stories about absentminded mathematicians by leaving my uncle's home on New Year's Day wearing his coat. On the morning of January 3, I believed I had found a polynomial B as in (5) 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.

What was to be done next? As a student I had had a bad experience when once I had claimed to have proved unsolvability of Hilbert's tenth problem, but during my talk found a mistake. I did not want to repeat such an embarrassment, and something in my new proof seemed rather suspicious to me. I thought at first that I had just managed to implement Julia Robinson's idea in a slightly different situation. However, in her construction an essential role was played by a special equation that implied one variable was exponentially greater than another. My supposed proof did not need to use such an equation at all, and that was strange. Later I realized that my construction was a dual of Julia Robinson's. In fact, I had found a Diophantine condition $H(a)$ which implied that

(19) $$\text{the length of the period of (16) is a multiple of the length of the period of (8).}$$

This $H$, however, could not play the role of Julia Robinson's $G$, which resulted in an essentially different construction."

1

The intuition I have is that relations definable by polynomials is complicated enough that projections can give rise to very complicated sets. The essential point here is not exponential growth, that comes from the unboundedness of the quantifiers, the essential point is that the graph of a very fast growing function can be represented by a polynomial.

On the other hand, if the question is about how polynomial equations can represent graphs of complicated function, then I guess the best explanation is by the people who came up with the idea, you can find about it in My Collaboration with JULIA ROBINSON by Yuri MATIYASEVICH (skip to the line numbered (6) in the text):

"I saw at once that Julia Robinson had a fresh and wonderful idea. It was connected with the special form of Pell's equation

(6) $$x^2-(a^2-1)y^2 = 1.$$

Solutions $<\chi_0, \psi_0>, <\chi_1, \psi_1>,\cdots, <\chi_n, \psi_n>,\cdots$ of this equation listed in the order of growth satisfy the recurrence relations

(7) $$\chi_{n+1}=2a\chi_n-\chi_{n-1}$$
$$\psi_{n+1}=2a\psi_n-\psi_{n-1}$$

It is easy to see that for any $m$ the sequences $\chi_0,\chi_1,\cdots, \psi_0,\psi_1,\cdots$ 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

(8) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-1)$$

is

(9) $$0, 1, 2,\cdots, a - 2,$$

whereas the period of the sequence

(10) $$\chi_0-(a-2)\psi_0,\chi_1-(a-2)\psi_1,\cdots, \chi_n-(a-2)\psi_n,\cdots (\mod 4a-5)$$

begins with

(11) $$2^0, 2^1, 2^2,\cdots$$

The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition $G(a)$ which would guarantee that

(12) $$\text{the length of the period of (8) is a multiple of the length of the period of (10).}$$

If such a condition is Diophantine and is valid for infinitely many values of $a$, then one can easily show that the relation $a = 2^c$ is Diophantine. Julia Robinson, however, was unable to find such a $G$ and, even today, we have no direct method for finding one.

I liked the idea of synchronization very much and tried to implement it in a slightly different situation. When, in 1966, I had started my investigations on Hilbert's tenth problem, I had begun to use Fibonacci numbers and had discovered (for myself) the equation

(13) $$x^2 - xy - y^2=\pm 1$$

which plays a role similar to that of the above Pell's equation; namely, Fibonacci numbers $\phi_n$ and only they are solutions of (13). The arithmetical properties of the sequences $\psi_n$ and $\phi_n$ are very similar. In particular, the sequence

(14) $$0, 1, 3, 8, 21, \cdots$$

of Fibonacci numbers with even indices satisfies the recurrence relation

(15)$$\phi_{n+1}=3\phi_n-\phi_{n-1}$$

similar to (7). This sequence grows like $[(3+\sqrt 5)/2]^n$ and can be used instead of (11) for constructing a relation of exponential growth. The role of (10) can be played by the sequence

(16) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-3)$$

because it begins like (14). Moreover, for special values of a the period can be determined explicitly; namely, if

(17) $$a = \phi_{2k}+\phi_{2k+2},$$

then the period of (16) is exactly

(18) $$0,1,3,\cdots,\phi_{2k},-\phi_{2k},\cdots,-3,1.$$

The simple structure of the period looked very promising.

I was thinking intensively in this direction, even on the night of New Year's Eve of 1970, and contributed to the stories about absentminded mathematicians by leaving my uncle's home on New Year's Day wearing his coat. On the morning of January 3, I believed I had found a polynomial B as in (5) 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.

What was to be done next? As a student I had had a bad experience when once I had claimed to have proved unsolvability of Hilbert's tenth problem, but during my talk found a mistake. I did not want to repeat such an embarrassment, and something in my new proof seemed rather suspicious to me. I thought at first that I had just managed to implement Julia Robinson's idea in a slightly different situation. However, in her construction an essential role was played by a special equation that implied one variable was exponentially greater than another. My supposed proof did not need to use such an equation at all, and that was strange. Later I realized that my construction was a dual of Julia Robinson's. In fact, I had found a Diophantine condition $H(a)$ which implied that

(19) $$\text{the length of the period of (16) is a multiple of the length of the period of (8).}$$

This $H$, however, could not play the role of Julia Robinson's $G$, which resulted in an essentially different construction."