# Diophantine system of equations

I'm trying to know if there is an efficient way to find the smallest (i.e lexicographically) triplet $(a,b,c)$ of integers verifying $$a^2+b^2+c^2 = x$$ $$a^3+b^3+c^3=y$$ $$a^4+b^4 + c^4 = z$$ if $(x,y,z)$ is known.

We assume that a solution exists for that triplet $(x,y,z)$.

Originally, this question is part of an algorithmic problem. So what I want is a fast way to find the triplet without having to brute-force.

What I've tried (the brute-force approach): going through all the possible values of $a$ since we can deduce an upper bound for its value, we remain with three equations where it's easy to find $b$ and $c$ and see if they are integers.

EDIT: We may assume as well that $a<b<c$.

If $a,b,c$ are integers such that

$$a^2 + b^2 + c^2 = x$$ $$a^3 + b^3 + c^3 = y$$ $$a^4 + b^4 + c^4 = z$$

then the following divisibility conditions must hold:

$$\left( a + b + c \right) \mid \left( x^2 - 2z \right)$$

$$\left( 4\left(ab + bc + ca\right) \right) \mid \left( x^4 + 6x^2z - 16xy^2 + 9z^2 \right)$$

$$\left( 2abc \right)^2 \mid \left( x^6 - 4x^3y^2 - 3x^2z^2 + 12xy^2z - 4y^4 - 2z^3 \right)$$

Of these, the last will cut down your search considerably.

• Can you please provide a quick hint how did you get these divisibility conditions ? – Blencer Dec 31 '16 at 2:24
• @Guru: I used Maple's Groebner basis package to "solve" for the elementary symmetric functions of $a,b,c$ in terms of $x,y,z$ – quasi Dec 31 '16 at 2:27
• Besides, these conditions do not solve the problem since with the condition $a<b<c$ we get $4a^6 < RHS$ but RHS can be very big, the range of searching for a is still large. Algorithmically, I start searching a beginning from 0, and whenever I get a solution for $a$ I stop the loop. Therefore, reducing the upper bound does not make any change. Finding a lower bound or a lower bound for $a$ would be more helpful. – Blencer Dec 31 '16 at 2:30
• For given integers $x,y,z$, Just factor the RHS (integer factors). – quasi Dec 31 '16 at 2:34
• Doesn't look like a simple task .. – Blencer Dec 31 '16 at 2:37

If you have software to find real roots, the following result provides another way to find qualifying triples $a,b,c$ ...

Proposition: If $a,b,c$ satisfy $a^2 + b^2 + c^2 = x$, $a^3 + b^3 + c^3 = y$, $a^4 + b^4 + c^4 = z$, then $a,b,c$ are roots of the following 12'th degree polynomial:

$$p(t) = \left(12\right)\left(t^{12}\right) -\left(24x\right)\left(t^{10}\right) -\left(16y\right)\left(t^9\right) +\left(24x^2-12z\right)\left(t^8\right) +\left(48xy\right)\left(t^7\right)$$ $$-\left(24x^3+8y^2\right)\left(t^6\right) -\left(24x^2y-24yz\right)\left(t^5\right)$$ $$+\left(15x^4+6x^2z-24xy^2+3z^2\right)\left(t^4\right) +\left(8x^3y-24xyz+16y^3\right)\left(t^3\right)$$ $$-\left(6x^5-12x^2y^2-6xz^2+12y^2z\right)\left(t^2\right) +\left(x^6-4x^3y^2-3x^2z^2+12xy^2z-4y^4-2z^3\right)$$

• I'm meant to solve just an algorithmic problem ... I mean just submitting some lines of code, so no, I don't think I'll be able to find the roots – Blencer Dec 31 '16 at 3:17
• wouldn't it be simpler to first get the degree $4$ polynomial of which $a+b+c$ is a root ? – mercio Jan 1 '17 at 0:20
• Yes, I did that as well -- didn't post it. Apparently it's a live programming contest problem. I wasn't aware of that when I posted my repsonses. – quasi Jan 1 '17 at 0:23