3
$\begingroup$

Why is Reduce or Solve unable to provide explicit solutions over integers for such simple system of equations?

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, x4}, Integers]

enter image description here

Since x3=1/x1 in all four alternatives it is evident that x1=1 or x1=-1 and so we have four solutions:

(x1==1&&x2==2&&x3==1&&x4==3)||(x1==1&&x2==3&&x3==1&&x4==2)||(x1==-1&&x2==-3&&x3==-1&&x4==-2)||(x1==-1&&x2==-2&&x3==-1&&x4==-3)

On the other hand Reduce provides explicit solutions for this similar (but more complicated) system of equations:

Reduce[{5 x1^2+4 x1 x3+3 x3^2==4,5 x1 x2+2 x2 x3+2 x1 x4+3 x3 x4==1,5 x2^2+4 x2 x4+3 x4^2==3},{x1,x2,x3,x4},Integers]

(x1==-1&&x2==0&&x3==1&&x4==1)||(x1==1&&x2==0&&x3==-1&&x4==-1)
$\endgroup$
2
  • 1
    $\begingroup$ This is a nonlinear Diophantine system. It's known there is no algorithm to determinate its solvability (see Wiki for info). MMA does its best. $\endgroup$
    – user64494
    Dec 11, 2023 at 12:29
  • $\begingroup$ Just to compare. The command of Maple 2023 isolve({x1*x3 = 1, 2*x2*x4 = 12, x1*x4 + x2*x3 = 5}) fails. $\endgroup$
    – user64494
    Dec 11, 2023 at 15:47

3 Answers 3

4
$\begingroup$

What is even more strange that using Reduce twice (or Reduce with Solve) provides the explicit solutions:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, 
   x4}, Integers] // Reduce
Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, 
   x4}, Integers] // Solve

(x1 == -1 && x3 == -1 && x2 == -3 && 
   x4 == -2) || (x1 == -1 && x3 == -1 && x2 == -2 && 
   x4 == -3) || (x1 == 1 && x3 == 1 && x2 == 2 && 
   x4 == 3) || (x1 == 1 && x3 == 1 && x2 == 3 && x4 == 2)

{{x1 -> -1, x2 -> -3, x3 -> -1, x4 -> -2}, {x1 -> -1, 
  x2 -> -2, x3 -> -1, x4 -> -3}, {x1 -> 1, x2 -> 2, x3 -> 1, 
  x4 -> 3}, {x1 -> 1, x2 -> 3, x3 -> 1, x4 -> 2}}

Even FullSimplify fails:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, 
   x4}, Integers] // FullSimplify

enter image description here

$\endgroup$
4
$\begingroup$

Also works with some alternate variable orders. For instance:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12},
 {x4, x1, x2, x3}, Integers]
(*
(x4 == -3 && x1 == -1 && x2 == -2 && x3 == -1) ||
 (x4 == -2 && x1 == -1 && x2 == -3 && x3 == -1) ||
 (x4 == 2 && x1 == 1 && x2 == 3 && x3 == 1) ||
 (x4 == 3 && x1 == 1 && x2 == 2 && x3 == 1)
*)

It maybe should be reported to WRI, since better behavior seems possible.

$\endgroup$
2
  • $\begingroup$ That's even stranger. (+1) $\endgroup$ Dec 11, 2023 at 15:21
  • $\begingroup$ Actually I think the double-Reduce is stranger. Even in human, by-hand work, it can make a difference which variable you eliminate first. And it is documented that Reduce depends on the order of the variables, which is what made me think to try a different order. I still think Reduce should probably be able to do a better job here, and the double-Reduce supports that claim. $\endgroup$
    – Goofy
    Dec 11, 2023 at 18:17
2
$\begingroup$

Here is a partial workaround in 13.3.1 on Windows 10:

FindInstance[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, x4}, Integers, 5]

FindInstance::fwsol: Warning: FindInstance found only 4 instance(s), but it was not able to prove 5 instances do not exist. {{x1 -> -1, x2 -> -3, x3 -> -1, x4 -> -2}, {x1 -> -1, x2 -> -2, x3 -> -1, x4 -> -3}, {x1 -> 1, x2 -> 2, x3 -> 1, x4 -> 3}, {x1 -> 1, x2 -> 3, x3 -> 1, x4 -> 2}}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.