Overview
- Does every degree admit an irreducible polynomial with few nonzero terms?
- How short can the lower-degree part of an irreducible polynomial be?
- Which obstructions exclude binary trinomials?
- When are the irreducible factors of a cyclotomic polynomial sparse?
Few nonzero coefficients
Let be the least number of nonzero coefficients of an irreducible degree- polynomial over . Von zur Gathen–Nöcker conjecture, for ,
These are existence statements: the support and coefficients may depend on the degree. They do not assert irreducibility for every polynomial of small weight.
The bounds also hold trivially in degree one, for example using . The equivalent binary formulation using trinomials or pentanomials concerns degrees at least two.
References 2
- GathenNocker2005 · Conjecture 2.5, author-hosted text p. 6Source
- MullenPanario2013 · Conjectures 3.4.30–3.4.31; §11.1.1.2Source
A short lower-degree part
For , define . A second conjecture is
The authors call these polynomials sedimentary. This condition bounds the positions of all nonleading terms, whereas sparsity bounds their number. Both forms allow fast reduction in a polynomial basis of .
References 2
- GathenNocker2005 · Conjecture 2.8, author-hosted text p. 7Source
- MullenPanario2013 · Conjecture 3.4.35 and Conjecture 11.1.20Source
Irreducible binomials
There is a complete criterion for the simplest support. Let have multiplicative order , and let . Then is irreducible over if and only if every prime divisor of divides but does not divide , and whenever .
Example
Over , the element has order four. Hence is irreducible for every . Over , fails the congruence condition and factors as
References 1
- LidlNiederreiter1997 · Theorem 3.75, irreducible binomialsSource
Example
Over , any polynomial with an even number of nonzero coefficients vanishes at . Thus an irreducible polynomial of degree greater than one must have odd weight. Swan’s theorem also excludes irreducible trinomials when . Five terms are therefore necessary in some degrees.
For degree eight,
is irreducible over . Its exact Frobenius certificate is and . The only prime divisor of eight is two, so these are precisely the required tests.
References 2
- Swan1962Obstruction for binary trinomials in degrees divisible by eight.Source
- MullenPanario2013 · Example 11.1.19Source
Sparse cyclotomic factors
A different problem asks whether every irreducible factor of , or of a single cyclotomic polynomial , has at most three nonzero terms. For with , every irreducible factor of has degree . Factors of come from all with . The question is which coefficients of these factors vanish.
Oliveira and Reis classified the integers for the problem over and . Cheng's characteristic-two extension has a published corrigendum and a corrected author version. The correction requires control of orders modulo powers of seven; the earlier implication from alone is insufficient. For example, , and over has an irreducible factor with four terms.
Example
Use , where
The defining polynomial is irreducible: repeated squaring gives , and . Now put
Reduction using the two displayed relations gives . Thus . Since , the only root of in is one. But , because has degree seven. Hence is a cubic with no root in the field, so it is irreducible. All four coefficients are nonzero.
References 3
- OliveiraReis2021Sparse · Abstract and the binary-field classificationSource
- Cheng2026SparseCharacteristicTwo · Theorem 1.3; use the corrigendum and corrected author versionSource
- Cheng2026SparseCorrigendum · Correction to Theorem 1.3; arXiv:2507.10779v2, Proposition 3.4 and Example 5.2Source
A single cyclotomic polynomial
Example
Over , and both factors are irreducible trinomials. But is irreducible because . Thus every irreducible factor of is a trinomial, while has a five-term irreducible factor.
Zhu and Wu's November 2026 preprint claims a classification of the pairs , , , for which every irreducible factor of has exactly three nonzero terms. It reduces the supports by power substitutions and then studies root orders. This is a preprint result about individual cyclotomic polynomials; it does not settle the bounded-weight conjecture for every degree.
References 2
- ZhuWu2026CyclotomicTrinomials · arXiv:2611.00647v2, Theorems 1.1 and 1.3; §§1–2Source
- LidlNiederreiter1997 · Theorem 2.47; the example follows by multiplication and Frobenius ordersSource
What the conjectures assert
The bounded-weight and short-tail conjectures above are recorded in von zur Gathen–Nöcker and the Handbook of Finite Fields. Their universal statements remain listed as open here; no resolution was verified in this review. A calculation proves existence only for the field and degree checked.
Once irreducibility of a degree- polynomial over is established, its Galois group over is the cyclic group . The remaining difficulty is the prescribed shape of the polynomial.
References 2
- GathenNocker2005 · Conjectures 2.5 and 2.8Source
- MullenPanario2013 · Conjectures 3.4.30–3.4.31 and 3.4.35Source
Questions
Does every binary degree admit an irreducible trinomial or pentanomial?
Scope. Every degree n≥2 over F_2; the support may depend on n.
The conjecture is . Even weights are impossible, and degrees divisible by eight require at least five terms.
References 2
- GathenNocker2005 · Conjecture 2.5Source
- MullenPanario2013 · Conjecture 3.4.30Source
Do four nonzero terms suffice over every finite field with more than two elements?
Scope. Every prime power q≥3 and degree n≥2.
The assertion is . It asks for at least one irreducible polynomial in each degree, without fixing the positions or values of its coefficients.
References 2
- GathenNocker2005 · Conjecture 2.5Source
- MullenPanario2013 · Conjecture 3.4.31Source
Can the lower-degree part always have degree at most ?
Scope. Every prime power q and degree n≥2.
The question asks for an irreducible with . The degree bound is logarithmic; the coefficients of are free.
References 2
- GathenNocker2005 · Conjecture 2.8Source
- MullenPanario2013 · Conjecture 3.4.35Source
When are all irreducible factors of a cyclotomic polynomial trinomials?
Scope. Prime powers , integers with , and exactly three nonzero terms in every factor of .
Zhu and Wu claim a complete classification in arXiv:2611.00647v2 (November 2026). The condition concerns a single cyclotomic polynomial; it is stronger than asking for one sparse irreducible of its degree, and different from requiring all factors of to be sparse.
References 1
- ZhuWu2026CyclotomicTrinomials · Theorems 1.1 and 1.3Source
Related topics
Finite fields and Frobenius
Root orders determine degrees of cyclotomic factors.
UsesIrreducibility over finite fields
Check sparse candidates by exact Frobenius tests.
UsesIrreducible polynomials with coefficient restrictions
Compare sparse support with arbitrary coefficient prescriptions.
UsesPrimitive and normal elements
Sparse polynomial bases and normal bases serve different computations.
UsesSparse polynomials and factor reversal
Compare sparse polynomials over finite fields with sparse polynomials in characteristic zero.
References
- Polynomial and Normal Bases for Finite Fields
von zur Gathen, Joachim and Nöcker, Michael. Journal of Cryptology, 18(4), 337–355, 2005.
Read the source - Handbook of Finite Fields
Mullen, Gary L. and Panario, Daniel (editors). CRC Press, 2013.
Read the source - Finite Fields
Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.
Read the source - Factorization of polynomials over finite fields
Swan, Richard G. Pacific Journal of Mathematics, 12(3), 1099–1106, 1962.
Read the source - On polynomials x^n − 1 over binary fields whose irreducible factors are binomials and trinomials
Oliveira, Daniela and Reis, Lucas. Finite Fields and Their Applications, 73, 101837, 2021.
Read the source - The 3-sparsity of X^n − 1 over finite fields of characteristic 2
Cheng, Kaimin. Transactions of the London Mathematical Society, 13(1), e70026, 2026.
Read the source - Corrigendum: The 3-sparsity of X^n − 1 over finite fields of characteristic 2
Cheng, Kaimin. Transactions of the London Mathematical Society, 13(1), e70035, 2026.
Read the source - Cyclotomic polynomials with trinomial irreducible factors over finite fields
Zhu, Li and Wu, Hongfeng. arXiv:2611.00647 [math.NT], 2026.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.