Extensions of Hilbert’s tenth problem: definability and decidability in number theory. (English) Zbl 1439.03081

Shlapentokh, Alexandra

Omodeo, Eugenio G. (ed.) et al., Martin Davis on computability, computational logic, and mathematical foundations. Cham: Springer. Outst. Contrib. Log. 10, 55-92 (2016).

Summary: This chapter surveys some of the developments in the area of Mathematics that grew out of the solution of Hilbert’s Tenth Problem by Martin Davis, Hilary Putnam, Julia Robinson and Yuri Matiyasevich.
For the entire collection see [Zbl 1365.03013].

MSC:

03D35	Undecidability and degrees of sets of sentences
03B25	Decidability of theories and sets of sentences
11U05	Decidability (number-theoretic aspects)
03C40	Interpolation, preservation, definability

Keywords:

Hilbert’s tenth problem; Diophantine definability; existential definability; recursively enumerable sets

References:

[1]	Colliot-Thélène, J.-L., Skorobogatov, A., & Swinnerton-Dyer, P. (1997). Double fibres and double covers: Paucity of rational points. Acta Arithmetica, 79, 113-135. · Zbl 0863.14011
[2]	Cornelissen, G., Pheidas, T., & Zahidi, K. (2005). Division-ample sets and diophantine problem for rings of integers. Journal de Théorie des Nombres Bordeaux, 17, 727-735. · Zbl 1161.11323 · doi:10.5802/jtnb.516
[3]	Cornelissen, G., & Zahidi, K. (2000). Topology of diophantine sets: Remarks on Mazur’s conjectures. In J. Denef, L. Lipshitz, T. Pheidas & J. Van Geel (Eds.), Hilbert’s tenth problem: Relations with arithmetic and algebraic geometry, Contemporary mathematics (Vol. 270, pp. 253-260). American Mathematical Society. · Zbl 0982.14014
[4]	Davis, M. (1973). Hilbert’s tenth problem is unsolvable. American Mathematical Monthly, 80, 233-269. · Zbl 0277.02008 · doi:10.2307/2318447
[5]	Davis, M., Matiyasevich, Y., & Robinson, J. (1976). Hilbert’s tenth problem. Diophantine equations: Positive aspects of a negative solution. Proceedings of Symposium on Pure Mathematics, 28, 323- 378. American Mathematical Society. · Zbl 0346.02026
[6]	Denef, J. (1975). Hilbert’s tenth problem for quadratic rings. Proceedings of the American Mathematical Society, 48, 214-220. · Zbl 0324.02032
[7]	Denef, J. (1980). Diophantine sets of algebraic integers II. Transactions of American Mathematical Society, 257(1), 227-236. · Zbl 0426.12009 · doi:10.1090/S0002-9947-1980-0549163-X
[8]	Denef, J., & Lipshitz, L. (1978). Diophantine sets over some rings of algebraic integers. Journal of London Mathematical Society, 18(2), 385-391. · Zbl 0399.10049 · doi:10.1112/jlms/s2-18.3.385
[9]	Denef, J., Lipshitz, L., Pheidas, T., & Van Geel, J. (Eds.). (2000). Hilbert’s tenth problem: Relations with arithmetic and algebraic geometry, Contemporary mathematics (Vol. 270). Providence, RI: American Mathematical Society. Papers from the workshop held at Ghent University, Ghent, November 2-5, 1999. · Zbl 0955.00034
[10]	Eisenträger, K., & Everest, G. (2009). Descent on elliptic curves and Hilbert’s tenth problem. Proceedings of the American Mathematical Society, 137(6), 1951-1959. · Zbl 1267.11120 · doi:10.1090/S0002-9939-08-09740-2
[11]	Eisenträger, K., Everest, G., & Shlapentokh, A. (2011). Hilbert’s tenth problem and Mazur’s conjectures in complementary subrings of number fields. Mathematical Research Letters, 18(6), 1141-1162. · Zbl 1294.11088 · doi:10.4310/MRL.2011.v18.n6.a7
[12]	Eisenträger, K., Miller, R., Park, J., & Shlapentokh, A. Easy as \({\mathbb{Q}} \). Work in progress. · Zbl 1427.11142
[13]	Ershov, Y. L. (1996). Nice locally global fields. I. Algebra i Logika, 35(4), 411-423, 497. · Zbl 0968.12002
[14]	Everest, G., van der Poorten, A., Shparlinski, I., & Ward, T. (2003). Recurrence sequences (Vol. 104). Mathematical Surveys and Monographs Providence, RI: American Mathematical Society. · Zbl 1033.11006
[15]	Fried, M. D., Haran, D., & Völklein, H. (1994). Real Hilbertianity and the field of totally real numbers. In Arithmetic geometry (Tempe, AZ, 1993)Contemporary Mathematics (Vol. 174, pp. 1-34). Providence, RI: American Mathematical Society. · Zbl 0815.12002
[16]	Friedberg, R. M. (1957). Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944). Proceedings of the National Academy of Sciences U.S.A., 43, 236-238. · Zbl 0080.24302 · doi:10.1073/pnas.43.2.236
[17]	Fukuzaki, K. (2012). Definability of the ring of integers in some infinite algebraic extensions of the rationals. MLQ Mathematical Logic Quarterly, 58(4-5), 317-332. · Zbl 1281.11106 · doi:10.1002/malq.201110020
[18]	Jarden, M., & Shlapentokh, A. On decidable fields. Work in progress. · Zbl 1387.12008
[19]	Koenigsmann, J. Defining \({\mathbb{Z}}\) in \({\mathbb{Q}} \). Annals of Mathematics. To appear. · Zbl 1015.03041
[20]	Kronecker, L. (1857). Zwei sätze über gleichungen mit ganzzahligen coefficienten. Journal für die Reine und Angewandte Mathematik, 53, 173-175. · ERAM 053.1389cj
[21]	Marker, D. (2002). Model theory: An introduction, Graduate texts in mathematics (Vol. 217). New York: Springer. · Zbl 1003.03034
[22]	Matiyasevich, Y.V. (1993). Hilbert’s tenth problem. Foundations of computing series. Cambridge, MA: MIT Press. Translated from the 1993 Russian original by the author, With a foreword by Martin Davis. · Zbl 0790.03008
[23]	Mazur, B. (1992). The topology of rational points. Experimental Mathematics, 1(1), 35-45. · Zbl 0784.14012
[24]	Mazur, B. (1994). Questions of decidability and undecidability in number theory. Journal of Symbolic Logic, 59(2), 353-371. · Zbl 0814.11059 · doi:10.2307/2275395
[25]	Mazur, B. (1998). Open problems regarding rational points on curves and varieties. In A. J. Scholl & R. L. Taylor (Eds.), Galois representations in arithmetic algebraic geometry. Cambridge University Press. · Zbl 0943.14009
[26]	Mazur, B., & Rubin, K. (2010). Ranks of twists of elliptic curves and Hilbert’s Tenth Problem. Inventiones Mathematicae, 181, 541-575. · Zbl 1227.11075 · doi:10.1007/s00222-010-0252-0
[27]	Muchnik, A. A. (1956). On the separability of recursively enumerable sets. Doklady Akademii Nauk SSSR (N.S.), 109, 29-32. · Zbl 0071.24602
[28]	Park, J. A universal first order formula defining the ring of integers in a number field. To appear in Math Research Letters. · Zbl 1298.11113
[29]	Perlega, S. (2011). Additional results to a theorem of Eisenträger and Everest. Archiv der Mathematik (Basel), 97(2), 141-149. · Zbl 1234.11073 · doi:10.1007/s00013-011-0277-7
[30]	Pheidas, T. (1988). Hilbert’s tenth problem for a class of rings of algebraic integers. Proceedings of American Mathematical Society, 104(2), 611-620. · Zbl 0697.12020
[31]	Poonen, B. Elliptic curves whose rank does not grow and Hilbert’s Tenth Problem over the rings of integers. Private Communication. · Zbl 1057.11068
[32]	Poonen, B. (2002). Using elliptic curves of rank one towards the undecidability of Hilbert’s Tenth Problem over rings of algebraic integers. In C. Fieker & D. Kohel (Eds.), 7 Number theory, Lecture Notes in Computer Science (Vol. 2369, pp. 33-42). Springer. · Zbl 1057.11068
[33]	Poonen, B. (2003). Hilbert’s Tenth Problem and Mazur’s conjecture for large subrings of \({\mathbb{Q}} \). Journal of AMS, 16(4), 981-990. · Zbl 1028.11077
[34]	Poonen, B. (2008). Undecidability in number theory. Notices of the American Mathematical Society, 55(3), 344-350. · Zbl 1194.03018
[35]	Poonen, B. (2009). Characterizing integers among rational numbers with a universal-existential formula. American Journal of Mathematics, 131(3), 675-682. · Zbl 1179.11047 · doi:10.1353/ajm.0.0057
[36]	Poonen, B., & Shlapentokh, A. (2005). Diophantine definability of infinite discrete non-archimedean sets and diophantine models for large subrings of number fields. Journal für die Reine und Angewandte Mathematik, 27-48, 2005. · Zbl 1139.11056
[37]	Prestel, A., & Schmid, J. (1991). Decidability of the rings of real algebraic and \(p\)-adic algebraic integers. Journal für die Reine und Angewandte Mathematik, 414, 141-148. · Zbl 0717.12006
[38]	Prestel, A. (1981). Pseudo real closed fields. In Set theory and model theory (Bonn, 1979), Lecture notes in mathematics (Vol. 872, pp. 127-156). Berlin-New York: Springer. · Zbl 0466.12018
[39]	Robinson, J. (1949). Definability and decision problems in arithmetic. Journal of Symbolic Logic, 14, 98-114. · Zbl 0034.00801 · doi:10.2307/2266510
[40]	Robinson, J. (1959). The undecidability of algebraic fields and rings. Proceedings of the American Mathematical Society, 10, 950-957. · Zbl 0100.01501 · doi:10.1090/S0002-9939-1959-0112842-7
[41]	Robinson, J. (1962). On the decision problem for algebraic rings. In Studies in mathematical analysis and related topics (pp. 297-304). Stanford, Calif: Stanford University Press. · Zbl 0117.01204
[42]	Robinson, R. M. (1964). The undecidability of pure transcendental extensions of real fields. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 10, 275-282. · Zbl 0221.02034 · doi:10.1002/malq.19640101803
[43]	Rogers, H. (1967). Theory of recursive functions and effective computability. New York: McGraw-Hill. · Zbl 0183.01401
[44]	Rohrlich, D. E. (1984). On \(L\)-functions of elliptic curves and cyclotomic towers. Inventiones Mathematicae, 75(3), 409-423. · Zbl 0565.14006 · doi:10.1007/BF01388636
[45]	Rumely, R. (1980). Undecidability and definability for the theory of global fields. Transactions of the American Mathematical Society, 262(1), 195-217. · Zbl 0472.03010 · doi:10.1090/S0002-9947-1980-0583852-6
[46]	Rumely, R. S. (1986). Arithmetic over the ring of all algebraic integers. Journal für die Reine und Angewandte Mathematik, 368, 127-133. · Zbl 0581.14014
[47]	Shlapentokh, A. First order definability and decidability in infinite algebraic extensions of rational numbers. arXiv:1307.0743 [math.NT]. · Zbl 1436.03204
[48]	Shlapentokh, A. (1989). Extension of Hilbert’s tenth problem to some algebraic number fields. Communications on Pure and Applied Mathematics, XLII, 939-962. · Zbl 0695.12020
[49]	Shlapentokh, A. (1994). Diophantine classes of holomorphy rings of global fields. Journal of Algebra, 169(1), 139-175. · Zbl 0810.11073 · doi:10.1006/jabr.1994.1276
[50]	Shlapentokh, A. (1994). Diophantine equivalence and countable rings. Journal of Symbolic Logic, 59, 1068-1095. · Zbl 0810.11072 · doi:10.2307/2275929
[51]	Shlapentokh, A. (1994). Diophantine undecidability in some rings of algebraic numbers of totally real infinite extensions of \({\mathbb{Q}} \). Annals of Pure and Applied Logic, 68, 299-325. · Zbl 0816.11066 · doi:10.1016/0168-0072(94)90024-8
[52]	Shlapentokh, A. (1997). Diophantine definability over some rings of algebraic numbers with infinite number of primes allowed in the denominator. Inventiones Mathematicae, 129, 489-507. · Zbl 0887.11053 · doi:10.1007/s002220050170
[53]	Shlapentokh, A. (2000). Defining integrality at prime sets of high density in number fields. Duke Mathematical Journal, 101(1), 117-134. · Zbl 1054.11064 · doi:10.1215/S0012-7094-00-10115-9
[54]	Shlapentokh, A. (2000). Hilbert’s tenth problem over number fields, a survey. In J. Denef, L. Lipshitz, T. Pheidas & J. Van Geel (Eds.), Hilbert’s Tenth problem: Relations with arithmetic and algebraic geometry, Contemporary mathematics (Vol. 270, pp. 107-137). American Mathematical Society. · Zbl 0994.03001
[55]	Shlapentokh, A. (2002). On diophantine definability and decidability in large subrings of totally real number fields and their totally complex extensions of degree 2. Journal of Number Theory, 95, 227-252. · Zbl 1082.11079 · doi:10.1016/S0022-314X(01)92759-3
[56]	Shlapentokh, A. (2006). Hilbert’s Tenth problem: Diophantine classes and extensions to global fields. Cambridge University Press. · Zbl 1196.11166
[57]	Shlapentokh, A. (2007). Diophantine definability and decidability in the extensions of degree 2 of totally real fields. Journal of Algebra, 313(2), 846-896. · Zbl 1172.11048 · doi:10.1016/j.jalgebra.2006.11.007
[58]	Shlapentokh, A. (2008). Elliptic curves retaining their rank in finite extensions and Hilbert’s tenth problem for rings of algebraic numbers. Transactions of the American Mathematical Society, 360(7), 3541-3555. · Zbl 1222.11147 · doi:10.1090/S0002-9947-08-04302-X
[59]	Shlapentokh, A. (2009). Rings of algebraic numbers in infinite extensions of \({\mathbb{Q}}\) and elliptic curves retaining their rank. Archive for Mathematical Logic, 48(1), 77-114. · Zbl 1179.11048 · doi:10.1007/s00153-008-0118-y
[60]	Shlapentokh, A. (2012). Elliptic curve points and Diophantine models of \({\mathbb{Z}}\) in large subrings of number fields. International Journal of Number Theory, 8(6), 1335-1365. · Zbl 1316.11112 · doi:10.1142/S1793042112500789
[61]	Silverman, J. (1986). The arithmetic of elliptic curves. New York, New York: Springer. · Zbl 0585.14026 · doi:10.1007/978-1-4757-1920-8
[62]	Tarski, T. (1986). A decision method for elementary algebra and geometry. In Collected papers, S. R. Givant & R. N. McKenzie (Eds.), Contemporary mathematicians (Vol. 3, pp. xiv+682). Basel: Birkhäuser Verlag. 1945-1957.
[63]	van den Dries, L. (1988). Elimination theory for the ring of algebraic integers. Journal für die Reine und Angewandte Mathematik, 388, 189-205. · Zbl 0659.12021
[64]	Videla, C. (1999). On the constructible numbers. Proceedings of American Mathematical Society, 127(3), 851-860. · Zbl 0920.03048 · doi:10.1090/S0002-9939-99-04611-0
[65]	Videla, C. (2000). Definability of the ring of integers in pro-\(p\) extensions of number fields. Israel Journal of Mathematics, 118, 1-14. · Zbl 0984.03034 · doi:10.1007/BF02803513
[66]	Videla, C.