2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I don't understand. What system of equations are you trying to solve? $\endgroup$ Apr 20, 2016 at 17:14
  • $\begingroup$ Can you precisely define the system of equations? $\endgroup$ Apr 20, 2016 at 17:15
  • $\begingroup$ @RobertIsrael Do these edits help? $\endgroup$ Apr 20, 2016 at 17:38
  • $\begingroup$ @StellaBiderman I tried making it a little more precise $\endgroup$ Apr 20, 2016 at 17:38
  • $\begingroup$ 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)? $\endgroup$
    – hardmath
    Apr 20, 2016 at 18:28

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$ Apr 20, 2016 at 19:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Apr 20, 2016 at 19:19
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Apr 20, 2016 at 19:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .