Talk:Permutation polynomial

The first Lemma of Higher Degree Polynomials

The first Lemma in the Higher Degree Polynomial section appears to imply that a polynomial over Z/p^kZ, k > 1 with $a_{i}=0~mod~p^{k}$ for all i > 0 and $a_{0}\neq 0~mod~p$ must be a permutation polynomial. But that can't be right, since it would be a mapping of all x to $a_{0}$ , which most certainly isn't a permutation. Is some context or other requirement for the if statement missing or unclear, or is the problem on my end? (Note: Timestamp is off because I forgot to sign it at first, this comment was made at 4:08 on June 20th, 2013) -Giematt (talk) 13:52, 20 June 2013 (UTC)[reply]

I found a source for a necessary and sufficient condition for said kind of permutation polynomial that appears to contradict what was previously there. I've replaced it for now.Giematt (talk) 02:03, 3 July 2013 (UTC)[reply]

same section, about condition g'(x) != 0 vs y² != -b/a for g(x)=ax³+bx

- shouldn't it be y² != -b/(3a) ?

- besides, Dickson_polynomials@wikipedia requires more conditions. — Preceding unsigned comment added by 194.199.26.79 (talk) 08:23, 28 March 2017 (UTC)[reply]

No. This lemma is not related to the previous statement which involved a formal derivative. Here the condition is simply that the factor

ax 2 + b

is irreducible. The reason that Dickson polynomials have more conditions is due to the fact that they are more specialized permutation polynomials (that is, they have a special form).--Bill Cherowitzo (talk) 04:01, 29 March 2017 (UTC)[reply]

- for q=17, a=3, b=1, there is no y² = -b/a , but still it is not a permutation. So I think there is a problem.

Yes, you are correct, there is a problem here. In fact, the result is false unless p = 3. The condition given is a necessary condition, but it is not sufficient. Dickson classified all cubic (in fact, everything up to degree 5) permutation polynomials over any finite field (not just the prime fields). He applied Hermite's condition to do this and the result is that cubics satisfying the necessary condition are permutation polynomials iff the characteristic of the field is 3. You could have come up with smaller counterexamples, say q = 5, a = 1 and b = 3. My apologies for not seeing this sooner. I will start working on improving the article very soon, but for right now I'll just remove the incorrect statement.--Bill Cherowitzo (talk) 17:22, 4 April 2017 (UTC)[reply]

- NB: If you plan to cleanup this article and maybe as well the one about Dickson polynomials (and appli to permutations), may I suggest this: these 2 articles are really really difficult to grasp for the non-specialist in Number Theory++ . (I have a master in Maths, a Phd, I'm a researcher close to applied maths, and still for days I went from overpuzzling to missunderstandings while trying to make polynomial-based permutations. I don't feel 100% clear yet. So I'm afraid students or potential "customers" for CS would suffer a lot here). I've explicited some implicit requirements I undestood and am sure of, but it's just an epsilon move. It would be great it you could manage to improve accessibility ! (permutations world is great and deserved to be known and understood :-) ). — Preceding unsigned comment added by Fabrice.Neyret (talk • contribs) 18:53, 4 April 2017 (UTC)[reply]

- About Z / p^k Z: according to https://eprint.iacr.org/2009/393.pdf (corrolaire 2.1) , k must be > 1. It's crucial to mention, since it would be tempting to see here a criterion to get g(x) for Z / p Z.

- More generally, it thus lack criterions to find g(x) for Z / p Z. We at least have Dickson polynomials (so maybe they should be mentioned in more details here ?) . Also, https://people.csail.mit.edu/rivest/pubs/Riv01c.pdf gives criterions for q=2^k : a_1 odd, sum_i>0{a_2i} even, sum_i>1{a_2i+1} even. — Preceding unsigned comment added by Fabrice.Neyret (talk • contribs) 17:27, 5 April 2017 (UTC)[reply]

I'll do my best and I will take a look at the Dickson polynomial page as well. My expertise has to do with PP's over fields and both of the papers you noted deal with rings which are not fields. I'd have to look them over before I could add anything but the references. I've started the rewrite, but it will be a while before I'm finished. If you could point out things that need to be expanded on that would be a great help. --Bill Cherowitzo (talk) 19:40, 5 April 2017 (UTC)--Bill Cherowitzo (talk) 19:40, 5 April 2017 (UTC)[reply]