A conjecture about binary functions on binary strings with partial inverses

Question

Given a positive integer $n$ we denote $B = \{0,1\}^n$. I conjecture that for any $f:B^2\to B$,

If there exists $g,h:B^2\to B$ s.t. for all $x,y$ in $B$, $g(f(x,y),x)=y$ and $h(f(x,y),y)=x$, then there exists $u,v:B\to B$ s.t. $f = (x,y)\mapsto u(v(x)\oplus y)$.

Note: $\oplus$ denote the bitwise xor.

A bit of context: I was trying to prove the noisy channel coding theorem in a different way than the classical ones using AEP or the error exponents and this would fill the last gap but I am a bit stuck with it and also maybe a bit tired/lazy (I am neither a student nor mathematician). It may very well be wrong but then a counterexample would be interesting. Any hint/help in comments appreciated. :)

Simple example: If you take $f = \oplus$ then $g = h = \oplus$ and $u = v = id_B$ works.

Answer 1

Following Alex's hint in the comments, here's a quick proof by sage that this conjecture fails.

We work with $B = \{ 00, 01, 10, 11 \}$. We write $f(x,y) = x+y$ for addition mod $4$ (in the obvious way), and we let $g(x,y) = h(x,y) = x-y$ (also computed mod $4$). Then notice

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

So we want to know if there are functions $u,v : B \to B$ so that

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

We could be smart about this, and "do math", but there are only $4^4 = 256$ functions $B \to B$... So there are $256^2$ many $(u,v)$ pairs to try...

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

This code (which you can play with yourself in an online sage interpreter, for instance here) never prints anything but the count. So, if you trust it, then $f$ cannot be written as $u(v(x) \oplus y)$ for any $u, v : B \to B$. Contrary to the conjecture.

---

I hope this helps ^_^