What can and cannot be done with Diophantine problems

Yu. V. Matiyasevich

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Classical and modern mathematics in the wake of Boris Nikolaevich Delone, Tome 275 (2011), pp. 128-143.

Résumé

This survey presents various theorems (obtained mainly by specialists in mathematical logic and computability theory) stating the impossibility of algorithms for solving certain Diophantine problems. Often the technique developed for obtaining such “negative” results also allows one to prove many “positive” theorems on the possibility of formulating Diophantine problems with special properties. This survey also lists a number of questions that remain open.

Bibliographie

[1] Adleman L., Manders K., “Diophantine complexity”, Foundations of computer science, Proc. 17th Annu. Symp., Houston (TX), Oct. 25–27, 1976, IEEE, New York, 1976, 81–88 | MR

[2] Andrews G. E., “E$\Upsilon $PHKA! $\mathrm {num} = \Delta + \Delta + \Delta $”, J. Number Theory, 23:3 (1986), 285–293 | DOI | MR | Zbl

[3] The millennium prize problems, eds. J. Carlson, A. Jaffe, A. Wiles, Amer. Math. Soc., Providence, RI; Clay Math. Inst., Cambridge, MA, 2006 http://www.claymath.org/library/monographs/MPP.pdf | MR

[4] Chaitin G.J., Algorithmic information theory, Cambridge Univ. Press, Cambridge, 1987 | MR | Zbl

[5] Cornelissen G., Zahidi K., “Topology of Diophantine sets: remarks on Mazur's conjectures”, Hilbert's tenth problem: relations with arithmetic and algebraic geometry, Contemp. Math., 270, Amer. Math. Soc., Providence, RI, 2000, 253–260 | DOI | MR | Zbl

[6] Davis M., “Arithmetical problems and recursively enumerable predicates”, J. Symb. Log., 18:1 (1953), 33–41 ; Devis M., “Arifmeticheskie problemy i rekursivno-perechislimye predikaty”, Matematika, 8:5 (1964), 15–22 | DOI | MR | Zbl

[7] Davis M., “Representation theorems for r.e. sets and a conjecture related to Poonen's larges subring of $\mathbb Q$”, Zap. nauch. sem. POMI, 377 (2010), 50–54 | MR | Zbl

[8] Davis M., Matijasevič Yu., Robinson J., “Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution”, Mathematical developments arising from Hilbert problems, Proc. Symp. Pure Math., 28, Amer. Math. Soc., Providence, RI, 1976, 323–378 | DOI | MR

[9] Davis M., Putnam H., Robinson J., “The decision problem for exponential Diophantine equations”, Ann. Math. Ser. 2, 74 (1961), 425–436 ; Devis M., Putnam Kh., Robinson Dzh., “Problema razreshimosti dlya pokazatelno-diofantovykh uravnenii”, Matematika, 8:5 (1964), 69–79 | DOI | MR | Zbl

[10] Denef J., “Hilbert's tenth problem for quadratic rings”, Proc. Amer. Math. Soc., 48:1 (1975), 214–220 | MR | Zbl

[11] Denef J., Lipshitz L., “Power series solutions of algebraic differential equations”, Math. Ann., 267:2 (1984), 213–238 | DOI | MR | Zbl

[12] Garey M.R., Johnson D.S., Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman, San Francisco, CA, 1979 ; Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR | Zbl | MR

[13] Grunewald F., Segal D., “On the integer solutions of quadratic equations”, J. reine und angew. Math., 569 (2004), 13–45 | DOI | MR | Zbl

[14] Hilbert D., “Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker Kongress zu Paris 1900”, Nachr. Kgl. Ges. Wiss. Göttingen. Math.-Phys. Kl., 1900, 253–297 ; Arch. Math. Phys., 1 (1901), 44–63 ; 213–237 ; Gesammelte Abhandlungen, Springer, Berlin, 1935 ; Bd. 3, Chelsea, New York, 1965; Compte rendu du deuxième congrès international des mathématiciens tenu à Paris du 6 au 12 août 1900 Gauthier-Villars, Paris, 1902; Editions Gabay, 1992; Hilbert D., “Mathematical problems”, Bull. Amer. Math. Soc., 8 (1902), 437–479 ; Mathematical developments arising from Hilbert problems, Proc. Symp. Pure Math., 28, Amer. Math. Soc., Providence, RI, 1976, 1–34 ; Гильберт Д., “Математические проблемы”, Проблемы Гильберта, Под ред. П.С. Александрова, Наука, М., 1969, 11–64 | Zbl | Zbl | Zbl | DOI | MR | Zbl

[15] Jones J.P., “Diophantine representation of Mersenne and Fermat primes”, Acta arith., 35:3 (1979), 209–221 | MR | Zbl

[16] Jones J.P., “Some undecidable determined games”, Intern. J. Game Theory, 11:2 (1982), 63–70 | DOI | MR | Zbl

[17] Jones J.P., “Universal Diophantine equation”, J. Symb. Log., 47:3 (1982), 549–571 | DOI | MR | Zbl

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

[19] Jones J.P., Sato D., Wada H., Wiens D., “Diophantine representation of the set of prime numbers”, Amer. Math. Mon., 83 (1976), 449–464 | DOI | MR | Zbl

[20] Kreisel G., “Mathematical significance of consistency proofs”, J. Symb. Log., 23:2 (1958), 155–182 | DOI | MR

[21] Levitz H., “Decidability of some problem pertaining to base 2 exponential Diophantine equations”, Ztschr. math. Log. und Grundl. Math., 31:2 (1985), 109–115 | DOI | MR | Zbl

[22] Matijasevič Ju.V., “Enumerable sets are Diophantine”, Sov. Math. Dokl., 11 (1970), 354–358 ; Mathematical logic in the 20th century, eds. G.E. Sacks, Singapore Univ. Press, Singapore; World Sci. Publ., River Edge, NJ, 2003, 269–273 | DOI | MR | Zbl

[23] Matiyasevich Yu.V., “Diophantine representation of the set of prime numbers”, Sov. Math. Dokl., 12 (1971), 249–254 | Zbl

[24] Matiyasevich Yu.V., “Arifmeticheskie predstavleniya perechislimykh mnozhestv s nebolshim chislom kvantorov”, Zap. nauch. sem. LOMI, 32 (1972), 77–84

[25] Matiyasevich Yu.V., “Suschestvovanie neeffektiviziruemykh otsenok v teorii eksponentsialno diofantovykh uravnenii”, Zap. nauch. sem. LOMI, 40 (1974), 77–93 | Zbl

[26] Matiyasevich Yu.V., “Prostye chisla perechislyayutsya polinomom ot 10 peremennykh”, Zap. nauch. sem. LOMI, 68 (1977), 62–82 | Zbl

[27] Matijasevič Yu.V., “Some purely mathematical results inspired by mathematical logic”, Logic, foundations of mathematics, and computability theory, Proc. 5th Intern. Congr. of Logic, Methodology and Philosophy of Science, London, Ontario (Canada), 1975, Pt. 1, eds. R.E. Butts, J. Hintikka, D. Reidel Publ. Co., Dordrecht, 1977, 121–127 | DOI | MR

[28] Matiyasevich Yu.V., “Algoritmicheskaya nerazreshimost eksponentsialno diofantovykh uravnenii s tremya neizvestnymi”, Teoriya algorifmov i matematicheskaya logika, VTs AN SSSR, M., 1979, 69–78 ; Matiyasevich Yu.V., “Algorithmic unsolvability of exponential Diophantine equations in three unknowns”, Sel. Math. Sov., 3 (1984), 223–232 | MR | Zbl

[29] Matiyasevich Yu.V., Hilbert's tenth problem, MIT Press, Cambridge, MA, 1993 | MR | MR | Zbl | Zbl

[30] Matiiassevitch You., Le dixième problème de Hilbert, Masson, Paris, 1995 http://logic.pdmi.ras.ru/~yumat/H10Pbook | MR | MR | Zbl | Zbl

[31] Matiyasevich Yu., “Diophantine flavor of Kolmogorov complexity”, Trans. Inst. Inform. and Autom. Probl. Nat. Acad. Sci. Armenia, 27 (2006), 111–122

[32] Matiyasevich Yu., “Computation paradigms in light of Hilbert's tenth problem”, New computational paradigms: Changing conceptions of what is computable, eds. S.B. Cooper, B. Löwe, A. Sorbi, Springer, New York, 2008, 59–85 | DOI | MR | Zbl

[33] Matiyasevich Yu., “Existential arithmetization of Diophantine equations”, Ann. Pure and Appl. Log., 157:2–3 (2009), 225–233 | DOI | MR | Zbl

[34] Mazur B., “The topology of rational points”, Exp. Math., 1:1 (1992), 35–45 | MR | Zbl

[35] Mazur B., “Questions of decidability and undesidability in number theory”, J. Symb. Log., 59:2 (1994), 353–371 | DOI | MR | Zbl

[36] Mazur B., Rubin K., “Ranks of twists of elliptic curves and Hilbert's tenth problem”, Invent. math., 181:3 (2010), 541–575 | DOI | MR | Zbl

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

[38] Poonen B., “Hilbert's tenth problem and Mazur's conjecture for large subrings of $\mathbb Q$”, J. Amer. Math. Soc., 16:4 (2003), 981–990 | DOI | MR | Zbl

[39] Pheidas T., Zahidi K., “Undecidability of existential theories of rings and fields: A survey”, Hilbert's tenth problem: relations with arithmetic and algebraic geometry, Contemp. Math., 270, Amer. Math. Soc., Providence, RI, 2000, 49–105 | DOI | MR | Zbl

[40] Putnam H., “An unsolvable problem in number theory”, J. Symb. Log., 25:3 (1960), 220–232 ; Putnam Kh., “Ob odnoi nerazreshimoi probleme arifmetiki”, Matematika, 8:5 (1964), 55–67 | DOI | MR

[41] Rabin M.O., “Effective computability of winning strategies”, Contributions to the theory of games, V. 3, Ann. Math. Stud., 39, eds. M. Dresher, A.W. Tucker, P. Wolff, Princeton Univ. Press, Princeton, NJ, 1957, 147–157 | MR

[42] Robinson J., “Unsolvable diophantine problems”, Proc. Amer. Math. Soc., 22 (1969), 534–538 | DOI | MR | Zbl

[43] Robinson J., The collected works of Julia Robinson, Amer. Math. Soc., Providence, RI, 1996 | MR

[44] Rumely R.S., “Arithmetic over the ring of all algebraic integers”, J. reine und angew. Math., 368 (1986), 127–133 | DOI | MR | Zbl

[45] Shlapentokh A., “A ring version of Mazur's conjecture on topology of rational points”, Intern. Math. Res. Not., 2003, no. 7, 411–423 | DOI | MR | Zbl

[46] Shlapentokh A., Hilbert's tenth problem: Diophantine classes and extensions to global fields, New Math. Monogr., 7, Cambridge Univ. Press, Cambridge, 2007 | MR | Zbl

[47] Siegel C.L., “Zur Theorie der quadratischen Formen”, Nachr. Akad. Wiss. Göttingen. II. Math.-Phys. Kl., 1972, 21–46 | MR | Zbl

[48] Smoryński C., Logical number theory I: An introduction, Springer, Berlin, 1991 | MR | Zbl

[49] Sun Zh.W., “A new relation-combining theorem and its application”, Ztschr. math. Log. und Grundl. Math., 38:3 (1992), 209–212 | DOI | MR | Zbl

[50] Sun Zh.W., “Reduction of unknowns in Diophantine representations”, Sci. China A., 35:3 (1992), 257–269 | MR | Zbl

[51] Vsemirnov M.A., “Beskonechnye mnozhestva prostykh chisel, dopuskayuschie diofantovy predstavleniya s vosemyu peremennymi”, Zap. nauch. sem. POMI, 220 (1995), 36–48 | MR | Zbl