# Why can Diophantine equations represent exponential growth?

Unfortunately there seems to be as yet no short intuitive explanation as to why Diophantine equations can represent exponential growth only a daunting list of number theoretic lemmas (Note: I've only heard explanations from logicians so if any number theorist wants to show me I'm wrong please do).

Anyone care to have a go?

-
That's a... very strange quote from a wikipedia page. It uses the first person singular? Really? Strange. – Simon Rose May 31 '11 at 5:32
For anyone confused by Simon Rose's comment: Richard Borcherds has just tidied up the Wikipedia page. – Neil Strickland May 31 '11 at 9:41
The section with the first-person-singular phrases is still there. – Will Jagy May 31 '11 at 16:53
It is odd that I can see those comments being taken out in the revision history, but I still see them on the actual page, with no intermediate revisions. – Douglas Zare May 31 '11 at 21:07
@Douglas: You probably want the direct link rather than the redirect (but the redirect should catch up, given some time). en.wikipedia.org/wiki/Diophantine_set#Matiyasevich.27s_theorem – George Lowther Jun 1 '11 at 21:30

A simple candidate for a diophantine relation exhibiting exponential growth is the relation between $x$ and $t$ in the equation $x^2-ty^2=1$. According to Barry Mazur ("Questions of Decidability and Undecidability in Number Theory", JSL v59, 1994), the relation $$\phi(t,x):\exists y\,\,\, x^2-ty^2=1$$ exhibits exponential growth if Gauss's class number conjecture is true, i.e. if there are infinitely many real quadratic fields of class number 1.

Many years before the MRDP theorem was proved, Martin Davis and Julia Robinson boiled down Hilbert's Tenth Problem to the question of the existence of a diophantine relation of exponential growth. See Julia Robinson's 1950 paper "Existential Definability in Arithmetic".

A caveat emptor is appropriate here, as I realized after responding to GH's comment. Julia Robinson shows in her paper that the relation $z=x^y$ is diophantine if there is a diophantine relation $\rho \subseteq\mathbb{N}\times \mathbb{N}$ satisfying

1. For no positive integer n is it true that $\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y<x^n$, and

2. There is an exponential tower $t$ such that $\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y<t(x)$, where an "exponential tower" is a function of the form $x^{x^{\ldots}}$.

Now Mazur's formula provides a (conditional) example of exponential growth in the sense of Julia Robinson's Condition (1), but violates Condition (2), because for a given $t$ there can be infinitely many pairs $x,y$ such that $x^2-ty^2=1$. (For example, when $t$ is square-free and greater than 1.)

This leads to a question that intrigues me: Is there some reasonably simple way to add some polynomial equations and inequalities (in any number of variables) to the equation $x^2-ty^2=1$ that forces the pairs $x,t$ in the equation $x^2-ty^2=1$ to satisfy Julia Robinson's Condition (2)? The result would be a quick proof of MRDP from the class number conjecture.

Incidentally, Mazur does mention that by a theorem of Hua, the least $x$ for which there is some $y$ such that $x^2-ty^2=1$ is bounded by an exponential tower in $t$.

-
If I remember correctly,it would suffice, for MRDP, to have a diophantine relation of at least exponential growth; you don't need a precise rate of growth. Despite this freedom, the known examples all look pretty complicated. – Andreas Blass May 31 '11 at 12:51
@SJR: What is the precise meaning of the statement "$\phi(t,x)$ exhibits exponential growth"? Thanks for your help. – GH from MO May 31 '11 at 17:40
@GH: In Robinson's paper a relation $\rho\subseteq\mathbb{N}\times \mathbb{N}$ has "roughly exponential growth" if (1) For no positive integers $n$ is it true that $\forall x,y\in \mathbb{N} \,\,\rho(x,y)\to y<x^n$, and (2) There is an exponential tower $t$ such that $\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y<t(x)$. Here an "exponential tower" is a function of the form $x^{x^{x\ldots}}$. – SJR May 31 '11 at 22:32
@SJR: Thanks for the explanation. Then your $\phi(t,x)$ has roughly exponential growth assuming the existence of infinitely many real class numbers $h(t)<t^{\frac{1}{2}-\delta}$ for some fixed $\delta>0$. – GH from MO Jun 1 '11 at 9:32
@GH: Did you notice the recently added section of my answer, at the end? – SJR Jun 1 '11 at 10:14

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, which can find in My Collaboration with JULIA ROBINSON by Yuri MATIYASEVICH (skip to the line numbered (6) in the 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."

-