On the density of normal bases in finite fields
type: Item
instance of: scholarly article
title: On the density of normal bases in finite fields
zbMATH Open document ID: 0952.11029
author: Gudmund S. Frandsen
published in: Finite Fields and their Applications
publication date: 2000-08-14T00:00:00Z
review text: 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.
reviewed by: Dirk Hachenberger
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 12E20
zbMATH DE Number: 1421406
zbMATH Keywords: finite field
zbMATH Keywords: Galois field
zbMATH Keywords: normal basis
MaRDI profile type: Publication
OpenAlex ID: W2010060099
cites work: Q4888749
cites work: The distribution of values of the Euler function
cites work: A density which counts multiplicity
cites work: Some remarks on Euler’s 𝜙 function and some related problems
cites work: Density of normal elements
cites work: Q5831393
cites work: Q4044675
cites work: Q3216750
cites work: Constructing normal bases in finite fields
cites work: Solving sparse linear equations over finite fields
DOI: 10.1006/FFTA.1999.0263
description: scientific article; zbMATH DE number 1421406