Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory | SpringerLink
Skip to main content
Springer Nature Link
Log in

Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory

  • Chapter
  • First Online:
Martin Davis on Computability, Computational Logic, and Mathematical Foundations

Part of the book series: Outstanding Contributions to Logic ((OCTR,volume 10))

  • 420 Accesses

Abstract

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.

The author has been partially supported by the NSF grant DMS-1161456.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 20019
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

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.

    Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Google Scholar 

  4. Davis, M. (1973). Hilbert’s tenth problem is unsolvable. American Mathematical Monthly, 80, 233–269.

    Article  Google Scholar 

  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.

    Google Scholar 

  6. Denef, J. (1975). Hilbert’s tenth problem for quadratic rings. Proceedings of the American Mathematical Society, 48, 214–220.

    Google Scholar 

  7. Denef, J. (1980). Diophantine sets of algebraic integers II. Transactions of American Mathematical Society, 257(1), 227–236.

    Article  Google Scholar 

  8. Denef, J., & Lipshitz, L. (1978). Diophantine sets over some rings of algebraic integers. Journal of London Mathematical Society, 18(2), 385–391.

    Article  Google Scholar 

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  12. Eisenträger, K., Miller, R., Park, J., & Shlapentokh, A. Easy as \({\mathbb{Q}}\). Work in progress.

    Google Scholar 

  13. Ershov, Y. L. (1996). Nice locally global fields. I. Algebra i Logika, 35(4), 411–423, 497.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  18. Jarden, M., & Shlapentokh, A. On decidable fields. Work in progress.

    Google Scholar 

  19. Koenigsmann, J. Defining \({\mathbb{Z}}\) in \({\mathbb{Q}}\). Annals of Mathematics. To appear.

    Google Scholar 

  20. Kronecker, L. (1857). Zwei sätze über gleichungen mit ganzzahligen coefficienten. Journal für die Reine und Angewandte Mathematik, 53, 173–175.

    Google Scholar 

  21. Marker, D. (2002). Model theory: An introduction, Graduate texts in mathematics (Vol. 217). New York: Springer.

    Google Scholar 

  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.

    Google Scholar 

  23. Mazur, B. (1992). The topology of rational points. Experimental Mathematics, 1(1), 35–45.

    Google Scholar 

  24. Mazur, B. (1994). Questions of decidability and undecidability in number theory. Journal of Symbolic Logic, 59(2), 353–371.

    Article  Google Scholar 

  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.

    Google Scholar 

  26. Mazur, B., & Rubin, K. (2010). Ranks of twists of elliptic curves and Hilbert’s Tenth Problem. Inventiones Mathematicae, 181, 541–575.

    Article  Google Scholar 

  27. Muchnik, A. A. (1956). On the separability of recursively enumerable sets. Doklady Akademii Nauk SSSR (N.S.), 109, 29–32.

    Google Scholar 

  28. Park, J. A universal first order formula defining the ring of integers in a number field. To appear in Math Research Letters.

    Google Scholar 

  29. Perlega, S. (2011). Additional results to a theorem of Eisenträger and Everest. Archiv der Mathematik (Basel), 97(2), 141–149.

    Article  Google Scholar 

  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.

    Google Scholar 

  31. Poonen, B. Elliptic curves whose rank does not grow and Hilbert’s Tenth Problem over the rings of integers. Private Communication.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  34. Poonen, B. (2008). Undecidability in number theory. Notices of the American Mathematical Society, 55(3), 344–350.

    Google Scholar 

  35. Poonen, B. (2009). Characterizing integers among rational numbers with a universal-existential formula. American Journal of Mathematics, 131(3), 675–682.

    Article  Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  39. Robinson, J. (1949). Definability and decision problems in arithmetic. Journal of Symbolic Logic, 14, 98–114.

    Article  Google Scholar 

  40. Robinson, J. (1959). The undecidability of algebraic fields and rings. Proceedings of the American Mathematical Society, 10, 950–957.

    Article  Google Scholar 

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  43. Rogers, H. (1967). Theory of recursive functions and effective computability. New York: McGraw-Hill.

    Google Scholar 

  44. Rohrlich, D. E. (1984). On \(L\)-functions of elliptic curves and cyclotomic towers. Inventiones Mathematicae, 75(3), 409–423.

    Article  Google Scholar 

  45. Rumely, R. (1980). Undecidability and definability for the theory of global fields. Transactions of the American Mathematical Society, 262(1), 195–217.

    Article  Google Scholar 

  46. Rumely, R. S. (1986). Arithmetic over the ring of all algebraic integers. Journal für die Reine und Angewandte Mathematik, 368, 127–133.

    Google Scholar 

  47. Shlapentokh, A. First order definability and decidability in infinite algebraic extensions of rational numbers. arXiv:1307.0743 [math.NT].

  48. Shlapentokh, A. (1989). Extension of Hilbert’s tenth problem to some algebraic number fields. Communications on Pure and Applied Mathematics, XLII, 939–962.

    Google Scholar 

  49. Shlapentokh, A. (1994). Diophantine classes of holomorphy rings of global fields. Journal of Algebra, 169(1), 139–175.

    Article  Google Scholar 

  50. Shlapentokh, A. (1994). Diophantine equivalence and countable rings. Journal of Symbolic Logic, 59, 1068–1095.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  53. Shlapentokh, A. (2000). Defining integrality at prime sets of high density in number fields. Duke Mathematical Journal, 101(1), 117–134.

    Article  Google Scholar 

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  56. Shlapentokh, A. (2006). Hilbert’s Tenth problem: Diophantine classes and extensions to global fields. Cambridge University Press.

    Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  61. Silverman, J. (1986). The arithmetic of elliptic curves. New York, New York: Springer.

    Book  Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  64. Videla, C. (1999). On the constructible numbers. Proceedings of American Mathematical Society, 127(3), 851–860.

    Article  Google Scholar 

  65. Videla, C. (2000). Definability of the ring of integers in pro-\(p\) extensions of number fields. Israel Journal of Mathematics, 118, 1–14.

    Article  Google Scholar 

  66. Videla, C. R. (2000). The undecidability of cyclotomic towers. Proceedings of American Mathematical Society, 128(12), 3671–3674.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. East Carolina University, Greenville, USA

    Alexandra Shlapentokh

Authors
  1. Alexandra Shlapentokh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexandra Shlapentokh .

Editor information

Editors and Affiliations

  1. University of Trieste, Trieste, Italy

    Eugenio G. Omodeo

  2. University of Udine, Udine, Italy

    Alberto Policriti

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Shlapentokh, A. (2016). Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory. In: Omodeo, E., Policriti, A. (eds) Martin Davis on Computability, Computational Logic, and Mathematical Foundations. Outstanding Contributions to Logic, vol 10. Springer, Cham. https://doi.org/10.1007/978-3-319-41842-1_3

Download citation

Publish with us

Policies and ethics

Search

Navigation