Towards finite-fold Diophantine representations

Yu. Matiyasevich

Zapiski Nauchnykh Seminarov POMI, Studies in number theory. Part 10, Tome 377 (2010), pp. 78-90

Résumé

Celebrated theorem established by Martin Davis, Hilary Putnam, and Julia Robinson in 1961 states that every effectively enumerable set of natural numbers has an exponential Diophantine representation. This theorem was improved by the author in two ways: $\bullet$ to the existence of Diophantine representation, $\bullet$ to the existence of so-called single-fold exponential Diophantine representation. However, it remains unknown whether these two improvements could be combined, that is, whether every effectively enumerable set has a single-fold (or at least finite-fold) Diophantine representation. In the paper, we discuss known results about single-fold exponential Diophantine representations, their applications, possible approaches to improving to the case of genuine Diophantine representations, and what would follow if such improvement is impossible. Bibl. 27 titles.

Bibliographie

[1] A. Baker, H. Davenport,, “The equations $3x^2-2=y^2$ and $8x^2-7=z^2$”, Quart. J. Math. Oxford Ser. (2), 20 (1969), 129–137 | DOI | MR | Zbl

[2] G. Chaitin, Algorithmic Information Theory, Cambridge University Press, Cambridge, England, 1987 | MR | Zbl

[3] G. V. Chudnovskii, Nekotorye algoritmicheskie problemy, Preprint IM-71-3, AN Ukr. SSR, Institut Matematiki, Kiev, 1971

[4] G. V. Chudnovsky, “Some Diophantine problems”, Contributions to the theory of transcendental numbers, Math. Surveys Monogr., 19, Amer. Math. Soc., Providence, RI, 1984, 265–295 | DOI | MR

[5] M. Davis, “Arithmetical problems and recursively enumerable predicates”, J. Symbolic Logic, 18:1 (1953), 33–41 | DOI | MR | Zbl

[6] M. Davis, H. Putnam, J. Robinson, “The decision problem for exponential Diophantine equations”, Ann. Math. (2), 74 (1961), 425–436 ; reprinted in: S. Feferman (ed.), The collected works of Julia Robinson, Collected Works, v. 6, Amer. Math. Soc., Providence, RI, 1996 | DOI | MR | Zbl | MR

[7] M. Davis, “One equation to rule them all”, Transactions of the New York Academy of Sciences. Series II, 30:6 (1968), 766–773 | DOI | Zbl

[8] M. Davis, “On the number of solutions of Diophantine equations”, Proc. Amer. Math. Soc., 35 (1972), 552–554 | DOI | MR | Zbl

[9] O. Herrman, “A nontrivial solution of the Diophantine equation $9(x^2+7y^2)^2-7(u^2+7v^2)^2=2$”, Computers in Number Theory, eds. A. O. L. Atkin, B. J. Birch, Academic Press, London, 1971, 207–212 | MR | Zbl

[10] Mathematical Developments arising from Hilbert problems, Proceedings of Symposia in Pure Mathematics, 28, ed. Browder Ed., American Mathematical Society, 1976, 1–34 | MR | Zbl

[11] J. P. Jones, Yu. V. Matijasevič, “A new representation for the symmetric binomial coefficient and its applications”, Annales Sci. Mathém. du Québec, 6:1 (1982), 81–97 | MR | Zbl

[12] E. E. Kummer, “Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen”, J. reine angew. Math., 44 (1852), 93–146 | DOI | Zbl

[13] D. H. Lehmer, “Continued fractions containing arithmetic progressions”, Scripta Math., 29 (1973), 17–24 | MR | Zbl

[14] H. Levitz, “Decidability of some problem pertaining to base 2 exponential Diophantine equations”, Zeitschrift Math. Logik Grundlagen Math., 31:2 (1985), 109–115 | DOI | MR | Zbl

[15] “Enumerable sets are Diophantine”, Soviet Math. Dokl., 11 (1970), 354–358 | Zbl

[16] “Existence of noneffectivizable estimates in the theory of exponential Diophantine equations”, J. of Soviet Mathematics, 8:3 (1977), 299–311 | DOI | MR | Zbl | Zbl

[17] “Algorithmic unsolvability of exponential Diophantine equations in three unknowns”, Sel. Math. Sov., 3 (1984), 223–232 | MR | Zbl

[18] Yu. V. Matiyasevich, Desyataya problema Gilberta, Nauka, Fizmatlit, Moskva, 1993 ; English translation: Hilbert's Tenth Problem, MIT Press, Cambridge (Massachusetts)–London, 1993 ; French translation: Le dixième Problème de Hilbert, Masson, Paris–Milan–Barselone, 1995; http://logic.pdmi.ras.ru/~yumat/H10Pbook | MR | Zbl | Zbl

[19] Yu. Matiyasevich, “Diophantine flavor of Kolmogorov complexity”, Trans. Inst. Informatics and Automation Problems National Acad. Sciences of Armenia, 27 (2006), 111–122

[20] J. Mc Laughlin, “Some new families of Tasoevian and Hurwitzian continued fractions”, Acta Arith., 135:3 (2008), 247–268 | DOI | MR | Zbl

[21] T. Ord, T. D. Kieu, “On the existence of a new family of Diophantine equations for $\Omega$”, Fundam. Inform., 56:3 (2003), 273–284 | MR | Zbl

[22] K. Prasad, “Computability and randomness of Nash equilibrium in infinite games”, J. Mathem. Economics, 20:5 (1991), 429–442 | DOI | MR | Zbl

[23] P. Riyapan, V. Laohakosol, T. Chaichana, “Two types of explicit continued fractions”, Period. Math. Hungar., 52:2 (2006), 51–72 | DOI | MR | Zbl

[24] J. Robinson, “Existential definability in arithmetic”, Transactions of the American Mathematical Society, 72 (1952), 437–449 ; reprinted in: The Collected Works of Julia Robinson, Collected Works, 6, American Mathematical Society, Providence, RI, 1996, 47–59 | DOI | MR | Zbl | MR

[25] D. Shanks, S. S. Wagstaff Jr., “48 more solutions of Martin Davis's quaternary quartic equation”, Math. Comp., 64:212 (1995), 1717–1731 | MR | Zbl

[26] C. Smoryński, “A note on the number of zeros of polynomials and exponential polynomials”, J. Symbolic Logic, 42:1 (1977), 99–106 | DOI | MR | Zbl

[27] B. G. Tasoev, “Ratsionalnye proiblizheniya k nekotorym beskonechnym tsepnym drobyam”, Trudy tbilisskogo universiteta. Mat., mekh., astronom., 24, 1988, 104–138 | MR | Zbl