6
$\begingroup$

Consider the function $f(x,a,b,c,d) = (((x \oplus a) + b) \oplus c) + d$ defined on $\mathbb{Z}_ {2^n}$, where $\oplus$ denotes bitwise exclusive-OR (XOR) and $+$ denotes addition modulo $2^n$.

Let's start with two definitions:

  1. $f(\cdot,a,b,c,d)$ is an identity function on $\mathbb{Z}_{2^n}$ if $\forall x \in \mathbb{Z}_{2^n}, f(x,a,b,c,d) = x$.
  2. $f(\cdot,a',b',c',d')$ is identical to $f(\cdot,a,b,c,d)$ if $\forall x \in \mathbb{Z}_{2^n}, f(x,a',b',c',d') = f(x,a,b,c,d)$.

In answer to this question, it has been shown that the number of identity functions is equal to $n \times 2^{n+2}$.

Furthemore, when looking in practice for several $n$, it seems that $n \times 2^{n+2}$ is also the number of identical functions for a given $(a,b,c,d) \in (\mathbb{Z}_{2^n})^4$.

In fact, identity functions are the specific case where $(a,b,c,d) \in (\mathbb{Z}_{2^n})^4$ is such that $f(x,a,b,c,d) = x$.

Is there a way to prove that the number of identity functions is equal to the number of identical functions? In other terms, how can we extend the demonstration for all $(a,b,c,d) \in (\mathbb{Z}_{2^n})^4$?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ How do you define XOR on $\mathbb{Z}_{2^n}$ for $n > 1$? $\endgroup$ – Derek Allums Jul 21 '17 at 15:56
  • $\begingroup$ @DerekAllums It's done bit by bit, for example with $n=4$, $(1001)_2 \oplus (0111)_2 = (1110)_2$. $\endgroup$ – Raoul722 Jul 21 '17 at 16:57
1
+100
$\begingroup$

I think this conjecture is false, actually—the number of "identical" functions seems to depend on the particular tuple. $\newcommand{\blank}{\underline{\hspace{0.7em}}}$

For example, when $n=3$, it seems like the tuple $\langle 0,0,0,0\rangle$ (which yields the identity function) belongs to a group of 96 = $4n\cdot 2^n$ tuples that all yield the same function, consistent with the result you've already proven.

But for the tuple $\langle 0, 1, 1, 0\rangle$, it seems like there are only 32 such tuples. If this is true, I suspect it will be because the collection of tuples that yield the identity have more symmetries available than the tuples that yield $\langle 0, 1, 1, 0\rangle$. This is a counterexample which establishes a negative result, showing that not all cosets of equivalent tuples have the same size $4n\cdot 2^n$.

Here is a partial explanation. Fix a particular bitstring length $n$. To avoid writing too many parentheses, assume that all operators are left-associative so that $a\boxplus b\boxplus c \boxplus d$ means $((a\boxplus b)\boxplus c)\boxplus d$.

The number $h \equiv 2^{n-1}$ has several special properties in this setting:

  1. The function $(\blank\oplus h)$ behaves identically to the translation $(\blank + h)$. Adding $h$ is equivalent to xoring by $h$.
  2. Viewed as an xor, it flips the highest bit of each number. Viewed as a translation (consider the numbers $0\ldots (2^n-1)$ arranged in a circle for modular arithmetic), it rotates each number by a half-turn.
  3. Because of this half-turn, adding/xoring with $h$ causes numbers higher than $h$ to become less than $h$, and vice-versa.
  4. And in fact, out of all possible xor functions $(\blank \oplus a)$ and all possible translation functions $(\blank + b)$, the only xor that is equivalent to some translation is $(\blank\oplus h)$ and the only translation that is equivalent to some xor is $(\blank + h)$.
  5. Adding/xoring $h$ twice does nothing: $\blank + h + h = \blank \oplus h \oplus h = \blank + h \oplus h = \blank \oplus h + h = \blank$.

Now suppose we have a function

$$\blank \oplus a + b$$

We know that operating by $h$ twice does nothing, so this function is equivalent to another one with the same form but with different parameters $a^\prime$ and $b^\prime$:

$$ \begin{align*} \blank \oplus a + b &= \blank \oplus a \oplus h + h + b\\ &= \blank \oplus (a\oplus h) + (h+b)\\ &= \blank \oplus a^\prime + b^\prime \end{align*} $$

Take a more complex example:

$$\blank \oplus a + b \oplus c + d$$

Using the same trick as before, we can find other tuples $\langle a^\prime, b^\prime, c^\prime, d^\prime\rangle$ which yield an equivalent function: We can insert a pair of $h$s between $a$ and $b$, or between $b$ and $c$, or between $c$ and $d$, or any combination of these— all of them yield different numbers.

Because we can insert a pair of $h$s in three different locations, and each combination of insertions yields a different tuple, we know that there are $2^3=8$ combinations.

As a consequence of this trick, we therefore know that for each tuple $\langle a, b, c, d\rangle$, there are at least eight tuples (itself included) which yield the same function.

Moreover, because of property (3), we can always apply an appropriate combination to find a representative tuple where $a,c < h$ (for example).


As for the identity, we know that $\blank \oplus 0 + 0 \oplus 0$ is an identity function. How many other such tuples also yield the identity function?

  • If we consider tuples with no xor component $(a=c=0)$, there are $2^n$ tuples $\langle 0, b, 0, -b\rangle$ equivalent to the identity.
  • If we consider tuples with no translation component $(b=d=0)$, there are $2^n$ tuples $\langle a, 0, \overline{a}, 0\rangle$ equivalent to the identity.
  • If we apply our multiplicity trick to the previous tuples, we multiply the number of results approximately eightfold, because each of the previous examples is independent of each of the others.

This is not an exhaustive careful counting of the possibilities (and in fact, we've counted $\langle 0,0,0,0\rangle$ more than once) but it makes clear one apparent advantage of the identity function. In particular, we can make both its translation and xor components independently zero, which means that we can obtain many different independent prototypes.

In contrast, other tuples like $\langle 0, 1, 1, 0\rangle$ do not have as many independent prototypes, because each position is more tightly coupled to the others; there is no way to "zero out" the interaction.


The tuples I find in particular are:

FOR THE IDENTITY
(0, 0, 0, 0)
(0, 0, 4, 4)
(0, 1, 0, 7)
(0, 1, 4, 3)
(0, 2, 0, 6)
(0, 2, 4, 2)
(0, 3, 0, 5)
(0, 3, 4, 1)
(0, 4, 0, 4)
(0, 4, 4, 0)
(0, 5, 0, 3)
(0, 5, 4, 7)
(0, 6, 0, 2)
(0, 6, 4, 6)
(0, 7, 0, 1)
(0, 7, 4, 5)
(1, 0, 1, 0)
(1, 0, 5, 4)
(1, 2, 1, 6)
(1, 2, 5, 2)
(1, 4, 1, 4)
(1, 4, 5, 0)
(1, 6, 1, 2)
(1, 6, 5, 6)
(2, 0, 2, 0)
(2, 0, 6, 4)
(2, 2, 2, 2)
(2, 2, 6, 6)
(2, 4, 2, 4)
(2, 4, 6, 0)
(2, 6, 2, 6)
(2, 6, 6, 2)
(3, 0, 3, 0)
(3, 0, 7, 4)
(3, 1, 3, 1)
(3, 1, 7, 5)
(3, 2, 3, 2)
(3, 2, 7, 6)
(3, 3, 3, 3)
(3, 3, 7, 7)
(3, 4, 3, 4)
(3, 4, 7, 0)
(3, 5, 3, 5)
(3, 5, 7, 1)
(3, 6, 3, 6)
(3, 6, 7, 2)
(3, 7, 3, 7)
(3, 7, 7, 3)
(4, 0, 0, 4)
(4, 0, 4, 0)
(4, 1, 0, 3)
(4, 1, 4, 7)
(4, 2, 0, 2)
(4, 2, 4, 6)
(4, 3, 0, 1)
(4, 3, 4, 5)
(4, 4, 0, 0)
(4, 4, 4, 4)
(4, 5, 0, 7)
(4, 5, 4, 3)
(4, 6, 0, 6)
(4, 6, 4, 2)
(4, 7, 0, 5)
(4, 7, 4, 1)
(5, 0, 1, 4)
(5, 0, 5, 0)
(5, 2, 1, 2)
(5, 2, 5, 6)
(5, 4, 1, 0)
(5, 4, 5, 4)
(5, 6, 1, 6)
(5, 6, 5, 2)
(6, 0, 2, 4)
(6, 0, 6, 0)
(6, 2, 2, 6)
(6, 2, 6, 2)
(6, 4, 2, 0)
(6, 4, 6, 4)
(6, 6, 2, 2)
(6, 6, 6, 6)
(7, 0, 3, 4)
(7, 0, 7, 0)
(7, 1, 3, 5)
(7, 1, 7, 1)
(7, 2, 3, 6)
(7, 2, 7, 2)
(7, 3, 3, 7)
(7, 3, 7, 3)
(7, 4, 3, 0)
(7, 4, 7, 4)
(7, 5, 3, 1)
(7, 5, 7, 5)
(7, 6, 3, 2)
(7, 6, 7, 6)
(7, 7, 3, 3)
(7, 7, 7, 7)

------------------------
FOR TRANSLATE 1, XOR 1

(0, 1, 1, 0)
(0, 1, 5, 4)
(0, 3, 1, 6)
(0, 3, 5, 2)
(0, 5, 1, 4)
(0, 5, 5, 0)
(0, 7, 1, 2)
(0, 7, 5, 6)
(3, 1, 2, 2)
(3, 1, 6, 6)
(3, 3, 2, 4)
(3, 3, 6, 0)
(3, 5, 2, 6)
(3, 5, 6, 2)
(3, 7, 2, 0)
(3, 7, 6, 4)
(4, 1, 1, 4)
(4, 1, 5, 0)
(4, 3, 1, 2)
(4, 3, 5, 6)
(4, 5, 1, 0)
(4, 5, 5, 4)
(4, 7, 1, 6)
(4, 7, 5, 2)
(7, 1, 2, 6)
(7, 1, 6, 2)
(7, 3, 2, 0)
(7, 3, 6, 4)
(7, 5, 2, 2)
(7, 5, 6, 6)
(7, 7, 2, 4)
(7, 7, 6, 0)
| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ You're right! For the tuple $\langle 0, 1, 1, 0\rangle$, there are only $32$ identical functions. How can we explain that tuples which define identity functions lead to more symmetries than others? $\endgroup$ – Raoul722 Jul 31 '17 at 5:46

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.