# Monic irreducible polynomials over $GF(k)$ with given trace

The trace of a degree $n$ polynomial in $x$ is the coefficient of $x^{n-1}$. A polynomial is irreducible if it cannot be factored. A polynomial is monic if the leading coefficient is 1. Below we use $a=\operatorname{root}(x^2+x+1)$ and $b=1+a$.

 (trace) $GF(2)$ $GF(3)$ $GF(4)$ $GF(5)$ $n$ 1 0 1,2 0 1,$a$,$b$ 0 1,2,3,4 0 1 1 1 1 1 1 1 1 1 2 1 0 1 1 2 0 2 2 3 1 1 3 2 5 5 8 8 4 2 1 6 6 16 12 30 30 5 3 3 16 16 51 51 125 124 6 5 4 39 38 170 160 516 516 7 9 9 104 104 585 585 2232 2232 8 16 14 270 270 2048 2016 9750 9750 9 28 28 729 726 7280 7280 43400 43400 10 51 48 1960 1960 26214 26112 195250 195248 11 93 93 5368 5368 95325 95325 887784 887784 12 170 165 14742 14736 349520 349180 4068740 4068740 13 315 315 40880 40880 1290555 1290555 18780048 18780048 14 585 576 113828 113828 4793490 4792320 87191964 87191964 15 1091 1091 318864 318848 17895679 17895679 406901000 406900992 16 2048 2032 896670 896670 67108864 67104768 1907343750 1907343750

## Examples

The two monic irreducible polynomials over GF(4) with trace $a$, where $a$ is a root of $x^2+x+1$, are $x^2+ax+1$ and $x^2+ax+a$.

## Enumeration (OEIS)

• The number of degree $n$ trace 1 irreducible polynomials over $GF(k)$ is equal to the number of $k$-ary Lyndon words of length $n$ whose characters sum to 1 mod $k$.
• The number $I_k(n;1)$ of trace 1 monic irreducible polynomials over $GF(k)$ is $I_k(n;1)=\frac{1}{kn}\sum_{d\vert n} [\gcd(d,k)=1] \mu(d) k^{n/d}.$ Here $[P]$ is $1$ if $P$ is true, and is $0$ if $P$ is false. If $k$ is a power of prime $p$, then the condition $[\gcd(d,k)=1]$ is equivalent to $[p\text{ does not divide }d]$. The number of irreducible polynomials with given trace were first counted by Carlitz [Car52]. The expression given above is from Ruskey, Miers, and Sawada [RMS01].
• The number of polynomials of degree $n$ over $GF(k)$ with a given trace is the same for any non-zero value of the trace. If $k$ is a power of the prime $p$, then the number with zero trace is equal to the number with any given non-zero trace if $p$ is not a divisor of $n$ (or $n=1$).
• The $GF(2)$ trace 1 column is OEIS A000048.
• The $GF(2)$ trace 0 column is OEIS A051841.
• The $GF(3)$ trace 0 column is OEIS A046209.
• The $GF(3)$ trace 1,2 column is OEIS A046211.
• The $GF(4)$ trace 0 column is OEIS A054661.
• The $GF(4)$ trace 1,$a$,$b$ column is OEIS A054660.
• The $GF(5)$ trace 0 column is OEIS A054663.
• The $GF(5)$ trace 1,2,3,4 column is OEIS A054662.

## References

• [Car52] L. Carlitz. A theorem of Dickson on irreducible polynomials. Proc. Amer. Math. Soc., 3:693–700, 1952.
• [RMS01] F. Ruskey, C. R. Miers, and J. Sawada. The number of irreducible polynomials and Lyndon words with given trace. SIAM J. Discrete Math., 14(2):240–245, 2001.