Revision history [back]

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$. The ideal generated by these equations together with 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)]
B = BooleanPolynomialRing(2*n, xy) 
R = PolynomialRing(GF(2),2*n, xy) 
Y = PolynomialRing(GF(2), n, xy[n:])
R.inject_variables()
x = R.gens()[:n]
y = R.gens()[n:]
print(x,y)
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 + [g^2+g for g in R.gens()] )
print(J.variety())

This code produces 32 solutions.

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$. The ideal generated by these equations together with 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)]
B = BooleanPolynomialRing(2*n, xy) 
R = PolynomialRing(GF(2),2*n, xy) 
Y = PolynomialRing(GF(2), n, xy[n:])
R.inject_variables()
x = R.gens()[:n]
y = R.gens()[n:]
print(x,y)
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 + [g^2+g for g in R.gens()] )
print(J.variety())

This code produces 32 solutions.

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$. The ideal generated by these equations together with 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)]
B R = BooleanPolynomialRing(2*n, PolynomialRing(GF(2),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 + [g^2+g for g in R.gens()] )
print(J.variety())

This code produces 32 solutions.

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$. The $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 these equations together with 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 = PolynomialRing(GF(2),2*n, 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 + [g^2+g for g in R.gens()] )
print(J.variety())

This code produces 32 solutions.

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.

First off, it is not possible to express $x_i$ in terms of $y_i$, since the $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.