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 σq(n)\sigma_q(n) be the least number of nonzero coefficients of an irreducible degree-nn polynomial over Fq\mathbb F_q. Von zur Gathen–Nöcker conjecture, for n≥2n\ge2,

σ2(n)≤5,σq(n)≤4(q≥3).\sigma_2(n)\le5,\qquad \sigma_q(n)\le4\quad(q\ge3).

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 x+1x+1. The equivalent binary formulation using trinomials or pentanomials concerns degrees at least two.

References 2

A short lower-degree part

For n≥2n\ge2, define τq(n)=min⁡{deg⁡h:xn+h is irreducible over Fq, deg⁡h<n}\tau_q(n)=\min\{\deg h:x^n+h\text{ is irreducible over }\mathbb F_q,\ \deg h<n\}. A second conjecture is

τq(n)≤3+log⁡qn.\tau_q(n)\le3+\log_q n.

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 Fqn\mathbb F_{q^n}.

References 2

Irreducible binomials

There is a complete criterion for the simplest support. Let a∈Fq×a\in\mathbb F_q^\times have multiplicative order ee, and let n≥2n\ge2. Then xn−ax^n-a is irreducible over Fq\mathbb F_q if and only if every prime divisor of nn divides ee but does not divide (q−1)/e(q-1)/e, and q≡1(mod4)q\equiv1\pmod4 whenever 4∣n4\mid n.

Example

Over F5\mathbb F_5, the element 22 has order four. Hence x2k−2x^{2^k}-2 is irreducible for every k≥1k\ge1. Over F3\mathbb F_3, x4+1x^4+1 fails the congruence condition and factors as (x2+x+2)(x2+2x+2).(x^2+x+2)(x^2+2x+2).

References 1

Example

Over F2\mathbb F_2, any polynomial with an even number of nonzero coefficients vanishes at 11. Thus an irreducible polynomial of degree greater than one must have odd weight. Swan’s theorem also excludes irreducible trinomials when 8∣n8\mid n. Five terms are therefore necessary in some degrees.

For degree eight,

x8+x4+x3+x+1x^8+x^4+x^3+x+1

is irreducible over F2\mathbb F_2. Its exact Frobenius certificate is x256≡x(modf)x^{256}\equiv x\pmod f and gcd⁡(f,x16−x)=1\gcd(f,x^{16}-x)=1. The only prime divisor of eight is two, so these are precisely the required tests.

References 2

Sparse cyclotomic factors

A different problem asks whether every irreducible factor of xm−1x^m-1, or of a single cyclotomic polynomial Φm(x)\Phi_m(x), has at most three nonzero terms. For m>1m>1 with gcd⁡(m,q)=1\gcd(m,q)=1, every irreducible factor of Φm\Phi_m has degree ord⁡m(q)\operatorname{ord}_m(q). Factors of xm−1x^m-1 come from all Φd\Phi_d with d∣md\mid m. The question is which coefficients of these factors vanish.

Oliveira and Reis classified the integers mm for the xm−1x^m-1 problem over F2\mathbb F_2 and F4\mathbb F_4. 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 7∤q2−17\nmid q^2-1 alone is insufficient. For example, ord⁡49(128)=3\operatorname{ord}_{49}(128)=3, and x49−1x^{49}-1 over F128\mathbb F_{128} has an irreducible factor with four terms.

Example

Use F128=F2[η]\mathbb F_{128}=\mathbb F_2[\eta], where

η7+η5+η3+η+1=0.\eta^7+\eta^5+\eta^3+\eta+1=0.

The defining polynomial M(t)=t7+t5+t3+t+1M(t)=t^7+t^5+t^3+t+1 is irreducible: repeated squaring gives t128≡t(modM)t^{128}\equiv t\pmod M, and gcd⁡(M,t2−t)=1\gcd(M,t^2-t)=1. Now put

h(X)=X3+(η3+η)X2+(η5+η4+η)X+1.h(X)=X^3+(\eta^3+\eta)X^2+(\eta^5+\eta^4+\eta)X+1.

Reduction using the two displayed relations gives X49≡1(modh)X^{49}\equiv1\pmod h. Thus h∣X49−1h\mid X^{49}-1. Since gcd⁡(49,127)=1\gcd(49,127)=1, the only root of X49−1X^{49}-1 in F128\mathbb F_{128} is one. But h(1)=η5+η4+η3≠0h(1)=\eta^5+\eta^4+\eta^3\ne0, because η\eta has degree seven. Hence hh is a cubic with no root in the field, so it is irreducible. All four coefficients are nonzero.

References 3

A single cyclotomic polynomial

Example

Over F2\mathbb F_2, Φ15(x)=(x4+x+1)(x4+x3+1),\Phi_{15}(x)=(x^4+x+1)(x^4+x^3+1), and both factors are irreducible trinomials. But Φ5(x)=x4+x3+x2+x+1\Phi_5(x)=x^4+x^3+x^2+x+1 is irreducible because ord⁡5(2)=4\operatorname{ord}_5(2)=4. Thus every irreducible factor of Φ15\Phi_{15} is a trinomial, while x15−1x^{15}-1 has a five-term irreducible factor.

Zhu and Wu's November 2026 preprint claims a classification of the pairs (q,m)(q,m), m>1m>1, gcd⁡(m,q)=1\gcd(m,q)=1, for which every irreducible factor of Φm\Phi_m 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

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-nn polynomial over Fq\mathbb F_q is established, its Galois group over Fq\mathbb F_q is the cyclic group CnC_n. The remaining difficulty is the prescribed shape of the polynomial.

References 2

Questions

OpenFinite fields

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 σ2(n)≤5\sigma_2(n)\le5. Even weights are impossible, and degrees divisible by eight require at least five terms.

References 2
Discuss this question →
OpenFinite fields

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 σq(n)≤4\sigma_q(n)\le4. It asks for at least one irreducible polynomial in each degree, without fixing the positions or values of its coefficients.

References 2
Discuss this question →
OpenFinite fields

Can the lower-degree part always have degree at most 3+log⁡qn3+\log_q n?

Scope. Every prime power q and degree n≥2.

The question asks for an irreducible xn+hx^n+h with deg⁡h≤3+log⁡qn\deg h\le3+\log_q n. The degree bound is logarithmic; the coefficients of hh are free.

References 2
Discuss this question →
ClaimedFinite fields

When are all irreducible factors of a cyclotomic polynomial trinomials?

Scope. Prime powers qq, integers m>1m>1 with gcd⁡(m,q)=1\gcd(m,q)=1, and exactly three nonzero terms in every factor of Φm\Phi_m.

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 xm−1x^m-1 to be sparse.

References 1
Discuss this question →

Related topics

References

  1. 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
  2. Handbook of Finite Fields

    Mullen, Gary L. and Panario, Daniel (editors). CRC Press, 2013.

    Read the source
  3. Finite Fields

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

    Read the source
  4. Factorization of polynomials over finite fields

    Swan, Richard G. Pacific Journal of Mathematics, 12(3), 1099–1106, 1962.

    Read the source
  5. 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
  6. 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
  7. 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
  8. Cyclotomic polynomials with trinomial irreducible factors over finite fields

    Zhu, Li and Wu, Hongfeng. arXiv:2611.00647 [math.NT], 2026.

    Read the source