Raphael Robinson, in a paper entitled _[Arithmetical Definitions in the Ring of Integers](https://doi.org/10.1090/S0002-9939-1951-0041080-4 )_, 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.