Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem It is well-known that the set of nonnegative integers $\mathbb{N}$ is definable in the ring of integers $\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have $\mathbb{N} = \{n \in \mathbb{Z} : \varphi(n)\}$, where $\varphi$ is the formula
$$\varphi(x) := \exists a\, \exists b\, \exists c\, \exists d \; x = a^2 + b^2 + c^2 + d^2$$
However, Lagrange's theorem is not so trivial, so I wonder:
Is there a more elementary and self-contained proof of the definability of $\mathbb{N}$ in the ring of integers?
Thank you.
 A: Raphael Robinson, in a paper entitled Arithmetical Definitions in the Ring of Integers, gives a definition of $\mathbb{N}$ in $\mathbb{Z}$ using only two existential quantifiers. He does not use Lagrange's Theorem, but he does use the fact that the equation $y^2-az^2=1$ has infinitely many solutions $y$ and $z$ whenever $a$ is a positive nonsquare integer. Whether this is "easier" than Lagrange's Theorem is debatable.
Robinson proves that $x\in \mathbb{N}$ if and only if
$$\exists y\exists z \left(x=y^2\vee (y^2=1+xz^2\wedge y^3\ne y)\right).$$
He also proves that no definition using just one existential quantifier is possible.
A: Here is an outline of a possible approach. We will show in a simple way that every natural number is a ratio of two sums of four squares, so that formula $\exists a_1,\dots,a_8:(a_1^2+a_2^2+a_3^2+a_4^2)n=a_5^2+a_6^2+a_7^2+a_8^2$ (edit: and not all $a_1,\dots,a_4$ are zero) describes $\mathbb N$. Let's call rational numbers $n$ satisfying this property good.
Lemma 1: A product of two good numbers is good. A reciprocal of a nonzero good number is good.
Proof: First part follows from the four-square identity, second is immediate.
Lemma 2: For any prime $p$ there is an integer $0<k<p$ such that $kp$ is good.
Proof: It's true for $2$, so suppose $p$ is odd. Then it's straightforward to verify there are precisely $\frac{p+1}{2}$ squares modulo $p$. Thus the sets $A=\{x^2\},B=\{-1-y^2\}$ for $x,y$ in $\mathbb Z/p\mathbb Z$ both have size $\frac{p+1}{2}$. So $|A|+|B|>p=|\mathbb Z/p\mathbb Z|$, so they have nontrivial intersection, say $x^2\equiv -1-y^2\pmod p$. Now replace $x,y$ with integers congruent to them such that $|x|,|y|<\frac{p}{2}$. Then $p\mid x^2+y^2+1<\frac{p^2}{4}+\frac{p^2}{4}+1<p^2$, so $x^2+y^2+1=kp$ for $0<k<p$ and we are clearly done.
Now we can easily finish: we proceed by induction. $0$ and $1$ are good. Consider $n>1$. If $n$ is composite, then $n=ab$ with $a,b<n$, so $a,b$ are good hence so is $n$ by lemma 1. If $n$ is prime, then by lemma 2 $kn$ is good for $0<k<n$. But then $k$ is good, hence so are $\frac{1}{k}$ and $n=\frac{1}{k}\cdot kn$ by lemma 1.
Of course for a large part this proof is the same as the proof of Lagrange's theorem, but at the very least we are avoiding a (crucial in the mentioned theorem) step of showing a prime is a sum of four squares.
