According to the author,

a univariate polynomial f over a field is decomposable if it is the composition f = g º h of two polynomials g and h whose degree is at least 2. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood.

Since g º h = g₁ º h₁ where g₁(x)=g(x-c) and h₁(x)=h(x)+c, we insist that h(0)=0. We also insist that f, g and h are monic. With these restrictions, in the tame case, composition is injective, that is, (g,h) ≠ (g₁,h₁) implies that g ºh ≠ g₁ º h₁ and hence the number s of decomposable polynomials of a given degree is equal to the size of the set S of eligible (g,h) pairs. In other words, s=|S|.

For a fixed degree of f, let S_k be the set of eligible pairs with k being the degree of g, and let s_k be the number of decomposable polynomials of the given degree with k being the degree of g. Clearly s_k   ≤   |S_k|. Note that it is possible in the wild case for f to be generated by elements of S_k and S_k’ with k ≠ k’: a distinct-degree collision. These are discussed in other papers by this author, while the current paper is concerned only with equal-degree collisions, when two elements of S_k generate the same f. In other words, the paper examines the reasons why s_k < |S_k|.

Decompositions where one factor is x^pd, so-called Frobenius decompositions, are treated specially. The author’s approach thereafter is unusual. He defines an algorithm (4.10) that takes f and k and returns N (N ≤ r+1 where r is the p-part of k) appropriate pairs (g,h) with f = g º h, or possibly “failure.” For good measure, he gives a complexity analysis of this algorithm. He then shows that “failure” is rare, and uses results of [1] to produce much better bounds for N, which depend on q = p^e, the size of the ground field.

The bottom line is that s_k   ≥  |S_k| (1-O(1/q)), with explicit (but complicated) values for the O(1/q) terms in various cases (theorem 6.1).