Una conjetura sobre funciones binarias en cadenas binarias con inversos parciales

Question

Dado un número entero positivo $n$ denotamos $B = \{0,1\}^n$ . Conjeturo que para cualquier $f:B^2\to B$ ,

Si existe $g,h:B^2\to B$ s.t. para todos $x,y$ en $B$ , $g(f(x,y),x)=y$ y $h(f(x,y),y)=x$ entonces existe $u,v:B\to B$ s.t. $f = (x,y)\mapsto u(v(x)\oplus y)$ .

Nota: $\oplus$ denota el bitwise xor.

Un poco de contexto : Yo estaba tratando de demostrar la teorema de la codificación de canales ruidosos de una manera diferente a las clásicas usando AEP o los exponentes de error y esto llenaría el último hueco pero estoy un poco atascado con ello y también quizás un poco cansado/vago (no soy ni estudiante ni matemático). Es muy posible que esté mal pero entonces un contraejemplo sería interesante. Se agradece cualquier sugerencia/ayuda en los comentarios :)

Ejemplo sencillo : Si toma $f = \oplus$ entonces $g = h = \oplus$ y $u = v = id_B$ funciona.

Answer 1

Siguiendo la sugerencia de Alex en los comentarios, he aquí una prueba rápida de salvia que esta conjetura falla.

Trabajamos con $B = \{ 00, 01, 10, 11 \}$ . Escribimos $f(x,y) = x+y$ para la adición mod $4$ (de la forma obvia), y dejamos que $g(x,y) = h(x,y) = x-y$ (también calculado mod $4$ ). Entonces observe

• $g(f(x,y),x) = (x+y)-x = y$
• $h(f(x,y),y) = (x+y)-y = x$

Así que queremos saber si hay funciones $u,v : B \to B$ para que

$$f(x,y) = x+y \ \% \ 4 = u(v(x) \oplus y)$$

Nosotros podría ser inteligente al respecto y "hacer cuentas", pero sólo hay $4^4 = 256$ funciones $B \to B$ ... Así que hay $256^2$ muchos $(u,v)$ pares para probar...

B = ["00", "01", "10", "11"]

# addition mod 4
def goal(x,y):
    sum = (int(x,base=2) + int(y,base=2)) % 4
    if sum == 0: return "00"
    if sum == 1: return "01"
    if sum == 2: return "10"
    if sum == 3: return "11"

def xor(x,y):
    a = "0" if x[0] == y[0] else "1"
    b = "0" if x[1] == y[1] else "1"
    return a + b

# all functions B --> B
fns = FiniteSetMaps(B,B)

# 256 * 256 * 4 * 4 ~ 1,000,000 iterations
# this takes < 10s on my laptop
count = 0
for u in fns:
    print("u: ", count, "/256")
    count += 1
    for v in fns:
        itWorked = True
        for x in B:
            for y in B:
                if u(xor(v(x),y)) != goal(x,y):
                    itWorked = False
        if itWorked:
            print("u: ", u)
            print("v: ", v)
            break

Este código (con el que puedes jugar tú mismo en un intérprete de sage en línea, por ejemplo aquí ) nunca imprime nada más que el recuento. Así que, si confías en ella, entonces $f$ no puede escribirse como $u(v(x) \oplus y)$ para cualquier $u, v : B \to B$ . Contrariamente a la conjetura.

---

Espero que esto ayude ^_^