I am trying to understand the relation between exclusive-OR (XOR) and modular addition in the function $f(x,a,b,c,d) = \bigg(\Big(\big((x \oplus a) \boxplus b\big) \oplus c\Big) \boxplus d\bigg)$ over $\mathbb{Z}_{2^n}$, where $\oplus$ denotes XOR and $\boxplus$ denotes addition modulo $2^n$.
It seems that when $n=2$, for any value of $(a,b,c,d)$, I can find $31$ different $(a',b',c',d')$ such that $f(x,a,b,c,d) = f(x,a',b',c',d')$.
I can explain it in the following way: bits of different operands can be flipped to get the same result at the end. For example, let's consider $(a,b,c,d) = (3,3,1,0)$. If we flip the most significant bit of $a$ and the most significant bit of $b$ we get $(a',b',c',d') = (1,1,1,0)$ and $f(x,a,b,c,d) = f(x,a',b',c',d')$ for any $x$. There are four other combinations, which explains the number of solutions $2^5 = 32$.
I get $96$ results for $n=3$, $256$ for $n=4$, etc... My problem is the following: whereas some combinations remain the same regardless of the parameter $n$, it seems that operands' size impact the number of combinations.
So my question is: given $n$, and $(a,b,c,d)$ how can I find the set $\mathcal{S}$ such that $\mathcal{S} = \{(a',b',c',d') \in (\mathbb{Z}_{2^n})^4\space | \space f(x,a,b,c,d) = f(x,a',b',c',d') \space \forall x \in \mathbb{Z}_{2^n}\}$?
Let's start with a few observations about $f$. I'll use $f(\cdot,a,b,c,d)$ to denote the function that maps $x\in\mathbb{Z}_{2^n}$ to $f(x,a,b,c,d)$ and refer to this as an identity function (on $\mathbb{Z}_{2^n}$) if $f(x,a,b,c,d)=x$ for all $x\in\mathbb{Z}_{2^n}$.
Somehow, my mind tricked me into thinking I should find all identity functions, not all identical functions $f(\cdot,a,b,c,d)=f(\cdot,a',b',c',d')$, so that's what I've done. They should be related somehow,...
If $f(\cdot,a,b,c,d)$ is an identity function on $\mathbb{Z}_{2^n}$, its reduction modulo $2^m$ for $m<n$ is an identity function on $\mathbb{Z}_{2^m}$: ie, if $a', b', c', d'\in\mathbb{Z}_{2^m}$ correspond to $a,b,c,d$ modulo $2^m$, then $f(\cdot,a',b',c',d')$ is an identity function on $\mathbb{Z}_{2^m}$.
If $b,d$ are both multiples of $2^k$ for $k\le n$, the addition terms modulo $2^n$ do not interfere with the lower $k$ bits, so if we split the numbers into lower $k$ and upper $n-k$ bits, ie $x=\hat x\cdot 2^k+x'$ etc, we can split $f(x,a,b,c,d)$ into two separate actions: $f(\hat x,\hat a,\hat b,\hat c,\hat d)$ on $\mathbb{Z}_{2^{n-k}}$ and $f(x',a',0,c',0)$ on $\mathbb{Z}_{2^k}$ (where $b'=d'=0$ by assumption). The latter of these, $f(x',a',0,c',0)$ is just XOR with $a'$ and then $c'$ which gives the identity function if $a'=c'$.
Since we may pick the largest such $k\le n$ so that $2^k$ divides $b$ and $d$, where $k=n$ corresponds to the case when $b=d=0$ in $\mathbb{Z}_{2^n}$, what remains to be solves is the case where either $b$ or $d$ is odd.
The simplest class of identity functions on $\mathbb{Z}_{2^n}$ are $f(\cdot,0,b,0,d)$ where $b + d=0$ modulo $2^n$.
At first glance, one might think that xor with anything other than zero would break the identity function since xor acts non-linearly on $\mathbb{Z}_{2^n}$. However, there are two exceptions.
First, xor with $2^{n-1}$ has the same effect as adding $2^{n-1}$, so we get identify functions $f(\cdot,a,b,c,d)$ for $b,d\in\mathbb{Z}_{2^n}$, $a,c\in\{0,2^{n-1}\}$ whenever $a+b+c+d=0$ modulo $2^n$.
Next, xor with $2^n-1$ maps $t\mapsto 2^n-1-t$ in $\mathbb{Z}_{2^n}$, which is also linear. Thus $f(\cdot,2^n-1,b,2^n-1,d)$ is an identity function when $b=d$.
Finally, these two may be combined: $a,c\in\{2^{n-1}-1,2^n-1\}$ makes $f(\cdot,a,b,c,d)$ an identity function if $a+b=c+d$ modulo $2^n$.
This gives four different classes of solution, and in all of them $b$ and $d$ are either both odd or both even, where it is the case where they are both odd we focus on as the basic solution.
If $b$ and $d$ are odd, we can pick $a,c$ in 8 different ways, either $a,c\in\{0,2^{n-1}\}$ or $a,c\in\{2^n-1,2^{n-1}-1\}$, and an arbitrary odd $d$, and then solve for $b$. Thus, there are $2^{n+2}$ solutions with $b,d$ odd.
If $b=\hat b\cdot 2^k$, $d=\hat d\cdot 2^k$ for odd $\hat b$ and $\hat d$, we do the split into $k$ lower bits and $n-k$ upper bits. For the $k$ lower bits, we have $b'=d'=0$ and need $a'=c'$ to get an identity function, which gives $2^k$ solutions. For the upper $n-k$ bits, we get the $2^{n-k+2}$ solutions found above for the case where $\hat b$ and $\hat d$ are odd.
We now have to add up the counts for different values of $k$. For $k=0,\ldots,n-2$ this is straight forward. However, the cases $k=n-1$ and $k=n$ (ie $b=d=0$) are both a little different, but are both easy to check: they have $3\cdot 2^n$ and $2^n$ solutions, respectively. In fact, for these two cases we may use that adding $2^{n-1}$ is the same as xor with $2^{n-1}$, so $f(\cdot,a,b,c,d)$ becomes an identity function for $b,d\in\{0,2^{n-1}\}$ if $a\oplus b\oplus c\oplus d=0$.
All in all, these result in $n\cdot 2^{n+2}$ identity functions.
I've checked with a Python script that these are all up to $n=9$, but see if I can come up with a proof.