Why can Diophantine equations represent exponential growth? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T06:19:08Z http://mathoverflow.net/feeds/question/66511 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66511/why-can-diophantine-equations-represent-exponential-growth Why can Diophantine equations represent exponential growth? lukepalmer 2011-05-31T01:48:43Z 2011-07-06T08:14:02Z <p>The <a href="http://en.wikipedia.org/wiki/Matiyasevich%27s_theorem#Matiyasevich.27s_theorem" rel="nofollow">wikipedia page</a> on Matiyasevich's theorem challenges:</p> <blockquote> <p>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).</p> </blockquote> <p>Anyone care to have a go?</p> http://mathoverflow.net/questions/66511/why-can-diophantine-equations-represent-exponential-growth/66519#66519 Answer by SJR for Why can Diophantine equations represent exponential growth? SJR 2011-05-31T04:31:35Z 2011-06-01T08:16:50Z <p>A simple candidate for a diophantine relation exhibiting exponential growth is the relation between $x$ and $t$ in the equation <code>$x^2-ty^2=1$</code>. According to Barry Mazur ("Questions of Decidability and Undecidability in Number Theory", JSL v59, 1994), the relation <code>$$\phi(t,x):\exists y\,\,\, x^2-ty^2=1$$</code> 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. </p> <p>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". </p> <p>[Added]</p> <p>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</p> <ol> <li><p>For no positive integer n is it true that <code>$\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y&lt;x^n$</code>, and</p></li> <li><p>There is an exponential tower $t$ such that <code>$\forall x,y\in \mathbb{N}\,\, \rho(x,y)\to y&lt;t(x)$</code>, where an "exponential tower" is a function of the form $x^{x^{\ldots}}$.</p></li> </ol> <p>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.)</p> <p>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.</p> <p>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$. </p> http://mathoverflow.net/questions/66511/why-can-diophantine-equations-represent-exponential-growth/69610#69610 Answer by Kaveh for Why can Diophantine equations represent exponential growth? Kaveh 2011-07-06T08:08:04Z 2011-07-06T08:14:02Z <p>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.</p> <p>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 <a href="http://logic.pdmi.ras.ru/~yumat/personaljournal/collaborationjulia/index.html" rel="nofollow">My Collaboration with JULIA ROBINSON </a> by Yuri MATIYASEVICH (skip to the line numbered (6) in the text) or in his book.</p> <hr> <p>"I saw at once that Julia Robinson had a fresh and wonderful idea. It was connected with the special form of Pell's equation</p> <p>(6) $$x^2-(a^2-1)y^2 = 1.$$</p> <p>Solutions $&lt;\chi_0, \psi_0>, &lt;\chi_1, \psi_1>,\cdots, &lt;\chi_n, \psi_n>,\cdots$ of this equation listed in the order of growth satisfy the recurrence relations</p> <p>(7) $$\chi_{n+1}=2a\chi_n-\chi_{n-1}$$<br> $$\psi_{n+1}=2a\psi_n-\psi_{n-1}$$ </p> <p>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</p> <p>(8) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-1)$$</p> <p>is</p> <p>(9) $$0, 1, 2,\cdots, a - 2,$$</p> <p>whereas the period of the sequence</p> <p>(10) $$\chi_0-(a-2)\psi_0,\chi_1-(a-2)\psi_1,\cdots, \chi_n-(a-2)\psi_n,\cdots (\mod 4a-5)$$ </p> <p>begins with</p> <p>(11) $$2^0, 2^1, 2^2,\cdots$$ </p> <p>The main new idea of Julia Robinson was to synchronize the two sequences by imposing a condition $G(a)$ which would guarantee that</p> <p>(12) $$\text{the length of the period of (8) is a multiple of the length of the period of (10).}$$ </p> <p>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.</p> <p>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</p> <p>(13) $$x^2 - xy - y^2=\pm 1$$</p> <p>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</p> <p>(14) $$0, 1, 3, 8, 21, \cdots$$</p> <p>of Fibonacci numbers with even indices satisfies the recurrence relation</p> <p>(15)$$\phi_{n+1}=3\phi_n-\phi_{n-1}$$</p> <p>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</p> <p>(16) $$\psi_0,\psi_1,\cdots,\psi_n,\cdots (\mod a-3)$$</p> <p>because it begins like (14). Moreover, for special values of a the period can be determined explicitly; namely, if</p> <p>(17) $$a = \phi_{2k}+\phi_{2k+2},$$</p> <p>then the period of (16) is exactly</p> <p>(18) $$0,1,3,\cdots,\phi_{2k},-\phi_{2k},\cdots,-3,1.$$</p> <p>The simple structure of the period looked very promising.</p> <p>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.</p> <p>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</p> <p>(19) $$\text{the length of the period of (16) is a multiple of the length of the period of (8).}$$ </p> <p>This $H$, however, could not play the role of Julia Robinson's $G$, which resulted in an essentially different construction."</p>