8

In particular, I was musing on this trick for swapping two values in a program without allocating any new variables. Wikipedia proves its correctness, and the proof picqued my curiosity.

It relies on the following four properties of XOR:

  • Commutativity: $A \oplus B = B \oplus A$
  • Associativity: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
  • Identity exists: there is a bit string, 0, (of length N) such that $A \oplus 0 = A$ for any $A$
  • Each element is its own inverse: for each $A$, $A \oplus A = 0$.

I suspect that it'd be trivial to construct another group for which those four properties of XOR hold, so I'm not interested in the assertion that other such groups exist. Instead, I ask:

Are there any other functions over bit strings that satisfy these same properties? If so, what are some examples? If not, can we prove that?

(For example, my first thought was $|x - y|$ while interpreting the binary strings as integers, which satisfies commutativity, identity existence, and each element being its own inverse, but not associativity.)

Matchu
  • 181
  • (Incidentally, I don't know enough about abstract algebra to know if it's the correct tag, but the tag's description sounded reasonable. Feel free to retag as you see fit—thanks!) – Matchu Oct 06 '14 at 22:02
  • Also, it's easy to show that XOR is the only operation to satisfy these properties over the domain ${0, 1}$, so anything that works on a bit-by-bit level is definitely right out. I suspect that, if the answer is "yes", mapping to some other domain will be the easiest way to show it… – Matchu Oct 06 '14 at 22:07
  • Hmm. XOR is also the only satisfactory choice for two-bit strings. All operations that include the identity $00$ are predefined, as are all operations between a value and itself, so we're left with the operations $a \oplus b$ such that $a \neq b$ and $00 \notin {a, b}$. $a \oplus b$ must not be the identity or $a$ or $b$ in order to satisfy the properties (the proof of which I'll leave to you; you end up with the contradiction that $a = b$ or that $00 \in {a, b}$), so there's only one valid result, and it's the result that XOR chooses, too. – Matchu Oct 06 '14 at 22:24
  • 1
    Any elementary $2$-group satisfies the request, that is a group $G$ such that $g^2=1$ for all $g\in G$. These groups can also be seen as the vector spaces over the field with two elements. – egreg Oct 06 '14 at 22:37
  • Incidentally, the last three conditions of the four given imply the first one. – rschwieb Mar 19 '15 at 12:12

1 Answers1

3

Let's assume the strings have n bits and the zero string is the identity element. Then the number of different operations is (2^n-1)! divided by the number computed by the formula in this link with p=2. In the case of n=2 the answer is that XOR is unique as mentioned by Matchu, but in general there are many, many different operations that satisfy the conditions. For example, for n=5 there are 822,336,494,953,469,303,808,000,000 different operations.

Every commutative, associative, self-inverse binary operation on a finite set is essentially XOR on bit strings of a fixed length, by the classification of finite abelian groups. As egreg says, this turns the set into a vector space of dimension n over the field with two elements. Any two groups of this type with the same size are isomorphic so any function from the set of bit strings to itself that is one-to-one, onto, and fixes 0 gives another operation, which is possibly the same.

The operation is the same if and only if the function is an automorphism of the vector space, and the group of such automorphisms is called the general linear group, in this case of a vector space of dimension n over the finite field with two elements.

The group of all permutations of the nonzero elements, which has (2^n-1)! elements, acts on the set of satisfactory binary operations, and the stabilizer of an operation, which is a subgroup of the group of such permutations, has the same size as the general linear group. By the orbit-stabilizer theorem, the number of different operations is (2^n-1)!/(size of the general linear group).

Matt Samuel
  • 58,164
  • The link is now broken – it's a hire car baby Sep 02 '23 at 08:31
  • Is there a very similar answer to this question? https://math.stackexchange.com/q/4762155/334732 It looks to me like my question is asking for the homomorphisms of the set you describe here, except possibly replacing your self-inverse condition here with something else such as closed under inverses. – it's a hire car baby Sep 02 '23 at 08:35