# Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$

Let $$\mathbb{Z}_2^n$$ be the field of bitvectors of length $$n$$ and define the xor operator $$\oplus$$ and the addition operator $$+$$ over this field, with $$+$$ having the usual overflow semantics (take addition modulo $$2^n$$).

Is it possible to express any mapping $$f: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$$ entirely in terms of $$\oplus$$ and $$+$$? It seems like it might be possible due to the nonlinearity of $$+$$.

For instance, if we were given $$n=2$$ and that $$f(0) = 3, f(1) = 1, f(2) = 3, f(3) = 1$$, then we could construct $$f$$ as $$f(x) = x\oplus(x+3)$$.

Nope. For instance, you can't express the function $$f(x)=x>>1$$. In general, the least-significant bit of $$f(x)$$ depends only on the least-significant bit of $$x$$. You can prove that by structural induction, using the following two properties: $$(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$$ and $$(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \bmod 2$$.