# Solve system of symbolic binary nonlinear equations

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)
R.inject_variables()
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 close merge delete

( 2022-03-13 14:49:28 +0200 )edit
1
( 2022-03-13 16:21:21 +0200 )edit

Sort by » oldest newest most voted

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)
R.inject_variables()
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 )
print(J.variety())


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.

more