[math-fun] Characterizing polys which permute GF(p)
A polynomial f(x) with coefficients in GF(p) permutes p iff f(x) is 1-1 function. We call f(x) a "perm" for short. After some deep discussions with Maxima, the permutation polynomials for GF(2) are [x, x + 1], while those for GF(3) are [x, - x - 1, - x, x - 1, x + 1, - x + 1]. As expected, there are 5!=120 perm polys for GF(5), with most being of degree 3. The simplest ones are: x, 2*x, -2*x, -x, x^3, 2*x^3, -2*x^3, -x^3. I. f(x)=x is a perm. II. If f(x) is a perm, then so is f(x)+c, c=0,1,2,...,p-1. Rules I+II take care of GF(2). And the evening and the morning were the first day. III. If f(x) is a perm, then so is c*f(x), c=1,2,3,...,p-1. Rules I+II+III take care of GF(3). And the evening and the morning were the second day. IV. x^k is a perm when gcd(k,p-1)=1. Rule IV subsumes rule I. Rules II+III+IV take care of GF(5). And the evening and the morning were the third day. V. If f(x) is a perm, then so is f(f(x)), etc. Rules II+III+IV+V take care of GF(7). And the evening and the morning were the fourth day. Now, once we have rule V, we can simplify rule II: If f(x) is a perm, then so is f(x)+1. Once we have rule V, we can simplify rule III: If f(x) is a perm, then so is g*f(x), where g is a generator of the multiplicative group of GF(p). Notice that rule II permutes *all* p elements, while rule III permutes the p-1 *all but zero* elements. Conjecture: rules II-V are sufficient for *every* GF(p). ??? We still don't have a trivial way to generate permutations which map one element to itself -- e.g., 0. Note that rules III,IV,V keep 0 fixed, but I don't think that they are sufficient to perform all permutations of the p-1 non-zero elements. We also don't have a trivial way to exchange only 2 adjacent elements & leave the rest fixed. If we could do this, then the theorem is proved, because we can use rules II & III to move any 2 elements adjacent to one another.
My former colleague, Mike Zieve (now a professor at MIchigan) has written a number of papers about permutation polynomials, the latest is http://arxiv.org/pdf/1312.1325.pdf . It gives a lot of references to known results and to his previous work. Victor On Sat, Mar 19, 2016 at 8:35 PM, Henry Baker <hbaker1@pipeline.com> wrote:
A polynomial f(x) with coefficients in GF(p) permutes p iff f(x) is 1-1 function. We call f(x) a "perm" for short.
After some deep discussions with Maxima, the permutation polynomials for GF(2) are [x, x + 1], while those for GF(3) are [x, - x - 1, - x, x - 1, x + 1, - x + 1].
As expected, there are 5!=120 perm polys for GF(5), with most being of degree 3. The simplest ones are: x, 2*x, -2*x, -x, x^3, 2*x^3, -2*x^3, -x^3.
I. f(x)=x is a perm.
II. If f(x) is a perm, then so is f(x)+c, c=0,1,2,...,p-1.
Rules I+II take care of GF(2).
And the evening and the morning were the first day.
III. If f(x) is a perm, then so is c*f(x), c=1,2,3,...,p-1.
Rules I+II+III take care of GF(3).
And the evening and the morning were the second day.
IV. x^k is a perm when gcd(k,p-1)=1. Rule IV subsumes rule I.
Rules II+III+IV take care of GF(5).
And the evening and the morning were the third day.
V. If f(x) is a perm, then so is f(f(x)), etc.
Rules II+III+IV+V take care of GF(7).
And the evening and the morning were the fourth day.
Now, once we have rule V, we can simplify rule II: If f(x) is a perm, then so is f(x)+1.
Once we have rule V, we can simplify rule III: If f(x) is a perm, then so is g*f(x), where g is a generator of the multiplicative group of GF(p).
Notice that rule II permutes *all* p elements, while rule III permutes the p-1 *all but zero* elements.
Conjecture: rules II-V are sufficient for *every* GF(p). ???
We still don't have a trivial way to generate permutations which map one element to itself -- e.g., 0. Note that rules III,IV,V keep 0 fixed, but I don't think that they are sufficient to perform all permutations of the p-1 non-zero elements.
We also don't have a trivial way to exchange only 2 adjacent elements & leave the rest fixed. If we could do this, then the theorem is proved, because we can use rules II & III to move any 2 elements adjacent to one another.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Henry Baker -
Victor Miller