En realidad, creo que esta conjetura es falsa: el número de funciones "idénticas" parece depender de la tupla concreta. $\newcommand{\blank}{\underline{\hspace{0.7em}}}$
Por ejemplo, cuando $n=3$ parece que la tupla $\langle 0,0,0,0\rangle$ (que da la función de identidad) pertenece a un grupo de 96 = $4n\cdot 2^n$ tuplas que dan la misma función, consistente con el resultado que ya has probado.
Pero para la tupla $\langle 0, 1, 1, 0\rangle$ Parece que sólo hay 32 tuplas de este tipo. Si esto es cierto, sospecho que será porque la colección de tuplas que dan la identidad tienen más simetrías disponibles que las tuplas que dan $\langle 0, 1, 1, 0\rangle$ . Este es un contraejemplo que establece un resultado negativo, mostrando que no todos los cosets de tuplas equivalentes tienen el mismo tamaño $4n\cdot 2^n$ .
He aquí una explicación parcial. Fijar una longitud de cadena de bits determinada $n$ . Para evitar escribir demasiados paréntesis, supongamos que todos los operadores son asociativos a la izquierda, de modo que $a\boxplus b\boxplus c \boxplus d$ significa $((a\boxplus b)\boxplus c)\boxplus d$ .
El número $h \equiv 2^{n-1}$ tiene varias propiedades especiales en este entorno:
- La función $(\blank\oplus h)$ se comporta de forma idéntica a la traducción $(\blank + h)$ . Añadiendo $h$ equivale a xorizar por $h$ .
- Visto como un xor, voltea el bit más alto de cada número. Visto como una traslación (considere los números $0\ldots (2^n-1)$ dispuestos en círculo para la aritmética modular), gira cada número media vuelta.
- A causa de esta media vuelta, la adición/extracción con $h$ provoca números más altos que $h$ para llegar a ser menos que $h$ y viceversa.
- Y de hecho, de todas las funciones xor posibles $(\blank \oplus a)$ y todas las posibles funciones de traducción $(\blank + b)$ el único xor que equivale a alguna traducción es $(\blank\oplus h)$ y la única traducción que equivale a algún xor es $(\blank + h)$ .
- Añadir/xortar $h$ dos veces no hace nada: $\blank + h + h = \blank \oplus h \oplus h = \blank + h \oplus h = \blank \oplus h + h = \blank$ .
Supongamos ahora que tenemos una función
$$\blank \oplus a + b$$
Sabemos que operar por $h$ dos veces no hace nada, por lo que esta función es equivalente a otra con la misma forma pero con diferentes parámetros $a^\prime$ y $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*} $$
Tomemos un ejemplo más complejo:
$$\blank \oplus a + b \oplus c + d$$
Utilizando el mismo truco que antes, podemos encontrar otras tuplas $\langle a^\prime, b^\prime, c^\prime, d^\prime\rangle$ que dan lugar a una función equivalente: Podemos insertar un par de $h$ s entre $a$ y $b$ o entre $b$ y $c$ o entre $c$ y $d$ o cualquier combinación de estos, todos ellos producen números diferentes.
Porque podemos insertar un par de $h$ s en tres lugares diferentes, y cada combinación de inserciones produce una tupla diferente, sabemos que hay $2^3=8$ combinaciones.
Como consecuencia de este truco, sabemos que para cada tupla $\langle a, b, c, d\rangle$ Hay al menos ocho tuplas (incluida ella misma) que dan lugar a la misma función.
Además, debido a la propiedad (3), siempre podemos aplicar una combinación adecuada para encontrar una tupla representativa donde $a,c < h$ (por ejemplo).
En cuanto a la identidad, sabemos que $\blank \oplus 0 + 0 \oplus 0$ es una función de identidad. ¿Cuántas otras tuplas de este tipo dan también la función identidad?
- Si consideramos las tuplas sin componente xor $(a=c=0)$ Hay $2^n$ tuplas $\langle 0, b, 0, -b\rangle$ equivalente a la identidad.
- Si consideramos las tuplas sin componente de traducción $(b=d=0)$ Hay $2^n$ tuplas $\langle a, 0, \overline{a}, 0\rangle$ equivalente a la identidad.
- Si aplicamos nuestro truco de la multiplicidad a las tuplas anteriores, multiplicamos el número de resultados aproximadamente por ocho, porque cada uno de los ejemplos anteriores es independiente de los demás.
No se trata de un recuento exhaustivo de las posibilidades (y de hecho, hemos contado $\langle 0,0,0,0\rangle$ más de una vez) pero deja clara una aparente ventaja de la función identidad. En particular, podemos hacer que sus componentes de traslación y xor independientemente cero lo que significa que podemos obtener muchos prototipos diferentes e independientes.
En cambio, otras tuplas como $\langle 0, 1, 1, 0\rangle$ no tienen tantos prototipos independientes, porque cada posición está más estrechamente acoplada a las demás; no hay forma de "eliminar" la interacción.
Las tuplas que encuentro en particular son:
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)
