# Elements of $GF(2^n)$ with given trace and subtrace

If $a$ is an element of $GF(2^n)$, then the (absolute) trace of $a$ is $\operatorname{tr}(a)=a+a^2+a^4+\cdots+a^{2^{n-1}}.$ Alternatively, we could define $\operatorname{tr}(a)$ to be the negation of the coefficient of $x^{n-1}$ in the (characteristic) polynomial $p(x) = (x - a) (x - a^2) (x - a^4) \cdots (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).

0 1 2 3 (0,0) (0,1) (1,0) (1,1) binomial coeffient sum (trace,subtrace) n 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 2 1 0 1 1 0 2 1 3 3 1 1 3 3 1 2 4 6 4 6 2 4 4 6 6 10 10 6 10 6 10 16 12 16 20 16 16 20 12 36 28 28 36 36 28 28 36 72 64 56 64 56 72 64 64 136 136 120 120 136 120 136 120 256 272 256 240 256 256 240 272 496 528 528 496 496 528 528 496 992 1024 1056 1024 1056 992 1024 1024 2016 2016 2080 2080 2016 2080 2016 2080 4096 4032 4096 4160 4096 4096 4160 4032 8256 8128 8128 8256 8256 8128 8128 8256 16512 16384 16256 16384 16256 16512 16384 16384 32896 32896 32640 32640 32896 32640 32896 32640 65536 65792 65536 65280 65536 65536 65280 65792 130816 131328 131328 130816 130816 131328 131328 130816 261632 262144 262656 262144 262656 261632 262144 262144 523776 523776 524800 524800 523776 524800 523776 524800 1048576 1047552 1048576 1049600 1048576 1048576 1049600 1047552 2098176 2096128 2096128 2098176 2098176 2096128 2096128 2098176 4196352 4194304 4192256 4194304 4192256 4196352 4194304 4194304

## Examples

• Let $GF(2^2)$ be defined by the field extension $GF(2)[x]/(1+x+x^2)$. The two elements of $GF(2^2)$ with trace 1 and subtrace 1 are $\{x, 1+x\}$.
• Let $GF(2^3)$ be defined by the field extension $GF(2)[x]/(1+x^2+x^3)$. The three elements of $GF(2^3)$ with trace 1 and subtrace 0 are $\{x, x^2, 1+x+x^2\}$.
• Let $GF(2^4)$ be defined by the field extension $GF(2)[x]/(1+x+x^4)$. The two elements of $GF(2^4)$ with trace 0 and subtrace 1 are $\{x+x^2,1+x+x^2\}$.

## Enumeration (OEIS)

• The column labelled 0 has entries $\binom{n}{0}+\binom{n}{4}+\binom{n}{8}+\cdots$, 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 OEIS A038503.
• The column labelled 1 has entries $\binom{n}{1}+\binom{n}{5}+\binom{n}{9}\cdots$, 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 OEIS A038504.
• The column labelled 2 has entries $\binom{n}{2}+\binom{n}{6}+\binom{n}{10}+\cdots$, 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 OEIS A038505.
• The column labelled 3 has entries $\binom{n}{3}+\binom{n}{7}+\binom{n}{11}+\cdots$, 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 OEIS A038506.
• Column (0,0) is OEIS A038518.
• Column (0,1) is OEIS A038519.
• Column (1,0) is OEIS A038520.
• Column (1,1) is OEIS A038521.
• For proofs of these facts, see [CMR+03].
• The entries in the above table can be expressed as the sum of two powers of 2. Let $m=\lfloor n/2\rfloor$. Then the entry of the first four columns are $2^{n-2}+s2^{m-1}$, where $s$ is 0, +1, or -1, depending on the corresponding entry from the table below. 0 1 2 3 coeff. sum $n$ mod 8 + 0 - 0 + + - - 0 + 0 - - + + - - 0 + 0 - - + + 0 - 0 + + - - +

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