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
Additional Information
- Kirsten Eisenträger
- Affiliation: Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802
- MR Author ID: 717302
- Email: eisentra@math.psu.edu
- Russell Miller
- Affiliation: Department of Mathematics, Queens College, 65-30 Kissena Boulevard, Queens, New York 11367 – and – Ph.D. Programs in Mathematics and Computer Science, CUNY Graduate Center, 365 Fifth Avenue, New York, New York 10016
- MR Author ID: 679194
- Email: Russell.Miller@qc.cuny.edu
- Jennifer Park
- Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
- Email: jmypark@umich.edu
- Alexandra Shlapentokh
- Affiliation: Department of Mathematics, East Carolina University, Greenville, North Carolina 27858
- MR Author ID: 288363
- ORCID: 0000-0003-1990-909X
- Email: shlapentokha@ecu.edu
- Received by editor(s): February 9, 2016
- Received by editor(s) in revised form: August 28, 2016, and September 22, 2016
- Published electronically: June 13, 2017
- Additional Notes: The first author was partially supported by NSF grant DMS-1056703.
The second author was partially supported by NSF grants DMS-1001306 and DMS-1362206 and by several PSC-CUNY Research Awards.
The third author was partially supported by NSF grant DMS-1069236 and by an NSERC PDF grant.
The fourth author was partially supported by NSF grant DMS-1161456. - © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 8291-8315
- MSC (2010): Primary 11U05; Secondary 12L05, 03D45
- DOI: https://doi.org/10.1090/tran/7075
- MathSciNet review: 3695862