Re: [math-fun] Characterizing polys which permute GF(p)
RCS: The function S(x) = (x-1)^(p-1) - x^(p-1) + x in GF(p) swaps 0 and 1, and fixes the other residues. WDS: Verify directly for 0 and 1; use Lagrange theorem that x^(p-1)=1 if x>0 for all other x mod p. Check. RCS: 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. WDS: correct: x+1 is the p-cycle, and the 01 swap is then all you need to generate every permutation. The reduction modulo x^p-x causes the reduced polynomial to have degree<p. RCS: For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, WDS: this cyclic-multiplicative-group fact is a theorem by E.Galois. Proofs are available in 1 Andre Weil: Basic number theory, on page 2, can read this page online here http://www.amazon.com/Basic-Number-Theory-Classics-Mathematics/dp/3540586555 2 J-P. Serre: A course in arithmetic, 3 Loo-Keng Hua: Introduction to number theory However: A. I disagree with RCS: though g must be from the extension field. Actually, g is a plain old field element, and Weil proves that. B. And the loop is among the q-1 NONZERO elements of GF(q), where q=p^e, not ALL elements like for x+1 if q prime. So it really is "a single loop plus an isolani." However, using S(x-K) rather than S(x) swaps K and K+1. Therefore, we can by composing S(x-K) and g*x in all possible ways reducing modulo x^p-x as RCS says, generate all permutations of the nonzero elements of GF(q). We then can also swap 0 with 1 using S(x)... which enables seeing that all permutations of the whole kaboodle, are accessible. RCS: The exponents in S become p^e-1, and the mod polynomial becomes 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]. WDS: it was anyhow obvious that the polynomials of degree<q generate all maps if GF(q) to self, by use of Lagrange interpolation. It seems to me this whole short post by RCS, is brilliantly simple, and (after my slight corrections) totally characterizes and constructs all permutation polynomials over all finite fields. However, there still is this criticism: what if I want the perm polynomials which work REGARDLESS of the value of q? RCS's generation method sort of handles each GF(q) by itself, it does not handle all of them in a unified way. So for example, the fact that x^k is a permutation polynomial in GF(q) if GCD(k,q-1)=1, which is fairly obvious from Galois' theorem, is not so obvious from RCS's construction (is it?). Is there a way to overcome this criticism? And by the way, to mention the obvious, see https://en.wikipedia.org/wiki/Permutation_polynomial which also gives the following beautiful characterization of the perm polynomials over the ring Z mod p^e: F(x) is a perm polynomial if and only if 1. it permutes Z mod p, and 2. F'(x) is nonzero for every ring element x. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Could it be, that some other "nice" set of polynomials generates the full perm group, but while RCS's set involved p-1 in exponents, the nice set is defined with, say, only bounded degrees. Then you could do everything RCS does, but using that generator set instead, and then you'd overcome the Criticism. Dickson found all perm polynomials of degree<=5 in finite fields; when are they enough to generate? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Correction: When I'd said "However, using S(x-K) rather than S(x) swaps K and K+1." I should have said S(x-K)+K.
[quibble^2] Quoting Warren D Smith <warren.wds@gmail.com>: [moby clippage -- rich]
RCS: For the other group generator, either A(x) = x+1, or G(x) = gx with g a primitive root may be used. WDS: [clip, not relevant to my quibble^2] RCS: For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, WDS: [clip] However: A. I disagree with RCS: though g must be from the extension field. Actually, g is a plain old field element, and Weil proves that.
Minor quibble: The map f(x)->2x (mod 5) is a loop (+ a singleton fixed point x=0), but in GF[25] it's several loops. Multipliers from the ground field GF[5] aren't primitive roots in GF[25]. Many of the other elements in GF[25] are primitive roots.
B. And the loop is among the q-1 NONZERO elements of GF(q), where q=p^e, not ALL elements like for x+1 if q prime. So it really is "a single loop plus an isolani."
This is true. My calling G a single loop is inaccurate in neglecting the fixed point. However, the two generators S=(01) and G=(1,g,...) DO generate the full permutation group (when loop G includes everything except 0): The permutation SG is a full length loop, inserting 0 into the G loop between 1 and g: SG = (1,0,g,g2,...,1/g).
WDS: it was anyhow obvious that the polynomials of degree<q generate all maps if GF(q) to self, by use of Lagrange interpolation.
"obvious" is in the eye of the beholder.
However, there still is this criticism: what if I want the perm polynomials which work REGARDLESS of the value of q? RCS's generation method sort of handles each GF(q) by itself, it does not handle all of them in a unified way. So for example, the fact that x^k is a permutation polynomial in GF(q) if GCD(k,q-1)=1, which is fairly obvious from Galois' theorem, is not so obvious from RCS's construction (is it?). Is there a way to overcome this criticism?
I'd like to see this too. It seems unlikely for non-linear polynomials: (all mod P): We require F(x)/=F(y) unless x=y. But F(x+1)-F(x) will be another polynomial G of lower degree. If we choose a random n, and let P be any prime dividing G(n) = F(n+1)-F(n), then F(x) mod P isn't a permutation, because F(n)=F(n+1) mod P. The patched-reciprocal R(x) = {1/x, except R(0)=0} is a permutation, so probably all the (ax+b)/(cx+d) are too, with a similar patch, and excluding p|ad-bc. Rich
The original question plus (ax+b)/(cx+d)brings up the question: Which rational functions over GF(n) (n = prime power) are permutations of GF(n) ? —Dan ———— P.S. Is there any way to define an infinite power series over a finite field, or some kind of completion of it?
On Mar 20, 2016, at 12:36 PM, rcs@xmission.com wrote:
The patched-reciprocal R(x) = {1/x, except R(0)=0} is a permutation, so probably all the (ax+b)/(cx+d) are too, with a similar patch, and excluding p|ad-bc.
participants (3)
-
Dan Asimov -
rcs＠xmission.com -
Warren D Smith