×

Elliptic divisibility sequences and undecidable problems about rational points. (English) Zbl 1178.11076

Summary: Julia Robinson has given a first-order definition of the rational integers \(\mathbb Z\) in the rational numbers \(\mathbb Q\) by a formula (\(\forall\exists\forall\exists\)) (\(F = 0\)) where the \(\forall\)-quantifiers run over a total of 8 variables, and where \(F\) is a polynomial. This implies that the \(\Sigma_5\)-theory of \(\mathbb Q\) is undecidable. We prove that a conjecture about elliptic curves provides an interpretation of \(\mathbb Z\) in \(\mathbb Q\) with quantifier complexity \(\forall\exists\), involving only one universally quantified variable. This improves the complexity of defining \(\mathbb Z\) in \(\mathbb Q\) in two ways, and implies that the \(\Sigma _{3}\)-theory, and even the \(\Pi _{2}\)-theory, of \(\mathbb Q\) is undecidable (recall that Hilbert’s Tenth Problem for \(\mathbb Q\) is the question whether the \(\Sigma_{1}\)-theory of \(\mathbb Q\) is undecidable). In short, granting the conjecture, there is a one-parameter family of hypersurfaces over \(\mathbb Q\) for which one cannot decide whether or not they all have a rational point. The conjecture is related to properties of elliptic divisibility sequences on an elliptic curve and its image under rational 2-descent, namely existence of primitive divisors in suitable residue classes, and we discuss how to prove weaker-in-density versions of the conjecture and present some heuristics.

MSC:

11U09 Model theory (number-theoretic aspects)
03B25 Decidability of theories and sets of sentences
03D35 Undecidability and degrees of sets of sentences
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Daniel Shanks, and Samuel Jr more solutions of Martin Davis s quaternary quartic equa - tion Math, Comp pp 1717– (1995)
[2] Victor Flynn, Franck Lepre vost Edward William and Joseph We - therell Empirical evidence for the Birch and Swinnerton - Dyer conjectures for modular Jacobians of genus curves Math, Comp 2 pp 236– (2001)
[3] Beltjukov, Decidability of the universal theory of natural numbers with addition and divisibility Studies in constructive mathematics and mathematical logic VII Zap Naucn Sem Leningrad Otdel Mat, Inst Steklov pp 15– (1976)
[4] Martin Davis, Hilbert s tenth problem is unsolvable Monthly, Math 80 pp 233– (1973) · Zbl 0277.02008
[5] Leonard Lipshitz, The Diophantine problem for addition and divisibility, Trans Amer Math Soc pp 235– (1978) · Zbl 0374.02025
[6] Jeroen Demeyer, and Jan An existential divisibility lemma for global fields no, Math pp 147– (2006) · Zbl 1195.11163
[7] Yuri, The Diophantineness of enumerable sets, Akad Nauk pp 191– (1970)
[8] Leonard Lipshitz, Some remarks on the Diophantine problem for addition and divisibility Proceedings of the Model Theory Meeting ( Brussels, Soc Math Belg 33 pp 41– (1980)
[9] Hahn, Cheon and Explicit valuations of division polynomials of an elliptic curve, Math pp 319– (1998) · Zbl 0922.11048
[10] Graham Everest, and Primes generated by elliptic curves, Proc Amer Math Soc pp 132– (2004)
[11] David Goss, Basic structures of function field arithmetic Springer - Verlag, Math Grenzgeb (1996) · Zbl 0874.11004
[12] Gunther Cornelissen, Stockage diophantien et hypothe se abc ge ne ralise e, Acad Sci Paris pp 328– (1999)
[13] Jean, - Divisibilite de certaines fonctions arithme tiques, Math 22 pp 227– (1976)
[14] Leonard Lipshitz, Undecidable existential problems for addition and divisibility in algebraic number rings, Trans Amer Math Soc pp 241– (1978) · Zbl 0385.03012
[15] Gunther Cornelissen, and Topology of Diophantine sets : remarks on Mazur s conjectures in : Hilbert s tenth problem : relations with arithmetic and algebraic geometry, Math pp 270– (1999)
[16] Leonard Lipshitz, Undecidable existential problems for addition and divisibility in algebraic number rings II, Proc Amer Math Soc pp 122– (1977) · Zbl 0365.02019 · doi:10.1090/S0002-9939-1977-0536659-5
[17] Chudnovsky, Chudnovsky and Sequences of numbers generated by addition in formal groups and new primality and factorization tests Adv, Appl Math 7 pp 385– (1986) · Zbl 0614.10004
[18] Alexandra Shlapentokh, Hilbert s tenth problem : Diophantine classes and extensions to global fields New Math Cambridge University Press Cambridge, Monogr (2007) · Zbl 1196.11166
[19] Daniel Shanks, The second - order term in the asymptotic expansion of Bx Math, Comp pp 75– (1964)
[20] Manfred Einsiedler, Graham Everest and Primes in elliptic divisibility sequences LMS, Comput Math pp 1– (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.