MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Inverse for a permutation over GF(2)

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

-
@CS: Yes, I think OP means a bijective function in the usual sense. There is in fact a lot of work on this sort of thing: see e.g. en.wikipedia.org/wiki/Permutation_polynomial – Pete L. Clark Mar 1 2010 at 17:42
Pete, it seems to me that your link doesn't answer the question, because it is about one bijective polynomial over some field. What I mean is a bijective map of $n$ variables, given by $n$ polynomials $f_i(x_1, \dots, x_n)$ over $GF(2)$. – Grigory Yaroslavtsev Mar 1 2010 at 18:08
Finite Fields, by Lidl and Niederreiter (CUP). Chapter 7, section 5 defines an orthogonal system of permutation polynomials, which does exactly what you want. I haven't checked thoroughly, but a lot seems to be known about these, just like Pete said. – Sonia Balagopalan Mar 1 2010 at 19:33
@GY: Sorry, I didn't mean to claim that it did. I was responding to a (now deleted) comment of Charles Siegel, who was (apparently only very briefly) confused about the terminology. – Pete L. Clark Mar 1 2010 at 23:56
Yeah, I removed my comment when I realized what was going on and that no one had responded to it yet. Apologies if it caused any confusion. – Charles Siegel Mar 2 2010 at 1:28
show 1 more comment

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.

-
 OK, if there is no formula, is there just some general method for getting inverse? I can see only the obvious way now --- calculating some values of the inverse polynomials and then making interpolation to get them. Thank you, the second question really doesn't make sense in general. However, in case $g(GF(2)^{n-1})$ is contained in the subspace $x_n=0$ of $GF(2)^{n}$ it does. Nice observation about the degree! – Grigory Yaroslavtsev Mar 2 2010 at 10:32 Thanks once more! Marked your answer as accepted. – Grigory Yaroslavtsev Mar 2 2010 at 19:35