From: Henry Baker <hbaker1@pipeline.com> Permutation polynomials aren't so easy to factor -- at least not into 2 factors that are both permutations.
Suppose that a permutation poly p(x) factors into q(x)*r(x), where q(x) & r(x) are also perm polys. But p(x) must have exactly 1 root, else two distinct roots map into zero. But since q(x) and r(x) are also perm polys, they must each have a single root. If they are different, then p(x) would have two distinct roots, a contradiction. If q(x) and r(x) share the same root, then p(x) has a repeated root.
But if p(x) has a repeated root, then by the pigeonhole principle, there is some field element without a preimage via p(x), so p(x) can't be a permutation poly -- once again a contradiction. --that is where you went wrong. Scratch that reasoning! x^3 is a perm poly mod 5, & has a repeated root!
So a permutation poly can't possibly factor into two permutation polys.
--so what you really proved was, a permpoly cannot factor into two permpolys, unless all three have the same root. Without loss of generality we can demand that root be 0 (via a translation). What about the SUM of two perm polys? When can it be a permpoly? This often happens when all three are linears. For example, perms F(x) with the property that F(x)+x also is a perm, might be called "queen perms" (?) due to their use in the N-queens problem. I would like to know this: Suppose I tell you K different linear polynomials L1(x), L2(x), ..., LK(x). About how many permutations F(x) of a finite field with q elements are there, such that F(x)+Lj(x) is always a permutation as well (for each j=1,2,...,K)? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)