2
$\begingroup$

I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf

  • Given 3 Boolean variables $x_i, x_j, x_k$ what is supposed to be the meaning of $x_i \oplus x_j \oplus x_k$?

    Is this to be understood as say $((x_i \oplus x_j )\oplus x_k )$? And hence this is true for only $2$ cases $x_i =0, x_j = 1, x_k =0$ and $x_i = 1, x_j = 0, x_k = 0$ ?

    But then we could have bracketed it as $(x_i \oplus (x_j \oplus x_k))$ and then the only true assignments would have looked as $x_i = 0, x_j =1, x_k = 0$ and $x_i = 0, x_j =0, x_k = 1$ and these are different.

    Also one could have used commutativity to write it in other re-arranged forms and gotten different true selections!

  • But then the note above seems to claim that if the $x_a$s are coming as coordinates of a vector $x \in \{\pm 1\}^n$ then the product $x_ix_j x_k$ is the same as having a linear equation in those $3$ variables. Why so? (for example an assignment $x_i = x_j = x_k =1$ will evaluate to $1$ for the product but under mod 2 arithmetic $x_i + x_j + x_k = 0$ for this assignment!)

Also it is being claimed that the value of $x_ix_jx_k$ can only be $\pm 1$ (which they denote as $a_{ijk}$) for $x \in \{\pm 1\}^n$ and that is okay only if one ignores the first claim that these are supposed to be linear equations!


This $x_ix_j x_k$ product notation looks more confusing later on when they say that corresponding to two subsets $S, T \subset \{1,..,n\}$ one can take two expressions of the form $x_S = \prod_{i \in S} x_i$ and $x_T = \prod_{i \in T} x_i$ and construct $x_U = x_S x_T$ and that this somehow corresponds to doing ``$U = S \oplus T$" - and I don't know what it means to take a XOR of two subsets!

$\endgroup$
5
$\begingroup$

XOR is an associative operation, so $x_i \oplus x_j \oplus x_k$ is unambiguous. There are in fact four satisfying assignments, given by $$ (x_i,x_j,x_k) \in \{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\}. $$

XOR satisfies the useful property $$ (-1)^{x \oplus y} = (-1)^x (-1)^y. $$ Therefore $x_i \oplus x_j \oplus x_k = 1$ is the same as $$ (-1)^{x_i} (-1)^{x_j} (-1)^{x_k} = (-1)^1.$$ If we think of our variables as $X_i = (-1)^{x_i}$, then the equation $x_i \oplus x_j \oplus x_k = 1$ is completely equivalent to $X_i X_j X_k = -1$. Since XOR is really just addition in the group $\mathbb{Z}_2$, you can think of both formulations as linear equations.


Yet another interpretation of XOR is in terms of sets. Just as AND corresponds to intersection and OR to union, the XOR operation corresponds to symmetric difference, sometimes denoted $\triangle$ or $\Delta$. You can easily check that $x_S x_T = x_{S \triangle T}$, essentially using $x_i^2 = 1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (1) If $x_i$ are the Boolean variables then a ``linear" equation in them has to look like $a_ix_i + a_jx_j + a_kx_k$ for $a_i, a_j a_k \in \{\pm\}^n$. But neither does $x_i \oplus x_j \oplus x_k$ nor does $X_i X_j X_k$ seem to be linear equations. Even over mod-2 operations the expression say $x_i + x_j + x_k$ is not the same as $x_ix_jx_k$. I am not getting your point! (2) Are you saying that when $\oplus$ is used between two sets we should read that as symmetric difference? So this is a new notation! $\endgroup$ – gradstudent Mar 13 '16 at 23:05
  • 1
    $\begingroup$ (1) If you think of the $x_i$ as elements of $\mathbb{Z}_2$, then $x_i \oplus x_j \oplus x_k = 1$ is just a linear equation (read $+$ for $\oplus$). (2) It's somewhat uncommon to use $\oplus$ for set, but the corresponding operation is definitely symmetric difference. $\endgroup$ – Yuval Filmus Mar 13 '16 at 23:08
  • $\begingroup$ Okay - I can see why $x_i \oplus x_j \oplus x_k = x_i + x_j + x_k$ over mod 2 operations but the whole proof is set up in terms of the product $x_i x_j x_k$ and that is clearly not the same as either of these two things above! $\endgroup$ – gradstudent Mar 13 '16 at 23:19
  • $\begingroup$ It's exactly the same if you replace $x_i$ with $(-1)^{x_i}$. $\endgroup$ – Yuval Filmus Mar 13 '16 at 23:20
  • $\begingroup$ Can't I think of it as $x_i \in \{-1,1\}$ and then XOR behaving as $x_i \oplus x_j = -x_ix_j$? Then $x_i \oplus x_j \oplus x_k = x_ix_jx_k$ and this evaluates to $1$ on exactly the $4$ options as before but with $0$ replaced by $-1$? Won't the proof in the link go through in this form too? $\endgroup$ – gradstudent Mar 17 '16 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.