The number of monic irreducible polynomials over GF(q) of given trace.

Below we use x = RootOf( z^2+z+1 ) and y = 1+x.

 GF(2) GF(3) GF(4) GF(5) (trace) n 1 0 1,2 0 1,x,y 0 1,2,3,4 0 1 1 1 1 1 1 1 1 1 2 1 0 1 1 2 0 2 2 3 1 1 3 2 5 5 8 8 4 2 1 6 6 16 12 30 30 5 3 3 16 16 51 51 125 124 6 5 4 39 38 170 160 516 516 7 9 9 104 104 585 585 2232 2232 8 16 14 270 270 2048 2016 9750 9750 9 28 28 729 726 7280 7280 43400 43400 10 51 48 1960 1960 26214 26112 195250 195248 11 93 93 5368 5368 95325 95325 887784 887784 12 170 165 14742 14736 349520 349180 4068740 4068740 13 315 315 40880 40880 1290555 1290555 18780048 18780048 14 585 576 113828 113828 4793490 4792320 87191964 87191964 15 1091 1091 318864 318848 17895679 17895679 406901000 406900992 16 2048 2032 896670 896670 67108864 67104768 1907343750 1907343750

Further Notes:

• Let Iq(n,1) denote the number of trace 1 monic irreducible polynomials over GF(q).
Iq(n,1)   =    1 qn
 __ \ / d | n
[gcd(d,q)=1]   µ(d) q n/d .

Here [P] is 1 if P is true, and is 0 if P is false. If q is the power of prime p, then the condition [gcd(d,q)=1] is equivalent to [p does not divide d].

• The trace of a degree n polynomial in x is the coefficient of xn-1. A polynomial is irreducible if it can't be factored. A polynomial is monic if the leading coefficient is 1.

• As an example, the two monic irreducible polynomials over GF(4) with trace a, where a is a root of x2+x+1, are x2+ax+1 and x2+ax+a.

• The number of polynomials of degree n over GF(q) with a given trace is the same for any non-zero value of the trace. If q is a power of the prime p, then the number with zero trace is equal to the number with any given non-zero trace if p is not a divisor of n (or n = 1).

• The number of degree n trace 1 irreducible polynomials over GF(q) is equal to the number of q-ary Lyndon words of length n whose characters sum to 1 mod q. See the page http://theory.cs.uvic.ca/inf/trs/lyn/Zq/lyn_tr_Zq.html.

• The GF(2) trace 1 entry is sequence A000048 in Neil J. Sloane's database of integer sequences.
The GF(2) trace 0 entry is sequence A051841 in Neil J. Sloane's database of integer sequences.
The GF(3) trace 0 entry is sequence A046209 in Neil J. Sloane's database of integer sequences.
The GF(3) trace 1,2 entry is sequence A046211 in Neil J. Sloane's database of integer sequences.
The GF(4) trace 0 entry is sequence A054661 in Neil J. Sloane's database of integer sequences.
The GF(4) trace 1,x,y entry is sequence A054660 in Neil J. Sloane's database of integer sequences.
The GF(5) trace 0 entry is sequence A054663 in Neil J. Sloane's database of integer sequences.
The GF(5) trace 1,2,3,4 entry is sequence A054662 in Neil J. Sloane's database of integer sequences.

• The number of irreducible polynomials with given trace were first counted by Carlitz, A theorem of Dickson on irreducible polynomials, Proc. AMS, 3 (1952) 693-700. The expression given above is from Ruskey, Miers, and Sawada, The number of irreducible polynomials and Lyndon words with a given trace, SIAM J. Discrete Mathematics, 14 (2001) 240-245.

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
Created December 13, 1999 by Frank Ruskey.
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 1840 visitors to this page since May 16, 2000 .