Composition collisions and projective polynomials
Joachim von zur Gathen, Mark W. Giesbrecht, Konstantin Ziegler · 2010
The functional decomposition of polynomials has been a topic of great interest and importance in pure and computer algebra and their applications. The structure of compositions of (suitably normalized) polynomials f = g o h in Fq[x] is well understood in many cases, but quite poorly when the degrees of both components are divisible by the characteristic p. This work investigates the decomposition of polynomials whose degree is a power of p. An (equal-degree) i-collision is a set of i distinct pairs (g, h) of polynomials, all with the same composition and deg g the same for all (g, h). Abhyankar (1997) introduced the projective polynomials xn+ ax + b, where n is of the form (rm -- 1)/(r -- 1) and r is a power of p. Our first tool is a bijective correspondence between i-collisions of certain additive trinomials, projective polynomials with i roots, and linear spaces with i Frobenius-invariant lines.