Undecidability in Number Theory

详细信息    查看全文

• 刊名：Lecture Notes in Mathematics
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：1
• 期：1
• 页码：159-195
• 全文大小：466 KB
• 参考文献：1. W. Anscombe, Definability in Henselian fields. Ph.D. thesis, Oxford, 2012
  2. G.L. Cherlin, Undecidability of rational function fields in nonzero characteristic. Stud. Log. Found. Math. 112, 85-5 (1984) CrossRef
  3. G. Cornelissen, K. Zahidi, Elliptic divisibility sequences and undecidable problems about rational points. J. Reine Angew. Math. 613, 1-3 (2007) CrossRef
  4. G. Cornelissen, T. Pheidas, K. Zahidi, Division-ample sets and the Diophantine problem for rings of integers. J. Theor. Nombres Bord. 17, 727-35 (2005) CrossRef
  5. G. Csicsery, Julia Robinson and Hilbert’s Tenth Problem. Documentary film by Zala Films (2010)
  6. L. Darnière, Decidability and local-global principles, in / Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Contemporary Mathematics, vol. 270 (American Mathematical Society, Providence, 2000), pp. 139-67
  7. M. Davis, Arithmetical problems and recursively enumerable predicates. J. Symb. Log. 18(1), 33-1 (1953) CrossRef
  8. M. Davis, Hilbert’s tenth problem is unsolvable. Am. Math. Monthly 80(3), 233-69 (1973) CrossRef
  9. M. Davis, H. Putnam, J. Robinson, The decision problem for exponential Diophantine equations. Ann. Math. (2) 74, 425-36 (1961)
  10. J. Demeyer, Recursively enumerable sets of polynomials over a finite field are Diophantine. Invent. Math. 170(3), 655-70 (2007) CrossRef
  11. J. Denef, Hilbert’s 10th Problem for quadratic rings. Proc. AMS 48, 214-20 (1975)
  12. J. Denef, The diophantine problem for polynomial rings and fields of rational functions. Trans. AMS 242, 391-99 (1978) CrossRef
  13. J. Denef, Diophantine sets over algebraic integer rings II. Trans. AMS 257, 227-36 (1980) CrossRef
  14. J. Denef, The diophantine problem for polynomial rings of positive characteristic, in / Logic Colloquium 78 (North Holland, Amsterdam, 1984), pp. 131-45
  15. J. Denef, L. Lipshitz, Diophantine sets over some rings of algebraic integers. J. Lond. Math. Soc. 18, 385-91 (1978) CrossRef
  16. J. Denef, H. Schoutens, On the decidability of the existential theory of \(\mathbb{F}_{p}[[T]]\) , in / Valuation Theory and Its Applications 2. Fields Institute Communications, vol. 33, ed. by F.-V. Kuhlmann et al. (2003), pp. 43-0, AMS
  17. J. Denef, L. Lipshitz, T. Pheidas, J. Van Geel, / Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Contemporary Mathematics, vol. 270 (American Mathematical Society, Providence, 2000)
  18. J.-L. Duret, Sur la théorie élémentaire des corps de fonctions. J. Symb. Log. 51(4), 948-56
  19. K. Eisentr?ger, Hilbert’s 10th Problem for algebraic function fields of characteristic 2. Pac. J. Math. 210(2), 261-81 (2003) CrossRef
  20. K. Eisentr?ger, A. Shlapentokh, Undecidability in function fields of positive characteristic. Int. Math. Res. Not. 2009, 4051-086 (2009)
  21. A.J. Engler, A. Prestel, / Valued Fields (Springer, Berlin, 2005)
  22. G. Faltings, Diophantine approximation on abelian varieties. Ann. Math. 133, 549-76 (1991) CrossRef
  23. M. Fried, D. Haran, H. V?lklein, Real hilbertianity and the field of totally real numbers. Contemp. Math. 74, 1-4 (1994) CrossRef
  24. M. Fried, M. Jarden, / Field Arithmetic (Springer, Berlin, 1986) [3rd edn., 2008] CrossRef
  25. K. G?del, über formal unentscheidbare S?tze der Principia Mathematica und verwandter Systeme. Monatsh. Math. Phys. 38, 173-98 (1931) CrossRef
  26. B. Green, F. Pop, P. Roquette, On Rumely’s local-global principle. Jber. Dt. Math.-Verein. 97, 43-4 (1995)
  27. D. Hilbert, Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker Kongress zu Paris 1900. Nachr. K. Ges. Wiss. G?ttingen, Math.-Phys. Kl. 3, 253-97 (1900)
  28. M. Hindry, J.H. Silverman, / Diophantine Geometry. Graduate Texts in Mathematics 201 (Springer, Berlin, 2000)
  29. J. Kirby, A. Macintyre, A. Onshuus, The algebraic numbers definable in various exponential fields. J. Inst. Math. Jussieu 11(04), 825-34 (2012) CrossRef
  30. J. Koenigsmann, Defining \(\mathbb{Z}\) in \(\mathbb{Q}\) . Ann. Math. arXiv:1011.3424v1 (2010, to appear)
  31. K.H. Kim, F.W. Roush, Diophantine undecidability of \(\mathbb{C}(t_{1},t_{2})\) . J. Algebra 150(1), 35-4
  32. L. Kronecker, Zwei S?tze über Gleichungen mit ganzzahligen Coefficienten. J. Reine Angew. Math. 53, 173-75 (1857) CrossRef
  33. M. Laczkovich, The removal of \(\pi\) from some undecidable problems involving elementary functions. Proc. AMS 131(7), 2235-240 (2002) CrossRef
  34. L. Lipshitz, The diophantine problem for addition and divisibility. Trans. AMS 235, 271-83 (1978) CrossRef
  35. A. Macintyre, The impact of G?del’s incompleteness theorems on mathematics, in / Kurt G?del, ed. by M. Baaz et al. (Cambridge University Press, Cambridge, 2011), pp. 3-5 CrossRef
  36. A. Macintyre, A. Wilkie, On the decidability of the real exponential field, in / Kreiseliana, ed. by P. Odifreddi (A.K. Peters, Wellesley, 1996), pp. 441-67
  37. Y.V. Matiyasevich, Diofantovost-perechislimykh mnozhestv. Dokl. AN SSSR 191(2), 278-82 (1970) (Translated in: Soviet Math. Doklady 11(2), 354-58, 1970)
  38. Y.V. Matiyasevich, Prostye chisla perechislyayutsya polinomom ot 10peremennykh. J. Sov. Math. 15(19), 33-4 (1981) (translated)
  39. Y.V. Matiyasevich, Hilbert’s 10th Problem: what was done and what is to be done, in / Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Contemporary Mathematics, vol. 270 (American Mathematical Society, Providence, 2000), pp. 1-7
  40. B. Mazur, Questions of decidability and undecidability in number theory. J. Symb. Log. 59(2), 353-71 (1994) CrossRef
  41. B. Mazur, Open problems regarding rational points on curves and varieties, in / Galois Representations in Arithmetic Algebraic Geometry, ed. by A.J. Scholl, R.L. Taylor (Cambridge University Press, Cambridge, 1998), pp. 239-66 CrossRef
  42. B. Mazur, K. Rubin Ranks of twists of elliptic curves and Hilbert’s tenth problem. Invent. Math. 181(3), 541-75 (2010) CrossRef
  43. L. Moret-Bailly, Groupes de Picard et problèmes de Skolem I and II. Ann. Scien. Ec. Norm. Sup. 22(2), 161-79; 181-94 (1989)
  44. O.T. O’Meara, / Introduction to Quadratic Forms (Springer, Berlin, 1973) CrossRef
  45. J. Park, A universal first order formula defining the ring of integers in a number field (2012). arXiv:1202.6371v1
  46. H. Pasten, Powerful values of polynomials and a conjecture of Vojta. J. Number Theory 133(9), 2843-206 (2013) CrossRef
  47. T. Pheidas, Hilbert’s tenth problem for a class of rings of algebraic integers. Proc. AMS 104, 611-20 (1988)
  48. T. Pheidas, Hilbert’s 10th Problem for fields of rational functions over finite fields. Invent. Math. 103, 1- (1991) CrossRef
  49. T. Pheidas, Extensions of Hilbert’s 10th Problem. J. Symb. Log. 59(2), 372-97 (1994) CrossRef
  50. T. Pheidas, Endomorphisms of elliptic curves and undecidability in function fields of positive characteristic. J. Algebra 273(1), 395-11 (2004) CrossRef
  51. T. Pheidas, K. Zahidi, Undecidability of existential theories of rings and fields: a survey, in / Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Contemporary Mathematics, vol. 270 (American Mathematical Society, Providence, 2000), pp. 49-05
  52. B. Poonen, Using elliptic curves of rank one towards the undecidability of Hilbert’s 10th Problem over rings of algebraic integers, in / Algorithmic Number Theory, ed. by C. Fieker, D.R. Kohel (Springer, Berlin, 2002), pp. 33-2 CrossRef
  53. B. Poonen, Hilbert’s 10th problem over rings of number-theoretic interest (2003). www-math.mit.edu/?poonen/papers/aws2003.pdf
  54. B. Poonen, Undecidability in number theory. Not. AMS 55(3), 344-50 (2008)
  55. B. Poonen, Characterizing integers among rational numbers with a universal-existential formula. Am. J. Math. 131(3), 675-82 (2009) CrossRef
  56. B. Poonen, The set of nonsquares in a number field is diophantine. Math. Res. Lett. 16(1), 165-70 (2009) CrossRef
  57. F. Pop, Embedding problems over large fields. Ann. Math. (2) 144(1), 1-4 (1996)
  58. A. Prestel, Pseudo real closed fields, in / Set Theory and Model Theory, ed. by R.B. Jensen, A.?Prestel. Springer Lecture Notes, vol. 872 (1981), pp. 127-56, Springer, Berlin
  59. A. Prestel, P. Roquette, / Formally p-Adic Fields. Springer Lecture Notes, vol. 1050 (1984), Springer, Berlin
  60. A. Prestel, J. Schmid, Existentially closed domains with radical relations. J. Reine Angew. Math. 407, 178-01 (1990)
  61. J. Robinson, Definability and decision problems in arithmetic. J. Symb. Log. 14(2), 98-14 (1949) CrossRef
  62. J. Robinson, Existential definability in arithmetic. Trans. AMS 72, 437-49 (1952) CrossRef
  63. J. Robinson, The undecidability of algebraic rings and fields. Proc. AMS 10, 950-57 (1959) CrossRef
  64. J. Robinson, On the decision problem for algebraic rings, in / Studies in Mathematical Analysis and Related Topics, ed. by G. Szeg? (Stanford University Press, Stanford, 1962), pp. 297-04
  65. R.M. Robinson, Undecidable rings. Trans. AMS 70(1), 137-59 (1951) CrossRef
  66. L.A. Rubel, An essay on diophantine equations for analytic functions. Exp. Math 13, 81-2 (1995)
  67. R. Rumely, Arithmetic over the ring of all algebraic integers. J. Reine Angew. Math. 368(5), 127-33 (1986)
  68. E.S. Selmer, The diophantine equation \(ax^{3} + by^{3} + cz^{3} = 0\) . Acta Math. 85, 203-62 (1951) and 92, 191-97 (1954)
  69. J.-P. Serre, / A Course in Arithmetic (Springer, Berlin, 1973) CrossRef
  70. A. Shlapentokh, Hilbert’s 10th Problem for rings of algebraic functions in one variable over fields of constants of positive characteristic. Trans. AMS 333, 275-98 (1992)
  71. A. Shlapentokh, Hilbert’s 10th problem over number fields, a survey, in / Hilbert’s Tenth Problem: Relations with Arithmetic and Algebraic Geometry. Contemporary Mathematics, vol. 270 (American Mathematical Society, Providence, 2000), pp. 107-37
  72. A. Shlapentokh, / Hilbert’s Tenth Problem, Diophantine Classes and Extensions to Global Fields (Cambridge University Press, Cambridge, 2007)
  73. A. Shlapentokh, H.N. Shapiro, Diophantine relationships between algebraic number fields. Comm. Pure Appl. Math. 42, 1113-122 (1989) CrossRef
  74. J.H. Silverman, / The Arithmetic of Elliptic Curves (Springer, Berlin, 1986) CrossRef
  75. L. van den Dries, Elimination theory for the ring of algebraic integers. J. Reine Angew. Math. 388, 189-05 (1988)
  76. L. van den Dries, / Lectures on the Model Theory of Valued Fields (Springer, Heidelberg, 2014) (this volume)
  77. X. Videaux, An analogue of Hilbert’s 10th problem for fields of meropmorphic functions over non-Archimedean valued fields. J. Number Theory 101, 48-3 (2003) CrossRef
  78. C. Videla, Hilbert’s 10th Problem for rational function fields in characteristic 2. Proc. AMS 120(1), 249-53 (1994)
  79. C. Videla, On the constructible numbers. Proc. AMS 127(3), 851-60 (1999) CrossRef
  80. C. Videla, Definability of the ring of integers in pro- / p Galois extensions of number fields. Isr. J. Math. 118(1), 1-4 (2000) CrossRef
  
• 作者单位：Jochen Koenigsmann (8)
  
  8. Mathematical Institute, Radcliff Observatory Quarter, Oxford, OX2 6GG, UK
  
• ISSN：1617-9692

文摘

In these lecture notes we give sketches of classical undecidability results in number theory, like G?del’s first Incompleteness Theorem (that the first order theory of the integers in the language of rings is undecidable), Julia Robinson’s extensions of this result to arbitrary number fields and rings of integers in them, as well as to the ring of totally real integers, and Matiyasevich’s negative solution of Hilbert’s 10th problem, i.e., the undecidability of the existential first-order theory of the integers. As Hilbert’s 10th problem is still open for the rationals (i.e., the question whether the existential theory of the field of rational numbers is decidable) we also present a sketch of the fact that there is a universal definition of the ring of integers inside the field of rationals. In terms of complexity this is the simplest definition known so far. If one had an existential definition instead then Hilbert’s 10th problem over the rationals would reduce to that over the integers (and hence be, as expected, unsolvable), but, modulo a widely believed in conjecture in number theory, we also indicate why there should be no such existential definition. We conclude with a list of nice open questions in the area.