# Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition:

$CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$

$IS(x)⇔ x=0 \vee x=1 \vee \exists y: \exists z: (CS(z,y) \wedge IS(y) \wedge (\forall z: (y < z \wedge z < x) ⇒ \neg IS(z)) \wedge x + z = y + y + 2)$

($IS$ stands for IsSquare, $CS$ stands for ConsecutiveSquares.)

Expanding $CS$ in terms of $IS$ gives an axiom in the language:

$IS(x) ⇔x=0 \vee x=1 \vee \exists y: \exists z: (IS(z) \wedge IS(y) \wedge z \lt y \wedge \forall w: (z \lt w) \wedge (w \lt y)⇒\neg IS(w)) \wedge IS(y) \wedge (\forall z: (y < z \wedge z < x) ⇒ \neg IS(z)) \wedge x + z = y + y + 2$

This seems to generalize to a recursive definition, using only addition, of the set of values of any univariate polynomial. Formally I am considering Presburger arithmetic with a unary predicate and associated axioms, yielding an incomplete system in this case.

There are other unary predicates which result in a complete theory. But my question is:

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$? If so, does it yield an incomplete system? Otherwise, how to prove that such a definition does not exist?

I recently asked "Is there no univariate integer polynomial that takes on the same positive values as the multivariate polynomial $x^2+y^2$? and accepted an answer but I don't understand how to apply it to this situation.

-
Do you mean $\{z\mid\exists x\exists y:x\cdot x+y\cdot y=z\}$, but first you want to define multiplication recursively? –  Asaf Karagila Feb 22 '12 at 8:35
@Asaf, no, I want some definition of IsSumOfTwoSquares in terms of itself (and addition), and if that is somehow possible I would like to know whether it can define multiplication (which implies the system is incomplete (or else inconsistent of course)). –  Dan Brumleve Feb 22 '12 at 8:40
@Dan Brumleve: Your recursive definition of $IS$ uses an auxiliary predicate, so presumably that is allowed. However, how does one rule out the auxiliary predicate $P(x,y,z)$ that says that $z=xy$? –  André Nicolas Feb 22 '12 at 8:47
@Dan Brumleve: The predicate $P$ can be defined recursively in terms of addition, in the usual way. –  André Nicolas Feb 22 '12 at 8:52
@André, in the case of the set of squares, we can define multiplication, in accordance with your answer to my old question that I linked to. The case I am wondering about here is the set of sums of two squares. –  Dan Brumleve Feb 22 '12 at 8:56

The function $$f(z) = \begin{cases} 1 & (\exists x)(\exists y)[z = x^2 + y^2]\\ 0 & \text{otherwise} \end{cases}$$ is primitive recursive. Therefore there is a recursive definition for this function which uses only the constant $0$ and the successor function $S(z) =z+1$ as starting points.