Squarefree polynomials over finite fields

Solution 1:

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.)

Solution 2:

I am five years late, but I had the same question. While Qiaochu's solution is neat and introduces interesting tools like zeta functions, the answer $q^d-q^{d-1}$ somehow seems teasingly combinatorial. Like Ofir pointed out, it almost seems magical.

I have an attempt at a more intuitive combinatorial solution without using zeta functions and cyclotomic identities. Please do check it out and tell me if there is any mistake. At some level, it might be a restatement of Qiaochu's proof, but in simpler language.

So we want to count the number of square free monic polynomials in $\mathbb{F}_q[X]$ of degree $d$. Denote this number by $S_{q}(d)$. The only important fact we shall use is that every monic polynomial $f(X) \in \mathbb{F}_q[X]$ can be $uniquely$ expressed as $$f(X)=r(X)^2.s(X)$$ where $r(X),s(X)$ are monic, and $s(X)$ is square-free. This result is folklore, but quite intuitive. The uniqueness here is essential to our counting.

Now we can build monic polynomials of degree $d$ by picking an arbitrary monic polynomial of degree $k$ for $0 \leq k \leq \lfloor d/2 \rfloor$ and a square-free polynomial of degree $d-2k$ and multiplying the square of the former with the latter (the uniqueness of the expression comes into play here in counting the possibilities). At this juncture, we would have to take cases based on whether $d$ is even or odd, and count accordingly. I'll explore the case of $d$ being even (the other case is conceptually the same).

Since $d$ is even, fix an even $k$ at most $d$. Then we have a recurrence $$S_{q}(d) + S_{q}(d-2) q^{1} + S_{q}(d-4)q^{2}+ \dots + q^{\frac{d}{2}}=\sum \limits_{k=0}^{d/2} S_{q}(d-2k) q^k = q^d$$ Note that $S_{q}(0)=1$ (that is, the only square-free monic polynomial of degree $0$ is the constant polynomial $1$). A simple induction can now be used to construct $S_{q}(d)$ from $S_{q}(d-2),S_{q}(d-4),\dots,1$. In fact, one can observe that with the induction hypothesis that $S_{q}(d-2k)=q^{d-2k}-q^{d-2k-1}$ for every $0 \leq k \leq d/2$ every summand in the above recurrence is of the form $q^{d-k}-q^{d-k-1}$ and so the sum above is telescopic and simplifies to $$S_{q}(d) + q^{d-1}=q^d$$