Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



As easy as $ \mathbb{Q}$: Hilbert's Tenth Problem for subrings of the rationals and number fields

Authors: Kirsten Eisenträger, Russell Miller, Jennifer Park and Alexandra Shlapentokh
Journal: Trans. Amer. Math. Soc. 369 (2017), 8291-8315
MSC (2010): Primary 11U05; Secondary 12L05, 03D45
Published electronically: June 13, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BS96] Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1: Efficient algorithms, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. MR 1406794
  • [CPZ05] 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
  • [CZ00] 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,
  • [Den79] J. Denef, The Diophantine problem for polynomial rings of positive characteristic, Logic Colloquium '78 (Mons, 1978) Stud. Logic Foundations Math., vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 131-145. MR 567668
  • [Den80] J. Denef, Diophantine sets over algebraic integer rings. II, Trans. Amer. Math. Soc. 257 (1980), no. 1, 227-236. MR 549163,
  • [DL78] 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,
  • [DPR61] Martin Davis, Hilary Putnam, and Julia Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961), 425-436. MR 0133227,
  • [Eis03] 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,
  • [Eis12] 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,
  • [EE09] 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,
  • [EES11] 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,
  • [ES09] Kirsten Eisenträger and Alexandra Shlapentokh, Undecidability in function fields of positive characteristic, Int. Math. Res. Not. IMRN 21 (2009), 4051-4086. MR 2549950,
  • [ES16] 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.
  • [Fri57] 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 0084474
  • [Koe16] Jochen Koenigsmann, Defining $ \mathbb{Z}$ in $ \mathbb{Q}$, Ann. of Math. (2) 183 (2016), no. 1, 73-93. MR 3432581,
  • [Lan70] Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
  • [Mat70] Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279-282 (Russian). MR 0258744
  • [Maz92] Barry Mazur, The topology of rational points, Experiment. Math. 1 (1992), no. 1, 35-45. MR 1181085
  • [MR10] 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,
  • [Mil08] Russell Miller, Computable fields and Galois theory, Notices Amer. Math. Soc. 55 (2008), no. 7, 798-807. MR 2436510
  • [Muc56] 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
  • [Par13] 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,
  • [Per11] Stefan Perlega, Additional results to a theorem of Eisenträger and Everest, Arch. Math. (Basel) 97 (2011), no. 2, 141-149. MR 2820576,
  • [Phe88] 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,
  • [Phe87i] Thanases Pheidas, An undecidability result for power series rings of positive characteristic, Proc. Amer. Math. Soc. 99 (1987), no. 2, 364-366. MR 870802,
  • [Phe87ii] 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,
  • [Phe91] Thanases Pheidas, Hilbert's tenth problem for fields of rational functions over finite fields, Invent. Math. 103 (1991), no. 1, 1-8. MR 1079837,
  • [Poo02] 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,
  • [Poo03] Bjorn Poonen, Hilbert's tenth problem and Mazur's conjecture for large subrings of $ \mathbb{Q}$, J. Amer. Math. Soc. 16 (2003), no. 4, 981-990. MR 1992832,
  • [PS05] 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,
  • [Rob49] Julia Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949), 98-114. MR 0031446,
  • [Rog67] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
  • [Shl89] 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,
  • [Shl94] Alexandra Shlapentokh, Diophantine classes of holomorphy rings of global fields, J. Algebra 169 (1994), no. 1, 139-175. MR 1296586,
  • [Shl97] 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,
  • [Shl00] Alexandra Shlapentokh, Defining integrality at prime sets of high density in number fields, Duke Math. J. 101 (2000), no. 1, 117-134. MR 1733734,
  • [Shl02] 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
  • [Shl08] 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,
  • [Soa87] Robert I. Soare, Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. MR 882921
  • [Vid94] 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,

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11U05, 12L05, 03D45

Retrieve articles in all journals with MSC (2010): 11U05, 12L05, 03D45

Additional Information

Kirsten Eisenträger
Affiliation: Department of Mathematics, The Pennsylvania State University, University Park, Pennsylvania 16802

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

Jennifer Park
Affiliation: Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109

Alexandra Shlapentokh
Affiliation: Department of Mathematics, East Carolina University, Greenville, North Carolina 27858

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.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society