# Solving $n$-binary-variable system of equations using only combinations of $n \over 2$ variables when $n \over 2$ is even

It seems that it's impossible to find the unique solution to an $n$-binary-variable system of XOR equations if you only use all $(n \text{ choose } {n \over 2})$ equations combining half the variables, when $n \over 2$ is even i.e. $n \mod 4 \equiv 0$. Why is that?

I'm not that great with notation (suggestions for improvement appreciated!), but for $n$ binary variables: $$x_1, \dots, x_n \in \{0, 1\}$$ ...we can define an "equation" as the XOR of half of those variables: $$(x_1 \wedge y_1) \oplus (x_2 \wedge y_2) \oplus \cdots \oplus (x_n \wedge y_n)$$ $$y = \text{permutation of }(1, \dots, 1, 0, \dots, 0)$$ ...where the number of $1$'s in $y$ is the same as the number of $0$'s which is an even number (i.e. $n \mod 4 \equiv 0$).

For example, you cannot find the unique solution to a system of four-variable equations when all you know are all the combinations of exactly two variables. Here's an example sequence of four variables whose values we know: $$x_{\text{example}} = (1, 1, 0, 0)$$

...and here's all $(n \text{ choose } {n \over 2}) = (4 \text{ choose } 2) = 6$ possible values of $y$:

$$y_1 = (0, 0, 1, 1)$$ $$y_2 = (0, 1, 1, 0)$$ $$y_3 = (1, 1, 0, 0)$$ $$y_4 = (0, 1, 0, 1)$$ $$y_5 = (1, 0, 1, 0)$$ $$y_6 = (1, 0, 0, 1)$$

...we can represent these equations and their solutions with a table/matrix:

     |     |     |     |     | xor(...)
=====+=====+=====+=====+=====+==========
y_1 |  0  |  0  |  1  |  1  | = 0 = (x_1 & 0) ^ (x_2 & 0) ^ (x_3 & 1) ^ (x_4 & 1) = x_3 ^ x_4
-----+-----+-----+-----+-----+----------
y_2 |  0  |  1  |  1  |  0  | = 1
-----+-----+-----+-----+-----+----------
y_3 |  1  |  1  |  0  |  0  | = 0
-----+-----+-----+-----+-----+----------
y_4 |  0  |  1  |  0  |  1  | = 1
-----+-----+-----+-----+-----+----------
y_5 |  1  |  0  |  1  |  0  | = 1
-----+-----+-----+-----+-----+----------
y_6 |  1  |  0  |  0  |  1  | = 1


...and do something like Gaussian Elimination (row operations using swap and XOR) to give us this:

     |     |     |     | xor(...)
=====+=====+=====+=====+==========
1  |  0  |  0  |  1  | = 1
-----+-----+-----+-----+----------
0  |  1  |  0  |  1  | = 1
-----+-----+-----+-----+----------
0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
0  |  0  |  1  |  1  | = 0
-----+-----+-----+-----+----------
0  |  0  |  1  |  1  | = 0


But notice that although we started with all possible combinations of two variables we cannot recover the values of $x_1 \dots x_4$. Instead, all we've found out for our $x_{\text{example}}$ is that $x_1 \neq x_4$, $x_2 \neq x_4$, and that $x_3 = x_4$.

Interestingly e.g. 10-variable systems can be solved while 12-variable systems cannot.

Can anyone show a proof of this for all values of $n$?

Edit: In the case of four variables like above I feel like it has something to do with the fact that the equations can only represent whether any two variables are equal or not equal. But I don't know how to extend that to the case of eight variables.

• I don't understand. What system of equations are you trying to solve? Apr 20, 2016 at 17:14
• Can you precisely define the system of equations? Apr 20, 2016 at 17:15
• @RobertIsrael Do these edits help? Apr 20, 2016 at 17:38
• @StellaBiderman I tried making it a little more precise Apr 20, 2016 at 17:38
• Perhaps you should clarify the meaning of "can't be solved". Does this refer to a system of equations that has no solution, or to a system of equations that has multiple solutions (so no unique solution)? Apr 20, 2016 at 18:28

Here is a somewhat more general result. I will use $\oplus$ to denote logical exclusive or.

Suppose we have a Boolean system of equations (equivalently, a system of linear equations in several variables $x_1,x_2,\ldots,x_n$ over $\mathbb{Z}/2\mathbb{Z}$).

If the equations can be rewritten in a form where all the variables appear only as in XOR'ing pairs of variables, then any solution $x_1,x_2,\ldots,x_n$ gives rise to a different solution by complementation, $\overline{x_1},\overline{x_2},\ldots, \overline{x_n}$.

Note that $x_i \oplus x_j \equiv \overline{x_i} \oplus \overline{x_j}$, regardless of whether $i,j$ are distinct or not.

So a system of the kind considered here cannot have a unique solution.

• How do we extend this from the case of pairs of XOR'd variables to XOR's of all even counts of variables? Perhaps by expanding the definition of a single-bit variable to a $b$-bit variable, $\oplus$ to the bitwise XOR, and $\overline{(x_1, x_2, \dots, x_b)} = (\overline{x_1}, \overline{x_2}, \dots, \overline{x_b})$? Wouldn't your answer about pairwise XOR'ing of single bits then apply to pairwise bitwise-XOR'ing of multi-bit variables (which is the same as XOR'ing any even count of variables)? Apr 20, 2016 at 19:16
• Since XOR is an associative operation, the XOR'ing of any even number of variables is equivalent to the XOR'ing of some number of pairs of variables. Apr 20, 2016 at 19:19
• Indeed you need the associative property of XOR to make sense of a (well-defined) notion of XOR'ing more than two variables at a time. Apr 20, 2016 at 19:20