2004/12/23 by Gunther Cornelissen, Cornelissen, Gunther, Karim Zahidi +1
Mathematics · #03B25 #11U05 #FOS: Mathematics #Logic (math.LO) #Number Theory (math.NT) #math.LO #math.NT #msc:03B25 #msc:11U05
paper · pdf · doi:10.48550/arxiv.math/0412473
39 pages, uses calrsfs. 3rd version: many small changes, change of title
arxiv created 2006/06/23 · arxiv updated 2009/12/01
Julia Robinson has given a first-order definition of the rational integers Z in the rational numbers Q by a formula (∀ ∃ ∀ ∃)(F=0) where the ∀-quantifiers run over a total of 8 variables, and where F is a polynomial. This implies that the Σ5-theory of Q is undecidable. We prove that a conjecture about elliptic curves provides an interpretation of Z in Q with quantifier complexity ∀ ∃, involving only one universally quantified variable. This improves the complexity of defining Z in Q in two ways, and implies that the Σ3-theory, and even the Π2-theory, of Q is undecidable (recall that Hilbert's Tenth Problem for Q is the question whether the Σ1-theory of Q is undecidable). In short, granting the conjecture, there is a one-parameter family of hypersurfaces over 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.