Condition on Vector Boolean Function to be Bijective

Question

Suppose the vector boolean function be

$$\begin{align} f:F^n_2 \longrightarrow F_2^n \\ (x_1,\dots ,x_n) \longrightarrow (x_2,\dots x_n,g) \\ \\ g:F^n_2 \longrightarrow F_2 \\ (x_1,\dots ,x_n) \longrightarrow \{0,1\} \end{align}$$

What should be the condition on the Boolean function $g$ so that $f$ becomes bijective i.e. 1-1 and Onto?

Answer 1

The condition is that:

$$g(0, x_2, x_3, ..., x_n) \ne g(1, x_2, x_3, ..., x_n)$$

for all $x_2, x_3, ..., x_n$

This can easily be derived from the condition that implies bijectivity of $f$; that is, $f(x_1, x_2, ..., x_n) = f(y_1, y_2, ..., y_n)$ implies that $x_1 = y_1$, $x_2 = y_2$, ..., $x_n = y_n$

Answer 2

For any fixed $x_2, \ldots, x_n$, $g$ must be a surjective function of $x_1$ (i.e. onto).