On the enumeration of polynomials with prescribed factorization pattern (Q2135566): Difference between revisions

The authors use generating functions over group rings to count polynomials over finite fields with the first few coefficients prescribed and a factorization pattern prescribed. They obtain different exact formulas for the number of monic \(n\)-smooth polynomial of degree \(m\) over a finite field, as well as the number of monic \(n\)-smooth polynomial of degree \(m\) with the prescribed trace coefficient. Let \(p\) and \(e\) be positive integers where \(p\) is prime. Let \({\mathbb F}_q\) be a finite field with \(q=p^e\) elements. Let \({\mathbb F}_q[x]\) denote the set of polynomials of polynomials over \({\mathbb F}_q\). Let \(M\) denote the set of monic polynomials over \({\mathbb F}_q\), and \(I\) denote the subset of these polynomials that are irreducible. For each positive integer \(d\), let \(M_d\) denote the set of degree \(d\) monic polynomials over \({\mathbb F}_q\), and let \(I_d\) be the subset of these polynomials that are irreducible. For \(f \in M\), let \(d(f)\) denote the degree of \(f\), \(r_i(f)\) denote the number of monic distinct irreducible factors of \(f\) with degree \(i\), and \(l_i(f)\) denote the number of monic degree \(i\) irreducible factors of \(f\) counting multiplicity. Put \(f(x)=x^{d(f)}+f_1x^{d(f)-1}+\dotsb+f_{d(f)}\), and set \(f_j=0\) if \(j>d(f)\). For \(f\in M\) and \(w\ge 0\), put \begin{align*} \langle f \rangle_w&=x^{d(f)}f(1/x) \pmod {x^{w+1}} =1+f_1x+\cdots+f_{w}x^{w} \pmod {x^{w+1}}. \end{align*} Let \(w\ge 0\) be a fixed integer and \(T\subset\mathbb{N}\) be a finite set. \begin{itemize} \item[1.] Define \(N(m,\prod_{i\in T}I_i^{r_i}, \langle f \rangle_w)\) as the number of monic polynomial \(g\) over \({\mathbb F}_q\) of degree \(m\) with \(\langle g \rangle_w=\langle f \rangle_w\), where \(g\) has \(r_i\) distinct monic degree \(i\) irreducible factors for each \(i\in T\). In particular, if \(m= \sum_{T} r_i\), then \(N(m,\prod_{i\in T}I_i^{r_i}, \langle f \rangle_w)\) is the number of monic polynomials over \({\mathbb F}_q\) of degree \(m\) with both the first \(w\) coefficients \(f_1,\ldots,f_w\) and a factorization pattern in terms of their degrees are prescribed. \item[2.] Define \(N^* (m,\prod_{i\in T}I_i^{l_i}, \langle f \rangle_w)\) as the number of degree \(m\) monic polynomial \(g\) over \({\mathbb F}_q\) with \(\langle g \rangle_w=\langle f \rangle_w\), where \(g\) has \(l_i\) monic degree \(i\) irreducible factors counting multiplicity for each \(i\in T\). In particular, if \(m= \sum_{T} l_i\), then \(N^*(m,\prod_{i\in T}I_i^{l_i}, \langle f \rangle_w)\) is the number of monic polynomials over \({\mathbb F}_q\) of degree \(m\) with both the first \(w\) coefficients \(f_1,\ldots,f_w\) and a factorization pattern in terms of their degrees counting multiplicity are prescribed. \end{itemize} The authors derive a general expression for \(N\) and \(N^*\) from the generating functions over group-rings for any fixed \(w\ge 0\) and any fixed \(T\subset\mathbb{N}\). These general results for \(N\) and \(N^*\) both have many corollaries that improve or recover known results. For instance, if \(w = 0\), for any monic polynomial \(f\), \(\langle f \rangle _0 = \langle 1 \rangle _0\); thus, the number of degree \(m\) monic irreducible polynomials \(g\) over \(\mathbb{F}_q\) is given by \begin{align*} I(m,\langle f \rangle_0) = N^*(m,I_m^{1}\prod_{i=1}^{m-1}I_i^0, \langle f \rangle_0), \end{align*} which gives the well-known formula \(|{I_m} | = (1/m) \sum_{k \mid m} \mu(m/k)q^k\), where \(\mu\) is the Möbius function (See [\textit{R. Lidl} and \textit{H. Niederreiter}, Finite fields. 2nd ed. Cambridge: Cambridge Univ. Press (1996; Zbl 0866.11069]) Another special case of the general problem of computing \(N\) and \(N^*\) in Definition 1, is to determine the number of monic polynomials \(f(x)\) with prescribed coefficients \(f_1, \dotsc,f_w\) and a given number of distinct linear factors, or linear factors counting multiplicity. For \(m\ge w\), \(N(m,I_1^r,\langle f \rangle_w)\) counts the number of degree \(m\) polynomials of the form \(x^m+f_1x^{m-1}+\cdots+f_wx^{m-w}+g(x)\) with \(r\) distinct linear factors, where \(f_1,\dotsc,f_w\in\mathbb{F}_q\) are fixed, and \(g(x)\in\mathbb{F}_q[x]\) is a polynomial of degree at most \(m-w-1\) that varies. This number is important due to its applications in Reed-Solomon codes. The authors also apply their results to the study of smooth polynomials. Polynomials whose irreducible factors are all of degree at most \(n\) are called \(n\)-smooth and they have applications in security. They obtain two exact formulas for the number of monic \(n\)-smooth polynomials of degree \(m\); also, they obtain two exact formulas for the number of degree \(m\) \(n\)-smooth polynomials of the form \(x^m + \alpha x^ {m-1} +g(x)\) where \(g\) is a polynomial of degree at most \(m-2\). The study of smooth polynomials have been considered by \textit{A. M. Odlyzko} [Lect. Notes Comput. Sci. 209, 224--314 (1985; Zbl 0594.94016)], \textit{R. Lovorn} [Rigourous subexponential algorithms for discrete logarithm algorithms in \(\mathbb{F}_{p^2}\). University of Georgia (PhD Thesis) (1992)], \textit{M. Car} [Acta Arith. 48, 145--165 (1987; Zbl 0575.12017)] and \textit{D. Panario} et al. [Lect. Notes Comput. Sci. 1423, 226--236 (1998; Zbl 0908.11057)]