Question

Given a permutation $f: \{0,1\}^n \rightarrow \{0,1\}^n$ as $n$ polynomials over $GF(2)$ how to get formulas for the inverse permutation $f^{-1}$?

I am interested in the answer to the previous question, although I would really like to know an answer to a more specific question. Let's consider a restricted permutation $g: \{0,1\}^{n-1} \rightarrow \{0,1\}^{n-1}$ that is obtained from $f(x_1, \ldots, x_n)$ if we fix any of its arguments to some constant (for example, $x_1 = 0$). How does $deg(g^{-1})$ depend on $deg(f^{-1})$ (here $deg(f)$ is a maximum over degrees of polynomials, corresponding to $f$)? My hypothesis is that $deg(g^{-1}) \ge deg(f^{-1}) - 1$ for at least one of the two values we can assign to $x_1$.

Answer 1

I very much doubt there is a formula for the inverse of a permutation. As far as degrees are concerned, I expect most permutations and their inverses to have degree $n$. A caveat here: the degree is not well-defined for functions in $GF(2)^n$ as e.g. $x=x^2$, but it is if you require all monomials to be squarefree. Then all functions can be represented by polynomials of degree at most $n$ and most of them have degree exactly $n$.

Your second question does not make sense. If $g(x_1,\ldots,x_{n-1})=f(x_1,\ldots,x_{n-1},0)$ there is no guarantee that $g(GF(2)^{n-1})$ is contained in the subspace $x_n=0$ of $GF(2)^n$ (which is where $f$ takes its values).

Edit: I just noticed that, for $n > 1$ a permutation has degree at most $n-1$, so I amend my guess to say that most permutations and their inverses have degree $n-1$.

The degree bound follows from the fact that a coordinate function of a permutation takes both values $0,1$ the same number of times and from the fact that the coefficient of $x_1 \cdots x_n$ of such a coordinate function is the sum of its values at all points of the domain.

Edit 2: (in reply to the comment below)

To compute the inverse, interpolation might be reasonable. Another way is to use the above observation on the coefficient of $x_1 \cdots x_n$. So, for instance, the coefficient of $x_2 \cdots x_n$ in a polynomial $p$ is the sum of the values of $x_1p$ which is also the sum of the values of $p$ on the points with $x_1=1$ and so on. I don't see a way to use the fact that we're dealing with permutations to improve on these methods.

As for your second question, if you assume $f$ preserves both $x_n=0$ and $x_n=1$ then I think the last coordinate of $f$ is $x_n$ and the same is true for the inverse. Then the highest degree occurs elsewhere and the inequality you want on degrees is obvious.