It is well-known that the set of nonnegative integers $\mathbb{N}$ is [definable](https://en.wikipedia.org/wiki/Definable_set) in the ring of integers $\mathbb{Z}$. Indeed, by [Lagrange's four squares theorem](https://en.wikipedia.org/wiki/Lagrange%27s_four-square_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.



Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem
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](https://en.wikipedia.org/wiki/Euler%27s_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.


