Compositions and collisions at degree p 2
Raoul Blankertz, Joachim von zur Gathen, Konstantin Ziegler · 2012
A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. In order to count the decomposables, one wants to know the number of equal-degree collisions of the form f = g o h = g* o h* with (g, h) ≠ (g*, h*) and deg g = deg g*. Such collisions only occur in the wild case, where the field characteristic p divides deg f. Reasonable bounds on the number of decomposables over a finite field are known, but they are less sharp in the wild case, in particular for degree p2.