Re: [math-fun] Characterizing polys which permute GF(p)
So Dickson worked on this problem in 1896 ! I'll have to track down his work. Thanks very much, Victor -- I thought there might be some literature on this problem, but I didn't know what to search for. I guessed correctly that other people also called them "permutation polynomials". At 06:46 PM 3/19/2016, Victor Miller wrote:
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.
The function S(x) = (x-1)^(p-1) - x^(p-1) + x in GF(p) swaps 0 and 1, and fixes the other residues. For the other group generator, either A(x) = x+1, or G(x) = gx with g a primitive root may be used. Composing these in all possible ways, while reducing mod x^p-x, generates the permutations. For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, though g must be from the extension field. The exponents in S become p^e-1, and the mod polynomial become x^p^e - x. Returning to GF[p]: If you add a third generator, L(x) = x + 1 - x^(p-1), which maps 0->1 and everything else to self, thereby losing some information, you can generate all the maps from GF[p]->GF[p]. These are 1-1 with the polynomials of degree < p. Similarly for GF[p^e]. Rich ------ Quoting Henry Baker <hbaker1@pipeline.com>:
So Dickson worked on this problem in 1896 ! I'll have to track down his work.
Thanks very much, Victor -- I thought there might be some literature on this problem, but I didn't know what to search for. I guessed correctly that other people also called them "permutation polynomials".
At 06:46 PM 3/19/2016, Victor Miller wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
More general are "exceptional polynomials" which were the subject of Dickson's thesis. A polynomial over a finite field is exceptional if it induces a one-to-one mapping on infinitely many extensions of the finite field. The following recent paper talks about classes of exceptional polynomials in characteristic 2: http://annals.math.princeton.edu/wp-content/uploads/annals-v172-n2-p12-p.pdf Victor On Sun, Mar 20, 2016 at 12:43 AM, Henry Baker <hbaker1@pipeline.com> wrote:
So Dickson worked on this problem in 1896 ! I'll have to track down his work.
Thanks very much, Victor -- I thought there might be some literature on this problem, but I didn't know what to search for. I guessed correctly that other people also called them "permutation polynomials".
At 06:46 PM 3/19/2016, Victor Miller wrote:
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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Also, these look promising: When Does a Polynomial Over a Finite Field Permute the Elements of the Field? Rudolf Lidl, Gary L. Mullen The American Mathematical Monthly Vol. 95, No. 3 (Mar., 1988), pp. 243-246 When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II Rudolf Lidl and Gary L. Mullen The American Mathematical Monthly Vol. 100, No. 1 (Jan., 1993), pp. 71-74 —Dan
On Mar 20, 2016, at 10:14 AM, Victor Miller <victorsmiller@gmail.com> wrote:
More general are "exceptional polynomials" which were the subject of Dickson's thesis. A polynomial over a finite field is exceptional if it induces a one-to-one mapping on infinitely many extensions of the finite field. The following recent paper talks about classes of exceptional polynomials in characteristic 2: http://annals.math.princeton.edu/wp-content/uploads/annals-v172-n2-p12-p.pdf
I don't have access to these papers. Are they available somewhere else, or could someone please email me a copy? Thx. At 10:43 AM 3/20/2016, Dan Asimov wrote:
Also, these look promising:
When Does a Polynomial Over a Finite Field Permute the Elements of the Field? Rudolf Lidl, Gary L. Mullen The American Mathematical Monthly Vol. 95, No. 3 (Mar., 1988), pp. 243-246
When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II Rudolf Lidl and Gary L. Mullen The American Mathematical Monthly Vol. 100, No. 1 (Jan., 1993), pp. 71-74
participants (4)
-
Dan Asimov -
Henry Baker -
rcs＠xmission.com -
Victor Miller