# Squarefree polynomials over finite fields

I'm trying to figure out how many squarefree polynomials there are of a fixed degree over $\mathbb{F}_2$ specifically (and in general, over any finite field). Looking at some low-degree examples seems to suggest that half of the polynomials of any given degree are squarefree, but I'm not sure how to prove this, or whether the pattern continues at all. I'm considering the possibility of using the formal derivative, and the fact that a polynomial is relatively prime to its formal derivative iff it is squarefree, but I don't see how to proceed with this. So is there a known formula?

-
Aren't there are 32 quintics in F_2[x]? – Will Dana Dec 22 '11 at 20:33
Sure. Sorry! And to boot I neglected to count those with irreducible quartic factors in a comment that is best forgotten ;-) – Jyrki Lahtonen Dec 22 '11 at 20:36

Recall that $$M(n, q) = \frac{1}{n} \sum_{d | n} \mu(d) q^{n/d}$$

is the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q$. The statement that there are $q^n$ monic polynomials of degree $n$ over $\mathbb{F}_q$ can then be written as the generating function identity $$\zeta(t) = \prod_{n \ge 1} \frac{1}{(1 - t^n)^{M(n, q)}} = \sum_{n \ge 0} q^n t^n = \frac{1}{1 - qt}$$

which is known as the cyclotomic identity and is the analogue for $\mathbb{F}_q[t]$ of the Euler product of the Riemann zeta function. If we instead want to count the number $s_n$ of squarefree monic polynomials of degree $n$ over $\mathbb{F}_q$, we want to work out the generating function $$\sum s_n t^n = \prod_{n \ge 1} (1 + t^n)^{M(n, q)}.$$

But by inspection this is just $$\frac{\zeta(t)}{\zeta(t^2)} = \frac{1 - qt^2}{1 - qt} = 1 + \sum_{n \ge 1} (q^n - q^{n-1}) t^n.$$

(The generating function identity $\zeta(t) = \zeta(t^2) \sum s_n t^n$ merely expresses the fact that every monic polynomial can be uniquely factored into its largest square factor and its squarefree part.)

Hence for $n \ge 1$ there are $q^n - q^{n-1} = \left( 1 - \frac{1}{q} \right) q^n$ monic squarefree polynomials of degree $n$ over $\mathbb{F}_q$. Jordan Ellenberg wrote a great blog post over at Quomodocumque explaining how this is related to the braid group and the analogous question about squarefree integers here.

(Note that you don't actually have to know the closed form of $M(n, q)$ for the above argument to work; I included it for the sake of concreteness.)

-
Amazing! Thank you very much. – Will Dana Dec 22 '11 at 20:32
+1: Very nice, indeed! – Jyrki Lahtonen Dec 22 '11 at 20:39
Could you care explaining the closed form of $M(n,q)$? I'm not really seeing it. And I think the $\mu(n)$ in the sum is actually a $\mu(d)$? – Patrick Da Silva Dec 22 '11 at 20:54
@Patrick: as I said, it doesn't actually matter for this problem, but it falls out of the cyclotomic identity after Mobius inversion; more concretely, counting the number of elements of $\mathbb{F}_{q^n}$ according to the degree of their minimal polynomial over $\mathbb{F}_q$ gives $q^n = \sum_{d | n} d M(d, q)$ and Mobius inversion gives the result. See also en.wikipedia.org/wiki/Necklace_polynomial . – Qiaochu Yuan Dec 22 '11 at 20:58
Hm. I didn't even think about working it out. Thanks. The sum wasn't useful for this problem but I liked the sum so I asked =P – Patrick Da Silva Dec 22 '11 at 21:00