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?

  • 2
    $\begingroup$ Aren't there are 32 quintics in F_2[x]? $\endgroup$ – Will Dana Dec 22 '11 at 20:33
  • $\begingroup$ Sure. Sorry! And to boot I neglected to count those with irreducible quartic factors in a comment that is best forgotten ;-) $\endgroup$ – 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.)

  • $\begingroup$ Amazing! Thank you very much. $\endgroup$ – Will Dana Dec 22 '11 at 20:32
  • $\begingroup$ 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)$? $\endgroup$ – Patrick Da Silva Dec 22 '11 at 20:54
  • 1
    $\begingroup$ @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 . $\endgroup$ – Qiaochu Yuan Dec 22 '11 at 20:58
  • $\begingroup$ 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 $\endgroup$ – Patrick Da Silva Dec 22 '11 at 21:00
  • $\begingroup$ How did you go to "Hence for n≥1 (n>1 I think) there are q^n−q^n−1=(1−1q)q^n monic squarefree polynomials of degree n ..." from the previous line? $\endgroup$ – user33646 Jun 13 '12 at 23:07

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$$

  • 1
    $\begingroup$ @QiaochuYuan I have posted a simpler combinatorial proof. Please do look at it and tell me if there's any mistake. Thanks. $\endgroup$ – BharatRam Jul 29 '16 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.