The Combinatorial Object Server

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

Enumeration (OEIS)

• The number $L(n;k)$ of length $n$ binary Lyndon words of density $k$ is \[ L(n;k)=\frac{1}{n}\sum_{d\vert \gcd(n,k)} \mu(d)\binom{n/d}{k/d}. \] Let $S$ be a subset of $\{0,1,\ldots,n\}$ and let \[ e(S)=\sum_{k\text{ in }S} L(n;k). \]
• Column (0,0) has value $e(\{k \text{ such that } k+n = 0 \pmod{4}\})$, which is OEIS A042980.
• Column (0,1) has value $e(\{k \text{ such that } k+n = 1 \pmod{4}\})$, which is OEIS A042979.
• Column (1,0) has value $e(\{k \text{ such that } k+n = 2 \pmod{4}\})$, which is OEIS A042981.
• Column (1,1) has value $e(\{k \text{ such that } k+n = 3 \pmod{4}\})$, which is OEIS A042982.

References

• [CMR+03] K. Cattell, C. R. Miers, F. Ruskey, J. Sawada, and M. Serra. The number of irreducible polynomials over GF(2) with given trace and subtrace. J. Combin. Math. Combin. Comput., 47:31–64, 2003.