The Combinatorial Object Server

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.