31
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Is this just asked out of curiosity, or do you have a problem with this use of the four-square theorem? I always regarded this approach as illustrating that the result (definability of $\mathbf N$ within $\mathbf Z$) has real substance to it. $\endgroup$
    – KConrad
    Commented Sep 10, 2016 at 9:46
  • $\begingroup$ Why don't you want to define $\mathbb N$ as a minimal subset $X$ in $\mathbb Z$ with the property $x\in X\ \Rightarrow\ x+1\in X$? $\endgroup$
    – Sergei Akbarov
    Commented Sep 10, 2016 at 9:50
  • 11
    $\begingroup$ @SergeiAkbarov This is not a first-order definition. $\endgroup$
    – Wojowu
    Commented Sep 10, 2016 at 9:50
  • $\begingroup$ Ah, excuse me, I did not understand the question! $\endgroup$
    – Sergei Akbarov
    Commented Sep 10, 2016 at 9:52
  • $\begingroup$ @SergeiAkbarov, probably I misunderstand, but minimal in what sense? If in the sense of set containment, then replacing $\mathbb N$ by its subset of successors seems to contradict its minimality. $\endgroup$
    – LSpice
    Commented Sep 10, 2016 at 13:24

2 Answers 2

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Very nice idea. $\endgroup$
    – user40023
    Commented Sep 10, 2016 at 13:14
  • $\begingroup$ Your definition of "good" is overly complicated. It is the same thing as being a sum of four rational squares. I think the definition of "good" should be described that way and the proof you wrote continues to work with no major changes. This puts into better perspective how this approach differs from the one using Lagrange: it's enough to use sums of four rational squares rather than four integer squares (nontrivial work shows those are the same property, but you don't need such an equivalence for this proof). $\endgroup$
    – KConrad
    Commented Sep 10, 2016 at 18:40
  • $\begingroup$ @KConrad It took me a little bit of thought, but I can agree with you. My definition of "good" makes it much clearer though why a reciprocal of good number is good. But I agree that argument with sums of four rational squares would be also be neat. Can you see a direct way (without Lagrange) to show that a good number (with my definition) is a sum of four rational squares? $\endgroup$
    – Wojowu
    Commented Sep 10, 2016 at 19:02
  • $\begingroup$ You proved it yourself: start with the ideas for Lagrange and change the end of the argument a little bit. I disagree that your definition makes it "much clearer" that a reciprocal of a good number is good. For any nonzero sum of $k$ squares, $a = \sum_{i=1}^n a_i^2$, we have $1/a = a/a^2 = \sum_{i=1}^k (a_i/a)^2$ is a sum of $k$ squares. I stand by my belief that writing the denominator as a sum of four squares instead of as a single square makes the condition look overly complicated. $\endgroup$
    – KConrad
    Commented Sep 10, 2016 at 21:19
  • $\begingroup$ @KConrad I see, and I agree. Having four squares in both numerator and denominator was just the first idea I had, but as you mention it does look overcomplicated if you realize you can deal with a single square in a denominator. $\endgroup$
    – Wojowu
    Commented Sep 10, 2016 at 21:23
35
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ Term "Pell's equation" is relevant here. $\endgroup$
    – Wojowu
    Commented Sep 10, 2016 at 13:20

You must log in to answer this question.