# Diophantine relations using an equation with polynomials of degree at most 4

I'm completely stuck at exercise 5.8.5 of Mathematical Logic, Chiswell & Hodges:

Here are the mentioned definition and theorem:

I'm stuck because I failed to use the hint given in the exercise. I can't figure out how to use such a property of functions on a relation (a function is a relation but the opposite isn't true). Also, I couldn't even figure out how this can be true for the following diophantine relation: "$x_1+x_2$ is a power of $5$". The equation $\phi(x_1,x_2,y)$ for such a relation is $x_1+x_2=y^5$.

You probably mean "$x_1+x_2$ is a fifth power", that is, $\exists y(x_1+x_2=y^5)$.

We want to say this: There exist $y, s, t, u, v$ such that $s=y^2$ and $t=sy$ and $u=ty$ and $v=uy$ such that $x_1+x_2=v$. This is equivalent to $$\exists y\exists s\exists t\exists u\exists v((s-y^2)^2+(t-sy)^2+(u-ty)^2+(v-uy)^2+(x_1+x_2-v)^2=0).\tag{1}$$ Note that the polynomial in (1) has degree $4$. Call it $P$. We are not quite finished, since $P$ contains minus signs. But we can rewrite $P=0$ as $Q=R$, where $Q$ and $R$ have positive coefficients (just bring the minus stuff in $P$ to the right-hand side).

The idea will work in general. We replace $z=y^{n+1}$, where $n$ is a fixed positive integer, by $$\exists t_1\cdots\exists t_{n}((t_1=y^2)\land (t_2=yt_1)\land \cdots \land (t_{n}=yt_{n-1})\land (z=t_n)).$$ Then (over the naturals, or the integers, or $\dots$) we use the sum of squares trick, $(a=b)\land (c=d)$ if and only if $(a-b)^2+(c-d)^2=0$.

Remark: This trick for avoiding high degree polynomials, but at the cost of introducing additional variables, occurs first, I believe, in the work of Skolem.

• Thank you very much for your answer! I understand the trick thanks to you. I'm going to try using it and induction to solve the exercise. Your Remark is what you taught me through the exercise: introducing additional variables. – Scientifica Jun 19 '16 at 22:57
• @Scientifica: You are welcome. Once upon a long time ago, I thought I had invented the trick. – André Nicolas Jun 19 '16 at 23:06
• :o that's impressive! – Scientifica Jun 20 '16 at 23:39
• Using the result you are proving, one can show that there is no algorithm for determining whether $F(x_1,\cdots,x_n)$ has a solution in integers, where $F$ is a quartic. By pushing a little more, one can show that there is no algorithm for determining whether $Q(x_1,\cdots,x_n)=1$ has a solution in integers, where $Q$ is a homogeneous quartic. – André Nicolas Jun 20 '16 at 23:51
• :o thank you for this comment. You gave an example of the importance of this result and that's nice. If I understand correctly, by showing that this result holds for quartics and using the exercise, we can conclude that there's no algorithm where $F$ is any polynomial (seems related to Hilbert's 10th problem), and I guess working on a particular case (quartic function) can make the proof easier. Since the problem reduces to quartics, I was quite tempted to think about it hhh. – Scientifica Jun 24 '16 at 1:20