Character sums over Galois rings and primitive polynomials over finite fields.
Let \(\mathbb F_q\) denote the finite field of order \(q=p^k\) where \(p\) is a prime. According to the \textit{T. Hansen} and \textit{G. L. Mullen} conjecture [Math. Comput. 59, 639--643 (1992; Zbl 0770.11053)] on the existence of primitive polynomials over \(\mathbb F_q\) with a prescribed coefficient, the authors consider the following problem: For any given elements \(a_1,a_2,a_3\in\mathbb F_q\), is there a primitive polynomial \(f(x)=x^n-a_1x^{n-1}+a_2x^{n-2}-a_3x^{n-3}+\ldots+(-1)^na_n\in\mathbb F_q[x]\)? In a previous paper, the second author has answered the question affirmatively for characteristic \(p>3\) and \(n\geq 7\) provided that \(q\) is sufficiently large. The proof given there was based on an expression of the coefficients \(a_1,\ldots,a_{p-1}\) in terms of traces of powers of the polynomial's roots. In this paper, the problem is approached by translating the existence of primitive polynomials over finite fields into the existence of primitive element solutions of systems of equations over Galois rings. Character sum methods and Cohen's sieve yield a constant \(C(n)\) for every \(n\geq7\) such that there exists a primitive polynomial \(f(x)\in\mathbb F_q[x]\) of degree \(n\) with prescribed coefficients \(a_1,a_2,a_3\) whenever \(q\geq C(n)\). By a more precise analysis, \(C(n)\) is reduced to a size which allows the verification for \(n\geq 8\) and \(q<C(n)\) through direct computation. (In the case \(n=7\), the complete answer to the existence question fails because of limited computer resources.)
primitive polynomials over finite fields
scientific article; zbMATH DE number 2029208