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 over , with . The unrestricted number of monic irreducibles is . We now restrict the coefficients before counting. If a coefficient is prescribed, its position matters; in particular, forces a factor .
For a root of degree , the first coefficient is minus its trace and the constant coefficient is times its norm. General coefficient prescriptions concern elementary symmetric functions of all Frobenius conjugates.
References 2
- LidlNiederreiter1997 · Trace, norm, and irreducible polynomialsSource
- TuxanidyWang2018 · §1Source
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- 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
- Rabin1980Source
- LidlNiederreiter1997 · Minimal polynomials, trace and normSource
Ranges of the coefficient theorems
Write . Prescribing values at a few positions and restricting every coefficient to a large set are different problems.
| Restriction | Fixed and varying parameters | Conclusion and exceptions | Source |
|---|---|---|---|
| One coefficient | Every , , and | Existence, except , or even with | Tuxanidy–Wang, Theorem 1.1 |
| Any prescribed positions | Fixed ; ; ; uniform in | Asymptotic count , with defined below | Pollack, Corollary 2 |
| Any prescribed positions | Every ; , | Existence | Ha, Theorem 1.3 |
| Any prescribed positions | Fixed ; , , | Existence | Ha, Corollary 1.2(2) |
| Each , with | Fixed ; ; sets may depend on | Asymptotic count with a separate constant-term factor; effective range below | Cheng, Theorem 1.1 |
| Coefficients independent and uniform among squares, including zero | Fixed ; | Irreducibility probability | 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
- TuxanidyWang2018 · Theorem 1.1Source
- Pollack2013Prescribed · Theorem 1 and Corollary 2Source
- Ha2016 · Corollary 1.2(2) and Theorem 1.3Source
- Cheng2025Restricted · Theorem 1.1Source
- BarySorokerShmueli2026Squares · Theorem 1Source
One prescribed coefficient
Hansen–Mullen theorem
Let , , and . There is a monic irreducible polynomial of degree whose coefficient of is , except in the following cases:
- and ;
- is even and .
The first exception forces a root at zero. In the second, 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 or , 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
- Wan1997Source
- HamMullen1998Source
- TuxanidyWang2018 · Theorem 1.1Source
- CohenPresern2008Primitive · Primitive-polynomial counterpartSource
Several prescribed coefficients
Let contain prescribed positions, and choose the coefficients at those positions. Assume if . Pollack proves, for each fixed , the uniform asymptotic formula as , where The uniformity includes the field, positions, and prescribed values. The second normalization reflects the nonzero constant coefficient of every degree- irreducible.
Ha's results allow a positive proportion of positions. In particular, for every , if and , every such prescription occurs. For fixed , , and , one may prescribe coefficients. The proofs use exponential sums and a function-field form of the circle method.
Example
Over , 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
- Pollack2013Prescribed · Theorem 1 and Corollary 2Source
- Ha2016 · Corollary 1.2(2) and Theorem 1.3Source
Allowed sets of coefficients
Now let range over an allowed set , 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 , and suppose with . As ,
For instance, requiring every nonleading coefficient to be nonzero gives the main term . 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
The factor equals one if zero is forbidden at the constant position, and otherwise.
References 2
- Porritt2019Restricted · Theorem 1.1Source
- Cheng2025Restricted · Theorem 1.1 and Corollary 1.3Source
Square coefficients
Fix . Choose the nonleading coefficients independently and uniformly from the set , including zero. Bary-Soroker and Shmueli prove For odd , uniform sampling from differs from squaring a uniform random element of : in the latter model, zero has half the probability of each nonzero square. For even , .
Example
The squares in are . The polynomial has square coefficients and is irreducible because its discriminant is , a nonsquare. The polynomial also has square coefficients, but it factors as .
This theorem fixes the degree and lets the field size grow. It does not assert the same estimate for fixed as the degree grows. Its proof uses Galois groups of function-field extensions and finite-field point counting.
References 1
- BarySorokerShmueli2026Squares · Theorem 1; Theorem 2 and §§3–5Source
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
- Cohen1970Source
- BankBarySorokerRosenzweig2015 · Theorem 2.3Source
Primitive and normal roots
Coefficient restrictions can be combined with conditions on a root. A primitive root generates ; a normal root has conjugates forming a basis over . These requirements are stronger than having degree . In particular, a normal root has nonzero trace, so its minimal polynomial cannot have a zero coefficient of . See primitive and normal elements for tests and existence theorems.
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
- MorganMullen1996CompletelyNormalSource
- Hellwig2026MorganMullen · arXiv:2610.36534v1, Theorem 1.2Source
Questions
Can any one coefficient be prescribed?
Scope. Every prime power , degree , position , and value .
There is a monic irreducible polynomial of degree over with coefficient at , except when , or when is even and . These are the only exceptions. Requiring a primitive root is a different problem with additional multiplicative conditions.
References 1
- TuxanidyWang2018 · Theorem 1.1Source
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
- Ha2016 · Theorem 1.1 and Corollary 1.2Source
- Pollack2013Prescribed · Corollary 2Source
Can degree and coefficient restrictions vary simultaneously?
Scope. A specified sequence of fields, degrees, and allowed coefficient sets
The problem depends on which of and the sets 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
- Cheng2025Restricted · Theorem 1.1Source
- BarySorokerShmueli2026Squares · Theorems 1–2Source
Related topics
Finite fields and Frobenius
Trace and norm explain the first and constant coefficients.
UsesIrreducibility over finite fields
Certify a polynomial found by a construction or search.
UsesPrimitive and normal elements
Add multiplicative and normal-basis conditions.
UsesFactorization statistics over finite fields
Extend irreducibility counts to all factorization types.
UsesSparse irreducible polynomials over finite fields
Prescribing most coefficients to zero leads to sparse polynomials.
References
- Finite Fields
Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.
Read the source - 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 - Probabilistic algorithms in finite fields
Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.
Read the source - Irreducible polynomials with several prescribed coefficients
Pollack, Paul. Finite Fields and Their Applications, 22, 70–78, 2013.
Read the source - Irreducible polynomials with several prescribed coefficients
Ha, Junsoo. Finite Fields and Their Applications, 40, 10–25, 2016.
Read the source - Counting irreducible polynomials with restricted coefficients
Cheng, Kaimin. Finite Fields and Their Applications, 108, Article 102691, 2025.
Read the source - 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 - Generators and irreducible polynomials over finite fields
Wan, Daqing. Mathematics of Computation, 66(219), 1195–1212, 1997.
Read the source - 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 - 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 - Irreducible polynomials over a finite field with restricted coefficients
Porritt, Sam. Canadian Mathematical Bulletin, 62, 429–439, 2019.
Read the source - The distribution of polynomials over finite fields
Cohen, Stephen D. Acta Arithmetica, 17(3), 255–271, 1970.
Read the source - 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 - 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 - Completely normal primitive basis generators of finite fields
Morgan, Ilene H. and Mullen, Gary L. Utilitas Mathematica, 49, 21–43, 1996.
Read the source - Resolvent Components of Completely Normal Elements and the Morgan-Mullen Conjecture
Hellwig, Florian. arXiv:2610.36534 [math.NT], 2026.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.