Overview

  • Can any one coefficient of an irreducible polynomial be prescribed?
  • How many arbitrary coefficient positions can be prescribed?
  • What changes when every coefficient is restricted to a set?
  • How do the answers depend on the field size and the degree?

The counting problem

Write f(x)=xn+an−1xn−1+⋯+a0f(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_0 over Fq\mathbb F_q, with n≥2n\ge2. The unrestricted number of monic irreducibles is Nq(n)∼qn/nN_q(n)\sim q^n/n. We now restrict the coefficients before counting. If a coefficient is prescribed, its position matters; in particular, a0=0a_0=0 forces a factor xx.

For a root α\alpha of degree nn, the first coefficient is minus its trace and the constant coefficient is (−1)n(-1)^n times its norm. General coefficient prescriptions concern elementary symmetric functions of all Frobenius conjugates.

References 2

Construction algorithms

A direct construction samples polynomials satisfying the chosen restrictions and applies the Frobenius irreducibility test. Every accepted polynomial is proved irreducible. An existence or counting theorem is needed to guarantee that the allowed set contains an irreducible polynomial, or to bound the expected number of trials.

If an extension field is already available, one can instead search for a degree-nn element with the required symmetric functions of its conjugates, then form its minimal polynomial. Trace and norm conditions are especially natural in this formulation.

References 2

Ranges of the coefficient theorems

Write f=xn+∑i=0n−1aixif=x^n+\sum_{i=0}^{n-1}a_ix^i. Prescribing values at a few positions and restricting every coefficient to a large set are different problems.

RestrictionFixed and varying parametersConclusion and exceptionsSource
One coefficient aj=ca_j=cEvery qq, n≥2n\ge2, and 0≤j<n0\le j<nExistence, except j=0,c=0j=0,c=0, or even qq with (n,j,c)=(2,1,0)(n,j,c)=(2,1,0)Tuxanidy–Wang, Theorem 1.1
Any rr prescribed positionsFixed ε>0\varepsilon>0; n→∞n\to\infty; r≤(1−ε)nr\le(1-\varepsilon)\sqrt n; uniform in qqAsymptotic count σNq(n)\sigma N_q(n), with σ\sigma defined belowPollack, Corollary 2
Any rr prescribed positionsEvery qq; n≥52n\ge52, r≤n/10r\le n/10ExistenceHa, Theorem 1.3
Any rr prescribed positionsFixed 0<ε<1/40<\varepsilon<1/4; q≥q0(ε)q\ge q_0(\varepsilon), n≥8n\ge8, r≤⌊(1/4−ε)n⌋r\le\lfloor(1/4-\varepsilon)n\rfloorExistenceHa, Corollary 1.2(2)
Each ai∈Aia_i\in A_i, with ∣Fq∖Ai∣≤q/2|\mathbb F_q\setminus A_i|\le\sqrt q/2Fixed q≥300q\ge300; n→∞n\to\infty; sets may depend on i,ni,nAsymptotic count with a separate constant-term factor; effective range belowCheng, Theorem 1.1
Coefficients independent and uniform among squares, including zeroFixed nn; q→∞q\to\inftyIrreducibility probability 1/n+On(q−1/2)1/n+O_n(q^{-1/2})Bary-Soroker–Shmueli, Theorem 1

In the Pollack and Ha rows, a prescribed constant coefficient must be nonzero. The square-coefficient estimate concerns growing field size; it gives no corresponding fixed-field, growing-degree estimate.

References 5

One prescribed coefficient

Hansen–Mullen theorem

Let n≥2n\ge2, 0≤j<n0\le j<n, and c∈Fqc\in\mathbb F_q. There is a monic irreducible polynomial of degree nn whose coefficient of xjx^j is cc, except in the following cases:

  • j=0j=0 and c=0c=0;
  • qq is even and (n,j,c)=(2,1,0)(n,j,c)=(2,1,0).

The first exception forces a root at zero. In the second, x2+ax^2+a is a square in characteristic two, because every element of a finite field of characteristic two has a square root.

Wan proved the theorem when n≥36n\ge36 or q>19q>19, and Ham and Mullen checked the remaining cases. Tuxanidy and Wang gave a later proof using periods of discrete Fourier transforms. The corresponding theorem for primitive polynomials has a different list of exceptions.

References 4

Several prescribed coefficients

Let I⊆{0,…,n−1}I\subseteq\{0,\ldots,n-1\} contain rr prescribed positions, and choose the coefficients at those positions. Assume a0≠0a_0\ne0 if 0∈I0\in I. Pollack proves, for each fixed ε>0\varepsilon>0, the uniform asymptotic formula #{f monic irreducible satisfying the prescriptions}∼σNq(n),r≤(1−ε)n,\#\{f\text{ monic irreducible satisfying the prescriptions}\}\sim\sigma N_q(n),\qquad r\le(1-\varepsilon)\sqrt n, as n→∞n\to\infty, where σ={q−r,0∉I,q1−r/(q−1),0∈I.\sigma=\begin{cases}q^{-r},&0\notin I,\\q^{1-r}/(q-1),&0\in I.\end{cases} The uniformity includes the field, positions, and prescribed values. The second normalization reflects the nonzero constant coefficient of every degree-nn irreducible.

Ha's results allow a positive proportion of positions. In particular, for every qq, if n≥52n\ge52 and r≤n/10r\le n/10, every such prescription occurs. For fixed 0<ε<1/40<\varepsilon<1/4, n≥8n\ge8, and q≥q0(ε)q\ge q_0(\varepsilon), one may prescribe ⌊(1/4−ε)n⌋\lfloor(1/4-\varepsilon)n\rfloor coefficients. The proofs use exponential sums and a function-field form of the circle method.

Example

Over F2\mathbb F_2, any six chosen coefficients of a monic polynomial of degree sixty may be prescribed, provided the constant coefficient is one if it is among them. Ha's theorem guarantees an irreducible polynomial satisfying those choices.

References 2

Allowed sets of coefficients

Now let aia_i range over an allowed set Ai⊆FqA_i\subseteq\mathbb F_q, possibly different for each position. This is different from fixing a small number of coefficients. Porritt treats one common allowed set; Cheng allows the sets to vary with the position.

A consequence of Cheng's theorem is the following. Fix q≥300q\ge300, and suppose Ai=Fq∖RiA_i=\mathbb F_q\setminus R_i with ∣Ri∣≤q/2|R_i|\le\sqrt q/2. As n→∞n\to\infty, #{f monic irreducible:ai∈Ai}=qn(q−1)∏i=0n−1∣Ai∣(∣A0∖{0}∣∣A0∣+O(q−n/45)).\#\{f\text{ monic irreducible}:a_i\in A_i\}=\frac{q}{n(q-1)}\prod_{i=0}^{n-1}|A_i|\left(\frac{|A_0\setminus\{0\}|}{|A_0|}+O(q^{-\sqrt{n/45}})\right).

For instance, requiring every nonleading coefficient to be nonzero gives the main term q(q−1)n−1/nq(q-1)^{n-1}/n. The constant coefficient enters separately because a zero there always makes a polynomial of degree at least two reducible.

Effective range

Cheng’s Theorem 1.1 gives the displayed estimate for

q≥300,n≥max⁡{140(log⁡qlog⁡δ)2,5000},δ=2q−q2 q+2q3/4.q\ge300,\qquad n\ge\max\left\{\frac1{40}\left(\frac{\log q}{\log\delta}\right)^2,5000\right\},\qquad \delta=\frac{2q-\sqrt q}{\sqrt2\,q+2q^{3/4}}.

The factor ∣A0∖{0}∣/∣A0∣|A_0\setminus\{0\}|/|A_0| equals one if zero is forbidden at the constant position, and 1−∣A0∣−11-|A_0|^{-1} otherwise.

References 2

Square coefficients

Fix n≥1n\ge1. Choose the nonleading coefficients independently and uniformly from the set Sq={a2:a∈Fq}S_q=\{a^2:a\in\mathbb F_q\}, including zero. Bary-Soroker and Shmueli prove Pr⁡(f is irreducible over Fq)=1n+On(q−1/2)(q→∞).\Pr(f\text{ is irreducible over }\mathbb F_q)=\frac1n+O_n(q^{-1/2})\qquad(q\to\infty). For odd qq, uniform sampling from SqS_q differs from squaring a uniform random element of Fq\mathbb F_q: in the latter model, zero has half the probability of each nonzero square. For even qq, Sq=FqS_q=\mathbb F_q.

Example

The squares in F5\mathbb F_5 are 0,1,40,1,4. The polynomial x2+x+1x^2+x+1 has square coefficients and is irreducible because its discriminant is 22, a nonsquare. The polynomial x2+1x^2+1 also has square coefficients, but it factors as (x−2)(x+2)(x-2)(x+2).

This theorem fixes the degree and lets the field size grow. It does not assert the same estimate for fixed qq as the degree grows. Its proof uses Galois groups of function-field extensions and finite-field point counting.

References 1

Factorization types

Counting irreducibles is one case of counting factorization types. A type records the degrees of the irreducible factors. For unrestricted polynomials, unique factorization gives exact counts; for suitable families over growing finite fields, the limiting proportions are those of permutation cycle types. See factorization statistics for the formulas and short-interval theorem.

References 2

Primitive and normal roots

Coefficient restrictions can be combined with conditions on a root. A primitive root generates Fqn×\mathbb F_{q^n}^{\times}; a normal root has conjugates forming a basis over Fq\mathbb F_q. These requirements are stronger than having degree nn. In particular, a normal root has nonzero trace, so its minimal polynomial cannot have a zero coefficient of xn−1x^{n-1}. See primitive and normal elements for tests and existence theorems.

References 2

Complete normality

Complete normality requires normality over every intermediate field. The Morgan–Mullen conjecture asks whether it can always be combined with primitivity. Published ranges and Hellwig's 2026 claimed resolution are recorded in the account of complete normality.

References 2

Questions

SettledFinite fields

Can any one coefficient be prescribed?

Scope. Every prime power qq, degree n≥2n\ge2, position 0≤j<n0\le j<n, and value c∈Fqc\in\mathbb F_q.

There is a monic irreducible polynomial of degree nn over Fq\mathbb F_q with coefficient cc at xjx^j, except when j=0,c=0j=0,c=0, or when qq is even and (n,j,c)=(2,1,0)(n,j,c)=(2,1,0). These are the only exceptions. Requiring a primitive root is a different problem with additional multiplicative conditions.

References 1
Discuss this question →
Research directionFinite fields

Which coefficient positions allow stronger bounds?

Scope. Fixed finite field, growing degree, and a specified family of prescription patterns

For a specified pattern of positions and values, one can ask for a larger proportion of prescribed coefficients, an asymptotic count, or an efficient construction. The bounds above establish sufficient ranges; they need not be optimal or the strongest known for every pattern.

References 2
Discuss this question →
Research directionFinite fields

Can degree and coefficient restrictions vary simultaneously?

Scope. A specified sequence of fields, degrees, and allowed coefficient sets

The problem depends on which of q,nq,n and the sets AiA_i vary. Cheng’s theorem allows increasing degree with large allowed sets, whereas the square-coefficient theorem fixes the degree. For a specified model, one can seek estimates uniform in both parameters or compare the ranges of these results. This formulation does not assert that every intermediate regime is open.

References 2
Discuss this question →

Related topics

References

  1. Finite Fields

    Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.

    Read the source
  2. A new proof of the Hansen–Mullen irreducibility conjecture

    Tuxanidy, Aleksandr and Wang, Qiang. Canadian Journal of Mathematics, 70(6), 1373–1389, 2018.

    Read the source
  3. Probabilistic algorithms in finite fields

    Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.

    Read the source
  4. Irreducible polynomials with several prescribed coefficients

    Pollack, Paul. Finite Fields and Their Applications, 22, 70–78, 2013.

    Read the source
  5. Irreducible polynomials with several prescribed coefficients

    Ha, Junsoo. Finite Fields and Their Applications, 40, 10–25, 2016.

    Read the source
  6. Counting irreducible polynomials with restricted coefficients

    Cheng, Kaimin. Finite Fields and Their Applications, 108, Article 102691, 2025.

    Read the source
  7. Irreducibility of polynomials with square coefficients over finite fields

    Bary-Soroker, Lior and Shmueli, Roy. Finite Fields and Their Applications, 109, Article 102714, 2026.

    Read the source
  8. Generators and irreducible polynomials over finite fields

    Wan, Daqing. Mathematics of Computation, 66(219), 1195–1212, 1997.

    Read the source
  9. Distribution of irreducible polynomials of small degrees over finite fields

    Ham, Kie H. and Mullen, Gary L. Mathematics of Computation, 67(221), 337–341, 1998.

    Read the source
  10. The Hansen-Mullen primitivity conjecture: completion of proof

    Cohen, Stephen D. and Prešern, Mateja. Number Theory and Polynomials, Cambridge University Press, London Mathematical Society Lecture Note Series, 352, 89–120, 2008.

    Read the source
  11. Irreducible polynomials over a finite field with restricted coefficients

    Porritt, Sam. Canadian Mathematical Bulletin, 62, 429–439, 2019.

    Read the source
  12. The distribution of polynomials over finite fields

    Cohen, Stephen D. Acta Arithmetica, 17(3), 255–271, 1970.

    Read the source
  13. Prime polynomials in short intervals and in arithmetic progressions

    Bank, Efrat and Bary-Soroker, Lior and Rosenzweig, Lior. Duke Mathematical Journal, 164(2), 277–295, 2015.

    Read the source
  14. Primitive normal bases for finite fields

    Lenstra, Hendrik W., Jr. and Schoof, René J. Mathematics of Computation, 48(177), 217–231, 1987.

    Read the source
  15. Completely normal primitive basis generators of finite fields

    Morgan, Ilene H. and Mullen, Gary L. Utilitas Mathematica, 49, 21–43, 1996.

    Read the source
  16. Resolvent Components of Completely Normal Elements and the Morgan-Mullen Conjecture

    Hellwig, Florian. arXiv:2610.36534 [math.NT], 2026.

    Read the source