Qué función $f$ tal implica de que $a_1 \oplus\, \cdots\,\oplus a_n = 0$ $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$

Question

Para un determinado algoritmo, necesito una función de $f$ en números enteros tales que

$a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$

(donde el $a_i$ son parejas distintas, enteros no negativos y $\oplus$ es la operación XOR en modo bit)

La función de $f$ debe ser computable en $O(m)$ donde $m$ es el número máximo de dígitos de la $a_i$. Por supuesto, el más simple de la función es el mejor. Preferiblemente la salida de la función de ajuste en $m$ dígitos así.

Hay algo como esto? También sería bueno tener una familia de un número finito de funciones $f_n$ tal que para una de las funciones del resultado de la operación anterior será $\neq 0$.

Mis propias consideraciones hasta ahora fueron los siguientes:

1. Si elegimos el " complemento como $f$, podemos descartar todos los casos en que $n$ es impar.
2. Si $n$ es aún, esto significa que por cada bit, un número de la $a_i$ tiene el conjunto de bits y el resto no tiene, por lo tanto, tomando el " complemento antes de cifrado xor no cambia el resultado.

Así que la parte más difícil parece ser el caso en que $n$ es incluso.

Answer 1

La función de $f$, si es que existe, debe tener muy grandes salidas.

Llame a un conjunto de números enteros "cerrado" si es cerrado bajo la operación $\oplus$. Un buen ejemplo de un conjunto cerrado de números enteros es el conjunto de enteros positivos menores que $2^k$ algunos $k$.

Deje $S$ ser un conjunto cerrado de enteros que forman el dominio de $f$. Tome como ejemplo los enteros positivos con en la mayoría de las $m$ bits. Deje $T$ ser el codominio de $f$, por lo que tenemos $f : S \to T$ la función de interés. Suponga además que el $T$ es un conjunto cerrado de números enteros.

Gran reclamo: $|T| \ge (2^{|S|}-1)/|S|$.

---

Prueba de dibujo:

Deje $A$ el conjunto de secuencias de $a_1 < a_2 < \dots < a_n$ de los distintos números enteros positivos en $S$. Deje $p : A \to S$ ser definido por $p(a_1,a_2,\dots,a_n) = a_1 \oplus \dots \oplus a_n$, y deje $q : A \to T$ ser definido por $q(a_1,\dots,a_n) = f(a_1) \oplus \dots \oplus f(a_n)$.

Reclamo: Si $p(a_1,\dots,a_n) = p(b_1,\dots,b_l),$$q(a_1,\dots,a_n) \ne q(b_1,\dots,b_l)$.

Prueba: Intercalar las secuencias de $a$$b$, eliminación de duplicados, para obtener una secuencia $c$. A continuación,$p(c) = p(a) \oplus p(b) = 0$, lo $q(c) \ne 0$; sin embargo,$q(c) = q(a) \oplus q(b)$.

Ahora, tenga en cuenta que hay $2^{|S|}-1$ elementos de $A$, por lo que no debe ser $(2^{|S|}-1)/|S|$ de esos elementos que comparten el mismo valor de $p$. Esto significa que $T$ debe contener $(2^{|S|}-1)/|S|$ valores distintos.

---

Por lo tanto, si $S$ se compone de $m$bits enteros, a continuación, $T$ debe consistir en aproximadamente el $(2^m-m)$bits enteros.

EDIT: Incorporación de los comentarios: la función de $f(a) = 2^a$ tiene la propiedad deseada, y casi logra esta obligado.