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.