How to find two functions $f,g :\mathbb Z_2^n\to \mathbb Z_2^n$ such that $f(x)+f(y) $ and $g(x)+g(y)$ determines $\{x,y\}$ uniquely

Question

The following problem bothers me for some days, I could not clear out my mind to get a satisfying answer:

How to find two functions $f,g :\mathbb Z_2^n\to \mathbb Z_2^n$ such that given $f(x)+f(y) $ and $g(x)+g(y)$ , we can find the two distinct elements $x,y\in \mathbb Z_2^n$ .

My attempt : ( I did not find the right approach to the problem yet)

The first thing I did is assuming that we can take $f=Id_{Z_2^n}$ (the identity function on $\mathbb Z_2^n$) , and the problem is equivalent to finding $g$ subject to $g(x+a)+g(x)=b$ having one or two solutions , but again I could not find any function that will do.

So I feel like I am missing something important here? do you have any ideas/ hints for me?

thank you.

Edit

First here is the original problem :

It'is a game between two preople, Person $A$ choses two different elements $x,y$ in $\mathbb Z_2^n$ . The person $B$ does not know $x$ nor $y$ but he can ask $A$ one question of the form " what is the value of $f_1(x)+f_1(y), ...,f_k(x)+f_k(y)$?" for some functions $f_1, f_2, ... f_k$, and $A$ is constraint to answer this question in the form $a_1,..., a_k$. How many functions should $B$ use to find $\{x,y\}$?

My conjecture is that $2$ questions are enaugh, and that's what I try to prove without much success.

The conjecture is supported by the fact that, the number of values of $\{x,y\}$ is $2^{2n-1}-2^{n-1}$ and the pair $(f(x)+f(y),g(x)+g(y))$ can take up to $(2^n-1)^2$ values for $n\geq 3$

---

Notation :

• $\mathbb Z_2$ denotes the quotient ring of the ring of integers modulo the ideal of even numbers, alternatively denoted by ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$
• $\mathbb Z_2^n $ means the vector space of lenght $n$ over $\mathbb Z_2.$
• The functions $f$ and $g$ are not supposed to be linear or whatso ever, all maps are allowed

Answer 1

Put a field structure on $\Bbb Z_2^n$, then pick $f(x)=x$ and $g(x)=x^3$.

If $x \neq y$ and you know $x+y = a ( \neq 0)$ and $x^3+y^3 = b$, then $b = (x+y)(x^2+xy+y^2) = a(a^2+xy)$, so that you know $axy = b+a^3$.

Then $x,y$ are the two roots of $a(T+x)(T+y) = aT^2+a^2T+(b+a^3)$.

This doesn't give you an easy way to actually find $x$ and $y$, but it is a proof that the map $(x,y) \mapsto (x+y,x^3+y^3)$ is $2$-to-$1$ away from the diagonal.