Ask Your Question

Solve system of symbolic binary nonlinear equations

asked 2022-03-13 13:39:23 +0200

Sanu gravatar image

updated 2022-03-13 18:28:05 +0200

slelievre gravatar image

I have 10 binary variables $x_0$, ..., $x_4$ and $y_0$, ..., $y_4$. I know $y_i = x_i + x_{(i+1)\bmod 5}$.

I want to write $x_i$ in terms of $y$ variables.

I know for this toy case we can use Gaussian elimination. But in actual case $y_i$s are nonlinear equations.

I tried this idea:

n = 5
xy = [f'x{i}' for i in range(n)] + [f'y{i}' for i in range(n)]
R = PolynomialRing(GF(2), 2*n, xy) 
Z = list(R.gens()) 
E = [y_0 == x_0*x_1 + x_2,
     y_1 == x_1*x_2+x_3,
     y_2 == x_2*x_3+x_4,
     y_3 == x_3*x_4+x_0,
     y_4 == x_4*x_0+x_1] 
solve(E, x0, x1, x2, x3, x4)

It is not working.

edit retag flag offensive close merge delete


Please add the actual (nonlinear) case, so that a better answer can be given.

rburing gravatar imagerburing ( 2022-03-13 14:49:28 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2022-03-13 21:07:17 +0200

Max Alekseyev gravatar image

updated 2022-03-13 21:21:57 +0200

First off, it is not possible to express $x_i$ in terms of $y_i$ since, for instance, all zero values for $y_i$ correspond to at least two different sets of $x_i$: all zeros and all ones.

Since $x_i$ and $y_i$ are binary, we also have equations $x_i^2+x_i=0$ and $y_i^2+y_i=0$, which will be taken into account if we use BooleanPolynomialRing(...) rather than PolynomialRing(GF(2),...). In this ring, the ideal generated by the given system happens to be 0-dimensional, and thus the system has a finite number of solutions in GF(2):

n = 5
xy = [f'x{i}' for i in range(n)] + [f'y{i}' for i in range(n)]
R = BooleanPolynomialRing(2*n, xy) 
E = [y0 - (x0*x1 + x2),
     y1 - (x1*x2 + x3),
     y2 - (x2*x3 + x4),
     y3 - (x3*x4 + x0),
     y4 - (x4*x0 + x1)]

J = R.ideal( E )

This code produces 32 solutions.

It can also be seen directly as fixing any values for $x_i$ immediately imply values for $y_i$. So, the above approach may be an overkill.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-03-13 13:39:23 +0200

Seen: 952 times

Last updated: Mar 13 '22