Actually, I still haven't been able to prove that the product of 2 perm polys can be another perm poly. The best I have so far: a quadratic *can't* be a perm poly -- or even a factor of a perm poly -- unless it has a repeated root in the field. Proof: a perm poly p(x) must have a root r in the field (p(r)=0), because some element must map to zero, but then its other factor must also be a zero in the field, which can be computed from the linear poly quotient(p(x),(x-r))=a*(x-s)*(x-r). But a perm poly can't have 2 distinct roots r,s, so r=s and p(x)=a*(x-r)^2, where a/=0. I was hoping to extend this theorem to even polynomials -- e.g., no quartic can be a perm poly, but we aren't in the reals anymore, so a quartic might still factor into a linear (which is a perm poly) and an irreducible cubic. Since the cubic is irreducible, and not a perm poly, it's ok that it has no linear factors. At 11:42 AM 3/30/2016, Warren D Smith wrote:
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).