Knuth's non-associative "group" on $\mathcal{P}(\mathbb{N})$

Abstract

Donald Knuth introduced in The Art of Computer Programming (Vol 4a) a fast approximation to the addition of integers (given in binary) in terms of bit-wise operations by $a+b\approx a\oplus b\oplus ((a\wedge b)\ll 1).$ Generalizing this to infinite bit-strings we get a binary operation on $\mathcal{P}(\mathbb{N})$, the power-set of $\mathbb{N}$ (which we identify with the collection of infinite bit-strings). We show that this operation is ``group-like'' in that it has a neutral element, inverses, but it is not associative. There are a lot of questions left, which the author has not been able to answer.

4 pages