Tame Decompositions and Collisions
Konstantin Ziegler (B-IT cosec)
Thursday, 8 May 2014, 16:30, b-it 1.25 (cosec meeting room)
A univariate polynomial f over a field is decomposable if f = g o h = g(h) for nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials over a finite field. The tame case, where the characteristic of Fq does not divide n = deg f, is fairly well-understood, and we have reasonable bounds on the number of decomposables of degree n. Nevertheless, no exact formula is known if n has more than two prime factors. In order to count the decomposables, one wants to know, under a suitable normalization, the number of collisions, where essentially different components (g, h) yield the same f. In the tame case, Ritt's Second Theorem classifies all collisions of two such pairs.
We present a normal form for collisions of any number of decompositions with any number of components and describe exactly the (non)uniqueness of the parameters in the tame case. This yields an efficiently computable formula for the exact number of such collisions over a finite field. We conclude with an efficient algorithm for the exact number of decomposable polynomials of degree n over a finite field Fq of characteristic coprime to n.