## 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