0
$\begingroup$

We have the equations

$$a_1x+b_1y+c_1z=d_1,$$ $$a_2x^2+b_2y^2+c_2z^2=d_2,$$ $$a_3x^3+b_3y^3+c_3z^3=d_3,$$

where $a_i,b_i,c_i \in\Bbb N$ at $i \in \{1,2,3\}$ are known.

Is there an efficient ($O(\log(d_1d_2d_3))$ time) procedure to find $x,y,z\in\Bbb N$ as solutions sought?

I can reduce the system of equations to $$c_1^2a_2x^2+c_1^2b_2y^2+ c_2(d_1-a_1x-b_1y)^2=c_1^2d_2,$$ $$c_1^3a_2x^2+c_1^3b_2y^2+ c_3(d_1-a_1x-b_1y)^3=c_1^3d_3.$$

Improve this question
$\endgroup$
2
  • $\begingroup$ could you please post? $\endgroup$
    – Turbo
    Commented Nov 4, 2015 at 10:07
  • $\begingroup$ I misread the question. $\endgroup$
    – Geoff Robinson
    Commented Nov 4, 2015 at 10:16

2 Answers 2

Reset to default
1
$\begingroup$

This system can be routinely reduced to a single univariate polynomial using resultants -- see https://en.wikipedia.org/wiki/Resultant

Improve this answer
$\endgroup$
5
  • $\begingroup$ It might be mentioned that "generically" this polynomial will have degree $6$, resulting in $6$ solutions (usually not in integers, of course). In special cases you may have more solutions or less. $\endgroup$
    – Robert Israel
    Commented Nov 4, 2015 at 18:29
  • $\begingroup$ @RobertIsrael. Could you explain how to solve over integers? $\endgroup$
    – Turbo
    Commented Nov 4, 2015 at 20:51
  • $\begingroup$ @MaxAlekseyev Could you explain the resultants technique? $\endgroup$
    – Turbo
    Commented Nov 4, 2015 at 20:52
  • $\begingroup$ @Turbo: Briefly speaking, the system $\{ p_1(x,y,z)=0, p_2(x,y,z)=0, p_3(x,y,z)=0 \}$ reduces to $\{ R_z(p_1,p_2)=0, R_z(p_1,p_3)=0 \}$ and then to a single equation $R_y(R_z(p_1,p_2),R_z(p_1,p_3))=0$ (of a single variable $x$), where $R_z$ and $R_y$ are resultants computed with respect to variables $z$ and $y$, respectively. $\endgroup$
    – Max Alekseyev
    Commented Nov 4, 2015 at 21:40
  • $\begingroup$ Once you have the polynomial (which will have integer coefficients), you want to check whether it has integer roots. Let's suppose the constant coefficient is so large you can't just check its factors. You might use Sturm's theorem to count the number of real roots; you can also bound the roots by easy inequalities. Then by repeatedly bisecting intervals and using Sturm's theorem, you can isolate roots in small enough intervals to check the integers in them directly. $\endgroup$
    – Robert Israel
    Commented Nov 5, 2015 at 1:14
0
$\begingroup$

Maple found closed for and the complexity is finding the rational roots of degree 6 univariate polynomial and then substitute in messy expressions.

The closed form is 300KB in text in expanded form and is available here: https://gist.githubusercontent.com/jor0/a9afaaf0b09c66d27edb/raw/9bf17e45e804d88dd796e6ad09b36fe7275cde79/turbo1.txt

It involves computing expressions depending on $a_i,b_i$, so in case they are large and $d_i$ are very small the complexity will depend on $a_i,b_i$ too.

Improve this answer
$\endgroup$
5
  • $\begingroup$ could you post maple code as well? $\endgroup$
    – Turbo
    Commented Nov 4, 2015 at 16:23
  • $\begingroup$ @Turbo here it is: q1:=[a1*x+b1*y+c1*z-d1,a2*x^2+b2*y^2+c2*z^2-d2,a3*x^3+b3*y^3+c3*z^3-d3];so:=solve(q1,[x,y,z]); $\endgroup$
    – joro
    Commented Nov 4, 2015 at 17:17
  • $\begingroup$ That huge general expression is not particularly useful. Given particular coefficients, it's better to compute the Groebner basis or resultants using those coefficients. $\endgroup$
    – Robert Israel
    Commented Nov 4, 2015 at 18:09
  • $\begingroup$ @joro Is this over $\Bbb Z$? $\endgroup$
    – Turbo
    Commented Nov 4, 2015 at 21:42
  • $\begingroup$ @Turbo No, it is over the rationals. In general the number of solutions is finite (possibly only unless the third equation is identically zero). From the finite solutions find the natural ones. $\endgroup$
    – joro
    Commented Nov 5, 2015 at 6:13

Not the answer you're looking for? Browse other questions tagged .