Tame decompositions and collisions

A univariate polynomial f   over a field is decomposable if f=g∘h=g(h)f=g∘h=g(h) with nonlinear polynomials g and h  . It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field FqFq. The tame case, where the characteristic of FqFq does not divide n=deg⁡fn=deg⁡f, is fairly well understood, and we have reasonable bounds on the number of decomposables of degree n. However, it is not known how to determine this number exactly if n   has more than two prime factors. There is an obvious inclusion–exclusion formula, but to evaluate its summands, one has to determine, under a suitable normalization, the number of collisions, where essentially different components (g,h)(g,h) yield the same f. Ritt's Second Theorem classifies all tame collisions of two such pairs.We present a normal form for tame collisions of any number of decompositions with any number of components and describe exactly the (non)uniqueness of the parameters. This yields the exact number of such collisions over a finite field. We conclude with a fast algorithm for the exact number of decomposable polynomials at degree n   over a finite field FqFq of characteristic coprime to n.