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

Examples:

Further Notes:

Let I_q(n,1) denote the number of trace 1 monic irreducible polynomials over GF(q).

I_q(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 x^n-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 x²+x+1, are x²+ax+1 and x²+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 2930 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.