Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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 '10 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 '10 at 18:08
2  
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 '10 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 '10 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 '10 at 1:28

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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 '10 at 10:32
    
Thanks once more! Marked your answer as accepted. –  Grigory Yaroslavtsev Mar 2 '10 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.