On the density of normal bases in finite fields (Q1971063)

For a prime power \(q>1\) let \({F}_q\) be the Galois field with \(q\) elements and for a polynomial \(f \in {F}_q[x]\) let \(\Phi_q(f)\) denote the number of polynomials \(g \in {F}_q[x]\) such that \(\deg(g) <\deg(f)\) and \(\text{gcd}(g,f)=1\). The author proves that \(\Phi_q(f) \geq q^n/({e\lceil {{log}}_qn \rceil})\) for any polynomial \(f \in {F}_q[x]\) of degree \(n\geq 2\) such that \(f(0)\not= 0\). This result is comparable with previous results on the number of units in the ring \({F}_q[x]/(f)\) [see, e.g., \textit{S. Gao} and \textit{D. Panario} [Finite Fields Appl. 3, 141-150 (1997; Zbl 0922.11100)]. The case \(f=x^n-1\) (for some \(n\)) is of particular interest, because \(\Phi_q(x^n-1)\) is equal to the number of elements \(\alpha \in {F}_{q^n}\) which generate a normal basis for \({F}_{q^n}\) over \({F}_q\), i.e., for which \(\{ \alpha, \alpha^q,\dots, \alpha^{q^{n-1}} \}\) is an \({F}_q\)-basis of \({F}_{q^n}\). Thus, the frequency \(\nu_q(n):=\Phi_q(x^n-1)/q^n\) of normal elements satisfies \(\nu_q(n) \geq 1/(e\lceil \log_qn \rceil)\) for all \(n,q \geq 2\). The author also achieves the following bound on the density of normal elements, which is asymptotically stronger: there exists a constant \(c_1\) such that \(\nu_q(n) \geq 0.28477/\sqrt{\log_qn}\) for all \(q \geq 2\) and all \(n \geq q^{c_1}\). Furthermore, by considering extensions of degree of the form \(n_k:=\text{lcm}_{d=1}^k(q^d-1)\) the author shows that for every prime power \(q\) one has \(\nu_q(n) < 0.61910 /\sqrt{\log_qn}\) for infinitely many \(n\). For small \(q\) the latter improves a bound of Gao and Panario by a constant factor.