On the factorization of iterated polynomials (Q1998690)

Let \(f(x)\) and \(g(x)\) be nonconstant polynomials over a finite field \(\mathbb{F}_q\), and suppose \(\deg g > 2\). Write \(g^{(n)}(x)\) for the \(n\)-fold composition of \(g\) with itself. In this paper, the author leverages the theory of spins, developed in [\textit{R. C. Mullin} et al., J. Comb. Math. Comb. Comput. 72, 121--143 (2010; Zbl 1211.11135)], to give upper and lower bounds on the order of growth of certain arithmetic functions related to the polynomials \(f(g^{(n)}(x))\). There are a number of arithmetic quantities related to a polynomial \(h(x)\) over \(\mathbb{F}_q\). For instance, one may be interested in the largest and smallest multiplicities of roots of \(h(x)\), or the degree of the squarefree part of \(h(x)\), or the largest and smallest degrees of irreducible factors of \(h(x)\), or the number of distinct irreducible factors of \(h(x)\), or the average degree of distinct irreducible factors of \(h(x)\). In this paper, the authors study how all of these quantities behave as \(n \to \infty\) when \(h(x) := f(g^{(n)}(x))\), generally expressing their answers in terms of the degrees of \(f\) and \(g\) (or closely related quantities), and the size of the base field \(\mathbb{F}_q\). Although some of their results may fail on ``small'' sets of polynomials, and many of them may be far from sharp, the methods employed by this paper are clear, the objects studied by this paper are natural, and the conclusions drawn by this paper are a notable improvement over the former state-of-the-art.