# 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}$.

(0,0) (0,1) (1,0) (1,1) (trace,subtrace) $n$ 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 2 1 2 2 2 3 2 5 4 4 5 6 8 8 8 15 13 15 13 24 24 24 27 45 48 48 45 85 80 85 85 155 160 155 160 288 288 297 288 550 541 541 550 1008 1024 1024 1024 1935 1920 1935 1920 3626 3626 3626 3654 6885 6912 6912 6885 13107 13056 13107 13107 24940 24989 24940 24989 47616 47616 47709 47616 91225 91136 91136 91225 174590 174760 174760 174760 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.