Tame decompositions and collisions. (July 2016)

• Record Type: Journal Article
• Authors: Ziegler, Konstantin
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 244
• Page End: 268
• Publication Date: 2016-07
• Subjects: 11T06 -- 12Y05 -- 68W30; Computer algebra -- Finite fields -- Tame polynomial decomposition -- Ritt's Second Theorem -- Counting special polynomials -- Combinatorics on polynomials; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.11.017
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A univariate polynomial f over a field is decomposable if 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 F q . The tame case, where the characteristic of F q does not divide n = 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 ) 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 F q of characteristic coprime to n .