Defining Integers in Rationals

Our natural way to think of rationals is that they are ratios (pairs up to equivalence) of integers. So rationals are built out of integers. But what if we are given rationals abstractly, and we want to decide if a given rational is an integer? That is how do we define integers if we are given rationals, and we are allowed some structures on the rationals. That is say we have rational field $\mathbb Q, +, \cdot , 0, 1$ , is there an “expression” $\phi(x)$ which is true only if $x$ is in $\mathbb Z$ ? The expressions has to be a logical expression in terms of the field structure, that is we want a first order formula (with existential and universal quantifiers) which defines integers inside rationals. (Informally, we want to define integers using polynomials equations over rationals). The simplest definition we can think of is as iterated sums of $1$ and their negative– but this, as it exists, is not a single formula.

Why do we want to do this? It’s just an interesting question for it’s own sake, but problems like this can help us solve Hilbert’s 10 th problem over rationals (That is, can we decide if a set of polynomial equations over rationals is solvable by an algorithm). The problem over integers is solved (Davis, Putnam, Robinson, Matijasevic), and we know it’s undecidable. So if we have a existential definition of integers over rationals (Diophantine definition), then we can can be prove that problem is undecidable over rationals by reduction to integers: If it is decidable, then an arbitrary system over integers can be rephrased as a system over rationals (write down more equations to declare that the variables have to be integers), and we have to decide over $\mathbb Z.$

For instance rationals and integers cannot be defined in the theory of real numbers $(\mathbb R, +, \cdot , 0, 1, <).$ This is because theory of ordered field of real numbers is decidable (by quantifier elimination) and hence first order definitions of integers over reals will mean that the theory over integers is decidable which is not true (DPRM theorem) !

Hilbert’s problem concerns positive existential theory — that is we want to decide certain statements which are about existence of a solution. Statements like

$\left(\exists x_{1} \exists x_{2} \cdots \exists x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right)=0$

We know Hilbert’s 10 is undecidable over integers and we still cannot prove that it is undecidable over rationals (if we had a diophantine definition of integers like we mentioned above, we would have a proof, but we don’t know how to produce such a definition or how to show that it doesn’t exist! It’s expected that a diophantine definition doesn’t exist — some conjectures like Bombieri-Lang in arithmetic geometry imply non-existence. For instance, there are more general conjectures like Mazur’s conjecture about the topology of sets which are diophantine: The topological closure of a variety $V(\mathbb Q)$ inside $V(\mathbb R)$ has finitely many components. If this is true, it’s clear that $\mathbb Z &fg=000000$ cannot be diophantine – it’s real topology has infinite isolated points

But if we take the full first order theory, it’s known to be undecidable over integers and also rationals.
Undecidability over integers: The main idea here is to show that every recursively enumerable set is definable (Godel), and then by halting problem there are recursively enumerable sets which cannot be decided. Indeed even DPRM theorem/ Hilbert 10 over integers is established by showing that every recursively enumerable set is diophantine (definable with one existential quantifier).

To show undecidability of the full theory over rationals, like mentioned above, it’s enough to show a first order definition (not necessarily diophantine/existential) of integers inside rationals). If we get “simpler” definitions (like say existential), we can prove undecidability of smaller/subparts of the theory.

What do we currently know about the complexity of defining $\mathbb Z$ in $\mathbb Q$ ? (Remember the best would be to find a diophantine/ definition with one existential quantifier/ one level of existential quantifiers – which as we indicated (Mazur’s conjecture) is unlikely to exist. )

The iterative definition of natural numbers is not a single statements, but infinite statements one for each number. But what if we define it’ as the subset containing 1 and satisfies the induction.– If we think carefully, this is a second order statement and quantifies over all subsets to uniquely define naturals among them.
Coming up with first order definitions is hard even for the simplest sets we can think of!

Robinson’s definition: ( $\Pi_4^{+}$ )

Robinson showed that the full first order theory over rationals is undecidable by exhibiting a first order definition of integers inside rationals. It is a $\Pi_4^{+}$ formula -4 level hierarchy of quantifiers which looks like

$\left( \forall X \exists Y \forall Z \exists T \right) P\left(X_{i}, Y_i, Z_k, T_l\right)=0$

We don’t try to reduce/present the formula in it’s simplest form like above. We try to write the induction axiom in terms of first order statements.

Let

S(P, Q, N) : \exists A \exists B \exists C\left(2+Q P N^{2}=A^{2}+Q B^{2}-P C^{2}\right)

\forall Q \forall P\left(\left[S(Q, P, 0) \wedge \forall T{S(Q, P, T) \Rightarrow S(Q, P, T+1)}\right] \Rightarrow S(Q, P, X) \right)

The idea is that $S(P, Q, N)$ for any fixed $(P, Q)$ primes allows to detect rationals $N$ whose denominators are coprime to $(P, Q)$ . Thus quantifying over all $(P, Q)$ allows us to detect integers (denominators have no prime factors).

In fact we have:

$S(1, p, N)$ for a prime $p = 1 \mod 4$ iff the denominators of $N$ is odd and is not divisible by $p$
$S(q, p, N)$ for $p=3 \mod 4$ iff the denominator of $N$ is not divisible by $p$ and $q$

These statements can be proved by local-global (Hasse-Minkowski) ideas for ternary quadratic forms.

Bjorn Poonen’s definition: ( $\Pi_2^{+}$ 2 universal and 7 existential quantifiers.)

$(\forall a, b)\left(\exists a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}, b_{3}, b_{4}, x_{1}, x_{2}, x_{3}, x_{4}, y_{1}, y_{2}, y_{3}, y_{4}, n\right)$

$0=\left(a+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}+a_{4}^{2}\right)\left(b+b_{1}^{2}+b_{2}^{2}+b_{3}^{2}+b_{4}^{2}\right)$ $\displaystyle [\left(x_{1}^{2}-a x_{2}^{2}-b x_{3}^{2}+a b x_{4}^{2}-1\right)^{2}+\prod_{n=0}^{2309}\left(\left(n-t-2 x_{1}\right)^{2}-4 a y_{2}^{2}-4 b y_{3}^{2}+4 a b y_{4}^{2}-4\right)^{2}]$

The formula is obtained by characterising integers as the subset of intersection of special sets related to quaternion algebras. Each special set is a sumset of traces of norm $1$ elements of the quaternion algebra. And integers are precisely the elements that belong to these sets for all quaternion algebras $H_{a,b}$ over rationals.

Jochen Koenigsmann’s definition: ( $\Pi_2^{+}$ with $2$ universal and $7$ existential quantifiers.)

He first get the follows improved to Pooenen’s expression (same number of quantifiers but lesser degree polynomial)

$t \in \mathbb{Z} \Longleftrightarrow \forall a, b ~~\exists ~x_{1}, x_{2}, x_{3}, x_{4}, y_{2}, y_{3}, y_{4} \quad$

$(a+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\cdot(b+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\cdot$
$[(x_{1}^{2}-a x_{2}^{2}-b x_{3}^{2}+a b x_{4}^{2}-1)^{2}+((t-2 x_{1})^{2}-4 a y_{2}^{2}-4 b y_{3}^{2}+4 a b y_{4}^{2}-4)^{2}]=0$

Then he find diophantine descriptions for the rationals with denominators coprime to a prime $\mathbb Z_{(p)},$ uniformly over $p$ . Next a description for Jacobson radical, to define integers in terms of the local rings $\displaystyle \cap_{l \in S}Z_{(l)}$ .

References:

1. Julia Robinson,Definability and decision problems in arithmetic, J.Symbolic Logic 14(2)(1949), 98-114
2. Bjorn Poonen, Characterizing integers among rational numbers with a universal-existential formula, Amer. J. Math.131(3)(2009), 675-682.
3. Jochen Koenigsmann, Defining $\mathbb Z$ in $\mathbb Q$ https://arxiv.org/pdf/1011.3424.pdf
4. How to Pick Out the Integers in the Rationals: An Application of Number Theory to Logic

Share this:

Related

Leave a comment Cancel reply