0

Let's say we have $n$ binary unknowns (i.e. either 0 or 1), $x_1$ to $x_n$. And we have some equations similar to the following:

$x_1 + x_2 + \dots + x_n = a_1$,

$x_1.x_2 + x_3.x_4 + \dots + x_{n-1}.x_n = a_2$,

$\dots$

$(1-x_1).x_2.x_3.(1-x_4) + (1-x_5).x_6.x_7.(1-x_8) + \dots = a_i$,

$\dots$

In linear equations systems, we can determine whether there is a solution or not based on number of unknowns vs. equations.

What I wonder is, is there a rule, similar to the linear equations for above kind of equations? If not, how should I approach solving these kinds of equations?

Thank you

xycf7
  • 131
  • 2
    In general, Bézout's theorem implies that (counting complex solutions with multiplicity, and possibly counting solutions "at $\infty$") one expects a number of solutions equal to $\delta_1\cdots\delta_m$ for a system of $m$ polynomial equations of degrees $\delta_1,...,\delta_m$. But, in general, it is hard to say whether they will be real/finite. https://en.wikipedia.org/wiki/B%C3%A9zout%27s_theorem#General_case – Giulio R Dec 19 '22 at 15:05
  • @GiulioR Maybe it is because I do not have math background, but I really did not understand that. But given that the unknowns could only be 0 or 1, is it possible to find a limit where there cannot be any solutions by increasing the number of distinct equations? – xycf7 Dec 19 '22 at 15:10
  • 1
    Sorry, misread! I did not take into account that the solutions can only be $0,1$. Then Bézout's theorem will only give an upper bound for the number of solutions. In general, it is hard to tell the number of solutions. If you have a more specific form for your equations maybe something could be said. Also, Bézout's theorem refers to the case when there are $n$ equations in $n$ variables. – Giulio R Dec 19 '22 at 15:18
  • Well, I split the unknowns in groups of $m$ items. And each group is multiplied together. And each unknown is either used as is or as it's negate, as $1-x$. This is determined by a binary pattern. If you check the 3rd equation, $m=4$ and the binary pattern is $0110$, so 1 and 4 are negated and 2 and 3 are multiplied as is. So, I can generate $2^m$ different equations for each $m$. And I have an upper limit, $m \leq k$. What I am trying to find is, at what value of $k$ (relative to the value of $n$) the equations stop having a solution. (Or something like this.) – xycf7 Dec 19 '22 at 15:21

0 Answers0