The number of irreducible polynomials over GF(2)
with given trace and subtrace.

Let p(x) be a polynomial of degree n. The trace of p(x) is the coefficient of x^n-1. The subtrace of p(x) is the coefficient of x^n-2.

	(trace,subtrace)
n	(0,0)	(0,1)	(1,0)	(1,1)
1	1	0	1	0
2	0	0	0	1
3	0	1	1	0
4	1	0	1	1
5	1	2	1	2
6	2	2	3	2
7	5	4	4	5
8	6	8	8	8
9	15	13	15	13
10	24	24	24	27
11	45	48	48	45
12	85	80	85	85
13	155	160	155	160
14	288	288	297	288
15	550	541	541	550
16	1008	1024	1024	1024
17	1935	1920	1935	1920
18	3626	3626	3626	3654
19	6885	6912	6912	6885
20	13107	13056	13107	13107
21	24940	24989	24940	24989
22	47616	47616	47709	47616
23	91225	91136	91136	91225
24	174590	174760	174760	174760
25	335626	335462	335626	335462

Examples:

Further Notes:

Let L(n,k) be the number of length n binary Lyndon words of density k.

L(n,k) =

d | gcd(n,k)

µ(d)

(

n/d

k/d

)

Let S be a subset of {0,1,...,n} and let

e(S) =

k in S

L(n,k).

Column (0,0) has value e({k such that k+n = 0 (mod 4)}) is sequence A042980 in Neil J. Sloane's database of integer sequences.
Column (0,1) has value e({k such that k+n = 1 (mod 4)}) is sequence A042979 in Neil J. Sloane's database of integer sequences.
Column (1,0) has value e({k such that k+n = 2 (mod 4)}) is sequence A042981 in Neil J. Sloane's database of integer sequences.
Column (1,1) has value e({k such that k+n = 3 (mod 4)}) is sequence A042982 in Neil J. Sloane's database of integer sequences.
For proofs of these facts, see Cattell, Miers, Ruskey, Sawada, Serra, The number of irreducible polynomials over GF(2) with given trace and subtrace, Journal of Combinatorial Mathematics and Combinatorial Computing, to appear (2002).

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 2607 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.

The number of irreducible polynomials over GF(2) with given trace and subtrace.

Examples:

Further Notes:

The number of irreducible polynomials over GF(2)
with given trace and subtrace.