The number of irreducible polynomials over GF(4)
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.

Below we use a = RootOf( x^2+x+1 ) and b = 1+a.

	(trace,subtrace)
n	(0,0)	(0,1) (0,a) (0,b)	(1,0) (a,0) (b,0)	(1,1) (a,b) (b,a)	(1,a) (1,b) (a,1) (a,a) (b,1) (b,b)
1	1	0	1	0	0
2	0	0	0	0	1
3	2	1	1	2	1
4	0	4	4	4	4
5	15	12	15	12	12
6	40	40	40	40	45
7	153	144	144	153	144
8	480	512	512	512	512
9	1841	1813	1841	1813	1813
10	6528	6528	6528	6528	6579
11	23901	23808	23808	23901	23808
12	87040	87380	87380	87380	87380
13	322875	322560	322875	322560	322560
14	1198080	1198080	1198080	1198080	1198665
15	4474738	4473647	4473647	4474738	4473647
16	16773120	16777216	16777216	16777216	16777216

Examples:

Monic irreducible polynomials over GF(4) of degree n = 2. Let r = RootOf( x^2+x+a ). Then r⁴ = r+1.

1,a	x²+x+a = (x+r)(x+r+1)
1,b	x²+x+b = (x+r+a)(x+r+b)
a,1	x²+ax+1 = (x+ar)(x+ar+a)
a,a	x²+ax+a = (x+ar+1)(x+ar+b)
b,1	x²+bx+1 = (x+br+1)(x+br+a)
b,b	x²+bx+b = (x+br)(x+br+b)

Monic irreducible polynomials over GF(4) of degree n = 3.

0,0	x^3+a	x^3+b
0,1	x^3+x+1
0,a	x^3+ax+1
0,b	x^3+bx+1
1,0	x^3+x^2+1
1,1	x^3+x^2+x+a	x^3+x^2+x+b
1,a	x^3+x^2+ax+b
1,b	x^3+x^2+bx+a
a,0	x^3+ax^2+1
a,1	x^3+ax^2+x+b
a,a	x^3+ax^2+ax+a
a,b	x^3+ax^2+bx+a	x^3+ax^2+bx+b
b,0	x^3+bx^2+1
b,1	x^3+bx^2+x+a
b,a	x^3+bx^2+ax+a	x^3+bx^2+ax+b
b,b	x^3+bx^2+bx+b

Further Notes:

Column (0,0) is sequence A074031 in Neil J. Sloane's database of integer sequences.
Column (0,1),(0,a),(0,b) is sequence A074032 in Neil J. Sloane's database of integer sequences.
Column (1,0),(a,0),(b,0) is sequence A074033 in Neil J. Sloane's database of integer sequences.
Column (1,1),(a,b),(b,a) is sequence A074034 in Neil J. Sloane's database of integer sequences.
Column (1,a),(1,b),(a,1),(a,a),(b,1),(b,b) is sequence A074035 in Neil J. Sloane's database of integer sequences.

Data source: Entries for n=1,2,...,9 were done by exhaustive Maple program (also n=10 entries (0,x)). For n odd entries match corresponding entries on the Lyndon words over F₄ page via a theorem of Miers and Ruskey. Some of the others are educated guesses.

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:13 PDT.
There have been 43 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.

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

Examples:

Further Notes:

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