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$.



Inverse for a permutation over GF(2)
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.


