As easy as ℚ: Hilbert’s Tenth Problem for subrings of the rationals and number fields

Eisenträger, Kirsten; Miller, Russell; Park, Jennifer; Shlapentokh, Alexandra

doi:10.1090/tran/7075

As easy as $\mathbb {Q}$: Hilbert’s Tenth Problem for subrings of the rationals and number fields
HTML articles powered by AMS MathViewer

by Kirsten Eisenträger, Russell Miller, Jennifer Park and Alexandra Shlapentokh PDF

Trans. Amer. Math. Soc. 369 (2017), 8291-8315 Request permission

Abstract:

Hilbert’s Tenth Problem over the rationals is one of the biggest open problems in the area of undecidability in number theory. In this paper we construct new, computably presentable subrings $R \subseteq \mathbb {Q}$ having the property that Hilbert’s Tenth Problem for $R$, denoted $\operatorname {HTP}(R)$, is Turing equivalent to $\operatorname {HTP}(\mathbb {Q})$.

We are able to put several additional constraints on the rings $R$ that we construct. Given any computable nonnegative real number $r\leq 1$ we construct such rings $R=\mathbb {Z}[\mathcal {S}^{-1}]$ with $\mathcal {S}$ a set of primes of lower density $r$. We also construct examples of rings $R$ for which deciding membership in $R$ is Turing equivalent to deciding $\operatorname {HTP}(R)$ and also equivalent to deciding $\operatorname {HTP}(\mathbb {Q})$. Alternatively, we can make $\operatorname {HTP}(R)$ have arbitrary computably enumerable degree above $\operatorname {HTP}(\mathbb {Q})$. Finally, we show that the same can be done for subrings of number fields and their prime ideals.

References

Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
Gunther Cornelissen, Thanases Pheidas, and Karim Zahidi, Division-ample sets and the Diophantine problem for rings of integers, J. Théor. Nombres Bordeaux 17 (2005), no. 3, 727–735 (English, with English and French summaries). MR 2212121
Gunther Cornelissen and Karim Zahidi, Topology of Diophantine sets: remarks on Mazur’s conjectures, Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999) Contemp. Math., vol. 270, Amer. Math. Soc., Providence, RI, 2000, pp. 253–260. MR 1802017, DOI 10.1090/conm/270/04377
J. Denef, The Diophantine problem for polynomial rings of positive characteristic, Logic Colloquium ’78 (Mons, 1978) Studies in Logic and the Foundations of Mathematics, vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 131–145. MR 567668
J. Denef, Diophantine sets over algebraic integer rings. II, Trans. Amer. Math. Soc. 257 (1980), no. 1, 227–236. MR 549163, DOI 10.1090/S0002-9947-1980-0549163-X
J. Denef and L. Lipshitz, Diophantine sets over some rings of algebraic integers, J. London Math. Soc. (2) 18 (1978), no. 3, 385–391. MR 518221, DOI 10.1112/jlms/s2-18.3.385
Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961), 425–436. MR 133227, DOI 10.2307/1970289
Kirsten Eisenträger, Hilbert’s tenth problem for algebraic function fields of characteristic 2, Pacific J. Math. 210 (2003), no. 2, 261–281. MR 1988534, DOI 10.2140/pjm.2003.210.261
Kirsten Eisenträger, Hilbert’s Tenth Problem for function fields of varieties over algebraically closed fields of positive characteristic, Monatsh. Math. 168 (2012), no. 1, 1–16. MR 2971736, DOI 10.1007/s00605-011-0364-7
Kirsten Eisenträger and Graham Everest, Descent on elliptic curves and Hilbert’s tenth problem, Proc. Amer. Math. Soc. 137 (2009), no. 6, 1951–1959. MR 2480276, DOI 10.1090/S0002-9939-08-09740-2
Kirsten Eisenträger, Graham Everest, and Alexandra Shlapentokh, Hilbert’s tenth problem and Mazur’s conjectures in complementary subrings of number fields, Math. Res. Lett. 18 (2011), no. 6, 1141–1162. MR 2915472, DOI 10.4310/MRL.2011.v18.n6.a7
Kirsten Eisenträger and Alexandra Shlapentokh, Undecidability in function fields of positive characteristic, Int. Math. Res. Not. IMRN 21 (2009), 4051–4086. MR 2549950, DOI 10.1093/imrn/rnp079
Kirsten Eisenträger and Alexandra Shlapentokh, Hilbert’s Tenth Problem over function fields of positive characteristic not containing the algebraic closure of a finite field, to appear in J. European Math. Soc.
Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236
Jochen Koenigsmann, Defining $\Bbb Z$ in $\Bbb Q$, Ann. of Math. (2) 183 (2016), no. 1, 73–93. MR 3432581, DOI 10.4007/annals.2016.183.1.2
Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian). MR 0258744
Barry Mazur, The topology of rational points, Experiment. Math. 1 (1992), no. 1, 35–45. MR 1181085
B. Mazur and K. Rubin, Ranks of twists of elliptic curves and Hilbert’s tenth problem, Invent. Math. 181 (2010), no. 3, 541–575. MR 2660452, DOI 10.1007/s00222-010-0252-0
Russell Miller, Computable fields and Galois theory, Notices Amer. Math. Soc. 55 (2008), no. 7, 798–807. MR 2436510
A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
Jennifer Park, A universal first-order formula defining the ring of integers in a number field, Math. Res. Lett. 20 (2013), no. 5, 961–980. MR 3207365, DOI 10.4310/MRL.2013.v20.n5.a12
Stefan Perlega, Additional results to a theorem of Eisenträger and Everest, Arch. Math. (Basel) 97 (2011), no. 2, 141–149. MR 2820576, DOI 10.1007/s00013-011-0277-7
Thanases Pheidas, Hilbert’s tenth problem for a class of rings of algebraic integers, Proc. Amer. Math. Soc. 104 (1988), no. 2, 611–620. MR 962837, DOI 10.1090/S0002-9939-1988-0962837-4
Thanases Pheidas, An undecidability result for power series rings of positive characteristic, Proc. Amer. Math. Soc. 99 (1987), no. 2, 364–366. MR 870802, DOI 10.1090/S0002-9939-1987-0870802-X
Thanases Pheidas, An undecidability result for power series rings of positive characteristic. II, Proc. Amer. Math. Soc. 100 (1987), no. 3, 526–530. MR 891158, DOI 10.1090/S0002-9939-1987-0891158-2
Thanases Pheidas, Hilbert’s tenth problem for fields of rational functions over finite fields, Invent. Math. 103 (1991), no. 1, 1–8. MR 1079837, DOI 10.1007/BF01239506
Bjorn Poonen, Using elliptic curves of rank one towards the undecidability of Hilbert’s tenth problem over rings of algebraic integers, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 33–42. MR 2041072, DOI 10.1007/3-540-45455-1_{4}
Bjorn Poonen, Hilbert’s tenth problem and Mazur’s conjecture for large subrings of $\Bbb Q$, J. Amer. Math. Soc. 16 (2003), no. 4, 981–990. MR 1992832, DOI 10.1090/S0894-0347-03-00433-8
Bjorn Poonen and Alexandra Shlapentokh, Diophantine definability of infinite discrete nonarchimedean sets and Diophantine models over large subrings of number fields, J. Reine Angew. Math. 588 (2005), 27–47. MR 2196727, DOI 10.1515/crll.2005.2005.588.27
Julia Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98–114. MR 31446, DOI 10.2307/2266510
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Alexandra Shlapentokh, Extension of Hilbert’s tenth problem to some algebraic number fields, Comm. Pure Appl. Math. 42 (1989), no. 7, 939–962. MR 1008797, DOI 10.1002/cpa.3160420703
Alexandra Shlapentokh, Diophantine classes of holomorphy rings of global fields, J. Algebra 169 (1994), no. 1, 139–175. MR 1296586, DOI 10.1006/jabr.1994.1276
Alexandra Shlapentokh, Diophantine definability over some rings of algebraic numbers with infinite number of primes allowed in the denominator, Invent. Math. 129 (1997), no. 3, 489–507. MR 1465332, DOI 10.1007/s002220050170
Alexandra Shlapentokh, Defining integrality at prime sets of high density in number fields, Duke Math. J. 101 (2000), no. 1, 117–134. MR 1733734, DOI 10.1215/S0012-7094-00-10115-9
Alexandra Shlapentokh, Diophantine definability and decidability in large subrings of totally real number fields and their totally complex extensions of degree 2, J. Number Theory 95 (2002), no. 2, 227–252. MR 1924099
Alexandra Shlapentokh, Elliptic curves retaining their rank in finite extensions and Hilbert’s tenth problem for rings of algebraic numbers, Trans. Amer. Math. Soc. 360 (2008), no. 7, 3541–3555. MR 2386235, DOI 10.1090/S0002-9947-08-04302-X
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Carlos R. Videla, Hilbert’s tenth problem for rational function fields in characteristic $2$, Proc. Amer. Math. Soc. 120 (1994), no. 1, 249–253. MR 1159179, DOI 10.1090/S0002-9939-1994-1159179-6