# Where is the flaw in my reasoning about the number of irreducible degree 9 polynomials over $\mathbb F_2$?

I am aware of the formula for the number of polynomials of degree $n$ over a finite field, and that it gives 56 for this particular case, but I wanted to know why the following train of thought is incorrect.

Let $X = \{f(t) \in \mathbb F_2[t] \mid f \text{ is irreducible and of degree } 9\}$

Then $\forall f \in X, f$ is automatically monic and hence separable, since otherwise by irreducibility we would have $f \in \mathbb F_2[t^2]$

From this we see that if $f,g$ were to share a root $\alpha$, then as they are both monic and irreducible, they would both be a minimal polynomial for $\alpha$ over $\mathbb F_2$. Therefore, by uniqueness of minimal polynomials, we have $f,g$.

So now consider $F(t)$, a product of every polynomial in $X$. We must have then that $F$ is separable, and hence the splitting field $L$ of $F$ over $K$ is Galois, cyclic and the degree of the extension is equal to the lowest common multiple of the degrees of all irreducible factors of $F$.

Therefore $|L:K| = 9$ and so we see that every $f(t) \in X$ splits over $L \cong \mathbb F_{2^9}$. Now, as the polynomials of $X$ have distinct roots, and they are separable so they have $9$ distinct roots in a splitting field, we see that $X$ is bounded by $\frac{|\mathbb F_{2^9}|}{9} = \frac{512}{9} = 56\frac{8}{9}$.

Now we need to discount every root in $\mathbb F_2$ in our count, because these have linear minimal polynomials. Further, I thought that you would also need to discount the roots from $\mathbb F_{2^8}$ since by the same logic, the polynomials of degree 8 or less form disjoint collections of roots in this field.

For this reason I actually had the upper bound $\frac{512-2-256}{9} = \frac{254}{9} = 28$.

Now, comparing these two results with the actual answer of $56$, I have two questions:

1. Why was it incorrect to discount $\mathbb F_{2^8}$ when I consider the roots that could actually belong to an irreducible, degree $9$ polynomial?
2. Using this argument I could only conclude that $|X| \leq 56$, but how would I ensure equality? This seems to suggest that for some (incomplete in the sense that some elements may be left out) partition of $\mathbb F_{2^9}$ into $56$ sets of size $9$, that each set corresponds to a polynomial in $\mathbb F_2[t]$, but I can't quite see how we can have this level of confidence in the coefficients of the polynomial. Is there any way to modify this argument in order to find the exact size of $X$ or would I need a different approach?

The finite field $\mathbb F_{p^m}$ is contained in $\mathbb F_{p^n}$ if and only if $m | n$. (Proof of "only if": if $\mathbb F_{p^m} \subset \mathbb F_{p^n}$, then the latter is a vector space over the former, of some finite dimension $d$, and then $(p^m)^d = p^n$ and so $md = n$.) In particular, $\mathbb F_{2^8}$ isn't contained in $\mathbb F_{2^9}$; the only subfields of $\mathbb F_{2^9}$ are $$\mathbb F_2 \subset \mathbb F_{2^3} \subset \mathbb F_{2^9}.$$ So the elements of $\mathbb F_{2^9}$ you need to discount are precisely those contained in $\mathbb F_{2^3}$. Running through your calculation again gives $\frac{512 - 8}{9} = 56$. To show that this is an exact answer, notice that every element of $\mathbb F_{2^9}$ not contained in $\mathbb F_{2^3}$ actually generates $\mathbb F_{2^9}$ as an $\mathbb F_2$-algebra, thus has an irreducible minimal polynomial of degree 9, and each such polynomial corresponds to exactly 9 field elements.