Re: Equation solver

Hi Tony,

I believe in general solving such system of non-congruences is NP-hard.

As of the practical solution, I'd replace each non-congruence with an inequality like

| C(0,0) + C(0,1) + C(1,0) + C(1,1) - 2 - 4k | <= 1,

where k is a new integer variable, which in other words means that the value C(0,0) + C(0,1) + C(1,0) + C(1,1) - 4k is at most at distance 1 from integer 2.

Similarly, C(i,j)=0 or 1 can be posed as | 2C(i,j) - 1 | <= 1, that is, 2C(i,j) is at most at distance 1 from integer 1.

Combining all such inequalities together further leads to a Closest Vector Problem (CVP), which in practice can be solved with LLL algorithm (function qflll() in PARI).

See https://en.wikipedia.org/wiki/Closest_vector_problem

Regards,

Max

On Thu, Aug 16, 2018 at 12:31 PM <tony.reix@laposte.net> wrote:

Hi,

I'm looking for an "Equation Solver" that would be able to solve equations like below (where: N=6, C(i,j)=0 or 1, with i=0..N-1, j=0..N1).
Any idea ?
Do you know about features of Pari which could help ?

Thanks

Tony

C(0,0) + C(0,1) + C(1,0) + C(1,1) != 0 (mod 4)
C(0,1) + C(0,2) + C(1,1) + C(1,2) != 0 (mod 4)
C(0,2) + C(0,3) + C(1,2) + C(1,3) != 0 (mod 4)
C(0,3) + C(0,4) + C(1,3) + C(1,4) != 0 (mod 4)
C(0,4) + C(0,5) + C(1,4) + C(1,5) != 0 (mod 4)
C(1,0) + C(1,1) + C(2,0) + C(2,1) != 0 (mod 4)
C(0,0) + C(0,2) + C(2,0) + C(2,2) != 0 (mod 4)
C(1,1) + C(1,2) + C(2,1) + C(2,2) != 0 (mod 4)
C(0,1) + C(0,3) + C(2,1) + C(2,3) != 0 (mod 4)
C(1,2) + C(1,3) + C(2,2) + C(2,3) != 0 (mod 4)
C(0,2) + C(0,4) + C(2,2) + C(2,4) != 0 (mod 4)
C(1,3) + C(1,4) + C(2,3) + C(2,4) != 0 (mod 4)
C(0,3) + C(0,5) + C(2,3) + C(2,5) != 0 (mod 4)
C(1,4) + C(1,5) + C(2,4) + C(2,5) != 0 (mod 4)
C(2,0) + C(2,1) + C(3,0) + C(3,1) != 0 (mod 4)
C(1,0) + C(1,2) + C(3,0) + C(3,2) != 0 (mod 4)
C(2,1) + C(2,2) + C(3,1) + C(3,2) != 0 (mod 4)
C(0,0) + C(0,3) + C(3,0) + C(3,3) != 0 (mod 4)
C(1,1) + C(1,3) + C(3,1) + C(3,3) != 0 (mod 4)
C(2,2) + C(2,3) + C(3,2) + C(3,3) != 0 (mod 4)
C(0,1) + C(0,4) + C(3,1) + C(3,4) != 0 (mod 4)
C(1,2) + C(1,4) + C(3,2) + C(3,4) != 0 (mod 4)
C(2,3) + C(2,4) + C(3,3) + C(3,4) != 0 (mod 4)
C(0,2) + C(0,5) + C(3,2) + C(3,5) != 0 (mod 4)
C(1,3) + C(1,5) + C(3,3) + C(3,5) != 0 (mod 4)
C(2,4) + C(2,5) + C(3,4) + C(3,5) != 0 (mod 4)
C(3,0) + C(3,1) + C(4,0) + C(4,1) != 0 (mod 4)
C(2,0) + C(2,2) + C(4,0) + C(4,2) != 0 (mod 4)
C(3,1) + C(3,2) + C(4,1) + C(4,2) != 0 (mod 4)
C(1,0) + C(1,3) + C(4,0) + C(4,3) != 0 (mod 4)
C(2,1) + C(2,3) + C(4,1) + C(4,3) != 0 (mod 4)
C(3,2) + C(3,3) + C(4,2) + C(4,3) != 0 (mod 4)
C(0,0) + C(0,4) + C(4,0) + C(4,4) != 0 (mod 4)
C(1,1) + C(1,4) + C(4,1) + C(4,4) != 0 (mod 4)
C(2,2) + C(2,4) + C(4,2) + C(4,4) != 0 (mod 4)
C(3,3) + C(3,4) + C(4,3) + C(4,4) != 0 (mod 4)
C(0,1) + C(0,5) + C(4,1) + C(4,5) != 0 (mod 4)
C(1,2) + C(1,5) + C(4,2) + C(4,5) != 0 (mod 4)
C(2,3) + C(2,5) + C(4,3) + C(4,5) != 0 (mod 4)
C(3,4) + C(3,5) + C(4,4) + C(4,5) != 0 (mod 4)
C(4,0) + C(4,1) + C(5,0) + C(5,1) != 0 (mod 4)
C(3,0) + C(3,2) + C(5,0) + C(5,2) != 0 (mod 4)
C(4,1) + C(4,2) + C(5,1) + C(5,2) != 0 (mod 4)
C(2,0) + C(2,3) + C(5,0) + C(5,3) != 0 (mod 4)
C(3,1) + C(3,3) + C(5,1) + C(5,3) != 0 (mod 4)
C(4,2) + C(4,3) + C(5,2) + C(5,3) != 0 (mod 4)
C(1,0) + C(1,4) + C(5,0) + C(5,4) != 0 (mod 4)
C(2,1) + C(2,4) + C(5,1) + C(5,4) != 0 (mod 4)
C(3,2) + C(3,4) + C(5,2) + C(5,4) != 0 (mod 4)
C(4,3) + C(4,4) + C(5,3) + C(5,4) != 0 (mod 4)
C(0,0) + C(0,5) + C(5,0) + C(5,5) != 0 (mod 4)
C(1,1) + C(1,5) + C(5,1) + C(5,5) != 0 (mod 4)
C(2,2) + C(2,5) + C(5,2) + C(5,5) != 0 (mod 4)
C(3,3) + C(3,5) + C(5,3) + C(5,5) != 0 (mod 4)
C(4,4) + C(4,5) + C(5,4) + C(5,5) != 0 (mod 4)