The number of elements of GF(2ⁿ)
with given trace and subtrace.

If a is an element of GF(2ⁿ), then the (absolute) trace of a is

Tr(a) = a + a² + a⁴ + ··· + a^{2^n-1}.

Alternatively, we could define Tr(a) to be the coefficient of x^n-1 in the (characteristic) polynomial

p(x) = (x - a) (x - a²) (x - a⁴ ) ··· (x - a^{2^n-1}).

The subtrace of a is the coefficient of x^n-2 in p(x). The coefficients of p(x) are guaranteed to be elements of GF(2), so the trace and subtrace are elements of GF(2) (i.e., the value is 0 or 1).

	Binomial Coeffient Sum				(trace,subtrace)
n	0	1	2	3	(0,0)	(0,1)	(1,0)	(1,1)
0	1	0	0	0	0	1	0	0
1	1	1	0	0	1	0	1	0
2	1	2	1	0	1	1	0	2
3	1	3	3	1	1	3	3	1
4	2	4	6	4	6	2	4	4
5	6	6	10	10	6	10	6	10
6	16	12	16	20	16	16	20	12
7	36	28	28	36	36	28	28	36
8	72	64	56	64	56	72	64	64
9	136	136	120	120	136	120	136	120
10	256	272	256	240	256	256	240	272
11	496	528	528	496	496	528	528	496
12	992	1024	1056	1024	1056	992	1024	1024
13	2016	2016	2080	2080	2016	2080	2016	2080
14	4096	4032	4096	4160	4096	4096	4160	4032
15	8256	8128	8128	8256	8256	8128	8128	8256
16	16512	16384	16256	16384	16256	16512	16384	16384
17	32896	32896	32640	32640	32896	32640	32896	32640
18	65536	65792	65536	65280	65536	65536	65280	65792
19	130816	131328	131328	130816	130816	131328	131328	130816
20	261632	262144	262656	262144	262656	261632	262144	262144
21	523776	523776	524800	524800	523776	524800	523776	524800
22	1048576	1047552	1048576	1049600	1048576	1048576	1049600	1047552
23	2098176	2096128	2096128	2098176	2098176	2096128	2096128	2098176
24	4196352	4194304	4192256	4194304	4192256	4196352	4194304	4194304

Notes:

The column labelled 0 has entries ( ⁿ₀ ) + ( ⁿ₄ ) + ( ⁿ₈ ) + ··· ,
which is also equal to the (0,1) column when n is even and the (0,0) column when n is odd.
Column 0 is sequence A038503 in Neil J. Sloane's database of integer sequences.
The column labelled 1 has entries ( ⁿ₁ ) + ( ⁿ₅ ) + ( ⁿ₉ ) + ··· ,
which is also equal to the (1,1) column when n is even and the (1,0) column when n is odd.
Column 1 is sequence A038504 in Neil J. Sloane's database of integer sequences.
The column labelled 2 has entries ( ⁿ₂ ) + ( ⁿ₆ ) + ( ⁿ₁₀ ) + ··· ,
which is also equal to the (0,0) column when n is even and the (0,1) column when n is odd.
Column 2 is sequence A038505 in Neil J. Sloane's database of integer sequences.
The column labelled 3 has entries ( ⁿ₃ ) + ( ⁿ₇ ) + ( ⁿ₁₁ ) + ··· ,
which is also equal to the (1,0) column when n is even and the (1,1) column when n is odd.
Column 3 is sequence A038506 in Neil J. Sloane's database of integer sequences.
Column (0,0) is sequence A038518 in Neil J. Sloane's database of integer sequences.
Column (0,1) is sequence A038519 in Neil J. Sloane's database of integer sequences.
Column (1,0) is sequence A038520 in Neil J. Sloane's database of integer sequences.
Column (1,1) is sequence A038521 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, manuscript, 1998.

The entries in the above table can be expressed as the sum of two powers of 2. Let m be the floor of n/2. Then the entry of the first four columns are 2^n-2 + s 2^m-1, where s is 0, +1, or -1, depending on the corresponding entry from the table below.

	Coeff. Sum
n mod 8	0	1	2	3
0	+	0	-	0
1	+	+	-	-
2	0	+	0	-
3	-	+	+	-
4	-	0	+	0
5	-	-	+	+
6	0	-	0	+
7	+	-	-	+

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 2979 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.

The number of elements of GF(2n) with given trace and subtrace.

The number of elements of GF(2ⁿ)
with given trace and subtrace.