2014/02/24 by Konstantin Ziegler, Ziegler, Konstantin
Computer Science · Engineering · #11T06 #12Y05 #Coding theory and cryptography #Commutative Algebra (math.AC) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1402.5945
openalex publication_date 2014/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 p 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 (g, h) yield the same f. In the tame case, Ritt's Second Theorem classifies all 2-collisions. We introduce a normal form for multi-collisions of decompositions of arbitrary length with exact description of the (non)uniqueness of the parameters. We obtain an efficiently computable formula for the exact number of such collisions at degree n over a finite field of characteristic coprime to p. This leads to an algorithm for the exact number of decomposable polynomials at degree n over a finite field Fq in the tame case.