CHARACTERIZING INTEGERS AMONG RATIONAL NUMBERS WITH A UNIVERSAL ...

CHARACTERIZING INTEGERS AMONG RATIONAL NUMBERS WITH A UNIVERSAL-EXISTENTIAL FORMULA BJORN POONEN Abstract. We prove that Z in definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points. We also give a formula, again with universal quantifiers followed by existential quantifiers, that in any number field defines the ring of integers.

• quaternion algebra hf
• decision problem for exponential diophan- tine equations
• existential formulas over z
• intersec- tion of tf
• ring of integers
• rational functions
• characteristic polynomial
• decision problems
• algorithm