{'fraction_non_alphanumeric': 0.05352584103931469, 'fraction_numerical': 0.019770806149656775, 'mean_word_length': 4.027092542421218, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Survey on counting special types of polynomials

Most integers are composite and most univariate polynomials over a finite field are reducible. The Prime Number Theorem and a classical result of Gau{\ss} count the remaining ones, approximately and exactly. For polynomials in two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. This survey presents counting results for some special classes of multivariate polynomials over a finite field, namely the the reducible ones, the s-powerful ones (divisible by the s-th power of a nonconstant polynomial), the relatively irreducible ones (irreducible but reducible over an extension field), the decomposable ones, and also for reducible space curves. These come as exact formulas and as approximations with relative errors that essentially decrease exponentially in the input size. Furthermore, a univariate polynomial f is decomposable if f = g o h for some nonlinear polynomials g and h. It is intuitively clear that the decomposable polynomials form a small minority among all polynomials. The tame case, where the characteristic p of Fq does not divide n = deg f, is fairly well-understood, and we obtain closely matching upper and lower bounds on the number of decomposable polynomials. In the wild case, where p does divide n, the bounds are less satisfactory, in particular when p is the smallest prime divisor of n and divides n exactly twice. The crux of the matter is to count the number of collisions, where essentially different (g, h) yield the same f. We present a classification of all collisions at degree n = p^2 which yields an exact count of those decomposable polynomials.


Introduction
Most integers are composite and most univariate polynomials over a finite field are reducible. The classical results of the Prime Number Theorem and a theorem of Gauß present approximations saying that randomly chosen integers up to x or polynomials of degree up to n are prime or irreducible with probability about 1/ ln x or 1/n, respectively.
Concerning special classes of univariate polynomials over a finite field, Zsigmondy (1894) counts those with a given number of distinct roots or without irreducible factors of a given degree. In the same situation, Artin (1924) counts the irreducible ones in an arithmetic progression and Hayes (1965) generalizes these results. Cohen (1969) and Car (1987) count polynomials with certain factorization patterns and Williams (1969) those with irreducible factors of given degree. Polynomials that occur as a norm in field extensions are studied by Gogia & Luthar (1981).
In two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. Carlitz (1963) provides the first count of irreducible multivariate polynomials. In Carlitz (1965), he goes on to study the fraction of irreducibles when bounds on the degrees in each variable are prescribed; see also Cohen (1968). In this survey, we opt for bounding the total degree because it has the charm of being invariant under invertible linear transformations. Gao & Lauder (2002) consider the counting problem in yet another model, namely where one variable occurs with maximal degree. The natural generating function (or zeta function) for the irreducible polynomials in two or more variables does not converge anywhere outside of the origin. Wan (1992) notes that this explains the lack of a simple combinatorial formula for the number of irreducible polynomials. But he gives a p-adic formula, and also a (somewhat complicated) combinatorial formula. For further references, see Mullen & Panario (2013, Section 3.6).
In the bivariate case, von zur Gathen (2008) proves precise approximations with an exponentially decreasing relative error. Von zur Gathen, Viola & Ziegler (2013) extend those results to multivariate polynomials and give further information such as exact formulas and generating functions. Bodin (2008) gives a recursive formula for the number of irreducible bivariate polynomials and remarks on a generalization for more than two variables; he follows up with Bodin (2010).
We present exact formulas for the numbers of reducible (Sections 2.1-2.3), s-powerful (Section 2.4), and relatively irreducible polynomials (Section 2.5). The formulas also yield simple, yet precise, approximations to these numbers, with rapidly decaying relative errors.
Geometrically, a single polynomial corresponds to a hypersurface, that is, to a cycle in affine or projective space of codimension 1. This correspondence preserves the respective notions of reducibility. Thus, Sections 2.1-2.3 can also be viewed as counting reducible hypersurfaces, in particular, planar curves, and Section 2.4 those with an s-fold component. From a geometric perspective, these results say that almost all hypersurfaces are irreducible. Can we say something similar for other types of varieties? Cesaratto, von zur Gathen & Matera (2013) give an affirmative answer for curves in P r for arbitrary r. A first question is how to parametrize the curves. Moduli spaces only include irreducible curves, and systems of defining equations do not work except for complete intersections. The natural parametrization is by the Chow variety C r,n of curves of degree n in P r , for some fixed r and n. The foundation of this approach is a result by Eisenbud & Harris (1992), who identified the irreducible components of C r,n of maximal dimension. We present the counting results in Section 2.6.
It is intuitively clear that the decomposable polynomials form a small minority among all multivariate polynomials over a field. Von zur Gathen (2011) gives a quantitative version of this intuition (see Section 2.7). The number of multivariate decomposable polynomials is also studied by Bodin, Dèbes & Najib (2009).
This concludes the first half (Section 2) of our survey, dealing with multivariate polynomials. The second half (Section 3) is devoted to counting univariate decomposable polynomials.
Some of the results in this survey are from joint work with Raoul Blankertz, Eda Cesaratto, Mark Giesbrecht, Guillermo Matera, and Alfredo Viola.
A version of this paper is to appear in Gutierrez, Schicho & Weimann (2014). The final publication will be available at Springer after publication.

Counting multivariate polynomials
We work in the polynomial ring F [x 1 , . . . , x r ] in r ≥ 1 variables over a field F and consider polynomials with total degree equal to some nonnegative integer n: The polynomials of degree at most n form an F -vector space of dimension r+n r . The property of a certain polynomial to be reducible, squareful, relatively irreducible, or decomposable is shared with all polynomials associated to the given one. For counting them, it is sufficient to take one representative. We choose an arbitrary monomial order, say, the degree-lexicographic one, so that the monic polynomials are those with leading coefficient 1, and write P r,n (F ) = {f ∈ P all r,n (F ) : f is monic}.
We use two different methodologies to obtain such bounds: generating functions and combinatorial counting. The usual approach, see Flajolet & Sedgewick (2009), of analytic combinatorics on series with integer coefficients leads, in our case, to power series that diverge everywhere (except at 0). We have not found a way to make this work. Instead, we use power series with symbolic coefficients, namely rational functions in a variable representing the field size. Several useful relations from standard analytic combinatorics carry over to this new scenario. In a first step, this yields in a straightforward manner an exact formula for the number under consideration (Theorem 2.5). This formula is, however, not very transparent. Even the leading term is not immediately visible.
In a second step, coefficient comparisons yield easy-to-use approximations to our number (Theorem 2.7). The relative error is exponentially decreasing in the bit size of the data. Thus, Theorem 2.7 gives a "third order" approximation for the number of reducible polynomials, and thus a "fourth order" approximation for the irreducible ones. The error term is in the big-Oh form and thus contains an unspecified constant.
In a third step, a different method, namely some combinatorial counting, yields "second order" approximations with explicit constants in the error term (Theorem 2.9).

Exact formula for reducible polynomials
To study reducible polynomials, we consider the following subsets of P r,n (F ): In the usual notions, the polynomial 1 is neither reducible nor irreducible. In our context, it is natural to have R r,0 (F ) = {1} and I r,0 (F ) = ∅.
The sets of polynomials are combinatorial classes with the total degree as size functions and we denote the corresponding generating functions by P r , I r , R r ∈ Z ≥0 z , respectively. Their coefficients are respectively, dropping the finite field F q with q elements from the notation. By definition, P r equals the disjoint union of R r and I r , and therefore R r = P r − I r .
By unique factorization, every element in P r corresponds to an unordered finite sequence of elements in I r , where repetition is allowed, and therefore by Flajolet & Sedgewick (2009, Theorem I.5), where µ is the number-theoretic Möbius-function. A resulting algorithm is easy to program and returns exact results with lightning speed. This approach quickly leads to explicit formulas. A composition of a positive integer n is a sequence j = (j 1 , j 2 , . . . , j |j| ) of positive integers j 1 , j 2 , . . . , j |j| with j 1 + j 2 + · · · + j |j| = n, where |j| denotes the length of the sequence. We define the set M n = {compositions of n}. (2.4) This standard combinatorial notion is not to be confused with the composition of polynomials, which we discuss in Sections 2.7 and 3.
Theorem 2.5 (Exact counting). Let r ≥ 1, q ≥ 2, P r,n as in (2.1), and I r,n the number of irreducible monic r-variate polynomials of degree n over F q . Then we have for n ≥ 1, and therefore for the number R r,n of reducible monic r-variate polynomials of degree n over F q R r,0 = 1, for n ≥ 1.
The formula of Theorem 2.5 is exact but somewhat cumbersome. The following two sections provide simple yet precise approximations, with rapidly decaying error terms.

Symbolic approximation for reducible polynomials
For r ≥ 2, the power series P r , I r , and R r do not converge anywhere except at 0, and the standard asymptotic arguments of analytic combinatorics are inapplicable. We now deviate from this approach and move from power series in Q z to power series in Q(q) z , where q is a symbolic variable representing the field size. For r ≥ 2 and n ≥ 0 we let in analogy to (2.1). We define the power series P r , I r , R r ∈ Q(q) z by Then R r,n (q) denotes the coefficient of z n in R r and counts symbolically the reducible monic r-variate polynomials of degree n.
For nonzero f ∈ Q(q), deg q f is the degree of f , that is, the numerator degree minus the denominator degree. The appearance of O(q −m ) with a positive integer m in an equation means the existence of some f with degree at most −m that makes the equation valid. If a term O(q −m ) appears, then we may conclude a numerical asymptotic result for growing prime powers q.

Explicit bounds for reducible polynomials
The third approach by "combinatorial counting" is somewhat more involved. The payoff of this additional effort is an explicit relative error bound. However, the calculations are sufficiently complicated for us to stop at the first error term. Thus we replace the asymptotic 1+O(q −r(r−1)/2 ) in (2.8) by 1/(1−q −1 ).
Theorem 2.9 (Explicit approximation). Let r, q ≥ 2, and ρ r,n as in Theorem 2.7. For the number #R r,n (F q ) of reducible monic r-variate polynomials of degree n over F q we have Remark 2.10. How close is our relative error estimate to being exponentially decaying in the input size? The usual dense representation of a polynomial in r variables and of degree n requires b r,n = r+n r monomials, each of them equipped with a coefficient from F q , using about log 2 q bits. Thus the total input size is about log 2 q · b r,n bits. This differs from log 2 q · (b r−1,n−1 − b r−1,2 ) by a factor of Up to this polynomial difference (in the exponent), the relative error is exponentially decaying in the bit size of the input, that is, (log q) times the number of coefficients in the usual dense representation. In particular, it is exponentially decaying in any of the parameters r, n, and log 2 q, when the other two are fixed.

Powerful polynomials
For an integer s ≥ 2, a polynomial is called s-powerful if it is divisible by the sth power of some nonconstant polynomial, and s-powerfree otherwise; it is As in the previous section, we restrict our attention to a finite field F = F q , which we omit from the notation. For the approach by generating functions, we consider the combinatorial classes Q r,s = n≥0 Q r,n,s and S r,s = P r Q r,s . Any monic polynomial f factors uniquely as f = g · h s where g is a monic s-powerfree polynomial and h an arbitrary monic polynomial, hence and by definition Q r,s = P r − S r,s for the generating functions of S r,s and Q r,s , respectively. For univariate polynomials, Carlitz (1932) To study the asymptotic behavior of Q r,n,s for r ≥ 2 we again deviate from the standard approach and move to power series in Q(q) z . With P r from (2.6), we define S r,s , Q r,s ∈ Q(q) z by The approach by generating functions now yields the following result. Its "general" case is (iv). We give exact expressions in special cases, namely for n < 3s in (ii) and for (n, s) = (6, 2) in (iii), which also apply when we substitute the size q of a finite field F q for q. Theorem 2.14 (Symbolic approximation). Let r, s ≥ 2, n ≥ 0, and Then the symbolic formula Q r,n,s (q) for the number of s-powerful monic r-variate polynomials of degree n over F q satisfies the following.
Theorem 2.17 (Explicit approximation). Let r, s, q ≥ 2, #Q r,n,s (F q ) the number of s-powerful monic r-variate polynomials of degree n over F q , and η r,n,s and δ as in Theorem 2.14.
(i) For (n, s) = (6, 2), we have δ = r(r + 1)(r 2 + 9r + 2)/24 and As noted in Remark 2.10 for reducible polynomials, the relative error term is (essentially) exponentially decreasing in the input size, and exponentially decaying in any of the parameters r, n, s, and log 2 q, when the other three are fixed.

Relatively irreducible polynomials
A polynomial over F is absolutely irreducible if it is irreducible over an algebraic closure of F , and relatively irreducible (or exceptional) if it is irreducible over F but factors over some extension field of F . We define As before, we restrict ourselves to finite fields and recall that all our polynomials are monic. We relate the generating function A r (F q ) of #A r,n (F q ) to the generating function I r (F q ) of irreducible polynomials as introduced in Section 2.1 and obtain with Möbius inversion. For an explicit formula, we combine the expression for I r,n (F q ) from Theorem 2.5 with (2.18).
Theorem 2.19 (Exact counting). For r, n ≥ 1, q ≥ 2, M n as in (2.4), P r,n as in (2.1), and I r,n as in (2.2), we have for the number E r,n of relatively irreducible monic r-variate polynomials of degree n over F q The approach by generating functions gives the following result.
Theorem 2.20 (Symbolic approximation). Let r, n ≥ 2, let be the smallest prime divisor of n, and Then the symbolic formula E r,n (q) for the number of relatively irreducible monic r-variate polynomials of degree n over F q satisfies the following.
While (i) and (ii) yield explicit bounds, the combinatorial approach does this for (iii).
Theorem 2.21 (Explicit approximation). Let r, q ≥ 2, and r,n and κ as in Theorem 2.20, and n be composite. Then for the number #E r,n (F q ) of relatively irreducible monic r-variate polynomials of degree n over F q we have |#E r,n (F q ) − r,n (q)| ≤ r,n (q) · 3q −κ .

Reducible space curves
The Chow variety of curves of degree n in the r-dimensional projective space P r = P r (F q ) over an algebraic closure F q is denoted by C r,n . Each point of the Chow variety C r,n actually corresponds to a unique effective cycle in P r of dimension 1 and degree n, that is, to a formal linear combination a i C i , where each C i is an irreducible curve in P r , each a i is a positive integer and Let C r,n (F q ) denote the Chow variety of effective F q -cycles and R * r,n (F q ) its closed subvariety of F q -reducible F q -cycles. Methods of algebraic geometry yield the following bounds on the probability that a random curve of degree n in P r (F q ) is F q -reducible.
Theorem 2.22. Let r ≥ 3 and g r,n = r + n − 2 n 2 · r + n − 1 (r − 1)(n + 1) , where e denotes the basis of the natural logarithm. For the number #R * r,n (F q ) of F q -reducible cycles of degree n we have the following.
We call an F q -reducible cycle absolutely reducible. An F q -cycle can be absolutely reducible for two reasons: either it is F q -reducible, as treated above, or relatively F q -irreducible, that is, is F q -irreducible and F q -reducible. The set of relatively F q -irreducible (or exceptional) F q -curves of degree n in P r is denoted by E * r,n (F q ). Theorem 2.23. Let r ≥ 3, n ≥ 4r −8, let denote the smallest prime divisor of n, and b r,n = 3(r − 2) + n(n + 3)/2, d ,n,r = (en/ ) r(r+1)(n 2 / 2 +1)+4rg r,n/ .
For the number #E * r,n (F q ) of relatively F q -irreducible cycles of degree n we have

Decomposable polynomials
For monic univariate g ∈ F [y] and h ∈ P r,n , we define their composition If deg g ≥ 2 and deg h ≥ 1, then (g, h) is a decomposition of f . A polynomial f ∈ P r,n is decomposable if there exist such g and h. There are other notions of decompositions. The present one is called uni-multivariate in von zur Gathen, Gutierrez & Rubio (2003). Another one is studied in Faugère & Perret (2008) for cryptanalytic purposes. In the context of univariate polynomials deg h ≥ 2 is also required, see Section 3.
It is sufficient to concentrate on polynomials with vanishing constant term, see subsection 3.1, and we denote by D r,n (F ) the set of all decomposable polynomials f ∈ P r,n (F ) with f (0, . . . , 0) = 0.
Theorem 2.24. Let F q be a finite field with q elements, r ≥ 2, and the smallest prime divisor of the composite integer n ≥ 2. Let m = n if r = 2, n/ is prime, and n/ ≤ 2 − 5, otherwise, Then for the number #D r,n (F q ) of decomposable monic r-variate polynomials with vanishing constant term of degree n over F q we have |#D r,n (F q ) − α r,n | ≤ α r,n · β r,n .

Counting univariate decomposable polynomials
The composition of two univariate polynomials g, h ∈ F [x] over a field F is denoted as f = g • h = g(h), and then (g, h) is a decomposition of f , and f is decomposable if g and h have degree at least 2. In the 1920s, Ritt, Fatou, and Julia studied structural properties of these decompositions over C, using analytic methods. Particularly important are two theorems by Ritt on the uniqueness, in a suitable sense, of decompositions, the first one for (many) indecomposable components and the second one for two components, as above. Engstrom (1941) and Levi (1942) proved them over arbitrary fields of characteristic zero using algebraic methods. The theory was extended to arbitrary characteristic by Fried & MacRae (1969), Dorey & Whaples (1974), Schinzel (1982Schinzel ( , 2000, Zannier (1993), and others. Its use in a cryptographic context was suggested by Cade (1985). In computer algebra, the decomposition method of Barton & Zippel (1985) requires exponential time. A fundamental dichotomy is between the tame case, where the characteristic p does not divide deg g, and the wild case, where p divides deg g, see von zur Gathen (1990a,b). (Schinzel (2000), § 1.5, uses tame in a different sense.) A breakthrough result of Kozen & Landau (1989) was their polynomial-time algorithm to compute tame decompositions; see also von zur Gathen, Kozen & Landau (1987); Kozen, Landau & Zippel (1996); Gutierrez & Sevilla (2006), and the survey articles of von zur Gathen (2002) and Gutierrez & Kozen (2003) with further references. Schur's conjecture, as proven by Turnwald (1995), offers a natural connection between the tame indecomposable polynomials in this section and certain absolutely irreducible bivariate polynomials, as studied in Section 2.5. More precisely, a tame polynomial f is indecomposable if (f (x) − f (y))/(x − y) is absolutely irreducible. Aside from natural exceptions, the converse is also true.
In the wild case, considerably less is known, both mathematically and computationally. Zippel (1991) suggests that the block decompositions of Landau & Miller (1985) for determining subfields of algebraic number fields can be applied to decomposing rational functions even in the wild case. A version of Zippel's algorithm in Blankertz (2014) computes in polynomial time all decompositions of a polynomial that are minimal in a certain sense. Avanzi & Zannier (2003) study ambiguities in the decomposition of rational functions over C. On a different but related topic, Zieve & Müller (2008) found interesting characterizations for Ritt's First Theorem, which deals with complete decompositions, where all components are indecomposable.
We have seen fairly precise estimates for the number of multivariate decomposable polynomials in Section 2.7. It is intuitively clear that the univariate decomposable polynomials also form only a small minority among all univariate polynomials over a field, and this second part of our survey confirms this intuition. The task is to approximate the number of decomposables over a finite field, together with a good relative error bound. One readily obtains an upper bound. The challenge then is to find an essentially matching lower bound.
A set of distinct decompositions of f is called a collision. The number of decomposable polynomials of degree n is thus the number of all pairs (g, h) with deg g · deg h = n reduced by the ambiguities introduced by collisions. An important tool for estimating the number of collisions is Ritt's Second Theorem. The first algebraic versions of this in positive characteristic p required p > deg(g • h). Zannier (1993) reduced this to the milder and more natural requirement g = 0 for all g in the collision. His proof works over an algebraic closed field, and Schinzel's 2000 monograph adapts it to finite fields.
In Section 3.2, we provide a precise quantitative version of Ritt's Second Theorem, by determining exactly the number of such collisions in the tame case, assuming that p n/ , where n is the degree of the composition and is the smallest prime divisor of n. This is based on a unique normal form for the polynomials occurring in Ritt's Second Theorem. Giesbrecht (1988) was the first to consider this counting problem. He showed that the decomposable polynomials form an exponentially small fraction of all univariate polynomials. General approximations to the number of univariate decomposable polynomials are shown in Section 3.3. They come with satisfactory (rapidly decreasing) relative error bounds except when p divides n = deg f exactly twice. Ziegler (2014) provides an exact count of tame univariate polynomials. In Section 3.4, we determine exactly the number of decomposable polynomials in one of the difficult wild cases, namely when n = p 2 .
Zannier (2008) studies a different but related question, namely compo- with a sparse polynomial f , having t terms. The degree is not bounded. He gives bounds, depending only on t, on the degree of g and the number of terms in h. Furthermore, he gives a parametrization of all such f , g, h in terms of varieties (for the coefficients) and lattices (for the exponents). Bodin, Dèbes & Najib (2009) also deal with counting.

Notation
A nonzero polynomial f ∈ F [x] over a field F of characteristic p ≥ 0 is monic if its leading coefficient lc(f ) equals 1. We call f original if its graph contains the origin, that is, Multiplication by a unit or addition of a constant does not change decomposability, since for all f , g, h as above and a, b ∈ F with a = 0. In other words, the set of decomposable polynomials is invariant under this action of Furthermore, any decomposition (g, h) can be normalized by this action, by taking a = lc ( , and h * = ah + b. Then g • h = g * • h * and g * and h * are monic original.
It is therefore sufficient to consider compositions f = g • h where all three polynomials are monic original. In such a tame decomposition, g and h are uniquely determined by f and deg g. For n ≥ 1 and any proper divisor e of n, we write Thus P n (F ) and D n (F ) are the subsets of original polynomials in the sets P 1,n (F ) and D 1,n (F ), respectively, as defined in the context of multivariate polynomials (subsection 2.7) but with right component h of degree at least 2. We sometimes leave out F from the notation when it is clear from the context and have over a finite field F q with q elements #P n = q n−1 , #D n,e ≤ q e+n/e−2 .
The set D n of all decomposable polynomials in P n satisfies In particular, D n = ∅ if n is prime and x ∈ P 1 is neither decomposable nor indecomposable. For the resulting inclusion-exclusion formula for #D n , we have to determine the collisions (or nonuniqueness) of decompositions, that is, It is useful to single out a special case of wild compositions when p > 0.
Example 3.2. We call an f ∈ P n ∩ F [x p ] a Frobenius composition, since then f = g * • x p for some g * ∈ P n/p , and any decomposition (g, h) of f = g • h is a Frobenius decomposition. We denote by ϕ : F −→ F the Frobenius endomorphism over a field F of characteristic p, with ϕ(a) = a p for all a ∈ F , and extend it to an F p -linear map ϕ : P n −→ P n with ϕ(x) = x. For h ∈ P n/p {x p }, this provides the collision If F is perfect -in particular if F is finite or algebraically closed -then ϕ is an automorphism on F and every Frobenius composition except x p 2 is a collision as in (3.3). Over F = F q , this yields q p−1 − 1 collisions in D p 2 and q n/p−1 collisions in D n for p | n = p 2 , called Frobenius collisions. This example is noted in Schinzel (1982, Section I.5, page 39).
For f ∈ P n (F ) and a ∈ F , the original shift of f by a is Original shifting defines a group action of the additive group of F on P n (F

Normal form for Ritt's Second Theorem
Ritt presented two types of essential collisions: where w ∈ F [x], z ∈ F × = F {0}, and T m is the mth Dickson polynomial of the first kind. And then he proved that these are all possibilities up to composition with linear polynomials. This involved four unspecified linear functions, and it is not clear whether there is a relation between the first and the second type of example. Von zur Gathen (2014b) presents a normal form for the decompositions in Ritt's Theorem under Zannier's assumption g (g * ) = 0 and the standard assumption gcd( , m) = 1, where m = k + deg w in (3.4). This normal form is unique unless p | m.
Theorem 3.5 (Ritt's Second Theorem, normal form). Let F be a field of characteristic p ≥ 0, let m > ≥ 2 be integers with gcd( , m) = 1 and n = m.

(i) (First Case) There exists a monic polynomial w ∈ F [x] of degree s and
where m = s + k is the division with remainder of m by , with 1 ≤ k < . Furthermore, we have
(iii) When ≥ 3, the First and Second Cases are mutually exclusive. For = 2, the Second Case is included in the First Case.
If p n, then the case where gcd( , m) = 1 is reduced to the previous one by a result of Tortrat (1988). This determines D n, ∩ D n,m exactly if p n = m.
Theorem 3.14 (Tame case). Let F q be a finite field of characteristic p, let δ denote Kronecker's delta function, and let m > ≥ 2 be integers with p n = m, i = gcd( , m) and s = m/ . For the number of monic original polynomials of degree n over F q with left components of degree and m we have ≤ q 2 +s−3 otherwise.
In the remaining case where p | n, the Frobenius collisions are easily counted and therefore excluded. We have the following upper bounds. (ii) If p | and < m, we set b = (m − + 1)/ . Then For perspective, we also note the following lower bounds on c from von zur Gathen (2013Gathen ( , 2014a. Unlike the exact result of Theorem 3.14, there is a substantial gap between the upper and lower bounds.

The number of decomposable univariate polynomials
The basic statement is that α n as in (3.18) is an approximation to the number of monic original decomposable polynomials of degree n, with relative error bounds of varying quality. The following is a condensed version of the more precise bounds in von zur Gathen (2014a).
Theorem 3.17. Let F q be a finite field with q elements and characteristic p, let be the smallest prime divisor of the composite integer n ≥ 2, and Then the following hold for the number #D n (F q ) of decomposable monic original polynomials of degree n over F q , where p n means that p divides n exactly twice.
The relative error in (v) is exponentially decreasing in the input size n log q, in the tame case and for growing n/3 2 . In (iv), the factor is 1 + O(q −1 ) over F q . When p = n, then we have a factor of about 2 in (ii), which is improved to about 4/3 in (iii). The case n = p 2 is settled in subsection 3.4.
Beyond the previous precise bounds, without asymptotics or unspecified constants, we now derive some conclusions about the asymptotic behavior. There are two parameters: the field size q and the degree n. When n is prime, then #D n (F q ) = 0, and prime values of n are excepted in the following. We consider the asymptotics in one parameter, where the other one is fixed, and also the special situations where gcd(q, n) = 1. Furthermore, we denote as "q, n −→ ∞" any infinite sequence of pairwise distinct (q, n). The cases n = 4 and p 2 n = p 2 for some prime p are the only ones where our methods do not show that #D n (F q )/α n −→ 1.
Theorem 3.19. Let #D n (F q ) be the number of decomposable monic original polynomials of degree n over F q , α n as in (3.18), and ν q,n = #D n (F q )/α n . We only consider composite n. ≤ ν q,n for any n, (ii) Let n be a composite integer and its smallest prime divisor. Then if 2 n and n = 2 , = 1 otherwise.

Collisions at degree p 2
The previous section gives satisfactory estimates for the number of decomposable polynomials at degree n unless p 2 n. The material of this section determines the number in the easiest of these open cases, namely for n = p 2 . First, we present two classes of explicit collisions at degree r 2 , where r is a power of the characteristic p > 0 of the field F . The collisions of Fact 3.20 consist of additive and subadditive polynomials. A polynomial A of degree r k is r-additive if it is of the form A = 0≤i≤k a i x r i with all a i ∈ F . We call a polynomial additive if it is p-additive. A polynomial is additive if and only if it acts additively on an algebraic closure F of F , that is A(a + b) = A(a) + A(b) for all a, b ∈ F ; see Goss (1996, Corollary 1.1.6). The composition of additive polynomials is additive, see for instance Proposition 1.1.2 of the cited book.
The decomposition structure of additive polynomials was first studied by Ore (1933). Dorey & Whaples (1974, Theorem 4) show that all components of an additive polynomial are additive. Giesbrecht (1988) gives lower bounds on the number of decompositions and algorithms to determine them.
For a divisor m of r − 1, the (r, m)-subadditive polynomial associated with the r-additive polynomial A is S = x( 0≤i≤k a i x (r i −1)/m ) m of degree r k . Then A and S are related as x m • A = S • x m . Dickson (1897) notes a special case of subadditive polynomials, and Cohen (1985) is concerned with the reducibility of some related polynomials. Cohen (1990a,b) investigates their connection to exceptional polynomials and coins the term "sub-linearized"; see also Cohen & Matthews (1994). Coulter, Havas & Henderson (2004) derive the number of indecomposable subadditive polynomials and present an algorithm to decompose subadditive polynomials.
Ore ( (u, s, ε, m) (3.21) For each t ∈ T and The polynomials f in (3.21) are "simply original" in the sense that they have a simple root at 0. This motivates the designation S. The second construction of collisions goes as follows.
m an integer with 1 < m < r − 1 and p m, m * = r − m, and (3.23) The polynomials f in (3.23) are "multiply original" in the sense that they have a multiple root at 0. This motivates the designation M . The notation is set up so that * acts as an involution on our data, leaving b, f , r, and x invariant. Zieve (2011) points out that the rational functions of case (4) in Proposition 5.6 of Avanzi & Zannier (2003) can be transformed into (3.23). Zieve also mentions that this example already occurs in unpublished work of his, joint with Robert Beals. In particular, the collisions in case (S) and case (M) have exactly #T and 2 distinct decompositions, respectively. Inclusion-exclusion now yields the following exact formula for the number of decomposable polynomials of degree p 2 over F q .
Theorem 3.25. Let F q be a finite field of characteristic p, δ Kronecker's delta function, and τ the number of positive divisors of p − 1. Then for the number #D p 2 (F q ) of decomposable monic original polynomials of degree p 2 over F q we have #D p 2 (F q ) = q 2p−2 − q p−1 + 1 − (τ q − q + 1)(q − 1)(qp − p − 2) 2(p + 1) In particular, we have #D 4 (F q ) = q 2 · 2 + q −2 3 for p = 2, We have two independent parameters p and d, and q = p d . For two eventually positive functions f, g : N 2 → R, here g ∈ O(f ) means that there are constants b and c so that g(p, d) ≤ c · f (p, d) for all p and d with p + d ≥ b. We have the following asymptotics.
Corollary 3.26. Let p ≥ 5, d ≥ 1, q = p d , and k ≥ 1. Then the number c k of decomposable monic original polynomials of degree p 2 over F q with exactly k decompositions is as follows Theorem 3.25 leads to lim q→∞ ν q, 2 = 1 for any prime > 2 in Theorem 3.19 (ii). For n = 4, the sequence has no limit, but oscillates between values close to lim inf q→∞ ν q,4 = 2/3 and to lim sup q→∞ ν q,4 = 1, and these are the only two accumulation points of the sequence ν q,4 .

Open problems
Further types of multivariate polynomials that are examined from a counting perspective include singular bivariate ones (von zur Gathen, 2008) and pairs of coprime polynomials (Hou & Mullen, 2009). It remains open to extend the methods of Section 2 to singular multivariate ones and achieve exponentially decreasing error bounds for coprime multivariate polynomials.
For univariate decomposable polynomials, the question of good asymptotics for ν q,n when q is fixed and n → ∞ is still open. More work is needed to understand the case where the characteristic p is the smallest prime divisor of the degree n, divides n exactly twice, and n = p 2 . Ritt's Second Theorem covers distinct-degree collisions, even in the wild case, see Zannier (1993); it would be interesting to see a parametrization even for p | m and obtain a similar classification for general equal-degree collisions.
Finally, this survey deals with polynomials only and the study of rational functions with the same methods remains open.